Learning path

Full curriculum

Full curriculum

Arrows go from each prerequisite to the units that depend on it. Hover or focus a unit to highlight its path.

Unit content

Amdahl's and Gustafson's scaling laws

Serial work places a hard limit on strong scaling.

Suppose a fraction $s$ of a fixed workload must remain serial and the remaining fraction $1-s$ parallelizes perfectly over $p$ processors. Amdahl's law gives the idealized speedup

$$S_p=\frac{1}{s+\frac{1-s}{p}}.$$

If $10%$ of the work is serial and $p=8$,

$$S_8=\frac{1}{0.1+0.9/8}\approx4.71,$$

far below eightfold speedup. As $p\to\infty$, the limit is $1/s=10$.

Amdahl's law assumes the problem size is fixed. Many parallel machines are instead used to solve larger problems. If the serial fraction of the parallel execution time is $s$, Gustafson's law estimates scaled speedup as

$$S_p^{\text{scaled}}=p-s(p-1).$$

With $p=8$ and $s=0.1$, this gives $7.3$: the larger problem contains more parallel work while the serial portion stays relatively small.

The two laws answer different questions. Amdahl asks how much faster a fixed job can become; Gustafson asks how much larger a job can be solved effectively as resources grow.