Parallel Selection on GPUs

TitleParallel Selection on GPUs
Publication TypeJournal Article
Year of Publication2019
AuthorsRibizel, T., and H. Anzt
JournalParallel Computing
Date Published2020-03
Keywordsapproximate selection, gpu, kth order statistics, multiselection, parallel selection algorithm

We present a novel parallel selection algorithm for GPUs capable of handling single rank selection (single selection) and multiple rank selection (multiselection). The algorithm requires no assumptions on the input data distribution, and has a much lower recursion depth compared to many state-of-the-art algorithms. We implement the algorithm for different GPU generations, always leveraging the respectively-available low-level communication features, and assess the performance on server-line hardware. The computational complexity of our SampleSelect algorithm is comparable to specialized algorithms designed for – and exploiting the characteristics of – “pleasant” data distributions. At the same time, as the proposed SampleSelect algorithm does not work on the actual element values but on the element ranks of the elements only, it is robust to the input data and can complete significantly faster for adversarial data distributions. We also address the use case of approximate selection by designing a variant that radically reduces the computational cost while preserving high approximation accuracy.

Short TitleParallel Computing
Project Tags: 
External Publication Flag: