k-Degree Parallel Comparison-Free Hardware Sorter for Complete Sorting

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.