Parallel Monte Carlo Methods: Independent Sampling and PRNG Challenges — enabling statistical simulations at scale

Monte Carlo methods generate independent random samples to estimate integrals, expectations, and distributions. Parallelization is embarrassingly parallel: each process generates independent sample streams, computes statistics, and reduces results via summation/averaging. This inherent parallelism makes Monte Carlo ideal for GPU acceleration and distributed computing.

Parallel Random Number Generation

Sequential PRNGs (Mersenne Twister, PCG) maintain state dependent on prior output, creating dependencies that inhibit parallelization. Parallel PRNGs decouple streams: each thread receives independent seed, generates non-overlapping subsequences. MRG32k3a (Multiple Recursive Generator) enables efficient parallel splitting via jump-ahead functions, precomputing seeds for distant points. NVIDIA cuRAND provides optimized GPU implementations: Philox counter-based RNG (stateless, deterministic), cuRAND Sobol (quasi-random, low-discrepancy for integration), and Mersenne Twister variants.

Quality and Statistical Guarantees

PRNG quality at scale requires spectral properties verification: k-dimensional equidistribution ensures low-discrepancy behavior over k-tuples of consecutive outputs. Correlation length (memory of future samples on prior samples) must remain bounded. Poorly chosen parallel seeds introduce correlation artifacts, systematically biasing estimates.

GPU Path Tracing Implementation

Ray tracing via Monte Carlo generates random ray samples, computes intersection geometry, and accumulates illumination. GPU implementations batch rays across threads (wavefront rendering), compute intersections in parallel, and apply BRDF (Bidirectional Reflectance Distribution Function) sampling with random numbers. Multiple bounces (depth) and samples per pixel drive sample count to millions, leveraging GPU parallelism across rays.

Quantum Monte Carlo

Variational QMC evaluates quantum wavefunctions via path integrals. Diffusion QMC evolves walkers (particles) stochastically according to imaginary-time Schrödinger equations, with branching/death based on local energy estimates. Parallel walker approach distributes walkers across processes: each walker evolves independently (embarrassingly parallel), with periodic averaging of local energy estimates for branching decisions.