Competition-style Sorting Networks

Sorting is a foundational operation in database systems, network packet processing, scientific computing, and hardware accelerators. General-purpose software sorting algorithms are well-understood, but hardware implementations demand different design criteria: fixed latency, high throughput, pipelineable structure, and efficient mapping to FPGA or ASIC resources. Data-dependent branching and irregular memory access patterns make software sorting algorithms generally unsuitable for direct hardware implementation.

This project defined the class of Competition-based Sorting Networks (CSN) — a new framework for hardware accelerators designed to optimise sorting operations. The central contribution is the Competition Sort Algorithm (CSA), which was evaluated against the well-known bitonic sort on both FPGA and GPU platforms. The CSA achieves a gain of up to 11× over bitonic sort on FPGA for small input sizes and a relative speedup of up to 3.32× on GPU.

The project was funded by Kuwait University Research Sector (grant EO03/21) and ran from July 2022 to November 2023. The research produced a journal paper published in the IEEE Transactions on Computers. Future directions include ASIC implementations for larger datasets and embedding a hardware-based sorting unit as a special function unit (SFU) in modern microprocessors.