Proceedings of the ACM SIGGRAPH Symposium on High Performance Graphics, 2011, p.89-98
2011
Volltextzugriff (PDF)
Details
- Autor(en) / Beteiligte
- Titel
- Randomized selection on the GPU
- Ist Teil von
- Proceedings of the ACM SIGGRAPH Symposium on High Performance Graphics, 2011, p.89-98
- Ort / Verlag
- New York, NY, USA: ACM
- Erscheinungsjahr
- 2011
- Quelle
- ACM Digital Library
- Beschreibungen/Notizen
- 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.
- Sprache
- Englisch
- Identifikatoren
- ISBN: 9781450308960, 1450308961DOI: 10.1145/2018323.2018338Titel-ID: cdi_acm_books_10_1145_2018323_2018338_brief
- Format
- –
- Schlagworte
- Computing methodologies -- Computer graphics -- Graphics systems and interfaces, Computing methodologies -- Computer graphics -- Graphics systems and interfaces -- Graphics processors, Computing methodologies -- Parallel computing methodologies, Computing methodologies -- Parallel computing methodologies -- Parallel programming languages, Mathematics of computing -- Probability and statistics -- Probabilistic algorithms, Mathematics of computing -- Probability and statistics -- Probabilistic reasoning algorithms -- Markov-chain Monte Carlo methods, Mathematics of computing -- Probability and statistics -- Probabilistic reasoning algorithms -- Sequential Monte Carlo methods, Software and its engineering -- Software notations and tools -- General programming languages -- Language types -- Parallel programming languages, Theory of computation -- Design and analysis of algorithms -- Data structures design and analysis -- Sorting and searching