State space construction and steady-state solution of GSPNs on a shared-memory multiprocessor
- 22 November 2002
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 112-121
- https://doi.org/10.1109/pnpm.1997.595542
Abstract
A common approach for the quantitative analysis of a generalized stochastic Petri net (GSPN) is to generate its entire state space and then solve the corresponding continuous-time Markov chain (CTMC) numerically. This analysis often suffers from two major problems: the state space explosion and the stiffness of the CTMC. In this paper we present parallel algorithms for shared-memory machines that attempt to alleviate both of these difficulties: the large main memory capacity of a multiprocessor can be utilized and long computation times are reduced by efficient parallelization. The algorithms comprise both CTMC construction and numerical steady-state solution. We give experimental results obtained with a Convex SPP1600 shared-memory multiprocessor that show the behavior of the algorithms and the parallel speedups obtained.Keywords
This publication has 15 references indexed in Scilit:
- On the construction of abstract GSPNs: an exercise in modelingPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- On the success of stochastic Petri netsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Performance evaluation of dynamic priority operating systemsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- A multi-level solution algorithm for steady-state Markov chainsPublished by Association for Computing Machinery (ACM) ,1994
- On the solution of GSPN reward modelsPerformance Evaluation, 1991
- The effect of execution policies on the semantics and analysis of stochastic Petri netsIEEE Transactions on Software Engineering, 1989
- On the product-form solution of a class of multiple-bus multiprocessor system modelsJournal of Systems and Software, 1986
- Ubiquitous B-TreeACM Computing Surveys, 1979
- A dichromatic framework for balanced treesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1978
- Concurrency of operations on B-treesActa Informatica, 1977