Worst Case O(N) Comparison-Free Hardware Sorting Engine
Sanchita Saha Ray, Dulal Adak, Surajeet Ghosh · IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems · 2021
This article proposes a novel comparison-free hardware sorting engine that sorts$N$unique$n$-bit elements (irrespective of signed and unsigned) consuming linear sorting latency of$O(N)$clock cycles. It can even efficiently sort$N$data elements with a nonzero duplicity rate in less than$O(N)$clock cycles. This sorting engine is designed using$n$-symmetric cascaded blocks utilizing few fundamental logic components. The entire design is synthesized for several data sets from pseudorandomly generated data elements to unique elements, and also from random to completely sorted elements with various duplicity rates. The architecture appears impartial with respect to ordering of elements. Synthesis results indicate that the proposed approach consumes reasonably lower field programmable gate array resources than existing approaches. The architecture takes per-element sorting latency in sorting 512 unique signed elements as 22.56 ns (48 bit) and takes 26.80 ns (64 bit) to sort 256 unique signed elements. The engine achieves sorting throughput rates as$\approx 117$-to-142 Million-Elements-per-second (MEps) (16 bit), 79-to-97 MEps (24 bit) for sorting 256-to-1K, whereas 66-to-73 MEps (32 bit) and 44-to-49 MEps (48 bit) for sorting 256-to-512 elements. However, it is 37 MEps (64 bit) in sorting 256 signed elements. This architecture consumes$\approx 1.52~\mu \text{W}$for the unique signed numbers (SNs) as per-byte processing power and$\approx 1.55~\mu \text{W}$for the SNs with nonzero duplicity rates.