Petri-net evaluation using APL2

ABSTRACT

A Petri net is a graphical and mathematical modeling tool useful in the analysis of concurrent, asynchronous, distributed, parallel, nondeterministic, and/or stochastic systems. In addition, interest in Petri nets is increasing in the software community to model the behavior of parallel computer programs. The introduction of timed Petri nets allows system or program performance to be estimated as well. This paper begins with a general discussion, including definitions, for both ordinary and timed Petri nets. Several analysis tools are outlined for ordinary and timed Petri nets including analysis of the incidence matrix, coverability tree, firing diagram, and the GRID (Graph of Reachable Instantaneous Descriptions). This paper then introduces a method for representing Petri nets in APL2 and defines an easy input method. An APL2 implementation of each of the above analysis tools is given. These functions are described in detail as to their operation. Several examples of their use are given including examples of deadlock detection and performance estimation.

REFERENCES

• 1: F. Archet/i, et.al., A Petri net modeling of a highly concurrent machine, 5th International Conference on Systems Engineering, Sept 1987, p 389'93
• 2: Carl K. Chang , Young-Fu Chang , Lin Yang , Ching-Roung Chou , Jong-Jeng Chen, Modeling a Real-Time Multitasking System in a Timed PQ Net, IEEE Software, v.6 n.2, p.46-51, March 1989 [doi>10.1109/52.23129]
• 3: R.H. Gallard, An Extension in the Definition of a Petri Net Execution, The Computer Journal, vol. 30, no. 1, 1987, p.16-19
• 4: Kumkum Garg, An approach to performance specification of communication protocols using timed Petri nets, IEEE Transactions on Software Engineering, v.11 n.10, p.1216-1225, Oct. 1985 [doi>10.1109/TSE.1985.231869]
• 5: P. J. Haas , G. S. Shedler, Stochastic Petri Net Representation of Discrete Event Simulations, IEEE Transactions on Software Engineering, v.15 n.4, p.381-393, April 1989 [doi>10.1109/32.16599]
• 6: Mark A. Holliday , Mary K. Vernon, A generalized timed petri net model for performance analysis, IEEE Transactions on Software Engineering, v.13 n.12, p.1297-1310, December 1, 1987 [doi>10.1109/TSE.1987.233141]
• 7: Chuang Lin , Dan Christian Marinescu, Stochastic High-Level Petri Nets and Applications, IEEE Transactions on Computers, v.37 n.7, p.815-825, July 1988 [doi>10.1109/12.2227]
• 8: Jan Magott, Performance Evaluation of Concurrent Systems using Petri nets, Information Processing Letters, vol. 18, no. 1, 1984, p.7-13
• 9: Marco Ajmone Marsan , Gianni Conte , Gianfranco Balbo, A class of generalized stochastic Petri nets for the performance evaluation of multiprocessor systems, ACM Transactions on Computer Systems (TOCS), v.2 n.2, p.93-122, May 1984 [doi>10.1145/190.191]
• 10: Marco Ajmone Marsan , Giovanni Chiola, On Petri nets with deterministic and exponentially distributed firing times, Advances in Petri Nets 1987, covers the 7th European Workshop on Applications and Theory of Petri Nets, p.132-145, June 01, 1986
• 11: Michael K. Molloy, Performance Analysis u:~ing Stochastic Petri Nets, IEEE Transactions on Computers, Vol. C-31, No. 9, p.913-917, Sept 1982
• 12: Michael K. Molloy, Discrete time stochastic Petri nets, IEEE Transactions on Software Engineering, v.11 n.4, p.417-423, April 1985 [doi>10.1109/TSE.1985.232230]
• 13: Tadao Murata, Petri Nets: Properties, Analysis and Applications, Proceedings of the IEEE, vol. 77, no. 4, April 1989, p.541-580
• 14: Jerre Noe and Gary J. Nutl, Macro E-nets for representation of Parallel systems, IEEE Transactions on Computers, Vol. C-22, No. 8, p.718-727, Aug 1973
• 15: Daniel Pease, Parallel Processors and Processing, CSE 763 Lecture notes, Syracuse University, 1987
• 16: C.V. Ramamoorthy and Gary S. Ho, Performance Evaluation of Asynchroous Concurrent Systems using Petri Nets, IEEE Transactions on Software Engineering, VoI.SE-6, No. 5, p.440-449, Sept 1980
• 17: Wlodzimierz M. Zuberek, M-timed Petri nets, priorities, preemptions, and performance evaluation of Petri nets, Advances in Petri Nets 1985, covers the 6th European Workshop on Applications and Theory in Petri Nets-selected papers, p.478-498, June 01, 1985
• 18: Wiedzimiers M. Zuberek, Performance Evaluation using Extended Timed Petri Nets, p.272-8 (1985;)
• 19: Wiedzimiers M. Zuberek, Timed Petri Nets and Preliminary Performance Evaluation, 1980

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications

          Nouns: APL

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Trees; Graph algorithms

General Terms:
Algorithms, Languages