Efficient Parallel Random Sampling—Vectorized, Cache-Efficient, and Online
| Autor: | Emanuel Schrade, Peter Sanders, Sebastian Lamm, Lorenz Hübschle-Schneider, Carsten Dachsbacher |
|---|---|
| Rok vydání: | 2018 |
| Předmět: |
Computer science
Applied Mathematics Parallel algorithm Sampling (statistics) Bernoulli sampling 010103 numerical & computational mathematics 0102 computer and information sciences Parallel computing Simple random sample 01 natural sciences 010201 computation theory & mathematics Vectorization (mathematics) Cache SIMD 0101 mathematics Massively parallel Software |
| Zdroj: | ACM Transactions on Mathematical Software. 44:1-14 |
| ISSN: | 1557-7295 0098-3500 |
| Popis: | We consider the problem of sampling n numbers from the range { 1,… , N } without replacement on modern architectures. The main result is a simple divide-and-conquer scheme that makes sequential algorithms more cache efficient and leads to a parallel algorithm running in expected time O ( n / p +log p ) on p processors, i.e., scales to massively parallel machines even for moderate values of n . The amount of communication between the processors is very small (at most O (log p )) and independent of the sample size. We also discuss modifications needed for load balancing, online sampling, sampling with replacement, Bernoulli sampling, and vectorization on SIMD units or GPUs. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|