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 a...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on circuits and systems. II, Express briefs Express briefs, 2020-08, Vol.67 (8), p.1449-1453
Main Authors: Chen, Weijie, Li, Weijun, Yu, Feng
Format: Article
Language:English
Subjects:
Architecture
Computer architecture
Continuity (mathematics)
Field programmable gate array (FPGA)
Field programmable gate arrays
high throughput
low latency
Parallel processing
Registers
Sorting
sorting architecture
Throughput
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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).
ISSN:1549-7747
1558-3791
DOI:10.1109/TCSII.2019.2938892