Title :
Load balancing and parallel implementation of iterative algorithms for row-continuous Markov chains
Author :
Colajanni, M. ; Angelaccio, M.
Author_Institution :
Rome Univ., Italy
Abstract :
Presents the first parallel algorithms for solving row-continuous or generalized birth-death (GBD) Markov chains on distributed memory MIMD multiprocessors. These systems are characterized by very large transition probability matrices, decomposable in heterogeneous tridiagonal blocks. The parallelization of three aggregation/disaggregation iterative methods is carried out by a unique framework that keeps into account the special matrix structure. Great effort has been also devoted to define a general algorithm for approximating the optimum workload. Various computational experiments show that Vantilborgh´s (1985) method is the fastest of the three algorithms on any data set dimension
Keywords :
Markov processes; distributed memory systems; iterative methods; mathematics computing; matrix algebra; parallel algorithms; resource allocation; aggregation/disaggregation iterative methods; data set dimension; distributed memory MIMD multiprocessors; generalized birth-death Markov chains; heterogeneous tridiagonal blocks; iterative algorithms; load balancing; optimum workload; parallel algorithms; row-continuous Markov chains; transition probability matrices; Biological system modeling; Gaussian processes; Iterative algorithms; Iterative methods; Load management; Matrix decomposition; Power system modeling; Steady-state; Stochastic processes; Vectors;
Conference_Titel :
Scalable High Performance Computing Conference, 1992. SHPCC-92, Proceedings.
Conference_Location :
Williamsburg, VA
Print_ISBN :
0-8186-2775-1
DOI :
10.1109/SHPCC.1992.232656
