Parallel shared-memory state-space exploration in stochastic modeling

Stochastic modeling forms the basis for analysis in many areas, including biological and economic systems, as well as the performance and reliability modeling of computers and communication networks. One common approach is the state-space-based technique, which, starting from a high-level model, uses depth-first search to generate both a description of every possible state of the model and the dynamics of the transitions between them. However, these state spaces, besides being very irregular in structure, are subject to a combinatorial explosion, and can thus become extremely large. In the interest therefore of utilizing both the large memory capacity and the greater computational performance of modern multiprocessors, we are interested in implementing parallel algorithms for the generation and solution of these problems. In this paper we describe the techniques we use to generate the state space of a stochastic Petri-net model using shared-memory multiprocessors. We describe some of the problems encountered and our solutions, in particular the use of modified B-trees as a data structure for the parallel search process. We present results obtained from experiments on two different shared-memory machines.