Computing Publications

Publications Home » Hypergraph-based Parallel Computa...

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

Conference or Workshop Paper
NSMC 2003, 4th International Workshop on Numerical Solution of Markov Chains
September, 2003

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 (510 kilobytes)
(need help viewing PDF files?)
GZipped Postscript of full publication (370 kilobytes)
(need help viewing GZipped Postscript files?)
BibTEX file for the publication
Conditions for downloading publications from this site. built & maintained by Ashok Argent-Katwala.