The question this answers
Which reductions can be parallelised safely, and what exactly does the combine operation have to satisfy?
Reducing a billion 64-bit floats to one value — sum, maximum, mean, and "the last value above threshold" — by splitting into 64 chunks, reducing each, and combining the 64 partials.
The input, read-only during the parallel phase. Each chunk accumulates into a private accumulator; only the 64 partials are shared, and only at the combine. A parallel reduce that has threads accumulating into one shared variable is not a reduce, it is a contended counter.
The parallel result equals the sequential result for *every* possible grouping and ordering the runtime might choose — which holds if and only if the combine is associative and the seed is a true identity for it.
Synchronization exists to preserve this sentence. If a schedule can make it false, the code is wrong no matter which primitive it uses.
Chunk, reduce locally, combine — and never share the accumulator
The shape is fork/join with a specific combine. Split the input into P chunks; each worker folds its chunk into a *private* accumulator; the P partials are then folded into one. The private accumulator is the point: a shared accumulator behind a lock serialises the entire loop and is reliably slower than the sequential version, and a shared accumulator without a lock is a lost-update race producing a low answer (The Atomicity Illusion).
This structure changes the cost model as well as the parallelism. Sequentially the reduction is P0 memory-bound passes over the data; in parallel it is the same total memory traffic spread over more cores, so a simple sum over a large array is frequently bounded by memory bandwidth rather than cores and scales far worse than the core count suggests (Memory Bandwidth: More Cores, Same Bus). Reductions with expensive per-element work — parsing, hashing, distance computation — scale much better because the arithmetic dominates the loads.
The combine step is usually written last and thought about least, which is backwards. The chunking is mechanical; the combine is where the correctness requirement lives, and the next section is entirely about it.
- Private accumulator per chunk; one combine at the end. Sharing the accumulator defeats the whole exercise.
- Chunks should be contiguous so each worker streams sequentially and the prefetcher helps.
- Cheap per-element work means the reduction is memory-bound and will not scale with cores.
- The number of chunks is a tuning parameter, not necessarily the worker count — more chunks help imbalance, fewer help locality.
1def parallel_reduce(data, chunk_reduce, combine, identity, workers):2 chunks = split(data, workers) # disjoint, contiguous for locality3 partials = run_in_parallel( # each worker gets a PRIVATE accumulator4 lambda c: functools.reduce(chunk_reduce, c, identity),5 chunks,6 )7 # The runtime may combine these in any order and any grouping:8 # ((p0 . p1) . (p2 . p3)) or (p0 . (p1 . (p2 . p3))) or ...9 # For the answer to be well-defined, all groupings must agree.10 return functools.reduce(combine, partials, identity)11 12# WRONG: one shared accumulator. Under a lock this is slower than sequential;13# without one it is a lost-update race that silently under-counts.14total = 0.015def worker(chunk):16 global total17 for x in chunk:18 total += x # read, add, write -- three steps, not one19 20# RIGHT: fold locally, combine once.21def worker(chunk):22 acc = 0.0 # private: no sharing, no synchronization23 for x in chunk:24 acc += x25 return acc # published exactly once, at the joinThe combine must be associative — and commutativity is a separate question
Associativity means (a ⊕ b) ⊕ c = a ⊕ (b ⊕ c): the *grouping* does not matter. That is precisely what a parallel reduce needs, because the runtime chooses the grouping — how many chunks, which partials combine first, in what tree shape — and you do not control it. If grouping changes the answer, then "the answer" is not a property of your input, it is a property of this run's scheduling.
Commutativity — a ⊕ b = b ⊕ a — is a *different* requirement, and it is needed only if the runtime may also reorder the operands. A reduce that preserves chunk order (chunk 0's partial always combines to the left of chunk 1's) needs associativity but not commutativity, which is why parallel string concatenation and list append work fine: concatenation is associative and not commutative. An unordered reduce, or one over an unordered collection, needs both. Knowing which your library provides is the difference between a correct parallel concat and a scrambled one.
The identity matters too, and it is the quieter bug. A parallel reduce seeds each chunk's accumulator with the identity, so a "seed" that is not a true identity is added P times instead of once. Seeding a sum with 100 gives 100 × P too much; seeding a maximum with 0 silently turns a max over negative numbers into 0. Sequentially neither of these shows up, because the seed is applied exactly once.
| Reduction | Associative? | Commutative? | True identity | Parallel-safe? |
|---|---|---|---|---|
| Sum (integers) | Yes | Yes | 0 | Yes — the textbook case |
| Sum (IEEE-754 floats) | No (rounding depends on grouping) | Yes | 0.0 (−0.0 for exactness edge cases) | Yes for the value, no for bitwise reproducibility |
| Max / Min | Yes | Yes | −∞ / +∞, never 0 | Yes |
| Count / Sum of squares | Yes | Yes | 0 | Yes |
| String / list concatenation | Yes | No | Empty string / empty list | Yes, only if chunk order is preserved |
| Subtraction, division | No | No | None | No — reformulate as a sum of negatives |
| Mean | No (as stated) | n/a | None | No directly; reduce to (sum, count) then divide once |
| Set union | Yes | Yes | Empty set | Yes |
| "Last element matching P" | Yes (right-biased pick) | No | None-sentinel | Yes, only with preserved order |
| Matrix multiply chain | Yes | No | Identity matrix | Yes, only if order preserved |
Floating-point addition is not associative, and the consequence is real
IEEE-754 addition rounds after every operation, so the grouping determines which intermediate values get rounded and by how much. (1e16 + 1.0) − 1e16 is 0.0 while 1e16 + (1.0 − 1e16) is 1.0, and the same phenomenon at smaller magnitudes is why a parallel sum of a billion floats gives an answer that differs from the sequential sum — and differs between runs, if the chunk count varies with available cores.
The schedule below shows two groupings of the same four partials producing two different totals. Nothing raced, no memory was shared, no invariant of the parallel machinery was broken. The reduction is simply not associative, so "the sum" was never uniquely defined by the input alone.
The practical consequences are worth stating flatly. The parallel result is usually *more* accurate than the sequential one, because pairwise combining keeps intermediate magnitudes closer together than a single running accumulator does — so this is not a case of parallel being wrong. But it is not reproducible: a test asserting bitwise equality against a sequential golden value will fail, a checksum computed in parallel will not match one computed sequentially, and a financial or scientific pipeline that requires run-to-run determinism must either fix the chunk count and the combine tree, or use a compensated (Kahan/Neumaier) or exact summation algorithm. Reduction Ordering: The Sum Changed When the Worker Count Did and Determinism: Same Input, Same Output? cover this consequence in depth; the requirement to *notice* it belongs here.
| # | Run A — pairwise tree (8 workers available) | Run B — left fold (2 workers available) | State |
|---|---|---|---|
| 1 | partials: p0=1e16, p1=1.0, p2=1.0, p3=−1e16 | · | p0=1e16 p1=1.0 p2=1.0 p3=-1e16 |
| 2 | combine (p0 ⊕ p3) → 0.0 — the large magnitudes cancel exactly | · | left=0.0 |
| 3 | combine (p1 ⊕ p2) → 2.0 | · | right=2.0 |
| 4 | combine left ⊕ right → 2.0 | · | Run A total=2.0 |
| 5 | · | same partials, but only two chunks were formed, so the fold is left-to-right | p0=1e16 p1=1.0 p2=1.0 p3=-1e16 |
| 6 | · | combine (p0 ⊕ p1) → 1e16 — the 1.0 is below the ulp of 1e16 and is rounded away | acc=1e16 |
| 7 | · | combine (acc ⊕ p2) → 1e16 — the second 1.0 vanishes too | acc=1e16 |
| 8 | · | combine (acc ⊕ p3) → 0.0 | Run B total=0.0 ✕ Same input, same operator, different grouping, different answer — the reduction was never associative, so no single "correct" total was defined. |
Key points
- Fold each chunk into a private accumulator; sharing one accumulator either serialises the loop or loses updates.
- The combine must be associative, because the runtime — not you — chooses the grouping.
- Commutativity is a separate requirement, needed only when operand order may change; order-preserving reduces need associativity alone.
- The seed must be a true identity: it is applied once per chunk, not once per reduction.
- IEEE-754 addition is not associative, so a parallel float sum is usually more accurate and never bitwise reproducible across differing chunk counts.
- Non-associative reductions can often be reformulated: a mean becomes a (sum, count) pair reduced associatively and divided once at the end.
- A cheap per-element operation makes the reduction memory-bound, so it will not scale with core count.
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.
- • Partition the input into disjoint contiguous chunks so each worker streams sequentially.
- • Each worker initialises a private accumulator with the identity and folds its chunk into it — no synchronization during the fold.
- • Each worker publishes exactly one partial result at the end of its chunk.
- • The partials are combined with the same operator, in a grouping the runtime chooses (often a balanced tree, sometimes a left fold).
- • The final value is the reduction of all partials, and it is well defined only if every grouping gives the same result.
- • For non-associative goals, reduce to an associative intermediate (sum and count; running min, max and count) and apply the final non-associative step once, sequentially.
- • Four workers fold four chunks into private accumulators and publish four partials; the runtime combines them pairwise; the result matches the sequential result for integer sums, for every scheduling.
- • Two runs with different core counts form different chunk counts, so the combine tree differs and the float total differs — nothing raced, the operation was simply not associative.
- • Threads share one accumulator without a lock: A reads 500, B reads 500, A writes 700, B writes 800 — A's contribution is gone, and the total is silently low (Shared Mutable State).
- • Threads share one accumulator with a lock: every element acquires and releases, the loop serialises on the lock, and the "parallel" version is slower than sequential with eight cores at 100% (What Contention Actually Costs).
- • A max reduction seeded with 0 over an all-negative input: each chunk returns 0, the combine returns 0, and the true maximum of −3 is never seen. Sequentially the same seed produces the same bug once; in parallel it produces it P times, which is not more wrong but is more confusing.
- • A concatenation reduce on an unordered runtime: chunk 3's partial combines before chunk 1's and the output string is scrambled, because the operator is associative but not commutative.
- • Guaranteed: with disjoint chunks and private accumulators, every element is included exactly once.
- • Guaranteed: for an associative operator with a true identity, the parallel result equals the sequential result exactly.
- • NOT guaranteed: bitwise equality with a sequential float reduction. Different grouping, different rounding.
- • NOT guaranteed: run-to-run reproducibility when the chunk count depends on available parallelism.
- • NOT guaranteed: operand order. Unless the library documents an order-preserving reduce, do not assume chunk 0 combines first.
- • NOT guaranteed: that the library checks associativity. Nothing verifies it; passing a subtraction compiles and runs and returns a number.
- • NOT guaranteed: speedup. For trivial per-element work the reduction is memory-bandwidth-bound and extra cores add little.
- • None during the fold, by construction — that is the entire design.
- • A shared accumulator turns the reduction into the most contended possible object: one cache line written by every worker on every element.
- • Partial results stored in adjacent slots of one array cause False Sharing: Different Variables, Same Cache Line if written repeatedly; write once at the end of the chunk.
- • The combine phase is a small synchronization point; with a balanced tree it is logarithmic in the chunk count and rarely matters.
- • Memory bandwidth is the shared resource for cheap operators — cores contend for it invisibly, and the symptom is scaling that flattens well before core count.
- • Lost update on a shared accumulator: a silently low total with no error.
- • Serialisation on a lock around the accumulator: correct, and slower than sequential.
- • Non-associative operator: a run-dependent answer that passes tests on a machine with a fixed core count and fails elsewhere.
- • Non-identity seed applied per chunk: an answer off by (seed × chunk count), or a max that never goes below the seed.
- • Order assumption violated by an unordered reduce, scrambling concatenation-style results.
- • Bitwise-determinism failures in downstream checksums and golden-value tests after a parallelisation that was numerically fine.
- • Overflow appearing at different points: partials may overflow where a running sequential accumulator would not, or vice versa.
- • Large inputs with non-trivial per-element work — parsing, hashing, distance computations — where arithmetic dominates memory traffic.
- • Associative aggregations that are the natural shape of the problem: sums, counts, extrema, histograms, set unions, sketch merges.
- • As a building block: most parallel analytics is a reduce with a richer combine, and getting the combine right once makes everything above it composable.
- • When you can reformulate a non-associative goal into an associative intermediate, which is usually possible and usually improves the code.
- • Cheap operators over large arrays, where memory bandwidth caps the speedup well below the core count.
- • Small inputs, where chunking and combine overhead exceeds a tight sequential loop (Parallel Overhead).
- • When bitwise reproducibility is a requirement and the chunk count is not pinned.
- • When the operator is genuinely non-associative and cannot be reformulated — a sequential fold is the correct answer, not a cleverer parallel one.
- • When each element's processing has side effects: a reduce assumes pure combination, and side effects reintroduce every sharing problem you removed.
- • Speedup versus chunk count, swept — the curve identifies both the overhead floor and the bandwidth ceiling.
- • Achieved memory bandwidth against the machine's peak; if you are near peak, more cores will not help.
- • Determinism check: run with different worker counts and compare results exactly. Any difference is a non-associativity finding, not a bug report.
- • Numerical error against a high-precision reference (extended precision or exact summation) for float reductions — parallel is usually better, and worth knowing by how much.
- • Time in the fold versus time in the combine; a combine that is a visible fraction means too many chunks.
- • Cache-miss rate per worker to confirm chunks are contiguous and the prefetcher is working.
- • The operator now carries an algebraic obligation (associativity, identity, sometimes commutativity) that the type system will not check and code review must.
- • Non-associative goals require a reformulated intermediate type — (sum, count) instead of mean — which propagates through the code.
- • Numerical results become dependent on the parallel configuration, so tests must compare with a tolerance and downstream checksums must be recomputed consistently.
- • Chunk count becomes a tuning parameter trading imbalance against overhead and locality.
- • Debugging a wrong total means checking three separate things — partition coverage, accumulator privacy, and operator algebra — and only the first is visible in a stack trace.
- • A sequential fold, when the input is small or the operator is cheap — the baseline, and it wins below the crossover.
- • SIMD within one thread: a vectorised sum uses one core and often beats a multi-threaded scalar sum on memory-bound work (SIMD: One Instruction, Many Elements).
- • A compensated summation algorithm (Kahan/Neumaier), when accuracy matters more than raw speed and you want a deterministic sequential result.
- • A database or columnar engine's aggregate, when the data already lives there — it will chunk, vectorise and parallelise better than application code.
- • Map-then-reduce with the map doing the expensive part, when per-element work dominates: parallelising the map is the win and the reduce is incidental (The Map/Reduce Pattern).
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
CPU parallelism simulator
Amdahl’s term, a synchronisation term, an oversubscription term and a bandwidth ceiling, each one a knob you can switch off. Real curves have more causes than four and are rarely this smooth. There is no ideal core count to read off this chart.
What people believe, and what is true
Addition is associative, so a parallel float sum gives the same answer.
Mathematical addition is associative; IEEE-754 addition rounds after each step and is not. The parallel total is usually more accurate and rarely bitwise identical.
The parallel result differed from the sequential one, so there is a race.
Check the operator first. A non-associative combine produces run-dependent answers with no race at all, and hunting for a race will not find anything.
Any fold can be parallelised by chunking it.
Only associative ones. A left fold with a non-associative operator — subtraction, division, or "apply this transformation then that one" where order encodes meaning — is inherently sequential.
The seed value is arbitrary as long as it is consistent.
It is applied once per chunk. A non-identity seed is multiplied by the chunk count, and a max seeded with 0 clamps every negative result.
Go deeper
Overview
Add up chunks separately, then add the chunk totals. This works when the operation does not care how you group things.
Practical
Private accumulator per chunk, identity seed, associative combine. If your goal is not associative, reduce to something that is and finish sequentially.
Advanced
Distinguish associativity from commutativity and check which your library assumes. Pin the chunk count if you need reproducibility; otherwise assert with tolerance.
Internals
Pairwise combining bounds float error growth logarithmically rather than linearly in element count, which is why the parallel total is generally the more accurate one even though it is the less reproducible one.