Parallel Implementation of Uniformization to Compute the Transient Solution of Stochastic Automata Networks

Abstract

Analysis of Stochastic Automata Networks (SAN) is a well
established approach for modeling the behaviour of
computing networks and systems, particularly
parallel systems. The transient study of performance measures
leads us to time and space complexity
problems as well as error control of the numerical results.
The SAN theory presents some advantages such as avoiding to build
the entire infinitesimal generator and facing the time complexity
problem thanks to the tensor algebra properties.

The aim of this study is the computation of the
transient state probability vector of SAN models.
We first select and modify the (stable) uniformization
method in order to compute that vector in a sequential way. We also
propose a new efficient algorithm to compute a product of a vector by a tensor
sum of matrices.
Then, we study the contribution of parallelism in front of
the increasing execution time for stiff models by developing
a parallel algorithm of the uniformization.
The latter algorithm is efficient and allows to
process, within a fair computing time, systems with
more than one million states and large mission time values.