Amdahl's law

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

Related Topics:
Computer - Gene Amdahl

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

an overall system when only a part of the system is improved.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

__TOC__

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Amdahl's law is a demonstration of the law of diminishing returns: while one could speed up part of a computer a hundred-fold or more, if the improvement only affects 12% of the overall task, the best the speedup could possibly be is rac{1}{1 - 0.12} = 1.136 times faster.

Related Topics:
Law of diminishing returns - Speedup

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

More technically, the law is concerned with the speedup achievable from an improvement to a computation that affects a proportion P of that computation where the improvement has a speedup of S. (For example, if an improvement can speedup 30% of the computation, P will be 0.3; if the improvement makes the portion affected twice as fast, S will be 2.) Amdahl's law states that the overall speedup of applying the improvement will be

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

:rac{1}{(1 - P) + rac{P}{S}}.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

To see how this formula was derived, assume that the running time of the old computation was 1, for some unit of time. The running time of the new computation will be the length of time the unimproved fraction takes (which is 1 − P) plus the length of time the improved fraction takes. The length of time for the improved part of the computation is the length of the improved part's former running time divided by the speedup, making the length of time of the improved part P/S. The final speedup is computed by dividing the old running time by the new running time, which is what the above formula does.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Here's another example. We are given a task is split up into four parts: P1 = .11 or 11%, P2 = .18 or 18%, P3 = .23 or 23%, P4 = .48 or 48%, which add up to 100%. Then we say P1 is not sped up, so S1 = 1 or 100%, P2 is sped up 5x, so S2 = 5 or 500%, P3 is sped up 20x, so S3 = 20 or 2000%, and P4 is sped up 1.6x, so S4 = 1.6 or 160%. By using the formula rac{P1}{S1} + rac{P2}{S2} + rac{P3}{S3} + rac{P4}{S4}, we find the running time is {rac{.11}{1} + rac{.18}{5} + rac{.23}{20} + rac{.48}{1.6}} = .4575 or a little less than 1/2 the original running time which we know is 1. Therfore the overall speed boost is rac{1}{.4575} = 2.186 or a little more than double the original speed using the formula rac{1}{rac{P1}{S1} + rac{P2}{S2} + rac{P3}{S3} + rac{P4}{S4}}. Notice how the 20x and 5x speedup don't have much effect on the overall speed boost and running time when over half of the task is only sped up 1x (i.e. not sped up) or 1.6x.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~