New paper on sorting large data sets with FPGAs to appear at FPGA 2020

Our new paper on using FPGAs to greatly accelerate sorting of large sets of data has been accepeted to appear at FPGA 2020.

This paper, “FPGA-Accelerated Samplesort for Large Data Sets,” was co-authored with Stony Brook PhD students Han Chen and Sergey Madaminov and Prof. Mike Ferdman. A preprint is available here.

Abstract: Sorting is a fundamental operation in many applications such as databases, search, and social networks. Although FPGAs have been shown very effective at sorting data sizes that fit on chip, systems that sort larger data sets by shuffling data on and off chip are bottlenecked by costly merge operations or data transfer time.

We propose a new technique for sorting large data sets, which uses a variant of the samplesort algorithm on a server with a PCIe-connected FPGA. Samplesort avoids merging by randomly sampling values to determine how to partition data into non-overlapping buckets that can be independently sorted. The key to our design is a novel parallel multi-stage hardware partitioner, which is a scalable high-throughput solution that greatly accelerates the samplesort partitioning step. Using samplesort for FPGA-accelerated sorting provides several advantages over mergesort, while also presenting a number of new challenges that we address with cooperation between the FPGA and the software running on the host CPU.

We prototype our design using Amazon Web Services FPGA instances, which pair a Xilinx Virtex UltraScale+ FPGA with a high-performance server. Our experiments demonstrate that our prototype system sorts 230 key-value records with a speed of 7.2 GB/s, limited only by the on-board DRAM capacity and available PCIe bandwidth. When sorting 230 records, our system exhibits a 37.4x speedup over the widely used GNU parallel sort on an 8-thread state-of-the-art CPU.

Speedup This graph illustrates the speedup of our implementation relative to parallel GNU Sort (8 threads). Please see paper for more detail.


This entry was posted on November 22, 2019.