new

diff --git a/paper.tex b/paper.tex
index 30470d18e20e9d66e979284e8fc502e63a72f0cd..936bd23bf98743e6b340113a8782a149f3575ebb 100644 (file)
--- a/paper.tex
+++ b/paper.tex
@@ -96,21 +96,25 @@ 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. The authors showed an interesting
 speedup that is 20 times as fast as the sequential implementation. 
 for a distributed memory one with MPI. They are able to compute the
 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}
-\KG{Je viens de supprimer les détails, la référence existe déja, a reverifier\LZK{Elle est où la référence?}}
-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. \LZK{Y a pas d'autres travaux pour la résolution de polynômes sur GPUs?}
+
+
+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. %\LZK{Y a pas d'autres travaux pour la résolution de polynômes sur GPUs?}

 
 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:
  \begin{itemize}
 
 \item The parallel implementation of Ehrlich-Aberth algorithm on a multi-GPU platform with a shared memory using OpenMP API. It is based on threads created from the same system process, such that each thread is attached to one GPU. In this case the communications between GPUs are done by OpenMP threads through shared memory.
 
 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:
  \begin{itemize}
 
 \item The parallel implementation of Ehrlich-Aberth algorithm on a multi-GPU platform with a shared memory using OpenMP API. It is based on threads created from the same system process, such that each thread is attached to one GPU. In this case the communications between GPUs are done by OpenMP threads through shared memory.

-\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. 
+\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.
+\item
+  Our method is efficient to compute the roots of sparse and full
+  polynomials of degree up to 5 millions.

  \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.
  \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.
-\AS{La résolution du problème pour des polynomes pleins de degré 6M est une contribution aussi à mon avis}}
+%\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. 
 


@@ -194,7 +198,16 @@ Q(z^k_i) = \exp(\ln(p(z^k_i)) - \ln(p'(z^k_i)) + \ln(\sum_{i\neq j}^n\frac{1}{z^
 
 
 
 
 
 

-Using the logarithm  and the exponential operators, we can replace any multiplications and divisions with additions and subtractions. Consequently, computations manipulate lower values in absolute values~\cite{Karimall98}. 
+Using the logarithm  and the exponential operators, we can replace any
+multiplications and divisions with additions and
+subtractions. Consequently, computations manipulate lower values in
+absolute values~\cite{Karimall98}. In practice, the  exponential and
+logarithm mode is used a root excepts the circle unit, represented by the radius $R$ evaluated in C language as :
+\begin{equation}
+\label{R.EL}
+R = exp(log(DBL\_MAX)/(2*n) );
+\end{equation}
+where \verb=DBL_MAX= stands for the maximum representable \verb=double= value.

 
 
 \subsection{The Ehrlich-Aberth parallel implementation on CUDA}
 
 
 \subsection{The Ehrlich-Aberth parallel implementation on CUDA}


@@ -218,7 +231,7 @@ 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
 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.\LZK{Quand est ce qu'on utilise un normal mode ou logarithm-exponential mode?}
+are transferred from the GPU to the CPU.%\LZK{Quand est ce qu'on utilise un normal mode ou logarithm-exponential mode?}

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