Sage Journals: Discover world-class research

Abstract

Generalized stochastic Petri nets (GSPNs) are widely used in the performance analysis of computer and communications systems. Response time densities and quantiles are often key outputs of such analysis. These can be extracted from a GSPN’s underlying semi-Markov process using a method based on numerical Laplace transform inversion. This method typically requires the solution of thousands of systems of complex linear equations, each of rank n, where n is the number of states in the model. For large models substantial processing power is needed and the computation must therefore be distributed. In this paper we describe the implementation of a response time analysis module for the Platform Independent Petri net Editor (PIPE2) which interfaces with Hadoop, an open-source implementation of Google’s MapReduce distributed programming environment, to provide distributed calculation of response time densities in GSPN models. The software is validated with results calculated analytically as well as simulated results for larger models. Excellent scalability is shown.

Keywords

generalized stochastic Petri nets MapReduce response time analysis

Get full access to this article

View all access options for this article.

References

Bonet, P. , C.M. Llado , R. Puijaner and W.J. Knottenbelt. 2007. PIPE v2.5: a Petri net tool for performance modelling. In Proceedings of the 23rd Latin American Conference on Informatics (CLEI 2007) , San Jose, Costa Rica, October 2007 .

Dingle, N.J. , P.G. Harrison and W.J. Knottenbelt. 2002. Response time densities in Generalised Stochastic Petri net models. In Proceedings of the 3rd ACM Workshop on Software and Performance (WOSP 2002), Rome, Italy, 2002, pp. 46-54.

Bause, F. and P.S. Kritzinger. 2002. Stochastic Petri Nets: An Introduction to the Theory, 2nd edition, Vieweg-Verlag, Wiesbaden.

Bradley, J.T. , N.J. Dingle , W.J. Knottenbelt and H.J. Wilson. 2004. Hypergraph-based parallel computation of passage time desnsities in large semi-Markov models. Linear Algebra and its Applications, 386: 311-334.

Abate, J. and W. Whitt. 1992. The Fourier-series method for inverting transforms of probability distributions. Queueing Systems, 10(1): 5-88.

Knottenbelt, W.J. and P.G. Harrison. 2002. Passage time distributions in large Markov chains. In Proceedings of ACM SIGMETRICS , Marina Del Rey, CA, June 2002, pp. 77-85.

Muppala, J.K. and K.S. Trivedi. 1992. Numerical transient analysis of finite Markovian queueing systems. In U.N. Bhat and I.V. Basawa , Eds, Queueing and Related Models, pp. 262-284.

Melamed, B. and M. Yadin. 1984. Randomization procedures in the computation of cumulative-time distributions over discrete state Markov processes. Operations Research, 32(4): 926-944.

Dingle, N.J. , P.G. Harrison and W.J. Knottenbelt. 2004. Uniformisation and hypergraph partitioning for the distributed computation of response time densities in very large Markov models. Journal of Parallel and Distributed Computing, 64(8): 908- 920.

10.

Bradley, J.T. and W.J. Knottenbelt. 2004. The ipc/HYDRA tool chain for the analysis of PEPA models. In Proceedings of the 1st International Conference on the Quantitative Evaluation of Systems (QEST 2004), September 2004, pp. 334-335.

11.

Dingle, N.J. 2004. Parallel Computation of Response Time Densities and Quantiles in Large Markov and Semi-Markov Models. PhD thesis, Imperial College, London, UK.

12.

Dean, J. and S. Ghemawat. 2004. MapReduce: simplified data processing on large clusters . In Proceedings of the OSDI’04: Sixth Symposium on Operating System Design and Implementation, San Francisco , CA, December 2004.

13.

Ekanayake, J. , S. Pallickara and G. Fox . 2008. MapReduce for data intensive scientific analyses. In Proceedings of the 4th IEEE International Conference on eScience, pp. 277-284.

14.

Kimber, T. , B. Kirby , T. Master and M. Worthington. 2007. Petri Nets Group Project Final Report. Technical report , Imperial College, London, UK.

15.

Knottenbelt, W.J. 1996. Generalised Markovian Analysis of Timed Transition Systems. Master’s thesis, University of Cape Town, Cape Town, South Africa.

16.

Woodside, C.M. and Y. Li . 1991. Performance Petri net analysis of communication protocol software by delay-equivalent aggregation. In Proceeding of the 4th International Workshop on Petri nets and Performance Models (PNPM’91), Melbourne , Australia, December 1991, IEEE Computer Society Press, Los Alamitos, CA, pp. 64-73.

Distributed Response Time Analysis of GSPN Models with MapReduce

Abstract

Keywords

Get full access to this article

References