The question this answers
Which computations have a parallel form at all, and how do I recognise the shape of the one in front of me?
Four jobs over the same 50-million-element array: scale every element (map), find the sum (reduce), compute running totals (scan), and sort it — plus the recursive shape underneath the last one.
The input array. Map and reduce touch disjoint regions and share nothing mutable. Scan and merge-based sort write into a separate output buffer, which is what keeps them free of in-place write conflicts — sorting in place in parallel is a materially harder problem.
Each parallel algorithm produces exactly the result its sequential specification defines, for every schedule the runtime may choose: same elements, same values, and same order wherever the specification fixes an order.
Synchronization exists to preserve this sentence. If a schedule can make it false, the code is wrong no matter which primitive it uses.
The five shapes, and the two numbers that decide whether parallelism helps
Almost everything parallel decomposes into five primitives. Map applies a function per element independently. Reduce folds all elements into one with an associative operator. Scan (prefix sum) produces, for each position, the reduction of everything up to it. Sort produces a permutation in order. Divide-and-conquer splits a problem into independent subproblems and combines their answers — and is really the general form the other four are instances of.
Two numbers decide whether a parallel form helps, and they are worth introducing here even though Work and Span develops them properly. Work is the total number of operations the parallel version performs — often more than the sequential algorithm does, which is the first honest thing to notice. Span is the longest chain of operations that must happen in sequence, and it is the floor no number of cores gets under. A map has span O(1) — every element is independent, so with enough workers it is one step. A reduce over a balanced tree has span O(log n). A naive left-to-right scan has span O(n), which is why the interesting fact about scan is that a different algorithm brings it to O(log n) at the cost of doing roughly twice the work.
That trade — more total work, shorter critical path — is the recurring shape of parallel algorithm design, and it is why "the parallel algorithm is less efficient" is often true and often irrelevant. A version doing 2n operations with span log n beats a version doing n operations with span n as soon as you have more than a handful of cores, and loses on one core. Parallel Overhead is the lesson on where that crossover lands.
| Shape | Work | Span (critical path) | What must be true | Parallelism helps when |
|---|---|---|---|---|
| Map | O(n) | O(1) | Per-element function is independent and side-effect-free | Per-element work is non-trivial; otherwise memory-bound |
| Reduce | O(n) | O(log n) | Combine is associative; seed is a true identity | Per-element work is non-trivial, or n is very large |
| Scan / prefix sum | O(n) sequential, ~O(2n) parallel | O(n) naive → O(log n) with a two-pass algorithm | Operator is associative — the same requirement as reduce | n is large and cores are plentiful; the extra work is real |
| Merge sort | O(n log n) | O(log² n) with a parallel merge, O(n) with a sequential merge | Comparison is a total order; output buffer separate from input | Above a size threshold; the merge is the part that limits you |
| Quicksort | O(n log n) expected | O(log² n) expected, degrades with bad pivots | Partition step parallelised or done sequentially per level | Sizes are balanced; skew makes it a straggler problem |
| Divide-and-conquer (general) | Problem-dependent | Depth of the recursion × combine cost | Subproblems are independent; combine is cheap relative to them | Subproblems are large enough to beat the fork cost |
| Sequential dependence (running state machine) | O(n) | O(n) — irreducible | Nothing; each step needs the previous state | Never, within one instance. Parallelise across instances instead |
Scan: the one that looks sequential and is not
A running total looks irreducibly sequential — output[i] needs output[i−1], so how could you compute the millionth without the 999,999th? The resolution is the single most useful idea in this lesson, because it generalises: you do not need the previous answer, you need the reduction of everything before you, and reductions parallelise.
The two-pass algorithm below is the practical form. Pass one: chunk the array and compute each chunk's total in parallel — an ordinary parallel reduce. Then compute an exclusive scan over the P chunk totals, which is sequential but P is tiny. Pass two: each chunk scans itself locally, offset by its chunk's prefix — parallel again. Two parallel passes over the data plus a trivial sequential middle, giving span O(log n) work-efficiently, at the cost of reading the array twice.
Once you see it, the pattern shows up everywhere: computing output offsets before a parallel compaction or partition, converting counts to positions in a radix sort, allocating ranges from variable-length outputs, line-start offsets when parsing a buffer in parallel. Any time you were about to write "I need a running counter, so this loop has to be sequential", the answer is usually a scan. And any time the operator is genuinely non-associative — a state machine whose transition depends on the accumulated state in a way that cannot be composed — the loop really is sequential, and the parallelism has to come from processing many independent inputs rather than one input faster.
- The sequential middle pass is over P chunk totals, so it is negligible — the serial fraction was shrunk, not eliminated (Amdahl's Law).
- Two passes over memory instead of one: work-efficient in operation count, not in bandwidth.
- Requires associativity, exactly like reduce. Non-associative operators have no parallel scan.
- Writes are disjoint by construction, so there are no locks anywhere in the algorithm.
1// Inclusive scan of a[0..n) into out[0..n) with an associative op.2// Span is O(log n)-ish; total work is about 2n reads instead of n.3void parallel_scan(const std::vector<int64_t>& a,4 std::vector<int64_t>& out,5 int P) // P = chunk count, P << n6{7 const size_t n = a.size();8 const size_t chunk = (n + P - 1) / P;9 std::vector<int64_t> chunk_total(P, 0);10 11 // -- 1: PARALLEL. Each chunk reduces itself. No sharing: chunk c writes12 // only chunk_total[c], and reads only its own slice.13 parallel_for(0, P, [&](int c) {14 int64_t acc = 0;15 for (size_t i = c * chunk; i < std::min((c + 1) * chunk, n); ++i)16 acc += a[i];17 chunk_total[c] = acc;18 });19 20 // -- 2: SEQUENTIAL, but over P elements, not n. This is the whole trick:21 // the irreducibly serial part was made tiny, not removed.22 std::vector<int64_t> offset(P, 0);23 for (int c = 1; c < P; ++c)24 offset[c] = offset[c - 1] + chunk_total[c - 1]; // exclusive scan25 26 // -- 3: PARALLEL. Each chunk scans locally, seeded with its offset.27 parallel_for(0, P, [&](int c) {28 int64_t acc = offset[c];29 for (size_t i = c * chunk; i < std::min((c + 1) * chunk, n); ++i) {30 acc += a[i];31 out[i] = acc; // disjoint writes: no locks32 }33 });34 // Note: for floating point, out[] will differ in the last bits from a35 // sequential scan, for exactly the reason in [[parallel-reduce]].36}Sorting, and what the recursion tree actually tells you
Parallel merge sort is the canonical divide-and-conquer example, and its recursion tree makes the limiting factor visible. Splitting is free and the leaves are perfectly parallel, but merging is not: the final merge combines two n/2 runs into one n run, and a *sequential* merge at the root has span O(n) — which means that no matter how many cores you throw at the leaves, the last merge alone takes linear time and caps your speedup at roughly log n. The fix is a parallel merge (binary-search each run's median into the other and merge the pieces independently), which brings the span down to O(log² n) and is why library parallel sorts are more complicated than "recurse in parallel".
The tree also shows the other structural fact: parallelism is maximal at the leaves and minimal at the root. Early on there is one task; near the leaves there are n/cutoff. So the top of the recursion under-uses the machine and the bottom over-decomposes it, which is exactly why every parallel divide-and-conquer has a sequential cutoff — below some size, stop forking and sort the block with an ordinary sequential algorithm, usually insertion sort for very small blocks.
Quicksort inverts the structure: the partition is the expensive part and the combine is free, so it parallelises well when pivots are balanced and turns into a straggler problem when they are not — the same skew story as Fork/Join, arriving through pivot choice. It is worth noticing that the two algorithms fail in opposite places, which is a good reason to know both shapes rather than one sorting function.
Key points
- Map, reduce, scan, sort and divide-and-conquer cover most parallel programs; recognising the shape is the transferable skill.
- Work is total operations; span is the longest sequential chain and is the floor no core count beats.
- Parallel algorithms often do *more* total work to shorten the span, and that trade is usually correct above a few cores.
- A running total is not sequential: you need the reduction of everything before you, and reductions parallelise. Scan is the answer to "I need a running counter".
- Scan needs associativity, exactly as reduce does; genuinely non-associative accumulation is irreducibly sequential within one input.
- In parallel merge sort the final merge is the critical path, which is why library implementations parallelise the merge itself.
- Every recursive decomposition needs a sequential cutoff — the top of the tree under-uses the machine and the bottom over-decomposes it.
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.
- • Identify the shape: is each element independent (map), is everything folded to one value (reduce), does each output depend on all prior inputs (scan), is it a permutation (sort), or is it a recursive split (divide-and-conquer)?
- • Check the algebraic requirement: independence for map, associativity for reduce and scan, a total order for sort, subproblem independence for divide-and-conquer.
- • Estimate span: constant for map, logarithmic for tree reduce and two-pass scan, and the recursion depth times combine cost for divide-and-conquer.
- • Choose a decomposition with more pieces than workers so a stealing scheduler can balance, and a sequential cutoff so pieces stay large enough to be worth scheduling.
- • Write results into disjoint locations so no synchronization is required inside the parallel phases.
- • Measure against the sequential version at several sizes to find the crossover, and keep the sequential version as the implementation below it.
- • Parallel map: workers process disjoint index ranges; every interleaving produces identical output because no worker reads what another writes.
- • Parallel map with a shared output index (
out[next++] = f(x)): two workers read next = 500, both write slot 500, one result is lost and slot 501 is never written — the classic reason parallel *filter* needs a scan to compute offsets first. - • Two-pass scan: all chunk reductions complete, then the P-element sequential pass runs, then all local scans run. A local scan that starts before the offsets are computed reads a zero offset and produces silently wrong running totals for every element in its chunk.
- • Parallel merge sort: sibling subtrees sort concurrently and touch disjoint ranges; merges at each level are independent; only the parent-child dependency is ordered, and it is enforced by the join.
- • Parallel quicksort with a pathological pivot: one partition holds 99% of the elements, its subtree becomes the critical path, and every other worker idles — correct output, no speedup.
- • In-place parallel partition without care: two workers swapping elements across the same boundary corrupt the permutation — which is why the simple parallel sorts use a separate output buffer.
- • Guaranteed: parallel map, reduce (associative), scan (associative) and merge sort produce exactly the sequential result for integer and comparison operations.
- • Guaranteed: with disjoint output ranges, no synchronization is needed within a parallel phase — the decomposition is the synchronization.
- • NOT guaranteed: bitwise identity for floating-point reduce or scan. Grouping changes rounding (Reduction Ordering: The Sum Changed When the Worker Count Did).
- • NOT guaranteed: stability of a parallel sort. Some parallel sorts are stable, many are not, and the docs are the only authority.
- • NOT guaranteed: that a parallel algorithm does the same amount of work as the sequential one. Scan does about twice as many operations; that is the price of the shorter span.
- • NOT guaranteed: speedup proportional to cores. Span, memory bandwidth and the sequential cutoff all cap it well before that.
- • NOT guaranteed: that a "parallel" library call actually runs in parallel. Many fall back to sequential below a size threshold, or when no thread pool is available.
- • Well-formed parallel map, reduce and scan contend on nothing but memory bandwidth — the decomposition removes logical sharing entirely.
- • The merge phase of a parallel sort concentrates work at the root, so the machine is under-used exactly when the remaining work is largest.
- • Any shared output cursor (a
next++index) is a serialisation point and a lost-update hazard; compute offsets with a scan instead. - • Deep recursion produces many small tasks whose scheduling and stealing overhead contends with the work itself (Work Stealing).
- • Adjacent per-chunk result slots are a False Sharing: Different Variables, Same Cache Line site when written repeatedly, though the algorithms here write each slot once.
- • Lost update on a shared output cursor in a parallel filter or compaction — missing and uninitialised output slots.
- • Reading a scan offset before the sequential middle pass completed, producing wrong running totals for a whole chunk.
- • Straggler subtrees in quicksort from unbalanced pivots — correct output, no speedup, and the profile blames the wrong thing.
- • Sequential merge at the root capping merge-sort speedup at roughly log n regardless of core count.
- • Over-decomposition below the cutoff, where task overhead exceeds the work and the parallel version is slower than sequential.
- • Assuming stability from a parallel sort that does not provide it, which shows up as reordered equal keys much later.
- • Applying a parallel scan or reduce with a non-associative operator, producing run-dependent results.
- • Large inputs with substantial per-element work, where map and reduce give near-linear speedup for very little code.
- • When a scan removes an apparent sequential dependency — parallel filter, compaction, partition, offset computation and parallel parsing all rest on it.
- • Sorting above a size threshold, where library parallel sorts deliver a solid multiple of sequential with no correctness work from you.
- • Recursive problems whose subproblems are naturally independent and comparable in size.
- • Small inputs, where the sequential version wins and the cutoff exists precisely to fall back to it.
- • Cheap per-element operations over big arrays, where memory bandwidth caps the result far below core count (Memory Bandwidth: More Cores, Same Bus).
- • Genuinely sequential dependence — a state machine, a running compression dictionary, an iterative solver whose step depends on the last — where the parallelism must come from independent inputs instead.
- • Unbalanced recursion, where one subtree dominates and the speedup collapses to that subtree.
- • When the sequential algorithm has a better constant factor: an O(n log n) parallel algorithm can lose to an O(n log n) sequential one with cache-friendly access patterns.
- • Speedup versus core count at several input sizes — the family of curves shows both the crossover and the span ceiling.
- • Wall time against sum-of-task-times ÷ cores, which separates imbalance from overhead.
- • Achieved memory bandwidth versus machine peak, to tell "not enough cores" from "no bandwidth left".
- • Task count and mean task duration, to check the cutoff: microsecond tasks mean it is too low.
- • Per-subtree time in a recursive algorithm, which localises a straggler to a specific pivot or split.
- • Equality against the sequential result on the same input — exact for integers, within tolerance for floats.
- • You now maintain a sequential implementation and a parallel one, plus the cutoff that chooses between them, and both need testing.
- • Cutoff and chunk-count constants are hardware-dependent tuning parameters with the same staleness problem as pool sizes.
- • The algebraic preconditions (associativity, independence, total order) are obligations the compiler will not check.
- • Parallel variants often need extra memory — an output buffer for scan and merge — which changes the memory profile of the whole program.
- • Debugging shifts from stepping through a loop to reasoning about a decomposition, and the failure is usually a wrong number rather than a crash.
- • The sequential algorithm, always the baseline — for most real input sizes it is the right answer and it is already correct.
- • A library parallel algorithm (parallel STL, rayon, Java streams) instead of a hand-rolled one: same shape, far fewer opportunities to be wrong.
- • SIMD within one thread, when the operation is uniform over adjacent data — often several times faster with no coordination at all (SIMD: One Instruction, Many Elements).
- • A better sequential algorithm: an O(n) approach beats a parallel O(n log n) one at every core count, and algorithmic improvement composes with parallelism rather than competing with it.
- • Parallelism across independent inputs rather than within one, when the computation is genuinely sequential — the answer for state machines and iterative solvers.
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 ]
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
Work, span and the speedup ceiling
critical path A → D → F → G = 90 ms work 20 + 30 + 25 + 40 + 15 + 20 + 10 = 160 ms ceiling T₁ / T∞ = 160 / 90 = 1.78× no extra edges — toggle one above
What people believe, and what is true
A running total cannot be parallelised because each value needs the previous one.
It needs the *reduction* of everything before it, and reductions parallelise. A two-pass scan does it with a logarithmic span at roughly twice the work.
The parallel algorithm is worse because it does more operations.
Parallel algorithms routinely trade extra work for a shorter critical path. That is a losing trade on one core and a winning one on many.
Parallel merge sort splits in parallel, so it scales with cores.
The final merge is the critical path. With a sequential merge the span is linear and speedup caps near log n no matter how many cores you have.
If the library call is named "parallel", the work ran in parallel.
Most implementations fall back to sequential below a size threshold or without an available thread pool, and none of them are obliged to tell you.
Go deeper
Overview
Most parallel work is one of five shapes: do the same thing to everything, squash everything into one value, running totals, sorting, or split-and-recurse.
Practical
Use library implementations, keep a sequential fallback below a cutoff, and reach for a scan whenever you think a loop needs a running counter.
Advanced
Span is the ceiling. Parallelise the merge in merge sort, watch pivot balance in quicksort, and never let a shared output cursor into a parallel loop — compute offsets with a scan.
Internals
Work-efficient scan is up-sweep then down-sweep over a balanced tree; the two-pass chunked version is the practical CPU form because it trades a tiny serial section for excellent cache behaviour.