From c4fa3c3385a0bfa02e9f3eba793fc25fc6d0d0dd Mon Sep 17 00:00:00 2001 From: couturie Date: Thu, 14 Jan 2016 17:44:01 +0100 Subject: [PATCH 1/1] new --- paper.tex | 83 +++++++++++++++++++++++++++++++------------------------ 1 file changed, 47 insertions(+), 36 deletions(-) diff --git a/paper.tex b/paper.tex index 49cd195..ae15aa8 100644 --- a/paper.tex +++ b/paper.tex @@ -715,8 +715,8 @@ where: \begin{eqnarray} \label{Log_H1} Q(z^{k}_{i})=\exp\left( \ln (p(z^{k}_{i}))-\ln(p'(z^{k}_{i}))+\ln \left( -\sum_{i\neq j}^{n}\frac{1}{z^{k}_{i}-z^{k}_{j}}\right)\right)\\ -i=1,...,n, \nonumber +\sum_{i\neq j}^{n}\frac{1}{z^{k}_{i}-z^{k}_{j}}\right)\right) \nonumber \\ +i=1,...,n \end{eqnarray} @@ -727,41 +727,52 @@ Using the logarithm and the exponential operators, we can replace any multiplic %propose to use the logarithm and the exponential of a complex in order to compute the power at a high exponent. Using the logarithm and the exponential operators, we can replace any multiplications and divisions with additions and subtractions. Consequently, computations manipulate lower absolute values and the roots for large polynomial degrees can be looked for successfully~\cite{Karimall98}. \subsection{Ehrlich-Aberth parallel implementation on CUDA} -We introduced three paradigms of parallel programming. 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. - - - - -Like any parallel code, a GPU parallel implementation first -requires to determine the sequential tasks and the -parallelizable parts of the sequential version of the -program/algorithm. In our case, all the operations that are easy -to execute in parallel must be made by the GPU to accelerate -the execution of the application, like the step 3 and step 4. On the other hand, all the -sequential operations and the operations that have data -dependencies between threads or recursive computations must -be executed by only one CUDA or CPU thread (step 1 and step 2). Initially, we specify the organization of parallel threads, by specifying the dimension of the grid Dimgrid, the number of blocks per grid DimBlock and the number of threads per block. - -The code is organized by what is named kernels, portions code that are run on GPU devices. For step 3, there are two kernels, the -first named \textit{save} is used to save vector $Z^{K-1}$ and the seconde 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 used the Gauss-Seidel mode of iteration. To -parallelize the code, we created kernels and many functions to -be executed on the GPU for all the operations dealing with the +%We introduced three paradigms of parallel programming. + +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. + + + + +Like any parallel code, a GPU parallel implementation first requires +to determine the sequential tasks and the parallelizable parts of the +sequential version of the program/algorithm. In our case, all the +operations that are easy to execute in parallel must be made by the +GPU to accelerate the execution of the application, like the step 3 +and step 4. On the other hand, all the sequential operations and the +operations that have data dependencies between threads or recursive +computations must be executed by only one CUDA or CPU thread (step 1 +and step 2). Initially, we specify the organization of parallel +threads, by specifying the dimension of the grid Dimgrid, the number +of blocks per grid DimBlock and the number of threads per block. + +The code is organized kernels which are part of code that are run on +GPU devices. For step 3, there are two kernels, the first 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 managed both functions -of evaluation of a polynomial: 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. +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. \begin{enumerate} \begin{algorithm}[htpb] -- 2.39.5