Fast data packet sorting method based on FPGA on-chip RAM

Abstract The study of fast sorting algorithms has long been an enduring research focus. Traditional sorting algorithms often suffer from high time complexity, typically staying at ( n 2 ) or O ( n × log 2 n ). Given the parallel processing advantages of field programmable gate array (FPGA), it has become a popular platform for algorithm acceleration. However, existing hardware sorting acceleration methods remain rooted in classical software algorithm models, merely leveraging hardware for parallel execution, without fully exploring the unique architecture and resources of FPGAs. In response, this paper proposes a fast sorting method that leverages on-chip random-access memory (RAM), uniquely tailored to FPGA characteristics. First, a mapping is established between the key fields of data packets and the on-chip RAM addresses. Then, the data packets are written into RAM based on this mapping, which also inevitably result in some RAM addresses being left empty. Next, a indicator register is maintained to dynamically track which RAM addresses are empty. Finally, the data packets are sequentially read from RAM addresses, and the indicator register helps skip empty addresses to enhance readout efficiency. Due to the inherent ordering of RAM addresses, the data packets become naturally ordered after read. Simulation results confirm that this method can reduce the time complexity to O ( n ), providing a novel solution for fast sorting in real-time data streams.