Generalized stochastic Petri net (GSPN) models are used in order to analyze the expected performance of a class of multiple bus multiprocessor systems with shared resources. Exploiting the unusual simplicity of the state space of the Markov chains derived by firing the reachability graphs of the GSPNs, these models are shown to admit a product form solution, despite the presence of passive resources that places them outside the range of applicability of the BCMP theorem. This result is supported by the formal proof of the local balance property in the case of two-bus systems; moreover the local balance property was numerically proved to hold for systems comprising up to ten processors and five busses. Flow-equivalent expressions are derived for the cases of two and three busses using a state aggregation technique. This method is proved to dramatically reduce the computational complexity of the model solution as compared with the standard solution of the original Markov chain, thus making the exact analysis of very large systems both practical and inexpensive.

On the Product Form Solution of a Class of Multiple Bus Multiprocessor System Models

BALBO, Gianfranco;DONATELLI, Susanna
1984-01-01

Abstract

Generalized stochastic Petri net (GSPN) models are used in order to analyze the expected performance of a class of multiple bus multiprocessor systems with shared resources. Exploiting the unusual simplicity of the state space of the Markov chains derived by firing the reachability graphs of the GSPNs, these models are shown to admit a product form solution, despite the presence of passive resources that places them outside the range of applicability of the BCMP theorem. This result is supported by the formal proof of the local balance property in the case of two-bus systems; moreover the local balance property was numerically proved to hold for systems comprising up to ten processors and five busses. Flow-equivalent expressions are derived for the cases of two and three busses using a state aggregation technique. This method is proved to dramatically reduce the computational complexity of the model solution as compared with the standard solution of the original Markov chain, thus making the exact analysis of very large systems both practical and inexpensive.
1984
International Workshop on Modeling and Performance Evaluation of Parallel Systems
Grenoble, France
December 1984
Modeling and Performance Evaluation of Parallel Systems
IMAG
55
86
Generalized Stochastic Petri Nets; Markov chain; Multiprocessor system; multiple bus; Product form
M. Ajmone Marsan; G. Balbo; G. Chiola; S. Donatelli
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2318/26297
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact