Reevaluating Amdahl's Law and Gustafson's Law
Yuan Chang Shi · 1996
ABSTRACT Researchers in the parallel processing community have been using Amdahl’s Law and Gustafson’s Law to obtainestimated speedups as measures of parallel program potential. In 1967, Amdahl’s Law was used as an argumentagainst massively parallel processing. Since 1988 Gustafson’s Law has been used to justify massively parallelprocessing (MPP). Interestingly, a careful analysis reveals that these two laws are in fact identical. The wellpublicized arguments were resulted from misunderstandings of the nature of both laws. This paper establishes the mathematical equivalence between Amdahl’s Law and Gustafson’s Law. We also focus onan often neglected prerequisite to applying the Amdahl’s Law: the and parallel programs must compute thesame total number of steps for the same input. There is a class of commonly used algorithms for which thisprerequisite is hard to satisfy. For these algorithms, the law can be abused. A simple rule is provided to identify thesealgorithms. We conclude that the use of the serial concept in parallel performance evaluation is misleading. It hascaused nearly three decades of confusion in the parallel processing community. This confusion disappears whenprocessing times are used in the formulations. Therefore, we suggest that time-based formulations would be the mostappropriate for parallel performance evaluation.This page is intentionally left blank to confirm with the JIDP’s typesetting requirement.1. Introduction In parallel program evaluation Amdahl’s Law has been widely cited. The analytical formulations in the literature,however, have caused much confusion to the understanding of the nature of the law [2]. The best known misuse wasperhaps the argument against massively parallel processing (MPP) [1]. The key to Amdahl’s Law is a processing percentage relative to the overall program execution time using a single processor. Therefore it is independent of the number of processors. It is then possible to derive an upper boundof speedup when the number of processors (P) approaches infinity. It seemed that small percentages, such as0.01-0.05, can restrict speedup to very small values. This observation had spread much pessimism in the parallelprocessing community. Parallel computational experiments indicate that many practical applications have indeedvery small percentages, much smaller than we had imagined. Gustafson revealed that it was indeed possible to achieve more than 1000 fold speedup using 1024 processors [4].This appeared to have broken the Amdahl’s Law and to have justified massively parallel processing.An alternative formulation was proposed. This is often referred to as the Gustafson’s Law [5] and has been widelyrefereed to as a scaled speedup measure. In Gustafson’s formulation, a new percentage is defined in referenceto the overall processing time using P processors. Therefore it is dependent on P. This P dependent percentageis easier to obtain than that in Amdahl’s formulation via computational experiments. But mathematically, Gustafson’sformulation cannot be directly used to observe P’s impact on speedup since it contains a P dependent variable.