Efficient discrete-event simulation of colored Petri nets
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 (SWN) 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, 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.
stochastic well-formed nets symbolic simulation discrete event simulation high-level petri nets model symmetries efficient simulation algorithms