Amdahl's law, named after computer architect Gene Amdahl, 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 generalized Amdahl's law is:
- <math>\frac{1}{\sum_{k=0}^{n}{\big(\frac{P_k}{S_k}\big)}}</math>
where
- <math>P_k \ </math> is a percentage of the instructions that can be improved (or slowed),
- <math>S_k \ </math> is the speed-up multiplier (where 1 is no speed-up and no slowing),
- <math>k \ </math> represents a label for each different percentage and speed-up, and
- <math>n \ </math> is the number of different speed-up/slow-downs resulting from the system change.
Contents |
Description
Amdahl's law is a model for the relationship between the expected speedup of parallelized implementations of an algorithm relative to the serial algorithm, under the assumption that the problem size remains the same when parallelized. For example, if for a given problem size a parallelized implementation of an algorithm can run 12% of the algorithm's operations arbitrarily fast (while the remaining 88% of the operations are not parallelizable), Amdahl's law states that the maximum speedup of the parallelized version is <math>\frac{1}{1 - 0.12} = 1.136</math> times faster than the non-parallelized implementation. 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 speed up 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
- <math>\frac{1}{(1 - P) + \frac{P}{S}}</math>.
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 which 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 <math>\frac{P1}{S1} + \frac{P2}{S2} + \frac{P3}{S3} + \frac{P4}{S4}</math>, we find the running time is <math>{\frac{.11}{1} + \frac{.18}{5} + \frac{.23}{20} + \frac{.48}{1.6}} = .4575</math> or a little less than ½ the original running time which we know is 1. Therefore the overall speed boost is <math>\frac{1}{.4575} = 2.186</math> or a little more than double the original speed using the formula <math>\frac{1}{\frac{P1}{S1} + \frac{P2}{S2} + \frac{P3}{S3} + \frac{P4}{S4}}</math>. 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.
Relation to law of diminishing returns
Amdahl's law is often conflated with the law of diminishing returns, whereas only a special case of applying Amdahl's law demonstrates 'law of diminishing returns'. If one picks optimally (in terms of the achieved speed-up) what to improve you will see monotonically decreasing improvements as you improve. If, however, one picks non-optimally, after improving a sub-optimal component and moving on to improve a more optimal improvement one can see an increase in return. Consider, for instance, the illustration. If one picks to work on B then A you find an increase in return. If, instead, one works on improving A then B you will find a diminishing return. Thus, strictly speaking, only one (optimal case) can appropriately be said to demonstrate 'law of diminishing returns'. Note that it is often rational to improve a system in an order that is "non-optimal" in this sense, given that some improvements are more difficult or consuming of development time than others. Amdahl's law does represent the law of diminishing returns if you are considering what sort of return you get by adding more processors to a machine, if you are running a fixed-size computation that will use all available processors to their capacity. Each new processor you add to the system will add less usable power than the previous one. Each time you double the number of processors the speedup ratio will diminish, as the total throughput heads toward the limit of
- <math>\frac{1}{(1 - P)}</math>.
This analysis neglects other potential bottlenecks such as memory bandwidth and I/O bandwidth, if they do not scale with the number of processors; however taking into account such bottlenecks would tend to further demonstrate the diminishing returns of only adding processors.
Speedup in a sequential program
The maximum speedup in an improved sequential program, where some part was sped up by <math>p</math> times is
- Max. Speedup <math>\le \frac{p}{1 + f * (p - 1)}</math>
where <math>f</math> (<math>0.0 < f < 1.0</math>) is the fraction of time (before the improvement) spent in the part that was not improved. For example,
- If part B (blue) is made five times faster, p = 5.0, <math>t_n</math> (red) = 3 seconds, <math>t_i</math> (blue) = 1 second and
- <math>f = t_n / (t_n + t_i) = 0.75</math>
- Max. Speedup <math>\le \frac{5}{1 + 0.75 * (5 - 1)} = 1.25</math>
- If part A (red) is made to run twice as fast, p = 2.0, <math>t_n</math> (blue) = 1 second, <math>t_i</math> (red) = 3 seconds and
- <math>f = t_n / (t_n + t_i) = 0.25</math>
- Max. Speedup <math>\le \frac{2}{1 + 0.25 * (2 - 1)} = 1.60</math> (better!!!)
Therefore, making A twice faster is better than making B five times faster.
- Improving part A by a factor of two will result in a +60% increase in overall program speed.
- However, improving part B by a factor of 5 (which presumably requires more effort) will only achieve an overall speedup of +25%.
Parallelization
In the special case of parallelization, Amdahl's law states that if F is the fraction of a calculation that is sequential (i.e. cannot benefit from parallelization), and (1 − F) is the fraction that can be parallelized, then the maximum speedup that can be achieved by using N processors is
- <math>\frac{1}{F + (1-F)/N}</math>.
In the limit, as N tends to infinity, the maximum speedup tends to 1/F. In practice, price/performance ratio falls rapidly as N is increased once (1 − F)/N is small compared to F. As an example, if F is only 10%, the problem can be sped up by only a maximum of a factor of 10, no matter how large the value of N used. For this reason, parallel computing is only useful for either small numbers of processors, or problems with very low values of F: so-called embarrassingly parallel problems. A great part of the craft of parallel programming consists of attempting to reduce F to the smallest possible value.
Limitations
According to Amdahl's law, the theoretical maximum speedup of using N processors would be N, namely linear speedup. However, it is not uncommon to observe more than N speedup on a machine with N processors in practice, namely super linear speedup. One possible reason is the effect of cache aggregation. In parallel computers, not only does the number of processors change, but so does the size of accumulated caches from different processors. With the larger accumulated cache size, more or even the entire data set can fit into caches, dramatically reducing memory access time and producing an additional speedup beyond that arising from pure computation.
Amdahl's Rule Of Thumb
Amdahl's Rule Of Thumb is that 1 byte of memory and 1 bit per second of I/O are required for each instruction per second supported by a computer. This also goes by the title Amdahl's Other Law.
See also
- Speedup
- Amdahl Corporation
- Ninety-ninety rule
- Gustafson's Law
- Karp-Flatt Metric
- Brooks's Law
- Moore's Law
References
- Gene Amdahl, "Validity of the Single Processor Approach to Achieving Large-Scale Computing Capabilities", AFIPS Conference Proceedings, (30), pp. 483-485, 1967. Note: Gene Amdahl has approved the use of his complete text in the Usenet comp.sys.super news group FAQ which goes out on the 20th of each month.
External links
- Reevaluating Amdahl's Law
- Reevaluating Amdahl's Law and Gustafson's Law
- A simple interactive Amdahl's Law calculator
- "Amdahl's Law" by Joel F. Klein, The Wolfram Demonstrations Project, 2007.
|
|
|
|---|---|
| General | |
| Parallelism | |
| Theory |
Speedup · Amdahl's law · Flynn's taxonomy (SISD • SIMD • MISD • MIMD) · Cost efficiency · Gustafson's law · Karp-Flatt metric |
| Elements | |
| Coordination | |
| Programming | |
| Hardware |
Computer cluster · Beowulf · Symmetric multiprocessing · Non-Uniform Memory Access · Cache only memory architecture · Asymmetric multiprocessing · Simultaneous multithreading · Shared memory · Distributed memory · Massively parallel processing · Superscalar processing · Vector processing · Supercomputer · Stream processing · GPGPU |
| Software | |
| APIs | |
| Problems | |
