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.