Amdahl's law

Suppose a road trip is 100 hours: 90 hours of open highway where extra horsepower helps, and 10 hours stuck in city traffic where it does not. If you buy an infinitely fast engine, you erase the 90 highway hours but the 10 city hours remain — so the trip can never drop below 10 hours, no matter how much you spend. Amdahl's law is this hard ceiling for parallel computing: the part of a program that must run serially sets a floor on the total time, so adding cores can only ever speed up the part that parallelizes, never the rest.

Put it in numbers. Let f be the fraction of the work that is inherently serial (must run on one core), so 1 - f is the parallelizable fraction. With N cores, the parallel part finishes in (1 - f)/N of its original time while the serial part stays at f. So the speedup is 1 / (f + (1 - f)/N). Now let N go to infinity: the (1 - f)/N term vanishes and speedup approaches 1/f. If just 10 percent of a program is serial (f = 0.1), the maximum possible speedup is 1/0.1 = 10x — even with a million cores. A mere 5 percent serial caps you at 20x. The serial fraction, not the core count, is the dictator.

This is the sobering law of the multicore era and the honest rebuttal to 'just add more cores.' It explains why throwing cores at a problem yields diminishing returns and why the serial bottleneck — startup, final reduction, locking, I/O — is where optimization effort pays off. There is an important counterpoint, Gustafson's law: in practice people grow the problem to fit the machine (run a bigger simulation on more cores), and for such scaled workloads the serial fraction shrinks relative to the growing parallel work, so large speedups stay achievable. Both are true — Amdahl bounds a fixed problem, Gustafson describes a growing one — and which applies depends on whether your workload is fixed-size or scalable.