Speedup prediction and diagnosis for shared memory multiprocessor systems
Thin-Fong Tsuei · 1991
Maximizing parallel program performance requires gaining more insight into parallel program and system behavior. In this thesis, we propose a modeling framework for parallel program speedup prediction and diagnosis for Multiple-Instruction-Multiple-Data shared memory multiprocessor systems. We identify a small number of parameters that characterize multiprocessor systems, and the resource demands of parallel programs. We develop a hierarchical comprehensive model to predict the overall speedup, and to diagnose the relative impact of three important causes of speedup degradation: (1) parallelism in a program, (2) lock contention, and (3) hardware resource contention. The uniqueness of the comprehensive model is that we decouple the speedup analysis according to the demands of the parallel program for three types of resources. We solve separate submodels for speedup degradation due to each of the three causes in a non-iterative hierarchical manner. The comprehensive model is designed such that suitable techniques can be selected independently for each submodel. The techniques used at all three levels are fairly general, but the submodel to analyze hardware resource contention must be developed for each specific multiprocessor system. The comprehensive model can be applied efficiently to an important class of parallel programs consisting of homogeneous concurrent processes, such as computations developed according to the SPMD (single program multiple data) parallel programming paradigm. We use the approach to predict and analyze parallel programs executing on the Sequent Symmetry-81 multiprocessor system. A memory and bus interference (MBI) model is developed for the Sequent S-81 system to complete the comprehensive analysis of parallel program speedup on the S-81 system. Results from the experiments provide important evidence that the model and its parameters are sufficient for predicting speedups with a high degree of accuracy. We illustrate uses of the MBI and comprehensive model for analyzing parallel system or program design modifications.