Deliverable D16b

Distributed and Parallel Simulation of Networks

• Introduction to the deliverable
• Contents of the deliverable

Introduction to Deliverable D16b

This deliverable reports the latest advances in Parallel and Distributed simulation. The type of simulation discussed here is the one based on evolution equations obtained for state variables of the systems, rather than on event-based simulation.

The evolution of the research is characterized by the following points:

• extension of the ``equational simulation'' technique, initially devised for stochastic event graphs (in general, linear (max,+) systems), to wider classes of Petri nets, namely: Free Choice Nets;

• the shift of emphasis from data parallel (or SIMD) architectures to more loosely coupled distributed memory architectures, such as heterogeneous groups of workstations connected by a local network;

• a careful algorithmic analysis of the simulation kernel, leading to a better understanding of the intrinsic computation and memory complexities of the simulation. This point made also appear connections between the equational simulation techniques and cyclic scheduling problems, and VLSI circuit optimization.

i/ The paper ``Parallel and Distributed Simulation of Free Choice Petri Nets'', by François Baccelli, Nathalie Furmento and Bruno Gaujal (D16b-1), describe how evolution equations for Free Choice Nets can be derived, structured and scheduled for parallel simulation. The decomposition of equations provides a natural way for grouping simulation elements in the distributed simulator, a well known crucial issue.

ii/ The equations used for this are not linear, which makes difficult their time simulation. In ``Some Algebraic Considerations for Efficient Computations in Timed Petri Nets'', by Bruno Gaujal (D16b-2), this difficulty is circumvented by considering an analogous fluid model, whose equations become linear in the standard algebra, and lend themselves to time parallel simulation.

iii/ In ``Minimal Representation of Uniform Recurrence Equations'', by Bruno Gaujal, Alain Jean-Marie and Jean Mairesse (D16b-3), distributed equational simulation is relocated in the wider context of scheduling cyclic computations in an ``optimal'' manner. For instance, in the case of linear (max,+) systems, one of the quantities to be minimized is the dimension of the equivalent linear operator. This problem is discussed using models and algorithms of graph theory.

Contents of the Deliverable

D16b-1

Parallel and Distributed Simulation of Free Choice Petri Nets, by François Baccelli, Nathalie Furmento and Bruno Gaujal. This paper appears in the proceedings of PADS'95, Lake Placid, June 1995

D16b-2

Some Algebraic Considerations for Efficient Computations in Timed Petri Nets, by Bruno Gaujal. This paper will appear in the proceedings of HICSS-29, Hawaii, Jan 96.

D16b-3

Minimal Representation of Uniform Recurrence Equations, by Bruno Gaujal, Alain Jean-Marie and Jean Mairesse. This paper appears as INRIA Research Report #2568, June 1995.