Amdahls Law

Proposed in 1967, Amdahls' Law examines the theoretical maximum speedup obtained by using parallel processing.

GeneAmdahl, "Validity of the Single Processor Approach to Achieving Large-Scale Computing Capabilities", AFIPS Conference Proceedings, (30), pp. 483-485, 1967

If N is the number of processors, s is the time spent by a processor on serial part of a program, and p is the time spent by a processor on a parallel part of a program, then the maximum possible speedup is given by:

(s+p) / (s+p/N)

which simplifies (by setting s+p=1) to

1 / (s+p/N) or N / (sN+p)

This "Law" has been re-evaluated since and its underlying assumptions challenged. TheInterestedReader might choose to look at

Although we should point out that Gustavson's Law which modifies Amdahl's Law only applies in somewhat exotic circumstances such as massively parallel systems rather than just ordinary clustering.

The section below was added by Juan Jose Arrieta-Camacho (http://hysteria.cheme.cmu.edu) based on Steinar Hauan's (www.andrew.cmu.edu/~steinhau) lecture notes on High Performance Computing

Amdahl's Law: If ts is the run time and f its parallelizable fraction, with n CPUs, the total time tt becomes:

tt=f*ts+(1-f)*ts/n

assuming infinite amount of processors and perfect communication (i.e. no loss of speed due to comunication time), the speedup factor S(n)(ratio of serial to parallel times, ts/tp) will be increased AT MOST:

     ts               n           1\lim''S(n) =
 ----------------- = ----------- =  ---\s-->inf
 f*ts+(1-s)*tp/n     1+(n-1)*f      f''

"Amdahl's Law -- Simplified":

"Each component of a computer system contributes delay to the system. If you make a single component of the system infinitely fast... system throughput will still exhibit the combined delays of the other components"

-- GeneAmdahl - one of the creators of IBM System 360 Architecture

...which also has bearing on optimizing software.

CategoryOptimization