X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/hpcc2014.git/blobdiff_plain/d08d0574c6782fe3a320861ccd6ec60a2ab6025e..6785b9ef58de0db67c33ca901c7813f3dfdc76e0:/hpcc.tex

diff --git a/hpcc.tex b/hpcc.tex
index 29d00a1..49caa2f 100644
--- a/hpcc.tex
+++ b/hpcc.tex
@@ -170,25 +170,31 @@ out will be presented before some concluding remarks and future works.
  
 \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
@@ -197,26 +203,38 @@ in a grid computing context.\LZK{RÃ©pÃ©tition par rapport Ã  l'intro}
   \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.
 
 
 
@@ -384,6 +402,42 @@ where $\MI$ is the maximum number of outer iterations and $\epsilon$ is the
 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 
@@ -402,7 +456,7 @@ environment. We have successfully executed the code in synchronous mode using pa
 
 
 
-\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
@@ -434,40 +488,6 @@ synchronous mode allowing to get a relative gain greater than 1.  This action
 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
