Parallel Random Number Generation is the technique of producing statistically independent streams of pseudo-random numbers across multiple parallel threads or processors — where naive approaches (sharing a single RNG with locking, or splitting a single sequence) produce either contention bottlenecks or statistical correlations that invalidate Monte Carlo simulation results, requiring purpose-built parallel RNG algorithms that guarantee both independence and reproducibility.

Why Parallel RNG Is Non-Trivial

A sequential PRNG produces a deterministic sequence from a seed. When P parallel threads need random numbers, three approaches exist, each with trade-offs:

1. Shared RNG with Lock: Thread-safe but serializes all random number requests — performance collapses at high thread counts. Unusable for GPU workloads. 2. Different Seeds per Thread: Each thread initializes an independent RNG with a unique seed. Simple but provides no guarantee that sequences don't overlap or correlate. For short-period generators, sequence overlap is likely. 3. Purpose-Built Parallel RNG: Algorithms designed from the ground up for independent parallel streams with proven statistical properties.

Parallel RNG Strategies

• Substream/Skip-Ahead: A single RNG with period 2^192 or larger is divided into P non-overlapping substreams by jumping ahead 2^128 positions per stream. Each thread gets its own substream. Guaranteed non-overlapping if substream length exceeds any thread's usage. Example: MRG32k3a (L'Ecuyer's Combined Multiple Recursive Generator) with skip-ahead.

• Counter-Based RNG (CBRNG): Stateless generators where random(key, counter) produces output deterministically from a key and counter. Each thread uses a unique key (or counter range). No state to manage, perfect for GPU. Examples: Philox (4-round Feistel cipher), ThreeFry (counter-mode block cipher). NVIDIA cuRAND implements Philox as the default GPU generator.

• Block Splitting: Thread i takes elements i, i+P, i+2P, ... from a single sequence. Preserves the original sequence's statistical properties but requires a statistically robust base generator.

GPU-Specific Considerations

• State Size: Each GPU thread needs its own RNG state. Philox state is just a 128-bit counter + 64-bit key = 24 bytes per thread — minimal register/memory overhead for millions of threads.
• Throughput: cuRAND Philox generates ~50 billion random numbers per second on an A100 GPU. Mersenne Twister is slower and has larger state (2.5 KB per thread).
• Reproducibility: Counter-based RNGs are perfectly reproducible — the same (key, counter) always produces the same output, regardless of execution order. Essential for debugging Monte Carlo simulations.

Statistical Quality

Parallel RNG streams must pass inter-stream correlation tests (BigCrush with combined streams) in addition to single-stream tests. Correlations between streams can bias Monte Carlo results without any single stream appearing defective. The TestU01 library provides rigorous statistical testing.

Parallel Random Number Generation is the statistical foundation of parallel Monte Carlo methods — providing the independent, high-quality randomness that makes stochastic simulation trustworthy when scaled across thousands of parallel execution units.