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.
Information from pubs.doc.ic.ac.uk/markov-uniformization-jpdc.