Randomized selection on the GPU

Laura Monroe, Joanne Wendelberger, Sarah Michalak
Los Alamos National Laboratory, Los Alamos, NM
Proceedings of the ACM SIGGRAPH Symposium on High Performance Graphics, HPG ’11, 2011


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





Download Download (PDF)   View View   Source Source   



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.
No votes yet.
Please wait...

* * *

* * *

HGPU group © 2010-2024 hgpu.org

All rights belong to the respective authors

Contact us: