Parallel Computing: Thousands of Calculations at Once
Learn what makes work parallel, how even a sum can be split up, and the limit no number of workers can beat.
A GPU’s thousands of cores only help if the work can be shared out. So what exactly makes a job “parallel”?
The test is dependency. Eight painters can each take a plank of a fence, because no plank waits for another. A cake is different: you can’t bake before you’ve mixed, or ice before you’ve baked. Hire eight bakers and the cake is no faster.
Some jobs look like cakes but can be rearranged into fences. Adding up a long list seems hopelessly step-by-step: total = total + next number, over and over. But addition doesn’t care about order. Split the list into pairs, add every pair at the same moment, then pair up the results, and so on. Sixteen numbers take four rounds instead of fifteen steps; a million numbers take twenty rounds instead of a million. The total number of additions is the same. Only the waiting disappears. GPU programs do this all the time: it’s called a reduction.
There’s a catch, spotted by computer architect Gene Amdahl in 1967. If even a small part of a job must run one step at a time, that part eventually dominates. Suppose 5% of a job is cake and 95% is fence. With infinite workers the fence part takes no time at all, but the cake part still takes 5%, so the job can never get more than 20× faster. This is Amdahl’s law, and it’s why engineers obsess over the last stubborn bits that won’t parallelise.
Neural networks are a lucky case: almost all fence. Millions of independent multiplications, plus sums that rearrange into trees. That is the deep reason they scale so well to thousands of cores, and later to thousands of GPUs.
Key takeaways
- Work is parallel when its pieces don’t wait for each other.
- Some sequential-looking jobs, like sums, can be rearranged into trees: same work, far less waiting.
- Amdahl’s law: the part that must run in order caps the speed-up at 1 ÷ (that share).
- Neural network maths is almost entirely parallel, which is why it scales to thousands of cores.
Check your understanding
Go deeper (more technical)
Amdahl’s law: speed-up = 1 / (s + (1 − s) / N), where s is the sequential share and N the number of workers. As N → ∞ it approaches 1/s. Its optimistic sibling, Gustafson’s law (1988), points out that with more workers we usually tackle bigger problems, where the parallel part grows and s shrinks: bigger models and bigger batches are exactly that.
On GPUs, reductions appear in softmax (summing exponentials), layer normalisation and the dot products inside matrix multiplication. Libraries implement them as trees within a warp, then across warps, then across blocks. Note that changing the order of floating-point additions can change the last digits of the result, one source of tiny run-to-run differences.