Optimal Parallel Hardware K-Sorter and Top K-Sorter, with FPGA Implementations
Naoyuki Matsumoto, Koji Nakano, Yasuaki Ito · 2015
This paper presents a FIFO-based parallel merge sorter optimized for the latest FPGA. More specifically, we show a sorter that sorts K keys in latency K+log2K-1 using log2K comparators. It uses K/M +log2K +log2M-1 memory blocks with capacity M to implement FIFOs. It receives K keys one by one in every clock cycle and outputs the sorted sequence of them from K + log2K - 1 clock cycles after. Since K clock cycles are necessary to input all K keys, our sorter is almost optimal in terms of the latency. Also, since the total FIFO capacity is only K +M log2K +M log2M -M and at least K keys must be stored in the sorter, our sorter is also almost optimal in terms of the total FIFO capacity if M is small. This paper also presents top K-sorter, which outputs top K keys in N input keys for any large N. Our top K-sorter runs in latency N + log2K using log2K + 1 comparators. It uses memory blocks of size M and the total FIFO capacity is only 2K+M log2K +M log2M - 2M. Quite surprisingly, the total FIFO capacity is independent of N. Also, since the latency must be at least N, that of our top Ksorter is almost optimal in terms of the latency. Finally, we have implemented our K-sorter and top K-sorter in a Xilinx Virtex-7 FPGA using built-in Distributed RAMs and Block RAMs. The implementation results show that our K-sorter reduces the used memory resources by half, and both K-sorter and top K-sorter are practical and efficient.