Randomized Selection on the GPU
| dc.contributor.author | Monroe, Laura | en_US |
| dc.contributor.author | Wendelberger, Joanne | en_US |
| dc.contributor.author | Michalak, Sarah | en_US |
| dc.contributor.editor | Carsten Dachsbacher and William Mark and Jacopo Pantaleoni | en_US |
| dc.date.accessioned | 2016-02-18T11:01:48Z | |
| dc.date.available | 2016-02-18T11:01:48Z | |
| dc.date.issued | 2011 | en_US |
| dc.description.abstract | 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. | en_US |
| dc.description.sectionheaders | GPU Computing & Computational Graphics | en_US |
| dc.description.seriesinformation | Eurographics/ ACM SIGGRAPH Symposium on High Performance Graphics | en_US |
| dc.identifier.doi | 10.1145/2018323.2018338 | en_US |
| dc.identifier.isbn | 978-1-4503-0896-0 | en_US |
| dc.identifier.issn | 2079-8687 | en_US |
| dc.identifier.pages | 89-98 | en_US |
| dc.identifier.uri | https://doi.org/10.1145/2018323.2018338 | en_US |
| dc.publisher | ACM | en_US |
| dc.subject | D.1.3 [Concurrent Programming] | en_US |
| dc.subject | Parallelprogramming. F.2.2 [Non | en_US |
| dc.subject | numerical Algorithms andProblems] | en_US |
| dc.subject | Non | en_US |
| dc.subject | numerical Algorithms and Problems Sortingand searching. G.3 [Probability and Statistics] | en_US |
| dc.subject | ProbabilisticAlgorithms. 1.3.1 [Computer Graphics] | en_US |
| dc.subject | Hardware Architecture Graphics processors. 1.3.1 [Computer Graphics] | en_US |
| dc.subject | HardwareArchitecture Parallel processing. | en_US |
| dc.subject | Experimental parallel algorithms | en_US |
| dc.subject | GPGPU | en_US |
| dc.subject | Las Vegasalgorithm | en_US |
| dc.subject | probabilistic algorithms | en_US |
| dc.subject | selection | en_US |
| dc.subject | kth order statistic. | en_US |
| dc.title | Randomized Selection on the GPU | en_US |