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
* http://www.scl.ameslab.gov/Publications/AmdahlsLaw/Amdahls.html
* http://www.cis.temple.edu/~shi/docs/amdahl/amdahl.html
----
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