Amdahl’s Law

Amdahl’s Law bounds the speedup from parallelizing a task. A task splits into a serial fraction and a parallel fraction. The serial fraction is the ceiling. No matter how many processors you add, the serial part still runs sequentially. From ECE459 L09.

On $N$ processors, the parallel time is:

$T_p=T_s\cdot \left(S+\frac{P}{N}\right)$

where:

• $T_s$ is the serial (single-processor) runtime
• $S$ is the serial fraction of the work
• $P=1-S$ is the parallelizable fraction
• $N$ is the number of processors

This rearranges into the speedup form:

$\text{speedup}=\frac{1}{(1-P)+P/N}\stackrel{N\to \infty }{\to }\frac{1}{1-P}$

The limit on the right is the hard ceiling set by the serial fraction alone.

Plugging in at $N=18$:

$P$	Speedup
$1$	$18\times$
$0.99$	$\sim 15\times$
$0.95$	$\sim 10\times$
$0.5$	$\sim 2\times$

Even a 5% serial fraction caps you at roughly $10\times$ on 18 cores.

Estimating $P$ empirically from a measured speedup at $N$:

$P_{\text{est}}=\frac{1/\text{speedup}-1}{1/N-1}$

where:

• $\text{speedup}$ is the observed speedup at $N$ processors
• $N$ is the number of processors used in the measurement

Generalized to many parts with individual speedups:

$\text{speedup}=\frac{1}{\frac{f_1}{S_{f_1}}+\frac{f_2}{S_{f_2}}+\dots }$

where:

• $f_i$ is the fraction of original runtime spent in part $i$
• $S_{f_i}$ is the speedup applied to part $i$

Use it to pick between optimization options: whichever formula gives the larger number wins. The speedups don’t have to come from parallelization.

Example from L09. A program with 4 parts; you can implement Option 1 or Option 2:

Part	Fraction of runtime	Option 1 speedup	Option 2 speedup
1	$0.55$	$1$	$2$
2	$0.25$	$5$	$1$
3	$0.15$	$3$	$1$
4	$0.05$	$10$	$1$

Plug and chug:

$\text{Option 1: }\text{speedup}=\frac{1}{0.55+\frac{0.25}{5}+\frac{0.15}{3}+\frac{0.05}{10}}=1.53$

$\text{Option 2: }\text{speedup}=\frac{1}{\frac{0.55}{2}+0.45}=1.38$

Option 1 wins. Option 2 attacks the biggest fraction but only at $2\times$. Spreading smaller speedups across the other parts adds up to more.

Assumptions that make Amdahl pessimistic

Amdahl assumes a fixed problem size, identical behaviour at 1 vs $N$ processors, and no overheads. It ignores synchronization cost, which drags real speedup down further.

Amdahl asks what fraction of your code can you parallelize. Gustafson’s Law flips the question: in practice you can just make the problem bigger.

Related

• Gustafson’s Law