A High-Performance and Cost-Effective Hardware Merge Sorter without Feedback Datapath

We propose a high-performance and cost-effective hardware merge sorter (HMS) without any feedback datapaths in order to develop the fastest hardware sorting accelerator. The operating frequencies of existing HMSs are severely limited by the presence of feedback datapaths. We show the idea of eliminating the feedback datapaths, and propose a concrete architecture adopting the idea and some implementation optimizations. The evaluation results show that our HMS achieves 1.59x throughput improvement with less hardware resources compared to the state-of-the-art HMS.

I. Introduction

Sorting is one of the essential operations used in many areas. With the advent of new technologies such as social networks and IoT devices, there is a significant increase in the size of data to be processed. Therefore, improving the performance of sorting, which has been already researched for several decades, now becomes even more critical.