modif Intro, partie commenté par RC et LZK

[kahina_paper2.git] / paper.tex

diff --git a/paper.tex b/paper.tex
index 5df0ef9ccf4d22496e782ee70983c9a04c2a7923..8203ed0ec7a6a605d6f076d48d51756fc13dbe1c 100644 (file)
--- a/paper.tex
+++ b/paper.tex
@@ -50,7 +50,7 @@ of polynomials of degree up-to 5 millions.
 \end{abstract}
 
 % no keywords
 \end{abstract}
 
 % no keywords

-\LZK{Faut pas mettre des keywords?}
+\LZK{Faut pas mettre des keywords?\KG{Oui d'après ça: "no keywords" qui se trouve dans leur fichier source!!, mais c'est Bizzard!!!}}

 
 
 \IEEEpeerreviewmaketitle
 
 
 \IEEEpeerreviewmaketitle


@@ -88,17 +88,15 @@ which each processor continues to update its approximations even
 though the latest values of other approximations $z^{k}_{i}$ have not
 been received from the other processors, in contrast with synchronous
 algorithms where it would wait those values before making a new
 though the latest values of other approximations $z^{k}_{i}$ have not
 been received from the other processors, in contrast with synchronous
 algorithms where it would wait those values before making a new

-iteration. Couturier et al.~\cite{Raphaelall01} proposed two methods
+iteration. Couturier and al.~\cite{Raphaelall01} proposed two methods

 of parallelization for a shared memory architecture with OpenMP and
 for a distributed memory one with MPI. They are able to compute the
 of parallelization for a shared memory architecture with OpenMP and
 for a distributed memory one with MPI. They are able to compute the

-roots of sparse polynomials of degree 10,000 in 116 seconds with
-OpenMP and 135 seconds with MPI only by using 8 personal computers and
-2 communications per iteration. The authors showed an interesting
-speedup comparing to the sequential implementation which takes up-to
-3,300 seconds to obtain same results. 
+roots of sparse polynomials of degree 10,000. The authors showed an interesting
+speedup that is 20 times as fast as the sequential implementation. 
+%which takes up-to 3,300 seconds to obtain same results. 

 \RC{si on donne des temps faut donner le proc, comme c'est vieux à mon avis faut supprimer ca, votre avis?} 
 \LZK{Supprimons ces détails et mettons une référence s'il y en a une}
 \RC{si on donne des temps faut donner le proc, comme c'est vieux à mon avis faut supprimer ca, votre avis?} 
 \LZK{Supprimons ces détails et mettons une référence s'il y en a une}

-
+\KG{Je viens de supprimer les détails, la référence existe déja, a reverifier}

 Very few work had been performed since then until the appearing of the Compute Unified Device Architecture (CUDA)~\cite{CUDA15}, a parallel computing platform and a programming model invented by NVIDIA. The computing power of GPUs (Graphics Processing Units) has exceeded that of traditional processors CPUs. However, CUDA adopts a totally new computing architecture to use the hardware resources provided by the GPU in order to offer a stronger computing ability to the massive data computing. Ghidouche et al.~\cite{Kahinall14} proposed an implementation of the Durand-Kerner method on a single GPU. Their main results showed that a parallel CUDA implementation is about 10 times faster than the sequential implementation on a single CPU for sparse polynomials of degree 48,000.
 
 In this paper we propose the parallelization of Ehrlich-Aberth method which has a good convergence and it is suitable to be implemented in parallel computers. We use two parallel programming paradigms OpenMP and MPI on CUDA multi-GPU platforms. Our CUDA-MPI and CUDA-OpenMP codes are the first implementations of Ehrlich-Aberth method with multiple GPUs for finding roots of polynomials. Our major contributions include:
 Very few work had been performed since then until the appearing of the Compute Unified Device Architecture (CUDA)~\cite{CUDA15}, a parallel computing platform and a programming model invented by NVIDIA. The computing power of GPUs (Graphics Processing Units) has exceeded that of traditional processors CPUs. However, CUDA adopts a totally new computing architecture to use the hardware resources provided by the GPU in order to offer a stronger computing ability to the massive data computing. Ghidouche et al.~\cite{Kahinall14} proposed an implementation of the Durand-Kerner method on a single GPU. Their main results showed that a parallel CUDA implementation is about 10 times faster than the sequential implementation on a single CPU for sparse polynomials of degree 48,000.
 
 In this paper we propose the parallelization of Ehrlich-Aberth method which has a good convergence and it is suitable to be implemented in parallel computers. We use two parallel programming paradigms OpenMP and MPI on CUDA multi-GPU platforms. Our CUDA-MPI and CUDA-OpenMP codes are the first implementations of Ehrlich-Aberth method with multiple GPUs for finding roots of polynomials. Our major contributions include:


@@ -109,7 +107,8 @@ In this paper we propose the parallelization of Ehrlich-Aberth method which has
 \item The parallel implementation of Ehrlich-Aberth algorithm on a multi-GPU platform with a distributed memory using MPI API, such that each GPU is attached and managed by a MPI process. The GPUs exchange their data by message-passing communications. 
  \end{itemize}
 This latter approach is more used on clusters to solve very complex problems that are too large for traditional supercomputers, which are very expensive to build and run.
 \item The parallel implementation of Ehrlich-Aberth algorithm on a multi-GPU platform with a distributed memory using MPI API, such that each GPU is attached and managed by a MPI process. The GPUs exchange their data by message-passing communications. 
  \end{itemize}
 This latter approach is more used on clusters to solve very complex problems that are too large for traditional supercomputers, which are very expensive to build and run.

-\LZK{Pas d'autres contributions possibles? J'ai supprimé les deux premiers points proposés précédemment.}
+\LZK{Pas d'autres contributions possibles? J'ai supprimé les deux premiers points proposés précédemment.
+\AS{La résolution du problème pour des polynomes pleins de degré 6M est une contribution aussi à mon avis}}

 
 The paper is organized as follows. In Section~\ref{sec2} we present three different parallel programming models OpenMP, MPI and CUDA. In Section~\ref{sec3} we present the implementation of the Ehrlich-Aberth algorithm on a single GPU. In Section~\ref{sec4} we present the parallel implementations of the Ehrlich-Aberth algorithm on multiple GPUs using the OpenMP and MPI approaches. In section~\ref{sec5} we present our experiments and discuss them. Finally, Section~\ref{sec6} concludes this paper and gives some hints for future research directions in this topic. 
 
 
 The paper is organized as follows. In Section~\ref{sec2} we present three different parallel programming models OpenMP, MPI and CUDA. In Section~\ref{sec3} we present the implementation of the Ehrlich-Aberth algorithm on a single GPU. In Section~\ref{sec4} we present the parallel implementations of the Ehrlich-Aberth algorithm on multiple GPUs using the OpenMP and MPI approaches. In section~\ref{sec5} we present our experiments and discuss them. Finally, Section~\ref{sec6} concludes this paper and gives some hints for future research directions in this topic. 
 


@@ -253,28 +252,31 @@ OpenMP and MPI is presented.
 \label{sec4}
 \subsection{an OpenMP-CUDA approach}
 Our OpenMP-CUDA implementation of EA algorithm is based on the hybrid
 \label{sec4}
 \subsection{an OpenMP-CUDA approach}
 Our OpenMP-CUDA implementation of EA algorithm is based on the hybrid

-OpenMP and CUDA programming model.  All the data are shared with
-OpenMP amoung all the OpenMP threads. The shared data are the solution
-vector $Z$, the polynomial to solve $P$, and the error vector $\Delta
-z$. The number of OpenMP threads is equal to the number of GPUs, each
-OpenMP thread binds to one GPU, and it controls a part of the shared
-memory. More precisely each OpenMP thread will be responsible to
-update its owns part of the vector Z. This part is call $Z_{loc}$ in
-the following. Then all GPUs will have a grid of computation organized
-according to the device performance and the size of data on which it
-runs the computation kernels.
+OpenMP and CUDA programming model. This algorithm is presented in
+Algorithm~\ref{alg2-cuda-openmp}.  All the data are shared with OpenMP
+amoung all the OpenMP threads. The shared data are the solution vector
+$Z$, the polynomial to solve $P$, its derivative $P'$, and the error
+vector $error$. The number of OpenMP threads is equal to the number of
+GPUs, each OpenMP thread binds to one GPU, and it controls a part of
+the shared memory. More precisely each OpenMP thread will be
+responsible to update its owns part of the vector $Z$. This part is
+called $Z_{loc}$ in the following. Then all GPUs will have a grid of
+computation organized according to the device performance and the size
+of data on which it 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
 
 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
-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
-used. The convergence is checked on the new roots (line 12). At the end
-of an iteration, the updated roots are copied from the GPU to the
-CPU (line 14) by direcly updating its own roots in the shared memory
-arrays containing all the roots.
+computation of the local size for each GPU is performed (line 4). Each
+thread starts by copying all the previous roots inside its GPU (line
+5). At each iteration, the following operations are performed. First
+the vector $Z$ is transferred from the CPU to the GPU (line 7).  Each
+GPU copies the previous roots (line 8) and it computes an iteration of
+the EA method on its own roots (line 9).  For that all the other roots
+are used. The local error is computed on the new roots (line 10) and
+the max of the local errors is computed on all OpenMP threads (lien 11). At
+the end of an iteration, the updated roots are copied from the GPU to
+the CPU (line 12) by direcly updating its own roots in the shared
+memory arrays containing all the roots.

 
 
 
 
 
 


@@ -306,27 +308,29 @@ Copy $P$, $P'$ from CPU to GPU\;
 
 \subsection{a MPI-CUDA approach}
 
 
 \subsection{a MPI-CUDA approach}
 

-Our parallel implementation of EA to find root of polynomials using a
-CUDA-MPI approach follows a similar computing approach to the one used
-in CUDA-OpenMP. Each process is responsible to compute its own part of
+Our parallel implementation of EA to find roots of polynomials using a
+CUDA-MPI approach follows a similar approach to the one used in
+CUDA-OpenMP. Each process is responsible to compute its own part of

 roots using all the roots computed by other processors at the previous
 iteration. The difference between both approaches lies in the way
 roots using all the roots computed by other processors at the previous
 iteration. The difference between both approaches lies in the way

-processes communicate and exchange data. With MPI processors need to
+processes communicate and exchange data. With MPI, processors need to

 send and receive data explicitely. So in
 Algorithm~\ref{alg2-cuda-mpi}, after the initialization all the
 processors have the same $Z$ vector. Then they need to compute the
 parameters used by the $MPI\_AlltoAll$ routines (line 4). In practise,
 send and receive data explicitely. So in
 Algorithm~\ref{alg2-cuda-mpi}, after the initialization all the
 processors have the same $Z$ vector. Then they need to compute the
 parameters used by the $MPI\_AlltoAll$ routines (line 4). In practise,

-each processor needs to compute its offset and its local size. Then
-processors need to allocate memory on their GPU (line 5). At the
-beginning of each iteration, a processor starts by transfering the
-whole vector Z from the CPU to the GPU (line 7). Then only the local
-part of $Z^{prev}$ is saved (line 8). After that, a processor is able
-to compute its own roots (line 9). Next, the local error can be
-computed (ligne 10) and the global error (line 11). Then the local
-roots are transfered from the GPU memory to the CPU memory (line 12)
-before being exchanged between all processors (linge 13) in order to
-give to all processors the last version of the roots. If the
-convergence is not statisfied, an new iteration is executed.
+each processor needs to compute its offset and its local
+size. Processors need to allocate memory on their GPU and need to copy
+their data on the GPU (line 5). At the beginning of each iteration, a
+processor starts by transfering the whole vector Z from the CPU to the
+GPU (line 7). Only the local part of $Z^{prev}$ is saved (line
+8). After that, a processor is able to compute an updated version of
+its own roots (line 9) with the EA method. The local error is computed
+(ligne 10) and the global error using $MPI\_Reduce$ (line 11). Then
+the local roots are transfered from the GPU memory to the CPU memory
+(line 12) before being exchanged between all processors (lige 13) in
+order to give to all processors the last version of the roots (with
+the MPI\_AlltoAll routine). If the convergence is not statisfied, an
+new iteration is executed.