FPGA-Based Large-Scale Sorting with Optimized Bandwidth Utilization
Open Access
- 21 March 2025
- journal article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Reconfigurable Technology and Systems
- Vol. 18 (2) , 1-27
Abstract
Fast sorting of large-scale data is an essential task for data centers. In previous works, the existing computational model of sorting kernel still results in lower bandwidth utilization on the external memory bus. And the execution of merge operations in merge sort circuit on FPGAs depends on control commands from the host CPU. In this case, the merge sort circuit is not fully offloaded to hardware layer for acceleration, resulting in a performance loss. We design an on-chip merge sort controller to efficiently command the merge sort process. The proposed controller has the ability to schedule multiple on-chip computing kernels simultaneously in a more efficient mode, thus ensuring that the circuit has a better bandwidth utilization. Meanwhile, fundamental factors affecting the performance of merge sort are studied and analyzed, and we propose a high-performance merge sort architecture. Results show that using the proposed controller-centered architecture, an overall improvement of 20%–30% in sorting throughput can be achieved. Compared with the state-of-the-art previous merge sorting implementation on FPGA, our circuit can achieve 1.22/1.46 \(\times\) speedup.
Keywords
Funding Information
- National Natural Science Foundation of China (61521003)
This publication has 15 references indexed in Scilit:
- The Future of FPGA Acceleration in Datacenters and the CloudACM Transactions on Reconfigurable Technology and Systems, 2022
- FANS: FPGA-Accelerated Near-Storage Sorting2021
- FPGA-Accelerated Samplesort for Large Data Sets2020
- Sorting Large Data Sets with FPGA-Accelerated Samplesort2019
- A High-Performance and Cost-Effective Hardware Merge Sorter without Feedback Datapath2018
- Terabyte Sort on FPGA-Accelerated Flash Storage2017
- Parallel Hardware Merge Sorter2016
- PARADISProceedings of the VLDB Endowment, 2015
- Modular Design of High-Throughput, Low-Latency Sorting UnitsIEEE Transactions on Computers, 2012
- Sorting networks and their applications1968