Why we go wide instead of fast
The first three guides of this rung told a single story: on real hardware the bottleneck is rarely arithmetic. The memory hierarchy makes a cache miss cost hundreds of cycles, so data locality and the BLAS-3 trick of reusing data in cache decide whether a kernel runs near its peak. All of that was about ONE processing core working as hard as it can. This guide adds the other lever the hardware gives you: instead of making one core faster, use many cores at the same time. That is parallelism, and it is no longer optional — it is the only direction the silicon still grows.
For decades a single core simply got faster each year: the clock ticked higher and you did nothing but recompile. Around the mid-2000s that engine stalled. Pushing the clock higher burned power roughly like the cube of the frequency and the chips melted — the so-called power wall. So designers stopped raising the clock and started stamping out MORE cores at the same speed: dual-core, then dozens, then thousands of tiny cores on a GPU. The free lunch ended. From then on a faster program is one that splits its work across cores, and the central design question becomes how those cores share data.
Splitting work is easy to say and hard to do well, because a numerical computation is a web of dependencies: x_{n+1} usually needs x_n. The art is finding the pieces that DON'T depend on each other and can run at the same time. Adding two vectors of length N is gloriously parallel — every entry c_i = a_i + b_i is independent, so a thousand cores can each take a slice. Summing one vector into a single number is trickier, because the running total is shared. Hold that contrast; it is the seed of everything in this guide.
Two memory models: one shared room or many mailboxes
There are two fundamentally different ways to wire many cores together, and the distinction is shared-memory versus distributed-memory, the shared- versus distributed-memory split. Picture it physically. Shared memory is one big room with many workers: every core can read and write the same address space directly, like colleagues writing on one shared whiteboard. Distributed memory is many separate rooms, each worker with their own private whiteboard; if room A needs a number from room B, someone has to physically carry it over. That carrying is the whole story of distributed computing.
Shared memory lives inside a single computer — the multicore chip in your laptop or one node of a cluster. You program it with threads: lightweight workers spun off the same process that all see the same data. The classic tools are OpenMP (you sprinkle hints like "run this loop in parallel" over ordinary code) and pthreads underneath. Communication is free in the sense that there is nothing to send — everyone already sees the whiteboard. The catch, as we will see, is that everyone can also scribble on it at once.
Distributed memory spans many computers — the hundreds or thousands of separate nodes in a supercomputer, each with its own RAM, linked by a fast network. There is no shared whiteboard at all, so cores cooperate by message passing: one process packs up a chunk of data and explicitly sends it across the wire, another receives it. The universal standard is MPI (Message Passing Interface), the message-passing model. It is more verbose to program — you write the sends and receives by hand — but it is the only model that reaches beyond a single machine, and it is how essentially every large simulation on Earth actually runs.
The hazard of sharing: race conditions
Shared memory's gift — everyone sees the same data — is also its trap. Suppose two threads both want to add their slice's partial sum into one shared total. "Add to total" looks like one action but is really three: read total from memory, add your value, write the new total back. If both threads read the old value before either writes, one update silently overwrites the other and a number simply vanishes. This is a race condition, the race condition: the answer depends on the unpredictable timing of who got there first, so the program gives different results on different runs.
shared: total = 0
Thread A Thread B
-------- --------
read total (sees 0)
read total (sees 0)
add 5 -> 5
add 3 -> 3
write total = 5
write total = 3 <-- A's +5 is LOST
final total = 3 (should be 8)
Run it again and timing may differ -> a DIFFERENT wrong answerThe fix is coordination, and it costs you. A lock (or mutex) lets only one thread touch the total at a time; an atomic operation makes "read-add-write" indivisible in hardware. Both work, but both serialize that step — while one thread holds the lock the others wait, which eats into the very speed-up you came for. The honest engineering move is to avoid the contention instead: give each thread its OWN private partial sum with no sharing at all, and combine the few partials only at the very end. Distributed memory sidesteps the hazard entirely — separate whiteboards cannot be scribbled on by a stranger — at the price of writing explicit messages.
Splitting a real problem: domain decomposition and reductions
How do you actually parallelize a PDE solve, the kind from the finite-difference rung? You cut up the geometry. Domain decomposition, the domain-decomposition idea, hands each process a tile of the grid — process 0 gets the left strip, process 1 the next, and so on. Each updates its own interior with no communication at all. The only data that must move is the thin boundary between neighbors: to update its edge cells, a process needs one layer of values from the tile next door. Those border layers are called ghost cells or halos, and each step the neighbors exchange them with a couple of MPI messages.
Notice the beautiful economy here. A tile of side L holds about L^2 interior points to update (work that grows like the area) but only about 4L boundary points to communicate (cost that grows like the perimeter). So as the tiles get bigger, the ratio of communication to computation SHRINKS — this is the surface-to-volume effect, and it is the deep reason large simulations scale at all. The work is cheap, local, and abundant; the talking is expensive but only happens along the seams. Good parallel design is mostly the craft of keeping that ratio small.
Some operations cannot be made purely local, and the vector-sum from the opening is the prototype. Summing N numbers, or computing a dot product or an L2 norm, is a reduction: every value must funnel into one answer. The trick is to do it as a binary tree — pair up, add, pair up the partials, add, halving the count each round — which finishes in about log_2(N) steps instead of N. A close relative, the parallel prefix sum (scan), computes all the running totals in the same logarithmic depth, and it is the unsung workhorse behind parallel sorting, sparse-matrix layout, and compaction. The lesson: even "inherently sequential" combining can often be reshaped into a shallow, parallel tree.
What scaling actually buys you
Throwing more cores at a problem does not give proportional speed-up, and the reason is brutal arithmetic. Every program has a fraction of work that is stubbornly serial — reading the input, the final reduction, a bit that simply must run in order. Amdahl's law, the Amdahl's law bound, says if a fraction s of the work is serial, then no matter how many cores P you add, the speed-up can never exceed 1/s. If even 5% is serial, your ceiling is 20x — forever, on a million cores. The serial sliver, not the parallel ocean, sets the limit, and this is the single most sobering fact in parallel computing.
That sounds like a death sentence, but there is a way out, and it hinges on what you hold fixed. Strong scaling fixes the total problem size and adds cores — this is what Amdahl's law caps, because the serial part stays the same size while the parallel part shrinks per core. Weak scaling instead grows the problem in step with the cores, so each core always has a full tile of work. The strong- versus weak-scaling distinction matters because in practice we rarely want the SAME problem faster — we want a BIGGER problem, a finer mesh, in the same wall-clock time. Weak scaling is how a real supercomputer earns its keep.
And here is where this rung's whole arc closes. A single core was already limited by memory, not flops — its arithmetic intensity decides whether it is memory-bound or compute-bound. Adding cores multiplies the flops but ALSO multiplies the demand on shared memory bandwidth and the network. A parallel program can hit a bandwidth wall or a communication wall long before it runs out of cores. So the questions never change, only their scale: where is the data, who needs to talk to whom, and what fraction is stuck running in order? Honest parallel performance is measured, not assumed — you plot a scaling curve and find the real ceiling, because the model is a bound, not a promise.