Tuesday, July 10, 2007

Amdahl's Law

Amdahl's law, named after computer architect Gene Amdahl, is used to find the maximum expected improvement to an overall system when only part of the system is improved. It is often used in parallel computing to predict the theoretical maximum speedup using multiple processors.

The generalized Amdahl's law is:

\frac{1}{\sum_{k=0}^{n}{\big(\frac{P_k}{S_k}\big)}}

where

  • P_k \ is a percentage of the instructions that can be improved (or slowed),
  • S_k \ is the speed-up multiplier (where 1 is no speed-up and no slowing),
  • k \ represents a label for each different percentage and speed-up, and
  • n \ is the number of different speed-up/slow-downs resulting from the system change.