Parallel simulation of performance Petri nets: extending the domain of parallel simulation

The authors present a parallel simulation protocol for performance Petri nets (PPNs), nets in which transition firings take randomly selected amounts of time. This protocol is interesting for two reasons. First, application of standard conservative or optimistic parallel simulation to PPNs results in either unnecessarily low (possibly no) parallelism or simply fails to produce correct results. Thus, this protocol may be thought of as addressing a class of models not amenable to standard parallel simulation, with PPNs being a particular example. Second, PPNs are currently analyzed using numerical techniques that have time and space requirements exponential in the size of the net. Simulation, particularly parallel simulation, is thus a practical alternative analysis method for these models, as is shown by measurement of execution times. The authors introduce a technique called selective receive that loosens a fundamental rule of conservative parallel simulation by allowing model components to sometimes ignore certain of their input channels and thus to determine their local clock times based on only a subset of their potential inputs