Distributed generation of state space for timed Petri nets

Rada, I. and Zuberek, W.M.

Proc. High Performance Computing Symposium 2001; Seattle, WA, 23-26 April 2001, pp.219-227.

Abstract:

A cluster of PC's is used for the generation of state space for timed Petri nets. Disjoint regions of the state graph are generated on different machines. On each machine, the communication is separated from the computation part, and is performed by two concurrent processes: one receiving, and one sending messages to other machines. The implementation is based on PVM (Parallel Virtual Machine) using a modified version of TPN-tools. Experiments performed on a cluster of 32 PC's show almost linear speedup for some classes of timed Petri nets.

Keywords:

Timed Petri nets, state space generation, distributed computing, concurrent processes, space partitioning, speedup, PVM.

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, S. Dalibor, and D. Kreische, 1998. "Parallel graph generation algorithms for shared and distributed memory machines"; in Parallel Computing: Fundamentals, Applications and New Directions (Advances in Parallel Computing vol.12), pp.581-588, Elsevier.
• S.C. Allmaier and G. Horton, 1997. "Parallel shared-memory state-space exploration in stochastic modeling"; Solving Irregularly Structured Problems in Parallel (LNCS 1253), pp.207-218, Springer-Verlag.
• S.C. Allmaier, M. Kowarschik, and G. Horton, 1997. "State space construction and steady state solution of GPSN on a shared memory multiprocessor"; Proc. 7-th 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 (LNCS 1639), pp.147-167, Springer-Verlag.
• G. Balbo, 1995. "On the success of stochastic Petri nets"; Proc. 6-th IEEE Conf. on Petri Nets and Performance Models (PNPM'95), pp.2-9.
• S. Caselli and G. Conte, 1991. "GSPN models of concurrent architectures with mesh topology"; Proc. 4-th Int. Workshop on Petri Nets and Performance Models (PNPM'91), pp.280-289.
• 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.
• G. Florin and S. Natkin, 1986. "One-place unbounded stochastic Petri nets: ergodic criteria and steady-state solutions"; Journal of Systems and Software, vol.6, no.1-2, pp.103-115.
• A. Geist, A. Beguelin, J. Dongarra, W. Jiang, R. Manchek, and V. Sunderam, 1994. PVM: Parallel Virtual Machine. A Users' Guide and Tutorial for Networked Parallel Computing. MIT Press.
• K. Kant, 1992. Introduction to Computer Systems Performance Evaluation. McGraw Hill.
• P. Marenzoni, S. Caselli, and G. Conte, 1997. "Analysis of large GSPN models: a distributed solution tool"; Proc. 7-th IEEE Int. Workshop on Petri Nets and Performance Models (PNPM'97), pp.122-131.
• T. Murata, 1989. "Petri nets: properties, analysis, and applications"; Proceedings of the IEEE, vol.77, no.4, pp.541-580.
• D. M. Nicol and G. Ciardo, 1997. "Automated parallelization of discrete state-space generation"; Journal of Parallel and Distributed Computing, vol.47, no.2, pp.153-167.
• D. Nicol and G. Ciardo, 1998. "Distributed state space generation of discrete state stochastic models"; INFORMS Journal on Computing, vol.10, no.1, pp.82-92.
• 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 A1B 3X5.
• W. Stewart, 1994. Introduction to the Numerical Solution of Markov Chains. Princeton University Press.
• P. Stotts and T. Pratt, 1990. "Coverability graphs for a class of synchronously executed unbounded Petri nets"; Journal of Parallel and Distributed Computing, vol.10, no.4, pp.253-260.
• B. Stroustrup, 1997. The C++ Programming Language (3-rd ed.). Addison-Wesley.
• W.M. Zuberek, 1988. "On generation of state space for timed Petri nets"; Proc. of ACM 16th Annual Computer Science Conference, pp.239-248.
• W.M. Zuberek, 1991. "Timed Petri nets - definitions, properties, and applications"; Microelectronics and Reliability, vol.31, no.4, pp.627-644.
• W.M. Zuberek, 2000. "Petri nets and timed Petri nets: basic concepts and properties" (Lecture notes for CS-6726: "Modeling and Analysis of Computer Systems"); Technical Report #2000-01, Department of Computer Science, Memorial University, St.John's, Canada A1B 3X5.

Available in pdf and postscript.