Deliverable D8
Deliverable D8
In performance evaluation, one typically distinguishes between two types of approaches: analytical results and simulation. When the system under study is very large, both types of techniques run into obvious problems.
One of the techniques proposed for the simulation of very large systems is the use of parallel and distributed computers. Making simulations run on such environments prompts in turn many difficult problems, and has been an active field the last few years. Within the QMIPS project, one may quote the results reported in Chapter 4 of the proceedings of the Sophia-Antipolis workshop, and in deliverables D16a and D16b.
In order to use efficiently massively parallel computers, such as the Connection Machine, but also programmable circuits, one has to exhibit regularity in the computation process of the simulation. One also has to take into account the fact that such computers usually work in a synchronous manner.
In the course of the QMIPS project, the existence of evolution equation for certain classes of discrete event systems has been used for this purpose.
The paper ``Parallel and Distributed Simulation of Free Choice Petri Nets'', by François Baccelli, Nathalie Furmento and Bruno Gaujal (D8-1, also D16b-1), describes how evolution equations for Free Choice Petri Nets can be derived, structured and scheduled for parallel simulation. It is shown that parallel matrix operations, which were shown to be very efficient for event graphs (see deliverable D16-a) can still be applied to Free Choice Nets, and that dramatic improvements over sequential, event-driven simulation, can be obtained.
When using analytical techniques, handling systems of large dimensions can sometimes be done using asymptotic analysis.
The second paper of this deliverable, ``An asymptotic analysis of closed queueing networks with branching populations'', by N. Bayer, E.G. Coffman, Jr. and Y. Kogan, is concerned in analytical methods rather than simulation. Branching-Queueing networks have been proposed as a tool for analyzing the behavior of programs on distributed systems. In the present study, they apply to programs with a large number of subtasks but a low branching probability.