AESOP home


Aggregation strategies for large semi-Markov processes

Marcel C. Guenther, Nicholas J. Dingle, Jeremy T. Bradley, William J. Knottenbelt

Conference or Workshop Paper
3rd International Symposium on Semi-Markov Models: Theory and Applications
May, 2009

High-level semi-Markov modelling paradigms such as semi-Markov stochastic Petri nets and process algebras are used to capture realistic performance models of computer and communication systems but often have the drawback of generating huge underlying semi-Markov processes. Extraction of performance measures such as steady-state probabilities and passage-time distributions therefore relies on sparse matrix-vector operations involving very large transition matrices. The computational complexity of such operations depends on the number of rows and non-zeros in the matrix.

Previous studies have shown that exact state-by-state aggregation of semi-Markov processes can be applied to reduce the number of states. However, it is important to select the order in which states are aggregated judiciously so as to avoid a dramatic increase in matrix density caused by the creation of additional transitions between remaining states. Our paper addresses this issue by presenting the concept of state space partitioning for aggregation. Partitioning the state space entails dividing it into a number of non-intersecting subsets. In contrast to previous algorithms that perform state-by-state aggregation on the global unpartitioned graph, our new algorithm works on a local partition-by-partition basis which allows more space-efficient aggregation. We introduce different partitioning methods for this purpose. Furthermore we discuss partition sorting methods that determine the order in which partitions should be aggregated. This order has a significant impact on the connectivity of the aggregate state space, and thus the density of the transition matrix.

Aggregation of partitions can be done in one of two ways. The first way is to use exact state-by-state aggregation to aggregate each individual state within a partition. For this purpose, we present a new state ordering algorithm, which takes into account the exact number of new transitions that are created when aggregating a particular state. This technique is preferable to existing ordering methods which only approximate the number of newly created transitions. A second approach to the aggregation of partitions is atomic partition aggregation. Inspired by a technique used in passage-time analysis, this collapses a whole partition into a small number of semi-Markov states and transitions.

Most partitionings produced by existing graph partitioners are not suitable for use with our atomic partition aggregation techniques, and we therefore present a new deterministic partitioning method which we term barrier partitioning. We show that barrier partitioning is capable of splitting large semi-Markov models into two balanced partitions such that first passage-time analysis can be performed using 50% less memory than existing algorithms, without compromising speed.

PDF of full publication (60.3 kilobytes)
(need help viewing PDF files?)
Postscript of full publication (97.2 kilobytes)
(need help viewing Postscript files?)
PDF of presentation slides (615.9 kilobytes)

Information from