Automated Parallelization of Timed Petri-Net Simulations

Timed Petri-nets are used to model numerous types of large complex systems, especially computer architectures and communication networks. While formal analysis of such models is sometimes possible, discrete-event simulation remains the most general technique available for assessing the model′s behavior. Simulation′s computational requirements, however, can be massive, especially on the large complex models that defeat analytic methods. One way of meeting these requirements is by executing the simulation on a parallel machine. This paper describes simple techniques for the automated parallelization of timed Petri-net simulations. We address the issue of processor synchronization as well as the automated mapping, both static and dynamic, of the Petri-net to the parallel architecture. As part of this effort we describe a new mapping algorithm, one that also applies to more general parallel computations. We establish analytic properties of the solution produced by the algorithm, including optimality on some regular topologies, The viability of our integrated approach is demonstrated empirically on the Intel iPSC/860 and Delta architectures on Petri-net-based simulations of parallel architectures.