The question this answers
Why does my parallel sum disagree with the sequential one, and disagree differently at 2, 4 and 8 workers?
Summing an array of doubles — a total revenue figure, a loss function, a physics accumulator — with a parallel reduce over W workers.
One partial sum per worker, combined once at the end. There is no concurrently mutated state and no synchronization in the hot loop; the association order of the additions is the only thing that changes with W.
The reduction visits every element exactly once and combines them all. What is NOT invariant, and what people assume is: that the resulting double is the same value at every worker count.
Synchronization exists to preserve this sentence. If a schedule can make it false, the code is wrong no matter which primitive it uses.
a + (b + c) is not (a + b) + c
Every IEEE-754 addition rounds its result to the nearest representable double. Rounding is exact and deterministic, and it is also *lossy*, so the loss depends on the magnitudes of the operands at the moment of the addition. Change the order and you change which additions round away which bits. Addition of real numbers is associative; addition of doubles is not, and that is not an implementation defect but a consequence of finite precision.
The read-out below is the whole lesson in one array. Eight values, four different chunkings, three different answers — 1.0, 2.0 and 0.0 — all produced by correct code, all reproducible, none of them a race. If you had a test asserting the total equals 1.0, it passes on your laptop with one worker and fails in CI with four, and you will spend a day looking for a concurrency bug that is not there.
The small case matters too, because it is the one people actually meet: (0.1 + 0.2) + 0.3 is 0.6000000000000001 while 0.1 + (0.2 + 0.3) is 0.6. Nothing dramatic, and quite enough to fail an equality assertion, produce a one-cent difference in a financial total, or make two runs of the same job disagree in a way that alarms an auditor.
- Associativity is a property of real arithmetic that finite-precision floating point does not have.
- Integer and fixed-point addition IS associative (absent overflow), so this problem is specific to floats and decimals-as-floats.
- Error grows with the number of additions and with the spread of magnitudes; a naive sequential sum of a million values is not the "right" answer either, just a different wrong one.
a = [ 1e16, 1.0, -1e16, 1.0, 1e16, 1.0, -1e16, 1.0 ] why the bits vanish: 1e16 + 1 == 1e16 (the gap between representable doubles near 1e16 is larger than 1) sequential, left to right ................. 1.0 1e16 +1 -> 1e16; -1e16 -> 0; +1 -> 1; 1e16 +1 -> 1e16; -1e16 -> 0; +1 -> 1 W=2 chunks of 4 .......................... 2.0 chunk0 [1e16,1,-1e16,1] -> 1.0 chunk1 [1e16,1,-1e16,1] -> 1.0 sum = 2.0 W=4 chunks of 2 .......................... 0.0 [1e16,1] -> 1e16 [-1e16,1] -> -1e16 [1e16,1] -> 1e16 [-1e16,1] -> -1e16 sum = 0.0 W=8 chunks of 1 .......................... 1.0 partials are the elements; combined in order = sequential and the everyday version: (0.1 + 0.2) + 0.3 == 0.6000000000000001 0.1 + (0.2 + 0.3) == 0.6 no race. no lost update. no bug. arithmetic.
The schedule that is not a race
The trace below is deliberately drawn as a schedule, because this is the one lesson in the domain where reading it that way is *misleading in a useful way*. Every step is correct. No two actors touch the same memory. Reorder the steps however you like and the answer is identical — the outcome depends on the partitioning, not on the interleaving.
That is exactly why this bug survives so long. Every instinct trained by the rest of this domain says "different results between runs means a race", so people add locks, add atomics, add barriers, and nothing changes, because the schedule was never the variable. The variable is W, and it is usually configuration rather than code — a pool size, a CPU count, a parallelism flag that differs between the developer machine and the production container.
The tell that distinguishes this from a real race is worth stating plainly: a race gives different answers on repeated runs at the same worker count; reduction ordering gives the same answer every time at a given W, and a different one at a different W. Run the job three times with W fixed. Identical results mean you are here, not in Reasoning About Races: A Method, Not an Instinct.
| # | Worker A (elements 0-3) | Worker B (elements 4-7) | Combiner | State |
|---|---|---|---|---|
| 1 | local = 0 + 1e16 | · | · | A.local=1e16 |
| 2 | local += 1 -> 1e16 (the 1 is rounded away) | · | · | A.local=1e16 |
| 3 | · | local = 0 + 1e16 | · | B.local=1e16 |
| 4 | local += -1e16 -> 0 | · | · | A.local=0 |
| 5 | · | local += 1 -> 1e16 (rounded away again) | · | B.local=1e16 |
| 6 | local += 1 -> 1 | · | · | A.local=1 |
| 7 | · | local += -1e16 -> 0 | · | B.local=0 |
| 8 | · | local += 1 -> 1 | · | B.local=1 |
| 9 | · | · | total = A.local + B.local = 2.0 | total=2.0 ✕ The sequential sum is 1.0. Two workers produced 2.0 — with no shared state, no synchronization and no schedule dependence. |
Buying reproducibility, and deciding whether you need it
Start with the question most teams skip: does this result need to be bit-reproducible, or only accurate? For a machine-learning loss, a physics simulation or an aggregate metric, a difference in the fifteenth significant digit is noise far below the modelling error, and the correct response is to compare with a tolerance and move on. For a financial total, a checksum, a consensus input, an audit figure or a regression test, reproducibility is a requirement, and it must be bought.
The strategies in the matrix cost different things. Fixed chunking — partition the array into a fixed number of chunks independent of worker count, and combine in a fixed order — is usually the best value: the answer becomes stable and reproducible at any W, without changing the arithmetic or the speed, and it costs only the discipline of not deriving the chunk count from availableProcessors(). Compensated (Kahan-style) summation costs a few extra operations per element and buys much higher accuracy, which is a different thing from reproducibility but often what people actually wanted.
The one that solves it completely is not using floats: integers or fixed-point (money in minor units, scaled integers) are associative and exactly reproducible under any partitioning. If the quantity is inherently discrete — money, counts, IDs — floats were the wrong representation and this lesson is telling you so. Where the values are genuinely continuous, pick a strategy, write the tolerance or the ordering guarantee into the test, and document it; see Determinism: Same Input, Same Output? for the general version of this decision.
- Never derive the chunk count from the core count if the result must be reproducible — that single line is what couples your answer to the machine.
- Reproducible and accurate are different goals with different fixes; be explicit about which one you need.
- If the quantity is money or a count, the real finding is that it should not be a float.
| Strategy | Reproducible across W? | More accurate? | Cost | Use when |
|---|---|---|---|---|
| Do nothing; compare with a tolerance | No | No | None | ML, simulation, metrics — the usual right answer |
| Fixed chunk count, fixed combine order | Yes | No | Chunk count must not depend on core count | Almost always worth doing; cheap and effective |
| Deterministic tree reduction | Yes | Somewhat — shallower error growth | Slightly more structure in the combine | Large arrays where accuracy also matters |
| Compensated (Kahan-style) summation | Only with fixed chunking | Substantially | A few extra operations per element | Long sums with mixed magnitudes |
| Sort by magnitude before summing | Yes, with a stable sort | Substantially | A sort — usually far more than the sum | Offline, accuracy-critical, small data |
| Integer or fixed-point arithmetic | Exactly | Exact | Range management and scaling discipline | Money, counts — anything discrete |
| Force sequential reduction | Yes | No | All the parallelism | Last resort; the reduction was rarely the bottleneck |
Key points
- Floating-point addition is not associative, so the order of a reduction changes the result — legitimately, deterministically, and without any race.
- A parallel reduction changes association order with the worker count, so the same input can give a different answer at 1, 2, 4 and 8 workers.
- The diagnostic: a race varies between runs at fixed W; reduction ordering is stable at each W and changes with W.
- Fixed chunking with a fixed combine order restores reproducibility at any worker count and costs essentially nothing.
- Reproducible and accurate are separate goals: compensated summation buys accuracy, fixed ordering buys reproducibility.
- For discrete quantities — money, counts — the real fix is integers, which are associative and exact.
The loop, answered
Every field is required, which is why no lesson here can recommend concurrency without naming the interleaving that breaks it, the complexity it adds, and the simpler thing to consider first.
- • Each IEEE-754 addition rounds to the nearest representable double, so information is discarded at every step depending on the operands' magnitudes.
- • A parallel reduce partitions the array into W chunks, sums each chunk independently, then combines the W partials.
- • Different W means different chunk boundaries, so different additions happen and different bits are rounded away.
- • The combine step adds another ordering choice — sequential over partials, or a tree — which is a second source of variation.
- • Compilers add a third: reassociation under fast-math, and fused multiply-add contraction, both of which change results without changing source.
- • The point of this lesson: no interleaving changes the result. Workers touch disjoint slices and private accumulators; every schedule at a given W yields the same double.
- • W=2: A sums [1e16,1,-1e16,1] to 1.0, B sums [1e16,1,-1e16,1] to 1.0, combine gives 2.0 — every time, in any order.
- • W=4: partials are 1e16, -1e16, 1e16, -1e16; combined left to right they give 0.0 — every time.
- • The one genuine interleaving hazard is the combine step done wrong: A reads total (0.0); B reads total (0.0); A writes 1.0; B writes 1.0 — a lost update, which is a real race and a different bug living next door to this one.
- • Dynamic work stealing makes the partitioning itself schedule-dependent, which converts this stable-per-W behaviour into genuinely run-to-run variable results — the one arrangement where it does look like a race.
- • IEEE-754 guarantees each individual operation is correctly rounded and deterministic — the arithmetic is not "fuzzy", it is exactly specified.
- • It guarantees nothing about association, so a sum is only defined up to the order in which it was performed.
- • A parallel reduce guarantees every element is included exactly once. It does NOT guarantee the same result as the sequential reduction, or as itself at a different W.
- • Fixed chunking with a fixed combine order guarantees reproducibility across worker counts, on the same platform and build configuration.
- • It does NOT guarantee reproducibility across platforms: extended-precision intermediates, FMA contraction and library differences can all change results for identical source.
- • Fast-math flags explicitly waive the ordering guarantee, so builds that differ in flags can differ in results with no source change.
- • There is essentially none in a well-written reduction: private accumulators, one combine at the end. That is why it is such a clean illustration of a non-race difference.
- • The contention that appears when it is written badly — a single shared
totalupdated per element — replaces the ordering problem with a lost-update race and destroys the parallelism at the same time. - • Atomic addition on a shared float is not a fix either: it serializes, it is far slower, and the addition order is still nondeterministic, so it makes reproducibility strictly worse.
- • A test asserting an exact total that passes locally at W=1 and fails in CI at W=4 — and is then "fixed" by adding a lock, which changes nothing.
- • Financial figures differing by cents between runs, discovered by an auditor rather than by the team.
- • A model that fails to reproduce a training run because the reduction order changed with the device or the parallelism setting.
- • A checksum or hash computed over accumulated floats that disagrees between machines, breaking a cache key or a deduplication scheme.
- • A real lost-update race on a shared accumulator, misattributed to floating-point ordering and therefore never fixed.
- • Fast-math enabled globally to speed one loop, silently changing results across an entire binary.
- • Knowing this exists prevents the most expensive version of the bug: a day spent hunting a race that is not there.
- • Fixed chunking is a small, cheap discipline that makes parallel numeric jobs reproducible and testable, which is worth having by default.
- • Compensated summation genuinely improves accuracy for long sums with mixed magnitudes, and parallel partial sums are themselves *more* accurate than a naive sequential sum because each partial accumulates fewer terms.
- • When reproducibility is pursued where it is not required, forcing sequential reduction and discarding real parallelism for digits nobody reads.
- • When exact-equality assertions are written against floating-point aggregates at all — the test is wrong before the concurrency arrives.
- • When fast-math is enabled to get a speedup and quietly changes results in code paths that needed the guarantee.
- • When the difference is treated as an error to eliminate rather than a property to manage, leading to increasingly elaborate machinery around what is a representation choice.
- • Run the job at W = 1, 2, 4, 8 on the same input and diff the results. Different-per-W and stable-per-run is the fingerprint.
- • Run three times at a fixed W. Identical results rule out a race; varying results mean you have both problems.
- • Compare against a higher-precision or compensated reference sum to see how large the error actually is relative to the values — often it is far below anything that matters.
- • Check build flags for fast-math and reassociation, and check whether the chunk count is derived from the core count. These two are the usual culprits.
- • Assert with a relative tolerance in tests and record the tolerance you chose, so a real regression is still detectable.
- • Reproducibility becomes an explicit, documented property of the computation rather than something assumed, and it must be re-checked when the parallelization changes.
- • Fixed chunking decouples chunk count from worker count, which slightly complicates load balancing and rules out naive dynamic partitioning.
- • Compensated summation adds arithmetic that a compiler may optimize away under fast-math — the fix and the flag can silently cancel out.
- • Tests must express tolerances rather than equalities, which requires deciding what tolerance is defensible for each quantity.
- • Cross-platform reproducibility, if genuinely required, constrains compiler flags, library versions and hardware — a heavy commitment worth making deliberately.
- • Use integers or fixed-point for anything discrete. Exact, associative, reproducible under every partitioning — the strongest fix when it applies.
- • Compare with a tolerance and stop trying to be bit-exact. For most numeric workloads this is correct rather than lazy.
- • Use a library reduction that documents a deterministic order, so the guarantee is someone else's to maintain.
- • Reduce sequentially. The reduction is rarely the expensive part — the per-element work usually is — so parallelizing the map and serializing the fold often costs almost nothing.
Parallel reduce and the combine tree
input [ 3, 6, 9, 12, 15, 18, 21, 24 ]
Fork/join and the split threshold
fork(lo, hi): if (hi - lo <= 64) return sequential(lo, hi) // the base case is the tuning knob mid = (lo + hi) / 2 left = spawn fork(lo, mid) // +0.05 ms right = fork(mid, hi) // run one half on THIS thread return left.join() + right // join is where the parallelism ends levels requested 4 → 4 actually taken leaves 16 × 256 elements span 0.91 ms total 1.21 ms
What people believe, and what is true
The parallel sum differs from the sequential one, so there is a race.
Check by running three times at fixed W. Stable results mean it is association order, not a race — no lock will change it.
The sequential answer is the correct one.
It is one rounding path among many. For long sums with mixed magnitudes, partial sums or compensated summation are typically *more* accurate than naive left-to-right.
Using atomic float addition makes it deterministic.
It serializes the reduction and destroys the parallelism, and the order of atomic additions is still nondeterministic — strictly worse on both axes.
This only matters in scientific computing.
It matters wherever an exact figure is expected: financial totals, checksums over aggregates, cache keys, regression tests and reproducible ML runs.