Stochastic Performance Prediction for Iterative Algorithms in Distributed Environments

✍ Scribed by Henri Casanova; Michael G. Thomason; Jack J. Dongarra

• Publisher: Elsevier Science
• Year: 1999
• Tongue: English
• Weight: 358 KB
• Volume: 58
• Category: Article
• ISSN: 0743-7315
• DOI: 10.1006/jpdc.1999.1543

✦ Synopsis

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.