A scalable, high-performance customized priority queue
A scalable, high-performance customized priority queue
复制标题
DOI：
10.1109/fpl.2014.6927413
复制
发表时间：
2014-10
期刊：
影响因子：
--
通讯作者：
Muhuan Huang;Kevin T. Lim;J. Cong
中科院分区：
文献类型：
--
作者：
Muhuan Huang;Kevin T. Lim;J. Cong
优先级队列是一种抽象数据结构，其中每个元素都与一个优先级相关联，并且总是首先从队列中检索最高优先级的元素。该数据结构在数据库中广泛使用，包括合并排序的最后阶段，预测合并排序的流数据的预读I/O，以及替换选择排序。典型的软件实现使用基于平衡二叉树的结构，为入队和出队操作提供O（log N）时间。为了提高性能，我们提出了几种可扩展且基于FPGA的高速优先级队列实现。我们的见解是，上面列出的应用程序主要通过“替换”操作使用优先级队列，该操作删除最高优先级的元素并将新元素放入队列中。因此，我们的设计是为这种操作定制的，允许一个简单和可扩展的架构。我们实现了三个优先级队列设计，包括使用基于寄存器的阵列，基于寄存器的树，和基于BRAM的树，这有不同的好处和吞吐量，频率和最大大小的权衡。更重要的是，所有的设计在替换操作之间都实现了O（1）时间。为了结合我们的设计最好的方面，我们提出了一个混合优先级队列（H-PQ），它结合了基于寄存器的阵列与多个BRAM为基础的树。平均而言，这种设计提供了对队列中顶部项目的非常快的访问时间（通过基于寄存器的阵列），同时扩展到大的优先级队列大小（通过基于BRAM的树）。在我们的评估中，我们发现与Xeon CPU实现相比，H-PQ实现了4.3倍的加速和21.5倍的能效。
Priority queues are abstract data structures where each element is associated with a priority, and the highest priority element is always retrieved first from the queue. The data structure is widely used within databases, including the last stage of a merge-sort, forecasting read-ahead I/O to stream data for the merge-sort, and replacement selection sort. Typical software implementations use a balanced binary tree-based structure, providing O(log N) time for both enqueue and dequeue operations. To improve the performance, we propose several scalable and high-speed FPGA-based implementations of a priority queue. Our insight is that the above listed applications primarily use priority queues through “replace” operations, which remove the highest priority element and place a new element into the queue. Thus, our designs are customized for this operation, allowing for a simple and scalable architecture. We implement three priority queue designs, including use of a register-based array, register-based tree, and BRAM-based tree, which have different benefits and trade-offs of throughput, frequency, and maximum size. More importantly, all designs achieve O(1) time between replace operations. To incorporate the best aspects of our designs, we propose a Hybrid Priority Queue (H-PQ), which combines a register-based array with multiple BRAM-based trees. This design provides, on average, very fast access times to the top items in the queue (through the register-based array), while scaling to large priority queue sizes (through the BRAM-based trees). In our evaluations, we find that H-PQ achieves 4.3x speedup and 21.5x energy efficiency, compared with the Xeon CPU implementations.