Amdahl's law

Amdahl's three-page paper has no equation and one figure. He observed that about 40 percent of the instructions executed in typical programs were data-management housekeeping, that this part looked inherently sequential, and that overhead alone would cap throughput at five to seven times the sequential rate however much parallel hardware you added. Others wrote it as a formula: if a fraction p of a job can be sped up by a factor n, total speedup is 1 / ((1 - p) + p / n). With p = 0.95 and unlimited n the speedup tends to 1 / 0.05 = 20. With n = 100 it is 16.8. The 5 percent you did not touch becomes the whole job as the rest shrinks.

It holds because it is arithmetic over a fixed total: the untouched part keeps its absolute time while everything around it shrinks. The transfer is to any pipeline. If a request spends 70 percent of its time in a model call and 5 percent parsing, a parser ten times faster saves 4.5 percent. The site's post on reducing large language model (LLM) API costs makes the same argument about money: output tokens cost several times input tokens, which points at shaving answers, but input tokens dominate the volume, so the big factor is the context resent on every call. Measure the fractions first, then work on the largest one.

John Gustafson's 1988 reply from Sandia showed the catch: Amdahl's picture assumes a fixed problem size, and in practice problems grow with the machine, so the serial fraction shrinks. On a 1024-processor hypercube his three applications reached speedups of 1021, 1020 and 1016. Yuan Shi showed in 1996 that this does not break the law: Gustafson's serial fractions are measured on the parallel machine, and translating them to Amdahl's definition gives 0.0004 to 0.0008 percent, for which Amdahl's formula predicts 1020 to 1016. The law is right; the serial fraction has to be measured for the problem you will run, and coordination overhead can grow with n and bend the curve downwards.