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
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
