\maketitle
\begin{abstract}
-Finding roots of polynomials is a very important part of solving
-real-life problems but it is not so easy for polynomials of high
-degrees. In this paper, we present two different parallel algorithms
-of the Ehrlich-Aberth method to find roots of sparse and fully defined
-polynomials of high degrees. Both algorithms are based on CUDA
-technology to be implemented on multi-GPU computing platforms but each
-using different parallel paradigms: OpenMP or MPI. The experiments
-show a quasi-linear speedup by using up-to 4 GPU devices compared to 1
-GPU to find roots of polynomials of degree up-to 1.4
-million. Moreover, other experiments show it is possible to find roots
-of polynomials of degree up-to 5 millions.
+Finding the roots of polynomials is a very important part of solving
+real-life problems but the higher the degree of the polynomials is,
+the less easy it becomes. In this paper, we present two different
+parallel algorithms of the Ehrlich-Aberth method to find roots of
+sparse and fully defined polynomials of high degrees. Both algorithms
+are based on CUDA technology to be implemented on multi-GPU computing
+platforms but each use different parallel paradigms: OpenMP or
+MPI. The experiments show a quasi-linear speedup by using up-to 4 GPU
+devices compared to 1 GPU to find the roots of polynomials of degree up-to
+1.4 million. Moreover, other experiments show it is possible to find the
+roots of polynomials of degree up-to 5 million.
\end{abstract}
\begin{IEEEkeywords}
\section{Introduction}
-Finding roots of polynomials of very high degrees arises in many complex problems of various domains such as algebra, biology or physics. A polynomial $p(x)$ in $\mathbb{C}$ in one variable $x$ is an algebraic expression in $x$ of the form:
+Finding the roots of polynomials of very high degrees arises in many complex problems of various domains such as algebra, biology or physics. A polynomial $p(x)$ in $\mathbb{C}$ in one variable $x$ is an algebraic expression in $x$ of the form:
\begin{equation}
p(x) = \displaystyle\sum^n_{i=0}{\alpha_ix^i},\alpha_n\neq 0,
\end{equation}
p(x)=\alpha_n\displaystyle\prod_{i=1}^n(x-z_i), \alpha_n\neq 0.
\end{equation}
-Most of the numerical methods that deal with the polynomial root-finding problem are simultaneous methods, \textit{i.e.} the iterative methods to find simultaneous approximations of the $n$ polynomial roots. These methods start from the initial approximations of all $n$ polynomial roots and give a sequence of approximations that converge to the roots of the polynomial. Two examples of well-known simultaneous methods for root-finding problem of polynomials are Durand-Kerner method~\cite{Durand60,Kerner66} and Ehrlich-Aberth method~\cite{Ehrlich67,Aberth73}.
-
-
-The convergence time of simultaneous methods drastically increases with the increasing of the polynomial's degree. The great challenge with simultaneous methods is to parallelize them and to improve their convergence. Many authors have proposed parallel simultaneous methods~\cite{Freeman89,Loizou83,Freemanall90,cs01:nj,Couturier02}, using several paradigms of parallelization (synchronous or asynchronous computations, mechanism of shared or distributed memory, etc). However, they have treated only polynomials not exceeding degrees of 20,000.
+Most of the numerical methods that deal with the polynomial
+root-finding problems are simultaneous methods, \textit{i.e.} the
+iterative methods to find simultaneous approximations of the $n$
+polynomial roots. These methods start from the initial approximation
+of all $n$ polynomial roots and give a sequence of approximations that
+converge to the roots of the polynomial. Two examples of well-known
+simultaneous methods for root-finding problem of polynomials are
+the Durand-Kerner method~\cite{Durand60,Kerner66} and the Ehrlich-Aberth method~\cite{Ehrlich67,Aberth73}.
+
+
+The convergence time of simultaneous methods drastically increases
+with the increasing of the polynomial's degree. The great challenge
+with simultaneous methods is to parallelize them and to improve their
+convergence. Many authors have proposed parallel simultaneous
+methods~\cite{Freeman89,Loizou83,Freemanall90,bini96,cs01:nj,Couturier02},
+using several paradigms of parallelization (synchronous or
+asynchronous computations, mechanism of shared or distributed memory,
+etc). However, so fat until now, only polynomials not exceeding
+degrees of less than 100,000 have been solved.
%The main problem of the simultaneous methods is that the necessary
%time needed for the convergence increases with the increasing of 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.
-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.
+With the recent advent of the Compute Unified Device Architecture
+(CUDA)~\cite{CUDA15}, a parallel computing platform and a programming
+model invented by NVIDIA had revived parallel programming interest for
+this problem. Indeed, the computing power of GPUs (Graphics Processing
+Units) has exceeded that of traditional CPUs processors, which makes it very appealing to the research community to investigate new parallel implementations for a whole set of scientific problems in the reasonable hope to solve bigger instances of well known computationally demanding issues such as the one beforehand. 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:
+In this paper we propose the parallelization of the Ehrlich-Aberth (EA) method which has a cubic convergence rate which is much better than the quadratic rate of the Durand-Kerner method which has already been investigated in \cite{Kahinall14}. In the other hand, EA is suitable to be implemented in parallel computers according to the data-parallel paradigm. In this model, computing elements carry computations on the data they are assigned and communicate with other computing elements in order to get fresh data or to synchronise. Classically, two parallel programming paradigms OpenMP and MPI are used to code such solutions. But in our case, computing elements are CUDA multi-GPU platforms. This architectural setting poses new programming challenges but offers also new opportunities to efficiently solve huge problems, otherwise considered intractable until recently. To the best of our knowledge, our CUDA-MPI and CUDA-OpenMP codes are the first implementations of EA 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
+\item The parallel implementation of EA 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 EA 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.
+ exchange their data by message-passing communications. This 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
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.
+
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.
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, \LZK{Je n'ai pas compris cette phrase!} represented by the radius $R$ evaluated in C language as :
+logarithm mode is used when a root is outisde the circle unit represented by the radius $R$ evaluated in C language with:
\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.
+where \verb=DBL_MAX= stands for the maximum representable
+\verb=double= value and $n$ is the degree of the polynimal.
\subsection{The Ehrlich-Aberth parallel implementation on CUDA}
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.
\begin{algorithm}[htpb]
\label{alg1-cuda}
\subsection{A MPI-CUDA approach}
-
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
\section{Conclusion}
\label{sec6}
-In this paper, we have presented parallel implementations of the Ehrlich-Aberth algorithm to solve full and sparse polynomials, on a 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 or 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 this paper, we have presented parallel implementations of the Ehrlich-Aberth algorithm to solve full and sparse polynomials, on a 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 or 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 a single GPU.
-Our next objective is to extend the model presented here with clusters of GPU nodes, with a three-level scheme: inter-node communications via MPI processes (distributed memory), management of multi-GPU nodes by OpenMP threads (shared memory).
+Our next objective is to extend the model presented here to clusters of GPU nodes, with a three-level scheme: inter-node communications via MPI processes (distributed memory), management of multi-GPU nodes by OpenMP threads (shared memory). Actual platforms may probably also contain purely multi-core nodes without any GPU. This heterogeneous setting may lead to the integration of load balancing algorithms so as to allow an optimal use of hardware ressources.
\section*{Acknowledgment}
