Efficient parallel random sampling-vectorized, cache-efficient, and online

DOI10.1145/3157734MaRDI QIDQ4581396zbMATH OpenOpenAlexWikidataFDO

Authors Peter Sanders, Sebastian Lamm, Lorenz Hübschle-Schneider, Emanuel Schrade, Carsten Dachsbacher

Publication date 17 August 2018

Published in ACM Transactions on Mathematical Software (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1610.05141

zbMATH Keywords

parallel algorithmscommunication efficient algorithmshypergeometric random deviates

Mathematics Subject Classification ID

Random number generation in numerical analysis (65C10) Parallel numerical computation (65Y05) Random graphs (graph-theoretic aspects) (05C80) Parallel algorithms in computer science (68W10)

Abstract: We consider the problem of sampling $n$ numbers from the range $1,ldots,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 $mathcalO(n/p+logp)$ 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 $mathcalO(logp)$) 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.

Recommendations

• An efficient parallel algorithm for random sampling
• Parallel streaming random sampling
• Faster methods for random sampling
• Efficient sampling of random permutations
• Random sampling with a reservoir

Cited in

(7)

• Efficient sampling of random permutations
• Ancestral Gumbel-top-k sampling for sampling without replacement
• Parallel Weighted Random Sampling
• Load-Balancing for Parallel Delaunay Triangulations
• An efficient parallel algorithm for random sampling
• Parallel Weighted Random Sampling
• Parallel streaming random sampling

This page was built for publication: Efficient parallel random sampling-vectorized, cache-efficient, and online

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4581396)