Amdahl's law

Suppose a job takes ten hours, and nine of those hours can be split among as many workers as you like, but one hour is a single task that only one person can do, start to finish. Hire a thousand workers and the nine parallel hours shrink to almost nothing — but that one stubborn hour remains. So the whole job can never drop below one hour, a 10x speed-up at best, no matter how many workers you throw at it. That hard ceiling is Amdahl's law, and it is the most sobering fact in parallel computing.

Stated precisely: if a fraction s of a program's work is inherently serial (cannot be parallelised) and the remaining fraction 1 - s is perfectly parallelisable across p processors, then the speed-up is S(p) = 1 / (s + (1 - s) / p). As p grows to infinity the parallel part vanishes and the speed-up tops out at 1 / s. So if just 5 percent of your runtime is serial (s = 0.05), the most you can ever get is a 20x speed-up — even with infinitely many cores. With 1 percent serial, the ceiling is 100x. The serial fraction, however small, sets a wall you cannot climb over by adding hardware; and worse, the diminishing returns bite early — going from 100 to 1000 cores on an s = 0.05 program barely moves the needle.

Amdahl's law is the reason 'parallelise everything' is naive and the reason profiling matters: the payoff from parallelism is dictated by your worst serial bottleneck, so the highest-value work is often eliminating or shrinking that serial fraction, not adding cores. It also explains a real frustration — a code that hits 8x on 16 cores but flatlines at 10x on 64. There is a hopeful counterpoint, Gustafson's law: in practice people do not keep the problem size fixed; they run bigger problems on bigger machines, and as the problem grows the parallel part usually grows faster than the serial part, so the effective serial fraction shrinks and large speed-ups stay reachable. Amdahl bounds fixed-size (strong) scaling; Gustafson rescues growing (weak) scaling.