k-Degree Parallel Comparison-Free Hardware Sorter for Complete Sorting
Sanchita Saha Ray, Surajeet Ghosh · IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems · 2022
This article presents a novel parallel comparison-free hardware sorting architecture that sorts$N$,$n$-bit elements consuming linear worst-case sorting latency of$\mathit {O(N)}$clock-cycles utilizing$k$-parallel clusters. A parallel cluster contains a number of identical blocks utilizing a few fundamental logic components. The architecture achieves a speed-up of${}({n}/[{\lceil {({n}/{k})}\rceil +k}])$over nonparallel architectures. The proposed sorting architecture identifies the largest element in every cycle with smaller clock periods compared to state-of-the-art comparison-free approaches and does not require any kind of preprocessing of the input data set, unlike most of the existing hardware sorters. The experimental result shows the degree of parallelism$(k)$for 16, 32, and 64-bit elements are, respectively, {4}, {4, 5, 6, 7, 8}, and {8} to achieve maximum system throughput. This sorter achieves a throughput of ≈194 Million Elements per second (MEps) for$k=6$and, it is ≈142 MEps for$k=8$to sort 256 elements of 32 and 64-bit, respectively, whereas it is ≈159 MEps for$k = 6$to sort 512 elements of 40 bit.