Work Area: Algorithms for Parallelism and Efficiency
Keywords performance evaluation, analytic methods, simulation, scheduling, load balancing
Start Date: 1 October 92 / Duration: 36 months / Status: running
[ participants / contact ]
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.
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.
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.
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.
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.
INRIA-Sophia Antipolis - F
Route des Lucioles 2004
F - 06902 SOPHIA ANTIPOLIS
Université René Descartes LAA - F
Universität Erlangen-Nürnberg - D
Università di Torino - I
CWI - NL
Imperial College - UK
University of Newcastle - UK
Dr. F. Baccelli
tel +33/93 65 77 69
fax +33/93 65 77 65
QMIPS - 7269, August 1994
please address enquiries to the ESPRIT Information Desk
html version of synopsis by Nick Cook