FLiMS: fast lightweight merge sorter

File Description SizeFormat 
FPT2018_FLiMS_accepted.pdfFile embargoed until 01 January 10000277.26 kBAdobe PDF    Request a copy
Title: FLiMS: fast lightweight merge sorter
Author(s): Papaphilippou, P
Brooks, C
Luk, W
Item 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.
Publication Date: 10-Dec-2018
Date of Acceptance: 16-Sep-2018
URI: http://hdl.handle.net/10044/1/64023
Publisher: IEEE
Copyright Statement: This paper is embargoed until publication.
Sponsor/Funder: Engineering & Physical Science Research Council (E
Commission of the European Communities
Engineering & Physical Science Research Council (E
Dunnhumby Limited
Funder's Grant Number: PO 1977926
516075101 (EP/N031768/1)
Conference Name: 2018 International Conference on Field-Programmable Technology (FPT)
Copyright Statement: This paper is embargoed until publication.
Keywords: bitonic merge
bitonic sort
merge join
distributed algorithms
Publication Status: Accepted
Start Date: 2018-12-10
Finish Date: 2018-12-14
Conference Place: Tenbusu-Naha hall, Okinawa, Japan
Embargo Date: publication subject to indefinite embargo
Appears in Collections:Faculty of Engineering

Items in Spiral are protected by copyright, with all rights reserved, unless otherwise indicated.

Creative Commons