The stubborn hour that no army can shrink
The previous guide handed you threads and MPI and showed how a job can be split across many workers, whether they share one memory or each hold their own piece. The natural hope is linear: ten workers, one tenth the time; a thousand workers, a thousandth. Amdahl's law is the cold splash of water that says no. Picture a ten-hour job where nine hours can be divided among as many workers as you like, but one hour is a single chore only one person can do start to finish — reading the input, say, or a setup step every later stage depends on. Hire a thousand workers and the nine parallel hours melt to almost nothing, yet that one stubborn hour remains. The whole job can never drop below one hour: a 10x speed-up at best, no matter the army.
Made precise: if a fraction s of the work is inherently serial (cannot be parallelized) and the rest, 1 - s, parallelizes perfectly across p processors, the speed-up is S(p) = 1 / (s + (1 - s) / p). Push p to infinity and the parallel term vanishes, leaving S = 1 / s. That is the whole story in one fraction — the ceiling is set entirely by the serial slice. A program that is 95% parallel (s = 0.05) caps at 1/0.05 = 20x however many cores you buy; one that is 99% parallel caps at 100x. The sobering part is how little serial work it takes to cap you low. Just 5% serial, and 999 of your thousand cores are buying you nothing beyond the first twenty-fold.
Amdahl's law (fixed problem, add processors):
S(p) = 1 / ( s + (1 - s)/p ) s = serial fraction
S(infinity) = 1 / s the hard ceiling
s = 0.50 -> cap 2x (p=8 already gives ~1.8x)
s = 0.10 -> cap 10x (p=8 gives ~4.7x)
s = 0.05 -> cap 20x
s = 0.01 -> cap 100x (need p=100 just to reach 50x)Strong scaling, weak scaling, and an honest escape hatch
Amdahl sounds like a death sentence for supercomputers, yet machines with a million cores are clearly worth building — so something in the picture is too pessimistic. The fix is to notice that Amdahl quietly froze one thing: the problem size. Asking 'fixed job, more workers — how much faster?' is strong scaling, and it is the harsh regime, because as you add processors each one's slice of work shrinks until the fixed serial hour dominates everything. But scientists rarely keep the job fixed. Given a bigger machine they simulate a finer mesh or more particles. The honest question becomes 'bigger job in the same time — how many more workers?' That is weak scaling, and it is far kinder.
Why is weak scaling kinder? Often the serial part is a roughly fixed overhead while the parallel part grows with the problem. Double the cores and the mesh, and the parallel work per core stays constant while the serial fraction s actually shrinks as a share of the now-larger total. The ceiling 1/s lifts as you grow. This is Gustafson's observation, the optimistic twin of Amdahl: with a workload that scales up alongside the hardware, useful speed-up keeps coming. Both laws are true; they answer different questions. Strong scaling tells you whether more cores finish this job faster (and Amdahl caps that hard). Weak scaling tells you whether more cores let you tackle a bigger job in the same wall-clock time (and here the news is good).
The stadium of line cooks: how a GPU works
If Amdahl warns you that parallelism has limits, the GPU is the machine that pushes those limits to an extreme and forces you to confront everything this rung has taught. The picture: a CPU is a few brilliant chefs, each following a complicated recipe quickly; a GPU is a stadium full of line cooks, each slow and simple, but thousands of them, all doing the identical chopping motion at once. For a varied gourmet meal you want the chefs. But for peeling ten thousand potatoes the exact same way, the army of line cooks finishes in a flash. GPU computing is the art of recasting numerical work into that second shape — the same operation on thousands of different data items — so the graphics chip's enormous parallelism can be unleashed.
This is the same SIMD idea you met in the vectorization guide, scaled up wildly. Where a CPU's vector unit applies one instruction to maybe eight numbers at once, a GPU runs thousands of threads in lockstep, all executing the identical instruction on their own slice of data. The catch is exactly the catch of SIMD: when threads must take different branches — some take the if, some take the else — the hardware can no longer keep them in step. It runs both paths and masks off the threads that should not act, so a kernel full of data-dependent branches throws away much of the machine. GPUs love straight-line, uniform arithmetic and punish irregular, branchy code. The work that fits is dense linear algebra, stencil sweeps, particle updates — and it is no accident these are this rung's bread and butter.
There is a second, deeper subtlety, and it connects straight back to guide one of this rung. A GPU has astonishing peak flops, but its arithmetic units starve unless data reaches them fast enough. GPUs hide memory latency not with big caches but with sheer oversubscription: tens of thousands of threads in flight, so that whenever one stalls waiting on memory, another ready thread instantly takes its place and the arithmetic units never idle. That trick only works if there is a huge supply of independent work — which is yet another way of saying GPUs demand massive, uniform parallelism. And just as on a CPU, a GPU kernel that touches memory in a scattered, cache-unfriendly pattern is throttled by memory bandwidth, not by flops. The roofline model applies to GPUs too; the machine is just bigger and the penalty for poor data locality even steeper.
Mixed precision: trading digits for speed, on purpose
GPUs sharpened a question that the rest of this rung mostly took for granted: how many digits do you actually need? Almost all scientific computing runs in double precision — 64 bits, about 16 decimal digits — because it is the safe default. But narrower formats are dramatically cheaper: a 32-bit single moves half the bytes and runs roughly twice as fast, and the 16-bit half precision that GPUs added for machine learning can be faster still, often several-fold, because so much of the work is memory-bound and fewer bytes means more numbers per trip from memory. The temptation is obvious. The danger is just as obvious: half precision carries only three or four reliable decimal digits, so naive use is a fast route to a meaningless answer.
The escape is mixed precision: do the bulk of the work in a cheap low precision, but guard the few steps where accuracy is fragile in high precision. The classic pattern is iterative refinement for solving A x = b. Factor A and take the first solve in single (or half) precision — fast but only roughly accurate. Then compute the residual r = b - A x_hat in double, solve the correction in cheap precision, and add it back. A few such cycles recover full double-precision accuracy while most of the flops ran at the cheap rate. You get the speed of low precision and the answer quality of high precision, because the expensive, accuracy-critical part — measuring the residual — is small.
Closing the rung: where the speed really comes from
Stand back and the whole rung tells one coherent story. Flops are cheap and memory is slow, so a good algorithm hoards locality and the memory hierarchy decides its speed. That is why BLAS-3 matrix-matrix kernels, which reuse each loaded number many times, run near peak while bandwidth-bound kernels crawl. Parallelism multiplies the arithmetic units, but Amdahl caps the payoff at 1/s and communication taxes it further. The GPU is the extreme expression of all of it at once: thousands of cheap units, brutal demands on locality and uniformity, and the same memory wall as everywhere else. Mixed precision is the newest lever, trading digits you can spare for speed you can use.
Notice what almost never appears on this list: lowering the flop count. The instinct from a first algorithms course — count operations, minimize them — is the wrong instinct for performance on real hardware, where two algorithms with the same flop count can differ by 10x because one streams memory nicely and the other thrashes the cache. This is the quiet thread running through every guide here: on a modern machine, where the data is matters more than how many operations you do. The reorderings and blockings that win are exactly the ones that keep hot data close, not the ones that shave a few multiplications.
One last honesty, the kind this whole ladder insists on. None of this changes a single digit of the answer's correctness theory. A GPU running a backward-unstable algorithm fast still produces garbage fast; mixed precision on an ill-conditioned problem just reaches the wrong answer sooner. Performance and accuracy are separate axes, and a fast wrong answer is the most expensive kind. So the discipline is to pick a stable algorithm for a well-conditioned problem first, then make it fast — chase locality, lean on tuned BLAS, parallelize what Amdahl allows, drop precision only where conditioning permits. Get that order right and the machine, however many cores or line cooks it holds, finally works for you.