Stochastic models for performance analyses of iterative algorithms in distributed environments

This research aims at creating a framework to analyze the performance of iterative algorithms in distributed environments. The parallelization of certain iterative algorithms is indeed a crucial issue for the efficient solution of large or complex optimization problems. Diverse implementation techniques for such parallelizations have become popular. They are examined here with a view to un-derstanding their impact on the algorithm behavior in a distributed environment. Several theoretical results concerning the sufficient conditions for, and speed of, convergence for parallel iterative algorithms are available. However, there is a gap between those results and what is relevant to the user at the application level. In particular, an estimate of the algorithm execution time is often desirable. The performance characterization presented in this dissertation follows a stochas-tic approach partially based on a Markov process. It addresses different character-istics of the algorithmic execution time such as mean values, standard deviations and rare events. It is shown how this approach can fill the aforementioned gap thanks to stochastic models, which take into account the distributed environment used to run the algorithm. We concentrate on distributed-memory systems. The results of this research enable the end-user to make informed choices about what combinations of distributed environment and implementation style should lead to appropriate execution time distributions.