A Hardware Design Generator of High-Performance FIFO-based Linear Insertion Streaming Sorters

M.L. Petrović, V.M. Milovanović (Univ. Kragujevac and NOVELIC, Serbia)

Sorting is an essential operation in many scientific and data processing applications, therefore it is significant to improve sorting efficiency. This paper demonstrates the hardware architecture of the fully streaming FIFO-based linear insertion sorters that provides high-performance sorting. Parameterizable and run-time reconfigurable sorters based on the insertion sort algorithm are written in the Chisel hardware design language. The proposed linear insertion sorter design generator supports a wide range of parameter settings such as sorting data type and data width, sorting directions, compile and run-time reconfigurable sorter depth, and memory type, among others, thus enabling fast and efficient agile design space exploration. A convenient method for testing the presented linear sorter generator on a commercially available FPGA platform is demonstrated. A comparison with other FIFO-based linear insertion sorters is given both in terms of resource utilization and sorting performance.