parallel random number

**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.