Quantitative Modelling In Parallel Systems
Description
- Project Title:
- Quantitative Modelling In Parallel Systems
- Acronym:
- QMIPS
- Number:
- 7269
- Work Area:
- Algorithms for Parallelism & Efficiency
- Coordinator:
- INRIA-Sophia Antipolis
Route des Lucioles 2004
BP 93
F - 06902 SOPHIA ANTIPOLIS
- Coordinator Country:
- F
- Partners
- Université René Descartes LAA F
Universität Erlangen-Nürnberg D
Università di Torino I
CWI NL
Imperial College UK
University of Newcastle UK
- Contact Point:
- Dr. F. Baccelli
- Telephone:
- +33/93 65 77 69
- Fax:
- +33/93 65 77 65
- E-Mail:
- baccelli@martingale.inri.fr
- Keywords:
- performance evaluation, analytic methods, simulation, scheduling, load balancing
- Start Date:
- 1 October 92
- Duration:
- 36 months
- Status:
- running
- Abstract:
- QMIPS aims at describing, predicting and optimising the dynamic, time dependent behaviour of parallel and distributed systems using quantitative modelling. Qmips focuses on the foundation of a methodology for the performance evaluation of these systems based on general formalisms stemming from theoretical computer science such as queueing theory, timed process algebras and timed petri nets. All aspects of quantitative analysis are investigated: analytical methods, simulation, control etc.
AIMS
A key initial objective is the design of timed stochastic formalisms which are amenable to a mathematical treatment leading to efficiently implementable algorithms. This first objective is mainly of a theoretical nature; it involves fundamental research in theoretical computer science, stochastic processes, discrete event simulation, and various aspects of control.
The long term aim is the design of software prototypes admitting a description of the algorithms and the architecture as an input and providing the basic performance characteristics of the system as an output. The implications of these methods to scheduling and load balancing will only be investigated at the end of the project.
APPROACH AND METHODS
Work Package 1 is concerned with research and evaluation studies of the various formalisms.
Queueing models offer a semiformal representation of discrete event systems with stochastic timing together with (some) functional information. They are one of the most prominent classes of models because of their vast analytical tractability.
Structural analysis is a well known qualitative analysis technique for Petri nets. Research on this formalism primarily focuses on the stochastic case using colored nets and the (max,+) approach.
A salient intention of Process Algebras is the support of (functional) constructivity: there is a design methodology which systematically allows one to build complex systems from smaller ones. Research on this aspect bears on the timed case.
Work Package 2 focuses on various types of applied mathematics and discrete event simulation techniques that allow one to capture the quantitative behaviour of these systems, once they have been described in one of the formalisms of WP 1.
Work Package 3 concerns the design of modelling software based on the formalisms and the solution methods of WP 1 and WP 2 and allowing one to predict the performance and to optimise the execution of given parallel algorithms executing on various architectures.
PROGRESS AND RESULTS
CWI
Analysis of a class of two-dimensional random walks on the lattice and of tandem queues for modelling a sequence of multiplexers. Methodological contributions on stochastic scheduling using MDP.
EHE
Analytical results on G-networks. which represent adequately semaphores, or on-line work assignment, in distributed environments. Load balancing algorithms based on adaptive control techniques.
IMP
Development of a probabilistic, timed CCS which provides a formalism for discrete event simulation with a rigorous semantics of the type already defined for standard CCS. Collaboration with EHE on G-networks and with INR on cache coherency.
INR
New stability properties of general Petri networks. Work initiated on a performance modelling environment based on several of the formalisms used by QMIPS members. New results on parallel simulation. Collaboration with CWI on product forms in Petri nets.
UER
Elaboration of the modularly composed multiprocessor example for the comparison of formalisms. Definition of an Extended Markovian Process Algebra (EMPA: Exponential and Immediate Transitions) and elaboration of SOS (Structural Operational Semantics).
UNE
Development of a spectral expansion method for the solution of Markov processes whose state space is a two-dimensional semi-infinite strip. Work on the reliability of multiprocessor systems.
UTO/ZAR
Generalisation to P/T Petri net structures of the linear programming technique. Preliminary results for symmetric coloured nets. Application of Courtois-Semal method to SWNs. New approximation algorithms and simulation methods for TPNs.
POTENTIAL
Most of the partners already have extensive industrial collaboration in the field of performance evaluation. Thus, the project will also serve industrial groups that use performance to keep up with the recent initiatives in this direction in the US. We will transfer to industry methods of performance analysis in general, and novel techniques developed within QMIPS in particular. The solution methods developed will lead to readily usable algorithms and to software prototypes. In particular, WP2 will result in an improved version of GREATSPN and on the realisation of a new prototype for the simulation and the analysis of certain stochastic Petri-nets called MAGMAS, and the completion of WP 3. will result in an enriched version of the software tool ARCHISSIME, based on the formalism of task graphs.
INFORMATION DISSEMINATION ACTIVITIES
The first QMIPS Workshop, on Stochastic Petri Nets, was held in Sophia-Antipolis on November 11-13, 1992. The proceedings are available as a Qmips-INRIA document.
The second QMIPS Workshop, on Model Construction, was held in Erlangen on March 17-20, 1993; its proceedings will be published as a Qmips-IMMD document.
Sven Müßig, last update 07-nov-1995. Your feedback is welcome.