A Probabilistic Approach to Symbolic Performance Modeling of Parallel Systems

A Probabilistic Approach to Symbolic Performance Modeling of Parallel Systems

Gautama, H.

Sips, H.J. (promotor)
van Gemund, A.J.C. (promotor)

Electrical Engineering, Mathematics and Computer Science

2004-12-16

Performance modeling plays a significant role in predicting the effects of a particular design choice or in diagnosing the cause for some observed performance behavior. Especially for complex systems such as parallel computer, typically, an intended performance cannot be achieved without recourse to some form of predictive models. In performance prediction of parallel programs we distinguish static and dynamic prediction approaches of which the choice represents a fundamental trade-off between the amount of information and its accuracy. Static techniques offer the advantage of producing analytical information on the performance effects of symbolic program/machine parameters without requiring costly execution or multiple simulation runs for each different parameter setting or input data set. However, their limitations in modeling dynamic program behavior may have a profound negative impact on prediction accuracy. Besides dynamic behavior due to scheduling and resource contention, another important source of dynamic behavior is the dependency of a program on the input data set. For such data-dependent programs, the execution time of the program can vary greatly across the space of input data sets. In this thesis we present a new approach to symbolic performance modeling of parallel programs that provides information on the distribution of execution times when considering a large space of input data sets. Our approach is based on statistical moments representation of distribution. We present a low-cost algorithm that computes the moments of the program execution time based on the moments associated with sequential, conditional and parallel composition. The novelty of our analysis technique is the combination between the general validity of the analysis with moment representation and ultra low solution complexity. The accuracy of our approach is experimentally evaluated for synthetic workloads as well as many empirical workloads measured from real parallel programs. Considering its ultra-low solution complexity, our approach provides an attractive cost-performance trade-off in analytical performance modeling of data-dependent parallel programs.

performance prediction
stochastic graph
workload distribution

http://resolver.tudelft.nl/uuid:6f85ea91-2398-4d98-ad75-cfd8ffdaa768

90-855-9024-8

Institutional Repository

doctoral thesis

(c) 2004 H. Gautama