ANALYSIS OF GSPN MODELS - Modelling with Generalised Stochastic Petri Nets - page 147

6.5 Simulation of GSPN Systems

One of the problems that hamper the analysis of GSPN systems is the
exponential growth of their state space that makes it often impossible to
construct (and store) their reachability sets. In these cases it becomes also
impossible to construct the associated stochastic processes, so that it often
happens that the only way of assessing the properties of the corresponding
systems is via simulation.
The simulation of a GSPN system for performance evaluation purposes cor-
responds to generating a sample path through the state space of the system,
and to collecting measurements on particular aspects of GSPN system be-
haviour.
GSPN systems a re suitable for discrete-event simulation in which the events
that characterize the changes of states and the times spent in states are
the only relevant aspects of model behaviour. Events correspond to transi-
tion firings and the time spent in states derives from the temporal distance
between transition firings. The simulation of a GSPN system corresponds
to identifying a current event that is certain to happen given the current
marking, as well as the other events that may happen in the future given
the information provided by the same marking (scheduled events). Firing
the transition that corresponds to the current event produces a change of
marking in which new transitions may become enabled, and other transitions
(that were previously enabled) may become disabled.
The identification of the transitions that are enabled in a given marking as
well as the transitions that are affected by the change of marking due to a
transition firing is one of the main problem in the e cient simulation of large
GSPN systems. When the set of transitions of the GSPN is large, testing at
each change of marking all the elements of the set to see which transitions
are enabled may be extremely time consuming. A considerable advantage
can be gained by exploiting interesting relationships among transitions that
can be obtained from a structural analysis of the model.
Consider the set E(M) of transitions that are enabled in a given marking
M. This set is usually substantially smaller than the set of transitions of
the GSPN. Supposing that transition t (t ∈ E(M)) has been selected to
fire, let ∆ t (M) and ∆ − t (M) represent the set of transitions whose enabling
is caused by the firing of t and the set of transitions that become disabled
after the firing of t, respectively. The set of transitions enabled in the new
marking M 0 (E(M 0 )) is related with the old one by the following relation:

E(M 0 ) = E(M) + ∆ t (M) − ∆ − t (M) (6.45)

Since the number of transitions affected by the firing of t is usually small,
this “incremental” construction of the new set of enabled transitions has
the potential of greatly reducing the time needed for its computation with