Amdahl's Law – Effective MIPS with n Processors (14 Marks)

Let $\alpha$ = fraction of code parallelizable (executable on $n$ processors simultaneously), so $(1-\alpha)$ is strictly sequential. Each processor rate = $x$ MIPS.

Let total instructions = $I$.

(a) Derivation:

Time if executed on single processor: $T_1 = \frac{I}{x}$ (in $\mu s$ if $x$ in MIPS, i.e., $10^6$ instr/sec)

With $n$ processors:

• Sequential part: $(1-\alpha)I$ instructions at rate $x$ → $T_{seq}= \frac{(1-\alpha)I}{x}$
• Parallel part: $\alpha I$ instructions shared among $n$ processors, effective rate $n\cdot x$ → $T_{par}= \frac{\alpha I}{n x}$

Total parallel time: $T_n = T_{seq}+T_{par}= \frac{I}{x}\left[(1-\alpha)+\frac{\alpha}{n}\right]$

Effective MIPS $M_{eff}= \frac{I}{T_n} = \frac{I}{\frac{I}{x}[(1-\alpha)+\alpha/n]} = \frac{x}{(1-\alpha)+\alpha/n}$

So $M_{eff}= \frac{x}{(1-\alpha)+\frac{\alpha}{n}} = \frac{n x}{n(1-\alpha)+\alpha}$

This is Amdahl's law: Speedup $S = \frac{T_1}{T_n}= \frac{1}{(1-\alpha)+\alpha/n}$, and $M_{eff}=x\cdot S$.

Checks: If $\alpha=0$ → $M_{eff}=x$ (no gain). If $\alpha=1$ → $M_{eff}=n x$ (linear). If $n\to\infty$ → $M_{eff}\to \frac{x}{1-\alpha}$ (bottleneck by sequential part).

(b) Numerical:

Given $n=16$, $x=4$ MIPS, $M_{eff}=40$ MIPS. Find $\alpha$.

$40 = \frac{4}{(1-\alpha)+\alpha/16}$

$(1-\alpha)+\alpha/16 = \frac{4}{40}=0.1$

$1-\alpha+0.0625\alpha =0.1$

$1-0.9375\alpha =0.1$

$0.9375\alpha =0.9$

$\alpha = \frac{0.9}{0.9375}=0.96$

$\alpha = 96\%$

Interpretation: 96% of code must be parallelizable to achieve 40 MIPS (≈10× speedup) with 16×4 MIPS processors. If $\alpha$ lower, cannot reach 40 MIPS even with infinite processors (max would be $x/(1-\alpha)$).