AUTOMATED PARALLELIZATION OF TIMED PETRI-NET SIMULATIONS

Timed Petri-nets are used to model numerous types of large complex sys tems, especially computer architectures and communication networks. Wh ile formal analysis of such models is sometimes possible, discrete-eve nt simulation remains the most general technique available for assessi ng the model's behavior. Simulation's computational requirements, howe ver, can be massive, especially on the large complex models that defea t analytic methods. One way of meeting these requirements is by execut ing the simulation on a parallel machine. This paper describes simple techniques for the automated parallelization of timed Petri-net simula tions. We address the issue of processor synchronization as well as th e automated mapping, both static and dynamic, of the Petri-net to the parallel architecture. As part of this effort we describe a new mappin g algorithm, one that also applies to more general parallel computatio ns. We establish analytic properties of the solution produced by the a lgorithm, including optimality on some regular topologies, The viabili ty of our integrated approach is demonstrated empirically on the Intel iPSC/860 and Delta architectures on Petri-net-based simulations of pa rallel architectures. (C) 1995 Academic Press, Inc