Computational & Technology Resources
an online resource for computational,
engineering & technology publications 

CivilComp Proceedings
ISSN 17593433 CCP: 112
PROCEEDINGS OF THE SIXTH INTERNATIONAL CONFERENCE ON PARALLEL, DISTRIBUTED, GPU AND CLOUD COMPUTING FOR ENGINEERING Edited by: P. Iványi and B.H.V. Topping
Paper 14
Synthetic presentation of iterative asynchronous parallel algorithms P. Spiteri
IRIT INPT, University of Toulouse, Toulouse, France P. Spiteri, "Synthetic presentation of iterative asynchronous
parallel algorithms", in P. Iványi, B.H.V. Topping, (Editors), "Proceedings of the Sixth International Conference on Parallel, Distributed, GPU and Cloud Computing for Engineering", CivilComp Press, Stirlingshire, UK, Paper 14, 2019. doi:10.4203/ccp.112.14
Keywords: asynchronous parallel algoritm, high performance computing, iterative method,
subdomain method, multisplitting methods, discretized pseudolinear problem, large scale systems,
nonlinear boundary value problems, optimization.
Summary
Iterative 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 subdomain 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.
purchase the fulltext of this paper (price £22)
go to the previous paper 
