Parallel Random
Parallel Random Number Generation is the challenge of producing statistically independent, high-quality random sequences across multiple threads or processors simultaneously — requiring careful design to avoid correlations between streams that would invalidate Monte Carlo simulations, cryptographic applications, and stochastic algorithms while maintaining reproducibility for debugging.
Why Parallel RNG Is Hard
- Sequential RNG (single stream): Each output depends on previous state — inherently serial.
- Naively sharing one RNG across threads: Lock contention destroys performance.
- Giving each thread its own RNG with different seed: Risk of inter-stream correlation — statistical artifacts.
Parallel RNG Strategies
| Strategy | Description | Quality | Speed |
|---|---|---|---|
| Leap-Frog | Thread i takes every N-th element from single stream | Medium | Medium |
| Block Splitting | Thread i gets contiguous block [i×K, (i+1)×K) | Good | Fast |
| Parameterized PRNG | Different generator parameters per thread | Good | Fast |
| Counter-Based | Stateless: random(key, counter) | Excellent | Very Fast |
Counter-Based RNGs (Modern Best Practice)
- Philox, Threefry: Counter-based RNGs designed for parallel computing.
- Concept: `output = encrypt(key, counter)` — any counter value produces independent random output.
- Parallel: Each thread uses the same key, different counter range → perfectly independent, no state sharing.
- Reproducible: Given key + counter → always produces same output.
- Skip-ahead: Can jump to any position in O(1) — no need to generate preceding values.
Framework Implementations
| Framework | Parallel RNG | API |
|---|---|---|
| CUDA (cuRAND) | Philox4x32-10, MRG32k3a | `curand_init(seed, sequence, offset, &state)` |
| PyTorch | Philox (CUDA), MT19937 (CPU) | `torch.Generator()` per stream |
| NumPy | PCG64, Philox | `numpy.random.SeedSequence` for spawning |
| C++ <random> | Various engines | Manual stream management |
| Intel MKL | VSL Leap-Frog, Block-Split | `vslNewStream()` per thread |
Reproducibility in Deep Learning
- Set seed: `torch.manual_seed(42)` + `torch.cuda.manual_seed_all(42)`.
- Deterministic mode: `torch.use_deterministic_algorithms(True)`.
- Challenge: Multi-GPU training with different random augmentations per GPU — need independent but deterministic streams.
- Solution: Use `SeedSequence.spawn()` (NumPy) or separate `Generator` per data worker.
Statistical Testing
- TestU01 (BigCrush): Suite of statistical tests for RNG quality — 160+ tests.
- PractRand: Practical randomness testing suite.
- Good parallel RNG must pass both single-stream and inter-stream correlation tests.
Parallel random number generation is a foundational requirement for reproducible scientific computing — incorrect parallelization of RNG can silently introduce statistical artifacts that invalidate simulation results, making proper parallel RNG design essential for trustworthy Monte Carlo methods and stochastic training.