.png){kind=icon}
.png){kind=icon}
Return
Competition-Style Sorting Networks (CSN): A Framework for Hardware-Based Sorting Operations
.png){kind=icon}
PRE
AI
DOI：10.1109/TC.2025.3605766.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
Sorting operations are considered to be a significant part of any computer system and are widely used in many applications. In applications where sorting has to be efficiently accomplished (i.e., in $O(1)$ time) on small-sized entries, hardware accelerators, such as ASICs, FPGAs, or GPUs, are used to speed up the sorting operations. In the literature, the bitonic sort algorithm (or variants thereof) is still considered to be the most commonly used approach in many hardware sort implementations for decades. However, the time complexity of the bitonic sort is $O((\log(n))^{2})$ for sorting $n$ elements, which does not satisfy the constant-time constraint we demand for our setting. In this paper, we propose competition-style sorting networks (CSNs), a framework for designing hardware-based competition-style class of sorting networks that captures all forms of two-stage sorting networks where the first stage (competition) consists of pairwise comparisons and the second stage (evaluation) ranks the entries and sorts them. To illustrate the utility of this framework, we develop and test one instance of this design, called the Competition Sort Algorithm (CSA), which has a time complexity of $O(1)$, and specifically, one clock cycle. We implemented and tested CSA on both an Intel Cyclone V FPGA and the NVIDIA Quadro T1000 GPU then measured its gain, which combines the trade-offs between the relative speedup and the relative area increase, against the bitonic sort. Our results show that the CSA achieves a significant gain of up to $11.01\times$ on the FPGA and a relative speedup of up to $3.32\times$ on the GPU. We also compare the area and latency of CSA with the bitonic sort algorithm on the FPGA.
Keywords:
Sorting networks
hardware-based sorting
constant-time sorting
hardware accelerators
Journal
IF:
3.8
Papers:
5.3K
Citations:
9.8K