\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 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, the white spaces the idle
-times and the arrows the communications.
-\AG{There are no ``white spaces'' on the figure.}
-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}
+As exposed in the introduction, parallel iterative methods are now widely used
+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}
\begin{figure}[!t]
\centering
\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
+%% engineers have to develop techniques for maximizing application performance of
+%% these multi-cluster platforms, by redesigning the applications and/or by using
+%% novel algorithms that can account for the composite and heterogeneous nature of
+%% the platform. Unfortunately, the deployment of such applications on these very
+%% large scale systems is very costly, labor intensive and time consuming. In this
+%% context, it appears that the use of simulation tools to explore various platform
+%% scenarios at will and to run enormous numbers of experiments quickly can be very
+%% promising. Several works\dots{}
+
+%% \AG{Several works\dots{} what?\\
+% Le paragraphe suivant se trouve déjà dans l'intro ?}
+In the context of asynchronous algorithms, the number of iterations to reach the
+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
+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
+nodes, inter and intra clusrters bandwith and latency, ....) and of the
+algorithm (number of splitting with the multisplitting algorithm), the
+multisplitting code will obtain the solution more or less quickly. Or course,
+the GMRES method also depends of the same parameters. As it is difficult to have
+access to many clusters, grids or supercomputers with many different network
+parameters, it is interesting to be able to simulate the behaviors of
+asynchronous iterative algoritms before being able to runs real experiments.
-It is very challenging to develop efficient applications for large scale,
-heterogeneous and distributed platforms such as computing grids. Researchers and
-engineers have to develop techniques for maximizing application performance of
-these multi-cluster platforms, by redesigning the applications and/or by using
-novel algorithms that can account for the composite and heterogeneous nature of
-the platform. Unfortunately, the deployment of such applications on these very
-large scale systems is very costly, labor intensive and time consuming. In this
-context, it appears that the use of simulation tools to explore various platform
-scenarios at will and to run enormous numbers of experiments quickly can be very
-promising. Several works\dots{}
-\AG{Several works\dots{} what?\\
- Le paragraphe suivant se trouve déjà dans l'intro ?}
-In the context of AIAC algorithms, the use of simulation tools is even more
-relevant. Indeed, this class of applications is 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.
tolerance threshold of the error computed between two successive local solution
$X_\ell^k$ and $X_\ell^{k+1}$.
+
+
+In this paper, we solve the 3D Poisson problem whose the mathematical model is
+\begin{equation}
+\left\{
+\begin{array}{l}
+\nabla^2 u = f \text{~in~} \Omega \\
+u =0 \text{~on~} \Gamma =\partial\Omega
+\end{array}
+\right.
+\label{eq:02}
+\end{equation}
+where $\nabla^2$ is the Laplace operator, $f$ and $u$ are real-valued functions, and $\Omega=[0,1]^3$. The spatial discretization with a finite difference scheme reduces problem~(\ref{eq:02}) to a system of sparse linear equations. The general iteration scheme of our multisplitting method in a 3D domain using a seven point stencil could be written as
+\begin{equation}
+\begin{array}{ll}
+u^{k+1}(x,y,z)= & u^k(x,y,z) - \frac{1}{6}\times\\
+ & (u^k(x-1,y,z) + u^k(x+1,y,z) + \\
+ & u^k(x,y-1,z) + u^k(x,y+1,z) + \\
+ & u^k(x,y,z-1) + u^k(x,y,z+1)),
+\end{array}
+\label{eq:03}
+\end{equation}
+where the iteration matrix $A$ of size $N_x\times N_y\times N_z$ of the discretized linear system is sparse, symmetric and positive definite.
+
+The parallel solving of the 3D Poisson problem with our multisplitting method requires a data partitioning of the problem between clusters and between processors within a cluster. We have chosen the 3D partitioning instead of the row-by-row partitioning in order to reduce the data exchanges at sub-domain boundaries. Figure~\ref{fig:4.2} shows an example of the data partitioning of the 3D Poisson problem between two clusters of processors, where each sub-problem is assigned to a processor. In this context, a processor has at most six neighbors within a cluster or in distant clusters with which it shares data at sub-domain boundaries.
+
+\begin{figure}[!t]
+\centering
+ \includegraphics[width=80mm,keepaspectratio]{partition}
+\caption{Example of the 3D data partitioning between two clusters of processors.}
+\label{fig:4.2}
+\end{figure}
+
+
+
+
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
We did not encounter major blocking problems when adapting the multisplitting algorithm previously described to a simulation environment like SimGrid unless some code
debugging. Indeed, apart from the review of the program sequence for asynchronous exchanges between processors within a cluster or between clusters, the algorithm was executed successfully with SMPI and provided identical outputs as those obtained with direct execution under MPI. In synchronous
-\section{Experimental results}
+\section{Simulation results}
When the \textit{real} application runs in the simulation environment and produces the expected results, varying the input
parameters and the program arguments allows us to compare outputs from the code execution. We have noticed from this
simulates the case of distant clusters linked with long distance network like
Internet.
-\AG{Cette partie sur le poisson 3D
- % on sait donc que ce n'est pas une plie ou une sole (/me fatigué)
- n'est pas à sa place. Elle devrait être placée plus tôt.}
-In this paper, we solve the 3D Poisson problem whose the mathematical model is
-\begin{equation}
-\left\{
-\begin{array}{l}
-\nabla^2 u = f \text{~in~} \Omega \\
-u =0 \text{~on~} \Gamma =\partial\Omega
-\end{array}
-\right.
-\label{eq:02}
-\end{equation}
-where $\nabla^2$ is the Laplace operator, $f$ and $u$ are real-valued functions, and $\Omega=[0,1]^3$. The spatial discretization with a finite difference scheme reduces problem~(\ref{eq:02}) to a system of sparse linear equations. The general iteration scheme of our multisplitting method in a 3D domain using a seven point stencil could be written as
-\begin{equation}
-\begin{array}{ll}
-u^{k+1}(x,y,z)= & u^k(x,y,z) - \frac{1}{6}\times\\
- & (u^k(x-1,y,z) + u^k(x+1,y,z) + \\
- & u^k(x,y-1,z) + u^k(x,y+1,z) + \\
- & u^k(x,y,z-1) + u^k(x,y,z+1)),
-\end{array}
-\label{eq:03}
-\end{equation}
-where the iteration matrix $A$ of size $N_x\times N_y\times N_z$ of the discretized linear system is sparse, symmetric and positive definite.
-
-The parallel solving of the 3D Poisson problem with our multisplitting method requires a data partitioning of the problem between clusters and between processors within a cluster. We have chosen the 3D partitioning instead of the row-by-row partitioning in order to reduce the data exchanges at sub-domain boundaries. Figure~\ref{fig:4.2} shows an example of the data partitioning of the 3D Poisson problem between two clusters of processors, where each sub-problem is assigned to a processor. In this context, a processor has at most six neighbors within a cluster or in distant clusters with which it shares data at sub-domain boundaries.
-
-\begin{figure}[!t]
-\centering
- \includegraphics[width=80mm,keepaspectratio]{partition}
-\caption{Example of the 3D data partitioning between two clusters of processors.}
-\label{fig:4.2}
-\end{figure}
-
As a first step, the algorithm was run on a network consisting of two clusters
containing 50 hosts each, totaling 100 hosts. Various combinations of the above
