From: couturie Date: Tue, 5 May 2015 09:36:14 +0000 (+0200) Subject: relecture abstract et intro et début de la section du l'async X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/rce2015.git/commitdiff_plain/7598268ddab4631d2d0bbb07f6e4f7cbf8cfc2f3?ds=inline;hp=4f3f422c55e11ca375bf5f17203c5d82ed9928aa relecture abstract et intro et début de la section du l'async --- diff --git a/biblio.bib b/biblio.bib index eaf5345..7cfae41 100644 --- a/biblio.bib +++ b/biblio.bib @@ -142,3 +142,34 @@ year = {2006}, key = {SimGrid}, year = 2014, } + +@Article{myBCCV05c, + author = {J. M. Bahi and S. Contassot-Vivier and R. Co +uturier and F. Vernier}, + title = {A decentralized convergence detection algorithm for asynchronous parallel iterative algorithms}, + journal = {IEEE Transactions on Parallel and Distributed Systems}, + year = {2005}, + volume = {16}, + number = {1}, + pages = {4--13}, +} + +@article{ccl09:ij, +inhal = {no}, +domainehal = {INFO:INFO_DC, INFO:INFO_CR, INFO:INFO_MO}, +equipe = {and}, +classement = {ACLI}, +impact-factor ={0.615}, +isi-acro = {J SUPERCOMPUT}, +author = {Charr, Jean-Claude and Couturier, Rapha\"el and Laiymani, David}, +title = {A Decentralized and Fault Tolerant Convergence Detection Algorithm for Asynchronous Iterative Algorithms}, +journal = {The journal of Supercomputing}, +doi = {10.1007/s11227-009-0293-6}, +url = {http://dx.doi.org/10.1007/s11227-009-0293-6}, +pages = {269--292}, +volume = 53, +number = 2, +publisher = {Springer}, +year = 2010, + +} \ No newline at end of file diff --git a/paper.tex b/paper.tex index 377a87f..cea0a41 100644 --- a/paper.tex +++ b/paper.tex @@ -90,7 +90,7 @@ analysis of simulated grid-enabled numerical iterative algorithms} %% Lilia Ziane Khodja: Department of Aerospace \& Mechanical Engineering\\ Non Linear Computational Mechanics\\ University of Liege\\ Liege, Belgium. Email: l.zianekhodja@ulg.ac.be -\begin{abstract} The behavior of multicore applications is always a challenge +\begin{abstract} The behavior of multi-core applications is always a challenge to predict, especially with a new architecture for which no experiment has been performed. With some applications, it is difficult, if not impossible, to build accurate performance models. That is why another solution is to use a simulation @@ -101,7 +101,7 @@ applications. In this paper, we focus our attention on two parallel iterative algorithms based on the Multisplitting algorithm and we compare them to the GMRES algorithm. -These algorithms are used to solve libear systems. Two different variantsof +These algorithms are used to solve libear systems. Two different variants of the Multisplitting are studied: one using synchronoous iterations and another one with asynchronous iterations. For each algorithm we have tested different parameters to see their influence. We strongly recommend people interested @@ -119,8 +119,8 @@ their applications using a simulation tool before. \maketitle -\section{Introduction} The use of multi-core architectures for solving large -scientific problems seems to become imperative in a lot of cases. +\section{Introduction} The use of multi-core architectures to solve large +scientific problems seems to become imperative in many situations. Whatever the scale of these architectures (distributed clusters, computational grids, embedded multi-core,~\ldots) they are generally well adapted to execute complex parallel applications operating on a large amount of data. @@ -131,8 +131,7 @@ are often very important. So, in this context it is difficult to optimize a given application for a given architecture. In this way and in order to reduce the access cost to these computing resources it seems very interesting to use a simulation environment. The advantages are numerous: development life cycle, -code debugging, ability to obtain results quickly,~\ldots at the condition that -the simulation results are in education with the real ones. +code debugging, ability to obtain results quickly,~\ldots. In counterpart, the simulation results need to be consistent with the real ones. In this paper we focus on a class of highly efficient parallel algorithms called \emph{iterative algorithms}. The parallel scheme of iterative methods is quite @@ -147,7 +146,7 @@ from its neighbors. We say that the iteration computation follows a synchronous scheme. In the asynchronous scheme a task can compute a new iteration without having to wait for the data dependencies coming from its neighbors. Both communication and computations are asynchronous inducing that there is no more -idle times, due to synchronizations, between two iterations~\cite{bcvc06:ij}. +idle time, due to synchronizations, between two iterations~\cite{bcvc06:ij}. This model presents some advantages and drawbacks that we detail in section~\ref{sec:asynchro} but even if the number of iterations required to converge is generally greater than for the synchronous case, it appears that @@ -155,15 +154,15 @@ the asynchronous iterative scheme can significantly reduce overall execution times by suppressing idle times due to synchronizations~(see~\cite{bahi07} for more details). -Nevertheless, in both cases (synchronous or asynchronous) it is very time -consuming to find optimal configuration and deployment requirements for a given -application on a given multi-core architecture. Finding good resource -allocations policies under varying CPU power, network speeds and loads is very -challenging and labor intensive~\cite{Calheiros:2011:CTM:1951445.1951450}. This -problematic is even more difficult for the asynchronous scheme where variations -of the parameters of the execution platform can lead to very different number of -iterations required to converge and so to very different execution times. In -this challenging context we think that the use of a simulation tool can greatly +Nevertheless, in both cases (synchronous or asynchronous) it is very time +consuming to find optimal configuration and deployment requirements for a given +application on a given multi-core architecture. Finding good resource +allocations policies under varying CPU power, network speeds and loads is very +challenging and labor intensive~\cite{Calheiros:2011:CTM:1951445.1951450}. This +problematic is even more difficult for the asynchronous scheme where a small +parameter variation of the execution platform can lead to very different numbers +of iterations to reach the converge and so to very different execution times. In +this challenging context we think that the use of a simulation tool can greatly leverage the possibility of testing various platform scenarios. The main contribution of this paper is to show that the use of a simulation tool @@ -175,7 +174,7 @@ algorithm with the GMRES (Generalized Minimal Residual) solver~\cite{saad86} in synchronous mode. The obtained results on different simulated multi-core architectures confirm the real results previously obtained on non simulated architectures. We also confirm the efficiency of the -asynchronous multisplitting algorithm comparing to the synchronous GMRES. In +asynchronous multisplitting algorithm compared to the synchronous GMRES. In this way and with a simple computing architecture (a laptop) SimGrid allows us to run a test campaign of a real parallel iterative applications on different simulated multi-core architectures. To our knowledge, there is no @@ -193,6 +192,25 @@ concluding remarks and perspectives. \section{The asynchronous iteration model} \label{sec:asynchro} +Asynchronous iterative methods have been studied for many years theorecally and +practically. Many methods have been considered and convergence results have been +proved. These methods can be used to solve in parallel fixed point problems +(i.e. problems for which the solution is $x^\star =f(x^\star)$. In practice, +asynchronous iterations methods can be used to solve, for example, linear and +non-linear systems of equations or optimization problems, interested readers are +invited to read~\cite{BT89,bahi07}. + +Before using an asynchronous iterative method, the convergence must be +studied. Otherwise, the application is not ensure to reach the convergence. An +algorithm that supports both the synchronous or the asynchronous iteration model +requires very few modifications to be able to be executed in both variants. In +practice, only the communications and convergence detection are different. In +the synchronous mode, the iterations are synchronized whereas in the +asynchronous one, they are not. It should be noticed that non blocking +communications can be used in both modes. Concerning the convergence detection, +synchronous variants can use a global convergence procedure which acts as a +global synchronization point. In the asynchronous model, the convergence dectection is more tricky as it must not synchronize all the processors. Interested readers can consult~\cite{myBCCV05c,bahi07,ccl09:ij}. + \section{SimGrid} \label{sec:simgrid}