AESOP home


Hypergraph-based Parallel Computation of Passage Time Densities in Large Semi-Markov Models

Jeremy T. Bradley, Nicholas J. Dingle, William J. Knottenbelt, Helen J. Wilson

Journal Article
Linear Algebra and Its Applications
Volume 386
July, 2004
DOI 10.1016/j.laa.2003.12.018

Passage time densities and quantiles are important performance and quality of service metrics, but their numerical derivation is, in general, computationally expensive. We present an iterative algorithm for the calculation of passage time densities in semi-Markov models, along with a theoretical analysis and empirical measurement of its convergence behaviour. In order to implement the algorithm efficiently in parallel, we use hypergraph partitioning to minimise communication between processors and to balance workloads. This enables the analysis of models with very large state spaces which could not be held within the memory of a single machine. We produce passage time densities and quantiles for very large semi-Markov models with over 15 million states and validate the results against simulation.

PDF of full publication (519.8 kilobytes)
(need help viewing PDF files?)
GZipped Postscript of full publication (380.7 kilobytes)
(need help viewing GZipped Postscript files?)

Information from