X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/kahina_paper1.git/blobdiff_plain/6dbe0b7204079bfef31d546107f53fd7f84e5d33..705f945860e432e730f66cdf91d7599b1e3cd3aa:/paper.tex?ds=inline diff --git a/paper.tex b/paper.tex index d9d72c3..bcf399a 100644 --- a/paper.tex +++ b/paper.tex @@ -115,14 +115,14 @@ The root finding problem consists in finding the values of all the $n$ values of \end{equation} The problem of finding a root is equivalent to that of solving a fixed-point problem. To see this, consider the fixed-point problem of finding the $n$-dimensional -vector $x$ such that +vector $x$ such that : \begin{center} $x=g(x)$ \end{center} where $g : C^{n}\longrightarrow C^{n}$. Usually, we can easily rewrite this fixed-point problem as a root-finding problem by setting $f(x) = x-g(x)$ and likewise we can recast the -root-finding problem into a fixed-point problem by setting +root-finding problem into a fixed-point problem by setting : \begin{center} $g(x)= f(x)-x$. \end{center} @@ -147,10 +147,10 @@ approximation of all the roots, starting with the Durand-Kerner (DK) method: %%\begin{center} \begin{equation} - Z_i^{k+1}=Z_{i}^k-\frac{P(Z_i^k)}{\prod_{i\neq j}(Z_i^k-Z_j^k)} + z_i^{k+1}=z_{i}^{k}-\frac{P(z_i^{k})}{\prod_{i\neq j}(z_i^{k}-z_j^{k})}, i = 1, . . . , n, \end{equation} %%\end{center} -where $Z_i^k$ is the $i^{th}$ root of the polynomial $P$ at the +where $z_i^k$ is the $i^{th}$ root of the polynomial $P$ at the iteration $k$. @@ -164,11 +164,12 @@ in the following form by Ehrlich~\cite{Ehrlich67} and Aberth~\cite{Aberth73} uses a different iteration formula given as fellows : %%\begin{center} \begin{equation} - Z_i^{k+1}=Z_i^k-\frac{1}{{\frac {P'(Z_i^k)} {P(Z_i^k)}}-{\sum_{i\neq j}(Z_i^k-Z_j^k)}}. +\label{Eq:EA} + z_i^{k+1}=z_i^{k}-\frac{1}{{\frac {P'(z_i^{k})} {P(z_i^{k})}}-{\sum_{i\neq j}\frac{1}{(z_i^{k}-z_j^{k})}}}, i = 1, . . . , n, \end{equation} %%\end{center} -where $P'(Z)$ is the polynomial derivative of $P$ evaluated in the -point $Z$. +where $P'(z)$ is the polynomial derivative of $P$ evaluated in the +point $z$. Aberth, Ehrlich and Farmer-Loizou~\cite{Loizon83} have proved that the Ehrlich-Aberth method (EA) has a cubic order of convergence for simple roots whereas the Durand-Kerner has a quadratic order of convergence. @@ -192,7 +193,7 @@ Freeman and Bane~\cite{Freemanall90} considered asynchronous algorithms, in which each processor continues to update its approximations even though the latest values of other $z_i((k))$ have not been received from the other processors, in contrast with synchronous algorithms where it would wait those values before making a new iteration. -Couturier et al. ~\cite{Raphaelall01} proposed two methods of parallelisation for +Couturier and al~\cite{Raphaelall01} proposed two methods of parallelisation for a shared memory architecture and for distributed memory one. They were able to compute the roots of polynomials of degree 10000 in 430 seconds with only 8 personal computers and 2 communications per iteration. Comparing to the sequential implementation @@ -201,55 +202,52 @@ where it takes up to 3300 seconds to obtain the same results, the authors show a Very few works had been since this last work until the appearing of the Compute Unified Device Architecture (CUDA)~\cite{CUDA10}, a parallel computing platform and a programming model invented by -NVIDIA. The computing power of GPUs (Graphics Processing Unit) has exceeded that of -of CPUs. However, CUDA adopts a totally new computing architecture to use the +NVIDIA. The computing power of GPUs (Graphics Processing Unit) has exceeded that of CPUs. However, CUDA adopts a totally new computing architecture to use the hardware resources provided by GPU in order to offer a stronger computing ability to the massive data computing. -Ghidouche et al. ~\cite{Kahinall14} proposed an implementation of the +Ghidouche and al~\cite{Kahinall14} proposed an implementation of the Durand-Kerner method on GPU. Their main result showed that a parallel CUDA implementation is 10 times as fast as the sequential implementation on a single CPU for high degree polynomials of about 48000. To our knowledge, it is the first time such high degree polynomials are numerically solved. -In this paper, we focus on the implementation of the Aberth method for -high degree polynomials on GPU. The paper is organised as fellows. Initially, we recall the Aberth method in Section.\ref{sec1}. Improvements for the Aberth method are proposed in Section.\ref{sec2}. Related work to the implementation of simultaneous methods using a parallel approach is presented in Section.\ref{secStateofArt}. -In Section.4 we propose a parallel implementation of the Aberth method on GPU and discuss it. Section 5 presents and investigates our implementation and experimental study results. Finally, Section 6 concludes this paper and gives some hints for future research directions in this topic. +In this paper, we focus on the implementation of the Ehrlich-Aberth method for +high degree polynomials on GPU. The paper is organized as fellows. Initially, we recall the Ehrlich-Aberth method in Section \ref{sec1}. Improvements for the Ehrlich-Aberth method are proposed in Section \ref{sec2}. Related work to the implementation of simultaneous methods using a parallel approach is presented in Section \ref{secStateofArt}. +In Section \ref{sec5} we propose a parallel implementation of the Ehrlich-Aberth method on GPU and discuss it. Section \ref{sec6} presents and investigates our implementation and experimental study results. Finally, Section\ref{sec7} 6 concludes this paper and gives some hints for future research directions in this topic. \section{The Sequential Aberth method} \label{sec1} A cubically convergent iteration method for finding zeros of -polynomials was proposed by O.Aberth~\cite{Aberth73}. The Aberth -method is a purely algebraic derivation. To illustrate the -derivation, we let $w_{i}(z)$ be the product of linear factors +polynomials was proposed by O. Aberth~\cite{Aberth73}. In the fellowing we present the main stages of the running of the Aberth method. +%The Aberth method is a purely algebraic derivation. +%To illustrate the derivation, we let $w_{i}(z)$ be the product of linear factors -\begin{equation} -w_{i}(z)=\prod_{j=1,j \neq i}^{n} (z-x_{j}) -\end{equation} +%\begin{equation} +%w_{i}(z)=\prod_{j=1,j \neq i}^{n} (z-x_{j}) +%\end{equation} -And let a rational function $R_{i}(z)$ be the correction term of the -Weistrass method~\cite{Weierstrass03} +%And let a rational function $R_{i}(z)$ be the correction term of the +%Weistrass method~\cite{Weierstrass03} -\begin{equation} -R_{i}(z)=\frac{p(z)}{w_{i}(z)} , i=1,2,...,n. -\end{equation} +%\begin{equation} +%R_{i}(z)=\frac{p(z)}{w_{i}(z)} , i=1,2,...,n. +%\end{equation} -Differentiating the rational function $R_{i}(z)$ and applying the -Newton method, we have: - -\begin{equation} -\frac{R_{i}(z)}{R_{i}^{'}(z)}= \frac{p(z)}{p^{'}(z)-p(z)\frac{w_{i}(z)}{w_{i}^{'}(z)}}= \frac{p(z)}{p^{'}(z)-p(z) \sum _{j=1,j \neq i}^{n}\frac{1}{z-x_{i}}}, i=1,2,...,n -\end{equation} +%Differentiating the rational function $R_{i}(z)$ and applying the +%Newton method, we have: -Substituting $x_{j}$ for z we obtain the Aberth iteration method. +%\begin{equation} +%\frac{R_{i}(z)}{R_{i}^{'}(z)}= \frac{p(z)}{p^{'}(z)-p(z)\frac{w_{i}(z)}{w_{i}^{'}(z)}}= \frac{p(z)}{p^{'}(z)-p(z) \sum _{j=1,j \neq i}^{n}\frac{1}{z-x_{j}}}, i=1,2,...,n +%\end{equation} +%where R_{i}^{'}(z)is the rational function derivative of F evaluated in the point z +%Substituting $x_{j}$ for $z_{j}$ we obtain the Aberth iteration method.% -In the fellowing we present the main stages of the running of the Aberth method. \subsection{Polynomials Initialization} -The initialization of a polynomial p(z) is done by setting each of the $n$ complex coefficients $a_{i}$ -: +The initialization of a polynomial p(z) is done by setting each of the $n$ complex coefficients $a_{i}$: \begin{equation} \label{eq:SimplePolynome} @@ -264,7 +262,7 @@ The initial guess is very important since the number of steps needed by the iter a given approximation strongly depends on it. In~\cite{Aberth73} the Aberth iteration is started by selecting $n$ equi-spaced points on a circle of center 0 and radius r, where r is -an upper bound to the moduli of the zeros. Later, Bini et al.~\cite{Bini96} +an upper bound to the moduli of the zeros. Later, Bini and al.~\cite{Bini96} performed this choice by selecting complex numbers along different circles and relies on the result of~\cite{Ostrowski41}. @@ -281,16 +279,17 @@ u_{i}=2.|a_{i}|^{\frac{1}{i}}; v_{i}=\frac{|\frac{a_{n}}{a_{i}}|^{\frac{1}{n-i}}}{2}. \end{equation} -\subsection{Iterative Function $H_{i}$} +\subsection{Iterative Function $H_{i}(z^{k})$} The operator used by the Aberth method is corresponding to the -following equation which will enable the convergence towards +following equation~\ref{Eq:EA} which will enable the convergence towards polynomial solutions, provided all the roots are distinct. \begin{equation} -H_{i}(z)=z_{i}-\frac{1}{\frac{p^{'}(z_{i})}{p(z_{i})}-\sum_{j\neq -i}{\frac{1}{z_{i}-z_{j}}}} +\label{Eq:Hi} +H_{i}(z^{k+1})=z_{i}^{k}-\frac{\frac{p(z_{i}^{k})}{p'(z_{i}^{k})}} +{1-\frac{p(z_{i}^{k})}{p'(z_{i}^{k})}\sum_{j=1,j\neq i}^{j=n}{\frac{1}{(z_{i}^{k}-z_{j}^{k})}}}, i=0,. . . .,n \end{equation} - +we notice that the function iterative $H_{i}$ in Eq.~\ref{Eq:Hi} it the same those presented in Eq.~\ref{Eq:EA}, but we prefer used the last one seen the advantage of its use to improve the Aberth method. More detail in the section ~\ref{sec2}. \subsection{Convergence Condition} The convergence condition determines the termination of the algorithm. It consists in stopping from running the iterative function $H_{i}(z)$ when the roots are sufficiently stable. We consider that the method @@ -299,7 +298,7 @@ converges sufficiently when : \begin{equation} \label{eq:Aberth-Conv-Cond} \forall i \in -[1,n];\frac{z_{i}^{(k)}-z_{i}^{(k-1)}}{z_{i}^{(k)}}<\xi +[1,n];\frac{z_{i}^{k}-z_{i}^{k-1}}{z_{i}^{k}}<\xi \end{equation} @@ -332,30 +331,34 @@ propose to use the logarithm and the exponential of a complex in order to comput Using the logarithm (eq.~\ref{deflncomplex}) and the exponential (eq.~\ref{defexpcomplex}) operators, we can replace any multiplications and divisions with additions and subtractions. Consequently, computations manipulate lower absolute values and the roots for large polynomial's degrees can be looked for successfully~\cite{Karimall98}. -Applying this solution for the Aberth method we obtain the +Applying this solution for the Ehrlich-Aberth method we obtain the iteration function with logarithm: %%$$ \exp \bigl( \ln(p(z)_{k})-ln(\ln(p(z)_{k}^{'}))- \ln(1- \exp(\ln(p(z)_{k})-ln(\ln(p(z)_{k}^{'})+\ln\sum_{i\neq j}^{n}\frac{1}{z_{k}-z_{j}})$$ \begin{equation} \label{Log_H2} -H_{i}(z)=z_{i}^{k}-\exp \left(\ln \left( -p(z_{k})\right)-\ln\left(p(z_{k}^{'})\right)- \ln -\left(1-Q(z_{k})\right)\right), +H_{i}(z^{k+1})=z_{i}^{k}-\exp \left(\ln \left( +p(z_{i}^{k})\right)-\ln\left(p'(z^{k}_{i})\right)- \ln +\left(1-Q(z^{k}_{i})\right)\right), \end{equation} where: \begin{equation} \label{Log_H1} -Q(z_{k})=\exp\left( \ln (p(z_{k}))-\ln(p(z_{k}^{'}))+\ln \left( -\sum_{k\neq j}^{n}\frac{1}{z_{k}-z_{j}}\right)\right). +Q(z^{k}_{i})=\exp\left( \ln (p(z^{k}_{i}))-\ln(p'(z^{k}^{i}))+\ln \left( +\sum_{k\neq j}^{n}\frac{1}{z^{k}_{i}-z^{k}_{j}}\right)\right). \end{equation} -This solution is applied when the root except the circle unit, represented by the radius $R$ evaluated as: -\begin{equation} -\label{R} -R = \exp( \log(DBL\_MAX) / (2*n) ) -\end{equation} - where $DBL\_MAX$ stands for the maximum representable double value. +This solution is applied when the root except the circle unit, represented by the radius $R$ evaluated in C language as: +\begin{verbatim} +R = exp(log(DBL_MAX)/(2*n) ); +\end{verbatim} + +%\begin{equation} + +%R = \exp( \log(DBL\_MAX) / (2*n) ) +%\end{equation} + where \verb=DBL_MAX= stands for the maximum representable \verb=double= value. \section{The implementation of simultaneous methods in a parallel computer} \label{secStateofArt} @@ -466,7 +469,8 @@ provides two read-only memory spaces, the constant space and the texture space, which reside in external DRAM, and are accessed via read-only caches. -\subsection{ The implementation of Aberth method on GPU} +\section{ The implementation of Aberth method on GPU} +\label{sec5} %%\subsection{A CUDA implementation of the Aberth's method } %%\subsection{A GPU implementation of the Aberth's method } @@ -510,15 +514,15 @@ In this sequential algorithm, one CPU thread executes all the steps. Let us loo There exists two ways to execute the iterative function that we call a Jacobi one and a Gauss-Seidel one. With the Jacobi iteration, at iteration $k+1$ we need all the previous values $z^{(k)}_{i}$ to compute the new values $z^{(k+1)}_{i}$, that is : \begin{equation} -H(i,z^{k+1})=\frac{p(z^{(k)}_{i})}{p'(z^{(k)}_{i})-p(z^{(k)}_{i})\sum^{n}_{j=1 j\neq i}\frac{1}{z^{(k)}_{i}-z^{(k)}_{j}}}, i=1,...,n. +z^{k+1}_{i}=\frac{p(z^{k}_{i})}{p'(z^{k}_{i})-p(z^{k}_{i})\sum^{n}_{j=1 j\neq i}\frac{1}{z^{k}_{i}-z^{k}_{j}}}, i=1,...,n. \end{equation} -With the Gauss-seidel iteration, we have: +With the Gauss-Seidel iteration, we have: \begin{equation} \label{eq:Aberth-H-GS} -H(i,z^{k+1})=\frac{p(z^{(k)}_{i})}{p'(z^{(k)}_{i})-p(z^{(k)}_{i})(\sum^{i-1}_{j=1}\frac{1}{z^{(k)}_{i}-z^{(k+1)}_{j}}+\sum^{n}_{j=i+1}\frac{1}{z^{(k)}_{i}-z^{(k)}_{j}})}, i=1,...,n. +z^{k+1}_{i}=\frac{p(z^{k}_{i})}{p'(z^{k}_{i})-p(z^{k}_{i})(\sum^{i-1}_{j=1}\frac{1}{z^{k}_{i}-z^{k+1}_{j}}+\sum^{n}_{j=i+1}\frac{1}{z^{k}_{i}-z^{k}_{j}})}, i=1,...,n. \end{equation} - +%%Here a finiched my revision %% Using Equation.~\ref{eq:Aberth-H-GS} for the update sub-step of $H(i,z^{k+1})$, we expect the Gauss-Seidel iteration to converge more quickly because, just as its ancestor (for solving linear systems of equations), it uses the most fresh computed roots $z^{k+1}_{i}$. The $4^{th}$ step of the algorithm checks the convergence condition using Equation.~\ref{eq:Aberth-Conv-Cond}. @@ -539,7 +543,7 @@ Let $K$ be the number of iterations necessary to compute all the roots, so the t \label{eq:T-global} T=\left[n\left(T_{i}(n)+T_{j}\right)+O(n)\right].K \end{equation} -The execution time increases with the increasing of the polynomial degree, which justifies to parallelise these steps in order to reduce the global execution time. In the following, we explain how we did parrallelize these steps on a GPU architecture using the CUDA platform. +The execution time increases with the increasing of the polynomial degree, which justifies to parallelize these steps in order to reduce the global execution time. In the following, we explain how we did parallelize these steps on a GPU architecture using the CUDA platform. \subsubsection{A Parallel implementation with CUDA } On the CPU, both steps 3 and 4 contain the loop \verb=for= and a single thread executes all the instructions in the loop $n$ times. In this subsection, we explain how the GPU architecture can compute this loop and reduce the execution time. @@ -609,7 +613,7 @@ The kernels terminate it computations when all the roots converge. Finally, the or from GPU memory to CPU memory \verb=(cudaMemcpyDeviceToHost))=. %%HIER END MY REVISIONS (SIDER) \section{Experimental study} - +\label{sec6} \subsection{Definition of the used polynomials } We study two categories of polynomials : the sparse polynomials and the full polynomials. \paragraph{A sparse polynomial}: is a polynomial for which only some coefficients are not null. We use in the following polonymial for which the roots are distributed on 2 distinct circles : @@ -645,25 +649,30 @@ In this section, we discuss the performance Ehrlich-Aberth method of root findi We performed a set of experiments on the sequential and the parallel algorithms, for both sparse and full polynomials and different sizes. We took into account the execution time, the polynomial size and the number of threads per block performed by sum or each experiment on CPUs and on GPUs. All experimental results obtained from the simulations are made in double precision data, for a convergence tolerance of the methods set to $10^{-7}$. Since we were more interested in the comparison of the performance behaviors of Ehrlich-Aberth and Durand-Kerner methods on CPUs versus on GPUs. The initialization values of the vector solution of the Ehrlich-Aberth method are given in section 2.2. -\subsubsection{The execution time in seconds of Ehrlich-Aberth algorithm on CPU core vs. on a Tesla GPU} +\subsubsection{The execution time in seconds of Ehrlich-Aberth algorithm on CPU OpenMP (1 core, 4 cores) vs. on a Tesla GPU} +%\begin{figure}[H] +%\centering + % \includegraphics[width=0.8\textwidth]{figures/Compar_EA_algorithm_CPU_GPU} +%\caption{The execution time in seconds of Ehrlich-Aberth algorithm on CPU core vs. on a Tesla GPU} +%\label{fig:01} +%\end{figure} + \begin{figure}[H] \centering - \includegraphics[width=0.8\textwidth]{figures/Compar_EA_algorithm_CPU_GPU} -\caption{The execution time in seconds of Ehrlich-Aberth algorithm on CPU core vs. on a Tesla GPU} + \includegraphics[width=0.8\textwidth]{figures/openMP-GPU} +\caption{The execution time in seconds of Ehrlich-Aberth algorithm on CPU OpenMP (1 core, 4 cores) vs. on a Tesla GPU} \label{fig:01} \end{figure} - Figure 1 %%show a comparison of execution time between the parallel and sequential version of the Ehrlich-Aberth algorithm with sparse polynomial exceed 100000, -We report the execution times of the Ehrlich-Aberth method implemented on one core of the Quad-Core Xeon E5620 CPU and those of the same methods implemented on one Nvidia Tesla K40c GPU, with sparse polynomial degrees ranging from 100,000 to 1,000,000. We can see that the method implemented on the GPU are faster than those implemented on the CPU. This is due to the GPU ability to compute the data-parallel functions faster than its CPU counterpart. However, the execution time for the CPU implementation exceed 5,000 s for 250,000 degrees polynomials, in counterpart the GPU implementation for the same polynomials not reach 100 s, more than again, % with 1,000,000 polynomials degrees GPU implementation not reach 2,300 s degrees. While CPU implementation need more than 10 hours. -with an execution time under to 2500 s CPU implementation can resolve polynomials degrees of only 200,000 s, whereas GPU implementation can resolve polynomials more than 1,000,000 degrees. We can also notice that the GPU implementation are almost 47 faster then those implementation on the CPU. Furthermore, we verify that the number of iterations is the same. This reduction of time allows us to compute roots of polynomial of more important degree at the same time than with a CPU. +We report respectively the execution time of the Ehrlich-Aberth method implemented initially on one core of the Quad-Core Xeon E5620 CPU than on four cores of the same machine with \textit{OpenMP} platform and the execution time of the same method implemented on one Nvidia Tesla K40c GPU, with sparse polynomial degrees ranging from 100,000 to 1,000,000. We can see that the method implemented on the GPU are faster than those implemented on the CPU (4 cores). This is due to the GPU ability to compute the data-parallel functions faster than its CPU counterpart. However, the execution time for the CPU(4 cores) implementation exceed 5,000 s for 250,000 degrees polynomials, in counterpart the GPU implementation for the same polynomials not reach 100 s, more than again, with an execution time under to 2500 s CPU (4 cores) implementation can resolve polynomials degrees of only 200,000, whereas GPU implementation can resolve polynomials more than 1,000,000 degrees. We can also notice that the GPU implementation are almost 47 faster then those implementation on the CPU(4 cores). However the CPU(4 cores) implementation are almost 4 faster then his implementation on CPU (1 core). Furthermore, we verify that the number of iterations and the convergence precision is the same for the both CPU and GPU implementation. %This reduction of time allows us to compute roots of polynomial of more important degree at the same time than with a CPU. - + %We notice that the convergence precision is a round $10^{-7}$ for the both implementation on CPU and GPU. Consequently, we can conclude that Ehrlich-Aberth on GPU are faster and accurately then CPU implementation. \subsubsection{Influence of the number of threads on the execution times of different polynomials (sparse and full)} To optimize the performances of an algorithm on a GPU, it is necessary to maximize the use of cores GPU (maximize the number of threads executed in parallel) and to optimize the use of the various memoirs GPU. In fact, it is interesting to see the influence of the number of threads per block on the execution time of Ehrlich-Aberth algorithm. -For that, we notice that the maximum number of threads per block for the Nvidia Tesla K40c GPU is 1024, so we varied the number of threads per block from 8 to 1024. We took into account the execution time for both sparse and full polynomials of size 50000 and 500000 degrees. +For that, we notice that the maximum number of threads per block for the Nvidia Tesla K40 GPU is 1024, so we varied the number of threads per block from 8 to 1024. We took into account the execution time for both sparse and full of 10 different polynomials of size 50000 and 10 different polynomials of size 500000 degrees. \begin{figure}[H] \centering @@ -718,20 +727,15 @@ This figure show the execution time of the both algorithm EA and DK with sparse \label{fig:01} \end{figure} -\subsubsection{The execution time of Ehrlich-Aberth algorithm on OpenMP(1 core, 4 cores) vs. on a Tesla GPU} +%\subsubsection{The execution time of Ehrlich-Aberth algorithm on OpenMP(1 core, 4 cores) vs. on a Tesla GPU} -\begin{figure}[H] -\centering - \includegraphics[width=0.8\textwidth]{figures/openMP-GPU} -\caption{The execution time in seconds of Ehrlich-Aberth algorithm on OpenMP(1 core, 4 cores) vs. on a Tesla GPU} -\label{fig:01} -\end{figure} -\section{Conclusion and perspective} +\section{Conclusion and perspective} +\label{sec7} \bibliography{mybibfile} \end{document}