computer science//Amdahl's law

Amdahl's law gives the overall speedup of a process when only part of it is made faster, and it is used to decide whether accelerating a step is worth it before paying for it. If a fraction \(f\) of the time is sped up by a factor \(s\) and the rest is untouched, the whole runs faster by

Amdahl's law gives the overall speedup of a process when only part of it is made faster, and it is used to decide whether accelerating a step is worth it before paying for it. If a fraction fff of the time is sped up by a factor sss and the rest is untouched, the whole runs faster by

S=1(1−f)+f/sS = \frac{1}{(1-f) + f/s}S=(1−f)+f/s1​

and as sss grows without bound the speedup approaches 1/(1−f)1/(1-f)1/(1−f). A job that is 90% parallelisable never runs more than ten times faster, however many processors it gets: with 10 it runs about 5.3 times faster, with 100 about 9.2.

It was stated for parallel computers and holds for any process made of a part that can be accelerated and a part that cannot: a build, a factory line, a clinical study where analysis gets faster and follow-up does not.

The part you did not speed up becomes the bottleneck.

Every gain on the accelerated fraction raises the share of time spent in the rest, so returns fall long before the fraction is exhausted.

The condition is the whole content. The formula assumes the unaccelerated part stays the same, so a change that reorganises the process (moving work out of the serial part) is a new process, and its fraction has to be measured again.

The fraction is measured, never guessed. Profiling a real run gives fff, and the cost of coordinating the parallel parts belongs to 1−f1-f1−f, which is why measured speedups fall short of the formula.