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 tensorproduct structured
matrix (with functions). The complexity of this operation is
O(N log N) as compared to the complexity of the regular
product N^{2}.
Optimization and use of the vector tensorproduct
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.
