Distributed Asynchronous Iterations
for Steady-State CTMC Analysis
Motivation
Steady state analysis of large CTMCs
is known to be very time and space consuming.
Beside sophisticated state space representations and
solution methods the use of parallel architectures has
recently attracted attention, particularly so in
the connection with heterogeneous workstation clusters
which are mainly available in practice.
Features
Generator matrix: Hierarchical Kronecker based representation, i.e. block-structured
Fixed point iteration: Two-stage iteration with
(a)synchronous outer iteration
obtained by block-Jacobi splitting and distributed inner iteration(s)
obtained by any desired splitting
Control of Iteration: steering parameter, e.g., number of inner iteration steps, degree asynchronism of outer iterations, initial load distribution etc; master process monitors progress of iteration
Parallel Setting: SPMD model, i.e., iteration vector is
distributed among workers, but every worker holds the complete generator matrix;
use of PVM, initial load distribution by heuristic graph partitioning techniques
Illustration Mathematical + Computational Model
Lehrstuhl Informatik IV, Universität Dortmund
© 26.09.2001