Back to Search
Start Over
FLiMS: A Fast Lightweight 2-Way Merger for Sorting.
- Source :
-
IEEE Transactions on Computers . Dec2022, Vol. 71 Issue 12, p3215-3226. 12p. - Publication Year :
- 2022
-
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 large trees and internalising the workload for fast computation. Also presented are efficient variations of FLiMS for optimizing throughput for skewed datasets, achieving stable sorting or using fewer dequeue signals. Additionally, FLiMS is 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. [ABSTRACT FROM AUTHOR]
- Subjects :
- *MERGERS & acquisitions
*FIELD programmable gate arrays
Subjects
Details
- Language :
- English
- ISSN :
- 00189340
- Volume :
- 71
- Issue :
- 12
- Database :
- Academic Search Index
- Journal :
- IEEE Transactions on Computers
- Publication Type :
- Academic Journal
- Accession number :
- 160620882
- Full Text :
- https://doi.org/10.1109/TC.2022.3146509