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

Private GIT Repository
ajout de quelques commentaires
[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 et non pas $n$!}
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 \LZK{C'est $a_n\neq 0$ (polynôme de degré $n$) et non pas $a_0 a_n\neq 0$, non?}
437 \LZK{Est-ce $\alpha_i$ sont les $z_i$ définis dans la suite du papier?}
438
439 The problem of finding the roots of polynomials can be encountered in numerous applications. \LZK{A mon avis on peut supprimer cette phrase}
440 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:
441 \begin{equation}
442 \label{DK}
443  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,
444 \end{equation}
445 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:
446 %%\begin{center}
447 \begin{equation}
448 \label{Eq:EA}
449  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,
450 \end{equation}
451 %%\end{center}
452 where $p'(z)$ is the polynomial derivative of $p$ evaluated in the point $z$.
453
454 %Aberth, Ehrlich and Farmer-Loizou~\cite{Loizou83} have proved that
455 %the Ehrlich-Aberth method (EA) has a cubic order of convergence for simple roots whereas the Durand-Kerner has a quadratic order of %convergence.
456
457 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.
458
459 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.
460
461 %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.
462
463 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.
464 \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.)?}
465
466 \LZK{Les contributions ne sont pas définies !!}
467  
468 %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.}
469
470 The paper is organized as follows. In Section~\ref{sec2} we present three different parallel programming models OpenMP, MPI and CUDA.
471 \LZK{A revoir toute cette organization}
472
473 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
474 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
475  
476 \section{Parallel programming models}
477 \label{sec2}
478 In this section we present three different parallel programming models: OpenMP, MPI and CUDA.
479  
480 \subsection{OpenMP}
481 %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.
482
483 %\subsection{OpenMP} 
484 %OpenMP is a shared memory programming API based on threads from
485 %the same system process. Designed for multiprocessor shared memory UMA or
486 %NUMA [10], it relies on the execution model SPMD ( Single Program, Multiple Data Stream )
487 %where the thread "master" and threads "slaves" asynchronously execute their codes
488 %communicate / synchronize via shared memory [7]. It also helps to build
489 %the loop parallelism and is very suitable for an incremental code parallelization
490 %Sequential natively. Threads share some or all of the available memory and can
491 %have private memory areas [6].
492
493 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.
494 \LZK{Cette partie est réécrite. A relire et à améliorer si possible.}  
495
496 \subsection{MPI} 
497 %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.
498
499 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.
500 \LZK{Cette partie est réécrite. A relire et à améliorer si possible.}
501  
502 \subsection{CUDA}
503 CUDA (an acronym for Compute Unified Device Architecture) is a parallel computing architecture developed by NVIDIA~\cite{CUDA10}. The
504 unit of execution in CUDA is called a thread. Each thread executes a kernel by the streaming processors in parallel. In CUDA,
505 a group of threads that are executed together is called a thread block, and the computational grid consists of a grid of thread
506 blocks. Additionally, a thread block can use the shared memory on a single multiprocessor while the grid executes a single
507 CUDA program logically in parallel. Thus in CUDA programming, it is necessary to design carefully the arrangement of the thread
508 blocks in order to ensure low latency and a proper usage of shared memory, since it can be shared only in a thread block
509 scope. The effective bandwidth of each memory space depends on the memory access pattern. Since the global memory has lower
510 bandwidth than the shared memory, the global memory accesses should be minimized.
511
512
513 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.
514
515 \section{The EA algorithm on a single GPU}
516 \label{sec3}
517 \subsection{The EA method}
518
519 A cubically convergent iteration method to find zeros of
520 polynomials was proposed by O. Aberth~\cite{Aberth73}. The
521 Ehrlich-Aberth (EA is short) method contains 4 main steps, presented in what
522 follows.
523
524 %The Aberth method is a purely algebraic derivation. 
525 %To illustrate the derivation, we let $w_{i}(z)$ be the product of linear factors 
526
527 %\begin{equation}
528 %w_{i}(z)=\prod_{j=1,j \neq i}^{n} (z-x_{j})
529 %\end{equation}
530
531 %And let a rational function $R_{i}(z)$ be the correction term of the
532 %Weistrass method~\cite{Weierstrass03}
533
534 %\begin{equation}
535 %R_{i}(z)=\frac{p(z)}{w_{i}(z)} , i=1,2,...,n.
536 %\end{equation}
537
538 %Differentiating the rational function $R_{i}(z)$ and applying the
539 %Newton method, we have:
540
541 %\begin{equation}
542 %\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
543 %\end{equation}
544 %where R_{i}^{'}(z)is the rational function derivative of F evaluated in the point z 
545 %Substituting $x_{j}$ for $z_{j}$ we obtain the Aberth iteration method.% 
546
547
548 \subsubsection{Polynomials Initialization}
549 The initialization of a polynomial $p(z)$ is done by setting each of the $n$ complex coefficients $a_{i}$:
550
551 \begin{equation}
552 \label{eq:SimplePolynome}
553   p(z)=\sum{a_{i}z^{n-i}} , a_{n} \neq 0,a_{0}=1, a_{i}\subset C
554 \end{equation}
555
556
557 \subsubsection{Vector $Z^{(0)}$ Initialization}
558 \label{sec:vec_initialization}
559 As for any iterative method, we need to choose $n$ initial guess points $z^{0}_{i}, i = 1, . . . , n.$
560 The initial guess is very important since the number of steps needed by the iterative method to reach
561 a given approximation strongly depends on it.
562 In~\cite{Aberth73} the Ehrlich-Aberth iteration is started by selecting $n$
563 equi-distant points on a circle of center 0 and radius r, where r is
564 an upper bound to the moduli of the zeros. Later, Bini and al.~\cite{Bini96}
565 performed this choice by selecting complex numbers along different
566 circles which relies on the result of~\cite{Ostrowski41}.
567
568 \begin{equation}
569 \label{eq:radiusR}
570 %%\begin{align}
571 \sigma_{0}=\frac{u+v}{2};u=\frac{\sum_{i=1}^{n}u_{i}}{n.max_{i=1}^{n}u_{i}};
572 v=\frac{\sum_{i=0}^{n-1}v_{i}}{n.min_{i=0}^{n-1}v_{i}};\\
573 %%\end{align}
574 \end{equation}
575 Where:
576 \begin{equation}
577 u_{i}=2.|a_{i}|^{\frac{1}{i}};
578 v_{i}=\frac{|\frac{a_{n}}{a_{i}}|^{\frac{1}{n-i}}}{2}.
579 \end{equation}
580
581 \subsubsection{Iterative Function}
582 The operator used by the Aberth method  corresponds to the
583 equation~\ref{Eq:EA1}, it enables the convergence towards
584 the polynomials zeros, provided all the roots are distinct.
585
586 %Here we give a second form of the iterative function used by the Ehrlich-Aberth method: 
587
588 \begin{equation}
589 \label{Eq:EA1}
590 EA: z^{k+1}_{i}=z_{i}^{k}-\frac{\frac{p(z_{i}^{k})}{p'(z_{i}^{k})}}
591 {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
592 \end{equation}
593
594 \subsubsection{Convergence Condition}
595 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:
596
597 \begin{equation}
598 \label{eq:Aberth-Conv-Cond}
599 \forall i \in [1,n];\vert\frac{z_{i}^{k}-z_{i}^{k-1}}{z_{i}^{k}}\vert<\xi
600 \end{equation}
601
602
603 %\begin{figure}[htbp]
604 %\centering
605  % \includegraphics[angle=-90,width=0.5\textwidth]{EA-Algorithm}
606 %\caption{The Ehrlich-Aberth algorithm on single GPU}
607 %\label{fig:03}
608 %\end{figure}
609
610 %the Ehrlich-Aberth method is an iterative  method, contain 4 steps, start from the initial approximations of all the
611 %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
612 %are lower than a fixed value $ε$ 
613
614
615 \subsection{EA parallel implementation on CUDA}
616 Like any parallel code, a GPU parallel implementation first
617 requires to determine the sequential tasks and the
618 parallelizable parts of the sequential version of the
619 program/algorithm. In our case, all the operations that are easy
620 to execute in parallel must be made by the GPU to accelerate
621 the execution of the application, like the step 3 and step 4. On the other hand, all the
622 sequential operations and the operations that have data
623 dependencies between threads or recursive computations must
624 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. 
625
626 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
627 first named \textit{save} is used to save vector $Z^{K-1}$ and the seconde one is named
628 \textit{update} and is used to update the $Z^{K}$ vector. For step 4, a kernel 
629 tests the convergence of the method. In order to
630 compute the function H, we have two possibilities: either to use
631 the Jacobi mode, or the Gauss-Seidel mode of iterating which uses the
632 most recent computed roots. It is well known that the Gauss-
633 Seidel mode converges more quickly. So, we used the Gauss-Seidel mode of iteration. To
634 parallelize the code, we created kernels and many functions to
635 be executed on the GPU for all the operations dealing with the
636 computation on complex numbers and the evaluation of the
637 polynomials. As said previously, we managed both functions
638 of evaluation of a polynomial: the normal method, based on
639 the method of Horner and the method based on the logarithm
640 of the polynomial. All these methods were rather long to
641 implement, as the development of corresponding kernels with
642 CUDA is longer than on a CPU host. This comes in particular
643 from the fact that it is very difficult to debug CUDA running
644 threads like threads on a CPU host. In the following paragraph
645 Algorithm~\ref{alg1-cuda} shows the GPU parallel implementation of Ehrlich-Aberth method.
646
647 \begin{enumerate}
648 \begin{algorithm}[htpb]
649 \label{alg1-cuda}
650 %\LinesNumbered
651 \caption{CUDA Algorithm to find roots with the Ehrlich-Aberth method}
652
653 \KwIn{$Z^{0}$ (Initial root's vector), $\varepsilon$ (Error tolerance
654   threshold), P (Polynomial to solve), Pu (Derivative of P), $n$ (Polynomial degrees), $\Delta z_{max}$ (Maximum value of stop condition)}
655
656 \KwOut {$Z$ (Solution root's vector), $ZPrec$ (Previous solution root's vector)}
657
658 %\BlankLine
659
660 \item Initialization of the of P\;
661 \item Initialization of the of Pu\;
662 \item Initialization of the solution vector $Z^{0}$\;
663 \item Allocate and copy initial data to the GPU global memory\;
664 \item k=0\;
665 \While {$\Delta z_{max} > \epsilon$}{
666 \item Let $\Delta z_{max}=0$\;
667 \item $ kernel\_save(ZPrec,Z)$\;
668 \item  k=k+1\;
669 \item $ kernel\_update(Z,P,Pu)$\;
670 \item $kernel\_testConverge(\Delta z_{max},Z,ZPrec)$\;
671
672 }
673 \item Copy results from GPU memory to CPU memory\;
674 \end{algorithm}
675 \end{enumerate}
676 ~\\ 
677
678
679  
680 \section{The EA algorithm on Multi-GPU}
681 \label{sec4}
682 \subsection{MGPU : an OpenMP-CUDA approach}
683 Our OpenMP-CUDA implementation of EA algorithm is based on the hybrid OpenMP and CUDA programming model. It works as follows.
684 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).
685
686 %\begin{figure}[htbp]
687 %\centering
688  % \includegraphics[angle=-90,width=0.5\textwidth]{OpenMP-CUDA}
689 %\caption{The OpenMP-CUDA architecture}
690 %\label{fig:03}
691 %\end{figure}
692 %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:
693
694 $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.  
695 \begin{enumerate}
696 \begin{algorithm}[htpb]
697 \label{alg2-cuda-openmp}
698 %\LinesNumbered
699 \caption{CUDA-OpenMP Algorithm to find roots with the Ehrlich-Aberth method}
700
701 \KwIn{$Z^{0}$ (Initial root's vector), $\varepsilon$ (Error tolerance
702   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)}
703
704 \KwOut {$Z$ ( Root's vector), $ZPrec$ (Previous root's vector)}
705
706 \BlankLine
707
708 \item Initialization of P\;
709 \item Initialization of Pu\;
710 \item Initialization of the solution vector $Z^{0}$\;
711 \verb=omp_set_num_threads(num_gpus);=
712 \verb=#pragma omp parallel shared(Z,$\Delta$ z,P);=
713 \verb=cudaGetDevice(gpu_id);=
714 \item Allocate and copy initial data from CPU memory to the GPU global memories\;
715 \item index= $Size/num\_gpus$\;
716 \item k=0\;
717 \While {$error > \epsilon$}{
718 \item Let $\Delta z=0$\;
719 \item $ kernel\_save(ZPrec,Z)$\;
720 \item  k=k+1\;
721 \item $ kernel\_update(Z,P,Pu,index)$\;
722 \item $kernel\_testConverge(\Delta z[gpu\_id],Z,ZPrec)$\;
723 %\verb=#pragma omp barrier;=
724 \item error= Max($\Delta z$)\;
725 }
726
727 \item Copy results from GPU memories to CPU memory\;
728 \end{algorithm}
729 \end{enumerate}
730 ~\\ 
731
732
733
734 \subsection{Multi-GPU : an MPI-CUDA approach}
735 %\begin{figure}[htbp]
736 %\centering
737  % \includegraphics[angle=-90,width=0.2\textwidth]{MPI-CUDA}
738 %\caption{The MPI-CUDA architecture }
739 %\label{fig:03}
740 %\end{figure}
741 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.
742
743 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.
744
745 \begin{enumerate}
746 \begin{algorithm}[htpb]
747 \label{alg2-cuda-mpi}
748 %\LinesNumbered
749 \caption{CUDA-MPI Algorithm to find roots with the Ehrlich-Aberth method}
750
751 \KwIn{$Z^{0}$ (Initial root's vector), $\varepsilon$ (Error tolerance
752   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)}
753
754 \KwOut {$Z$ (Solution root's vector), $ZPrec$ (Previous solution root's vector)}
755
756 \BlankLine
757 \item Initialization of P\;
758 \item Initialization of Pu\;
759 \item Initialization of the solution vector $Z^{0}$\;
760 \item Allocate and copy initial data from CPU memories to GPU global memories\;
761 \item $index= Size/num_gpus$\;
762 \item k=0\;
763 \While {$error > \epsilon$}{
764 \item Let $\Delta z=0$\;
765 \item $kernel\_save(ZPrec,Z)$\;
766 \item  k=k+1\;
767 \item $kernel\_update(Z,P,Pu,index)$\;
768 \item $kernel\_testConverge(\Delta z,Z,ZPrec)$\;
769 \item ComputeMaxError($\Delta z$,error)\;
770 \item Copy results from GPU memories to CPU memories\;
771 \item Send $Z[id]$ to all processes\;
772 \item Receive $Z[j]$ from every other process j\;
773 }
774 \end{algorithm}
775 \end{enumerate}
776 ~\\ 
777
778 \section{Experiments}
779 \label{sec5}
780 We study two categories of polynomials: sparse polynomials and full polynomials.\\
781 {\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:
782 \begin{equation}
783         \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})
784 \end{equation}\noindent
785 {\it A full polynomial} is, in contrast, a polynomial for which all the coefficients are not null. A full polynomial is defined by:
786 %%\begin{equation}
787         %%\forall \alpha_{i} \in C,\forall n_{i}\in N^{*}; P(z)= \sum^{n}_{i=1}(z^{n^{i}}.a_{i})
788 %%\end{equation}
789
790 \begin{equation}
791      {\Large \forall a_{i} \in C, i\in N;  p(x)=\sum^{n}_{i=0} a_{i}.x^{i}} 
792 \end{equation}
793 For our tests, a CPU Intel(R) Xeon(R) CPU E5620@2.40GHz and a GPU K40 (with 6 Go of ram) are used. 
794 %SIDER : Une meilleure présentation de l'architecture est à faire ici.
795
796 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.
797 All experimental results obtained are made in double precision data, the convergence threshold of the methods is set to $10^{-7}$.
798 %Since we were more interested in the comparison of the
799 %performance behaviors of Ehrlich-Aberth and Durand-Kerner methods on
800 %CPUs versus on GPUs.
801 The initialization values of the vector solution
802 of the methods are given in %Section~\ref{sec:vec_initialization}.
803
804 \subsection{Evaluating the M-GPU (CUDA-OpenMP) approach}
805
806 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.
807 \subsubsection{Execution times in seconds of the EA method for solving sparse polynomials on GPUs using shared memory paradigm with OpenMP}
808  
809 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.
810
811 \begin{figure}[htbp]
812 \centering
813   \includegraphics[angle=-90,width=0.5\textwidth]{Sparse_omp}
814 \caption{Execution times in seconds of the Ehrlich-Aberth method for solving sparse polynomials on GPUs using shared memory paradigm with OpenMP}
815 \label{fig:01}
816 \end{figure}
817
818 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.   
819
820 \subsubsection{Execution times in seconds of the Ehrlich-Aberth method for solving full polynomials on GPUs using shared memory paradigm with OpenMP}
821
822 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.
823
824 \begin{figure}[htbp]
825 \centering
826   \includegraphics[angle=-90,width=0.5\textwidth]{Full_omp}
827 \caption{Execution times in seconds of the Ehrlich-Aberth method for solving full polynomials on multiple GPUs using shared memory paradigm with OpenMP}
828 \label{fig:03}
829 \end{figure}
830
831 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.
832
833 \subsection{Evaluting the Multi-GPU (CUDA-MPI) approach}
834 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.
835
836 \subsubsection{Execution times in seconds of the Ehrlich-Aberth method for solving sparse polynomials on GPUs using distributed memory paradigm with MPI}
837
838 \begin{figure}[htbp]
839 \centering
840   \includegraphics[angle=-90,width=0.5\textwidth]{Sparse_mpi}
841 \caption{Execution times in seconds of the Ehrlich-Aberth method for solving sparse polynomials on GPUs using distributed memory paradigm with MPI}
842 \label{fig:02}
843 \end{figure}
844 ~\\
845 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.
846 %%SIDER : Je n'ai pas reformuler car je n'ai pas compris la phrase, merci de l'ecrire ici en fran\cais.
847 \\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.
848 \subsubsection{Execution times in seconds of the Ehrlich-Aberth method for solving full polynomials on GPUs using distributed memory paradigm with MPI}
849
850 \begin{figure}[htbp]
851 \centering
852   \includegraphics[angle=-90,width=0.5\textwidth]{Full_mpi}
853 \caption{Execution times in seconds of the Ehrlich-Aberth method for full polynomials on GPUs using distributed memory paradigm with MPI}
854 \label{fig:04}
855 \end{figure}
856 %SIDER : Corriger le point de la courbe 3-GPUs qui correpsond à un degré de 600000
857
858 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.
859
860 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.
861
862
863
864
865 %\begin{figure}[htbp]
866 %\centering
867  % \includegraphics[angle=-90,width=0.5\textwidth]{Sparse}
868 %\caption{Comparaison between MPI and OpenMP versions of the Ehrlich-Aberth method for solving sparse plynomials on GPUs}
869 %\label{fig:05}
870 %\end{figure}
871
872 %\begin{figure}[htbp]
873 %\centering
874  % \includegraphics[angle=-90,width=0.5\textwidth]{Full}
875 %\caption{Comparaison between MPI and OpenMP versions of the Ehrlich-Aberth method for solving full polynomials on GPUs}
876 %\label{fig:06}
877 %\end{figure}
878
879 %\begin{figure}[htbp]
880 %\centering
881  % \includegraphics[angle=-90,width=0.5\textwidth]{MPI}
882 %\caption{Comparaison of execution times of the Ehrlich-Aberth method for solving sparse and full polynomials on GPUs with distributed memory paradigm using MPI}
883 %\label{fig:07}
884 %\end{figure}
885
886 %\begin{figure}[htbp]
887 %\centering
888  % \includegraphics[angle=-90,width=0.5\textwidth]{OMP}
889 %\caption{Comparaison of execution times of the Ehrlich-Aberth method for solving sparse and full polynomials on GPUs with shared memory paradigm using OpenMP}
890 %\label{fig:08}
891 %\end{figure}
892
893 % An example of a floating figure using the graphicx package.
894 % Note that \label must occur AFTER (or within) \caption.
895 % For figures, \caption should occur after the \includegraphics.
896 % Note that IEEEtran v1.7 and later has special internal code that
897 % is designed to preserve the operation of \label within \caption
898 % even when the captionsoff option is in effect. However, because
899 % of issues like this, it may be the safest practice to put all your
900 % \label just after \caption rather than within \caption{}.
901 %
902 % Reminder: the "draftcls" or "draftclsnofoot", not "draft", class
903 % option should be used if it is desired that the figures are to be
904 % displayed while in draft mode.
905 %
906 %\begin{figure}[!t]
907 %\centering
908 %\includegraphics[width=2.5in]{myfigure}
909 % where an .eps filename suffix will be assumed under latex, 
910 % and a .pdf suffix will be assumed for pdflatex; or what has been declared
911 % via \DeclareGraphicsExtensions.
912 %\caption{Simulation results for the network.}
913 %\label{fig_sim}
914 %\end{figure}
915
916 % Note that the IEEE typically puts floats only at the top, even when this
917 % results in a large percentage of a column being occupied by floats.
918
919
920 % An example of a double column floating figure using two subfigures.
921 % (The subfig.sty package must be loaded for this to work.)
922 % The subfigure \label commands are set within each subfloat command,
923 % and the \label for the overall figure must come after \caption.
924 % \hfil is used as a separator to get equal spacing.
925 % Watch out that the combined width of all the subfigures on a 
926 % line do not exceed the text width or a line break will occur.
927 %
928 %\begin{figure*}[!t]
929 %\centering
930 %\subfloat[Case I]{\includegraphics[width=2.5in]{box}%
931 %\label{fig_first_case}}
932 %\hfil
933 %\subfloat[Case II]{\includegraphics[width=2.5in]{box}%
934 %\label{fig_second_case}}
935 %\caption{Simulation results for the network.}
936 %\label{fig_sim}
937 %\end{figure*}
938 %
939 % Note that often IEEE papers with subfigures do not employ subfigure
940 % captions (using the optional argument to \subfloat[]), but instead will
941 % reference/describe all of them (a), (b), etc., within the main caption.
942 % Be aware that for subfig.sty to generate the (a), (b), etc., subfigure
943 % labels, the optional argument to \subfloat must be present. If a
944 % subcaption is not desired, just leave its contents blank,
945 % e.g., \subfloat[].
946
947
948 % An example of a floating table. Note that, for IEEE style tables, the
949 % \caption command should come BEFORE the table and, given that table
950 % captions serve much like titles, are usually capitalized except for words
951 % such as a, an, and, as, at, but, by, for, in, nor, of, on, or, the, to
952 % and up, which are usually not capitalized unless they are the first or
953 % last word of the caption. Table text will default to \footnotesize as
954 % the IEEE normally uses this smaller font for tables.
955 % The \label must come after \caption as always.
956 %
957 %\begin{table}[!t]
958 %% increase table row spacing, adjust to taste
959 %\renewcommand{\arraystretch}{1.3}
960 % if using array.sty, it might be a good idea to tweak the value of
961 % \extrarowheight as needed to properly center the text within the cells
962 %\caption{An Example of a Table}
963 %\label{table_example}
964 %\centering
965 %% Some packages, such as MDW tools, offer better commands for making tables
966 %% than the plain LaTeX2e tabular which is used here.
967 %\begin{tabular}{|c||c|}
968 %\hline
969 %One & Two\\
970 %\hline
971 %Three & Four\\
972 %\hline
973 %\end{tabular}
974 %\end{table}
975
976
977 % Note that the IEEE does not put floats in the very first column
978 % - or typically anywhere on the first page for that matter. Also,
979 % in-text middle ("here") positioning is typically not used, but it
980 % is allowed and encouraged for Computer Society conferences (but
981 % not Computer Society journals). Most IEEE journals/conferences use
982 % top floats exclusively. 
983 % Note that, LaTeX2e, unlike IEEE journals/conferences, places
984 % footnotes above bottom floats. This can be corrected via the
985 % \fnbelowfloat command of the stfloats package.
986
987
988
989
990 \section{Conclusion}
991 \label{sec5}
992 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. 
993 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.
994
995
996 %In future, we will evaluate our parallel implementation of Ehrlich-Aberth algorithm on other parallel programming model 
997
998 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).
999
1000 %present a communication approach between multiple GPUs. The comparison between MPI and OpenMP as GPUs controllers shows that these
1001 %solutions can effectively manage multiple graphics cards to work together
1002 %to solve the same problem
1003
1004
1005  %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. 
1006
1007
1008
1009
1010 % conference papers do not normally have an appendix
1011
1012
1013 % use section* for acknowledgment
1014 \section*{Acknowledgment}
1015
1016
1017 The authors would like to thank...
1018
1019
1020
1021
1022
1023 % trigger a \newpage just before the given reference
1024 % number - used to balance the columns on the last page
1025 % adjust value as needed - may need to be readjusted if
1026 % the document is modified later
1027 %\IEEEtriggeratref{8}
1028 % The "triggered" command can be changed if desired:
1029 %\IEEEtriggercmd{\enlargethispage{-5in}}
1030
1031 % references section
1032
1033 % can use a bibliography generated by BibTeX as a .bbl file
1034 % BibTeX documentation can be easily obtained at:
1035 % http://mirror.ctan.org/biblio/bibtex/contrib/doc/
1036 % The IEEEtran BibTeX style support page is at:
1037 % http://www.michaelshell.org/tex/ieeetran/bibtex/
1038 %\bibliographystyle{IEEEtran}
1039 % argument is your BibTeX string definitions and bibliography database(s)
1040 %\bibliography{IEEEabrv,../bib/paper}
1041 %\bibliographystyle{./IEEEtran}
1042 \bibliography{mybibfile}
1043
1044 %
1045 % <OR> manually copy in the resultant .bbl file
1046 % set second argument of \begin to the number of references
1047 % (used to reserve space for the reference number labels box)
1048 %\begin{thebibliography}{1}
1049
1050 %\bibitem{IEEEhowto:kopka}
1051 %H.~Kopka and P.~W. Daly, \emph{A Guide to \LaTeX}, 3rd~ed.\hskip 1em plus
1052  % 0.5em minus 0.4em\relax Harlow, England: Addison-Wesley, 1999.
1053   
1054 %\bibitem{IEEEhowto:NVIDIA12} 
1055  %NVIDIA Corporation, \textit{Whitepaper NVIDA’s Next Generation CUDATM Compute
1056 %Architecture: KeplerTM }, 1st ed., 2012.
1057
1058 %\end{thebibliography}
1059
1060
1061
1062
1063 % that's all folks
1064 \end{document}
1065
1066