A Streaming High-Throughput Linear Sorter System with Contention Buffering

Popular sorting algorithms do not translate wellinto hardware implementations. Instead, hardware-based solutionslike sorting networks, systolic sorters, and linear sortersexploit parallelism to increase sorting efficiency. Linear sorters,built from identical nodes with simple control, have less areaand latency than sorting networks, but they are limited intheir throughput. We present a system composed of multiplelinear sorters acting in parallel to increase overall throughput. Interleaving is used to increase bandwidth and allow sortingof multiple values per clock cycle, and the amount ofinterleaving and depth of the linear sorters can be adaptedto suit specific applications. Contention for available linearsorters in the system is solved through the use of buffers thataccumulate conflicting requests, dispatching them in bulk toreduce latency penalties. Implementation of this system into afield programmable gate array (FPGA) results in a speedupof 68 compared to a MicroBlaze processor running quicksort