Stochastic Performance Prediction for Iterative Algorithms in Distributed Environments

Henri Casanova, Michael G. Thomason, Jack J. Dongarra

Research output: Contribution to journalArticlepeer-review

6 Scopus citations

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 languageEnglish
Pages (from-to)68-91
Number of pages24
JournalJournal of Parallel and Distributed Computing
Volume58
Issue number1
DOIs
StatePublished - Jul 1999

Keywords

  • Convergence; distributed-memory; iterative algorithm; Markov chain; multiuser; parallel; performance prediction; stochastic modeling

Fingerprint

Dive into the research topics of 'Stochastic Performance Prediction for Iterative Algorithms in Distributed Environments'. Together they form a unique fingerprint.

Cite this