The Effect of Time Constraints on Scaled Speedup
Patrick H Worley · SIAM Journal on Scientific and Statistical Computing · 1990
Gustafson, Montry, and Benner introduced the concept of scaled speedup to characterize the capabilities of distributed-memory multiprocessors. They argued that, for a fixed-size problem, the behavior of the speedup of an algorithm as a function of the number of processors, the speedup curve, can be too pessimistic a measure of a multiprocessor architecture. Instead, they measured the speedup of algorithms when the size of the corresponding problem grew with the number of processors. They referred to the resulting function as the scaled speedup curve. The scaled speedup curve is a function of how the size of the problem is allowed to grow. In this paper, it is demonstrated that allowing the size of a problem to grow to fill the available memory can produce dramatically different results from allowing the size of a problem to grow subject to satisfying an upper bound on the execution time. In particular, if a constraint on the execution time is enforced, then the scaled speedup curve is often very similar to the speedup curve for a fixed-size problem. It is shown that no more than 50 processors can be used efficiently for some common problems in scientific computation when using the current generation of distributed-memory multiprocessors. For other problems, it is shown that the scaled speedup curve indicates that massively parallel computers will be useful even if the execution time is constrained. In all of the cases examined; a meaningful interpretation of the scaled speedup curve depends on a constraint on the execution time.