Fast k-selection algorithms for graphics processing units
Authors:
Open Access
- 1 July 2012
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in ACM Journal of Experimental Algorithmics
- Vol. 17
Abstract
Finding the kth-largest value in a list of n values is a well-studied problem for which many algorithms have been proposed. A naïve approach is to sort the list and then simply select the kth term in the sorted list. However, when the sorted list is not needed, this method does quite a bit of unnecessary work. Although sorting can be accomplished efficiently when working with a graphics processing unit (GPU), this article proposes two GPU algorithms, radixSelect and bucketSelect, which are several times faster than sorting the vector. As the problem size grows so does the time savings of these algorithms with a sixfold speed-up over GPU sorting for float vectors larger than 2 24 and for double vectors larger than 2 20 , ultimately reaching a 19.1 times speed-up for double vectors of length 2 28 .Keywords
Funding Information
- Division of Mathematical Sciences (DMS-1112612)
This publication has 10 references indexed in Scilit:
- Randomized selection on the GPU2011
- HIGH PERFORMANCE AND SCALABLE RADIX SORTING: A CASE STUDY OF IMPLEMENTING DYNAMIC PARALLELISM FOR GPU COMPUTINGParallel Processing Letters, 2011
- Hard Thresholding Pursuit: An Algorithm for Compressive SensingSIAM Journal on Numerical Analysis, 2011
- Normalized Iterative Hard Thresholding: Guaranteed Stability and PerformanceIEEE Journal of Selected Topics in Signal Processing, 2010
- GPU-QuicksortACM Journal of Experimental Algorithmics, 2009
- Subspace Pursuit for Compressive Sensing Signal ReconstructionIEEE Transactions on Information Theory, 2009
- CoSaMP: Iterative signal recovery from incomplete and inaccurate samplesApplied and Computational Harmonic Analysis, 2009
- Selection by distributive partitioningInformation Processing Letters, 1980
- Algorithm 64: QuicksortCommunications of the ACM, 1961
- Algorithm 65: findCommunications of the ACM, 1961