AESOP home


Parallel Computation of Response Time Densities and Quantiles in Large Markov and Semi-Markov Models

Nicholas J. Dingle

PhD Thesis
Department of Computing, Imperial College London. University of London.
September, 2004

Response time quantiles reflect user-perceived quality of service more accurately than mean or average response time measures. Consequently, on-line transaction processing benchmarks, telecommunications Service Level Agreements and emergency services legislation all feature stringent 90th percentile response time targets.

This thesis presents techniques and tools for extracting response time densities, quantiles and moments from large-scale models of real-life systems. This work expands the applicability, capacity and specification power of prior work, which was hitherto focused on the analysis of Markov models which only support exponential delays.

Response time densities or cumulative distribution functions of interest are computed by calculating and subsequently numerically inverting their Laplace transforms. We develop techniques for the extraction of response time measures from Generalised Stochastic Petri Nets (GSPNs) and Semi-Markov Stochastic Petri Nets (SM-SPNs). The latter is our proposed modelling formalism for the high-level specification of semi-Markov models which support generally-distributed delays.

The techniques presented improve dramatically on the state-space capacity of previous work in two ways. Firstly, we use a space-efficient function representation scheme based on the evaluation demands of a numerical Laplace transform inversion algorithm. Secondly, we exploit the processing power and memory capacity of a network of machines to perform calculations in parallel. Hypergraph partitioning is used to minimise the amount of communication between processors whilst ensuring that the computational load is balanced. An alternative approach, based on exact state-level aggregation, is also described.

Finally, we describe an extended Continuous Stochastic Logic (eCSL) for the formulation of performance queries for high-level models in a concise and rigorous manner.

Response time and scalability results which have been produced on a range of architectures (including workstation clusters and parallel computers) are presented for several case studies. Our implementations exhibit good scalability and demonstrate the ability to analyse models with state spaces of O(10^7) states and above.

PDF of full publication (1.9 megabytes)
(need help viewing PDF files?)
GZipped Postscript of full publication (1.1 megabytes)
(need help viewing GZipped Postscript files?)

Information from