Colored Petri nets are a powerful formalism for the description of complex, asynchronous distributed systems. They can express in a very concise way the behavior of very large systems, especially in case these systems are composed of many replications of a few basic components that individually behave in a similar way. The simulation of such models is, however, difficult to perform in a computationally efficient way. For the specific class of stochastic well-formed nets (SWNs), we present a set of optimizations that allow a very efficient implementation of the event-driven simulation technique. Three approaches are followed to improve simulation efficiency: first, an efficient algorithm for the computation of the occurrences of a transition in a given marking; second, reduction of the amount of work needed to schedule or preempt the occurrence of a transition as a consequence of a marking change, taking into account the restrictions on color functions for the SWN formalism; third, reduction of the average length of the event list in the case of symmetric models where the so-called symbolic simulation technique applies. The approach is validated by performance measurements on several large SWN models taken from the literature

Efficient discrete-event simulation of colored Petri nets

GAETA, Rossano
1996-01-01

Abstract

Colored Petri nets are a powerful formalism for the description of complex, asynchronous distributed systems. They can express in a very concise way the behavior of very large systems, especially in case these systems are composed of many replications of a few basic components that individually behave in a similar way. The simulation of such models is, however, difficult to perform in a computationally efficient way. For the specific class of stochastic well-formed nets (SWNs), we present a set of optimizations that allow a very efficient implementation of the event-driven simulation technique. Three approaches are followed to improve simulation efficiency: first, an efficient algorithm for the computation of the occurrences of a transition in a given marking; second, reduction of the amount of work needed to schedule or preempt the occurrence of a transition as a consequence of a marking change, taking into account the restrictions on color functions for the SWN formalism; third, reduction of the average length of the event list in the case of symmetric models where the so-called symbolic simulation technique applies. The approach is validated by performance measurements on several large SWN models taken from the literature
1996
22
629
639
Discrete event simulation; high level Petri nets; stochastic well formed nets; model symmetries; efficient simulation algorithms; symbolic simulation
R. GAETA
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2318/113735
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 38
  • ???jsp.display-item.citation.isi??? 26
social impact