Randomized selection on the GPU
Los Alamos National Laboratory, Los Alamos, NM
Proceedings of the ACM SIGGRAPH Symposium on High Performance Graphics, HPG ’11, 2011
@inproceedings{monroe2011randomized,
title={Randomized selection on the GPU},
author={Monroe, L. and Wendelberger, J. and Michalak, S.},
booktitle={Proceedings of the ACM SIGGRAPH Symposium on High Performance Graphics},
pages={89–98},
year={2011},
organization={ACM}
}
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.
September 19, 2011 by hgpu
