X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/hpcc2014.git/blobdiff_plain/7c13e863b8fb839dcd1bfd2ae4e76db730f5c130..671864fc27e3f1eaeff1a01d2a0a99d047e43247:/hpcc.tex?ds=inline

diff --git a/hpcc.tex b/hpcc.tex
index d5be4d4..29eca38 100644
--- a/hpcc.tex
+++ b/hpcc.tex
@@ -322,19 +322,7 @@ is solved independently by a cluster and communications are required to update t
 \label{algo:01}
 \end{figure}
 
-Algorithm on Figure~\ref{algo:01} shows the main key points of the
-multisplitting method to solve a large sparse linear system. This algorithm is
-based on an outer-inner iteration method where the parallel synchronous GMRES
-method is used to solve the inner iteration. It is executed in parallel by each
-cluster of processors. For all $l,m\in\{1,\ldots,L\}$, the matrices and vectors
-with the subscript $l$ represent the local data for cluster $l$, while
-$\{A_{lm}\}_{m\neq l}$ are off-diagonal matrices of sparse matrix $A$ and
-$\{X_m\}_{m\neq l}$ contain vector elements of solution $x$ shared with
-neighboring clusters. At every outer iteration $k$, asynchronous communications
-are performed between processors of the local cluster and those of distant
-clusters (lines~\ref{algo:01:send} and~\ref{algo:01:recv} in
-Figure~\ref{algo:01}). The shared vector elements of the solution $x$ are
-exchanged by message passing using MPI non-blocking communication routines.
+Algorithm on Figure~\ref{algo:01} shows the main key points of the multisplitting method to solve a large sparse linear system. This algorithm is based on an outer-inner iteration method where the parallel synchronous GMRES method is used to solve the inner iteration. It is executed in parallel by each cluster of processors. For all $l,m\in\{1,\ldots,L\}$, the matrices and vectors with the subscript $l$ represent the local data for cluster $l$, while $\{A_{lm}\}_{m\neq l}$ are off-diagonal matrices of sparse matrix $A$ and $\{X_m\}_{m\neq l}$ contain vector elements of solution $x$ shared with neighboring clusters. At every outer iteration $k$, asynchronous communications are performed between processors of the local cluster and those of distant clusters (lines~\ref{algo:01:send} and~\ref{algo:01:recv} in Figure~\ref{algo:01}). The shared vector elements of the solution $x$ are exchanged by message passing using MPI non-blocking communication routines.
 
 \begin{figure}[!t]
 \centering
@@ -343,21 +331,7 @@ exchanged by message passing using MPI non-blocking communication routines.
 \label{fig:4.1}
 \end{figure}
 
-The global convergence of the asynchronous multisplitting solver is detected
-when the clusters of processors have all converged locally. We implemented the
-global convergence detection process as follows. On each cluster a master
-processor is designated (for example the processor with rank 1) and masters of
-all clusters are interconnected by a virtual unidirectional ring network (see
-Figure~\ref{fig:4.1}). During the resolution, a Boolean token circulates around
-the virtual ring from a master processor to another until the global convergence
-is achieved. So starting from the cluster with rank 1, each master processor $i$
-sets the token to \textit{True} if the local convergence is achieved or to
-\text\it{False} otherwise, and sends it to master processor $i+1$. Finally, the
-global convergence is detected when the master of cluster 1 receives from the
-master of cluster $L$ a token set to \textit{True}. In this case, the master of
-cluster 1 broadcasts a stop message to masters of other clusters. In this work,
-the local convergence on each cluster $l$ is detected when the following
-condition is satisfied
+The global convergence of the asynchronous multisplitting solver is detected when the clusters of processors have all converged locally. We implemented the global convergence detection process as follows. On each cluster a master processor is designated (for example the processor with rank 1) and masters of all clusters are interconnected by a virtual unidirectional ring network (see Figure~\ref{fig:4.1}). During the resolution, a Boolean token circulates around the virtual ring from a master processor to another until the global convergence is achieved. So starting from the cluster with rank 1, each master processor $i$ sets the token to {\it True} if the local convergence is achieved or to {\it False} otherwise, and sends it to master processor $i+1$. Finally, the global convergence is detected when the master of cluster 1 receives from the master of cluster $L$ a token set to {\it True}. In this case, the master of cluster 1 broadcasts a stop message to masters of other clusters. In this work, the local convergence on each cluster $l$ is detected when the following condition is satisfied
 \begin{equation*}
   (k\leq \MI) \text{ or } (\|X_l^k - X_l^{k+1}\|_{\infty}\leq\epsilon)
 \end{equation*}
@@ -398,7 +372,7 @@ study that the results depend on the following parameters:
   experimentation of the simulation in having an execution time in asynchronous
   less than in synchronous mode (i.e. speed-up less than 1).
 \end{itemize}
-\LZK{Propositions pour changer le terme ``speedup'': acceleration ratio ou relative gain}
+\LZK{Propositions pour remplacer le terme ``speedup'': acceleration ratio ou relative gain}
 
 A priori, obtaining a speedup less than 1 would be difficult in a local area
 network configuration where the synchronous mode will take advantage on the
@@ -409,14 +383,45 @@ configuration, degrading the inter-cluster network performance will
 This action simulates the case of clusters linked with long distance network
 like Internet.
 
+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 of 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
 factors have providing the results shown in Table~\ref{tab.cluster.2x50} with a
 matrix size ranging from $N_x = N_y = N_z = \text{62}$ to 171 elements or from
 $\text{62}^\text{3} = \text{\np{238328}}$ to $\text{171}^\text{3} =
 \text{\np{5211000}}$ entries.
-\CER{Voir ma remarque plus si nécessaire de décrire en détail le partitionnement 3D}
-\LZK{Je pense qu'il faut donner ici le type du problème traité (Poisson 3D). Le partitionnement 3D permet juste de définir le schéma de dépendances (1 proc a au max 6 voisins dans le cluster local ou dans les clusters distants)}
+
 % use the same column width for the following three tables
 \newlength{\mytablew}\settowidth{\mytablew}{\footnotesize\np{E-11}}
 \newenvironment{mytable}[1]{% #1: number of columns for data