 The speedup of a program using multiple processors in parallel computing is limited by the sequential fraction of the program. For example, if 0.5 portion of the program is sequential, the theoretical maximum speedup using parallel computing would be 2 (1/(0.5+(1-0.5)/N)) when N is very very big 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. Image File history File linksMetadata Amdahl-law. ...
Image File history File linksMetadata Amdahl-law. ...
In computer engineering, computer architecture is the conceptual design and fundamental operational structure of a computer system. ...
Gene Myron Amdahl (born November 16, 1922) is an American computer architect and hi-tech entrepreneur of Norwegian descent, chiefly known for his work on mainframe computers at International Business Machines (IBM) and later his own companies. ...
Parallel computing is the simultaneous execution of the same task (split up and specially adapted) on multiple processors in order to obtain results faster. ...
In parallel computing, speedup refers to how much a parallel algorithm is faster than a corresponding sequential algorithm. ...
Description
Amdahl's law can be interpreted more technically, but in simplest terms it means that it is the algorithm that decides the speedup not the number of processors. You eventually reach a place where you can not parallelise the algorithm any more. Flowcharts are often used to graphically represent algorithms. ...
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  times faster. In economics, diminishing returns is the short form of diminishing marginal returns. ...
 Assume that a task has two independent parts, A and B. B takes roughly 25% of the time of the whole computation. By working very hard, one may be able to make this part 5 times faster, but this only reduces the time for the whole computation by a little. In contrast, one may need to perform less work to make part A be twice as fast. This will make the computation much faster than by optimizing part B, even though B got a bigger speed-up, (5x versus 2x). 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 Image File history File links Optimizing-different-parts. ...
 . 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  , we find the running time is  or a little less than ½ the original running time which we know is 1. Therefore the overall speed boost is  or a little more than double the original speed using the formula . 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.
Parallelisation In the special case of parallelisation, Amdahl's law states that if F is the fraction of a calculation that is sequential (i.e. cannot benefit from parallelisation), and (1 − F) is the fraction that can be parallelised, then the maximum speedup that can be achieved by using N processors is  . 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. The infinity symbol ∞ in several typefaces The word infinity comes from the Latin infinitas or unboundedness. ...
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. CPU redirects here. ...
In the jargon of parallel computing, an embarrassingly parallel workload (or embarrassingly parallel problem) is one for which no particular effort is needed to segment the problem into a very large number of parallel tasks, and there is no essential dependency (or communication) between those parallel tasks. ...
Parallel programming is a computer programming technique that provides for the execution of operations in parallel, either within a single computer, or across a number of systems. ...
Amdahl's Rule Of Thumb Amdahl's Rule Of Thumb is that 1 byte of memory and 1 byte 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. In psychology, memory is the ability of an organism to store, retain, and subsequently recall information. ...
In computing, Input/output, or I/O, is the collection of interfaces that different functional units (sub-systems) of an information processing system use to communicate with each other, or the signals (information) sent through those interfaces. ...
In computer science, an instruction typically refers to a single operation of a processor within a computer architecture. ...
See also Amdahl Corporation was founded by Dr. Gene Amdahl, a former IBM employee, in 1970, and specializes in IBM mainframe-compatible computer products. ...
In computer programming and software engineering, the ninety-ninety rule states: The first 90% of the code accounts for the first 10% of the development time. ...
Gustafsons Law (also known as Gustafson-Barsis law) is a law in computer engineering which states that any sufficiently large problem can be efficiently parallelized. ...
Brooks law was stated by Fred Brooks as It appeared in his 1975 book The Mythical Man-Month. ...
References - Gene Amdahl, "Validity of the Single Processor Approach to Achieving Large-Scale Computing Capabilities", AFIPS Conference Proceedings, (30), pp. 483-485, 1967.
External links - Reevaluating Amdahl's Law
- Reevaluating Amdahl's Law and Gustafson's Law
|
Feeds |
Contact