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