-
-
-
\documentclass[conference]{IEEEtran}
-
\usepackage[ruled,vlined]{algorithm2e}
-
-
\hyphenation{op-tical net-works semi-conduc-tor}
-
\bibliographystyle{IEEEtran}
-
-
\usepackage{amsfonts}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\todo[color=orange!10,#1]{\sffamily\textbf{AS:} #2}\xspace}
-
-
\begin{document}
\title{Two parallel implementations of Ehrlich-Aberth algorithm for root-finding of polynomials on multiple GPUs with OpenMP and MPI}
-\author{\IEEEauthorblockN{Kahina Guidouche, Abderrahmane Sider }
+\author{\IEEEauthorblockN{Kahina Ghidouche, Abderrahmane Sider }
\IEEEauthorblockA{Laboratoire LIMED\\
Faculté des sciences exactes\\
Université de Bejaia, 06000, Algeria\\
\end{abstract}
% no keywords
-\LZK{Faut pas mettre des keywords?}
+\LZK{Faut pas mettre des keywords?\KG{Oui d'après ça: "no keywords" qui se trouve dans leur fichier source!!, mais c'est Bizzard!!!}}
\IEEEpeerreviewmaketitle
though the latest values of other approximations $z^{k}_{i}$ 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
+iteration. Couturier and al.~\cite{Raphaelall01} proposed two methods
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 in 116 seconds with
-OpenMP and 135 seconds with MPI only by using 8 personal computers and
-2 communications per iteration. The authors showed an interesting
-speedup comparing to the sequential implementation which takes up-to
-3,300 seconds to obtain same results.
+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}
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.
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:
\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.
\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.}
+\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.
-%\LZK{A revoir toute cette organization: je viens de la revoir}
+
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
{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=1,\ldots,n
\end{equation}
-This method contains 4 steps. The first step consists in the initializing the polynomial. The second step initializes the solution vector $Z$ using the Guggenheimer method~\cite{Gugg86} to ensure that initial roots are all distinct from each other. In step 3, the iterative function based on the Newton's method~\cite{newt70} and Weiestrass operator~\cite{Weierstrass03} is applied. In our case, the Ehrlich-Aberth is applied as in~(\ref{Eq:EA1}). Iterations of the Ehrlich-Aberth method will converge to the roots of the considered polynomial. In order to stop the iterative function, a stop condition is applied, this is the 4th step. This condition checks that all the root modules are lower than a fixed value $\epsilon$.
+This method contains 4 steps. The first step consists in the
+initializing the polynomial. The second step initializes the solution
+vector $Z$ using the Guggenheimer method~\cite{Gugg86} to ensure that
+initial roots are all distinct from each other. In step 3, the
+iterative function based on the Newton's method~\cite{newt70} and
+Weiestrass operator~\cite{Weierstrass03} is applied. In our case, the
+Ehrlich-Aberth is applied as in~(\ref{Eq:EA1}). Iterations of the
+Ehrlich-Aberth method will converge to the roots of the considered
+polynomial. In order to stop the iterative function, a stop condition
+is applied, this is the 4th step. This condition checks that all the
+root modules are lower than a fixed value $\epsilon$.
\begin{equation}
\label{eq:Aberth-Conv-Cond}
\subsection{The Ehrlich-Aberth parallel implementation on CUDA}
-Our objective consists in implementing a root finding polynomial
-algorithm on multiple GPUs. To this end, it is primordial to know how
-to manage CUDA contexts of different GPUs. A direct method for
-controlling the various GPUs is to use as many threads or processes as
-GPU devices. We can choose the GPU index based on the identifier of
-OpenMP thread or the rank of the MPI process. Both approaches will be
-investigated. \LZK{Répétition! Le même texte est déjà écrit comme
- intro dans la section II. Sinon ici on parle seulement de
- l'implémentation cuda sans mpi et openmp! \RC{Je suis d'accord à
- revoir après, quand les 2 parties suivantes seront plus stables}}
-
-
-
-
-Like any parallel code, a GPU parallel implementation first requires to determine the sequential code and the data-parallel operations of a algorithm. In fact, all the operations that are easy to execute in parallel must be made by the GPU to accelerate the execution, like the steps 3 and 4. On the other hand, all the sequential operations and the operations that have data dependencies between CUDA threads or recursive computations must be executed by only one CUDA thread or a CPU thread (the steps 1 and 2).\LZK{La méthode est déjà mal présentée, dans ce cas c'est encore plus difficile de comprendre que représentent ces différentes étapes!} Initially, we specify the organization of parallel threads by specifying the dimension of the grid \verb+Dimgrid+, the number of blocks per grid \verb+DimBlock+ and the number of threads per block.
-
-The code is organized as kernels which are parts of code that are run on GPU devices. For step 3, there are two kernels, the first is named \textit{save} is used to save vector $Z^{K-1}$ and the second one is
-named \textit{update} and is used to update the $Z^{K}$ vector. For
-step 4, a kernel tests the convergence of the method. In order to
-compute the function H, we have two possibilities: either to use the
-Jacobi mode, or the Gauss-Seidel mode of iterating which uses the most
-recent computed roots. It is well known that the Gauss-Seidel mode
-converges more quickly. So, we use Gauss-Seidel iterations. To
-parallelize the code, we create kernels and many functions to be
-executed on the GPU for all the operations dealing with the
-computation on complex numbers and the evaluation of the
-polynomials. As said previously, we manage both functions of
-evaluation: the normal method, based on the method of
-Horner and the method based on the logarithm of the polynomial. All
-these methods were rather long to implement, as the development of
-corresponding kernels with CUDA is longer than on a CPU host. This
-comes in particular from the fact that it is very difficult to debug
-CUDA running threads like threads on a CPU host. In the following
-paragraph Algorithm~\ref{alg1-cuda} shows the GPU parallel
-implementation of Ehrlich-Aberth method.
-\LZK{Vaut mieux expliquer l'implémentation en faisant référence à l'algo séquentiel que de parler des différentes steps.}
+The code is organized as kernels which are parts of code that are run
+on GPU devices. Algorithm~\ref{alg1-cuda} describes the CUDA
+implementation of the Ehrlich-Aberth on a GPU. This algorithms starts
+by initializing the polynomial and its derivative (line 1). The
+initialization of the roots is performed (line 2). Data are transfered
+from the CPU to the GPU (after allocation of the required memory on
+the GPU) (line 3). Then at each iteration, if the error is greater
+than a threshold, the following operations are performed. The previous
+roots are saved using a kernel (line 5). Then the new root with the
+new iterations are computed using the EA method with a Gauss Seidel
+iteration modes in order to use the lastest roots updated (line
+6). This improves the convergence. This kernel is, in pratice, very
+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
+are transferred from the GPU to the CPU.
+
\begin{algorithm}[htpb]
+\label{alg1-cuda}
\LinesNumbered
\SetAlgoNoLine
\caption{Finding roots of polynomials with the Ehrlich-Aberth method on a GPU}
-\KwIn{$n$ (polynomial's degree), $\epsilon$ (tolerance threshold)}
+\KwIn{ $\epsilon$ (tolerance threshold)}
\KwOut{$Z$ (solution vector of roots)}
Initialize the polynomial $P$ and its derivative $P'$\;
Set the initial values of vector $Z$\;
Copy $P$, $P'$ and $Z$ from CPU to GPU\;
-\While{\emph{not convergence}}{
- $Z^{prev}$ = KernelSave($Z,n$)\;
- $Z$ = KernelUpdate($P,P',Z,n$)\;
- $\Delta Z$ = KernelComputeError($Z,Z^{prev},n$)\;
- $\Delta Z_{max}$ = CudaMaxFunction($\Delta Z,n$)\;
- TestConvergence($\Delta Z_{max},\epsilon$)\;
+\While{$error > \epsilon$}{
+ $Z^{prev}$ = KernelSave($Z$)\;
+ $Z$ = KernelUpdate($P,P',Z$)\;
+ $error$ = KernelComputeError($Z,Z^{prev}$)\;
}
Copy $Z$ from GPU to CPU\;
-\label{alg1-cuda}
-\LZK{J'ai modifié l'algo. Sinon, est ce qu'on doit mettre en paramètre
- $Z^{prev}$ ou $Z$ tout court (dans le cas où on exploite
- l'asynchronisme des threads cuda!) pour le Kernel\_Update? }
-\RC{Le $Z_{prev}$ sert à calculer l'erreur donc j'ai remis Z. La ligne
-avec TestConvergence ca fait une ligne de plus.}
\end{algorithm}
+
+The development of this code is a rather long task, as the development
+of corresponding kernels with CUDA is longer than on a CPU host. This
+comes in particular from the fact that it is very difficult to debug
+CUDA running threads like threads on a CPU host. In the following
+section the GPU parallel implementation of Ehrlich-Aberth method with
+OpenMP and MPI is presented.
+
+
+
+
-\section{The EA algorithm on Multiple GPUs}
+\section{The EA algorithm on multiple GPUs}
\label{sec4}
\subsection{an OpenMP-CUDA approach}
Our OpenMP-CUDA implementation of EA algorithm is based on the hybrid
-OpenMP and CUDA programming model. All the data are shared with
-OpenMP amoung all the OpenMP threads. The shared data are the solution
-vector $Z$, the polynomial to solve $P$, and the error vector $\Delta
-z$. The number of OpenMP threads is equal to the number of GPUs, each
-OpenMP thread binds to one GPU, and it controls a part of the shared
-memory. More precisely each OpenMP thread will be responsible to
-update its owns part of the vector Z. This part is call $Z_{loc}$ in
-the following. Then all GPUs will have a grid of computation organized
-according to the device performance and the size of data on which it
-runs the computation kernels.
+OpenMP and CUDA programming model. This algorithm is presented in
+Algorithm~\ref{alg2-cuda-openmp}. All the data are shared with OpenMP
+amoung all the OpenMP threads. The shared data are the solution vector
+$Z$, the polynomial to solve $P$, its derivative $P'$, and the error
+vector $error$. The number of OpenMP threads is equal to the number of
+GPUs, each OpenMP thread binds to one GPU, and it controls a part of
+the shared memory. More precisely each OpenMP thread will be
+responsible to update its owns part of the vector $Z$. This part is
+called $Z_{loc}$ in the following. Then all GPUs will have a grid of
+computation organized according to the device performance and the size
+of data on which it runs the computation kernels.
To compute one iteration of the EA method each GPU performs the
followings steps. First roots are shared with OpenMP and the
-computation of the local size for each GPU is performed (lines 5-7 in
-Algo\ref{alg2-cuda-openmp}). Each thread starts by copying all the
-previous roots inside its GPU (line 9). Then each GPU will copy the
-previous roots (line 10) and it will compute an iteration of the EA
-method on its own roots (line 11). For that all the other roots are
-used. The convergence is checked on the new roots (line 12). At the end
-of an iteration, the updated roots are copied from the GPU to the
-CPU (line 14) by direcly updating its own roots in the shared memory
-arrays containing all the roots.
+computation of the local size for each GPU is performed (line 4). Each
+thread starts by copying all the previous roots inside its GPU (line
+5). At each iteration, the following operations are performed. First
+the vector $Z$ is transferred from the CPU to the GPU (line 7). Each
+GPU copies the previous roots (line 8) and it computes an iteration of
+the EA method on its own roots (line 9). For that all the other roots
+are used. The local error is computed on the new roots (line 10) and
+the max of the local errors is computed on all OpenMP threads (lien 11). At
+the end of an iteration, the updated roots are copied from the GPU to
+the CPU (line 12) by direcly updating its own roots in the shared
+memory arrays containing all the roots.
\begin{algorithm}[htpb]
+\label{alg2-cuda-openmp}
\LinesNumbered
\SetAlgoNoLine
\caption{Finding roots of polynomials with the Ehrlich-Aberth method on multiple GPUs using OpenMP}
-\KwIn{$n$ (polynomial's degree), $\epsilon$ (tolerance threshold), $ngpu$ (number of GPUs)}
+\KwIn{ $\epsilon$ (tolerance threshold)}
\KwOut{$Z$ (solution vector of roots)}
Initialize the polynomial $P$ and its derivative $P'$\;
Set the initial values of vector $Z$\;
-Start of a parallel part with OpenMP ($Z$, $\Delta Z$, $\Delta
-Z_{max}$, $P$, $P'$ are shared variables)\;
-$id_{gpu}$ = cudaGetDevice()\;
-$n_{loc}$ = $n/ngpu$ (local size)\;
-%$idx$ = $id_{gpu}\times n_{loc}$ (local offset)\;
+Start of a parallel part with OpenMP ($Z$, $error$, $P$, $P'$ are shared variables)\;
+Determine the local part of the OpenMP thread\;
Copy $P$, $P'$ from CPU to GPU\;
-\While{\emph{not convergence}}{
+\While{$error > \epsilon$}{
Copy $Z$ from CPU to GPU\;
- $Z^{prev}$ = KernelSave($Z,n$)\;
- $Z_{loc}$ = KernelUpdate($P,P',Z^{prev},n_{loc}$)\;
- $\Delta Z_{loc}$ = KernelComputeError($Z_{loc},Z^{prev}_{loc},n_{loc}$)\;
- $\Delta Z_{max}[id_{gpu}]$ = CudaMaxFunction($\Delta Z_{loc},n_{loc}$)\;
+ $Z^{prev}_{loc}$ = KernelSave($Z_{loc}$)\;
+ $Z_{loc}$ = KernelUpdate($P,P',Z$)\;
+ $error_{loc}$ = KernelComputeError($Z_{loc},Z^{prev}_{loc}$)\;
+ $error = max(error_{loc})$\;
Copy $Z_{loc}$ from GPU to $Z$ in CPU\;
- $max$ = MaxFunction($\Delta Z_{max},ngpu$)\;
- TestConvergence($max,\epsilon$)\;
}
-\label{alg2-cuda-openmp}
-\LZK{J'ai modifié l'algo. Le $P$ est mis shared. Qu'en est-il pour
- $P'$?}\RC{Je l'ai rajouté. Bon sinon le n\_loc ne remplace pas
- vraiment un offset et une taille mais bon... et là il y a 4 lignes
- pour la convergence, c'est bcp ... Zloc, Zmax, max et
- testconvergence. On pourrait faire mieux}
\end{algorithm}
-\subsection{an MPI-CUDA approach}
+\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
+roots using all the roots computed by other processors at the previous
+iteration. The difference between both approaches lies in the way
+processes communicate and exchange data. With MPI, processors need to
+send and receive data explicitely. So in
+Algorithm~\ref{alg2-cuda-mpi}, after the initialization all the
+processors have the same $Z$ vector. Then they need to compute the
+parameters used by the $MPI\_AlltoAll$ routines (line 4). In practise,
+each processor needs to compute its offset and its local
+size. Processors need to allocate memory on their GPU and need to copy
+their data on the GPU (line 5). At the beginning of each iteration, a
+processor starts by transfering the whole vector Z from the CPU to the
+GPU (line 7). Only the local part of $Z^{prev}$ is saved (line
+8). After that, a processor is able to compute an updated version of
+its own roots (line 9) with the EA method. The local error is computed
+(ligne 10) and the global error using $MPI\_Reduce$ (line 11). Then
+the local roots are transfered from the GPU memory to the CPU memory
+(line 12) before being exchanged between all processors (lige 13) in
+order to give to all processors the last version of the roots (with
+the MPI\_AlltoAll routine). If the convergence is not statisfied, an
+new iteration is executed.
-Our parallel implementation of EA to find root of polynomials using a CUDA-MPI approach is a data parallel approach. It splits input data of the polynomial to solve among MPI processes. In Algorithm \ref{alg2-cuda-mpi}, input data are the polynomial to solve $P$, the solution vector $Z$, the previous solution vector $ZPrev$, and the value of errors of stop condition $\Delta z$. Let $p$ denote the number of MPI processes on and $n$ the degree of the polynomial to be solved. The algorithm performs a simple data partitioning by creating $p$ portions, of at most $\lceil n/p \rceil$ roots to find per MPI process, for each $Z$ and $ZPrec$. Consequently, each MPI process of rank $k$ will have its own solution vector $Z_{k}$ and $ZPrec$, the error related to the stop condition $\Delta z_{k}$, enabling each MPI process to compute $\lceil n/p \rceil$ roots.
-Since a GPU works only on data already allocated in its memory, all local input data, $Z_{k}$, $ZPrec$ and $\Delta z_{k}$, must be transferred from CPU memories to the corresponding GPU memories. Afterwards, the same EA algorithm (Algorithm \ref{alg1-cuda}) is run by all processes but on different polynomial subset of roots $ p(x)_{k}=\sum_{i=1}^{n} a_{i}x^{i}, k=1,...,p$. Each MPI process executes the loop \verb=(While(...)...do)= containing the CUDA kernels but each MPI process computes only its own portion of the roots according to the rule ``''owner computes``''. The local range of roots is indicated with the \textit{index} variable initialized at (line 5, Algorithm \ref{alg2-cuda-mpi}), and passed as an input variable to $kernel\_update$ (line 10, Algorithm \ref{alg2-cuda-mpi}). After each iteration, MPI processes synchronize (\verb=MPI_Allreduce= function) by a reduction on $\Delta z_{k}$ in order to compute the maximum error related to the stop condition. Finally, processes copy the values of new computed roots from GPU memories to CPU memories, then communicate their results to other processes with \verb=MPI_Alltoall= broadcast. If the stop condition is not verified ($error > \epsilon$) then processes stay withing the loop \verb= while(...)...do= until all the roots sufficiently converge.
\begin{algorithm}[htpb]
\label{alg2-cuda-mpi}
-%\LinesNumbered
+\LinesNumbered
+\SetAlgoNoLine
\caption{CUDA-MPI Algorithm to find roots with the Ehrlich-Aberth method}
-\KwIn{$Z^{0}$ (Initial root's vector), $\varepsilon$ (Error tolerance
- threshold), P (Polynomial to solve), Pu (Derivative of P), $n$ (Polynomial degrees), $\Delta z$ ( error of stop condition), $num_gpus$ (number of MPI processes/ number of GPUs), Size (number of roots)}
+\KwIn{ $\epsilon$ (tolerance threshold)}
-\KwOut {$Z$ (Solution root's vector), $ZPrec$ (Previous solution root's vector)}
+\KwOut {$Z$ (solution vector of roots)}
\BlankLine
-Initialization of P\;
-Initialization of Pu\;
-Initialization of the solution vector $Z^{0}$\;
-Distribution of Z\;
-Allocate memory to GPU\;
+Initialize the polynomial $P$ and its derivative $P'$\;
+Set the initial values of vector $Z$\;
+Determine the local part of the MPI process\;
+Computation of the parameters for the $MPI\_AlltoAll$\;
+Copy $P$, $P'$ from CPU to GPU\;
\While {$error > \epsilon$}{
-copy Z from CPU to GPU\;
-$ZPrec_{loc}=kernel\_save(Z_{loc})$\;
-$Z_{loc}=kernel\_update(Z,P,Pu)$\;
-$\Delta z=kernel\_testConv(Z_{loc},ZPrec_{loc})$\;
-$error=MPI\_Reduce(\Delta z)$\;
-Copy $Z_{loc}$ from GPU to CPU\;
-$Z=MPI\_AlltoAll(Z_{loc})$\;
+ Copy $Z$ from CPU to GPU\;
+ $Z^{prev}_{loc}$ = KernelSave($Z_{loc}$)\;
+ $Z_{loc}$ = KernelUpdate($P,P',Z$)\;
+ $error_{loc}$ = KernelComputeError($Z_{loc},Z^{prev}_{loc}$)\;
+ $error=MPI\_Reduce(error_{loc})$\;
+ Copy $Z_{loc}$ from GPU to CPU\;
+ $Z=MPI\_AlltoAll(Z_{loc})$\;
}
\end{algorithm}
