A probabilistic approach to parallel system performance modelling

For the development of efficient parallel applications, fast but reliable performance predictions are essential. Many existing modelling formalisms are either not directly suited to model parallel applications, or too expensive. This paper describes several extensions and improvements to a previously introduced methodology, based on an extension of queueing networks. The set of machine model building blocks is extended, a new algorithm for the prediction of multiple-class parallel section completion times is introduced, and it is shown how programs containing conditional statements at the program level and memory hierarchies at the machine level are modelled. The concepts introduced in this paper are illustrated by a number of examples throughout the paper, and a case study comparing the predictions to measurements carried out on an actual parallel machine