Reevaluating Amdahl's law

Reviewer: Michael Wolfe

This short technical note could just as well have been entitled “Validity of the multiple-processor approach to achieving large-scale computing capabilities.” Amdahl's law states that given any problem of fixed size, a certain percentage s of the time spent solving that problem cannot be run in parallel, so the potential speedup for parallel processing is bounded by (1/ s). Gustafson states that for many real problems, the constant is not the size of the problem, but rather the time that the experimenter wants to wait for the answer; given a faster or bigger machine, the user will increase the size of the problem, or the accuracy of the solution, rather than solve the same problem faster. I have seen this phenomenon myself, so I tend to believe it. This short note, and its supporting work (which won the Gordon Bell and Alan Karp awards for parallel processing speedup [1], and made the New York Times) will certainly generate a great deal of controversy, since it makes perhaps the most serious challenge yet to Amdahl's law.