The syntactic nature and compositionality characteristic of stochastic process algebras make models to be easily understood by human beings, but not convenient for machines as well as people to directly carry out mathematical analysis and stochastic simulation. This paper presents a numerical representation schema for the stochastic process algebra PEPA, which can provide a platform to directly and conveniently employ a variety of computational approaches to both qualitatively and quantitatively analyse the models. Moreover, these approaches developed on the basis of the schema are demonstrated and discussed. In particular, algorithms for automatically deriving the schema from a general PEPA model and simulating the model based on the derived schema to derive performance measures are presented.
Our work is motivated and stimulated by the pioneering work on the numerical vector form and activity matrix in @cite_1 , which was dedicated to the fluid approximation for PEPA. The P T structure underlying each PEPA model, as stated in Theorem in this paper, reveals tight connections between stochastic process algebras and stochastic Petri nets. Based on this structure and the theories developed for Petri nets, several powerful techniques for structural analysis of PEPA were presented in @cite_0 , including a structure-based deadlock-checking method which avoids the state space explosion problem. @cite_5 , a new operational semantics was proposed to give a compact symbolic representation of PEPA models. This semantics extends the application scope of the fluid approximation of PEPA by incorporating all the operators of the language and removing earlier assumptions on the syntactical structure of the models amenable to this analysis. Moreover, the paper @cite_2 shows how to derive the performance metrics such as action throughput and capacity utilisaition from the fluid approximation of a PEPA model.
@cite_0 @cite_5 @cite_1 @cite_2
2076829994 2111390218 2112901936
The exact performance analysis of large-scale software systems with discrete-state approaches is difficult because of the well-known problem of state-space explosion. This paper considers this problem with regard to the stochastic process algebra PEPA, presenting a deterministic approximation to the underlying Markov chain model based on ordinary differential equations. The accuracy of the approximation is assessed by means of a substantial case study of a distributed multithreaded application. In this paper we present a novel performance analysis technique for large scale systems modelled in the stochastic process algebra PEPA. In contrast to the well-known approach of analysing via continuous time Markov chains, our underlying mathematical representation is a set of coupled ordinary differential equations (ODEs). This analysis process supports all of the comhinators of the PEPA algebra and is well suited to systems with large numbers of replicated components. The paper presents an elegant procedure for the generation of the ODEs and compares the results of this analysis with more conventional methods. Reasoning about the performance of models of software systems typically entails the derivation of metrics such as throughput, utilization, and response time. If the model is a Markov chain, these are expressed as real functions of the chain, called reward models. The computational complexity of reward-based metrics is of the same order as the solution of the Markov chain, making the analysis infeasible when evaluating large-scale systems. In the context of the stochastic process algebra PEPA, the underlying continuous-time Markov chain has been shown to admit a deterministic (fluid) approximation as a solution of an ordinary differential equation, which effectively circumvents state-space explosion. This paper is concerned with approximating Markovian reward models for PEPA with fluid rewards, i.e., functions of the solution of the differential equation problem. It shows that (1) the Markovian reward models for typical metrics of performance enjoy asymptotic convergence to their fluid analogues, and that (2) via numerical tests, the approximation yields satisfactory accuracy in practice.