Randomized Selection on the GPU

Thumbnail Image
Date
2011
Authors
Monroe, Laura
Wendelberger, Joanne
Michalak, Sarah
Journal Title
Journal ISSN
Volume Title
Publisher
ACM
Abstract
We implement here a fast and memory-sparing probabilistic top k selection algorithm on the GPU. The algorithm proceeds via an iterative probabilistic guess-and-check process on pivots for a three-way partition. When the guess is correct, the problem is reduced to selection on a much smaller set. This probabilistic algorithm always gives a correct result and always terminates. Las Vegas algorithms of this kind are a form of stochastic optimization and can be well suited to more general parallel processors with limited amounts of fast memory.
Description

        
@inproceedings{
10.1145:2018323.2018338
,
booktitle = {
Eurographics/ ACM SIGGRAPH Symposium on High Performance Graphics
},
editor = {
Carsten Dachsbacher and William Mark and Jacopo Pantaleoni
},
title = {{
Randomized Selection on the GPU
}},
author = {
Monroe, Laura
 and 
Wendelberger, Joanne
 and 
Michalak, Sarah
},
year = {
2011
},
publisher = {
ACM
},
ISSN = {
2079-8687
},
ISBN = {
978-1-4503-0896-0
},
DOI = {
10.1145/2018323.2018338
}
}
Citation
URI
https://doi.org/10.1145/2018323.2018338
Collections
High-Performance Graphics 2011