Access Restriction

Author Alabi, Tolu ♦ Blanchard, Jeffrey D. ♦ Gordon, Bradley ♦ Steinbach, Russel
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©2012
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Computer programming, programs & data
Subject Keyword k-Selection ♦ CUDA ♦ GPGPU ♦ Graphics processing units ♦ Multicore ♦ Order statistics
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}.$
ISSN 10846654
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2012-10-01
Publisher Place New York
e-ISSN 10846654
Journal Journal of Experimental Algorithmics (JEA)
Volume Number 17
Page Count 29
Starting Page 4.1
Ending Page 4.29

Open content in new tab

   Open content in new tab
Source: ACM Digital Library