Parallel Random Number

Parallel Random Number Generation is the computational challenge of producing independent, high-quality pseudorandom number streams across multiple parallel threads or processes — where naive approaches (shared global RNG with locking, or identical seeds per thread) produce either a serialization bottleneck or correlated sequences that invalidate Monte Carlo results, requiring specialized parallel RNG techniques to guarantee both statistical quality and computational efficiency.

The Problem with Naive Approaches

• Shared RNG with Lock: One global generator protected by a mutex. Each thread locks, generates, unlocks. Completely serial — might as well be single-threaded for RNG-bound workloads.
• Same Seed Per Thread: Every thread generates the identical sequence. Monte Carlo simulations produce correlated samples, biasing results.
• Thread-ID as Seed: Different seeds produce sequences that may overlap (for short-period generators) or exhibit subtle correlations that degrade statistical quality.

Parallel RNG Strategies

• Substream Splitting (Leap-Frogging): A single long-period generator is divided into non-overlapping subsequences. Thread k takes elements k, k+P, k+2P, ... from the master sequence. Requires a generator with efficient skip-ahead (advance state by N steps in O(log N) time). Mersenne Twister and counter-based RNGs support this.

• Parameterized Generators: Each thread uses a structurally different generator instance (different parameters, different polynomial in a linear feedback shift register). The streams are provably independent, not just non-overlapping. Example: DCMT (Dynamic Creator for Mersenne Twister) generates unique MT parameters for each thread.

• Counter-Based RNGs: Philox, Threefry (Random123 library). The RNG is a pure function: output = f(counter, key). Each thread uses a unique key and increments its own counter. No state, no splitting, trivially parallel. High quality (passes all TestU01 tests) and extremely fast on GPUs (5-10 cycles per random number).

GPU Random Number Generation

• cuRAND: NVIDIA's library providing GPU-optimized generators. XORWOW (default), MRG32k3a, Philox, and MTGP32. Each GPU thread initializes its own generator state with `curand_init(seed, sequence_id, offset)`. The sequence_id provides independent streams.
• Performance: Counter-based generators (Philox) produce ~100 billion random numbers per second on a modern GPU — sufficient for even the most demanding Monte Carlo simulations.

Reproducibility

Scientific computing requires deterministic results. Parallel RNG must produce the same random sequence regardless of thread scheduling. Counter-based RNGs achieve this naturally — the output depends only on (counter, key), not on execution order. State-based RNGs (Mersenne Twister) require careful stream assignment to ensure reproducibility across different thread counts.

Parallel Random Number Generation is the statistical foundation of parallel Monte Carlo methods — ensuring that the random samples driving simulations, optimization, and stochastic algorithms are both statistically independent across threads and computationally efficient at scale.