Techniques for the Construction and Analysis of Algebraic Performance Models

Graham Clark


The performance modeller may attempt to quantitatively analyse the behaviour of computer systems by building performance models. Such models may become unwieldy, and so high-level structured modelling modelling techniques have been developed. A stochastic process algebra (SPA) provides such a technique, a compositional modelling calculus. Hillston's PEPA is an SPA, a classical process algebra enhanced to represent the performance of systems. This thesis uses PEPA as a foundation, and examines different ways to assist the SPA performance modeller.
A weak stage in the SPA methodology is the calculation of concrete performance measures, since much research does not focus beyond a steady-state probability vector. A framework is developed for specifying steady-state performance measures for PEPA models. The technique is used at the high-level of the process algebra, and not applied directly to states, or the stochastic process. It employs an enhanced modal logic to allow the modeller to identify interesting model behaviour. Furthermore, the modeller may choose to study only the behaviour of subcomponents in the model context. The method automatically specifies a Markov reward model (MRM). The modal logic is suitably expressive`; it is shown to characterise PEPA's strong equivalence relation. Conditions are given under which model subcomponents may be aggregated such that the MRM is guaranteed to be strongly lumpable. The technique is compared to various other solutions to the reward specification problem.
If a randomly distributed model feature possesses the insensitivity property, then the equilibrium solution of the model only depends on the mean of the distribution. A new SPA combinator is defined which builds a model from a set of simple components restricted to queue to perform particular activities. It is demonstrated that a subset of the activities of these SPA models are insensitive, and therefore may have generally distributed durations. Furthermore, it is proven that a model of this structure exhibits a product form solution over its submodels, allowing its solution to be expressed as a product over the smaller solutions of its parts. This work leads to a more general examination of insensitivity in SPA models. An extension to PEPA is defined which allows activities with generally distributed durations. Balance conditions are given which guarantee the insensitivity of these activities. However these conditions are strong, and at the level of the stochastic process.
Models of transaction processing systems (TPS) are presented as a case study. These systems consist of a centralised database, and a set of transactions which access database objects. Sample performance measures are specified for TPS models, and a model of a TPS is constructed using the new combinator, guaranteeing the insensitivity of a subset of its activities.

This report is available in the following formats:

Previous | Index | Next