Amdahl's law

Amdahl's law, named after computer architect Gene Amdahl, is used to find out the maximum expected improvement to

Parallelization

In the special case of parallelization, Amdahl's law states that if F is the fraction of a calculation that is sequential (i.e. cannot benefit from parallelisation), and (1 − F) is the fraction that can be parallelised, then the maximum speedup that can be achieved by using N processors is

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

:rac{1}{F + (1-F)/N}.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

In the limit, as N tends to infinity, the maximum speedup tends to 1/F. In practice, price/performance ratio falls rapidly as N is increased once (1 − F)/N is small compared to F.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

As an example, if F is only 10%, the problem can be sped up by only a maximum of a factor of 10, no matter how large the value of N used. For this reason, parallel computing is only useful for either small numbers of processors, or problems with very low values of F: so-called embarrassingly parallel problems. A great part of the craft of parallel programming consists of attempting to reduce F to the smallest possible value.

Related Topics:
Parallel computing - Processor - Embarrassingly parallel - Parallel programming

~ ~ ~ ~ ~ ~ ~ ~ ~ ~