parallel random number generation
**Parallel Random Number Generation** — Producing statistically independent and reproducible streams of random numbers across multiple threads or processes for stochastic simulations and randomized algorithms.
**Challenges in Parallel RNG** — Sequential random number generators maintain internal state that creates dependencies between successive outputs, making naive parallelization incorrect. Simply sharing a single generator with locks destroys performance through contention. Splitting a single sequence by assigning every Nth value to process N can introduce subtle correlations. Reproducibility requires that the same random sequence is generated regardless of the number of processors or scheduling order, which conflicts with dynamic load balancing.
**Counter-Based Random Number Generators** — Threefry and Philox generators produce random outputs as a pure function of a counter and a key, eliminating the need for sequential state. Each thread uses a unique key and increments its own counter independently, guaranteeing zero communication overhead. These generators pass stringent statistical tests including BigCrush while providing trivial parallelization. Philox uses hardware-accelerated multiply operations making it efficient on GPUs, while Threefry uses only additions and rotations for portability.
**Stream Splitting Approaches** — Leapfrog splitting assigns every Pth element to process P from a single base sequence, suitable when the total draw count is known. Block splitting gives each process a contiguous block of the sequence using skip-ahead operations. Parameterized splitting creates independent generator instances with different parameters, as in the SPRNG library. The DotMix family provides provably independent streams through dot-product hashing of thread identifiers with generator states.
**Practical Implementation Patterns** — JAX and PyTorch use splittable RNG systems where a parent key generates child keys for each parallel operation. cuRAND provides device-side generators with per-thread state initialization using unique sequence numbers. For Monte Carlo simulations, each work unit receives a deterministic seed derived from its task identifier, ensuring reproducibility under any parallelization scheme. Statistical testing with TestU01 or PractRand should verify independence across parallel streams, not just individual stream quality.
**Parallel random number generation underpins the correctness and reproducibility of stochastic parallel applications, requiring careful design to maintain statistical quality while enabling scalable concurrent execution.**