Scalable Problems and Memory-Bounded Speedup
Authors: X.-H. Sun, L. Ni
Date: September, 1993
Venue: Journal of Parallel and Distributed Computing, Vol. 19, pp.27-37
Type: Journal
Abstract
In this paper three models of parallel speedup are studied. They are fixed-size speedup, fixed-time speedup, and memory-bounded speedup. The latter two consider the relationship between speedup and problem scalability. Two sets of speedup formulations are derived for these three models. One set considers uneven workload allocation and communication overhead and gives more accurate estimation. Another set considers a simplified case and provides a clear picture on the impact of the sequential portion of an applica- tion on the possible performance gain from parallel processing. The simplified fixed-size speedup is Amdahl's law. The simplified fixed-time speedup is Gustafson's scaled speedup. The simplified memory-bounded speedup contains both Amdahl's law and Gus- tafson's scaled speedup as special cases. This study leads to a better understanding of parallel processing.