The question this answers
When the work is pure computation and one core is already saturated, what is left?
Summing one billion 32-bit floats held in a 4 GB array, on a machine with four physical cores.
The input array, which is read-only for the whole computation — the single property that makes this parallelise cleanly. The output accumulator is shared and is the only thing that needs coordinating.
The final sum accounts for every one of the billion elements exactly once. No element is added twice, none is skipped, and no partial sum is overwritten by another worker's partial sum.
Synchronization exists to preserve this sentence. If a schedule can make it false, the code is wrong no matter which primitive it uses.
Four cores, and where the missing 30% went
The naive expectation is 4× and the honest answer is closer to 3×. The gap is not mysterious and it is not overhead in the hand-waving sense: it is a specific list of things that are not the addition. Splitting the range. Spawning or waking workers. Four cores contending for one memory bus while streaming 4 GB. Waiting for the slowest chunk. Combining four partial sums under a lock or an atomic.
The curve below flattens harder than Amdahl alone would predict, and the reason is worth naming precisely: summing floats is roughly one arithmetic operation per four bytes loaded, which makes it memory-bandwidth-bound long before it is ALU-bound. Four cores do not get four times the bandwidth from one memory controller. [[memory-bandwidth-limits]] is the whole story; [[amdahls-law]] is the more general ceiling.
This is why "we added cores and it did not get four times faster" is not a bug report. Sublinear scaling is the normal case, and the engineering question is whether the actual factor justifies the actual complexity.
[[oversubscription]].What the cores are actually doing
The parallel version is not four copies of the program. It is one split, four independent partial computations that share nothing, and one merge — the fork/join shape that [[fork-join]] generalises. The interesting property is the middle: during the parallel phase there is no shared mutable state at all, because each worker owns a disjoint slice of a read-only array and its own private accumulator.
That is not incidental. It is the design. Every parallel algorithm that scales does so by arranging for the parallel phase to touch nothing shared, and confining all coordination to the split and the merge, where it can be done once instead of a billion times. A version where four workers atomically add into one shared accumulator is also correct and is roughly 40 times slower than the sequential loop, because every increment becomes a cache line ping-ponging between cores. See [[false-sharing]] and [[atomics-are-not-magic]].
Notice the serial head and tail in the timeline. They are small here, and they are the part that does not shrink when you add cores — which is the entire content of Amdahl's Law expressed as a picture.
The shape of a parallel reduction
The code is short and every line of it is a decision. Private accumulators rather than a shared one. Chunk boundaries computed once. A merge that runs after every worker has finished, so the merge itself needs no synchronisation. Nothing atomic anywhere in the hot loop.
One property this code does *not* have is bit-identical output. Floating-point addition is not associative, so (a+b)+c and a+(b+c) can differ in the last bits, and a four-way split produces a different grouping than a sequential loop. The parallel sum is not wrong; it is a different, equally valid rounding. If a test asserts an exact float or a financial total must reconcile to the cent, this is a real change in behaviour and it belongs in the design discussion rather than in a bug report six months later. [[reduction-ordering]] and [[determinism]] cover it properly.
The second property to notice: chunk sizes are equal, which is only the right call when per-element cost is uniform. It is uniform here. For work where it is not — parsing variable-length records, rendering pages of different complexity — equal chunks produce the idle-core imbalance visible on core 3 above, and the answer is smaller chunks with dynamic assignment, which is what [[work-stealing]] exists for.
1double parallel_sum(const float* data, size_t n, unsigned workers) {2 std::vector<double> partial(workers, 0.0); // one slot per worker...3 std::vector<std::thread> threads;4 const size_t chunk = n / workers;5 6 for (unsigned w = 0; w < workers; ++w) {7 size_t begin = w * chunk;8 size_t end = (w == workers - 1) ? n : begin + chunk;9 // ...captured by index, so no two threads ever write the same slot.10 threads.emplace_back([=, &partial] {11 double local = 0.0; // private: stays in a register12 for (size_t i = begin; i < end; ++i) local += data[i];13 partial[w] = local; // exactly one write, at the end14 });15 }16 for (auto& t : threads) t.join(); // happens-before edge: the17 // main thread now sees every18 // partial[w] write safely19 double total = 0.0;20 for (double p : partial) total += p; // merge is serial and trivial21 return total;22}23// WRONG, and ~40x slower than the sequential loop:24// std::atomic<double> total; ... total += data[i]; // per element25// One cache line, four cores, one billion contended read-modify-writes.26// Also note: partial[] slots are adjacent doubles. On a 64-byte cache line,27// four workers writing partial[0..3] would false-share -- harmless here because28// each writes exactly once, ruinous if written per iteration.Key points
- Parallelism exists because single-core clock speed stopped improving; more transistors became more cores rather than faster ones.
- It adds throughput by doing more computing per unit time. It is the only one of the two models that requires hardware you might not have.
- Speedup is reliably sublinear. Split, merge, load imbalance, memory bandwidth and coordination each take their cut.
- A scalable parallel phase shares nothing. All coordination belongs in the split and the merge, executed once, not per element.
- Contended atomics in the hot loop can make the parallel version slower than the sequential one, sometimes by more than an order of magnitude.
- Equal chunks assume equal per-item cost. When that is false, cores go idle at the join and the speedup is set by the slowest chunk.
- Parallel floating-point reduction changes the rounding. That is a behaviour change, not a bug, and it must be an explicit decision.
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 ranges — disjointness is what removes the need for synchronisation inside the loop.
- • Hand each range to a worker that can occupy its own core: an OS thread, a pool task, or a process in a runtime where threads cannot. See
[[choosing-an-execution-model]]. - • Each worker accumulates into a private local, which the compiler keeps in a register and which no other core can touch.
- • Each worker writes its result once, to a slot no other worker writes.
- • Join every worker, which establishes the happens-before edge that makes those writes visible to the merging thread. See
[[happens-before]]. - • Merge the partials serially. Cost is proportional to worker count, not to input size.
- • Workers finish in the order 3, 1, 0, 2; the join blocks until 2 finishes, so wall clock is the slowest chunk plus the merge — never the average.
- • Two workers write
partial[1]because the chunk arithmetic overlapped at a boundary: one partial sum is overwritten, the total is short by 250 million elements, and it is short by a *plausible* amount, so nothing looks obviously wrong. - • A shared
total += data[i]without synchronisation: worker 0 reads total (1e6), worker 1 reads total (1e6), worker 0 writes 1e6+x, worker 1 writes 1e6+y — worker 0's contribution is gone. In C++ this is also a data race and therefore undefined behaviour, not merely a wrong number. See[[data-races]]. - • The merge runs before every worker has joined: the main thread reads slots that have not been written and may not even see the writes that have. Reading a shared array without the join's happens-before edge is a visibility bug independent of timing.
- • Parallel execution guarantees that independent work occupies distinct cores, given enough free cores and enough work to amortise the split.
- • It does not guarantee any particular speedup — memory bandwidth, the serial fraction and load imbalance all cap it, and none of them appear in the code.
- • It does not guarantee determinism of completion order, and for floating-point reductions it does not guarantee bit-identical results.
- • The join guarantees visibility of each worker's writes to the joining thread. Without it, you have no guarantee those writes are observable at all — a memory-model fact, not a timing one. See
[[safe-publication]]. - • It guarantees nothing about *fairness* between chunks: the OS may deschedule one worker for an unrelated process and stretch the join arbitrarily.
- • Memory bandwidth is the dominant contention for streaming reductions: four cores share one memory controller and saturate it well before they saturate their ALUs.
- • Last-level cache is shared. Four workers streaming disjoint 1 GB ranges evict each other continuously and each sees a lower hit rate than the sequential version did.
- • Any shared accumulator is a single cache line contended by every core, which is the worst possible access pattern on a coherent machine.
- • Adjacent slots in the partials array sit on one cache line; writing them per-iteration rather than once is textbook false sharing. See
[[false-sharing]]. - • The join is a synchronisation point where the fastest workers wait for the slowest, and their cores do nothing.
- • Lost update on a shared accumulator: an entire chunk's contribution disappears and the answer is wrong by a believable amount.
- • Off-by-one chunk boundaries: elements double-counted or skipped, producing an answer that is close enough to pass a smoke test.
- • False sharing: correct results, and a parallel version several times slower than sequential, with no lock anywhere in the code to blame.
- • Load imbalance: three cores idle at the join while one finishes, so the measured speedup is a fraction of the core count.
- • Oversubscription: more workers than cores, so the scheduler spends your time on context switches. See
[[more-threads-not-faster]]. - • Nondeterministic floating-point totals breaking a reconciliation check that had held for years.
- • Large, uniform, independent computation over data already in memory: reductions, transforms, image and video processing, compression, hashing, simulation steps.
- • Any workload where a profile shows one core pinned at 100% and the others idle, and the hot function is pure computation over partitionable data. See
[[cpu-saturation]]. - • Batch work with a wall-clock deadline, where the machine is otherwise yours and cores are the resource you already paid for.
- • Small inputs. Splitting and joining a 200-microsecond job across four threads reliably costs more than the job. See
[[parallel-overhead]]. - • Work with a large serial fraction: at 30% serial, infinite cores still cap you at about 3.3×, and four cores get you roughly 2.1×.
- • Memory-bandwidth-bound loops, where extra cores contend for the resource that was already the constraint.
- • On a shared box: taking four cores for your batch job is taking them from whatever else runs there, and the aggregate outcome can be worse.
- • When the result must be bit-reproducible and the reduction is floating point.
- • Per-core utilisation, not the average. One core at 100% and three at 4% is the signature that says parallelism is available and unused.
- • Speedup as a function of worker count, plotted. The knee tells you what the actual constraint is: near the core count means cores; well below it means bandwidth, imbalance or the serial fraction.
- • Achieved memory bandwidth against the machine's peak. Near peak means adding cores cannot help and the fix is fewer bytes per operation.
- • Time from first-worker-finished to last-worker-finished. Large means imbalance, and the fix is smaller chunks or work stealing, not more workers.
- • Cache miss rate per core sequential versus parallel — a large jump points at eviction between workers rather than at the algorithm.
- • Partitioning logic is new code with new boundary bugs, and its failures are silent: a wrong total rather than an exception.
- • The merge step needs its own correctness argument, especially for non-commutative or non-associative operations.
- • Results become nondeterministic in completion order and, for floats, in value — so tests and reconciliation must be rewritten to match.
- • You have taken on a resource-allocation decision: how many workers, on a machine you may share, with no universal formula. See
[[thread-pool-sizing]]. - • Debugging moves from "read the loop" to "reason about four stacks", and profiling must be per-core to say anything useful.
- • Make the sequential version faster first: a better algorithm, better memory layout, or SIMD within one core often beats a 3× thread-level win and adds no concurrency. See
[[simd]]. - • Reduce the work: sample, precompute, cache, or store the aggregate incrementally so the billion-element pass never happens.
- • Move it off the request path. If the answer can be 200 ms stale, a background job computes it once and every reader gets it for free.
- • Use a library primitive —
std::reducewith an execution policy, a vectorised array operation — which has already made these decisions and been tested against them.
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.
Parallel reduce and the combine tree
input [ 3, 6, 9, 12, 15, 18, 21, 24 ]
Amdahl's law: the serial ceiling
s = 0.10 n = 32
Amdahl S(n) = 1 / (s + (1 − s)/n) = 7.805× ← fixed problem, more machine
S(1 000 000) = 10.000× ← a million cores, and still under 10×
Gustafson S(n) = s + n(1 − s) = 28.900× ← fixed time, bigger problemWhy is 8 cores only 4.5×?
| workers | ideal | Amdahl only | realistic | limited by |
|---|---|---|---|---|
| 1 | 1.0× | 1.00× | 1.00× | none |
| 2 | 2.0× | 1.90× | 1.85× | serial |
| 4 | 4.0× | 3.48× | 3.19× | serial |
| 6 | 6.0× | 4.80× | 4.17× | serial |
| 8 | 8.0× | 5.93× | 4.17× | bandwidth |
| 10 | 10.0× | 6.90× | 4.17× | bandwidth |
| 12 | 12.0× | 7.74× | 4.17× | bandwidth |
| 14 | 14.0× | 8.48× | 4.17× | bandwidth |
| 16 | 16.0× | 9.14× | 4.17× | bandwidth |
What people believe, and what is true
Four cores means four times faster.
Four cores means at most four times faster, minus the serial fraction, minus load imbalance, minus memory bandwidth, minus coordination. Three times is a good result.
Making the accumulator atomic makes it parallel-safe and fast.
Atomic makes it correct. One billion contended atomic operations on one cache line across four cores is dramatically slower than one core doing plain additions.
The parallel version gives the same answer.
For integers, yes. For floating point, a different grouping of additions gives a different rounding. The answer is equally valid and not identical.
Go deeper
Overview
One core got as fast as it was going to get. Parallelism is how you use the other seven, and it only helps if the work is computation you can split.
Practical
Split into disjoint ranges, accumulate privately, write once, join, merge. Keep synchronisation out of the inner loop entirely, and measure per-core utilisation rather than the average.
Advanced
For streaming reductions the ceiling is arithmetic intensity, not cores. At one add per four bytes loaded you saturate the memory system at two or three cores, and the way past it is fewer bytes — better layout, smaller types, fusing passes — not more threads.