AESOP home

Publications

Uniformization and Hypergraph Partitioning for the Distributed Computation of Response Time Densities in Very Large Markov Models

Nicholas J. Dingle, Peter G. Harrison, William J. Knottenbelt

Journal Article
Journal of Parallel and Distributed Computing
Volume 64
Issue 8
pp.908–920
July, 2004
Elsevier
DOI 10.1016/j.jpdc.2004.03.017
Abstract

Fast response times and the satisfaction of response time quantile targets are important performance criteria for almost all transaction processing and computer-communication systems. We present a distributed uniformization-based technique for obtaining response time densities from very large unstructured Markov models. Our method utilizes hypergraph partitioning to minimize inter-processor communication while maintaining a good load balance. The resulting algorithm scales well on a distributed-memory parallel computer and, unusually for a problem of this nature, also produces near-linear speed-ups on a network of commodity PCs linked by 100 Mbps ethernet. We demonstrate our approach by calculating passage time densities in a 1.6 million state Markov chain derived from a Generalized Stochastic Petri net model and a 10.8 million state Markov chain derived from a closed tree-like queueing network. We compare the accuracy of our results with simulation and known analytical solutions and contrast the run-time performance of our technique with an approach based on numerical Laplace transform inversion.

PDF of full publication (639.7 kilobytes)
(need help viewing PDF files?)

Information from pubs.doc.ic.ac.uk/markov-uniformization-jpdc.