Approximate and Exact Selection on GPUs

TitleApproximate and Exact Selection on GPUs
Publication TypeConference Paper
Year of Publication2019
AuthorsRibizel, T., and H. Anzt
Conference Name2019 IEEE International Parallel and Distributed Processing Symposium Workshops
Date Published2019-05
Conference LocationRio de Janeiro, Brazil

We present a novel algorithm for parallel selection on GPUs. 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 using 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 SampleSelect does not work on the actual values but the ranks of the elements only, it is robust to the input data and can complete significantly faster for adversarial data distributions. Additionally to the exact SampleSelect, we address the use case of approximate selection by designing a variant that radically reduces the computational cost while preserving high approximation accuracy.

Project Tags: 
External Publication Flag: