Parallel Simulation of Stochastic Petri Nets Using Recursive Equations

摘要

A parallel simulation method for the class of stochastic decision free Petrinets, that is amenable to an SIMD implementation is proposed. This method is based on the max, plus or minus linear structure of recursive equations that were established for this type of system. Two variants are analyzed, the spatial and the temporal methods. The spatial method allows simulation of large networks. The temporal method, which generalizes to Petri nets a method that was introduced recently for queues, is of more use for simulating systems for a long interval. The emphasis is put on the spatial approach which is shown to provide a simple way of estimating both the cycle time and the statistics of the marking process. The theoretical complexity of this algorithm is investigated. In particular, a few examples of practical interest are provided (blocking queues in tandem and a stochastic job shop model) for which the cost of simulating O(NT) events of a net of size T is in O(N log T) with this parallel simulation method, while the classical sequential discrete event simulation is in O(NT) at least. These theoretical considerations are confirmed by experimental results obtained from a prototype that was implemented on the Connection Machine.