#redirect Amdahl's law
'''Amdahl's law''', named after computer architect Gene Amdahl, is used to find out the maximum expected improvement to an overall system when only a part of the system is improved. 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. 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 :. 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. 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 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''. 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. ==References== * Gene Amdahl, "Validity of the Single Processor Approach to Achieving Large-Scale Computing Capabilities", AFIPS Conference Proceedings, (30), pp. 483-485, 1967. ==See also== *Observations named after people ==External links== * [http://www.scl.ameslab.gov/Publications/Gus/AmdahlsLaw/Amdahls.html Reevaluating Amdahl's Law] * [http://joda.cis.temple.edu/~shi/docs/amdahl/amdahl.html Reevaluating Amdahl's Law and Gustafson's Law] Computer architecture Eponymous laws
anyone want to explain this a bit more in the article? What is the practical meaning of this? And is this a "real" law, as in law of physics, or a "approximate" law, like Moore's Law, or a "folklore law" like Murphy's? -- User:Tarquin :It's a practical engineering law for a vast class of imaginable computers. A nit-pick might be that in certain special cases it would be 1 / max(F, (1-F)/P), assuming that even the irreducible sequential bit can be done in parallel with the parallel bit, but the result for p --> infinity is the same: 1/F. :It's always possible that some new kind of computer will "break" Amdahl's law, but this would be the same as F --> 0, in which case Amdahl's law could still be held to be valid. User:The Anome I just put up the general case of Amdhal's law with an explaination of what it means. Another example could still be put in to show the law of diminishing returns, which is really the "big picture" you're looking for, but I want to see the current version stabilize first. User:Mshonle 02:43, 24 Jan 2004 (UTC) :Wow, just saw the recent deletion of the contents of the article. I can't imagine why someone would want to do that. Glad someone put it back up. User:Mshonle 11:12, 23 Mar 2004 (UTC) -- I was a little confused about this law, usually Wikipedia explains things so nicely but this article was a little hard to understand :). This link does some explaining as well, but is very long winded: http://www.phy.duke.edu/brahma/beowulf_book/node21.html --User:ShaunMacPherson 19:24, 8 Apr 2004 (UTC) The link above does not work anymore, here is another one including PDF and PS http://www.phy.duke.edu/~rgb/Beowulf/beowulf_book/ Do I misunderstand, or does the meaning of ''F'' flip-flop in the middle of this article. Yuck. User:Gareth Owen 15:35, 5 May 2004 (UTC) :In the second part of the article, 1-F and F should be swapped. Then, the Ps should be changed back to Fs. User:Mshonle 17:55, 5 May 2004 (UTC) == Trivial law == I think the problem with explaining this "law" is that it is too trivial. If you express it in durations rather than speedups and proportions then it boils down to something so obvious that nobody would even call it a law. Let me try: Consider a process with multiple phases, such as getting out in the morning. Let's call the total duration of the process T and duration of one phase (such as eating breakfast), t. Duration of all other phases is then T-t. If we speed up the chosen phase by a factor of S, the time it takes to complete it will be t/S, and the total duration will become: (T-t) + t/S How hard is that? You get the usual form of the law by taking a ratio of T by the above expression and using P for t/T. -- User:Bdolicki 14:35, 9 May 2005 (UTC) :Most call it a law, even though it may seem like a misnomer to you. However, there are insights to be gained even from trivial ideas. For example, imagine being stuck in a budget meeting and spending three hours talking about a budget item that wouldn't change the overall picture much. The idea that "little can be gained from this" wasn't obvious to everyone. (Indeed, some may say the best laws seem obvious in retrospect.) User:Mshonle 22:24, 9 May 2005 (UTC) :: I don't mind the name. If many people refer to it as Amdahl's law then an article under that name. My problem is this: The fact that it is trivial is not apparent from how it is presented in the article. On the first reading I got impression that it is something that I didn't know before. So let's change the presentation so that it becomes easier to follow, starting with the obvious and getting to the final form by a simple mathematical substitution. User:Bdolicki 20:40, 10 May 2005 (UTC) ::: As I understand it, you just want to see the reciprocal first? The formula presented is just the reciprocal of what you want, which isn't much complication. Perhaps I'm misunderstanding? Further, Amdahl's law is concerned with "speed up," a technical unit, and changing the unit of the law doesn't seem worth it. Also, reducing to time taken for a particular run simplifies it, but misses the "big picture" point that is concerned with fractions taken (and is universal for all runs). User:Mshonle 02:30, 11 May 2005 (UTC)
See other meanings of words starting from letter:
Words begining with Amdahl\'s_law:
Amdahl's_Law
Amdahl's_law
Amdahl's_law
Amdahl's Law
#redirect Amdahl's law
Amdahl's law
'''Amdahl's law''', named after computer architect Gene Amdahl, is used to find out the maximum expected improvement to an overall system when only a part of the system is improved. 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. 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 :. 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. 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 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''. 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. ==References== * Gene Amdahl, "Validity of the Single Processor Approach to Achieving Large-Scale Computing Capabilities", AFIPS Conference Proceedings, (30), pp. 483-485, 1967. ==See also== *Observations named after people ==External links== * [http://www.scl.ameslab.gov/Publications/Gus/AmdahlsLaw/Amdahls.html Reevaluating Amdahl's Law] * [http://joda.cis.temple.edu/~shi/docs/amdahl/amdahl.html Reevaluating Amdahl's Law and Gustafson's Law] Computer architecture Eponymous laws
Amdahl's law
anyone want to explain this a bit more in the article? What is the practical meaning of this? And is this a "real" law, as in law of physics, or a "approximate" law, like Moore's Law, or a "folklore law" like Murphy's? -- User:Tarquin :It's a practical engineering law for a vast class of imaginable computers. A nit-pick might be that in certain special cases it would be 1 / max(F, (1-F)/P), assuming that even the irreducible sequential bit can be done in parallel with the parallel bit, but the result for p --> infinity is the same: 1/F. :It's always possible that some new kind of computer will "break" Amdahl's law, but this would be the same as F --> 0, in which case Amdahl's law could still be held to be valid. User:The Anome I just put up the general case of Amdhal's law with an explaination of what it means. Another example could still be put in to show the law of diminishing returns, which is really the "big picture" you're looking for, but I want to see the current version stabilize first. User:Mshonle 02:43, 24 Jan 2004 (UTC) :Wow, just saw the recent deletion of the contents of the article. I can't imagine why someone would want to do that. Glad someone put it back up. User:Mshonle 11:12, 23 Mar 2004 (UTC) -- I was a little confused about this law, usually Wikipedia explains things so nicely but this article was a little hard to understand :). This link does some explaining as well, but is very long winded: http://www.phy.duke.edu/brahma/beowulf_book/node21.html --User:ShaunMacPherson 19:24, 8 Apr 2004 (UTC) The link above does not work anymore, here is another one including PDF and PS http://www.phy.duke.edu/~rgb/Beowulf/beowulf_book/ Do I misunderstand, or does the meaning of ''F'' flip-flop in the middle of this article. Yuck. User:Gareth Owen 15:35, 5 May 2004 (UTC) :In the second part of the article, 1-F and F should be swapped. Then, the Ps should be changed back to Fs. User:Mshonle 17:55, 5 May 2004 (UTC) == Trivial law == I think the problem with explaining this "law" is that it is too trivial. If you express it in durations rather than speedups and proportions then it boils down to something so obvious that nobody would even call it a law. Let me try: Consider a process with multiple phases, such as getting out in the morning. Let's call the total duration of the process T and duration of one phase (such as eating breakfast), t. Duration of all other phases is then T-t. If we speed up the chosen phase by a factor of S, the time it takes to complete it will be t/S, and the total duration will become: (T-t) + t/S How hard is that? You get the usual form of the law by taking a ratio of T by the above expression and using P for t/T. -- User:Bdolicki 14:35, 9 May 2005 (UTC) :Most call it a law, even though it may seem like a misnomer to you. However, there are insights to be gained even from trivial ideas. For example, imagine being stuck in a budget meeting and spending three hours talking about a budget item that wouldn't change the overall picture much. The idea that "little can be gained from this" wasn't obvious to everyone. (Indeed, some may say the best laws seem obvious in retrospect.) User:Mshonle 22:24, 9 May 2005 (UTC) :: I don't mind the name. If many people refer to it as Amdahl's law then an article under that name. My problem is this: The fact that it is trivial is not apparent from how it is presented in the article. On the first reading I got impression that it is something that I didn't know before. So let's change the presentation so that it becomes easier to follow, starting with the obvious and getting to the final form by a simple mathematical substitution. User:Bdolicki 20:40, 10 May 2005 (UTC) ::: As I understand it, you just want to see the reciprocal first? The formula presented is just the reciprocal of what you want, which isn't much complication. Perhaps I'm misunderstanding? Further, Amdahl's law is concerned with "speed up," a technical unit, and changing the unit of the law doesn't seem worth it. Also, reducing to time taken for a particular run simplifies it, but misses the "big picture" point that is concerned with fractions taken (and is universal for all runs). User:Mshonle 02:30, 11 May 2005 (UTC)
See other meanings of words starting from letter:
A
AB | AC | AD | AE | AF | AG | AH | AI | AJ | AK | AL | AM | AN | AO | AP | AR | AS | AT | AU | AW | AX | AY | AZ |Words begining with Amdahl\'s_law:
Amdahl's_Law
Amdahl's_law
Amdahl's_law
Sponsored links: praca.
These materials are based on Wikipedia and licensed under the GNU FDL
YouTube.com videos better site than Turbo Tax 2007
