Revisiting Hardware Priority Queue Architectures
Priority queues - data structures that serve elements based on priority rather than insertion order - are fundamental in a wide range of applications, including operating systems, graph algorithms, and data compression. Software implementations, typically based on binary heaps with O(log N) complexity, are sufficient for many scenarios; however they can become performance bottlenecks in latency-sensitive domains such as networking and robotics. Hardware-based priority queues exploit parallelism to significantly reduce operation latency, delivering critical performance improvements in latency-sensitive applications. Despite the breadth of prior work on hardware priority queues, two major challenges remain. First, many foundational architectures were proposed and studied years ago, calling into question their relevance given modern hardware advancements. Second, comprehensive comparisons across different architectures are lacking, making it difficult to evaluate trade-offs in performance, resource utilization, and scalability. This paper addresses both gaps by implementing and evaluating several representative hardware priority queue architectures on modern FPGA platforms and providing a quantitative analysis to guide future design choices. All implementations, tests, and analyses are available through our open-source library at https://github.com/realise-lab/hwpq.