Amdahl's law

• Observation made by Gene Amdahl

Observation

• When we speed up one part of a system, the effect on the overall system performance depends on:
  • Significance of that part
  • How much did the part speed up

Mathematical formula

Assumptions

• Assume that $T_{old}$ is the time required by the overall system to perform an operation before the improvement
• $\alpha$ - Fraction of the overall time consumed by the part that will be improved
• $k$ - Factor by which the part is improved
• $T_{new}$ - Time required by the overall system after the improvement

Derivation

$$\begin{array}{rl}Timeoriginallyrequiredbytheimprovedpart& =\alpha T_{old}\\ Timerequiredbythepartafterimprovement& =\frac{\alpha T_{old}}{k}\\ \therefore T_{new}& =T_{old}-\alpha T_{old}+\frac{\alpha T_{old}}{k}\\ & =T_{old}\left[(1-\alpha )+\frac{\alpha }{k}\right]\\ Speedup(S)& =\frac{1}{(1-\alpha )+\frac{\alpha }{k}}\end{array}$$

Example

• Consider the case where a part of the system initially consumed $\text{60\%}$ of the time. $(\alpha =0.6)$
• It is sped up by the factor of 3 $(k=3)$
• Then the overall system sped up by:

$$\begin{array}{rl}S& =\frac{1}{1-0.6+\frac{0.6}{3}}\\ & =\frac{1}{0.4+0.2}\\ & =\frac{1}{0.6}=\frac{10}{6}=\frac{5}{3}\\ & =1.67\text{x}\end{array}$$ $$\text{Thus the speedup, }S=1.67\text{x}$$

Implication

When $k=\infty$, $S_{\infty }=\frac{1}{1-\alpha }$.

Thus, high improvement can only be achieved by improving large parts of the system

Sources

• Computer Systems - A Programmer’s Perspective

Related Notes