Approximate closed-form aggregation of a fork-join structure in generalised stochastic petri nets

ABSTRACT

In this paper an aggregation technique for generalised stochastic Petri nets (GSPNs) possessing synchronised parallel structures is presented. Parallel processes featuring synchronisation constraints commonly occur in fields such as product assembly and computer process communications, however their existence in closed networks severely complicates analysis. This paper details the derivation of computationally-simple closed-form expressions which permit the aggregation of a GSPN subnet featuring a fork-join structure. The aggregation expressions presented in this paper do not require the generation of the underlying continuous time Markov chain of the original net, and do not follow an iterative procedure. The resulting aggregated GSPN accurately approximates the stationary token distribution behaviour of the original net, and this is shown by the analysis of a number of example GSPNs.

References

1. F. Baccelli, W. A. Massey, and D. Towsley, "Acyclic fork-join queuing networks," Journal of the Association for Computing Machinery, vol. 36, no. 3, pp. 615--642, 1989.]]
2. J. L. Peterson, Petri Net Theory and the Modeling of Systems. NJ, USA: Prentice Hall, 1981.]]
3. W. Reisig, Petri Nets: An Introduction. Springer, 1985.]]
4. M. A. Marsan, G. Balbo, G. Conte, S. Donatelli, and G. Franceschinis, Modelling with Generalized Stochastic Petri Nets. Chichester, England: John Wiley and Sons, 1995.]]
5. J. Desel and W. Reisig, "Place/transition Petri nets." in LNCS 1491, 1998, pp. 122--173.]]
6. A. Valmari, "The state explosion problem." in LNCS 1491, 1998, pp. 429--528.]]
7. J. Freiheit and A. Heindl, "Novel formulae for GSPN aggregation." in The Tenth IEEE/ACM International Symposium on Modeling, Analysis and Simulation of Computer and Telecommunication Systems (MASCOTS 2002), 2002, pp. 209--216.]]
8. J. Freiheit and J. Billington, "New developments in closed-form computation for GSPN aggregation." in LNCS 2885, 2003, pp. 471--490.]]
9. J. Freiheit and J. Billington, "Closed-form token distribution computation of GSPNs without synchronisation," in 11th International Conference on Analytical and Stochastic Modelling Techniques and Applications (ASMTA 2004), 2004, pp. 199--206.]]
10. M. Sereno, "Approximate mean value analysis technique for non-product form solution stochastic Petri nets: An application to stochastic marked graphs," in Proceedings 6th International Workshop on Petri Nets and Performance Models - PNPM'95, IEEE Computer Soc. Press, Durham, N. Carolina, USA, 1995, pp. 42--51.]]
11. T. G. Robertazzi, Computer Networks and Systems, 3rd ed. New York: Springer-Verlag, 2000.]]
12. K. Chandy, U. Herzog, and L. Woo, "Parametric analysis of queueing networks," IBM Journal of Research and Development, vol. 19, no. 1, pp. 36--42, January 1975.]]
13. G. Balbo, S. C. Bruell, and S. Ghanta, "Combining queueing networks and generalized stochastic Petri nets for the solution of complex models of system behavior," IEEE Transactions on Computers, vol. 37, no. 10, pp. 1251--1268, 1988.]]
14. D. C. Petriu and C. M. Woodside, "Approximate mean value analysis based on Markov chain aggregation by composition," Linear Algebra and its Applications, vol. 386, pp. 335--358, 2004.]]
15. E. Varki, "Mean value technique for closed fork-join networks," in SIGMETRICS '99: Proceedings of the 1999 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, 1999, pp. 103--112.]]
16. J. Freiheit, Matrizen- und zustandsraumreduzierende Verfahren zur Leistungsbewertung großer stochastischer Petrinetze. TU Berlin, June 2002, PhD Thesis.]]
17. M. A. Marsan, G. Balbo, and G. Conte, Performance models of multiprocessor systems. Cambridge, MA, USA: MIT Press, 1986.]]
18. G. Florin and S. Natkin, "Generalization of queueing network product form solutions to stochastic Petri nets," IEEE Transactions on Software Engineering, vol. 17, no. 2, pp. 99--107, 1991.]]
19. L. Flatto and S. Hahn, "Two parallel queues created by arrivals with two demands," SIAM Journal on Applied Mathematics, vol. 44, no. 5, p. 1041, 1984.]]
20. Y. C. Liu and H. G. Perros, "A decomposition procedure for the analysis of a closed fork/join queueing system," IEEE Transactions on Computers, vol. 40, no. 3, pp. 365--370, 1991.]]
21. B. Prabhakar, N. Bambos, and T. S. Mountford, "Synchronization of Poisson processes and queueing networks with service and synchronization nodes," Advances in Applied Probability, vol. 32, no. 3, pp. 824--843, 2000.]]
22. A. Duda and T. Czachórski, "Performance evaluation of fork and join synchronization primitives," Acta Informatica, vol. 24, no. 5, pp. 525--553, 1987.]]
23. W. Henderson and D. Lucic, "Aggregation and disaggregation through insensitivity in stochastic Petri nets," Performance Evaluation, vol. 17, no. 2, pp. 91--114, 1993.]]
24. S. Donatelli and M. Sereno, "On the product form solution for stochastic Petri nets," in LNCS 616, 1992, pp. 154--172.]]
25. "The MathWorks," http://www.mathworks.com/.]]
26. "TimeNET," http://pdv.cs.tu-berlin.de/~timenet/.]]

Index Terms

• Computer systems organization

  • Architectures

    • Parallel architectures

      • Cellular architectures

• Hardware

  • Emerging technologies

    • Quantum technologies

      • Quantum dots and cellular automata

• Mathematics of computing

  • Probability and statistics

    • Statistical paradigms

      • Queueing theory

    • Stochastic processes

• Software and its engineering

  • Software organization and properties

    • Software system structures

      • Software system models

        • Petri nets

• Theory of computation

  • Models of computation

    • Concurrency

      • Parallel computing models

    • Probabilistic computation