= Amdahl's law
{c}
{title2=$S_p=1/(s+(1-s)/p)$}
<Amdahl's law> bounds the speedup obtained by accelerating only part of a fixed computation. Let fraction $s$ of its original execution time remain serial, while fraction $1-s$ divides perfectly among $p$ identical processors. Then
$$
T_p=T_1\left(s+\frac{1-s}{p}\right),\qquad S_p=\frac{T_1}{T_p}=\frac{1}{s+(1-s)/p}.
$$
The terms add because the serial and accelerated parts still both have to finish. If $s=0.1$, ten processors give $S_{10}=100/19\approx5.26$; even infinitely many cannot exceed speedup ten.
<Gene M. Amdahl>'s 1967 argument emphasized sequential work and irregularities in real computations.<Validity of the single processor approach to achieving large scale computing capabilities by Gene M. Amdahl>[printed p.483, sequential housekeeping and physical-problem irregularities]{ref} The displayed idealized formula follows from the stated time decomposition. Communication, <synchronization>, unequal work and limited <memory bandwidth> can reduce actual speedup. Increasing the problem size changes the serial fraction and asks a different scaling question.
Back to article page
