Reduced Markov Models Of Parallel Programs With Replicated Processes
Markus Siegle · 1994
The behaviour of parallel programs with replicated processes is modelled by continuous time Markov chains. For high-level model description, we use stochastic automata networks. We are particularly interested in models of parallel programs which exhibit symmetries. Exact lumpability is exploited for reducing the model’s state space, thus making complex models of large real systems computationally tractable. Complexity analysis of a new reduction algorithm shows that the method can be applied efficiently in practice. Keywords: Parallel Programming, Markov Models, Lumpability, State Space Reduction.