AESOP home


Tackling Large State Spaces in Performance Modelling

William J. Knottenbelt, Jeremy T. Bradley

Book Chapter
SFM-07:PE, 7th International School on Formal Methods for the Design of Computer, Communication and Software Systems: Performance Evaluation. 28 May - 2 June 2007
Formal Methods for Performance Evaluation
Lecture Notes in Computer Science
Volume 4486
May, 2007
DOI 10.1007/978-3-540-72522-0_8

Stochastic performance models provide a powerful way of capturing and analysing the behaviour of complex concurrent systems. Traditionally, performance measures for these models are derived by generating and then analysing a (semi-)Markov chain corresponding to the model's behaviour at the state-transition level. However, and especially when analysing industrial-scale systems, workstation memory and compute power is often overwhelmed by the sheer number of states. This chapter explores an array of techniques for analysing stochastic performance models with large state spaces. We concentrate on explicit techniques suitable for unstructured state spaces and show how memory and run time requirements can be reduced using a combination of probabilistic algorithms, disk-based solution techniques and communication-efficient parallelism based on hypergraph-partitioning. We apply these methods to different kinds of performance analysis, including steady-state and passage-time analysis, and demonstrate them on case study examples.


Bernardo, Hillston (Eds)

PDF of full publication (999.6 kilobytes)
(need help viewing PDF files?)
GZipped Postscript of full publication (528.4 kilobytes)
(need help viewing GZipped Postscript files?)
PDF of presentation slides (3.4 megabytes)

Information from