People

Research activity in 1997

During 1997 the activity of the research group working on "Methods and Tools for the Analysis and Development of Performance Oriented Computer Systems" has been focused on the following topics:

1. Stochastic Petri Nets (SPN) have been used to study several performance evaluation problems in the fields of concurrent programming, parallel computing systems, and telecommunication systems. In particular, the following topics have been addressed:

2. The increasing use of SPN models in different fields of science and industry has brought up the need of extending the formalism so that activities with generally distributed durations can be represented without loosing the possibility of analytically solving the above models, and of dealing with extremely large state spaces. In this context, the following topics have been investigated:

1. The formalism of GSPN has been extended with transitions characterized by generally distributed firing times. New techniques to study the transient and the steady state behavior were developed. Particular attention was devoted to the complexity of the algorithms, trying to avoid the state space explosion using the formalism of Kronecker algebra.
2. The research activity on the formalization of non-Markovian Stochastic Petri Nets has been continued. The non-Markovian models, appeared so far in the literature, were based on the assignment of an individual memory policy to each timed transition. The activity of our group has been devoted to introduce interlaced, or state dependent, memory policies, where the memory of a transition can be modified by the occurrence of some condition on the PN. Adhering to the spirit of the graphical PN language, the investigated memory policies have been represented as new primitives in the form of suitable "memory resetting" arcs.
3. Various models of system with performance that degrades as time passes have been studied. Preliminary results have been applied to the estimation of the otimal calibration interval of measuring instruments devoted to the control and the quality assessment of an industrial process, in conjunction with the MEMC Electronic Materials Industry of Novara (Italy). Future extensions of the present activity are planned for the modeling of smoothly degrading software systems.
4. Additional work has been done in the field of the structured solution methods for SPN, where tensor algebra is used to devise solution methods of reduced temporal and space complexity. In particular we have enlarged the set of nets to which the method can be applied, and we have studied its complexity in comparison with traditional methods. Tensor based methods have also been applied to the state space construction and subsequent solution of SPN with Phase-type distributions.

2. The research activity on the relationships between the SPN and the Queueing Networks (QN) formalism, started in past years, is continued investigating the following topics:

1. The solution of many SPN and Queueing networks models is computationally effective when the model is structured in such a way that its solution can be expressed as a product of relatively simple terms that depend on the features of each individual component. Product form solution techniques have been studied in the context of both formalisms, with emphasis on the following issues:

• Definition of algorithms for the computation of performance indices. One of these algorithms, the Mean Value Analysis (MVA), developed for the SPN formalism, has been used to devise iterative methods that allow to compute approximate performance measures for model that do not satisfy the product form solution constraints. These approximate methods have a wide application domain as they can been applied to ``real systems'' that seldom have product form solutions. In particular, using the Approximate MVA, a method for the computation of the performance measures for mobile communication networks has been derived.

• The study of the asymptotic properties of Product Form Queueing Networks (PFQN) is continued addressing the case of multi-class PFQNs in which different bottlenecks can be identified when the model is analyzed from the point of view of the individual classes of entities that visit the nodes of the model. The analysis has been carried-on under the assumption that the proportion of entities of the different classes (called population mix) is kept constant while their total number grows to infinity. Asymptotic formulas are obtained for the throughputs, utilizations, and response times of these types of networks. Computationally simple expressions have been derived that allow to identify the nodes of the network that are bottlenecks for the behaviour of the model when its load is characterized by a given population mix. Algorithms are provided for identifying how the bottleneck migrates from one station to another when the population mix changes. Calling switching point the population mix that characterize the change of state of a network node (from bottleneck to non-bottleneck and viceversa), results have been obtained which show that well know approximation methods yield poor results when used to evaluate the performance of networks operating with population mixes that are close to the switching points, while are quite robust in the other cases.

1. The relationships among stochastic Petri nets and Queueing networks with finite capacity resources (FC-QNs) have been studied. In particular, the SPN formalism is used to obtain a formal specification of the basic blocking mechanisms that arise in the FC-QNs.

2. Design techniques that allow the development of performance efficient parallel applications have been devised and applied to real world case studies. In particular, the following topics have been investigated:

1. The design and implementation of a parallel algorithm for concept induction, able to semi-automatically adapt its characteristics to those of the computing platform used for its execution, has been carried out. In order to be suitable for a wide class of parallel executing platforms, ranging from classical parallel computing systems to cluster of workstations connected by a local area network, appropriate load balancing and latency toleration techniques have been devised and implemented. Typical applications of this sytstem include data-mining in large databases and classification problems.
2. Techniques for effective performance management of distributed applications have been studied. In particular, a new approach called pro-active performance management has been defined. The approach is based on the use of forecast techniques that allow to predict the instant in time when a given resource management action should be carried out, rather than waiting that the system reaches a given (possibly undesired) state, as it is done with classical reactive approaches. As a consequence of its greater "timeliness", our approach results in a more efficient management. Pro-active management strategies can be applied to a broad class of problems, including load balancing and protocols for distributed simulation.

1. Realization of a training course in open learning on "Safety Engineering" for industrial technicians, as a multimedia module distributed on CD-ROM with title "Reliability Methods for Safety Engineering". This work has been done within the European ADAPT Project (IC/0018-0019/A) "Sicuro".
2. Implementation, in cooperation with the ``Istituto di Informatica e Telecomunicazioni'' of the Universita' di Catania, of the WEBSPN tool, which allows the analysis of non-exponential SPN models.
3. Completion of version 2.0 of the GreatSPN software package, a tool (with a graphical interface) that allows to edit and analyze Stochastic Petri Net models. The tool has been distributed in the last ten years to more than one hundred universities and research centers all over the world.
4. Participation to the works of ISO/IEC JTC1/SC7-WG11 on the project 7.9.13 for the standardization of the High Level Petri Net Formalism.

During 1997 the group has been involved in the following national and international research projects:

G. Balbo:

• Chairman of the Scientific Program Committee of the 18-th Intern. Conference on Application and Theory of Petri Nets ICATPN'97, Toulouse, France, June 1997.
• Member of the Scientific Program Committees of the 7-th Seventh Intern. Workshop on Petri Nets and Performance Models, St. Malo, France, June 1997 and of the 9-th Intern. Conference on Modelling Techniques and Tools for Computer Performance Evaluation, St. Malo, France, June 1997.
• Member of the Editorial Board of the International Journal of Computer Systems Science and Engineering, CRL Publishing Ltd, Leics, U.K.
• Member of the IFIP Working Group 7.3 "Information Processing System Modeling, Measurement and Evaluation".
• Referee for the following international Journals: Advances in Petri Nets, Electronic Letters, European Journal of Operation Research, Formal Methods in System Design, IEE Proceedings, IEEE Transactions on Computers, Performance Evaluation.
• Referee for the Ph.D. Dissertations of Dr. Marenzoni (University of Parma) and Dr. Basagni (University of Milano) and for the Master Thesis of Ing. Faggi (CSELT)

A. Bobbio:

• Co-chairman for the 7-th International Workshop on Petri Nets and Performance Models (PNPM97), Saint Malo, France, June 1997
• Referee for the following international Journals and Conferences: IEEE Transaction on Computers, IEEE Transactions on Software Engineering, IEEE Transactions on Reliability, EUROMICRO Journal of Systems Architecture, IEEE Fault-tolerant Computing Symposiumn 1997, International Workshop on Petri Nets and Performance Models 1997, International Conference on Application and Theory of Petri Nets 1997.

M. Sereno:

• Member of the Scientific Program Committee of the 7-th International Workshop on Petri Nets and Performance Models 1997, St. Malo, France, June 1997
• Referee for the following international Journals and Conferences: IEEE Transactions on Software Engineering, Performance Evaluation, Telecommunication Systems (North Holland), Computer Systems -- Science and Engineering (CRL Publishing Ltd.), The Computer Journal.

S. Donatelli:

• Member of the Scientific Program Committe of the 7th International Workshop on Petri Nets Performance Models, St. Malo, France, June 1997.
• Referee for the following international Journals and Conferences: International Conference on Application and Theory of Petri Nets 1997, International Workshop on Petri Nets and Performance Models 1997, Journal of the ACM, IEEE Transactions of Software Engineering, Theoretical Computer Science, International Peformance and Dependability Symposium, ACM SIGMETRICS

G. Franceschinis:

• Member of the Scientific Program Committe of the 7th International Workshop on Petri Nets Performance Models, St. Malo, France, June 1997.
• Referee for the following international Journals and Conferences: 7^th International Workshop on Petri Nets and Performance Models, 9th International Conference on Modelling Techniques and Tools for Computer Performance Evaluation, 18th International Conference on Application and Theory of Petri Nets, 2^nd International Workshop on Software Engineering for Parallel Distributed Systems (PDSE97), IEEE Transactions on Software Engineering, Lecture Notes in Computer Science (Special Issue of Advances n Petri Nets on Object-Oriented Programming and Models of Concurrency.
• External examiner for Isabel Rojas-Mujica's PhD at the University of Edinburgh; thesis title: "Compositional construction and analysis of Petri net systems".

C. Anglano:

• Member of the Scientific Program Committee of the 1997 Heterogeneous Computing Workshop, Geneva, Switzeralnd, April 1997
• Member of the Scientific Program Committee of the International Conference on Applied Modelling and Simulation, Banff, Canada, August 1997
• Referee for the following international Journals and Conferences: IEEE Transactions on Parallel and Distributed Systems, EUROMICRO Journal of Systems Architecture, EUROMICRO Workshop on Parallel and Distributed Processing, International Conference on Application and Theory of Petri Nets, EUROPAR '97, ISMIS '97

M. Scarpa:

• Referee for the following international Conferences: International Workshop on Petri Nets and Performance Models (PNPM97), International Conference on Applied Modelling and Simulation

In addition to the presentations given to conferences and workshops of the papers listed in the bibliography, the members of the group partecipated to the following events:

G. Balbo:

• Session chairman at the 7-thSeventh Intern. Workshop on Petri Nets and Performance Models, St. Malo, France, June 1997.
• Session chairman at the 9-th Intern. Conference on Modelling Techniques and Tools for Computer Performance Evaluation, St. Malo, France, June 1997.
• Introductory talk at the18-th Intern. Conference on Application and Theory of Petri Nets, Toulouse, France, June 1997.

A. Bobbio:

• Tutorial presented in cooperation with Miklos Telek (Technical University of Budapest) at the the 7-th International Workshop on Petri Nets and Performance Models 1997
• Course on "Reliability methods and Techniques" taught at the Master course on "Safety Engineering" organized by COREP
• Course on "Reliability of components and systems" taught at the Master course on "Environmental Engineering" organized by COREP

S. Donatelli:

• Tutorial presented at the 7th International Workshop on Petri Nets and Performance Models, St. Malo, France, June 3-6, 1997, together with Prof. Gianfranco Ciardo, of the College of Williams and Mary, Williamsburg, Virginia (USA), entitled ``Kronecker operators for the description and solution of large Markov models generated by Stochastic Petri Nets''.
• Tutorial on Stochastic Petri Nets at the ``introductory tutorial'' of the 18th International Conference on Application and Theory of Petri Nets, Toulouse, June 1997.