Abstract
The parallelization of iterative algorithms is an important issue for efficient solution of large numerical problems. Several theoretical results concerning sufficient conditions for, and speed of, convergence of parallel iterative algorithms are available. However, those results usually do not take into account the processor workloads and network communications at the application level. The approach in this paper develops a Markov chain based on random variables which describe aspects of the multiuser, distributed-memory environment and the phases of the algorithm. The performance characterization addresses stochastic characteristics of the algorithmic execution time such as mean values and standard deviations. We present simulation results as well as experimental results over different time periods. The results provide information about the impact of distributed environment and implementation style on long-run, expected execution time characteristics.
Original language | English |
---|---|
Pages (from-to) | 68-91 |
Number of pages | 24 |
Journal | Journal of Parallel and Distributed Computing |
Volume | 58 |
Issue number | 1 |
DOIs | |
State | Published - Jul 1999 |
Keywords
- Convergence; distributed-memory; iterative algorithm; Markov chain; multiuser; parallel; performance prediction; stochastic modeling