Terabyte Sort on FPGA-Accelerated Flash Storage
Authors:
- Sang-Woo JunSJSang-Woo Jun
- Shuotao XuSXShuotao Xu
- ArvindARArvind
- 1 April 2017
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 17-24
Abstract
Sorting is one of the most fundamental and useful applications in computer science, and continues to be an important tool in analyzing large datasets. An important and challenging subclass of sorting problems involves sorting terabyte scale datasets with hundreds of billions of records. The conventional method of sorting such large amounts of data is to distribute the data and computation over a cluster of machines. Such solutions can be fast but are often expensive and power-hungry. In this paper, we propose a solution based on flash storage connected to a collection of FPGA-based sorting accelerators that perform large-scale merge-sort in storage. The accelerators include highly efficient sorting networks and merge trees that use bitonic sorting to emit multiple sorted values every cycle. We show that by appropriate use of accelerators we can remove all the computation bottlenecks so that the end-to-end sorting performance is limited only by the flash storage bandwidth. We demonstrate that our flash-based system matches the performance of existing distributed-cluster solutions of much larger scale. More importantly, our prototype is able to show almost twice the power efficiency compared to the existing Joulesort record holder. An optimized system with less wasteful components is projected to be four times more efficient compared to the current record holder, sorting over 200,000 records per joule of energy.Keywords
This publication has 22 references indexed in Scilit:
- SIMD- and cache-friendly algorithm for sorting an array of structuresProceedings of the VLDB Endowment, 2015
- BlueDBM2015
- Scalable multi-access flash store for big data analytics2014
- Sorting networks on FPGAsThe VLDB Journal, 2011
- Efficient implementation of sorting on multi-core SIMD CPU architectureProceedings of the VLDB Endowment, 2008
- A case for flash memory ssd in enterprise database applications2008
- MapReduceCommunications of the ACM, 2008
- AA-Sort: A New Parallel Sorting Algorithm for Multi-Core SIMD Processors16th International Conference on Parallel Architecture and Compilation Techniques (PACT 2007), 2007
- A piepline sorting chip1987
- VLSI parallel shift sort algorithm and designIntegration, 1984