new

[kahina_paper2.git] / maj.tex

diff --git a/maj.tex b/maj.tex
index fe899a307a0a0c0affa2e5590f53d3c106dd03d7..ef1900914cd89dfa03a63bdcb19f95fd9c3829bb 100644 (file)
--- a/maj.tex
+++ b/maj.tex
@@ -9,7 +9,8 @@
 \usepackage[textsize=footnotesize]{todonotes}
 \usepackage{amsmath}
 \usepackage{amssymb}
 \usepackage[textsize=footnotesize]{todonotes}
 \usepackage{amsmath}
 \usepackage{amssymb}

-\usepackage{float} 
+\usepackage{float}
+\usepackage{listings}

 \newcommand{\LZK}[2][inline]{%
   \todo[color=red!10,#1]{\sffamily\textbf{LZK:} #2}\xspace}
 \newcommand{\RC}[2][inline]{%
 \newcommand{\LZK}[2][inline]{%
   \todo[color=red!10,#1]{\sffamily\textbf{LZK:} #2}\xspace}
 \newcommand{\RC}[2][inline]{%


@@ -32,7 +33,7 @@ Email: \{kahina.ghidouche,ar.sider\}@univ-bejaia.dz}
 \and
 \IEEEauthorblockN{Lilia Ziane Khodja, Raphaël Couturier}
 \IEEEauthorblockA{FEMTO-ST Institute\\
 \and
 \IEEEauthorblockN{Lilia Ziane Khodja, Raphaël Couturier}
 \IEEEauthorblockA{FEMTO-ST Institute\\

-  University of   Bourgogne Franche-Comte, France\\
+  University  Bourgogne Franche-Comte, France\\

 Email: zianekhodja.lilia@gmail.com\\ raphael.couturier@univ-fcomte.fr}}
 
 
 Email: zianekhodja.lilia@gmail.com\\ raphael.couturier@univ-fcomte.fr}}
 
 


@@ -275,10 +276,10 @@ where \verb=DBL_MAX= stands for the maximum representable
 
 
 \subsection{The Ehrlich-Aberth parallel implementation on CUDA}
 
 
 \subsection{The Ehrlich-Aberth parallel implementation on CUDA}

-\KG{Je viens de refaire cette section}

 The algorithm ~\ref{alg1-cuda} shows sketch of the Ehrlich-Aberth method using CUDA.
 The algorithm ~\ref{alg1-cuda} shows sketch of the Ehrlich-Aberth method using CUDA.

-The first steps consist in the initialization of the input data like, the polynomial P,derivative of P and the vector solution Z. Then, all data of the root finding problem
-must be copied from the CPU memory to the GPU global memory,because
+The first step consists in the initialization of the input data, for
+exemple the polynomial P, the derivative of P and the vector solution Z. Then, all data of the root finding problem
+are transfered from the CPU memory to the GPU global memory, because

 the GPUs only work on the data filled in their memories.
 Next, all the data-parallel arithmetic operations inside the main loop
 \verb=(while(...))= are executed as kernels by the GPU. The
 the GPUs only work on the data filled in their memories.
 Next, all the data-parallel arithmetic operations inside the main loop
 \verb=(while(...))= are executed as kernels by the GPU. The


@@ -287,7 +288,7 @@ order to check the convergence of the roots after each iteration (line
 7, Algorithm~\ref{alg1-cuda}). Then the new roots with the
 new iterations are computed using the EA method with a Gauss-Seidel
 iteration mode in order to use the latest updated roots (line
 7, Algorithm~\ref{alg1-cuda}). Then the new roots with the
 new iterations are computed using the EA method with a Gauss-Seidel
 iteration mode in order to use the latest updated roots (line

-6). This improves the convergence. This kernel is, in practice, very
+6). This improves the convergence compared to the Jacobi method. This kernel is, in practice, very

 long since it performs all the operations with complex numbers with
 the normal mode of the EA method as in Eq.~\ref{Eq:EA1} but also with the logarithm-exponential one as in Eq.(~\ref{Log_H1},~\ref{Log_H2}). The last kernel checks the convergence of the roots after each update of $Z^{k}$, according to formula Eq.~\ref{eq:Aberth-Conv-Cond} line (7). We used the functions of the CUBLAS Library (CUDA Basic Linear Algebra Subroutines) to implement this kernel. The algorithm terminates its computations when all the roots have
 converged.
 long since it performs all the operations with complex numbers with
 the normal mode of the EA method as in Eq.~\ref{Eq:EA1} but also with the logarithm-exponential one as in Eq.(~\ref{Log_H1},~\ref{Log_H2}). The last kernel checks the convergence of the roots after each update of $Z^{k}$, according to formula Eq.~\ref{eq:Aberth-Conv-Cond} line (7). We used the functions of the CUBLAS Library (CUDA Basic Linear Algebra Subroutines) to implement this kernel. The algorithm terminates its computations when all the roots have
 converged.


@@ -310,7 +311,7 @@ converged.
 %are transferred from the GPU to the CPU.
 \begin{algorithm}[htpb]
 \label{alg1-cuda}
 %are transferred from the GPU to the CPU.
 \begin{algorithm}[htpb]
 \label{alg1-cuda}

-%\LinesNumbered
+\LinesNumbered

 %\SetAlgoNoLine
 \caption{Finding roots of polynomials with the Ehrlich-Aberth method on a GPU}
 \KwIn{ $\epsilon$ (tolerance threshold)}
 %\SetAlgoNoLine
 \caption{Finding roots of polynomials with the Ehrlich-Aberth method on a GPU}
 \KwIn{ $\epsilon$ (tolerance threshold)}


@@ -326,13 +327,22 @@ Copy $P$, $P'$ and $Z$ from CPU to GPU\;
 Copy $Z$ from GPU to CPU\;
 \end{algorithm}
 
 Copy $Z$ from GPU to CPU\;
 \end{algorithm}
 

-This figure shows the second kernel code
-\begin{figure}[htbp]
-\centering
-\includegraphics[angle=+0,width=0.4\textwidth]{code1}
-\caption{The Kernel Update code}
-\label{fig:00}
-\end{figure}
+Listing~\ref{lst:01} shows the a simplified version of second kernel
+code (some parameters in the kernels have been simplified in order to
+increase the readability). As can be seen this
+kernel calls multiple kernels, all the kernals for complex numbers and
+kernels for the evaluation of a polynomial are not detailed. 
+
+\begin{footnotesize}
+\lstinputlisting[label=lst:01,caption=Kernels to update the roots]{code.c}
+\end{footnotesize}
+
+%\begin{figure}[htbp]
+%\centering
+%\includegraphics[angle=+0,width=0.4\textwidth]{code}
+%\caption{The Kernel Update code}
+%\label{fig:00}
+%\end{figure}

 
 %We noticed that the code is executed by a large number of GPU threads organized as grid of to dimension (Number of block per grid (NbBlock), number of threads per block(Nbthread)), the Nbthread is fixed initially, the NbBlock is computed as fallow: 
 %$ NbBlocks= \frac{N+Nbthreads-1}{Nbthreads} where N: the number of root$
 
 %We noticed that the code is executed by a large number of GPU threads organized as grid of to dimension (Number of block per grid (NbBlock), number of threads per block(Nbthread)), the Nbthread is fixed initially, the NbBlock is computed as fallow: 
 %$ NbBlocks= \frac{N+Nbthreads-1}{Nbthreads} where N: the number of root$


@@ -347,7 +357,9 @@ Ehrlich-Aberth method with OpenMP and MPI is presented.
 
 \section{The Ehrlich-Aberth algorithm on multiple GPUs}
 \label{sec4}
 
 \section{The Ehrlich-Aberth algorithm on multiple GPUs}
 \label{sec4}

-\KG{we remind that to manage the CUDA contexts of different GPUs, We investigate two parallel paradigms: OpenMP and MPI. In this section we present the both \textit{OpenMP-CUDA} approach and the \textit{MPI-CUDA} approach used to implement the Ehrlich-Aberth algorithm on multiple GPUs.}
+In order  to manage the CUDA contexts of different GPUs, two parallel
+paradigms are investigated: OpenMP and MPI. In this section we present
+ the \textit{OpenMP-CUDA}  and the \textit{MPI-CUDA} approaches used to implement the Ehrlich-Aberth algorithm on multiple GPUs.

 
 \subsection{An OpenMP-CUDA approach}
 Our OpenMP-CUDA implementation of EA algorithm is based on the hybrid
 
 \subsection{An OpenMP-CUDA approach}
 Our OpenMP-CUDA implementation of EA algorithm is based on the hybrid


@@ -381,7 +393,7 @@ memory arrays containing all the roots.
 
 \begin{algorithm}[htpb]
 \label{alg2-cuda-openmp}
 
 \begin{algorithm}[htpb]
 \label{alg2-cuda-openmp}

-%\LinesNumbered
+\LinesNumbered

 %\SetAlgoNoLine
 \caption{Finding roots of polynomials with the Ehrlich-Aberth method on multiple GPUs using OpenMP}
 \KwIn{ $\epsilon$ (tolerance threshold)}
 %\SetAlgoNoLine
 \caption{Finding roots of polynomials with the Ehrlich-Aberth method on multiple GPUs using OpenMP}
 \KwIn{ $\epsilon$ (tolerance threshold)}


@@ -432,7 +444,7 @@ new iteration is executed.
 
 \begin{algorithm}[htpb]
 \label{alg2-cuda-mpi}
 
 \begin{algorithm}[htpb]
 \label{alg2-cuda-mpi}

-%\LinesNumbered
+\LinesNumbered

 %\SetAlgoNoLine
 \caption{Finding roots of polynomials with the Ehrlich-Aberth method on multiple GPUs using MPI}
 
 %\SetAlgoNoLine
 \caption{Finding roots of polynomials with the Ehrlich-Aberth method on multiple GPUs using MPI}
 


@@ -471,8 +483,8 @@ We study two categories of polynomials: sparse polynomials and full polynomials.
      {\Large \forall \alpha_{i} \in \mathbb{C}, i\in \mathbb{N};  p(x)=\sum^{n}_{i=0} \alpha_{i}.x^{i}} 
 \end{equation}
 
      {\Large \forall \alpha_{i} \in \mathbb{C}, i\in \mathbb{N};  p(x)=\sum^{n}_{i=0} \alpha_{i}.x^{i}} 
 \end{equation}
 

-\KG{For our tests, a CPU Intel(R) Xeon(R) CPU
-X5650@2.40GHz and 4 GPUs cards Tesla Kepler K40,are used with CUDA version 7.5}.
+For our tests, a CPU Intel(R) Xeon(R) CPU
+X5650@2.40GHz and 4 GPUs cards Tesla Kepler K40, are used with CUDA version 7.5.

  
  In order to evaluate both the GPU and Multi-GPU approaches, we performed a set of
 experiments on a single GPU and multiple GPUs using OpenMP or MPI with
  
  In order to evaluate both the GPU and Multi-GPU approaches, we performed a set of
 experiments on a single GPU and multiple GPUs using OpenMP or MPI with


@@ -585,7 +597,7 @@ Our next objective is to extend the model presented here to clusters of GPU node
 
 \section*{Acknowledgment}
 This  paper  is   partially  funded  by  the  Labex   ACTION  program  (contract
 
 \section*{Acknowledgment}
 This  paper  is   partially  funded  by  the  Labex   ACTION  program  (contract

-ANR-11-LABX-01-01). 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.
+ANR-11-LABX-01-01) and the Franche-Comte regional council. 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.

 
 
 \bibliography{mybibfile}
 
 
 \bibliography{mybibfile}