Performance study of distributed generation of state spaces using colored Petri nets

Zuberek, W.M.

Int. Workshop on Practica Use of CPNs and Design/CPN (CPN'02); Aarhus, Denmark, 27-29 August 2002, pp.81-98.

Abstract:

The performance of many distributed applications depends upon the ratio of computation to communication times. In the case of distributed generation of state spaces for timed Petri nets, this ratio is determined by the partitioning function which assigns generated states to classes associated with processors; if the partition classes correspond to clusters of states with only a few connections between clusters, the required communication is minimized, and the performance is maximized. The effects of state clustering are analyzed by simulating a colored timed Petri net modeling the distributed state space generation.

Keywords:

Colored Petri nets, state space generation, cluster computing, performance analysis, event-driven simulation.

References:

• M. Ajmone Marsan, G. Balbo, and G. Conte, 1984. "A class of generalized stochastic Petri nets for the performance evaluation of systems"; ACM Transactions on Computer Systems, vol.2, no.2, pp.93-122.
• S.C. Allmaier and G. Horton, 1997. "Parallel shared-memory state-space exploration in stochastic modeling"; in "Solving Irregularly structured Problems in Parallel (IRREGULAR'97)" (Lecture Notes in Computer Science), vol.1253, pp.207-218, Springer-Verlag.
• S.C. Allmaier, S. Dalibor, and D. Kreische, 1997. "Parallel graph generation algorithms for shared and distributed memory machines"; in "Parallel Computing: Fundamentals, Applications and New Directions" (Proc. of the Conference ParCo'97), Advances in Parallel Computing vol.12, pp.581-588, Elsevier, North-Holland.
• S.C. Allmaier, M. Kowarschik, and G. Horton, 1997. "State space construction and steady state solution of GPSN on a shared memory multiprocessor"; Proc. IEEE Int. Workshop Petri Nets and Performance Models (PNPM '97), pp.112-121.
• S.C. Allmaier and D. Kreische, 1999. "Parallel approaches to the numerical transient analysis of stochastic reward nets"; in "Application and Theory of Petri Nets 1999" (Proc. 20th International Conference, IACTPN'99), (Lecture Notes in Computer Science 1639), pp.147-167, Springer-Verlag.
• F. Bause and P. Krinzinger, 1996. Stochastic Petri Nets - An Introduction to the Theory. Vieweg.
• E.M. Clarke, O. Grumberg, D. Peled, 1999. Model Checking. MIT Press.
• E. Dijkstra, W. Feijen, and A. van Gasteren, 1983. "Derivation of a termination detection algorithm for distributed computations"; Information Processing Letters, vol.16, no.5, pp.217-219.
• A. Geist, A. Beguelin, J. Dongarra, W. Jiang, R. Manchek, and V. Sunderam, 1994. PVM: Parallel Virtual Machine. A Users' Guide and Tutorial. MIT Press.
• M.A. Holliday, M.K. Vernon, 1987. "Exact performance estimates for multiprocessor memory and bus interference"; IEEE Trans. on Computers, vol.36, no.1, pp.76-85.
• K. Jensen, 1987. "Coloured Petri nets"; in "Advanced Course on Petri Nets 1986" (Lecture Notes in Computer Science 254), pp.248-299, Springer-Verlag.
• P. Marenzoni, S. Caselli, and G. Conte, 1997. "Analysis of large GSPN models: a distributed solution tool"; Proc. IEEE Int. Workshop on Petri Nets and Performance Models (PNPM'97), pp.122-131.
• K.L. McMillan, 2000. "A methodology for hardware verification using compositional model checking", Science of Computer Programming, vol.37, no.1-3, pp.279-309.
• T. Murata, 1989. "Petri nets: properties, analysis, and applications"; Proceedings of the IEEE, vol.77, no.4, pp.541-580.
• J. Peterson, 1981. Petri Net Theory and the Modeling of Systems. Prentice Hall.
• I. Rada, 2000. "Distributed generation of state space for timed Petri nets"; M.Sc. Thesis, Department of Computer Science, Memorial University of Newfoundland, St.John's, Canada.
• I. Rada, W.M. Zuberek, 2001. "Distributed generation of state space for timed Petri nets"; Proc. High Performance Computing Symposium 2001, Seattle, WA, pp.219-227.
• M.R. Steed, M.J. Clement, 1996. "Performance prediction of PVM programs"; Proc. 10-th Int. Parallel Processing Symposium (IPPS-96), pp.803-807.
• W. Stewart, 1994. Introduction to the Numerical Solution of Markov Chains. Princeton University Press.
• B. Wilkinson, 1996. Computer Architecture - Design and Performance (2-nd ed.). Prentice Hall.
• W.M. Zuberek, 1991. "Timed Petri nets, definitions, properties, and applications"; Microelectronics and Reliability, vol.31, no.4, pp.627-644.
• W.M. Zuberek, 1996. "Modeling using timed Petri nets - model description and representation"; Technical Report #9601, Department of Computer Science, Memorial University, St.John's, Canada A1B 3X5.
• W.M. Zuberek, 1996. "Modeling using timed Petri nets - event-driven simulation"; Techical Report #9602, Department of Computer Science, Memorial University, St.John's, Canada A1B 3X5.