X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/kahina_paper2.git/blobdiff_plain/0f3cb1c99b8729c26d0a8da0ae2b6d97b2f2dfc2..048a430c1ced6539008e4733fa88179f738cb5b0:/paper.tex diff --git a/paper.tex b/paper.tex index 5384818..18dd3c2 100644 --- a/paper.tex +++ b/paper.tex @@ -351,22 +351,17 @@ % author names and affiliations % use a multiple column layout for up to three different % affiliations -\author{\IEEEauthorblockN{Michael Shell} -\IEEEauthorblockA{School of Electrical and\\Computer Engineering\\ -Georgia Institute of Technology\\ -Atlanta, Georgia 30332--0250\\ -Email: http://www.michaelshell.org/contact.html} +\author{\IEEEauthorblockN{Kahina Guidouche, Abderrahmane Sider } + \IEEEauthorblockA{Laboratoire LIMED\\ + Faculté des sciences exactes\\ + Université de Bejaia, 06000, Algeria\\ +Email: \{kahina.ghidouche,ar.sider\}@univ-bejaia.dz} \and -\IEEEauthorblockN{Homer Simpson} -\IEEEauthorblockA{Twentieth Century Fox\\ -Springfield, USA\\ -Email: homer@thesimpsons.com} -\and -\IEEEauthorblockN{James Kirk\\ and Montgomery Scott} -\IEEEauthorblockA{Starfleet Academy\\ -San Francisco, California 96678--2391\\ -Telephone: (800) 555--1212\\ -Fax: (888) 555--1212}} +\IEEEauthorblockN{Lilia Ziane Khodja, Raphaël Couturier} +\IEEEauthorblockA{FEMTO-ST Institute\\ + University of Bourgogne Franche-Comte\\ + France\\ +Email: zianekhodja.lilia@gmail.com, raphael.couturier@univ-fcomte.fr}} % conference papers do not typically use \thanks and this command % is locked out in conference mode. If really needed, such as for @@ -990,7 +985,8 @@ In this experiments we report the execution time of the EA algorithm, on single \begin{figure}[htbp] \centering \includegraphics[angle=-90,width=0.5\textwidth]{Sparse_omp} -\caption{Execution time in seconds of the Ehrlich-Aberth method to solve sparse polynomials on multiple GPUs.} +\caption{Execution time in seconds of the Ehrlich-Aberth method to + solve sparse polynomials on multiple GPUs with CUDA-OpenMP.} \label{fig:01} \end{figure} @@ -1005,7 +1001,8 @@ These experiments show the execution times of the EA algorithm, on a single GPU \begin{figure}[htbp] \centering \includegraphics[angle=-90,width=0.5\textwidth]{Full_omp} -\caption{Execution time in seconds of the Ehrlich-Aberth method to solve full polynomials on multiple GPUs} +\caption{Execution time in seconds of the Ehrlich-Aberth method to + solve full polynomials on multiple GPUs with CUDA-OpenMP.} \label{fig:02} \end{figure} @@ -1023,7 +1020,8 @@ approach to solve full and sparse polynomials of degrees ranging from \begin{figure}[htbp] \centering \includegraphics[angle=-90,width=0.5\textwidth]{Sparse_mpi} -\caption{Execution time in seconds of the Ehrlich-Aberth method to solve sparse polynomials on multiple GPUs.} +\caption{Execution time in seconds of the Ehrlich-Aberth method to + solve sparse polynomials on multiple GPUs with CUDA-MPI.} \label{fig:03} \end{figure} Figure~\ref{fig:03} shows the execution times of te EA algorithm, @@ -1034,25 +1032,36 @@ for a single GPU, and multiple GPUs (2, 3, 4) with the CUDA-MPI approach. \begin{figure}[htbp] \centering \includegraphics[angle=-90,width=0.5\textwidth]{Full_mpi} -\caption{Execution times in seconds of the Ehrlich-Aberth method for full polynomials on GPUs using the Multi-GPU} +\caption{Execution times in seconds of the Ehrlich-Aberth method for + full polynomials on multiple GPUs with CUDA-MPI.} \label{fig:04} \end{figure} In Figure~\ref{fig:04}, we can also observe that the CUDA-MPI approach is also efficient to solve full polynimails on multiple GPUs. -\subsection{Comparing the CUDA-OpenMP approach and the CUDA-MPI approach} -In the previuos section we saw that both approches are very effective in reducing execution time for sparse as well as full polynomials. At this stage, the interesting question is which approach is better. In the fellowing, we present appropriate experiments comparing the two Multi-GPU approaches to answer the question. +\subsection{Comparison of the CUDA-OpenMP and the CUDA-MPI approaches} + +In the previuos section we saw that both approches are very effecient +to reduce the execution times the sparse and full polynomials. In +this section we try to compare these two approaches. \subsubsection{Solving sparse polynomials} In this experiment three sparse polynomials of size 200K, 800K and 1,4M are investigated. \begin{figure}[htbp] \centering \includegraphics[angle=-90,width=0.5\textwidth]{Sparse} -\caption{Execution time for solving sparse polynomials of three distinct sizes on multiple GPUs using MPI and OpenMP approaches using Ehrlich-Aberth} +\caption{Execution times to solvs sparse polynomials of three + distinct sizes on multiple GPUs using MPI and OpenMP with the + Ehrlich-Aberth method} \label{fig:05} \end{figure} -In Figure~\ref{fig:05} there two curves for each polynomial size : one for the MPI-CUDA and another for the OpenMP. We can see that the results are similar between OpenMP and MPI for the polynomials size of 200K. For the size of 800K, the MPI version is a little slower than the OpenMP approach but for the 1,4 millions size, there is a slight advantage for the MPI version. +In Figure~\ref{fig:05} there is one curve for CUDA-MPI and another one +for CUDA-OpenMP. We can see that the results are quite similar between +OpenMP and MPI for the polynomials size of 200K. For the size of 800K, +the MPI version is a little bit slower than the OpenMP approach but for +the 1,4 millions size, there is a slight advantage for the MPI +version. \subsubsection{Solving full polynomials} \begin{figure}[htbp] @@ -1064,14 +1073,22 @@ In Figure~\ref{fig:05} there two curves for each polynomial size : one for the M In Figure~\ref{fig:06}, we can see that when it comes to full polynomials, both approaches are almost equivalent. \subsubsection{Solving sparse and full polynomials of the same size with CUDA-MPI} -In this experiment we compare the execution time of the EA algorithm according to the number of GPUs for solving sparse and full polynomials on Multi-GPU using MPI. We chose three sparse and full polynomials of size 200K, 800K and 1,4M. + +In this experiment we compare the execution time of the EA algorithm +according to the number of GPUs to solve sparse and full +polynomials on multiples GPUs using MPI. We chose three sparse and full +polynomials of size 200K, 800K and 1,4M. \begin{figure}[htbp] \centering \includegraphics[angle=-90,width=0.5\textwidth]{MPI} -\caption{Execution time for solving sparse and full polynomials of three distinct sizes on multiple GPUs using MPI} +\caption{Execution times to solve sparse and full polynomials of three distinct sizes on multiple GPUs using MPI.} \label{fig:07} \end{figure} -in figure ~\ref{fig:07} we can see that CUDA-MPI can solve sparse and full polynomials of high degrees, the execution time with sparse polynomial are very low comparing to full polynomials. with sparse polynomials the number of monomial are reduce, consequently the number of operation are reduce than the execution time decrease. +In Figure~\ref{fig:07} we can see that CUDA-MPI can solve sparse and +full polynomials of high degrees, the execution times with sparse +polynomial are very low compared to full polynomials. With sparse +polynomials the number of monomials is reduced, consequently the number +of operations is reduced and the execution time decreases. \subsubsection{Solving sparse and full polynomials of the same size with CUDA-OpenMP} @@ -1082,17 +1099,23 @@ in figure ~\ref{fig:07} we can see that CUDA-MPI can solve sparse and full polyn \label{fig:08} \end{figure} -Figure ~\ref{fig:08} shows the impact of sparsity on the effectiveness of the CUDA-OpenMP approach. We can see that the impact fellows the same pattern, a difference in execution time in favor of the sparse polynomials. -%SIDER : il faut une explication ici. je ne vois pas de prime abords, qu'est-ce qui engendre cette différence, car quelques soient les coefficients nulls ou non nulls, c'est toutes les racines qui sont calculées qu'elles soient similaires ou non (degrés de multiplicité). -\subsection{Scalability of the EA method on Multi-GPU to solve very high degree polynomials} -These experiments report the execution time according to the degrees of polynomials ranging from 1,000,000 to 5,000,000 for both approaches with sparse and full polynomials. +Figure ~\ref{fig:08} shows the impact of sparsity on the effectiveness of the CUDA-OpenMP approach. We can see that the impact follows the same pattern, a difference in execution time in favor of the sparse polynomials. + +\subsection{Scalability of the EA method on multiple GPUs to solve very high degree polynomials} +These experiments report the execution times of the EA method for +sparse and full polynomials ranging from 1,000,000 to 5,000,000. \begin{figure}[htbp] \centering \includegraphics[angle=-90,width=0.5\textwidth]{big} \caption{Execution times in seconds of the Ehrlich-Aberth method for solving full polynomials of high degree on 4 GPUs for sizes ranging from 1M to 5M} \label{fig:09} \end{figure} -In figure ~\ref{fig:09} we can see that both approaches are scalable and can solve very high degree polynomials. With full polynomial both approaches give interestingly very similar results. For the sparse case however, there are a noticeable difference in favour of MPI when the degree is above 4M. Between 1M and 3M, the OMP approach is more effective and under 1M degree, OMP and MPI approaches are almost equivalent. +In Figure~\ref{fig:09} we can see that both approaches are scalable +and can solve very high degree polynomials. With full polynomial both +approaches give very similar results. However, for sparse polynomials +there are a noticeable difference in favour of MPI when the degree is +above 4 millions. Between 1 and 3 millions, OpenMP is more effecient. +Under 1 million, OpenMPI and MPI are almost equivalent. %SIDER : il faut une explication sur les différences ici aussi. @@ -1220,8 +1243,10 @@ Our next objective is to extend the model presented here at clusters of nodes fe % use section* for acknowledgment \section*{Acknowledgment} +Computations have been performed on the supercomputer facilities of +the Mésocentre de calcul de Franche-Comté. We also would like to thank +Nvidia for hardware donation under CUDA Research Center 2014. -The authors would like to thank...