A Comparison-free Hardware Sorting Engine
Surajeet Ghosh, Shaon Dasgupta, Sanchita Saha Ray · 2019
This paper proposes a novel compare free hardware sorting engine that sorts N numerous data elements in approximately N clock cycles and detects the largest element in the 1st clock cycle. This sorting engine has been designed using N symmetric cascaded blocks those are built using few fundamental logic components. In this architecture, sorting and storing operations are performed in a pipelined manner. The complete design is synthesized for several data sets from pseudorandomly generated data elements to all unique elements to all the same elements, and also from random to completely sorted data elements. It has been observed that, the engine appears impartial to the input ordering. Synthesis results indicate that the proposed approach consumes reasonably low FPGA resource. The architecture is tested considering delay components of 65-nm standard cell library. For sorting 128 to 64K data elements of size 16, 24, and 32 bits at 125 MHz, this architecture takes per-element sorting delay as approximately 5.3 to 8 ns (1 clock cycle), while it takes 7.72 to 11.8 ns (1 to 2 clock cycles) and 10.16 to 15.5 ns (2 clock cycles), respectively. The engine achieves sorting throughput rate as approximately 125 to 200 Million Elements per second (MEps) (16 bit), 85 to 130 MEps (24 bits) and 65 to 98 MEps (32 bits) for sorting 128 to 64K data elements.