]> AND Private Git Repository - kahina_paper2.git/blob - paper.tex
Logo AND Algorithmique Numérique Distribuée

Private GIT Repository
f3b0a91ecf424f18553c01d0c8ba9b25cfc3ec74
[kahina_paper2.git] / paper.tex
1
2 %% bare_conf.tex
3 %% V1.4b
4 %% 2015/08/26
5 %% by Michael Shell
6 %% See:
7 %% http://www.michaelshell.org/
8 %% for current contact information.
9 %%
10 %% This is a skeleton file demonstrating the use of IEEEtran.cls
11 %% (requires IEEEtran.cls version 1.8b or later) with an IEEE
12 %% conference paper.
13 %%
14 %% Support sites:
15 %% http://www.michaelshell.org/tex/ieeetran/
16 %% http://www.ctan.org/pkg/ieeetran
17 %% and
18 %% http://www.ieee.org/
19
20 %%*************************************************************************
21 %% Legal Notice:
22 %% This code is offered as-is without any warranty either expressed or
23 %% implied; without even the implied warranty of MERCHANTABILITY or
24 %% FITNESS FOR A PARTICULAR PURPOSE! 
25 %% User assumes all risk.
26 %% In no event shall the IEEE or any contributor to this code be liable for
27 %% any damages or losses, including, but not limited to, incidental,
28 %% consequential, or any other damages, resulting from the use or misuse
29 %% of any information contained here.
30 %%
31 %% All comments are the opinions of their respective authors and are not
32 %% necessarily endorsed by the IEEE.
33 %%
34 %% This work is distributed under the LaTeX Project Public License (LPPL)
35 %% ( http://www.latex-project.org/ ) version 1.3, and may be freely used,
36 %% distributed and modified. A copy of the LPPL, version 1.3, is included
37 %% in the base LaTeX documentation of all distributions of LaTeX released
38 %% 2003/12/01 or later.
39 %% Retain all contribution notices and credits.
40 %% ** Modified files should be clearly indicated as such, including  **
41 %% ** renaming them and changing author support contact information. **
42 %%*************************************************************************
43
44
45 % *** Authors should verify (and, if needed, correct) their LaTeX system  ***
46 % *** with the testflow diagnostic prior to trusting their LaTeX platform ***
47 % *** with production work. The IEEE's font choices and paper sizes can   ***
48 % *** trigger bugs that do not appear when using other class files.       ***                          ***
49 % The testflow support page is at:
50 % http://www.michaelshell.org/tex/testflow/
51
52
53
54 \documentclass[conference]{IEEEtran}
55 % Some Computer Society conferences also require the compsoc mode option,
56 % but others use the standard conference format.
57 %
58 % If IEEEtran.cls has not been installed into the LaTeX system files,
59 % manually specify the path to it like:
60 % \documentclass[conference]{../sty/IEEEtran}
61
62
63
64
65
66 % Some very useful LaTeX packages include:
67 % (uncomment the ones you want to load)
68
69
70 % *** MISC UTILITY PACKAGES ***
71 %
72 %\usepackage{ifpdf}
73 % Heiko Oberdiek's ifpdf.sty is very useful if you need conditional
74 % compilation based on whether the output is pdf or dvi.
75 % usage:
76 % \ifpdf
77 %   % pdf code
78 % \else
79 %   % dvi code
80 % \fi
81 % The latest version of ifpdf.sty can be obtained from:
82 % http://www.ctan.org/pkg/ifpdf
83 % Also, note that IEEEtran.cls V1.7 and later provides a builtin
84 % \ifCLASSINFOpdf conditional that works the same way.
85 % When switching from latex to pdflatex and vice-versa, the compiler may
86 % have to be run twice to clear warning/error messages.
87
88
89
90
91
92
93 % *** CITATION PACKAGES ***
94 %
95 %\usepackage{cite}
96 % cite.sty was written by Donald Arseneau
97 % V1.6 and later of IEEEtran pre-defines the format of the cite.sty package
98 % \cite{} output to follow that of the IEEE. Loading the cite package will
99 % result in citation numbers being automatically sorted and properly
100 % "compressed/ranged". e.g., [1], [9], [2], [7], [5], [6] without using
101 % cite.sty will become [1], [2], [5]--[7], [9] using cite.sty. cite.sty's
102 % \cite will automatically add leading space, if needed. Use cite.sty's
103 % noadjust option (cite.sty V3.8 and later) if you want to turn this off
104 % such as if a citation ever needs to be enclosed in parenthesis.
105 % cite.sty is already installed on most LaTeX systems. Be sure and use
106 % version 5.0 (2009-03-20) and later if using hyperref.sty.
107 % The latest version can be obtained at:
108 % http://www.ctan.org/pkg/cite
109 % The documentation is contained in the cite.sty file itself.
110
111
112
113
114
115
116 % *** GRAPHICS RELATED PACKAGES ***
117 %
118 \ifCLASSINFOpdf
119    \usepackage[pdftex]{graphicx}
120    
121   % declare the path(s) where your graphic files are
122   % \graphicspath{{../pdf/}{../jpeg/}}
123   % and their extensions so you won't have to specify these with
124   % every instance of \includegraphics
125   % \DeclareGraphicsExtensions{.pdf,.jpeg,.png}
126 \else
127   % or other class option (dvipsone, dvipdf, if not using dvips). graphicx
128   % will default to the driver specified in the system graphics.cfg if no
129   % driver is specified.
130   % \usepackage[dvips]{graphicx}
131   % declare the path(s) where your graphic files are
132   % \graphicspath{{../eps/}}
133   % and their extensions so you won't have to specify these with
134   % every instance of \includegraphics
135   % \DeclareGraphicsExtensions{.eps}
136 \fi
137 % graphicx was written by David Carlisle and Sebastian Rahtz. It is
138 % required if you want graphics, photos, etc. graphicx.sty is already
139 % installed on most LaTeX systems. The latest version and documentation
140 % can be obtained at: 
141 % http://www.ctan.org/pkg/graphicx
142 % Another good source of documentation is "Using Imported Graphics in
143 % LaTeX2e" by Keith Reckdahl which can be found at:
144 % http://www.ctan.org/pkg/epslatex
145 %
146 % latex, and pdflatex in dvi mode, support graphics in encapsulated
147 % postscript (.eps) format. pdflatex in pdf mode supports graphics
148 % in .pdf, .jpeg, .png and .mps (metapost) formats. Users should ensure
149 % that all non-photo figures use a vector format (.eps, .pdf, .mps) and
150 % not a bitmapped formats (.jpeg, .png). The IEEE frowns on bitmapped formats
151 % which can result in "jaggedy"/blurry rendering of lines and letters as
152 % well as large increases in file sizes.
153 %
154 % You can find documentation about the pdfTeX application at:
155 % http://www.tug.org/applications/pdftex
156
157
158
159
160
161 % *** MATH PACKAGES ***
162 %
163 \usepackage{amsmath}
164 % A popular package from the American Mathematical Society that provides
165 % many useful and powerful commands for dealing with mathematics.
166 %
167 % Note that the amsmath package sets \interdisplaylinepenalty to 10000
168 % thus preventing page breaks from occurring within multiline equations. Use:
169 %\interdisplaylinepenalty=2500
170 % after loading amsmath to restore such page breaks as IEEEtran.cls normally
171 % does. amsmath.sty is already installed on most LaTeX systems. The latest
172 % version and documentation can be obtained at:
173 % http://www.ctan.org/pkg/amsmath
174
175
176
177
178
179 % *** SPECIALIZED LIST PACKAGES ***
180 %
181 \usepackage{algorithmic}
182 % algorithmic.sty was written by Peter Williams and Rogerio Brito.
183 % This package provides an algorithmic environment fo describing algorithms.
184 % You can use the algorithmic environment in-text or within a figure
185 % environment to provide for a floating algorithm. Do NOT use the algorithm
186 % floating environment provided by algorithm.sty (by the same authors) or
187 % algorithm2e.sty (by Christophe Fiorio) as the IEEE does not use dedicated
188 % algorithm float types and packages that provide these will not provide
189 % correct IEEE style captions. The latest version and documentation of
190 % algorithmic.sty can be obtained at:
191 % http://www.ctan.org/pkg/algorithms
192 % Also of interest may be the (relatively newer and more customizable)
193 % algorithmicx.sty package by Szasz Janos:
194 % http://www.ctan.org/pkg/algorithmicx
195 \usepackage[ruled,vlined]{algorithm2e}
196
197
198
199 % *** ALIGNMENT PACKAGES ***
200 %
201 %\usepackage{array}
202 % Frank Mittelbach's and David Carlisle's array.sty patches and improves
203 % the standard LaTeX2e array and tabular environments to provide better
204 % appearance and additional user controls. As the default LaTeX2e table
205 % generation code is lacking to the point of almost being broken with
206 % respect to the quality of the end results, all users are strongly
207 % advised to use an enhanced (at the very least that provided by array.sty)
208 % set of table tools. array.sty is already installed on most systems. The
209 % latest version and documentation can be obtained at:
210 % http://www.ctan.org/pkg/array
211
212
213 % IEEEtran contains the IEEEeqnarray family of commands that can be used to
214 % generate multiline equations as well as matrices, tables, etc., of high
215 % quality.
216
217
218
219
220 % *** SUBFIGURE PACKAGES ***
221 %\ifCLASSOPTIONcompsoc
222 %  \usepackage[caption=false,font=normalsize,labelfont=sf,textfont=sf]{subfig}
223 %\else
224 %  \usepackage[caption=false,font=footnotesize]{subfig}
225 %\fi
226 % subfig.sty, written by Steven Douglas Cochran, is the modern replacement
227 % for subfigure.sty, the latter of which is no longer maintained and is
228 % incompatible with some LaTeX packages including fixltx2e. However,
229 % subfig.sty requires and automatically loads Axel Sommerfeldt's caption.sty
230 % which will override IEEEtran.cls' handling of captions and this will result
231 % in non-IEEE style figure/table captions. To prevent this problem, be sure
232 % and invoke subfig.sty's "caption=false" package option (available since
233 % subfig.sty version 1.3, 2005/06/28) as this is will preserve IEEEtran.cls
234 % handling of captions.
235 % Note that the Computer Society format requires a larger sans serif font
236 % than the serif footnote size font used in traditional IEEE formatting
237 % and thus the need to invoke different subfig.sty package options depending
238 % on whether compsoc mode has been enabled.
239 %
240 % The latest version and documentation of subfig.sty can be obtained at:
241 % http://www.ctan.org/pkg/subfig
242
243
244
245
246 % *** FLOAT PACKAGES ***
247 %
248 %\usepackage{fixltx2e}
249 % fixltx2e, the successor to the earlier fix2col.sty, was written by
250 % Frank Mittelbach and David Carlisle. This package corrects a few problems
251 % in the LaTeX2e kernel, the most notable of which is that in current
252 % LaTeX2e releases, the ordering of single and double column floats is not
253 % guaranteed to be preserved. Thus, an unpatched LaTeX2e can allow a
254 % single column figure to be placed prior to an earlier double column
255 % figure.
256 % Be aware that LaTeX2e kernels dated 2015 and later have fixltx2e.sty's
257 % corrections already built into the system in which case a warning will
258 % be issued if an attempt is made to load fixltx2e.sty as it is no longer
259 % needed.
260 % The latest version and documentation can be found at:
261 % http://www.ctan.org/pkg/fixltx2e
262
263
264 %\usepackage{stfloats}
265 % stfloats.sty was written by Sigitas Tolusis. This package gives LaTeX2e
266 % the ability to do double column floats at the bottom of the page as well
267 % as the top. (e.g., "\begin{figure*}[!b]" is not normally possible in
268 % LaTeX2e). It also provides a command:
269 %\fnbelowfloat
270 % to enable the placement of footnotes below bottom floats (the standard
271 % LaTeX2e kernel puts them above bottom floats). This is an invasive package
272 % which rewrites many portions of the LaTeX2e float routines. It may not work
273 % with other packages that modify the LaTeX2e float routines. The latest
274 % version and documentation can be obtained at:
275 % http://www.ctan.org/pkg/stfloats
276 % Do not use the stfloats baselinefloat ability as the IEEE does not allow
277 % \baselineskip to stretch. Authors submitting work to the IEEE should note
278 % that the IEEE rarely uses double column equations and that authors should try
279 % to avoid such use. Do not be tempted to use the cuted.sty or midfloat.sty
280 % packages (also by Sigitas Tolusis) as the IEEE does not format its papers in
281 % such ways.
282 % Do not attempt to use stfloats with fixltx2e as they are incompatible.
283 % Instead, use Morten Hogholm'a dblfloatfix which combines the features
284 % of both fixltx2e and stfloats:
285 %
286 % \usepackage{dblfloatfix}
287 % The latest version can be found at:
288 % http://www.ctan.org/pkg/dblfloatfix
289
290
291
292
293 % *** PDF, URL AND HYPERLINK PACKAGES ***
294 %
295 %\usepackage{url}
296 % url.sty was written by Donald Arseneau. It provides better support for
297 % handling and breaking URLs. url.sty is already installed on most LaTeX
298 % systems. The latest version and documentation can be obtained at:
299 % http://www.ctan.org/pkg/url
300 % Basically, \url{my_url_here}.
301
302
303
304
305 % *** Do not adjust lengths that control margins, column widths, etc. ***
306 % *** Do not use packages that alter fonts (such as pslatex).         ***
307 % There should be no need to do such things with IEEEtran.cls V1.6 and later.
308 % (Unless specifically asked to do so by the journal or conference you plan
309 % to submit to, of course. )
310
311
312 % correct bad hyphenation here
313 \hyphenation{op-tical net-works semi-conduc-tor}
314 %\usepackage{graphicx}
315 \bibliographystyle{IEEEtran}
316 % argument is your BibTeX string definitions and bibliography database(s)
317 %\bibliography{IEEEabrv,../bib/paper}
318 %\bibliographystyle{elsarticle-num}
319
320
321
322
323 \usepackage{amsfonts}
324 \usepackage[utf8]{inputenc}
325 \usepackage[T1]{fontenc}
326 \usepackage[textsize=footnotesize]{todonotes}
327 \newcommand{\LZK}[2][inline]{%
328   \todo[color=red!10,#1]{\sffamily\textbf{LZK:} #2}\xspace}
329
330
331
332
333
334 \begin{document}
335 %
336 % paper title
337 % Titles are generally capitalized except for words such as a, an, and, as,
338 % at, but, by, for, in, nor, of, on, or, the, to and up, which are usually
339 % not capitalized unless they are the first or last word of the title.
340 % Linebreaks \\ can be used within to get better formatting as desired.
341 % Do not put math or special symbols in the title.
342 \title{Two parallel implementations of Ehrlich-Aberth algorithm for root finding of polynomials
343 on  multiple GPUs with OpenMP and MPI}
344
345
346 % author names and affiliations
347 % use a multiple column layout for up to three different
348 % affiliations
349 \author{\IEEEauthorblockN{Michael Shell}
350 \IEEEauthorblockA{School of Electrical and\\Computer Engineering\\
351 Georgia Institute of Technology\\
352 Atlanta, Georgia 30332--0250\\
353 Email: http://www.michaelshell.org/contact.html}
354 \and
355 \IEEEauthorblockN{Homer Simpson}
356 \IEEEauthorblockA{Twentieth Century Fox\\
357 Springfield, USA\\
358 Email: homer@thesimpsons.com}
359 \and
360 \IEEEauthorblockN{James Kirk\\ and Montgomery Scott}
361 \IEEEauthorblockA{Starfleet Academy\\
362 San Francisco, California 96678--2391\\
363 Telephone: (800) 555--1212\\
364 Fax: (888) 555--1212}}
365
366 % conference papers do not typically use \thanks and this command
367 % is locked out in conference mode. If really needed, such as for
368 % the acknowledgment of grants, issue a \IEEEoverridecommandlockouts
369 % after \documentclass
370
371 % for over three affiliations, or if they all won't fit within the width
372 % of the page, use this alternative format:
373
374 %\author{\IEEEauthorblockN{Michael Shell\IEEEauthorrefmark{1},
375 %Homer Simpson\IEEEauthorrefmark{2},
376 %James Kirk\IEEEauthorrefmark{3}, 
377 %Montgomery Scott\IEEEauthorrefmark{3} and
378 %Eldon Tyrell\IEEEauthorrefmark{4}}
379 %\IEEEauthorblockA{\IEEEauthorrefmark{1}School of Electrical and Computer Engineering\\
380 %Georgia Institute of Technology,
381 %Atlanta, Georgia 30332--0250\\ Email: see http://www.michaelshell.org/contact.html}
382 %\IEEEauthorblockA{\IEEEauthorrefmark{2}Twentieth Century Fox, Springfield, USA\\
383 %Email: homer@thesimpsons.com}
384 %\IEEEauthorblockA{\IEEEauthorrefmark{3}Starfleet Academy, San Francisco, California 96678-2391\\
385 %Telephone: (800) 555--1212, Fax: (888) 555--1212}
386 %\IEEEauthorblockA{\IEEEauthorrefmark{4}Tyrell Inc., 123 Replicant Street, Los Angeles, California 90210--4321}}
387
388
389
390
391 % use for special paper notices
392 %\IEEEspecialpapernotice{(Invited Paper)}
393
394
395
396
397 % make the title area
398 \maketitle
399
400 % As a general rule, do not put math, special symbols or citations
401 % in the abstract
402 \begin{abstract}
403 \LZK{J'ai un peu modifié l'abstract. Sinon à revoir pour le degré max des polynômes après les tests de raph.}
404 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 to find roots of polynomials of degree up-to 1.4 billion. To our knowledge, this is the first paper to present this technology mix to solve such a highly demanding problem in parallel programming. \LZK{Je n'ai pas bien saisi la dernière phrase.}
405 \end{abstract}
406
407 % no keywords
408
409
410
411
412 % For peer review papers, you can put extra information on the cover
413 % page as needed:
414 % \ifCLASSOPTIONpeerreview
415 % \begin{center} \bfseries EDICS Category: 3-BBND \end{center}
416 % \fi
417 %
418 % For peerreview papers, this IEEEtran command inserts a page break and
419 % creates the second title. It will be ignored for other modes.
420 \IEEEpeerreviewmaketitle
421
422
423 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
424 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
425 \section{Introduction}
426 Polynomials are mathematical algebraic structures that play an important role in science and engineering by capturing physical phenomena and expressing any outcome as a function of some unknown variables. Formally speaking, a polynomial $p(x)$ of degree $n$ having $n$ coefficients in the complex plane $\mathbb{C}$ is:
427 \begin{equation}
428 p(x)=\sum_{i=0}^{n}{a_ix^i}.
429 \end{equation}
430 \LZK{Dans ce cas le polynôme a $n+1$ coefficients !}
431
432 The root-finding problem consists in finding the $n$ different values of the unknown variable $x$ for which $p(x)=0$. Such values are called zeros or roots of $p$. If zeros are $\{\alpha_{i}\}_{1\leq i\leq n}$, then $p(x)$ can be written as :
433 \begin{equation}
434  p(x)=a_n\prod_{i=1}^n(x-\alpha_i), a_0 a_n\neq 0.
435 \end{equation}
436
437 The problem of finding the roots of polynomials can be encountered in numerous applications. \LZK{A mon avis on peut supprimer cette phrase}
438 Most of the numerical methods that deal with the polynomial root-finding problem are simultaneous ones, \textit{i.e.} the iterative methods to find simultaneous approximations of the $n$ polynomial zeros. 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. The first method of this group is Durand-Kerner method:
439 \begin{equation}
440 \label{DK}
441  DK: z_i^{k+1}=z_{i}^{k}-\frac{P(z_i^{k})}{\prod_{i\neq j}(z_i^{k}-z_j^{k})},   i = 1, \ldots, n,
442 \end{equation}
443 where $z_i^k$ is the $i^{th}$ root of the polynomial $p$ at the iteration $k$. Another method discovered by Borsch-Supan~\cite{ Borch-Supan63} and also described by Ehrlich~\cite{Ehrlich67} and Aberth~\cite{Aberth73} uses a different iteration form as follows:
444 %%\begin{center}
445 \begin{equation}
446 \label{Eq:EA}
447  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, \ldots, n,
448 \end{equation}
449 %%\end{center}
450 where $p'(z)$ is the polynomial derivative of $p$ evaluated in the point $z$.
451
452 %Aberth, Ehrlich and Farmer-Loizou~\cite{Loizou83} have proved that
453 %the Ehrlich-Aberth method (EA) has a cubic order of convergence for simple roots whereas the Durand-Kerner has a quadratic order of %convergence.
454
455 The main problem of the simultaneous methods is that the necessary time needed for the convergence increases with the increasing of the polynomial's degree. Many authors have treated the problem of implementing  simultaneous methods in parallel. Freeman~\cite{Freeman89} implemented and compared DK, EA and another method of the fourth order of convergence proposed by Farmer and Loizou~\cite{Loizou83} on a 8-processor linear chain, for polynomials of degree up-to 8. The method of Farmer and Loizou~\cite{Loizou83} often diverges, but the first two methods (DK and EA) have a speed-up equals to 5.5. Later, 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^{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 of parallelization for a shared memory architecture with \textit{OpenMP} and for a distributed memory one with \textit{MPI}. They are able to compute the roots of sparse polynomials of degree 10,000 in 116 seconds with \textit{OpenMP} and 135 seconds with \textit{MPI} only by using 8 personal computers and 2 communications per iteration. \LZK{je suppose que c'est pour la version mpi (only by using 8 personal computers and 2 communications per iteration). A t on utilisé le même nombre de procs pour les deux versions openmp et mpi} The authors showed an interesting speedup comparing to the sequential implementation that takes up-to 3,300 seconds to obtain same results.
456
457 Very few work had been performed since then 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 Units) has exceeded that of 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 and 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.
458
459 %Finding polynomial roots rapidly and accurately is the main objective of our work. We consider two architectures: shared-memory computers with OpenMP API and distributed-memory computers with MPI API. The first approach is based on threads from the same system process, with each thread attached to one GPU and after the various memory allocations, each thread launches its part of computations. To do this we must first load on the GPU required data and after the computations are carried, repatriate the result on the host. The second approach i.e distributed memory with MPI relies on the MPI library which is often used for parallel programming~\cite{Peter96} in cluster systems because it is a message-passing programming language. Each GPU is attached to one MPI process, and a loop is in charge of the distribution of tasks between the MPI processes. This solution can be used on one GPU, or executed on a distributed cluster of GPUs, employing the Message Passing Interface (MPI) to communicate between separate CUDA cards. This solution permits scaling of the problem size to larger classes than would be possible on a single device and demonstrates the performance which users might expect from future HPC architectures where accelerators are deployed.
460
461 Finding polynomial roots rapidly and accurately is the main objective of our work. In this paper we propose the parallelization of Ehrlich-Aberth method using two parallel programming paradigms OpenMP and MPI on multi-GPU platforms. We consider two architectures: shared memory and distributed memory computers. The first parallel algorithm is implemented on shared memory computers by 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. The second parallel algorithm uses the MPI API, such that each GPU is attached and managed by a MPI process. The GPUs exchange their data by message-passing communications. This latter approach is more used on distributed memory clusters to solve very complex problems that are too large for traditional supercomputers, which are very expensive to build and run.
462 \LZK{Cette partie est réécrite. \\ Sinon qu'est ce qui a été fait pour l'accuracy dans ce papier (Finding polynomial roots rapidly and accurately is the main objective of our work.)?}
463  
464 %This paper is organized as follows. In Section~\ref{sec2} we recall the Ehrlich-Aberth method. In section~\ref{sec3} we present EA algorithm on single GPU. In section~\ref{sec4} we propose the EA algorithm implementation on Multi-GPU for (OpenMP-CUDA) approach and (MPI-CUDA) approach. In sectioné\ref{sec5} we present our experiments and discus it. Finally, Section~\ref{sec6} concludes this paper and gives some hints for future research directions in this topic.}
465
466 The paper is organized as follows. In Section~\ref{sec2} we present three different parallel programming models OpenMP, MPI and CUDA.
467 \LZK{A revoir toute cette organization}
468
469 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
470 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
471  
472 \section{Parallel programming models}
473 \label{sec2}
474 In this section we present three different parallel programming models: OpenMP, MPI and CUDA.
475  
476 \subsection{OpenMP}
477 %Open Multi-Processing (OpenMP) is a shared memory architecture API that provides multi thread capacity~\cite{openmp13}. OpenMP is a portable approach for parallel programming on shared memory systems based on compiler directives, that can be included in order to parallelize a loop. In this way, a set of loops can be distributed along the different threads that will access to different data allocated in local shared memory. One of the advantages of OpenMP is its global view of application memory address space that allows relatively fast development of parallel applications with easier maintenance. However, it is often difficult to get high rates of performance in large scale applications. Although usage of OpenMP  threads and managed data explicitly done with MPI can be considered, this approcache undermines the advantages of OpenMP.
478
479 %\subsection{OpenMP} 
480 %OpenMP is a shared memory programming API based on threads from
481 %the same system process. Designed for multiprocessor shared memory UMA or
482 %NUMA [10], it relies on the execution model SPMD ( Single Program, Multiple Data Stream )
483 %where the thread "master" and threads "slaves" asynchronously execute their codes
484 %communicate / synchronize via shared memory [7]. It also helps to build
485 %the loop parallelism and is very suitable for an incremental code parallelization
486 %Sequential natively. Threads share some or all of the available memory and can
487 %have private memory areas [6].
488
489 OpenMP (Open Multi-processing) is an application programming interface for shared memory parallel programming~\cite{openmp13}. It is a portable approach based on the multithreading designed for shared memory computers, where a master thread forks a number of slave threads which execute blocks of code in parallel. An OpenMP program alternates sequential regions and parallel regions of code, where the sequential regions are executed by the master thread and the parallel ones may be executed by multiple threads. During the execution of an OpenMP program the threads communicate their data (read and modified) in the shared memory. One advantage of OpenMP is the global view of the memory address space of an application. This allows relatively a fast development of parallel applications with easier maintenance. However, it is often difficult to get high rates of performances in large scale-applications.
490 \LZK{Cette partie est réécrite. A relire et à améliorer si possible.}  
491
492 \subsection{MPI} 
493 %The MPI (Message Passing Interface) library allows to create computer programs that run on a distributed memory architecture. The various processes have their own environment of execution and execute their code in a asynchronous way, according to the MIMD model  (Multiple Instruction streams, Multiple Data streams); they communicate and synchronize by exchanging messages~\cite{Peter96}. MPI messages are explicitly sent, while the exchanges are implicit within the framework of a multi-thread programming environment like OpenMP or Pthreads.
494
495 MPI (Message Passing Interface) is a portable message passing style of the parallel programming designed especially for the distributed memory architectures~\cite{Peter96}. In most MPI implementations, a computation contains a fixed set of processes created at the initialization of the program in such way one process is created per processor. The processes synchronize their computations and communicate by sending/receiving messages to/from other processes. In this case, the data are explicitly exchanged by message passing while the data exchanges are implicit in a multithread programming model like OpenMP and Pthreads. However in the MPI programming model, the processes may either execute different programs referred to as multiple program multiple data (MPMD) or every process executes the same program (SPMD). The MPI approach is one of most used HPC programming model to solve large scale and complex applications.
496 \LZK{Cette partie est réécrite. A relire et à améliorer si possible.}
497  
498 \subsection{CUDA}
499 CUDA (an acronym for Compute Unified Device Architecture) is a parallel computing architecture developed by NVIDIA~\cite{CUDA10}. The
500 unit of execution in CUDA is called a thread. Each thread executes a kernel by the streaming processors in parallel. In CUDA,
501 a group of threads that are executed together is called a thread block, and the computational grid consists of a grid of thread
502 blocks. Additionally, a thread block can use the shared memory on a single multiprocessor while the grid executes a single
503 CUDA program logically in parallel. Thus in CUDA programming, it is necessary to design carefully the arrangement of the thread
504 blocks in order to ensure low latency and a proper usage of shared memory, since it can be shared only in a thread block
505 scope. The effective bandwidth of each memory space depends on the memory access pattern. Since the global memory has lower
506 bandwidth than the shared memory, the global memory accesses should be minimized.
507
508
509 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.
510
511 \section{The EA algorithm on a single GPU}
512 \label{sec3}
513 \subsection{The EA method}
514
515 A cubically convergent iteration method to find zeros of
516 polynomials was proposed by O. Aberth~\cite{Aberth73}. The
517 Ehrlich-Aberth (EA is short) method contains 4 main steps, presented in what
518 follows.
519
520 %The Aberth method is a purely algebraic derivation. 
521 %To illustrate the derivation, we let $w_{i}(z)$ be the product of linear factors 
522
523 %\begin{equation}
524 %w_{i}(z)=\prod_{j=1,j \neq i}^{n} (z-x_{j})
525 %\end{equation}
526
527 %And let a rational function $R_{i}(z)$ be the correction term of the
528 %Weistrass method~\cite{Weierstrass03}
529
530 %\begin{equation}
531 %R_{i}(z)=\frac{p(z)}{w_{i}(z)} , i=1,2,...,n.
532 %\end{equation}
533
534 %Differentiating the rational function $R_{i}(z)$ and applying the
535 %Newton method, we have:
536
537 %\begin{equation}
538 %\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
539 %\end{equation}
540 %where R_{i}^{'}(z)is the rational function derivative of F evaluated in the point z 
541 %Substituting $x_{j}$ for $z_{j}$ we obtain the Aberth iteration method.% 
542
543
544 \subsubsection{Polynomials Initialization}
545 The initialization of a polynomial $p(z)$ is done by setting each of the $n$ complex coefficients $a_{i}$:
546
547 \begin{equation}
548 \label{eq:SimplePolynome}
549   p(z)=\sum{a_{i}z^{n-i}} , a_{n} \neq 0,a_{0}=1, a_{i}\subset C
550 \end{equation}
551
552
553 \subsubsection{Vector $Z^{(0)}$ Initialization}
554 \label{sec:vec_initialization}
555 As for any iterative method, we need to choose $n$ initial guess points $z^{0}_{i}, i = 1, . . . , n.$
556 The initial guess is very important since the number of steps needed by the iterative method to reach
557 a given approximation strongly depends on it.
558 In~\cite{Aberth73} the Ehrlich-Aberth iteration is started by selecting $n$
559 equi-distant points on a circle of center 0 and radius r, where r is
560 an upper bound to the moduli of the zeros. Later, Bini and al.~\cite{Bini96}
561 performed this choice by selecting complex numbers along different
562 circles which relies on the result of~\cite{Ostrowski41}.
563
564 \begin{equation}
565 \label{eq:radiusR}
566 %%\begin{align}
567 \sigma_{0}=\frac{u+v}{2};u=\frac{\sum_{i=1}^{n}u_{i}}{n.max_{i=1}^{n}u_{i}};
568 v=\frac{\sum_{i=0}^{n-1}v_{i}}{n.min_{i=0}^{n-1}v_{i}};\\
569 %%\end{align}
570 \end{equation}
571 Where:
572 \begin{equation}
573 u_{i}=2.|a_{i}|^{\frac{1}{i}};
574 v_{i}=\frac{|\frac{a_{n}}{a_{i}}|^{\frac{1}{n-i}}}{2}.
575 \end{equation}
576
577 \subsubsection{Iterative Function}
578 The operator used by the Aberth method  corresponds to the
579 equation~\ref{Eq:EA1}, it enables the convergence towards
580 the polynomials zeros, provided all the roots are distinct.
581
582 %Here we give a second form of the iterative function used by the Ehrlich-Aberth method: 
583
584 \begin{equation}
585 \label{Eq:EA1}
586 EA: z^{k+1}_{i}=z_{i}^{k}-\frac{\frac{p(z_{i}^{k})}{p'(z_{i}^{k})}}
587 {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,. . . .,n
588 \end{equation}
589
590 \subsubsection{Convergence Condition}
591 The convergence condition determines the termination of the algorithm. It consists in stopping the iterative function  when the roots are sufficiently stable. We consider that the method converges sufficiently when:
592
593 \begin{equation}
594 \label{eq:Aberth-Conv-Cond}
595 \forall i \in [1,n];\vert\frac{z_{i}^{k}-z_{i}^{k-1}}{z_{i}^{k}}\vert<\xi
596 \end{equation}
597
598
599 %\begin{figure}[htbp]
600 %\centering
601  % \includegraphics[angle=-90,width=0.5\textwidth]{EA-Algorithm}
602 %\caption{The Ehrlich-Aberth algorithm on single GPU}
603 %\label{fig:03}
604 %\end{figure}
605
606 %the Ehrlich-Aberth method is an iterative  method, contain 4 steps, start from the initial approximations of all the
607 %roots of the polynomial,the second step initialize the solution vector $Z$ using the Guggenheimer method to assure the distinction of the initial vector roots, than in step 3 we apply the the iterative function based on the Newton's method and Weiestrass operator[...,...], wich will make it possible to converge to the roots solution, provided that all the root are different. At the end of each application of the iterative function, a stop condition is verified consists in stopping the iterative process when the whole of the modules of the roots
608 %are lower than a fixed value $ε$ 
609
610
611 \subsection{EA parallel implementation on CUDA}
612 Like any parallel code, a GPU parallel implementation first
613 requires to determine the sequential tasks and the
614 parallelizable parts of the sequential version of the
615 program/algorithm. In our case, all the operations that are easy
616 to execute in parallel must be made by the GPU to accelerate
617 the execution of the application, like the step 3 and step 4. On the other hand, all the
618 sequential operations and the operations that have data
619 dependencies between threads or recursive computations must
620 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. 
621
622 The code is organzed  by what is named kernels, portions o code that are run on GPU devices. For step 3, there are two kernels, the
623 first named \textit{save} is used to save vector $Z^{K-1}$ and the seconde one is named
624 \textit{update} and is used to update the $Z^{K}$ vector. For step 4, a kernel 
625 tests the convergence of the method. In order to
626 compute the function H, we have two possibilities: either to use
627 the Jacobi mode, or the Gauss-Seidel mode of iterating which uses the
628 most recent computed roots. It is well known that the Gauss-
629 Seidel mode converges more quickly. So, we used the Gauss-Seidel mode of iteration. To
630 parallelize the code, we created kernels and many functions to
631 be executed on the GPU for all the operations dealing with the
632 computation on complex numbers and the evaluation of the
633 polynomials. As said previously, we managed both functions
634 of evaluation of a polynomial: the normal method, based on
635 the method of Horner and the method based on the logarithm
636 of the polynomial. All these methods were rather long to
637 implement, as the development of corresponding kernels with
638 CUDA is longer than on a CPU host. This comes in particular
639 from the fact that it is very difficult to debug CUDA running
640 threads like threads on a CPU host. In the following paragraph
641 Algorithm~\ref{alg1-cuda} shows the GPU parallel implementation of Ehrlich-Aberth method.
642
643 \begin{enumerate}
644 \begin{algorithm}[htpb]
645 \label{alg1-cuda}
646 %\LinesNumbered
647 \caption{CUDA Algorithm to find roots with the Ehrlich-Aberth method}
648
649 \KwIn{$Z^{0}$ (Initial root's vector), $\varepsilon$ (Error tolerance
650   threshold), P (Polynomial to solve), Pu (Derivative of P), $n$ (Polynomial degrees), $\Delta z_{max}$ (Maximum value of stop condition)}
651
652 \KwOut {$Z$ (Solution root's vector), $ZPrec$ (Previous solution root's vector)}
653
654 %\BlankLine
655
656 \item Initialization of the of P\;
657 \item Initialization of the of Pu\;
658 \item Initialization of the solution vector $Z^{0}$\;
659 \item Allocate and copy initial data to the GPU global memory\;
660 \item k=0\;
661 \While {$\Delta z_{max} > \epsilon$}{
662 \item Let $\Delta z_{max}=0$\;
663 \item $ kernel\_save(ZPrec,Z)$\;
664 \item  k=k+1\;
665 \item $ kernel\_update(Z,P,Pu)$\;
666 \item $kernel\_testConverge(\Delta z_{max},Z,ZPrec)$\;
667
668 }
669 \item Copy results from GPU memory to CPU memory\;
670 \end{algorithm}
671 \end{enumerate}
672 ~\\ 
673
674
675  
676 \section{The EA algorithm on Multi-GPU}
677 \label{sec4}
678 \subsection{MGPU : an OpenMP-CUDA approach}
679 Our OpenMP-CUDA implementation of EA algorithm is based on the hybrid OpenMP and CUDA programming model. It works as follows.
680 Based on the metadata, a shared memory is used to make data evenly shared among OpenMP threads. The shared data are the solution vector $Z$, the polynomial to solve $P$, and  the error vector $\Delta z$. Let (T\_omp) the number of OpenMP threads be equal to the number of GPUs, each OpenMP thread binds to one GPU,  and controls a part of the shared memory, that is a part of the vector Z , that is $(n/num\_gpu)$ roots where $n$ is the polynomial's degree and $num\_gpu$ the total number of available GPUs. Each OpenMP thread copies its data from host memory to GPU’s device memory.Then every GPU will have a grid of computation organized according to the device performance and the size of data on which it runs the computation kernels. %In principle a grid is set by two parameter DimGrid, the number of block per grid, DimBloc: the number of threads per block. The following schema  shows the architecture of (CUDA,OpenMP).
681
682 %\begin{figure}[htbp]
683 %\centering
684  % \includegraphics[angle=-90,width=0.5\textwidth]{OpenMP-CUDA}
685 %\caption{The OpenMP-CUDA architecture}
686 %\label{fig:03}
687 %\end{figure}
688 %Each thread OpenMP compute the kernels on GPUs,than after each iteration they copy out the data from GPU memory to CPU shared memory. The kernels are re-runs is up to the roots converge sufficiently. Here are below the corresponding algorithm:
689
690 $num\_gpus$ OpenMP threads  are created using \verb=omp_set_num_threads();=function (step $3$, Algorithm \ref{alg2-cuda-openmp}), the shared memory is created using \verb=#pragma omp parallel shared()= OpenMP function (line $5$, Algorithm\ref{alg2-cuda-openmp}), then each OpenMP thread allocates memory and copies initial data from CPU memory to GPU global memory, executes the kernels on GPU, but computes only his portion of roots indicated with variable \textit{index} initialized in (line 5, Algorithm \ref{alg2-cuda-openmp}), used as input data in the $kernel\_update$ (line 10, Algorithm \ref{alg2-cuda-openmp}). After each iteration, all OpenMP threads synchronize using \verb=#pragma omp barrier;= to gather all the correct values of $\Delta z$, thus allowing the computation the maximum stop condition on vector $\Delta z$ (line 12, Algorithm \ref{alg2-cuda-openmp}). Finally, threads copy the results from GPU memories to CPU memory. The OpenMP threads execute kernels until the roots sufficiently converge.  
691 \begin{enumerate}
692 \begin{algorithm}[htpb]
693 \label{alg2-cuda-openmp}
694 %\LinesNumbered
695 \caption{CUDA-OpenMP Algorithm to find roots with the Ehrlich-Aberth method}
696
697 \KwIn{$Z^{0}$ (Initial root's vector), $\varepsilon$ (Error tolerance
698   threshold), P (Polynomial to solve), Pu (Derivative of P), $n$ (Polynomial degree), $\Delta z$ ( Vector of errors for stop condition), $num_gpus$ (number of OpenMP threads/ Number of GPUs), $Size$ (number of roots)}
699
700 \KwOut {$Z$ ( Root's vector), $ZPrec$ (Previous root's vector)}
701
702 \BlankLine
703
704 \item Initialization of P\;
705 \item Initialization of Pu\;
706 \item Initialization of the solution vector $Z^{0}$\;
707 \verb=omp_set_num_threads(num_gpus);=
708 \verb=#pragma omp parallel shared(Z,$\Delta$ z,P);=
709 \verb=cudaGetDevice(gpu_id);=
710 \item Allocate and copy initial data from CPU memory to the GPU global memories\;
711 \item index= $Size/num\_gpus$\;
712 \item k=0\;
713 \While {$error > \epsilon$}{
714 \item Let $\Delta z=0$\;
715 \item $ kernel\_save(ZPrec,Z)$\;
716 \item  k=k+1\;
717 \item $ kernel\_update(Z,P,Pu,index)$\;
718 \item $kernel\_testConverge(\Delta z[gpu\_id],Z,ZPrec)$\;
719 %\verb=#pragma omp barrier;=
720 \item error= Max($\Delta z$)\;
721 }
722
723 \item Copy results from GPU memories to CPU memory\;
724 \end{algorithm}
725 \end{enumerate}
726 ~\\ 
727
728
729
730 \subsection{Multi-GPU : an MPI-CUDA approach}
731 %\begin{figure}[htbp]
732 %\centering
733  % \includegraphics[angle=-90,width=0.2\textwidth]{MPI-CUDA}
734 %\caption{The MPI-CUDA architecture }
735 %\label{fig:03}
736 %\end{figure}
737 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.
738
739 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.
740
741 \begin{enumerate}
742 \begin{algorithm}[htpb]
743 \label{alg2-cuda-mpi}
744 %\LinesNumbered
745 \caption{CUDA-MPI Algorithm to find roots with the Ehrlich-Aberth method}
746
747 \KwIn{$Z^{0}$ (Initial root's vector), $\varepsilon$ (Error tolerance
748   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)}
749
750 \KwOut {$Z$ (Solution root's vector), $ZPrec$ (Previous solution root's vector)}
751
752 \BlankLine
753 \item Initialization of P\;
754 \item Initialization of Pu\;
755 \item Initialization of the solution vector $Z^{0}$\;
756 \item Allocate and copy initial data from CPU memories to GPU global memories\;
757 \item $index= Size/num_gpus$\;
758 \item k=0\;
759 \While {$error > \epsilon$}{
760 \item Let $\Delta z=0$\;
761 \item $kernel\_save(ZPrec,Z)$\;
762 \item  k=k+1\;
763 \item $kernel\_update(Z,P,Pu,index)$\;
764 \item $kernel\_testConverge(\Delta z,Z,ZPrec)$\;
765 \item ComputeMaxError($\Delta z$,error)\;
766 \item Copy results from GPU memories to CPU memories\;
767 \item Send $Z[id]$ to all processes\;
768 \item Receive $Z[j]$ from every other process j\;
769 }
770 \end{algorithm}
771 \end{enumerate}
772 ~\\ 
773
774 \section{Experiments}
775 \label{sec5}
776 We study two categories of polynomials: sparse polynomials and full polynomials.\\
777 {\it A sparse polynomial} is a polynomial for which only some coefficients are not null. In this paper, we consider sparse polynomials for which the roots are distributed on 2 distinct circles:
778 \begin{equation}
779         \forall \alpha_{1} \alpha_{2} \in C,\forall n_{1},n_{2} \in N^{*}; P(z)= (z^{n_{1}}-\alpha_{1})(z^{n_{2}}-\alpha_{2})
780 \end{equation}\noindent
781 {\it A full polynomial} is, in contrast, a polynomial for which all the coefficients are not null. A full polynomial is defined by:
782 %%\begin{equation}
783         %%\forall \alpha_{i} \in C,\forall n_{i}\in N^{*}; P(z)= \sum^{n}_{i=1}(z^{n^{i}}.a_{i})
784 %%\end{equation}
785
786 \begin{equation}
787      {\Large \forall a_{i} \in C, i\in N;  p(x)=\sum^{n}_{i=0} a_{i}.x^{i}} 
788 \end{equation}
789 For our tests, a CPU Intel(R) Xeon(R) CPU E5620@2.40GHz and a GPU K40 (with 6 Go of ram) are used. 
790 %SIDER : Une meilleure présentation de l'architecture est à faire ici.
791
792 In order to evaluate both the MGPU and Multi-GPU approaches, we performed a set of experiments on a single GPU and multiple GPUs using OpenMP or MPI by EA algorithm, for both sparse and full polynomials of different sizes.
793 All experimental results obtained are made in double precision data, the convergence threshold of the methods is set to $10^{-7}$.
794 %Since we were more interested in the comparison of the
795 %performance behaviors of Ehrlich-Aberth and Durand-Kerner methods on
796 %CPUs versus on GPUs.
797 The initialization values of the vector solution
798 of the methods are given in %Section~\ref{sec:vec_initialization}.
799
800 \subsection{Evaluating the M-GPU (CUDA-OpenMP) approach}
801
802 We report here  the results of the set of experiments with M-GPU approach for full and sparse polynomials of different degrees, and we compare it with a Single GPU execution.
803 \subsubsection{Execution times in seconds of the EA method for solving sparse polynomials on GPUs using shared memory paradigm with OpenMP}
804  
805 In this experiments we report the execution time of the EA algorithm, on single GPU and Multi-GPU with (2,3,4) GPUs, for different sparse polynomial degrees ranging from 100,000 to 1,400,000.
806
807 \begin{figure}[htbp]
808 \centering
809   \includegraphics[angle=-90,width=0.5\textwidth]{Sparse_omp}
810 \caption{Execution times in seconds of the Ehrlich-Aberth method for solving sparse polynomials on GPUs using shared memory paradigm with OpenMP}
811 \label{fig:01}
812 \end{figure}
813
814 This figure~\ref{fig:01} shows that the (CUDA-OpenMP) Multi-GPU approach reduces the execution time by a factor up to 100 w.r.t the single GPU apparaoch and a by a factor of 1000 for polynomials  exceeding degree 1,000,000. It shows the advantage to use the OpenMP parallel paradigm to gather the capabilities of several GPUs and solve polynomials of very high degrees.   
815
816 \subsubsection{Execution times in seconds of the Ehrlich-Aberth method for solving full polynomials on GPUs using shared memory paradigm with OpenMP}
817
818 The experiments shows the execution time of the EA algorithm, on a single GPU and on multiple GPUs using the CUDA OpenMP approach for full polynomials of degrees ranging from 100,000 to 1,400,000.
819
820 \begin{figure}[htbp]
821 \centering
822   \includegraphics[angle=-90,width=0.5\textwidth]{Full_omp}
823 \caption{Execution times in seconds of the Ehrlich-Aberth method for solving full polynomials on multiple GPUs using shared memory paradigm with OpenMP}
824 \label{fig:03}
825 \end{figure}
826
827 Results with full polynomials show very important savings in execution time. For a polynomial of degree 1,4 million, the CUDA-OpenMP approach with 4 GPUs solves it 4 times as fast as single GPU, thus achieving a quasi-linear speedup.
828
829 \subsection{Evaluting the Multi-GPU (CUDA-MPI) approach}
830 In this part we perform a set of experiments to compare Multi-GPU (CUDA MPI) approach with single GPU, for solving full and sparse polynomials of degrees ranging from 100,000 to 1,400,000.
831
832 \subsubsection{Execution times in seconds of the Ehrlich-Aberth method for solving sparse polynomials on GPUs using distributed memory paradigm with MPI}
833
834 \begin{figure}[htbp]
835 \centering
836   \includegraphics[angle=-90,width=0.5\textwidth]{Sparse_mpi}
837 \caption{Execution times in seconds of the Ehrlich-Aberth method for solving sparse polynomials on GPUs using distributed memory paradigm with MPI}
838 \label{fig:02}
839 \end{figure}
840 ~\\
841 This figure shows 4 curves of execution time of EA algorithm, a curve with single GPU, 3 curves with multiple GPUs (2, 3, 4). We can clearly see that the curve with single GPU is above the other curves, which shows consumption in execution time compared to the Multi-GPU. We can see also that the CUDA-MPI approach reduces the execution time by a factor of 100 for polynomials of degree more than 1,000,000 whereas a single GPU is of the scale 1000.
842 %%SIDER : Je n'ai pas reformuler car je n'ai pas compris la phrase, merci de l'ecrire ici en fran\cais.
843 \\cette figure montre 4 courbes de temps d'exécution pour l'algorithme EA, une courbe avec un seul GPU, 3 courbes pour multiple GPUs(2, 3, 4), on peut constaté clairement que la courbe à un seul GPU est au-dessus des autres courbes, vue sa consomation en temps d'exècution. On peut voir aussi qu'avec l'approche Multi-GPU (CUDA-MPI) reduit le temps d'exècution jusqu'à l'echelle 100 pour le polynômes qui dépasse 1,000,000 tandis que Single GPU est de l'echelle 1000.
844 \subsubsection{Execution times in seconds of the Ehrlich-Aberth method for solving full polynomials on GPUs using distributed memory paradigm with MPI}
845
846 \begin{figure}[htbp]
847 \centering
848   \includegraphics[angle=-90,width=0.5\textwidth]{Full_mpi}
849 \caption{Execution times in seconds of the Ehrlich-Aberth method for full polynomials on GPUs using distributed memory paradigm with MPI}
850 \label{fig:04}
851 \end{figure}
852 %SIDER : Corriger le point de la courbe 3-GPUs qui correpsond à un degré de 600000
853
854 Figure \ref{fig:04} shows the execution time of the algorithm on single GPU and on multipe GPUs with (2, 3, 4) GPUs for full polynomials. With the CUDA-MPI approach, we notice that the three curves are distinct from each other, more we use GPUs more the execution time decreases. On the other hand the curve with a single GPU is well above the other curves.
855
856 This is due to the use of MPI parallel paradigm that divides the problem computations and assigns portions to each GPU. But unlike the single GPU which carries all the computations on a single GPU, data communications are introduced, consequently engendering more execution time. But experiments show that execution time is still highly reduced.
857
858
859
860
861 %\begin{figure}[htbp]
862 %\centering
863  % \includegraphics[angle=-90,width=0.5\textwidth]{Sparse}
864 %\caption{Comparaison between MPI and OpenMP versions of the Ehrlich-Aberth method for solving sparse plynomials on GPUs}
865 %\label{fig:05}
866 %\end{figure}
867
868 %\begin{figure}[htbp]
869 %\centering
870  % \includegraphics[angle=-90,width=0.5\textwidth]{Full}
871 %\caption{Comparaison between MPI and OpenMP versions of the Ehrlich-Aberth method for solving full polynomials on GPUs}
872 %\label{fig:06}
873 %\end{figure}
874
875 %\begin{figure}[htbp]
876 %\centering
877  % \includegraphics[angle=-90,width=0.5\textwidth]{MPI}
878 %\caption{Comparaison of execution times of the Ehrlich-Aberth method for solving sparse and full polynomials on GPUs with distributed memory paradigm using MPI}
879 %\label{fig:07}
880 %\end{figure}
881
882 %\begin{figure}[htbp]
883 %\centering
884  % \includegraphics[angle=-90,width=0.5\textwidth]{OMP}
885 %\caption{Comparaison of execution times of the Ehrlich-Aberth method for solving sparse and full polynomials on GPUs with shared memory paradigm using OpenMP}
886 %\label{fig:08}
887 %\end{figure}
888
889 % An example of a floating figure using the graphicx package.
890 % Note that \label must occur AFTER (or within) \caption.
891 % For figures, \caption should occur after the \includegraphics.
892 % Note that IEEEtran v1.7 and later has special internal code that
893 % is designed to preserve the operation of \label within \caption
894 % even when the captionsoff option is in effect. However, because
895 % of issues like this, it may be the safest practice to put all your
896 % \label just after \caption rather than within \caption{}.
897 %
898 % Reminder: the "draftcls" or "draftclsnofoot", not "draft", class
899 % option should be used if it is desired that the figures are to be
900 % displayed while in draft mode.
901 %
902 %\begin{figure}[!t]
903 %\centering
904 %\includegraphics[width=2.5in]{myfigure}
905 % where an .eps filename suffix will be assumed under latex, 
906 % and a .pdf suffix will be assumed for pdflatex; or what has been declared
907 % via \DeclareGraphicsExtensions.
908 %\caption{Simulation results for the network.}
909 %\label{fig_sim}
910 %\end{figure}
911
912 % Note that the IEEE typically puts floats only at the top, even when this
913 % results in a large percentage of a column being occupied by floats.
914
915
916 % An example of a double column floating figure using two subfigures.
917 % (The subfig.sty package must be loaded for this to work.)
918 % The subfigure \label commands are set within each subfloat command,
919 % and the \label for the overall figure must come after \caption.
920 % \hfil is used as a separator to get equal spacing.
921 % Watch out that the combined width of all the subfigures on a 
922 % line do not exceed the text width or a line break will occur.
923 %
924 %\begin{figure*}[!t]
925 %\centering
926 %\subfloat[Case I]{\includegraphics[width=2.5in]{box}%
927 %\label{fig_first_case}}
928 %\hfil
929 %\subfloat[Case II]{\includegraphics[width=2.5in]{box}%
930 %\label{fig_second_case}}
931 %\caption{Simulation results for the network.}
932 %\label{fig_sim}
933 %\end{figure*}
934 %
935 % Note that often IEEE papers with subfigures do not employ subfigure
936 % captions (using the optional argument to \subfloat[]), but instead will
937 % reference/describe all of them (a), (b), etc., within the main caption.
938 % Be aware that for subfig.sty to generate the (a), (b), etc., subfigure
939 % labels, the optional argument to \subfloat must be present. If a
940 % subcaption is not desired, just leave its contents blank,
941 % e.g., \subfloat[].
942
943
944 % An example of a floating table. Note that, for IEEE style tables, the
945 % \caption command should come BEFORE the table and, given that table
946 % captions serve much like titles, are usually capitalized except for words
947 % such as a, an, and, as, at, but, by, for, in, nor, of, on, or, the, to
948 % and up, which are usually not capitalized unless they are the first or
949 % last word of the caption. Table text will default to \footnotesize as
950 % the IEEE normally uses this smaller font for tables.
951 % The \label must come after \caption as always.
952 %
953 %\begin{table}[!t]
954 %% increase table row spacing, adjust to taste
955 %\renewcommand{\arraystretch}{1.3}
956 % if using array.sty, it might be a good idea to tweak the value of
957 % \extrarowheight as needed to properly center the text within the cells
958 %\caption{An Example of a Table}
959 %\label{table_example}
960 %\centering
961 %% Some packages, such as MDW tools, offer better commands for making tables
962 %% than the plain LaTeX2e tabular which is used here.
963 %\begin{tabular}{|c||c|}
964 %\hline
965 %One & Two\\
966 %\hline
967 %Three & Four\\
968 %\hline
969 %\end{tabular}
970 %\end{table}
971
972
973 % Note that the IEEE does not put floats in the very first column
974 % - or typically anywhere on the first page for that matter. Also,
975 % in-text middle ("here") positioning is typically not used, but it
976 % is allowed and encouraged for Computer Society conferences (but
977 % not Computer Society journals). Most IEEE journals/conferences use
978 % top floats exclusively. 
979 % Note that, LaTeX2e, unlike IEEE journals/conferences, places
980 % footnotes above bottom floats. This can be corrected via the
981 % \fnbelowfloat command of the stfloats package.
982
983
984
985
986 \section{Conclusion}
987 \label{sec5}
988 In this paper, we have presented a parallel implementation of Ehrlich-Aberth algorithm for solving full and sparse polynomials, on single GPU with CUDA and on multiple GPUs using two parallel paradigms : shared memory with OpenMP and distributed memory with MPI. These architectures were addressed by a CUDA-OpenMP approach and CUDA-MPI approach, respectively. 
989 The experiments show that, using parallel programming model like (OpenMP, MPI), we can efficiently manage multiple graphics cards to work together to solve the same problem and accelerate the parallel execution with 4 GPUs and solve a polynomial of degree 1,000,000, four times faster than on single GPU, that is a quasi-linear speedup.
990
991
992 %In future, we will evaluate our parallel implementation of Ehrlich-Aberth algorithm on other parallel programming model 
993
994 Our next objective is to extend the model presented here at clusters of nodes featuring  multiple GPUs, with a three-level scheme: inter-node communication via MPI processes (distributed memory), management of multi-GPU node by OpenMP threads (shared memory).
995
996 %present a communication approach between multiple GPUs. The comparison between MPI and OpenMP as GPUs controllers shows that these
997 %solutions can effectively manage multiple graphics cards to work together
998 %to solve the same problem
999
1000
1001  %than we have presented two communication approach between multiple GPUs.(CUDA-OpenMP) approach and (CUDA-MPI) approach, in the objective to manage multiple graphics cards to work together and solve the same problem. in the objective to manage multiple graphics cards to work together and solve the same problem. 
1002
1003
1004
1005
1006 % conference papers do not normally have an appendix
1007
1008
1009 % use section* for acknowledgment
1010 \section*{Acknowledgment}
1011
1012
1013 The authors would like to thank...
1014
1015
1016
1017
1018
1019 % trigger a \newpage just before the given reference
1020 % number - used to balance the columns on the last page
1021 % adjust value as needed - may need to be readjusted if
1022 % the document is modified later
1023 %\IEEEtriggeratref{8}
1024 % The "triggered" command can be changed if desired:
1025 %\IEEEtriggercmd{\enlargethispage{-5in}}
1026
1027 % references section
1028
1029 % can use a bibliography generated by BibTeX as a .bbl file
1030 % BibTeX documentation can be easily obtained at:
1031 % http://mirror.ctan.org/biblio/bibtex/contrib/doc/
1032 % The IEEEtran BibTeX style support page is at:
1033 % http://www.michaelshell.org/tex/ieeetran/bibtex/
1034 %\bibliographystyle{IEEEtran}
1035 % argument is your BibTeX string definitions and bibliography database(s)
1036 %\bibliography{IEEEabrv,../bib/paper}
1037 %\bibliographystyle{./IEEEtran}
1038 \bibliography{mybibfile}
1039
1040 %
1041 % <OR> manually copy in the resultant .bbl file
1042 % set second argument of \begin to the number of references
1043 % (used to reserve space for the reference number labels box)
1044 %\begin{thebibliography}{1}
1045
1046 %\bibitem{IEEEhowto:kopka}
1047 %H.~Kopka and P.~W. Daly, \emph{A Guide to \LaTeX}, 3rd~ed.\hskip 1em plus
1048  % 0.5em minus 0.4em\relax Harlow, England: Addison-Wesley, 1999.
1049   
1050 %\bibitem{IEEEhowto:NVIDIA12} 
1051  %NVIDIA Corporation, \textit{Whitepaper NVIDA’s Next Generation CUDATM Compute
1052 %Architecture: KeplerTM }, 1st ed., 2012.
1053
1054 %\end{thebibliography}
1055
1056
1057
1058
1059 % that's all folks
1060 \end{document}
1061
1062