From WikiChip
Amdahl's Law

amdahl.svg

Amdahl's Law is a formulation an observation that attempts to give an upper bound on the performance increase that can be realized when a fixed workload is moved to a more parallel environment (e.g. multiprocessing or multi-core environment). The law is named after Dr. Gene M. Amdahl who first addressed the problem in his 1967 paper "Validity of the single processor approach to achieving large scale computing capabilities".

Amdahl's Law says that for fixed workloads, the upper bound of the speedup expected from moving to a more parallelized environment gets dominated by the sequential portion of the code as the parallel portion gets further divided into smaller and smaller chunks.

Theory

amdahl's law by sequential portion.png

Consider a program executing on a single-core uniprocessor computer. Suppose this program is operating on a fixed workload with a total execution time of Equation upper T minutes. Now let's suppose we want to divide or partition this program to execute over multiple nodes (e.g., cores). Some fraction, Equation alpha , of the program's code cannot be parallelized and must be executed sequentially. This portion of the program is the sequential bottleneck.

The portion of the program that can be executed in parallel is therefore Equation 1 minus alpha . Since no speedup is obtained from the sequential bottleneck portion of the program, regardless of the number of execution nodes, it always accounts for Equation alpha upper T of the time. Likewise, the execution time of the parallel portion of the program decreases linearly with more node, i.e., Equation StartFraction left-parenthesis 1 minus alpha right-parenthesis upper T Over n EndFraction speedup is obtained.

Amdahl's Law states that the speedup factor for spanning a program across Equation n nodes over the use of a single processing node can be expressed as:

Equation upper S left-parenthesis n right-parenthesis less-than-or-equal-to StartStartFraction upper T OverOver alpha upper T plus StartFraction left-parenthesis 1 minus alpha right-parenthesis upper T Over n EndFraction EndEndFraction equals StartStartFraction 1 OverOver alpha plus StartFraction left-parenthesis 1 minus alpha right-parenthesis Over n EndFraction EndEndFraction

It can be seen that the greatest speedup is only obtained if the sequential bottleneck portion of the program is eliminated (i.e., Equation alpha right-arrow 0 ). In such situations as the number of nodes becomes sufficiently large (i.e., Equation n right-arrow normal infinity ), the speedup approaches Equation StartFraction 1 Over alpha EndFraction . It can be seen that the upper bound on the speedup is actually independent of the number of nodes but instead is entirely limited by the sequential bottleneck part of the program which cannot be parallelized.

Example

Suppose you want to achieve a speedup of 80 with just 100 cores. That is, Equation StartStartFraction 1 OverOver alpha plus StartFraction left-parenthesis 1 minus alpha right-parenthesis Over 100 EndFraction EndEndFraction equals 80 . This requires Equation alpha equals 0.002525 or 99.7475% of the program's execution to be parallelizable.

Bibliography

  • Amdahl, Gene M. "Validity of the single processor approach to achieving large scale computing capabilities." Proceedings of the April 18-20, 1967, spring joint computer conference. ACM, 1967.

See also