`On-the-fly' solution techniques for stochastic Petri nets and extensions

Daniel D. Deavours, William H. Sanders

Research output: Contribution to conferencePaper

Abstract

Use of a high-level modeling representation, such as stochastic Petri nets, frequently results in a very large state space. In this paper, we propose new methods that can tolerate such large state spaces and that do not require any special structure in the model. First, we develop methods that generate rows and columns of the state transition-rate-matrix on-the-fly, eliminating the need to explicitly store the matrix at all. Next, we introduce a new iterative solution method, called modified adaptive Gauss-Seidel, that exhibits locality in its use of data from the state transition-rate-matrix. This permits the caching of portions of the matrix, hence reducing the solution time. Finally, we develop a new memory- and computationally-efficient technique for Gauss-Seidel-based solvers that avoids the need for generating rows of A in order to solve Ax = b. Taken together, these new results show that one can solve very large SPN, GSPN, SRN, and SAN models without any special structure.

Original languageEnglish (US)
Pages132-141
Number of pages10
StatePublished - Jan 1 1997
EventProceedings of the 1997 7th International Workshop on Petri Nets and Performance Models - Saint Malo, Fr
Duration: Jun 3 1997Jun 6 1997

Other

OtherProceedings of the 1997 7th International Workshop on Petri Nets and Performance Models
CitySaint Malo, Fr
Period6/3/976/6/97

Fingerprint

Stochastic Petri Nets
Petri nets
Gauss-Seidel
State Transition
State Space
Caching
Iterative Solution
Locality
Data storage equipment
Modeling
Model

ASJC Scopus subject areas

  • Applied Mathematics
  • Modeling and Simulation

Cite this

Deavours, D. D., & Sanders, W. H. (1997). `On-the-fly' solution techniques for stochastic Petri nets and extensions. 132-141. Paper presented at Proceedings of the 1997 7th International Workshop on Petri Nets and Performance Models, Saint Malo, Fr, .

`On-the-fly' solution techniques for stochastic Petri nets and extensions. / Deavours, Daniel D.; Sanders, William H.

1997. 132-141 Paper presented at Proceedings of the 1997 7th International Workshop on Petri Nets and Performance Models, Saint Malo, Fr, .

Research output: Contribution to conferencePaper

Deavours, DD & Sanders, WH 1997, '`On-the-fly' solution techniques for stochastic Petri nets and extensions', Paper presented at Proceedings of the 1997 7th International Workshop on Petri Nets and Performance Models, Saint Malo, Fr, 6/3/97 - 6/6/97 pp. 132-141.
Deavours DD, Sanders WH. `On-the-fly' solution techniques for stochastic Petri nets and extensions. 1997. Paper presented at Proceedings of the 1997 7th International Workshop on Petri Nets and Performance Models, Saint Malo, Fr, .
Deavours, Daniel D. ; Sanders, William H. / `On-the-fly' solution techniques for stochastic Petri nets and extensions. Paper presented at Proceedings of the 1997 7th International Workshop on Petri Nets and Performance Models, Saint Malo, Fr, .10 p.
@conference{799249cd0edd40309159b0f1ac1ad4ac,
title = "`On-the-fly' solution techniques for stochastic Petri nets and extensions",
abstract = "Use of a high-level modeling representation, such as stochastic Petri nets, frequently results in a very large state space. In this paper, we propose new methods that can tolerate such large state spaces and that do not require any special structure in the model. First, we develop methods that generate rows and columns of the state transition-rate-matrix on-the-fly, eliminating the need to explicitly store the matrix at all. Next, we introduce a new iterative solution method, called modified adaptive Gauss-Seidel, that exhibits locality in its use of data from the state transition-rate-matrix. This permits the caching of portions of the matrix, hence reducing the solution time. Finally, we develop a new memory- and computationally-efficient technique for Gauss-Seidel-based solvers that avoids the need for generating rows of A in order to solve Ax = b. Taken together, these new results show that one can solve very large SPN, GSPN, SRN, and SAN models without any special structure.",
author = "Deavours, {Daniel D.} and Sanders, {William H.}",
year = "1997",
month = "1",
day = "1",
language = "English (US)",
pages = "132--141",
note = "Proceedings of the 1997 7th International Workshop on Petri Nets and Performance Models ; Conference date: 03-06-1997 Through 06-06-1997",

}

TY - CONF

T1 - `On-the-fly' solution techniques for stochastic Petri nets and extensions

AU - Deavours, Daniel D.

AU - Sanders, William H.

PY - 1997/1/1

Y1 - 1997/1/1

N2 - Use of a high-level modeling representation, such as stochastic Petri nets, frequently results in a very large state space. In this paper, we propose new methods that can tolerate such large state spaces and that do not require any special structure in the model. First, we develop methods that generate rows and columns of the state transition-rate-matrix on-the-fly, eliminating the need to explicitly store the matrix at all. Next, we introduce a new iterative solution method, called modified adaptive Gauss-Seidel, that exhibits locality in its use of data from the state transition-rate-matrix. This permits the caching of portions of the matrix, hence reducing the solution time. Finally, we develop a new memory- and computationally-efficient technique for Gauss-Seidel-based solvers that avoids the need for generating rows of A in order to solve Ax = b. Taken together, these new results show that one can solve very large SPN, GSPN, SRN, and SAN models without any special structure.

AB - Use of a high-level modeling representation, such as stochastic Petri nets, frequently results in a very large state space. In this paper, we propose new methods that can tolerate such large state spaces and that do not require any special structure in the model. First, we develop methods that generate rows and columns of the state transition-rate-matrix on-the-fly, eliminating the need to explicitly store the matrix at all. Next, we introduce a new iterative solution method, called modified adaptive Gauss-Seidel, that exhibits locality in its use of data from the state transition-rate-matrix. This permits the caching of portions of the matrix, hence reducing the solution time. Finally, we develop a new memory- and computationally-efficient technique for Gauss-Seidel-based solvers that avoids the need for generating rows of A in order to solve Ax = b. Taken together, these new results show that one can solve very large SPN, GSPN, SRN, and SAN models without any special structure.

UR - http://www.scopus.com/inward/record.url?scp=0030677731&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0030677731&partnerID=8YFLogxK

M3 - Paper

AN - SCOPUS:0030677731

SP - 132

EP - 141

ER -