Fast K-selection Algorithms for Graphics Processing Units

Tolu Alabi, Jeffrey D. Blanchard, Bradley Gordon, Russel Steinbach
Grinnell College
Grinnell College, 2011


   title={Fast K-selection Algorithms for Graphics Processing Units},

   author={Alabi, Tolu and Blanchard, Jeffrey D. and Gordon, Bradley and Steinbach, Russel},



Download Download (PDF)   View View   Source Source   Source codes Source codes



Finding the kth largest value in a list of n values is a well-studied problem for which many algorithms have been proposed. A naive 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 has done 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 speedup for oat 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.
No votes yet.
Please wait...

* * *

* * *

HGPU group © 2010-2021 hgpu.org

All rights belong to the respective authors

Contact us: