A Hybrid Pipelined Architecture for High Performance Top-K Sorting on FPGA

We present a hybrid pipelined sorting architecture capable of finding and producing as its output the K largest elements from an input sequence. The architecture consists of a bitonic sorter and L cascaded sorting units. The sorting unit is designed to output P elements during every cycle with the aim of increasing the throughput and lowering the latency. The function of the bitonic sorter is to generate a segmented ordered sequence. The sorting unit processes this sequence to identify and output the P largest elements. Hence, the K=PL largest elements are obtained after the segmented ordered sequence proceeds through L cascaded sorting units. Variable-length and continuous sequences are supported by the proposed sorting architecture. The results of the implementation show that the sorting architecture can achieve a throughput of 22.88 GB/s with P=16 on a state-of-the-art Field Programmable Gate Array (FPGA).