AESOP home


Parallel Performance Analysis of Large Markov Models

William J. Knottenbelt

PhD Thesis
Department of Computing, Imperial College of Science, Technology and Medicine. University of London.
December, 1999

Stochastic performance models provide a formal way of capturing and analysing the complex dynamic behaviour of concurrent systems. Such models can be specified by several high-level formalisms, including Stochastic Petri nets, Queueing networks and Stochastic Process Algebras. Traditionally, performance statistics for these models are derived by generating and then solving a Markov chain corresponding to the model's behaviour at the state transition level. However, workstation memory and compute power are often overwhelmed by the sheer number of states in the Markov chain and the size of their internal computer representations.

This thesis presents two parallel and distributed techniques which significantly increase the size of the models that can be analysed using Markov modelling. The techniques attack the space and time requirements of both major phases of the analysis, i.e. construction of the Markov chain from a high-level model (state space generation) and solution of the Markov chain to determine its equilibrium distribution (steady-state solution). Space requirements are reduced through the use of probabilistic and disk-based storage schemes. Time requirements are reduced by exploiting the compute power provided by a distributed memory parallel computer or a network of workstations. Neither method places any restrictions on the type of model that can be analysed.

Both techniques have been implemented in C++ on a 16-node Fujitsu AP3000 distributed memory parallel computer. The methods are applied to the analysis of very large models of the order of 100 million states and 1 billion transitions. The state generator delivers substantial speedups (85% efficiency on 16 nodes) and exhibits good scalability which is confirmed by a theoretical performance model. The steady-state analyser delivers competitive speedups for a sparse linear equation solver (45% efficiency on 16 nodes). The other tools required to build a complete parallel analysis pipeline have also been implemented, thus providing an automatic way of obtaining performance measures for unrestricted high-level system specifications with very large underlying Markov chains.

PDF of full publication (3.8 megabytes)
(need help viewing PDF files?)
GZipped Postscript of full publication (1.1 megabytes)
(need help viewing GZipped Postscript files?)

Information from