From c539c4056821d3539c4c46fef943c2b0db313628 Mon Sep 17 00:00:00 2001 From: couturie Date: Thu, 21 Jan 2016 22:02:19 +0100 Subject: [PATCH] english correct --- paper.tex | 55 +++++++++++++++++++++++++++++++++++++------------------ 1 file changed, 37 insertions(+), 18 deletions(-) diff --git a/paper.tex b/paper.tex index f34155e..00c9625 100644 --- a/paper.tex +++ b/paper.tex @@ -39,17 +39,17 @@ Email: zianekhodja.lilia@gmail.com\\ raphael.couturier@univ-fcomte.fr}} \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} @@ -64,7 +64,7 @@ of polynomials of degree up-to 5 millions. \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} @@ -73,10 +73,25 @@ where $\{\alpha_i\}_{0\leq i\leq n}$ are complex coefficients and $n$ is a high 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,bini96,cs01:nj,Couturier02}, using several paradigms of parallelization (synchronous or asynchronous computations, mechanism of shared or distributed memory, etc). However, they have solved 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 @@ -100,9 +115,13 @@ The convergence time of simultaneous methods drastically increases with the incr %roots of sparse polynomials of degree 10,000. The authors showed an interesting %speedup that is 20 times as fast as the sequential implementation. -But 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 processors CPUs, 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. +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 (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: +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 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. -- 2.39.5