Competition-Style Sorting Networks (CSN): A Framework for Hardware-Based Sorting Operations

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 <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">O</i>(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 <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">O</i>((log(<italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</i>))<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup>) for sorting <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</i> elements, which does not satisfy the constant-time constraint we demand for our setting. In this paper, we propose <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">competition-style sorting networks</i> (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 <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">O</i>(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 <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">gain</i>, 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× on the FPGA and a relative speedup of up to 3.32× on the GPU. We also compare the area, power, and latency of CSA with the bitonic sort algorithm on the FPGA.