$X_{0}$ to find an approximate value $X^*$ of the solution with a very low residual error. Several well-known methods
demonstrate the convergence of these algorithms~\cite{BT89,Bahi07}.
-Parallelization of such algorithms generally involve the division of the problem into several \emph{blocks} that will
-be solved in parallel on multiple processing units. The latter will communicate each intermediate results before a new
-iteration starts and until the approximate solution is reached. These parallel computations can be performed either in
-\emph{synchronous} mode where a new iteration begins only when all nodes communications are completed,
-or in \emph{asynchronous} mode where processors can continue independently with few or no synchronization points. For
-instance in the \textit{Asynchronous Iterations~-- Asynchronous Communications (AIAC)} model~\cite{bcvc06:ij}, local
-computations do not need to wait for required data. Processors can then perform their iterations with the data present
-at that time. Even if the number of iterations required before the convergence is generally greater than for the
-synchronous case, AIAC algorithms can significantly reduce overall execution times by suppressing idle times due to
-synchronizations especially in a grid computing context (see~\cite{Bahi07} for more details).
-
-Parallel (synchronous or asynchronous) applications may have different
-configuration and deployment requirements. Quantifying their resource
-allocation policies and application scheduling algorithms in grid computing
-environments under varying load, CPU power and network speeds is very costly,
-very labor intensive and very time
-consuming~\cite{Calheiros:2011:CTM:1951445.1951450}. The case of AIAC
-algorithms is even more problematic since they are very sensible to the
-execution environment context. For instance, variations in the network bandwidth
-(intra and inter-clusters), in the number and the power of nodes, in the number
-of clusters\dots{} can lead to very different number of iterations and so to
-very different execution times. Then, it appears that the use of simulation
-tools to explore various platform scenarios and to run large numbers of
-experiments quickly can be very promising. In this way, the use of a simulation
-environment to execute parallel iterative algorithms found some interests in
-reducing the highly cost of access to computing resources: (1) for the
-applications development life cycle and in code debugging (2) and in production
-to get results in a reasonable execution time with a simulated infrastructure
-not accessible with physical resources. Indeed, the launch of distributed
-iterative asynchronous algorithms to solve a given problem on a large-scale
-simulated environment challenges to find optimal configurations giving the best
-results with a lowest residual error and in the best of execution time.
+Parallelization of such algorithms generally involve the division of the problem
+into several \emph{blocks} that will be solved in parallel on multiple
+processing units. The latter will communicate each intermediate results before a
+new iteration starts and until the approximate solution is reached. These
+parallel computations can be performed either in \emph{synchronous} mode where a
+new iteration begins only when all nodes communications are completed, or in
+\emph{asynchronous} mode where processors can continue independently with no
+synchronization points~\cite{bcvc06:ij}. In this case, local computations do not
+need to wait for required data. Processors can then perform their iterations
+with the data present at that time. Even if the number of iterations required
+before the convergence is generally greater than for the synchronous case,
+asynchronous iterative algorithms can significantly reduce overall execution
+times by suppressing idle times due to synchronizations especially in a grid
+computing context (see~\cite{Bahi07} for more details).
+
+Parallel applications based on a (synchronous or asynchronous) iteration model
+may have different configuration and deployment requirements. Quantifying their
+resource allocation policies and application scheduling algorithms in grid
+computing environments under varying load, CPU power and network speeds is very
+costly, very labor intensive and very time
+consuming~\cite{Calheiros:2011:CTM:1951445.1951450}. The case of asynchronous
+iterative algorithms is even more problematic since they are very sensible to
+the execution environment context. For instance, variations in the network
+bandwidth (intra and inter-clusters), in the number and the power of nodes, in
+the number of clusters\dots{} can lead to very different number of iterations
+and so to very different execution times. Then, it appears that the use of
+simulation tools to explore various platform scenarios and to run large numbers
+of experiments quickly can be very promising. In this way, the use of a
+simulation environment to execute parallel iterative algorithms found some
+interests in reducing the highly cost of access to computing resources: (1) for
+the applications development life cycle and in code debugging (2) and in
+production to get results in a reasonable execution time with a simulated
+infrastructure not accessible with physical resources. Indeed, the launch of
+distributed iterative asynchronous algorithms to solve a given problem on a
+large-scale simulated environment challenges to find optimal configurations
+giving the best results with a lowest residual error and in the best of
+execution time.
To our knowledge, there is no existing work on the large-scale simulation of a
-real AIAC application. {\bf The contribution of the present paper can be
- summarised in two main points}. First we give a first approach of the
-simulation of AIAC algorithms using a simulation tool (i.e. the SimGrid
-toolkit~\cite{SimGrid}). Second, we confirm the effectiveness of the
-asynchronous multisplitting algorithm by comparing its performance with the
-synchronous GMRES (Generalized Minimal Residual) \cite{ref1}. Both these codes
-can be used to solve large linear systems. In this paper, we focus on a 3D
-Poisson problem. We show, that with minor modifications of the initial MPI
-code, the SimGrid toolkit allows us to perform a test campaign of a real AIAC
-application on different computing architectures.
+real asynchronous iterative application. {\bf The contribution of the present
+ paper can be summarised in two main points}. First we give a first approach
+of the simulation of asynchronous iterative algorithms using a simulation tool
+(i.e. the SimGrid toolkit~\cite{SimGrid}). Second, we confirm the
+effectiveness of the asynchronous multisplitting algorithm by comparing its
+performance with the synchronous GMRES (Generalized Minimal Residual)
+\cite{ref1}. Both these codes can be used to solve large linear systems. In
+this paper, we focus on a 3D Poisson problem. We show, that with minor
+modifications of the initial MPI code, the SimGrid toolkit allows us to perform
+a test campaign of a real asynchronous iterative application on different
+computing architectures.
% The simulated results we
%obtained are in line with real results exposed in ??\AG[]{ref?}.
SimGrid had allowed us to launch the application from a modest computing
\section{Motivations and scientific context}
As exposed in the introduction, parallel iterative methods are now widely used
-in many scientific domains. They can be classified in three main classes
+in many scientific domains. They can be classified in three main classes
depending on how iterations and communications are managed (for more details
-readers can refer to~\cite{bcvc06:ij}). In the \textit{Synchronous Iterations~--
- Synchronous Communications (SISC)} model data are exchanged at the end of each
-iteration. All the processors must begin the same iteration at the same time and
-important idle times on processors are generated. The \textit{Synchronous
- Iterations~-- Asynchronous Communications (SIAC)} model can be compared to the
-previous one except that data required on another processor are sent
-asynchronously i.e. without stopping current computations. This technique
-allows to partially overlap communications by computations but unfortunately,
-the overlapping is only partial and important idle times remain. It is clear
-that, in a grid computing context, where the number of computational nodes is
-large, heterogeneous and widely distributed, the idle times generated by
-synchronizations are very penalizing. One way to overcome this problem is to use
-the \textit{Asynchronous Iterations~-- Asynchronous Communications (AIAC)}
-model. Here, local computations do not need to wait for required
-data. Processors can then perform their iterations with the data present at that
-time. Figure~\ref{fig:aiac} illustrates this model where the gray blocks
-represent the computation phases. With this algorithmic model, the number of
-iterations required before the convergence is generally greater than for the two
-former classes. But, and as detailed in~\cite{bcvc06:ij}, AIAC algorithms can
-significantly reduce overall execution times by suppressing idle times due to
-synchronizations especially in a grid computing context.
-%\LZK{Répétition par rapport à l'intro}
+readers can refer to~\cite{bcvc06:ij}). In the synchronous iterations model,
+data are exchanged at the end of each iteration. All the processors must begin
+the same iteration at the same time and important idle times on processors are
+generated. It is possible to use asynchronous communications, in this case, the
+model can be compared to the previous one except that data required on another
+processor are sent asynchronously i.e. without stopping current computations.
+This technique allows to partially overlap communications by computations but
+unfortunately, the overlapping is only partial and important idle times remain.
+It is clear that, in a grid computing context, where the number of computational
+nodes is large, heterogeneous and widely distributed, the idle times generated
+by synchronizations are very penalizing. One way to overcome this problem is to
+use the asynchronous iterations model. Here, local computations do not need to
+wait for required data. Processors can then perform their iterations with the
+data present at that time. Figure~\ref{fig:aiac} illustrates this model where
+the gray blocks represent the computation phases. With this algorithmic model,
+the number of iterations required before the convergence is generally greater
+than for the two former classes. But, and as detailed in~\cite{bcvc06:ij},
+asynchronous iterative algorithms can significantly reduce overall execution
+times by suppressing idle times due to synchronizations especially in a grid
+computing context.
\begin{figure}[!t]
\centering
\includegraphics[width=8cm]{AIAC.pdf}
- \caption{The Asynchronous Iterations~-- Asynchronous Communications model}
+ \caption{The asynchronous iterations model}
\label{fig:aiac}
\end{figure}
-\RC{Je serais partant de virer AIAC et laisser asynchronous algorithms... à voir}
%% It is very challenging to develop efficient applications for large scale,
%% heterogeneous and distributed platforms such as computing grids. Researchers and
convergence depends on the delay of messages. With synchronous iterations, the
number of iterations is exactly the same than in the sequential mode (if the
parallelization process does not change the algorithm). So the difficulty with
-asynchronous algorithms comes from the fact it is necessary to run the algorithm
+asynchronous iteratie algorithms comes from the fact it is necessary to run the algorithm
with real data. In fact, from an execution to another the order of messages will
change and the number of iterations to reach the convergence will also change.
According to all the parameters of the platform (number of nodes, power of
