Deliverable D16a
Distributed and Parallel Simulation of Networks
Several new techniques of parallel simulation of
discrete event systems have been proposed in the
last ten years or so. One of them is based
on the distribution of the event table; other
and more recent techniques based on the
parallel prefix algorithm have been proposed
for queues. The main contributions of the Qmips
project within this framework are summarized below
The paper ``Parallel simulation of
Stochastic Equations Using Recursive Equations'', by the INRIA
group is contained in Chapter 4 of the proceedings
of the Sophia Antipolis Workshop (D16a-1). This paper
proposes a new technique for the parallel
simulation of very large systems. This technique
is based on a canonical representation of
the recursive equations for
stochastic event graphs proposed by F. Baccelli in 1992.
It is amenable to a SIMD implementation.
A prototype called MAGMAS has been designed on
the INRIA Sophia-Antipolis Connection Machine.
Run times three to four orders of magnitude
less than those of conventional simulation running on
a powerful workstation have been
exhibited.
This paper was recently published in ACM TOMACS.
Most of the work presented in this paper predates
the starting of the project.
The new theoretical contributions
on this type of simulations bear on its optimization.
In the paper ``Marking Optimization
and Parallelism of Marked Graphs'', also by the INRIA
group, (D16a-2), it is shown that
the speed-up can be optimized via a good choice
of the initial marking. Algorithms giving the
optimal marking are provided. It is also shown
that the obtained maximal speed-up
is a function of a measure of the
intrinsic parallelism of the net.
Concerning the development of the MAGMAS prototype,
new features include:
- Graphical interfaces;
- Algorithms for marking optimization;
- Statistical estimators.
The paper ``Distributed Simulation of Timed Petri
Nets Exploiting the Net Structure to Obtain Efficiency'', by
the Torino Group (see D12-1, Chapter 3 of the Sophia-Antipolis Workshop)
describes an implementation of both the
conservative and the optimistic approaches of distributed
event table simulation. The speedup optimization uses
a partitioning technique which is based on a structural analysis
of the net. Implementations have been undertaken
for the Intel iPSC/860 hypercube, the Sequent Balance, and
networks of Transputers.
Recent developments on the matter bear on the software
prototype and its interfacing with GreatSPN.
- D16a-1
- Chapter 4 of the Proceedings of the Sophia-Antipolis Workshop
on Stochastic Petri Nets.
``Parallel
simulation of Stochastic Equations Using Recursive Equations'', by
F. Baccelli and M. Canales.
``Distributed Simulation of Timed Petri
Nets Exploiting the Net Structure to Obtain Efficiency'', by
G. Chiola and A. Ferscha.
- D16a-2
- Marking Optimization and Parallelism of Marked Graphs, Miguel
Canales and Bruno Gaujal, INRIA Report RR 2049, presented at the
Torino Qmips Workshop on Solution Methods, 1993.
Page Web by
Alain Jean-Marie
(Alain.Jean-Marie@sophia.inria.fr)
Last Modified: 26 September 1995.