essaie de remettre l'algo openmp, je mettrai surement le MPI après

[kahina_paper2.git] / paper.tex

diff --git a/paper.tex b/paper.tex
index 5384818700adda22fb3a50b581e3ad4251742f4c..e826d2d01e4008b59b782c23de208e1972dc608d 100644 (file)
--- a/paper.tex
+++ b/paper.tex
@@ -178,7 +178,7 @@
 
 % *** SPECIALIZED LIST PACKAGES ***
 %
 
 % *** SPECIALIZED LIST PACKAGES ***
 %

-\usepackage{algorithmic}
+

 % algorithmic.sty was written by Peter Williams and Rogerio Brito.
 % This package provides an algorithmic environment fo describing algorithms.
 % You can use the algorithmic environment in-text or within a figure
 % algorithmic.sty was written by Peter Williams and Rogerio Brito.
 % This package provides an algorithmic environment fo describing algorithms.
 % You can use the algorithmic environment in-text or within a figure


@@ -351,22 +351,16 @@
 % author names and affiliations
 % use a multiple column layout for up to three different
 % affiliations
 % author names and affiliations
 % use a multiple column layout for up to three different
 % affiliations

-\author{\IEEEauthorblockN{Michael Shell}
-\IEEEauthorblockA{School of Electrical and\\Computer Engineering\\
-Georgia Institute of Technology\\
-Atlanta, Georgia 30332--0250\\
-Email: http://www.michaelshell.org/contact.html}
-\and
-\IEEEauthorblockN{Homer Simpson}
-\IEEEauthorblockA{Twentieth Century Fox\\
-Springfield, USA\\
-Email: homer@thesimpsons.com}
+\author{\IEEEauthorblockN{Kahina Guidouche, Abderrahmane Sider }
+  \IEEEauthorblockA{Laboratoire LIMED\\
+    Faculté des sciences exactes\\
+    Université de Bejaia, 06000, Algeria\\
+Email: \{kahina.ghidouche,ar.sider\}@univ-bejaia.dz}

 \and
 \and

-\IEEEauthorblockN{James Kirk\\ and Montgomery Scott}
-\IEEEauthorblockA{Starfleet Academy\\
-San Francisco, California 96678--2391\\
-Telephone: (800) 555--1212\\
-Fax: (888) 555--1212}}
+\IEEEauthorblockN{Lilia Ziane Khodja, Raphaël Couturier}
+\IEEEauthorblockA{FEMTO-ST Institute\\
+  University of   Bourgogne Franche-Comte, France\\
+Email: zianekhodja.lilia@gmail.com\\ raphael.couturier@univ-fcomte.fr}}

 
 % conference papers do not typically use \thanks and this command
 % is locked out in conference mode. If really needed, such as for
 
 % conference papers do not typically use \thanks and this command
 % is locked out in conference mode. If really needed, such as for


@@ -778,10 +772,10 @@ 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.
 
 paragraph Algorithm~\ref{alg1-cuda} shows the GPU parallel
 implementation of Ehrlich-Aberth method.
 

-\begin{enumerate}

 \begin{algorithm}[htpb]
 \label{alg1-cuda}
 \begin{algorithm}[htpb]
 \label{alg1-cuda}

-%\LinesNumbered
+\LinesNumbered
+\SetAlgoNoLine

 \caption{CUDA Algorithm to find roots with the Ehrlich-Aberth method}
 
 \KwIn{$Z^{0}$ (Initial root's vector), $\varepsilon$ (Error tolerance
 \caption{CUDA Algorithm to find roots with the Ehrlich-Aberth method}
 
 \KwIn{$Z^{0}$ (Initial root's vector), $\varepsilon$ (Error tolerance


@@ -791,27 +785,19 @@ implementation of Ehrlich-Aberth method.
 
 %\BlankLine
 
 
 %\BlankLine
 

-\item Initialization of P\;
-\item Initialization of Pu\;
-\item Initialization of the solution vector $Z^{0}$\;
-\item Allocate and copy initial data to the GPU global memory\;
-\item k=0\;
-\item \While {$\Delta z_{max} > \epsilon$}{
-\item   Let $\Delta z_{max}=0$\;
-\item   $ kernel\_save(ZPrec,Z)$\;
-\item   k=k+1\;
-\item   $ kernel\_update(Z,P,Pu)$\;
-\item $kernel\_testConverge(\Delta z_{max},Z,ZPrec)$\;
+Initialization of P\;
+Initialization of Pu\;
+Initialization of the solution vector $Z^{0}$\;
+Allocate and copy initial data to the GPU global memory\;
+\While {$\Delta z_{max} > \epsilon$}{
+   $ kernel\_save(ZPrec,Z)$\;
+   $ kernel\_update(Z,P,Pu)$\;
+ $\Delta z_{max}=kernel\_testConverge(Z,ZPrec)$\;

 
 }
 
 }

-\item Copy results from GPU memory to CPU memory\;
+Copy results from GPU memory to CPU memory\;

 \end{algorithm}
 \end{algorithm}

-\end{enumerate}
-~\\ 

 
 

-\RC{Au final, on laisse ce code, on l'explique, si c'est kahina qui
-  rajoute l'explication, il faut absolument ajouter \KG{dfsdfsd}, car
-  l'anglais sera à relire et je ne veux pas tout relire... }

  
 \section{The EA algorithm on Multiple GPUs}
 \label{sec4}
  
 \section{The EA algorithm on Multiple GPUs}
 \label{sec4}


@@ -868,43 +854,40 @@ shared memory arrays containing all the roots.
 %% roots sufficiently converge.
 
 
 %% roots sufficiently converge.
 
 

-%% \begin{enumerate}
-%% \begin{algorithm}[htpb]
-%% \label{alg2-cuda-openmp}
-%% %\LinesNumbered
-%% \caption{CUDA-OpenMP Algorithm to find roots with the Ehrlich-Aberth method}
-
-%% \KwIn{$Z^{0}$ (Initial root's vector), $\varepsilon$ (Error tolerance
-%%   threshold), P (Polynomial to solve), Pu (Derivative of P), $n$ (Polynomial degree), $\Delta z$ ( Vector of errors for stop condition), $num_gpus$ (number of OpenMP threads/ Number of GPUs), $Size$ (number of roots)}
-
-%% \KwOut {$Z$ ( Root's vector), $ZPrec$ (Previous root's vector)}
-
-%% \BlankLine
+\begin{algorithm}[htpb]
+\label{alg2-cuda-openmp}
+\LinesNumbered
+\SetAlgoNoLine
+\caption{CUDA-OpenMP Algorithm to find roots with the Ehrlich-Aberth method}

 
 

-%% \item Initialization of P\;
-%% \item Initialization of Pu\;
-%% \item Initialization of the solution vector $Z^{0}$\;
-%% \verb=omp_set_num_threads(num_gpus);=
-%% \verb=#pragma omp parallel shared(Z,$\Delta$ z,P);=
-%% \verb=cudaGetDevice(gpu_id);=
-%% \item Allocate and copy initial data from CPU memory to the GPU global memories\;
-%% \item index= $Size/num\_gpus$\;
-%% \item k=0\;
-%% \While {$error > \epsilon$}{
-%% \item Let $\Delta z=0$\;
-%% \item $ kernel\_save(ZPrec,Z)$\;
-%% \item  k=k+1\;
-%% \item $ kernel\_update(Z,P,Pu,index)$\;
-%% \item $kernel\_testConverge(\Delta z[gpu\_id],Z,ZPrec)$\;
-%% %\verb=#pragma omp barrier;=
-%% \item error= Max($\Delta z$)\;
-%% }
+\KwIn{$Z^{0}$ (Initial root's vector), $\varepsilon$ (Error tolerance
+  threshold), P (Polynomial to solve), Pu (Derivative of P), $n$ (Polynomial degree), $\Delta z$ ( Vector of errors for stop condition), $num\_gpus$ (number of OpenMP threads/ Number of GPUs), $Size$ (number of roots)}
+
+\KwOut {$Z$ ( Root's vector), $ZPrec$ (Previous root's vector)}
+
+\BlankLine
+
+Initialization of P\;
+Initialization of Pu\;
+Initialization of the solution vector $Z^{0}$\;
+omp\_set\_num\_threads(num\_gpus)\;
+\#pragma omp parallel shared(Z,$\Delta$ z,P)\;
+\Indp
+{
+gpu\_id=cudaGetDevice()\;
+Allocate memory on GPU\;
+Compute local size and offet according to gpu\_id\;
+\While {$error > \epsilon$}{
+  copy Z from CPU to GPU\;
+$ ZPrec_{loc}=kernel\_save(Z_{loc})$\;
+$ Z_{loc}=kernel\_update(Z,P,Pu)$\;
+$\Delta z[gpu\_id] = kernel\_testConv(Z_{loc},ZPrec_{loc})$\;
+$  error= Max(\Delta z)$\;
+  copy $Z_{loc}$ from GPU to Z in CPU
+}
+\Indm}
+\end{algorithm}

 
 

-%% \item Copy results from GPU memories to CPU memory\;
-%% \end{algorithm}
-%% \end{enumerate}
-%% ~\\ 
-%% \RC{C'est encore pire ici, on ne voit pas les comm CPU <-> GPU }

 
 
 \subsection{Multi-GPU : an MPI-CUDA approach}
 
 
 \subsection{Multi-GPU : an MPI-CUDA approach}


@@ -990,7 +973,8 @@ In this experiments we report the execution time of the EA algorithm, on single
 \begin{figure}[htbp]
 \centering
   \includegraphics[angle=-90,width=0.5\textwidth]{Sparse_omp}
 \begin{figure}[htbp]
 \centering
   \includegraphics[angle=-90,width=0.5\textwidth]{Sparse_omp}

-\caption{Execution time in seconds of the Ehrlich-Aberth method to solve sparse polynomials on multiple GPUs.}
+\caption{Execution time in seconds of the Ehrlich-Aberth method to
+  solve sparse polynomials on multiple GPUs with CUDA-OpenMP.}

 \label{fig:01}
 \end{figure}
 
 \label{fig:01}
 \end{figure}
 


@@ -1005,7 +989,8 @@ These experiments show the execution times of the EA algorithm, on a single GPU
 \begin{figure}[htbp]
 \centering
   \includegraphics[angle=-90,width=0.5\textwidth]{Full_omp}
 \begin{figure}[htbp]
 \centering
   \includegraphics[angle=-90,width=0.5\textwidth]{Full_omp}

-\caption{Execution time in seconds of the Ehrlich-Aberth method to solve full polynomials on multiple GPUs}
+\caption{Execution time in seconds of the Ehrlich-Aberth method to
+  solve full polynomials on multiple GPUs with CUDA-OpenMP.}

 \label{fig:02}
 \end{figure}
 
 \label{fig:02}
 \end{figure}
 


@@ -1023,7 +1008,8 @@ approach to solve full and sparse polynomials of degrees ranging from
 \begin{figure}[htbp]
 \centering
   \includegraphics[angle=-90,width=0.5\textwidth]{Sparse_mpi}
 \begin{figure}[htbp]
 \centering
   \includegraphics[angle=-90,width=0.5\textwidth]{Sparse_mpi}

-\caption{Execution time in seconds of the Ehrlich-Aberth method to solve sparse polynomials on multiple GPUs.}
+\caption{Execution time in seconds of the Ehrlich-Aberth method to
+  solve sparse polynomials on multiple GPUs with CUDA-MPI.}

 \label{fig:03}
 \end{figure}
 Figure~\ref{fig:03} shows the execution times of te EA algorithm,
 \label{fig:03}
 \end{figure}
 Figure~\ref{fig:03} shows the execution times of te EA algorithm,


@@ -1034,25 +1020,36 @@ for a single GPU, and multiple GPUs (2, 3, 4) with the CUDA-MPI approach.
 \begin{figure}[htbp]
 \centering
  \includegraphics[angle=-90,width=0.5\textwidth]{Full_mpi}
 \begin{figure}[htbp]
 \centering
  \includegraphics[angle=-90,width=0.5\textwidth]{Full_mpi}

-\caption{Execution times in seconds of the Ehrlich-Aberth method for full polynomials on GPUs using the Multi-GPU}
+\caption{Execution times in seconds of the Ehrlich-Aberth method for
+  full polynomials on  multiple GPUs with CUDA-MPI.}

 \label{fig:04}
 \end{figure}
 
 In Figure~\ref{fig:04}, we can also observe that the CUDA-MPI approach
 is also efficient to solve full polynimails on multiple GPUs.
 \label{fig:04}
 \end{figure}
 
 In Figure~\ref{fig:04}, we can also observe that the CUDA-MPI approach
 is also efficient to solve full polynimails on multiple GPUs.

-\subsection{Comparing  the CUDA-OpenMP approach and the CUDA-MPI approach}

 
 

-In the previuos section we saw that both approches are very effective in reducing execution time for sparse as well as full polynomials. At this stage, the interesting question is which approach is better. In the fellowing, we present appropriate experiments comparing the two Multi-GPU approaches to answer the question.
+\subsection{Comparison of  the CUDA-OpenMP and the CUDA-MPI approaches}
+
+In the previuos section we saw that both approches are very effecient
+to  reduce the execution times the  sparse and full polynomials. In
+this section we try to compare these two approaches.

 
 \subsubsection{Solving sparse polynomials}
 In this experiment three sparse polynomials of size 200K, 800K and 1,4M are investigated.
 \begin{figure}[htbp]
 \centering
  \includegraphics[angle=-90,width=0.5\textwidth]{Sparse}
 
 \subsubsection{Solving sparse polynomials}
 In this experiment three sparse polynomials of size 200K, 800K and 1,4M are investigated.
 \begin{figure}[htbp]
 \centering
  \includegraphics[angle=-90,width=0.5\textwidth]{Sparse}

-\caption{Execution time  for solving sparse polynomials of three distinct sizes on multiple GPUs using MPI and OpenMP approaches using Ehrlich-Aberth}
+\caption{Execution times  to solvs sparse polynomials of three
+  distinct sizes on multiple GPUs using MPI and OpenMP with the
+  Ehrlich-Aberth method}

 \label{fig:05}
 \end{figure}
 \label{fig:05}
 \end{figure}

-In Figure~\ref{fig:05} there two curves for each polynomial size : one for the MPI-CUDA and another for the OpenMP. We can see that the results are similar between OpenMP and MPI for the polynomials size of 200K. For the size of 800K, the MPI version is a little slower than the OpenMP approach but for the 1,4 millions size, there is a slight advantage for the MPI version.
+In Figure~\ref{fig:05} there is one curve for CUDA-MPI and another one
+for CUDA-OpenMP. We can see that the results are quite similar between
+OpenMP and MPI for the polynomials size of 200K. For the size of 800K,
+the MPI version is a little bit slower than the OpenMP approach but for
+the 1,4 millions size, there is a slight advantage for the MPI
+version.

 
 \subsubsection{Solving full polynomials}
 \begin{figure}[htbp]
 
 \subsubsection{Solving full polynomials}
 \begin{figure}[htbp]


@@ -1064,14 +1061,22 @@ In Figure~\ref{fig:05} there two curves for each polynomial size : one for the M
 In Figure~\ref{fig:06}, we can see that when it comes to full polynomials, both approaches are almost equivalent.
 
 \subsubsection{Solving sparse and full polynomials of the same size with CUDA-MPI}
 In Figure~\ref{fig:06}, we can see that when it comes to full polynomials, both approaches are almost equivalent.
 
 \subsubsection{Solving sparse and full polynomials of the same size with CUDA-MPI}

-In this experiment we compare the execution time of the EA algorithm according to the number of GPUs for solving sparse and full polynomials on Multi-GPU using MPI. We chose three sparse and full polynomials of size 200K, 800K  and 1,4M. 
+
+In this experiment we compare the execution time of the EA algorithm
+according to the number of GPUs to solve sparse and full
+polynomials on multiples GPUs using MPI. We chose three sparse and full
+polynomials of size 200K, 800K and 1,4M.

 \begin{figure}[htbp]
 \centering
  \includegraphics[angle=-90,width=0.5\textwidth]{MPI}
 \begin{figure}[htbp]
 \centering
  \includegraphics[angle=-90,width=0.5\textwidth]{MPI}

-\caption{Execution time for solving sparse and full polynomials of three distinct sizes on multiple GPUs using MPI}
+\caption{Execution times to solve sparse and full polynomials of three distinct sizes on multiple GPUs using MPI.}

 \label{fig:07}
 \end{figure}
 \label{fig:07}
 \end{figure}

-in figure ~\ref{fig:07} we can see that CUDA-MPI can solve sparse and full polynomials of high degrees, the execution time with sparse polynomial are very low comparing to full polynomials. with sparse polynomials the number of monomial are reduce, consequently the number of operation are reduce than the execution time decrease. 
+In Figure~\ref{fig:07} we can see that CUDA-MPI can solve sparse and
+full polynomials of high degrees, the execution times with sparse
+polynomial are very low compared to full polynomials. With sparse
+polynomials the number of monomials is reduced, consequently the number
+of operations is reduced and the execution time decreases.

 
 \subsubsection{Solving sparse and full polynomials of the same size with CUDA-OpenMP}
 
 
 \subsubsection{Solving sparse and full polynomials of the same size with CUDA-OpenMP}
 


@@ -1082,17 +1087,23 @@ in figure ~\ref{fig:07} we can see that CUDA-MPI can solve sparse and full polyn
 \label{fig:08}
 \end{figure}
 
 \label{fig:08}
 \end{figure}
 

-Figure ~\ref{fig:08} shows the impact of sparsity on the effectiveness of the CUDA-OpenMP approach. We can see that the impact fellows the same pattern, a difference in execution time in favor of the sparse polynomials. 
-%SIDER : il faut une explication ici. je ne vois pas de prime abords, qu'est-ce qui engendre cette différence, car quelques soient les coefficients nulls ou non nulls, c'est toutes les racines qui sont calculées qu'elles soient similaires ou non (degrés de multiplicité).
-\subsection{Scalability of the EA method on Multi-GPU to solve very high degree polynomials}
-These experiments report the execution time according to the degrees of polynomials ranging from 1,000,000 to 5,000,000 for both approaches with sparse and full  polynomials. 
+Figure ~\ref{fig:08} shows the impact of sparsity on the effectiveness of the CUDA-OpenMP approach. We can see that the impact follows the same pattern, a difference in execution time in favor of the sparse polynomials. 
+
+\subsection{Scalability of the EA method on multiple GPUs to solve very high degree polynomials}
+These experiments report the execution times of the EA method for
+sparse and full polynomials ranging from 1,000,000 to 5,000,000.

 \begin{figure}[htbp]
 \centering
  \includegraphics[angle=-90,width=0.5\textwidth]{big}
  \caption{Execution times in seconds of the Ehrlich-Aberth method for solving full polynomials of high degree on 4 GPUs for sizes ranging from 1M to 5M}
 \label{fig:09}
 \end{figure}
 \begin{figure}[htbp]
 \centering
  \includegraphics[angle=-90,width=0.5\textwidth]{big}
  \caption{Execution times in seconds of the Ehrlich-Aberth method for solving full polynomials of high degree on 4 GPUs for sizes ranging from 1M to 5M}
 \label{fig:09}
 \end{figure}

-In figure ~\ref{fig:09} we can see that both approaches are scalable and can solve very high degree polynomials. With full polynomial both approaches give interestingly very similar results. For the sparse case however, there are a noticeable difference in favour of MPI when the degree is above 4M. Between 1M and 3M, the OMP approach is more effective and under 1M degree, OMP and MPI approaches are almost equivalent.
+In Figure~\ref{fig:09} we can see that both approaches are scalable
+and can solve very high degree polynomials. With full polynomial both
+approaches give very similar results. However, for sparse polynomials
+there are a noticeable difference in favour of MPI when the degree is
+above 4 millions. Between 1  and 3 millions, OpenMP is more effecient.
+Under 1 million, OpenMPI and MPI are almost equivalent.

 
 %SIDER : il faut une explication sur les différences ici aussi.
  
 
 %SIDER : il faut une explication sur les différences ici aussi.
  


@@ -1196,13 +1207,25 @@ In figure ~\ref{fig:09} we can see that both approaches are scalable and can sol
 
 \section{Conclusion}
 \label{sec6}
 
 \section{Conclusion}
 \label{sec6}

-In this paper, we have presented a parallel implementation of Ehrlich-Aberth algorithm for solving full and sparse polynomials, on single GPU with CUDA and on multiple GPUs using two parallel paradigms : shared memory with OpenMP and distributed memory with MPI. These architectures were addressed by a CUDA-OpenMP approach and CUDA-MPI approach, respectively. 
-The experiments show that, using parallel programming model like (OpenMP, MPI), we can efficiently manage multiple graphics cards to work together to solve the same problem and accelerate the parallel execution with 4 GPUs and solve a polynomial of degree 1,000,000, four times faster than on single GPU, that is a quasi-linear speedup.
+In this paper, we have presented a parallel implementation of
+Ehrlich-Aberth algorithm to solve full and sparse polynomials, on
+single GPU with CUDA and on multiple GPUs using two parallel
+paradigms: shared memory with OpenMP and distributed memory with
+MPI. These architectures were addressed by a CUDA-OpenMP approach and
+CUDA-MPI approach, respectively.  Experiments show that, using
+parallel programming model like (OpenMP, MPI). We can efficiently
+manage multiple graphics cards to solve the same
+problem and accelerate the parallel execution with 4 GPUs and solve a
+polynomial of degree up to 5,000,000, four times faster than on single
+GPU. 

 
 
 %In future, we will evaluate our parallel implementation of Ehrlich-Aberth algorithm on other parallel programming model 
 
 
 
 %In future, we will evaluate our parallel implementation of Ehrlich-Aberth algorithm on other parallel programming model 
 

-Our next objective is to extend the model presented here at clusters of nodes featuring  multiple GPUs, with a three-level scheme: inter-node communication via MPI processes (distributed memory), management of multi-GPU node by OpenMP threads (shared memory).
+Our next objective is to extend the model presented here with clusters
+of GPU nodes, with a three-level scheme: inter-node communication via
+MPI processes (distributed memory), management of multi-GPU node by
+OpenMP threads (shared memory).

 
 %present a communication approach between multiple GPUs. The comparison between MPI and OpenMP as GPUs controllers shows that these
 %solutions can effectively manage multiple graphics cards to work together
 
 %present a communication approach between multiple GPUs. The comparison between MPI and OpenMP as GPUs controllers shows that these
 %solutions can effectively manage multiple graphics cards to work together


@@ -1220,8 +1243,10 @@ Our next objective is to extend the model presented here at clusters of nodes fe
 % use section* for acknowledgment
 \section*{Acknowledgment}
 
 % use section* for acknowledgment
 \section*{Acknowledgment}
 

+Computations have been performed on the supercomputer facilities of
+the Mésocentre de calcul de Franche-Comté. We also would like to thank
+Nvidia for hardware donation under CUDA Research Center 2014.

 
 

-The authors would like to thank...