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
Your response
You must be logged in to post a comment.
