Synthetic presentation of iterative asynchronous parallel algorithms.

International audienceIterative asynchronous parallel methods are nowadays gaining renewed interest in the community of researchers interested in High Performance Computing (HPC), in the specific case of massive parallelism. This is because these methods avoid the deadlock phenomena and that moreover a rigorous load balancing is not necessary, which is not the case with synchronous methods. Such iterative asynchronous parallel methods are of great interest when there are many synchronizations between processors, which in the case of iterative methods is the case when convergence is slow. Indeed in iterative synchronous parallel methods, to respect the task sequence graph that defines in fact the logic of the algorithm used, processors must wait for the results they need and calculated by other processors; such expectations of the results emitted by concurrent processors therefore cause idle times for standby processors. It is to overcome this drawback that asynchronous parallel iterative methods have been introduced first for the resolution of large scale linear systems and then for the resolution of highly nonlinear algebraic systems of large size as well, where the solution may be subject to constraints. This kind of method has been widely studied worldwide by many authors. The purpose of this presentation is to present as broadly and pedagogically as possible the asynchronous parallel iterative methods as well as the issues related to their implementation and application in solving many problems arising from High Performance Computing. We will therefore try as much as possible to present the underlying concepts that allow a good understanding of these methods by avoiding as much as possible an overly rigorous mathematical formalism; references to the main pioneering work will also be made. After a general introduction we will present the basic concepts that allow to model asynchronous parallel iterative methods including as a particular case synchronous methods. We will then present the algorithmic extensions of these methods consisting of asynchronous sub-domain methods, asynchronous multisplitting methods as well as asynchronous parallel methods with flexible communications. In each case an analysis of the behavior of these methods will be presented. Note that the first kind of analysis allows to obtain an estimate of the asymptotic rate of convergence. The difficult problem of the stopping test of asynchronous parallel iterations will be also studied, both by computer sciences considerations and also by numerical aspects related to the mathematical analysis of the behavior of theses iterative parallel methods. The parallel asynchronous methods have been implemented on various architectures and we will present the main principles that made it possible to code them. These parallel asynchronous methods have been used for the resolution of several kind of mathematical problems and we will list the main applications processed. Finally we will try to specify in which cases and on which type of architecture these methods are efficient and interesting to use