Amdahl's law is named after computer architect Gene Amdahl, and is used to find the maximum expected improvement to an overall system when only part of the system is improved. It is often used in parallel computing to predict the theoretical maximum speedup using multiple processors.
The speedup of a program using multiple processors in parallel computing is limited by the time needed for the sequential fraction of the program.
In this example is the sequential calculation time t1 standardize to 1.
If s is the unchangeable part of a sequential calculation and (1-s) the parallel code:
t1 = 1 = s + (1-s)
For the parallel execution on n CPU's would be sequential code the same, but the parallel code would shared to:
(1-s)
tn = s + -------
n
So that the maximum acceleration (without the parallel additional expenditure) is:
1
Max. = ------------
1 - s
s + --------
n
And for n -> inf.
1
Max. = -------
s
For the next step is it important to know, that
1/(a+b) <= 1/a and 1/(a+b) <= 1/b for a,b >= 0
The maximum reachable acceleration is independent of the usable CPU's.
E.g. are 10% of the program sequential (s = 0.1) then is the maximum acceleration 1/s = 10.
