Stochastic Automata Networks (SAN)

The use of Stochastic Automata Networks (SANs) is becoming increasingly important in performance modelling issues related to parallel and distributed computer systems. As such models become increasingly complex, so also does the complexity of the modelling process. Parallel and distributed systems are often viewed as collections of components that operate more or less independently, requiring only infrequent interaction such as synchronizing their actions, or operating at different rates depending on the state of parts of the overall system. This is exactly the viewpoint adopted by SANs. The components are modelled as individual stochastic automata that interact with each other. Furthermore, the state space explosion problem associated with Markov chain models is mitigated by the fact that the state transition matrix is not stored, nor even generated. Instead, it is represented by a number of much smaller matrices, one for each of the stochastic automata that constitute the system, and from these all relevent information may be determined without explicitly forming the global matrix. The implication is that a considerable saving in memory is effected by storing the matrix in this fashion. This saving is even enforced by the use of functions (of the current global state) as transition rates.

Generalized Tensor Algebra

We have proposed an extension of the regular tensor (or Kronecker) operators for matrices. This extension allows to use functions (of the current state of the SAN) as entries of the matrices. It has been shown that certain algebraic properties can be extended from the classical theory. These properties are used to design an efficient algorithm to compute the multiplication of a vector with a tensor-product structured matrix (with functions). The complexity of this operation is O(N log N) as compared to the complexity of the regular product N².

Optimization and use of the vector tensor-product structured matrix

This algorithm can be optimized (special treatment of the diagonal, reordering of automata according to function profile, grouping of automata). As far as computation time is concerned, since the numerical methods used are iterative, it is important to keep both the number of iterations and the amount of computation per iteration to a minimum. The number of iterations needed to compute the solution to a required accuracy depends on the method chosen. It was shown how projection methods such as Arnoldi and GMRES could be used to substantially reduce the number of iterations needed when compared with the basic power method. Additionally, some results were also given concerning the development of preconditioning strategies that may be used to speed up the iterative process.