Revision as of 12:27, 6 June 2017

Amdahl's Law is formulation 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 detailed the law in his 1967 paper "Validity of the single processor approach to achieving large scale computing capabilities".

Theory

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 minutes. Now let's suppose we want to divide or partition this program to execute over multiple nodes (e.g., cores). Some fraction, , 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 . Since no speedup is obtained from the sequential bottleneck portion of the program, regardless of the number of execution nodes, it always accounts for of the time. Likewise, the execution time of the parallel portion of the program decreases linearly with more node, i.e., speedup is obtained.