FPGA-Accelerated Samplesort for Large Data Sets
FPGA-Accelerated Samplesort for Large Data Sets
复制标题
适用于大型数据集的 FPGA 加速采样排序
DOI：
10.1145/3373087.3375304
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Peter Milder
中科院分区：
文献类型：
--
作者：
Han Chen;S. Madaminov;M. Ferdman;Peter Milder
在数据库，搜索和社交网络等许多应用程序中，排序是一个基本操作。尽管FPGA在分类适合芯片的数据大小方面非常有效，但是通过昂贵的合并操作或数据传输时间来瓶颈来对较大的数据集进行对更大的数据集进行排序。我们提出了一种用于对大数据集进行排序的新技术，该技术使用具有PCIE连接的FPGA的服务器上的样品算法的变体。样品避免通过随机采样值合并，以确定如何将数据划分为可以独立分类的非重叠桶。我们设计的关键是一个新颖的平行多阶段硬件分区器，它是一种可扩展的高通量解决方案，可大大加速样品分区步骤。使用样品进行FPGA加速排序，比Mergesort提供了几个优点，同时还提出了许多新的挑战，这些挑战与FPGA与主机CPU上运行的软件之间的合作解决了许多新挑战。我们使用Amazon Web Services FPGA实例原型设计，该实例将Xilinx Virtex Ultrascale+ FPGA与高性能服务器配对。我们的实验表明，我们的原型系统以7.2 GB/s的速度对2^30键值记录进行分类，仅受板上DRAM容量和可用的PCIE带宽的限制。在对2^30记录进行排序时，我们的系统在8线程最新的CPU上表现出37.4倍的速度。
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 2^30 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 2^30 records, our system exhibits a 37.4x speedup over the widely used GNU parallel sort on an 8-thread state-of-the-art CPU.