An adaptable high-throughput FPGA merge sorter for accelerating database analytics
File(s)fpl20sorter.pdf (412.16 KB)
Accepted version
Author(s)
Papaphilippou, Philippos
Brooks, Chris
Luk, Wayne
Type
Conference Paper
Abstract
This work improves on the latest research about sorting acceleration on FPGAs. An efficient design is introduced for sorting data that fit on-chip, with the additional functionality to merge sorted sublists recursively, for an input of arbitrary length. While many-leaf mergers are conventionally single-rate, a novel technique in our approach is to use a parallel merge tree only for the latest stages of the merge tree, to enable bandwidth-adapted multi-rate many-leaf merge. Our open-source RTL generator produces sorting peripherals with customisable parallelism and data format. We evaluate our FPGA design as an 128-bit wide peripheral on an MPSoC platform, with a speedup of up to 49 times over the A53 core for sorting, and up to 27 times speedup for our specialized database analytics application.
Date Issued
2020-10-13
Date Acceptance
2020-05-19
Citation
2020 30th International Conference on Field-Programmable Logic and Applications (FPL), 2020, pp.65-72
Publisher
IEEE
Start Page
65
End Page
72
Journal / Book Title
2020 30th International Conference on Field-Programmable Logic and Applications (FPL)
Copyright Statement
© 2020 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.
Sponsor
Dunnhumby Limited
Engineering & Physical Science Research Council (E
Commission of the European Communities
Engineering & Physical Science Research Council (E
Engineering and Physical Sciences Research Council
Grant Number
PO: 250130012887
516075101 (EP/N031768/1)
671653
PO 20131167
EP/L00058X/1, PO 20131167
Source
The International Conference on Field-Programmable Logic and Applications (FPL) 2020
Subjects
FPGA
sorting
generator
database acceleration
mergesort
analytics
high-throughput
stream processing
distinct count
group by
Publication Status
Published
Start Date
2020-08-31
Finish Date
2020-09-04
Coverage Spatial
Gothenburg, Sweden (virtual)
Date Publish Online
2020-10-13