A Cost-Effective and Scalable Merge Sorter Tree on FPGAs
A Cost-Effective and Scalable Merge Sorter Tree on FPGAs
复制标题
FPGA 上经济高效且可扩展的合并排序树
DOI：
10.1109/candar.2016.0023
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Kenji Kise
中科院分区：
文献类型：
--
作者：
T. Usui;Thiem Van Chu;Kenji Kise
排序是重要的计算内核，应用于图像处理、数据压缩、数据库操作等许多领域。人们已经进行了许多使用 FPGA 加速排序的尝试。其中大多数都是基于归并排序算法。合并排序树是用于大规模排序的树结构体系结构。如果具有 K 个输入叶子的合并排序树合并 N 个元素，则合并阶段会递归执行，因此其时间复杂度为 O(NlogK(N))。因此，为了获得更高的排序性能，增加输入叶子的数量K是有效的。然而，硬件资源的使用是O(K)。有效地实现具有许多输入叶子的合并排序树是很困难的。伊藤等人。最近提出了一种算法，可以将具有 K 个输入叶子的合并排序树的硬件复杂性从 O(K) 降低到 O(log(K))。然而，他们只报告 K 为 8 和 16 时的评估结果。在本文中，我们基于他们的算法提出了一种经济高效且可扩展的合并排序树架构。我们表明，与硬件复杂度为 O(K) 的传统设计相比，我们的设计实现了几乎相同的性能。我们在 Xilinx XC7VX485T-2 FPGA 上实现了具有 1,024 个输入叶的合并排序树，结果表明，与传统设计相比，所提出的架构的逻辑片利用率提高了 52.4 倍，而性能仅下降了 1.31 倍。我们成功实现了一个非常大的合并排序树，具有 4,096 个输入叶子，这是使用传统设计无法实现的。该树实现了每秒 1.49 亿个 64 位元素的合并吞吐量，同时使用 FPGA 的 1.72% 的切片和 7.48% 的块 RAM。
Sorting is an important computation kernel used in a lot of fields such as image processing, data compression, and database operation. There have been many attempts to accelerate sorting using FPGAs. Most of them are based on merge sort algorithm. Merge sorter trees are tree-structured architectures for large-scale sorting. If a merge sorter tree with K input leaves merges N elements, merge phases are performed recursively, so its time complexity is O(NlogK(N)). Hence, to achieve higher sorting performance, it is effective to increase the number of input leaves K. However, the hardware resource usage is O(K). It is difficult to efficiently implement a merge sorter tree with many input leaves. Ito et al. have recently proposed an algorithm which can reduce the hardware complexity of a merge sorter tree with K input leaves from O(K) to O(log(K)). However, they only report the evaluation results when K is 8 and 16. In this paper, we propose a cost-effective and scalable merge sorter tree architecture based on their algorithm. We show that our design achieves almost the same performance compared to the conventional design of which the hardware complexity is O(K). We implement a merge sorter tree with 1,024 input leaves on a Xilinx XC7VX485T-2 FPGA and show that the proposed architecture has 52.4x better logic slice utilization with only 1.31x performance degradation compared with the conventional design. We succeed in implementing a very large merge sorter tree with 4,096 input leaves which cannot be implemented using the conventional design. This tree achieves a merging throughput of 149 million 64-bit elements per second while using 1.72% of slices and 7.48% of Block RAMs of the FPGA.
DOI：
10.1145/2678373.2665678
发表时间：
2014-10
期刊：
2014 ACM/IEEE 41st International Symposium on Computer Architecture (ISCA)
影响因子：
--
作者：
Andrew Putnam;Adrian M. Caulfield;Eric S. Chung;Derek Chiou;Kypros Constantinides;J. Demme;H. Esmaeilzadeh;J. Fowers;Gopi Prashanth Gopal;J. Gray;M. Haselman;S. Hauck;Stephen Heil;Amir Hormati;Joo-Young Kim;S. Lanka;J. Larus;Eric Peterson;Simon Pope;Aaron Smith;J. Thong;Phillip Yi Xiao;D. Burger
通讯作者：
Andrew Putnam;Adrian M. Caulfield;Eric S. Chung;Derek Chiou;Kypros Constantinides;J. Demme;H. Esmaeilzadeh;J. Fowers;Gopi Prashanth Gopal;J. Gray;M. Haselman;S. Hauck;Stephen Heil;Amir Hormati;Joo-Young Kim;S. Lanka;J. Larus;Eric Peterson;Simon Pope;Aaron Smith;J. Thong;Phillip Yi Xiao;D. Burger