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

Warning: round() expects parameter 2 to be long, array given in /export/vol/www/aesop/inc/format.inc on line 506
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 ( kilobytes)
(need help viewing PDF files?)

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