Parallel Decomposition
Fork/join, parallel reduce, map/reduce as a computational pattern, the overhead that makes parallelising small work slower, Amdahl and Gustafson as complementary intuitions, and work versus span as the real ceiling on a dependency graph.
Split the work, run the pieces, wait for all of them, combine. The split is easy and the combine is arithmetic — the join is the part that carries the correctness, because it is the only place a happens-before edge exists between the children and the parent that reads their results.
Q · What exactly does the join give me, beyond "the children finished"?
Sum a billion numbers by summing chunks and combining the partials. The decomposition is trivial and the requirement is not: the combine must be associative, or "the same computation" produces a different answer depending on how the runtime happened to schedule it.
Q · Which reductions can be parallelised safely, and what exactly does the combine operation have to satisfy?
Not a product and not a framework — a computational shape. Transform each input independently, group the intermediates by key, reduce each group. Once you can see the shape you find it everywhere: in a SQL GROUP BY, in a browser tab counting words, in a metrics pipeline, in eight lines of local code.
Q · What is the actual computational pattern here, independent of any system that implements it?
Map, reduce, scan, sort and divide-and-conquer are the primitives almost every parallel program is built from. The useful skill is not implementing them — your library already did — it is recognising which shape a problem has, and knowing that scan is parallelisable at all.
Q · Which computations have a parallel form at all, and how do I recognise the shape of the one in front of me?
Splitting, scheduling, synchronizing and combining are work the sequential version never does. For small tasks that overhead exceeds the task, and the parallel version is measurably slower on more hardware — which is why every parallel decomposition needs a size below which it stops decomposing.
Q · Why is my parallel version slower than the sequential one, on the same machine, with more cores working?
The part that cannot be parallelised sets a ceiling on everything else. If a tenth of the job must happen in sequence, an infinite number of cores still cannot make it more than ten times faster — and long before infinity, each extra core is buying almost nothing.
Q · I parallelised the expensive loop and the job is only twice as fast on sixteen cores — where did the rest of the speedup go?
The complement to Amdahl, not the refutation. Amdahl fixes the problem and asks how much faster a bigger machine makes it. Gustafson fixes the time budget and asks how much bigger a problem the machine lets you solve — and for that question the scaling looks almost linear.
Q · If bigger machines barely help a fixed job, why does everyone keep buying them?
Work is everything the computation has to do; span is the longest chain of steps that must happen one after another. Work divided by workers is the optimistic answer, span is the floor, and no scheduler, runtime or core count gets you below the span.
Q · How much parallelism does this computation actually contain, before I go looking for a machine to run it on?
Draw the edges and the parallelism reveals itself. A depends on nothing; B, C and D depend on A; E depends on D. That graph tells you exactly which tasks can run simultaneously, which chain sets the finish time, and which task is worth optimising — before you write a scheduler or buy a core.
Q · Given a set of tasks and what each one needs, which of them can actually run at the same time?