FLiMS: a fast lightweight 2-way merger for sorting
File(s)tc22flimsj_acc (1).pdf (1.06 MB)
Accepted version
Author(s)
Papaphilippou, Philippos
Luk, Wayne
Brooks, Chris
Type
Journal Article
Abstract
In this paper, we present FLiMS, a highly-efficient and simple parallel algorithm for merging two sorted lists residing in banked and/or wide memory. On FPGAs, its implementation uses fewer hardware resources than the state-of-the-art alternatives, due to the reduced number of comparators and elimination of redundant logic found on prior attempts. In combination with the distributed nature of the selector stage, a higher performance is achieved for the same amount of parallelism or higher. This is useful in many applications such as in parallel merge trees to achieve high-throughput sorting, where the resource utilisation of the merger is critical for building larger trees and internalising the workload for faster computation. Also presented are efficient variations of FLiMS for optimizing throughput for skewed datasets, achieving stable sorting or using fewer dequeue signals. FLiMS is also shown to perform well as conventional software on modern CPUs supporting single-instruction multiple-data (SIMD) instructions, surpassing the performance of some standard libraries for sorting.
Date Issued
2022-12-01
Date Acceptance
2022-01-01
Citation
IEEE Transactions on Computers, 2022, 71 (12), pp.3215-3226
ISSN
0018-9340
Publisher
Institute of Electrical and Electronics Engineers (IEEE)
Start Page
3215
End Page
3226
Journal / Book Title
IEEE Transactions on Computers
Volume
71
Issue
12
Copyright Statement
© 2022 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.
Identifier
https://ieeexplore.ieee.org/document/9695338
Publication Status
Published
Date Publish Online
2022-01-27