FLiMS: fast lightweight merge sorter
File(s)FPT2018_FLiMS_accepted.pdf (277.26 KB)
Accepted version
Author(s)
Papaphilippou, Philippos
Brooks, Chris
Luk, Wayne
Type
Conference Paper
Abstract
We have developed a highly-efficient and simple parallel hardware design for merging two sorted lists residing in banked (or multi-ported) memory. The FPGA implementation uses half the hardware resources required for implementing the current state-of-the-art architecture. This is achieved with better performance and half the latency, for the same amount of parallelism. The challenges for the merge operations in FPGAs have been the low clock frequency due to the feedback datapath of the merger being the critical path for timing, and also the high resource utilisation in recent attempts to eliminate/remove the feedback datapath. Our solution uses a modified version of the bitonic merge block, as found in a bitonic sorter, repurposed for performing parallel merge for streaming data. As with the state-of-the-art, it can be considered feedback-less since it only nests one parallel comparison for any desired level of parallelism. This leads to high operating frequency designs, 1.3 times higher than the previous best on our test platform. Since the new design uses 2 times fewer hardware resources, it allows more parallelism and leaves room for additional logic.
Date Issued
2019-06-20
Date Acceptance
2018-09-16
Citation
2019
Publisher
IEEE
Copyright Statement
© 2019 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
Identifier
https://ieeexplore.ieee.org/document/8742328
Grant Number
PO: 250130008264
516075101 (EP/N031768/1)
671653
20104124
Source
2018 International Conference on Field-Programmable Technology (FPT)
Subjects
bitonic merge
bitonic sort
merge join
parallel
FPGA
databases
operators
distributed algorithms
Zynq
SIMD
Publication Status
Published
Start Date
2018-12-10
Finish Date
2018-12-14
Coverage Spatial
Tenbusu-Naha hall, Okinawa, Japan
Date Publish Online
2019-06-20