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. However, simulation's computational requirements 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. Simple techniques for the automated parallelization of timed Petri-net simulations are described. Both the issue of processor synchronization, as well as the automated mapping, static and dynamic, of the Petri-net to the parallel architecture are addressed. As part of this effort, a new mapping algorithm, one that also applies to more general parallel computations, is described. Analytic properties of the solution produced by the algorithm, including optimality on some regular topologies, are established. The viability of our integrated approach is demonstrated empirically on the Intel iPSC/860 and Delta architectures using many processors. Excellent performance is observed on models of parallel architectures.