From: couturie <couturie@extinction>
Date: Sun, 17 Jan 2016 20:17:16 +0000 (+0100)
Subject: mise à jour des algos et des explications
X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/kahina_paper2.git/commitdiff_plain/5a148233379bd1acbd9c6872c8cf113b73198d5a

mise à jour des algos et des explications
---

diff --git a/paper.tex b/paper.tex
index 9733c3d..5df0ef9 100644
--- a/paper.tex
+++ b/paper.tex
@@ -152,7 +152,17 @@ z^{k+1}_{i}=z_{i}^{k}-\frac{\frac{p(z_{i}^{k})}{p'(z_{i}^{k})}}
 {1-\frac{p(z_{i}^{k})}{p'(z_{i}^{k})}\sum_{j=1,j\neq i}^{j=n}{\frac{1}{(z_{i}^{k}-z_{j}^{k})}}}, i=1,\ldots,n
 \end{equation}
 
-This method contains 4 steps. The first step consists in the initializing the polynomial. The second step initializes the solution vector $Z$ using the Guggenheimer method~\cite{Gugg86} to ensure that initial roots are all distinct from each other. In step 3, the iterative function based on the Newton's method~\cite{newt70} and Weiestrass operator~\cite{Weierstrass03} is applied. In our case, the Ehrlich-Aberth is applied as in~(\ref{Eq:EA1}). Iterations of the Ehrlich-Aberth method will converge to the roots of the considered polynomial. In order to stop the iterative function, a stop condition is applied, this is the 4th step. This condition checks that all the root modules are lower than a fixed value $\epsilon$.
+This method contains 4 steps. The first step consists in the
+initializing the polynomial. The second step initializes the solution
+vector $Z$ using the Guggenheimer method~\cite{Gugg86} to ensure that
+initial roots are all distinct from each other. In step 3, the
+iterative function based on the Newton's method~\cite{newt70} and
+Weiestrass operator~\cite{Weierstrass03} is applied. In our case, the
+Ehrlich-Aberth is applied as in~(\ref{Eq:EA1}). Iterations of the
+Ehrlich-Aberth method will converge to the roots of the considered
+polynomial. In order to stop the iterative function, a stop condition
+is applied, this is the 4th step. This condition checks that all the
+root modules are lower than a fixed value $\epsilon$.
 
 \begin{equation}
 \label{eq:Aberth-Conv-Cond}
@@ -188,66 +198,58 @@ Using the logarithm  and the exponential operators, we can replace any multiplic
 
 \subsection{The Ehrlich-Aberth parallel implementation on CUDA}
 
-Our objective consists in implementing a root finding polynomial
-algorithm on multiple GPUs. To this end, it is primordial to know how
-to manage CUDA contexts of different GPUs. A direct method for
-controlling the various GPUs is to use as many threads or processes as
-GPU devices. We can choose the GPU index based on the identifier of
-OpenMP thread or the rank of the MPI process. Both approaches will be
-investigated. \LZK{Répétition! Le même texte est déjà écrit comme
-  intro dans la section II. Sinon ici on parle seulement de
-  l'implémentation cuda sans mpi et openmp! \RC{Je suis d'accord à
-    revoir après, quand les 2 parties suivantes seront plus stables}}
-
-
-
-
-Like any parallel code, a GPU parallel implementation first requires to determine the sequential code and the data-parallel operations of a algorithm. In fact, all the operations that are easy to execute in parallel must be made by the GPU to accelerate the execution, like the steps 3 and 4. On the other hand, all the sequential operations and the operations that have data dependencies between CUDA threads or recursive computations must be executed by only one CUDA thread or a CPU thread (the steps 1 and 2).\LZK{La méthode est déjà mal présentée, dans ce cas c'est encore plus difficile de comprendre que représentent ces différentes étapes!} Initially, we specify the organization of parallel threads by specifying the dimension of the grid \verb+Dimgrid+, the number of blocks per grid \verb+DimBlock+ and the number of threads per block.
-
-The code is organized as kernels which are parts of code that are run on GPU devices. For step 3, there are two kernels, the first is named \textit{save} is used to save vector $Z^{K-1}$ and the second one is
-named \textit{update} and is used to update the $Z^{K}$ vector. For
-step 4, a kernel tests the convergence of the method. In order to
-compute the function H, we have two possibilities: either to use the
-Jacobi mode, or the Gauss-Seidel mode of iterating which uses the most
-recent computed roots. It is well known that the Gauss-Seidel mode
-converges more quickly. So, we use Gauss-Seidel iterations. To
-parallelize the code, we create kernels and many functions to be
-executed on the GPU for all the operations dealing with the
-computation on complex numbers and the evaluation of the
-polynomials. As said previously, we manage both functions of
-evaluation: the normal method, based on the method of
-Horner and the method based on the logarithm of the polynomial. All
-these methods were rather long to implement, as the development of
-corresponding kernels with CUDA is longer than on a CPU host. This
-comes in particular from the fact that it is very difficult to debug
-CUDA running threads like threads on a CPU host. In the following
-paragraph Algorithm~\ref{alg1-cuda} shows the GPU parallel
-implementation of Ehrlich-Aberth method.
-\LZK{Vaut mieux expliquer l'implémentation en faisant référence à l'algo séquentiel que de parler des différentes steps.}
 
 
 
+The code is organized as kernels which are parts of code that are run
+on GPU devices. Algorithm~\ref{alg1-cuda} describes the CUDA
+implementation of the Ehrlich-Aberth on a GPU.  This algorithms starts
+by initializinf the polynomial and its derivative (line 1). The
+initialization of the roots is performed (line 2). Data are transfered
+from the CPU to the GPU (after allocation of the required memory on
+the GPU) (line 3). Then at each iteration, if the error is greater
+than a threshold, the following operations are performed. The previous
+roots are saved using a kernel (line 5). Then the new root with the
+new iterations are computed using the EA method with a Gauss Seidel
+iteration modes in order to use the lastest roots updated (line
+6). This improves the convergence. This kernel is, in pratice, very
+long since it performs all the operations with complex numbers with
+the normal mode of the EA method but also with the
+logarithm-exponential one. Then the error is computed with a final
+kernel (line 7). Finally when the EA method has converged, the roots
+are transferred from the GPU to the CPU.
+
 \begin{algorithm}[htpb]
+\label{alg1-cuda}
 \LinesNumbered
 \SetAlgoNoLine
 \caption{Finding roots of polynomials with the Ehrlich-Aberth method on a GPU}
-\KwIn{$n$ (polynomial's degree), $\epsilon$ (tolerance threshold)}
+\KwIn{ $\epsilon$ (tolerance threshold)}
 \KwOut{$Z$ (solution vector of roots)}
 Initialize the polynomial $P$ and its derivative $P'$\;
 Set the initial values of vector $Z$\;
 Copy $P$, $P'$ and $Z$ from CPU to GPU\;
-\While{$\Delta Z_{max} > \epsilon$}{
-  $Z^{prev}$ = KernelSave($Z,n$)\;
-  $Z$ = KernelUpdate($P,P',Z,n$)\;
-  $\Delta Z_{max}$ = KernelComputeError($Z,Z^{prev},n$)\;
+\While{$error > \epsilon$}{
+  $Z^{prev}$ = KernelSave($Z$)\;
+  $Z$ = KernelUpdate($P,P',Z$)\;
+  $error$ = KernelComputeError($Z,Z^{prev}$)\;
 }
 Copy $Z$ from GPU to CPU\;
-\label{alg1-cuda}
-\RC{La ligne avec TestConvergence ca fait une ligne de plus.\LZK{Oui j'ai hésité à l'ajouter. On peut faire le test dans la condition de while mais quelle est la valeur initiale de $\Delta Z_{max}$?! Ou bien on s'en fiche?}}
 \end{algorithm}
 
+
+The development of this code is a rather long task, as the development
+of corresponding kernels with CUDA is longer than on a CPU host. This
+comes in particular from the fact that it is very difficult to debug
+CUDA running threads like threads on a CPU host.  In the following
+section the GPU parallel implementation of Ehrlich-Aberth method with
+OpenMP and MPI is presented.
+
+
+
+
  
-\section{The EA algorithm on Multiple GPUs}
+\section{The EA algorithm on multiple GPUs}
 \label{sec4}
 \subsection{an OpenMP-CUDA approach}
 Our OpenMP-CUDA implementation of EA algorithm is based on the hybrid
@@ -265,7 +267,7 @@ runs the computation kernels.
 To compute one iteration of the EA method each GPU performs the
 followings steps. First roots are shared with OpenMP and the
 computation of the local size for each GPU is performed (lines 5-7 in
-Algo\ref{alg2-cuda-openmp}). Each thread starts by copying all the
+Algorithm \ref{alg2-cuda-openmp}). Each thread starts by copying all the
 previous roots inside its GPU (line 9). Then each GPU will copy the
 previous roots (line 10) and it will compute an iteration of the EA
 method on its own roots (line 11).  For that all the other roots are
@@ -277,31 +279,25 @@ arrays containing all the roots.
 
 
 \begin{algorithm}[htpb]
+\label{alg2-cuda-openmp}
 \LinesNumbered
 \SetAlgoNoLine
 \caption{Finding roots of polynomials with the Ehrlich-Aberth method on multiple GPUs using OpenMP}
-\KwIn{$n$ (polynomial's degree), $\epsilon$ (tolerance threshold), $ngpu$ (number of GPUs)}
+\KwIn{ $\epsilon$ (tolerance threshold)}
 \KwOut{$Z$ (solution vector of roots)}
 Initialize the polynomial $P$ and its derivative $P'$\;
 Set the initial values of vector $Z$\;
-Start of a parallel part with OpenMP ($Z$, $\Delta Z_{max}$, $P$, $P'$ are shared variables)\;
-$id_{gpu}$ = cudaGetDevice()\;
-$n_{loc}$ = $n/ngpu$ (local size)\;
-$offset$ = $id_{gpu}\times n_{loc}$ (local offset)\;
+Start of a parallel part with OpenMP ($Z$, $error$, $P$, $P'$ are shared variables)\;
+Determine the local part of the OpenMP thread\;
 Copy $P$, $P'$ from CPU to GPU\;
-\While{$max > \epsilon$}{
+\While{$error > \epsilon$}{
   Copy $Z$ from CPU to GPU\;
-  $Z^{prev}$ = KernelSave($Z,n$)\;
-  $Z[offset]$ = KernelUpdate($P,P',Z,n_{loc}$)\;
-  $\Delta Z_{max}[id_{gpu}]$ = KernelComputeError($Z[offset],Z^{prev}[offset],n_{loc}$)\;
-  Copy $Z[offset]$ from GPU to $Z$ in CPU\;
-  $max$ = MaxFunction($\Delta Z_{max},ngpu$)\; 
+  $Z^{prev}_{loc}$ = KernelSave($Z_{loc}$)\;
+  $Z_{loc}$ = KernelUpdate($P,P',Z$)\;
+  $error_{loc}$ = KernelComputeError($Z_{loc},Z^{prev}_{loc}$)\;
+  $error = max(error_{loc})$\;
+  Copy $Z_{loc}$ from GPU to $Z$ in CPU\;
 }
-\label{alg2-cuda-openmp}
-\RC{Je l'ai rajouté. Bon sinon le n\_loc ne remplace pas
-  vraiment un offset et une taille mais bon... et là il y a 4 lignes
-  pour la convergence, c'est bcp ... Zloc, Zmax, max et
-  testconvergence. On pourrait faire mieux\LZK{Modifié, c'est bon!}}
 \end{algorithm}
 
 
@@ -337,29 +333,28 @@ convergence is not statisfied, an new iteration is executed.
 \begin{algorithm}[htpb]
 \label{alg2-cuda-mpi}
 \LinesNumbered
+\SetAlgoNoLine
 \caption{CUDA-MPI Algorithm to find roots with the Ehrlich-Aberth method}
 
-\KwIn{$Z^{0}$ (Initial root's vector), $\varepsilon$ (Error tolerance
-  threshold), P (Polynomial to solve), P' (Derivative of P), $n$ (Polynomial degrees), $\Delta z$ ( error of stop condition)}
+\KwIn{  $\epsilon$ (tolerance threshold)}
 
-\KwOut {$Z$ (Solution root's vector)}
+\KwOut {$Z$ (solution vector of roots)}
 
 \BlankLine
-Initialization of P\;
-Initialization of Pu\;
-Initialization of the solution vector $Z^{0}$\;
+Initialize the polynomial $P$ and its derivative $P'$\;
+Set the initial values of vector $Z$\;
+Determine the local part of the MPI process\;
 Computation of the parameters for the $MPI\_AlltoAll$\;
-Allocate memory to GPU\;
+Copy $P$, $P'$ from CPU to GPU\;
 \While {$error > \epsilon$}{
-copy Z from CPU to GPU\;
-$Z^{Prev}_{loc}=kernel\_save(Z_{loc})$\;
-$Z_{loc}=kernel\_update(Z,P,P')$\;
-$\Delta z=kernel\_testConv(Z_{loc},Z^{prev}_{loc})$\;
-$error=MPI\_Reduce(\Delta z)$\;
-Copy $Z_{loc}$ from GPU to CPU\;
-$Z=MPI\_AlltoAll(Z_{loc})$\;
+  Copy $Z$ from CPU to GPU\;
+  $Z^{prev}_{loc}$ = KernelSave($Z_{loc}$)\;
+  $Z_{loc}$ = KernelUpdate($P,P',Z$)\;
+  $error_{loc}$ = KernelComputeError($Z_{loc},Z^{prev}_{loc}$)\;
+  $error=MPI\_Reduce(error_{loc})$\;
+  Copy $Z_{loc}$ from GPU to CPU\;
+  $Z=MPI\_AlltoAll(Z_{loc})$\;
 }
-\RC{A uniformiser avec les autres algos, mais les grandes lignes sont là}
 \end{algorithm}