PERFORMANCE EVALUATION OF PARALLEL SYSTEMS BY USING UNBOUNDED GENERALIZED STOCHASTIC PETRI NETS

This paper presents methods of calculating efficiently the performance measures of parallel systems by using unbounded generalized stochastic Petri nets. One of the main limitations of the use of Petri nets for modeling and evaluating the performance of complex parallel systems is the explosion in the number of states to be analyzed. This is what occurs when unbounded places appear in the model. The state space of such nets is infinite, but it is possible to take advantage of the natural symmetries of the system to aggregate the states of the net and construct a finite graph of lumped states which can easily be analyzed. With the methods developed in this paper, the unbounded places introduce a complexity similar to that of safe places of the net. These methods can be used to evaluate models of open parallel systems in which unbounded places appear; systems which are k-bounded but are complex and have large values of k can also be evaluated in an approximate way by means of simpler unbounded models. From the steady-state solution of the model, it is possible to obtain automatically the performance measures of parallel systems represented by this type of nets, such as the time devoted to the execution of each task, the time during which each processor of the system is operating or the memory necessary for the execution of a job in a multiprocessor architecture.