Reevaluating Amdahl's law
John Leroy Gustafson · 1995
At Sandia National Laboratories, we are currently en-gaged in research involving massively parallel process-ing. There is considerable skepticism regarding the via-bility of massive parallelism; the skepticism centers around Amdahl’s law, an argument put forth by Gene Amda.hl in 1967 [l] that even when the fraction of serial work in a given problem is small, say, s, the maximum speedup obtainable from even an infinite number of parallel processors is only l/s. We now have timing results for a 1024-processor system that demon-strate that the assumptions underlying Amdahl’s 1967 argument are inappropriate for the current approach to massive ensemble parallelism. If N is the number of processors, s is the amount of time spent (by a serial processor) on serial parts of a program, and p is the amount of time spent (by a serial processor) on parts of the program that can be done in parallel, then Amdahl’s law says that speedup is given by Speedup = (s + p)/(s + p/N) = l/b + p/N), where we have set total time s + p = 1 for algebraic simphcity. For N = 1024 this is an unforgivingly steep function of s near s = 0 (see Figure 1). The steepness of the graph near s = 0 (approximately-N’) implies that very few problems will experience even a loo-fold speedup. Yet, for three very practical applications (s = 0.4-0.8 percent) used at Sandia, we have achieved speedup factors on a 1024-processor hy-percube that we believe are unprecedented [2]: 2022 for beam stress analysis using conjugate gradients, 1020 for baffled surface wave simulation using explicit finite dif-0 1988 ACM OOOI-0782/88/0500-0532 $1.50 ferences, and 1016 for unstable fluid flow using flux-corrected transport. How can this be, when Amdahl’s argument would predict otherwise? The expression and graph both contain the implicit assumption that p is independent of N, which is vir-tually never the case. One does not take a fixed-sized problem and run it on various numbers of p:rocessors