floating point reproducibility parallel

**Floating-Point Reproducibility in Parallel Computing** is the **challenge of obtaining identical numerical results across different parallel runs, hardware configurations, and thread counts — arising from the non-associativity of floating-point arithmetic where (a+b)+c ≠ a+(b+c) in finite precision, causing reductions performed in different orders (due to non-deterministic scheduling) to produce different final bit patterns even when mathematically equivalent**. **The Non-Associativity Problem** IEEE 754 floating-point operations are not associative because of rounding: each operation rounds to the nearest representable value. Adding 1e15 + 1.0 + (-1e15) in left-to-right order gives 0.0 (catastrophic cancellation), but 1.0 + (-1e15) + 1e15 = 1.0. In parallel reductions, threads accumulate partial sums in non-deterministic order depending on scheduling, producing run-to-run variation. **Sources of Non-Determinism** - **Parallel reduction order**: different thread scheduling = different summation order. - **CUDA atomic operations**: atomicAdd on GPU is non-deterministic order. - **MPI_Allreduce**: not required to be reproducible (though many implementations are for fixed communicator). - **Multi-threaded BLAS**: thread count affects reduction partitioning. - **FMA (fused multiply-add)**: a×b+c fused vs separate — different rounding. **Techniques for Reproducibility** - **Fixed reduction order**: enforce sequential reduction order (defeats parallelism). - **Kahan compensated summation**: tracks rounding error in compensation variable c; sum += (x - c); effectively doubles precision of accumulation. O(N) cost, ~2× overhead. - **Pairwise summation**: divide-and-conquer binary tree reduction — better numerical accuracy than sequential, same order for same thread count. - **ExBLAS / ReproBLAS**: use reproducible summation algorithms (superaccumulator — fixed-point accumulation in 4096-bit integer), fully reproducible regardless of parallelism. - **Deterministic GPU kernels**: CUDA 10+ deterministic convolution (cuDNN ``-determinism`` flag), uses slower but reproducible algorithms. **Reproducibility vs Performance** Fully reproducible algorithms typically have 1.5–5× overhead vs fastest non-reproducible. The tradeoff: - **Scientific validation**: same input → same output essential for debugging, regression testing. - **ML training**: non-determinism in gradient accumulation causes different convergence paths, complicating debugging. - **Certification**: safety-critical applications (nuclear, medical) require reproducible computation. **Practical Mitigation** - Set fixed random seeds and deterministic algorithm flags (``torch.use_deterministic_algorithms(True)``). - Use float64 instead of float32 to reduce sensitivity to order. - Document non-reproducibility explicitly in scientific software. - Use verification against reference (single-thread result) rather than run-to-run comparison. Floating-Point Reproducibility is **the often-overlooked numerical correctness challenge that transforms seemingly equivalent parallel computations into divergent results — a fundamental tension between the mathematical ideal of associativity and the computational reality of finite-precision arithmetic in massively parallel systems**.