Title :
Parallel randomization for large structured Markov chains
Author_Institution :
Informatik IV, Dortmund Univ., Germany
Abstract :
Multiprocessor architectures with few but powerful processors are gaining more and more popularity. We describe a parallel iterative algorithm to perform randomization for a continuous time Markov chain with a Kronecker representation on a shared memory architecture. The Kronecker representation is modified for a parallel matrix-vector multiplication with a fast multiplication scheme and no write conflicts on iteration vectors. The proposed technique is applied on a model of a workstation cluster for dependability analysis, corresponding computations are performed on two multiprocessor architectures, a Sun enterprise and a SGI Origin 2000 to measure its performance.
Keywords :
Markov processes; iterative methods; matrix algebra; multi-threading; parallel algorithms; performance evaluation; randomised algorithms; shared memory systems; vectors; workstation clusters; Kronecker representation; SGI Origin 2000; Sun enterprise; continuous time Markov chain; dependability analysis; fast multiplication scheme; large structured Markov chains; multiprocessor architectures; parallel iterative algorithm; parallel matrix-vector multiplication; parallel randomization; shared memory architecture; workstation cluster; Concurrent computing; Jacobian matrices; Memory architecture; Numerical analysis; Performance analysis; Sparse matrices; State-space methods; Steady-state; Stochastic processes; Workstations;
Conference_Titel :
Dependable Systems and Networks, 2002. DSN 2002. Proceedings. International Conference on
Print_ISBN :
0-7695-1101-5
DOI :
10.1109/DSN.2002.1029011
