Research activity in 1994
The main activity of the research group on modelling and analysis of parallel
and distributedsystems has been the development of a methodology for the
analysis of computing systems using probabilistic models such as Queueing
Networks (QN) and Stochastic Petri Nets (SPN).
The original work conducted by the group has been concerned with the
development of computationally efficient algorithms for the solution of product
form queueing networks used for the study of the efficiency of time sharing
systems. These algorithms have been later extended to allow the approximate
analysis of non-product form models.
Since 1982 the group has been involved with the definition of the Generalized
Stochastic Petri net (GSPN) formalism, with the development of its analysis
tools and with its application to multiprocessor performance evaluation.
The earlier work focused on the stochastic aspect of the formalism, showing how
GSPNs could be developed to specify Markov and semi-Markov models of parallel
and distributed systems with an emphasis on the advantage of using a graphical
formalism to represent important aspect of these systems.
Subsequently, a greater attention has been devoted to the structural properties
of Petri net models as a way to integrate in the methodology validation and
evaluation aspects and to improve the analysis algorithms also by computing
fast performance bounds.The need of using the formalism to study real-life
problems led to the development of the Well Formed Stocahstic Petri Nets (SWN)
that directly account for the symmetries of the model reducing the complexity
of their state space analysis.
An important practical experience in the use of QN and GSPN models for the
analysis of important systems has been gained during the first CNR-PFI project
(Progetto Finalizzato Informatica of the Italian National Research Council)
when a prototype multiprocessor architecture developed within the project was
evaluated using these techniques.A similar experience was also carried on
within the ESPRIT I project N. 967 "PADMAVATI: Parallel Associative Development
Machine as a Vehicle for Artificial Intelligence" where a Transputer based
parallel architecture was studied in cooperation with CSELT (the research
laboratories of the Italian telephone company) from the point of view of the
impact of its multi-stage interconnection network. More recently, the GSPN
formalism has been used within the second CNR-PFI project to model concurrent
software leading to the development of a parallel programming environment where
the compiler for an extended version of the C language enhanced with
concurrency primitives, produces a GSPN representation of the concurrent
structure of each compiled program. This net may then be used for a preliminary
evaluation of the program and for obtaining indications on how to allocate it
on a given parallel architecture. Recent work has also been performed for the
analysis of massively parallel and heterogeneous architectures, as well as of
polling protocols in communication networks.
The need for providing system designers with validation and evaluation tools
has been one of the main topics of the ESPRIT II project N. 2143 "IMSE: The
Integrated Modelling Support Environment" where the research group developed
the integration of GSPN and QN analyzers. The importance of studying different
modelling formalisms and of extending their solution techniques is one of the
main research topics of the ESPRIT III BRA project N.7269 "QMIPS: Quantitative
Modelling in Parallel Systems" where the group represents the University of
Torino in a consortium with seven other European universities.
The most recent activity of the group relates to the problem of the complexity
of the analysis of large models. Several research directions are pursued
yielding the development of product form algorithms for a restricted class of
SPN, of parallel algorithms for the analysis of models deriving from the
composition of simple GSPNs, of algorithms that apply lumpability criteria to
colored stochastic Petri net models by exploiting their symmetric behaviour,
and of approximation methods for the analysis of the Markov chains associated
with GSPN models when they exhibit a quasi-lumpability property. The need for a
compositional approach in the development of models of real systems has also
led to the study of the relationships between Petri net based formalisms and
timed process algebras that have been recently proposed in the literature.
Most of this work has been conducted in cooperation with research groups of the
Computer Science Department of the University of Iowa (USA), of the ETSII of
the Universidad de Zaragoza (Spain), of the Laboratoire MASI of the University
of Paris VI (France), of the Computer Science Department of the University of
California at Los Angeles (USA), of the Dipartimento di Elettronica e
Telecomunicazioni del Politecnico di Torino, and of the Dipartimento di
Informatica e Sistemistica of the Universita' di Napoli.
The group sponsored and participated in the organization of several
international workshops and conferences among which the 5-th International
Conference on Modelling Techniques and Tools for Computer Performance
Evaluation and the16-th International Conference on Application and
Theory of Petri Nets.
The experience gained by the members of the group has led to the production of
three books on Performance Evaluation techniques: "Computational Algorithms for
Closed Queueing Networks", by Steven C. Bruell and Gianfranco Balbo - North
Holland (1980), "Performance Models of Multiprocessor Systems", by Marco Ajmone
Marsan, Gianfranco Balbo, and Gianni Conte - MIT Press (1986), and "Modelling
with Generalized Stochastic Petri Nets" by Marco Ajmone Marsan, Gianfranco
Balbo, Gianni Conte, Susanna Donatelli, and Giuliana Franceschinis - John Wiley
(1995), and to the publication of more than one hundred papers in international
journals and proceedings of international conferences.
