Search papers, labs, and topics across Lattice.
This paper revisits and evaluates various hardware priority queue architectures on modern FPGA platforms to address performance bottlenecks in latency-sensitive applications. By implementing and rigorously analyzing these architectures, the authors provide a comprehensive comparison that highlights trade-offs in performance, resource utilization, and scalability. The findings reveal that contemporary hardware advancements significantly impact the relevance of older architectures, guiding future design choices in priority queue implementations.
Modern FPGA implementations of hardware priority queues can drastically outperform traditional software methods, revealing critical insights into architectural relevance.
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.
