From: RCE Date: Tue, 17 Nov 2015 21:19:06 +0000 (+0100) Subject: RCE - 17/11/2015 - Juste la premiere version. X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/these_charles_emile.git/commitdiff_plain/a84d210b4e8cc45730579629651a610559792413 RCE - 17/11/2015 - Juste la premiere version. --- diff --git a/1D-2D-3D Domain decomposition.pdf b/1D-2D-3D Domain decomposition.pdf new file mode 100644 index 0000000..b044797 Binary files /dev/null and b/1D-2D-3D Domain decomposition.pdf differ diff --git a/3D data partitionning btw 2 clusters.pdf b/3D data partitionning btw 2 clusters.pdf new file mode 100644 index 0000000..e41073f Binary files /dev/null and b/3D data partitionning btw 2 clusters.pdf differ diff --git a/Architecture des CPU multi-coeurs.pdf b/Architecture des CPU multi-coeurs.pdf new file mode 100644 index 0000000..b4a1c71 Binary files /dev/null and b/Architecture des CPU multi-coeurs.pdf differ diff --git a/Asynchronous iterations model.pdf b/Asynchronous iterations model.pdf new file mode 100644 index 0000000..0a39684 Binary files /dev/null and b/Asynchronous iterations model.pdf differ diff --git a/COMA architecture.pdf b/COMA architecture.pdf new file mode 100644 index 0000000..82be475 Binary files /dev/null and b/COMA architecture.pdf differ diff --git a/Evolution de la puissance de calcul mondiale.pdf b/Evolution de la puissance de calcul mondiale.pdf new file mode 100644 index 0000000..bcc07df Binary files /dev/null and b/Evolution de la puissance de calcul mondiale.pdf differ diff --git a/MIMD Distributed Memory.pdf b/MIMD Distributed Memory.pdf new file mode 100644 index 0000000..be53196 Binary files /dev/null and b/MIMD Distributed Memory.pdf differ diff --git a/MIMD Hybride.pdf b/MIMD Hybride.pdf new file mode 100644 index 0000000..6e722c5 Binary files /dev/null and b/MIMD Hybride.pdf differ diff --git a/MIMD Shared memory - SMP.pdf b/MIMD Shared memory - SMP.pdf new file mode 100644 index 0000000..839bef4 Binary files /dev/null and b/MIMD Shared memory - SMP.pdf differ diff --git a/NUMA architecture.pdf b/NUMA architecture.pdf new file mode 100644 index 0000000..68d7e6d Binary files /dev/null and b/NUMA architecture.pdf differ diff --git a/Synchronous iterations model.pdf b/Synchronous iterations model.pdf new file mode 100644 index 0000000..304c482 Binary files /dev/null and b/Synchronous iterations model.pdf differ diff --git a/These_RCE.aux b/These_RCE.aux new file mode 100644 index 0000000..5450ad3 --- /dev/null +++ b/These_RCE.aux @@ -0,0 +1,70 @@ +\relax +\catcode `:\active +\catcode `;\active +\catcode `!\active +\catcode `?\active +\select@language{french} +\@writefile{toc}{\select@language{french}} +\@writefile{lof}{\select@language{french}} +\@writefile{lot}{\select@language{french}} +\select@language{french} +\@writefile{toc}{\select@language{french}} +\@writefile{lof}{\select@language{french}} +\@writefile{lot}{\select@language{french}} +\newlabel{eq:1}{{1}{6}} +\@writefile{toc}{\contentsline {subsection}{\numberline {0.0.1}Partitionnement du probl\`eme}{7}} +\providecommand*\caption@xref[2]{\@setref\relax\@undefined{#1}} +\newlabel{fig:1.a}{{1a}{7}} +\newlabel{sub@fig:1.a}{{a}{7}} +\newlabel{fig:1.b}{{1b}{7}} +\newlabel{sub@fig:1.b}{{b}{7}} +\@writefile{lof}{\contentsline {figure}{\numberline {1}{\ignorespaces Partitionnement du probl\`eme\relax }}{7}} +\@writefile{toc}{\contentsline {subsection}{\numberline {0.0.2}Modes d'ex\'ecution synchrone et asynchrone}{8}} +\newlabel{fig:2.a}{{2a}{8}} +\newlabel{sub@fig:2.a}{{a}{8}} +\newlabel{fig:2.b}{{2b}{8}} +\newlabel{sub@fig:2.b}{{b}{8}} +\@writefile{lof}{\contentsline {figure}{\numberline {2}{\ignorespaces Mod\`eles de communication\relax }}{8}} +\@writefile{toc}{\contentsline {subsection}{\numberline {0.0.3}Algorithme de Jacobi}{9}} +\@writefile{toc}{\contentsline {subsection}{\numberline {0.0.4}M\'ethode de r\'esolution GMRES}{9}} +\@writefile{toc}{\contentsline {subsection}{\numberline {0.0.5}Solveur multisplitting}{9}} +\@writefile{toc}{\contentsline {subsection}{\numberline {0.0.6}MPI - Message Passing Interface}{10}} +\@writefile{toc}{\contentsline {subsection}{\numberline {0.0.7}Simulateur SIMGRID}{10}} +\@writefile{toc}{\contentsline {subsection}{\numberline {0.0.8}Performance de l'application parall\`ele et scalabilit\'e}{11}} +\newlabel{eq:5}{{5}{11}} +\newlabel{eq:6}{{6}{12}} +\newlabel{eq:7}{{7}{12}} +\newlabel{eq:8}{{8}{12}} +\newlabel{eq:9}{{9}{13}} +\@writefile{toc}{\contentsline {subsection}{\numberline {0.0.9}Taux d'erreur lors de la pr\'ediction}{13}} +\@writefile{toc}{\contentsline {subsection}{\numberline {0.0.10}Weak contre strong scaling}{13}} +\@writefile{lof}{\contentsline {figure}{\numberline {3}{\ignorespaces Weak vs Strong scaling: Temps d'ex\'ecution et Speedup\relax }}{14}} +\newlabel{fig:3}{{3}{14}} +\@writefile{toc}{\contentsline {subsubsection}{\numberline {0.0.10.1}Facteur architecture des processeurs}{16}} +\@writefile{lof}{\contentsline {figure}{\numberline {4}{\ignorespaces Architecture des CPU multicoeurs\relax }}{17}} +\newlabel{fig:4}{{4}{17}} +\newlabel{fig:5.a}{{5a}{18}} +\newlabel{sub@fig:5.a}{{a}{18}} +\newlabel{fig:5.b}{{5b}{18}} +\newlabel{sub@fig:5.b}{{b}{18}} +\newlabel{fig:5.c}{{5c}{18}} +\newlabel{sub@fig:5.c}{{c}{18}} +\@writefile{lof}{\contentsline {figure}{\numberline {5}{\ignorespaces Mod\`eles de m\'emoire MIMD\relax }}{18}} +\@writefile{toc}{\contentsline {subsubsection}{\numberline {0.0.10.2}Facteur : M\'emoire et stockage}{18}} +\@writefile{lof}{\contentsline {figure}{\numberline {6}{\ignorespaces Evolution de la puissance de calcul mondiale\relax }}{19}} +\newlabel{fig:6}{{6}{19}} +\newlabel{fig:6.a}{{7a}{20}} +\newlabel{sub@fig:6.a}{{a}{20}} +\newlabel{fig:6.b}{{7b}{20}} +\newlabel{sub@fig:6.b}{{b}{20}} +\newlabel{fig:6.c}{{7c}{20}} +\newlabel{sub@fig:6.c}{{c}{20}} +\@writefile{lof}{\contentsline {figure}{\numberline {7}{\ignorespaces Mod\`eles de m\'emoire MIMD\relax }}{20}} +\@writefile{toc}{\contentsline {subsubsection}{\numberline {0.0.10.3}Facteur : R\'eseaux de communication}{21}} +\@writefile{toc}{\contentsline {subsection}{\numberline {0.0.11}Facteurs li\'es au code de l'application}{22}} +\@writefile{toc}{\contentsline {subsubsection}{\numberline {0.0.11.1}Facteur : Taille du probl\`eme}{22}} +\@writefile{toc}{\contentsline {subsubsection}{\numberline {0.0.11.2}Performance de la parall\'elisation}{22}} +\newlabel{eq:10}{{10}{22}} +\newlabel{eq:11}{{11}{22}} +\newlabel{eq:12}{{12}{23}} +\newlabel{eq:12}{{13}{23}} diff --git a/These_RCE.log b/These_RCE.log new file mode 100644 index 0000000..cfc77ad --- /dev/null +++ b/These_RCE.log @@ -0,0 +1,947 @@ +This is pdfTeX, Version 3.14159265-2.6-1.40.16 (MiKTeX 2.9) (preloaded format=pdflatex 2015.11.9) 17 NOV 2015 20:52 +entering extended mode +**These_RCE.tex +(These_RCE.tex +LaTeX2e <2015/01/01> patch level 2 +Babel <3.9m> and hyphenation patterns for 69 languages loaded. +("C:\Program Files (x86)\MiKTeX 2.9\tex\latex\base\report.cls" +Document Class: report 2014/09/29 v1.4h Standard LaTeX document class +("C:\Program Files (x86)\MiKTeX 2.9\tex\latex\base\size10.clo" +File: size10.clo 2014/09/29 v1.4h Standard LaTeX file (size option) +) +\c@part=\count79 +\c@chapter=\count80 +\c@section=\count81 +\c@subsection=\count82 +\c@subsubsection=\count83 +\c@paragraph=\count84 +\c@subparagraph=\count85 +\c@figure=\count86 +\c@table=\count87 +\abovecaptionskip=\skip41 +\belowcaptionskip=\skip42 +\bibindent=\dimen102 +) +("C:\Program Files (x86)\MiKTeX 2.9\tex\latex\psnfss\times.sty" +Package: times 2005/04/12 PSNFSS-v9.2a (SPQR) +) +("C:\Program Files (x86)\MiKTeX 2.9\tex\latex\setspace\setspace.sty" +Package: setspace 2011/12/19 v6.7a set line spacing +) +("C:\Program Files (x86)\MiKTeX 2.9\tex\latex\geometry\geometry.sty" +Package: geometry 2010/09/12 v5.6 Page Geometry + +("C:\Program Files (x86)\MiKTeX 2.9\tex\latex\graphics\keyval.sty" +Package: keyval 2014/10/28 v1.15 key=value parser (DPC) +\KV@toks@=\toks14 +) +("C:\Program Files (x86)\MiKTeX 2.9\tex\generic\oberdiek\ifpdf.sty" +Package: ifpdf 2011/01/30 v2.3 Provides the ifpdf switch (HO) +Package ifpdf Info: pdfTeX in PDF mode is detected. +) +("C:\Program Files (x86)\MiKTeX 2.9\tex\generic\oberdiek\ifvtex.sty" +Package: ifvtex 2010/03/01 v1.5 Detect VTeX and its facilities (HO) +Package ifvtex Info: VTeX not detected. +) +("C:\Program Files (x86)\MiKTeX 2.9\tex\generic\ifxetex\ifxetex.sty" +Package: ifxetex 2010/09/12 v0.6 Provides ifxetex conditional +) +\Gm@cnth=\count88 +\Gm@cntv=\count89 +\c@Gm@tempcnt=\count90 +\Gm@bindingoffset=\dimen103 +\Gm@wd@mp=\dimen104 +\Gm@odd@mp=\dimen105 +\Gm@even@mp=\dimen106 +\Gm@layoutwidth=\dimen107 +\Gm@layoutheight=\dimen108 +\Gm@layouthoffset=\dimen109 +\Gm@layoutvoffset=\dimen110 +\Gm@dimlist=\toks15 + +("C:\Program Files (x86)\MiKTeX 2.9\tex\latex\geometry\geometry.cfg")) +("C:\Program Files (x86)\MiKTeX 2.9\tex\latex\base\fontenc.sty" +Package: fontenc 2005/09/27 v1.99g Standard LaTeX package + +("C:\Program Files (x86)\MiKTeX 2.9\tex\latex\base\t1enc.def" +File: t1enc.def 2005/09/27 v1.99g Standard LaTeX file +LaTeX Font Info: Redeclaring font encoding T1 on input line 48. +)) +("C:\Program Files (x86)\MiKTeX 2.9\tex\latex\base\inputenc.sty" +Package: inputenc 2015/03/17 v1.2c Input encoding file +\inpenc@prehook=\toks16 +\inpenc@posthook=\toks17 + +("C:\Program Files (x86)\MiKTeX 2.9\tex\latex\base\latin9.def" +File: latin9.def 2015/03/17 v1.2c Input encoding file +)) +("C:\Program Files (x86)\MiKTeX 2.9\tex\generic\babel\babel.sty" +Package: babel 2015/08/03 3.9m The Babel package + +************************************* +* Local config file bblopts.cfg used +* +("C:\Program Files (x86)\MiKTeX 2.9\tex\latex\00miktex\bblopts.cfg" +File: bblopts.cfg 2006/07/31 v1.0 MiKTeX 'babel' configuration +) +("C:\Program Files (x86)\MiKTeX 2.9\tex\latex\babel-french\frenchb.ldf" +Language: frenchb 2015/10/04 v3.1i French support from the babel system + +("C:\Program Files (x86)\MiKTeX 2.9\tex\generic\babel\babel.def" +File: babel.def 2015/08/03 3.9m Babel common definitions +\babel@savecnt=\count91 +\U@D=\dimen111 +) +\l@acadian = a dialect from \language\l@french +\l@canadien = a dialect from \language\l@french +\FBcolonskip=\skip43 +\FBthinskip=\skip44 +\FB@interchartokenstateORI=\count92 +Package babel Info: Making : an active character on input line 356. +Package babel Info: Making ; an active character on input line 357. +Package babel Info: Making ! an active character on input line 358. +Package babel Info: Making ? an active character on input line 359. +\FBguillskip=\skip45 +\FBguill@level=\count93 +\FB@Mht=\dimen112 +\std@mcc=\count94 +\dec@mcc=\count95 +\listindentFB=\skip46 +\labelwidthFB=\skip47 +\leftmarginFB=\skip48 +\parindentFFN=\dimen113 +)) +("C:\Program Files (x86)\MiKTeX 2.9\tex\latex\carlisle\scalefnt.sty") +("C:\Program Files (x86)\MiKTeX 2.9\tex\latex\amsmath\amsmath.sty" +Package: amsmath 2013/01/14 v2.14 AMS math features +\@mathmargin=\skip49 + +For additional information on amsmath, use the `?' option. +("C:\Program Files (x86)\MiKTeX 2.9\tex\latex\amsmath\amstext.sty" +Package: amstext 2000/06/29 v2.01 + +("C:\Program Files (x86)\MiKTeX 2.9\tex\latex\amsmath\amsgen.sty" +File: amsgen.sty 1999/11/30 v2.0 +\@emptytoks=\toks18 +\ex@=\dimen114 +)) +("C:\Program Files (x86)\MiKTeX 2.9\tex\latex\amsmath\amsbsy.sty" +Package: amsbsy 1999/11/29 v1.2d +\pmbraise@=\dimen115 +) +("C:\Program Files (x86)\MiKTeX 2.9\tex\latex\amsmath\amsopn.sty" +Package: amsopn 1999/12/14 v2.01 operator names +) +\inf@bad=\count96 +LaTeX Info: Redefining \frac on input line 210. +\uproot@=\count97 +\leftroot@=\count98 +LaTeX Info: Redefining \overline on input line 306. +\classnum@=\count99 +\DOTSCASE@=\count100 +LaTeX Info: Redefining \ldots on input line 378. +LaTeX Info: Redefining \dots on input line 381. +LaTeX Info: Redefining \cdots on input line 466. +\Mathstrutbox@=\box26 +\strutbox@=\box27 +\big@size=\dimen116 +LaTeX Font Info: Redeclaring font encoding OML on input line 566. +LaTeX Font Info: Redeclaring font encoding OMS on input line 567. +\macc@depth=\count101 +\c@MaxMatrixCols=\count102 +\dotsspace@=\muskip10 +\c@parentequation=\count103 +\dspbrk@lvl=\count104 +\tag@help=\toks19 +\row@=\count105 +\column@=\count106 +\maxfields@=\count107 +\andhelp@=\toks20 +\eqnshift@=\dimen117 +\alignsep@=\dimen118 +\tagshift@=\dimen119 +\tagwidth@=\dimen120 +\totwidth@=\dimen121 +\lineht@=\dimen122 +\@envbody=\toks21 +\multlinegap=\skip50 +\multlinetaggap=\skip51 +\mathdisplay@stack=\toks22 +LaTeX Info: Redefining \[ on input line 2665. +LaTeX Info: Redefining \] on input line 2666. +) +("C:\Program Files (x86)\MiKTeX 2.9\tex\latex\amscls\amsthm.sty" +Package: amsthm 2015/03/04 v2.20.2 +\thm@style=\toks23 +\thm@bodyfont=\toks24 +\thm@headfont=\toks25 +\thm@notefont=\toks26 +\thm@headpunct=\toks27 +\thm@preskip=\skip52 +\thm@postskip=\skip53 +\thm@headsep=\skip54 +\dth@everypar=\toks28 +) +("C:\Program Files (x86)\MiKTeX 2.9\tex\latex\amsfonts\amssymb.sty" +Package: amssymb 2013/01/14 v3.01 AMS font symbols + +("C:\Program Files (x86)\MiKTeX 2.9\tex\latex\amsfonts\amsfonts.sty" +Package: amsfonts 2013/01/14 v3.01 Basic AMSFonts support +\symAMSa=\mathgroup4 +\symAMSb=\mathgroup5 +LaTeX Font Info: Overwriting math alphabet `\mathfrak' in version `bold' +(Font) U/euf/m/n --> U/euf/b/n on input line 106. +)) +("C:\Program Files (x86)\MiKTeX 2.9\tex\latex\url\url.sty" +\Urlmuskip=\muskip11 +Package: url 2013/09/16 ver 3.4 Verb mode for urls, etc. +) +(C:\Users\rmj2666\AppData\Roaming\MiKTeX\2.9\tex\latex\numprint\numprint.sty +Package: numprint 2012/08/20 v1.39 Print numbers (HH) + +("C:\Program Files (x86)\MiKTeX 2.9\tex\latex\tools\array.sty" +Package: array 2014/10/28 v2.4c Tabular extension package (FMi) +\col@sep=\dimen123 +\extrarowheight=\dimen124 +\NC@list=\toks29 +\extratabsurround=\skip55 +\backup@length=\skip56 +) +\c@nprt@mantissa@digitsbefore=\count108 +\c@nprt@mantissa@digitsafter=\count109 +\c@nprt@exponent@digitsbefore=\count110 +\c@nprt@exponent@digitsafter=\count111 +\nprt@digitwidth=\skip57 +\nprt@sepwidth=\skip58 +\nprt@decimalwidth=\skip59 +\nprt@blockwidth=\skip60 +\nprt@digittoks=\toks30 +\nprt@pretoks=\toks31 +\nprt@posttoks=\toks32 +\nprt@thisdigit=\count112 +\nprt@curpos=\count113 +\nprt@rndpos=\count114 +\c@nprt@digitsfirstblock=\count115 +\c@nprt@blockcnt=\count116 +\c@nprt@cntprint=\count117 + +No configuration file `numprint.cfg' found.) +("C:\Program Files (x86)\MiKTeX 2.9\tex\latex\tools\xspace.sty" +Package: xspace 2014/10/28 v1.13 Space after command names (DPC,MH) +) +(C:\Users\rmj2666\AppData\Roaming\MiKTeX\2.9\tex\latex\todonotes\todonotes.sty +Package: todonotes 2015/07/09 .dtx Todonotes source and documentation. +Package: todonotes 2012/07/25 + +("C:\Program Files (x86)\MiKTeX 2.9\tex\latex\base\ifthen.sty" +Package: ifthen 2014/09/29 v1.1c Standard LaTeX ifthen package (DPC) +) +("C:\Program Files (x86)\MiKTeX 2.9\tex\latex\xkeyval\xkeyval.sty" +Package: xkeyval 2014/12/03 v2.7a package option processing (HA) + +("C:\Program Files (x86)\MiKTeX 2.9\tex\generic\xkeyval\xkeyval.tex" +("C:\Program Files (x86)\MiKTeX 2.9\tex\generic\xkeyval\xkvutils.tex" +\XKV@toks=\toks33 +\XKV@tempa@toks=\toks34 +) +\XKV@depth=\count118 +File: xkeyval.tex 2014/12/03 v2.7a key=value parser (HA) +)) +("C:\Program Files (x86)\MiKTeX 2.9\tex\latex\xcolor\xcolor.sty" +Package: xcolor 2007/01/21 v2.11 LaTeX color extensions (UK) + +("C:\Program Files (x86)\MiKTeX 2.9\tex\latex\00miktex\color.cfg" +File: color.cfg 2007/01/18 v1.5 color configuration of teTeX/TeXLive +) +Package xcolor Info: Driver file: pdftex.def on input line 225. + +("C:\Program Files (x86)\MiKTeX 2.9\tex\latex\pdftex-def\pdftex.def" +File: pdftex.def 2011/05/27 v0.06d Graphics/color for pdfTeX + +("C:\Program Files (x86)\MiKTeX 2.9\tex\generic\oberdiek\infwarerr.sty" +Package: infwarerr 2010/04/08 v1.3 Providing info/warning/error messages (HO) +) +("C:\Program Files (x86)\MiKTeX 2.9\tex\generic\oberdiek\ltxcmds.sty" +Package: ltxcmds 2011/11/09 v1.22 LaTeX kernel commands for general use (HO) +) +\Gread@gobject=\count119 +) +Package xcolor Info: Model `cmy' substituted by `cmy0' on input line 1337. +Package xcolor Info: Model `hsb' substituted by `rgb' on input line 1341. +Package xcolor Info: Model `RGB' extended on input line 1353. +Package xcolor Info: Model `HTML' substituted by `rgb' on input line 1355. +Package xcolor Info: Model `Hsb' substituted by `hsb' on input line 1356. +Package xcolor Info: Model `tHsb' substituted by `hsb' on input line 1357. +Package xcolor Info: Model `HSB' substituted by `hsb' on input line 1358. +Package xcolor Info: Model `Gray' substituted by `gray' on input line 1359. +Package xcolor Info: Model `wave' substituted by `hsb' on input line 1360. +) +("C:\Program Files (x86)\MiKTeX 2.9\tex\latex\pgf\frontendlayer\tikz.sty" +("C:\Program Files (x86)\MiKTeX 2.9\tex\latex\pgf\basiclayer\pgf.sty" +("C:\Program Files (x86)\MiKTeX 2.9\tex\latex\pgf\utilities\pgfrcs.sty" +("C:\Program Files (x86)\MiKTeX 2.9\tex\generic\pgf\utilities\pgfutil-common.te +x" +\pgfutil@everybye=\toks35 +\pgfutil@tempdima=\dimen125 +\pgfutil@tempdimb=\dimen126 + +("C:\Program Files (x86)\MiKTeX 2.9\tex\generic\pgf\utilities\pgfutil-common-li +sts.tex")) +("C:\Program Files (x86)\MiKTeX 2.9\tex\generic\pgf\utilities\pgfutil-latex.def +" +\pgfutil@abb=\box28 + ("C:\Program Files (x86)\MiKTeX 2.9\tex\latex\ms\everyshi.sty" +Package: everyshi 2001/05/15 v3.00 EveryShipout Package (MS) +)) +("C:\Program Files (x86)\MiKTeX 2.9\tex\generic\pgf\utilities\pgfrcs.code.tex" +Package: pgfrcs 2015/08/07 v3.0.1a (rcs-revision 1.31) +)) +Package: pgf 2015/08/07 v3.0.1a (rcs-revision 1.15) + ("C:\Program Files (x86)\MiKTeX 2.9\tex\latex\pgf\basiclayer\pgfcore.sty" +("C:\Program Files (x86)\MiKTeX 2.9\tex\latex\graphics\graphicx.sty" +Package: graphicx 2014/10/28 v1.0g Enhanced LaTeX Graphics (DPC,SPQR) + +("C:\Program Files (x86)\MiKTeX 2.9\tex\latex\graphics\graphics.sty" +Package: graphics 2014/10/28 v1.0p Standard LaTeX Graphics (DPC,SPQR) + +("C:\Program Files (x86)\MiKTeX 2.9\tex\latex\graphics\trig.sty" +Package: trig 1999/03/16 v1.09 sin cos tan (DPC) +) +("C:\Program Files (x86)\MiKTeX 2.9\tex\latex\00miktex\graphics.cfg" +File: graphics.cfg 2007/01/18 v1.5 graphics configuration of teTeX/TeXLive +) +Package graphics Info: Driver file: pdftex.def on input line 94. +) +\Gin@req@height=\dimen127 +\Gin@req@width=\dimen128 +) +("C:\Program Files (x86)\MiKTeX 2.9\tex\latex\pgf\systemlayer\pgfsys.sty" +("C:\Program Files (x86)\MiKTeX 2.9\tex\generic\pgf\systemlayer\pgfsys.code.tex +" +Package: pgfsys 2014/07/09 v3.0.1a (rcs-revision 1.48) + ("C:\Program Files (x86)\MiKTeX 2.9\tex\generic\pgf\utilities\pgfkeys.code.tex +" +\pgfkeys@pathtoks=\toks36 +\pgfkeys@temptoks=\toks37 + +("C:\Program Files (x86)\MiKTeX 2.9\tex\generic\pgf\utilities\pgfkeysfiltered.c +ode.tex" +\pgfkeys@tmptoks=\toks38 +)) +\pgf@x=\dimen129 +\pgf@y=\dimen130 +\pgf@xa=\dimen131 +\pgf@ya=\dimen132 +\pgf@xb=\dimen133 +\pgf@yb=\dimen134 +\pgf@xc=\dimen135 +\pgf@yc=\dimen136 +\w@pgf@writea=\write3 +\r@pgf@reada=\read1 +\c@pgf@counta=\count120 +\c@pgf@countb=\count121 +\c@pgf@countc=\count122 +\c@pgf@countd=\count123 +\t@pgf@toka=\toks39 +\t@pgf@tokb=\toks40 +\t@pgf@tokc=\toks41 + +("C:\Program Files (x86)\MiKTeX 2.9\tex\generic\pgf\systemlayer\pgf.cfg" +File: pgf.cfg 2008/05/14 (rcs-revision 1.7) +) +Driver file for pgf: pgfsys-pdftex.def + +("C:\Program Files (x86)\MiKTeX 2.9\tex\generic\pgf\systemlayer\pgfsys-pdftex.d +ef" +File: pgfsys-pdftex.def 2014/10/11 (rcs-revision 1.35) + +("C:\Program Files (x86)\MiKTeX 2.9\tex\generic\pgf\systemlayer\pgfsys-common-p +df.def" +File: pgfsys-common-pdf.def 2013/10/10 (rcs-revision 1.13) +))) +("C:\Program Files (x86)\MiKTeX 2.9\tex\generic\pgf\systemlayer\pgfsyssoftpath. +code.tex" +File: pgfsyssoftpath.code.tex 2013/09/09 (rcs-revision 1.9) +\pgfsyssoftpath@smallbuffer@items=\count124 +\pgfsyssoftpath@bigbuffer@items=\count125 +) +("C:\Program Files (x86)\MiKTeX 2.9\tex\generic\pgf\systemlayer\pgfsysprotocol. +code.tex" +File: pgfsysprotocol.code.tex 2006/10/16 (rcs-revision 1.4) +)) +("C:\Program Files (x86)\MiKTeX 2.9\tex\generic\pgf\basiclayer\pgfcore.code.tex +" +Package: pgfcore 2010/04/11 v3.0.1a (rcs-revision 1.7) + ("C:\Program Files (x86)\MiKTeX 2.9\tex\generic\pgf\math\pgfmath.code.tex" +("C:\Program Files (x86)\MiKTeX 2.9\tex\generic\pgf\math\pgfmathcalc.code.tex" +("C:\Program Files (x86)\MiKTeX 2.9\tex\generic\pgf\math\pgfmathutil.code.tex") +("C:\Program Files (x86)\MiKTeX 2.9\tex\generic\pgf\math\pgfmathparser.code.tex +" +\pgfmath@dimen=\dimen137 +\pgfmath@count=\count126 +\pgfmath@box=\box29 +\pgfmath@toks=\toks42 +\pgfmath@stack@operand=\toks43 +\pgfmath@stack@operation=\toks44 +) +("C:\Program Files (x86)\MiKTeX 2.9\tex\generic\pgf\math\pgfmathfunctions.code. +tex" +("C:\Program Files (x86)\MiKTeX 2.9\tex\generic\pgf\math\pgfmathfunctions.basic +.code.tex") +("C:\Program Files (x86)\MiKTeX 2.9\tex\generic\pgf\math\pgfmathfunctions.trigo +nometric.code.tex") +("C:\Program Files (x86)\MiKTeX 2.9\tex\generic\pgf\math\pgfmathfunctions.rando +m.code.tex") +("C:\Program Files (x86)\MiKTeX 2.9\tex\generic\pgf\math\pgfmathfunctions.compa +rison.code.tex") +("C:\Program Files (x86)\MiKTeX 2.9\tex\generic\pgf\math\pgfmathfunctions.base. +code.tex") +("C:\Program Files (x86)\MiKTeX 2.9\tex\generic\pgf\math\pgfmathfunctions.round +.code.tex") +("C:\Program Files (x86)\MiKTeX 2.9\tex\generic\pgf\math\pgfmathfunctions.misc. +code.tex") +("C:\Program Files (x86)\MiKTeX 2.9\tex\generic\pgf\math\pgfmathfunctions.integ +erarithmetics.code.tex"))) +("C:\Program Files (x86)\MiKTeX 2.9\tex\generic\pgf\math\pgfmathfloat.code.tex" +\c@pgfmathroundto@lastzeros=\count127 +)) +("C:\Program Files (x86)\MiKTeX 2.9\tex\generic\pgf\basiclayer\pgfcorepoints.co +de.tex" +File: pgfcorepoints.code.tex 2013/10/07 (rcs-revision 1.27) +\pgf@picminx=\dimen138 +\pgf@picmaxx=\dimen139 +\pgf@picminy=\dimen140 +\pgf@picmaxy=\dimen141 +\pgf@pathminx=\dimen142 +\pgf@pathmaxx=\dimen143 +\pgf@pathminy=\dimen144 +\pgf@pathmaxy=\dimen145 +\pgf@xx=\dimen146 +\pgf@xy=\dimen147 +\pgf@yx=\dimen148 +\pgf@yy=\dimen149 +\pgf@zx=\dimen150 +\pgf@zy=\dimen151 +) +("C:\Program Files (x86)\MiKTeX 2.9\tex\generic\pgf\basiclayer\pgfcorepathconst +ruct.code.tex" +File: pgfcorepathconstruct.code.tex 2013/10/07 (rcs-revision 1.29) +\pgf@path@lastx=\dimen152 +\pgf@path@lasty=\dimen153 +) +("C:\Program Files (x86)\MiKTeX 2.9\tex\generic\pgf\basiclayer\pgfcorepathusage +.code.tex" +File: pgfcorepathusage.code.tex 2014/11/02 (rcs-revision 1.24) +\pgf@shorten@end@additional=\dimen154 +\pgf@shorten@start@additional=\dimen155 +) +("C:\Program Files (x86)\MiKTeX 2.9\tex\generic\pgf\basiclayer\pgfcorescopes.co +de.tex" +File: pgfcorescopes.code.tex 2015/05/08 (rcs-revision 1.46) +\pgfpic=\box30 +\pgf@hbox=\box31 +\pgf@layerbox@main=\box32 +\pgf@picture@serial@count=\count128 +) +("C:\Program Files (x86)\MiKTeX 2.9\tex\generic\pgf\basiclayer\pgfcoregraphicst +ate.code.tex" +File: pgfcoregraphicstate.code.tex 2014/11/02 (rcs-revision 1.12) +\pgflinewidth=\dimen156 +) +("C:\Program Files (x86)\MiKTeX 2.9\tex\generic\pgf\basiclayer\pgfcoretransform +ations.code.tex" +File: pgfcoretransformations.code.tex 2015/08/07 (rcs-revision 1.20) +\pgf@pt@x=\dimen157 +\pgf@pt@y=\dimen158 +\pgf@pt@temp=\dimen159 +) +("C:\Program Files (x86)\MiKTeX 2.9\tex\generic\pgf\basiclayer\pgfcorequick.cod +e.tex" +File: pgfcorequick.code.tex 2008/10/09 (rcs-revision 1.3) +) +("C:\Program Files (x86)\MiKTeX 2.9\tex\generic\pgf\basiclayer\pgfcoreobjects.c +ode.tex" +File: pgfcoreobjects.code.tex 2006/10/11 (rcs-revision 1.2) +) +("C:\Program Files (x86)\MiKTeX 2.9\tex\generic\pgf\basiclayer\pgfcorepathproce +ssing.code.tex" +File: pgfcorepathprocessing.code.tex 2013/09/09 (rcs-revision 1.9) +) +("C:\Program Files (x86)\MiKTeX 2.9\tex\generic\pgf\basiclayer\pgfcorearrows.co +de.tex" +File: pgfcorearrows.code.tex 2015/05/14 (rcs-revision 1.43) +\pgfarrowsep=\dimen160 +) +("C:\Program Files (x86)\MiKTeX 2.9\tex\generic\pgf\basiclayer\pgfcoreshade.cod +e.tex" +File: pgfcoreshade.code.tex 2013/07/15 (rcs-revision 1.15) +\pgf@max=\dimen161 +\pgf@sys@shading@range@num=\count129 +) +("C:\Program Files (x86)\MiKTeX 2.9\tex\generic\pgf\basiclayer\pgfcoreimage.cod +e.tex" +File: pgfcoreimage.code.tex 2013/07/15 (rcs-revision 1.18) + +("C:\Program Files (x86)\MiKTeX 2.9\tex\generic\pgf\basiclayer\pgfcoreexternal. +code.tex" +File: pgfcoreexternal.code.tex 2014/07/09 (rcs-revision 1.21) +\pgfexternal@startupbox=\box33 +)) +("C:\Program Files (x86)\MiKTeX 2.9\tex\generic\pgf\basiclayer\pgfcorelayers.co +de.tex" +File: pgfcorelayers.code.tex 2013/07/18 (rcs-revision 1.7) +) +("C:\Program Files (x86)\MiKTeX 2.9\tex\generic\pgf\basiclayer\pgfcoretranspare +ncy.code.tex" +File: pgfcoretransparency.code.tex 2013/09/30 (rcs-revision 1.5) +) +("C:\Program Files (x86)\MiKTeX 2.9\tex\generic\pgf\basiclayer\pgfcorepatterns. +code.tex" +File: pgfcorepatterns.code.tex 2013/11/07 (rcs-revision 1.5) +))) +("C:\Program Files (x86)\MiKTeX 2.9\tex\generic\pgf\modules\pgfmoduleshapes.cod +e.tex" +File: pgfmoduleshapes.code.tex 2014/03/21 (rcs-revision 1.35) +\pgfnodeparttextbox=\box34 +) +("C:\Program Files (x86)\MiKTeX 2.9\tex\generic\pgf\modules\pgfmoduleplot.code. +tex" +File: pgfmoduleplot.code.tex 2015/08/03 (rcs-revision 1.13) +) +("C:\Program Files (x86)\MiKTeX 2.9\tex\latex\pgf\compatibility\pgfcomp-version +-0-65.sty" +Package: pgfcomp-version-0-65 2007/07/03 v3.0.1a (rcs-revision 1.7) +\pgf@nodesepstart=\dimen162 +\pgf@nodesepend=\dimen163 +) +("C:\Program Files (x86)\MiKTeX 2.9\tex\latex\pgf\compatibility\pgfcomp-version +-1-18.sty" +Package: pgfcomp-version-1-18 2007/07/23 v3.0.1a (rcs-revision 1.1) +)) +("C:\Program Files (x86)\MiKTeX 2.9\tex\latex\pgf\utilities\pgffor.sty" +("C:\Program Files (x86)\MiKTeX 2.9\tex\latex\pgf\utilities\pgfkeys.sty" +("C:\Program Files (x86)\MiKTeX 2.9\tex\generic\pgf\utilities\pgfkeys.code.tex" +)) ("C:\Program Files (x86)\MiKTeX 2.9\tex\latex\pgf\math\pgfmath.sty" +("C:\Program Files (x86)\MiKTeX 2.9\tex\generic\pgf\math\pgfmath.code.tex")) +("C:\Program Files (x86)\MiKTeX 2.9\tex\generic\pgf\utilities\pgffor.code.tex" +Package: pgffor 2013/12/13 v3.0.1a (rcs-revision 1.25) + +("C:\Program Files (x86)\MiKTeX 2.9\tex\generic\pgf\math\pgfmath.code.tex") +\pgffor@iter=\dimen164 +\pgffor@skip=\dimen165 +\pgffor@stack=\toks45 +\pgffor@toks=\toks46 +)) +("C:\Program Files (x86)\MiKTeX 2.9\tex\generic\pgf\frontendlayer\tikz\tikz.cod +e.tex" +Package: tikz 2015/08/07 v3.0.1a (rcs-revision 1.151) + +("C:\Program Files (x86)\MiKTeX 2.9\tex\generic\pgf\libraries\pgflibraryplothan +dlers.code.tex" +File: pgflibraryplothandlers.code.tex 2013/08/31 v3.0.1a (rcs-revision 1.20) +\pgf@plot@mark@count=\count130 +\pgfplotmarksize=\dimen166 +) +\tikz@lastx=\dimen167 +\tikz@lasty=\dimen168 +\tikz@lastxsaved=\dimen169 +\tikz@lastysaved=\dimen170 +\tikzleveldistance=\dimen171 +\tikzsiblingdistance=\dimen172 +\tikz@figbox=\box35 +\tikz@figbox@bg=\box36 +\tikz@tempbox=\box37 +\tikz@tempbox@bg=\box38 +\tikztreelevel=\count131 +\tikznumberofchildren=\count132 +\tikznumberofcurrentchild=\count133 +\tikz@fig@count=\count134 + +("C:\Program Files (x86)\MiKTeX 2.9\tex\generic\pgf\modules\pgfmodulematrix.cod +e.tex" +File: pgfmodulematrix.code.tex 2013/09/17 (rcs-revision 1.8) +\pgfmatrixcurrentrow=\count135 +\pgfmatrixcurrentcolumn=\count136 +\pgf@matrix@numberofcolumns=\count137 +) +\tikz@expandcount=\count138 + +("C:\Program Files (x86)\MiKTeX 2.9\tex\generic\pgf\frontendlayer\tikz\librarie +s\tikzlibrarytopaths.code.tex" +File: tikzlibrarytopaths.code.tex 2008/06/17 v3.0.1a (rcs-revision 1.2) +))) +("C:\Program Files (x86)\MiKTeX 2.9\tex\generic\pgf\frontendlayer\tikz\librarie +s\tikzlibrarypositioning.code.tex" +File: tikzlibrarypositioning.code.tex 2008/10/06 v3.0.1a (rcs-revision 1.7) +) +("C:\Program Files (x86)\MiKTeX 2.9\tex\latex\tools\calc.sty" +Package: calc 2014/10/28 v4.3 Infix arithmetic (KKT,FJ) +\calc@Acount=\count139 +\calc@Bcount=\count140 +\calc@Adimen=\dimen173 +\calc@Bdimen=\dimen174 +\calc@Askip=\skip61 +\calc@Bskip=\skip62 +LaTeX Info: Redefining \setlength on input line 80. +LaTeX Info: Redefining \addtolength on input line 81. +\calc@Ccount=\count141 +\calc@Cskip=\skip63 +) +\c@@todonotes@numberoftodonotes=\count142 +) +("C:\Program Files (x86)\MiKTeX 2.9\tex\latex\caption\subcaption.sty" +Package: subcaption 2015/09/15 v1.1-100 Sub-captions (AR) + +("C:\Program Files (x86)\MiKTeX 2.9\tex\latex\caption\caption.sty" +Package: caption 2015/09/17 v3.3-111 Customizing captions (AR) + +("C:\Program Files (x86)\MiKTeX 2.9\tex\latex\caption\caption3.sty" +Package: caption3 2015/09/20 v1.7-115 caption3 kernel (AR) +Package caption3 Info: TeX engine: e-TeX on input line 57. +\captionmargin=\dimen175 +\captionmargin@=\dimen176 +\captionwidth=\dimen177 +\caption@tempdima=\dimen178 +\caption@indent=\dimen179 +\caption@parindent=\dimen180 +\caption@hangindent=\dimen181 +) +\c@ContinuedFloat=\count143 +) +\c@subfigure=\count144 +\c@subtable=\count145 +) +(These_RCE.aux + +LaTeX Warning: Label `eq:12' multiply defined. + +) +LaTeX Font Info: Checking defaults for OML/cmm/m/it on input line 56. +LaTeX Font Info: ... okay on input line 56. +LaTeX Font Info: Checking defaults for T1/cmr/m/n on input line 56. +LaTeX Font Info: ... okay on input line 56. +LaTeX Font Info: Checking defaults for OT1/cmr/m/n on input line 56. +LaTeX Font Info: ... okay on input line 56. +LaTeX Font Info: Checking defaults for OMS/cmsy/m/n on input line 56. +LaTeX Font Info: ... okay on input line 56. +LaTeX Font Info: Checking defaults for OMX/cmex/m/n on input line 56. +LaTeX Font Info: ... okay on input line 56. +LaTeX Font Info: Checking defaults for U/cmr/m/n on input line 56. +LaTeX Font Info: ... okay on input line 56. +LaTeX Font Info: Try loading font information for T1+ptm on input line 56. + ("C:\Program Files (x86)\MiKTeX 2.9\tex\latex\psnfss\t1ptm.fd" +File: t1ptm.fd 2001/06/04 font definitions for T1/ptm. +) +*geometry* driver: auto-detecting +*geometry* detected driver: pdftex +*geometry* verbose mode - [ preamble ] result: +* driver: pdftex +* paper: a4paper +* layout: +* layoutoffset:(h,v)=(0.0pt,0.0pt) +* modes: +* h-part:(L,W,R)=(71.13188pt, 483.69687pt, 42.67912pt) +* v-part:(T,H,B)=(56.9055pt, 731.23584pt, 56.9055pt) +* \paperwidth=597.50787pt +* \paperheight=845.04684pt +* \textwidth=483.69687pt +* \textheight=731.23584pt +* \oddsidemargin=-1.1381pt +* \evensidemargin=-1.1381pt +* \topmargin=-52.36449pt +* \headheight=12.0pt +* \headsep=25.0pt +* \topskip=10.0pt +* \footskip=30.0pt +* \marginparwidth=65.0pt +* \marginparsep=11.0pt +* \columnsep=10.0pt +* \skip\footins=9.0pt plus 4.0pt minus 2.0pt +* \hoffset=0.0pt +* \voffset=0.0pt +* \mag=1000 +* \@twocolumnfalse +* \@twosidefalse +* \@mparswitchfalse +* \@reversemarginfalse +* (1in=72.27pt=25.4mm, 1cm=28.453pt) + +LaTeX Info: Redefining \degres on input line 56. +LaTeX Info: Redefining \dots on input line 56. +LaTeX Info: Redefining \up on input line 56. +("C:\Program Files (x86)\MiKTeX 2.9\tex\context\base\supp-pdf.mkii" +[Loading MPS to PDF converter (version 2006.09.02).] +\scratchcounter=\count146 +\scratchdimen=\dimen182 +\scratchbox=\box39 +\nofMPsegments=\count147 +\nofMParguments=\count148 +\everyMPshowfont=\toks47 +\MPscratchCnt=\count149 +\MPscratchDim=\dimen183 +\MPnumerator=\count150 +\makeMPintoPDFobject=\count151 +\everyMPtoPDFconversion=\toks48 +) ABD: EveryShipout initializing macros +Package caption Info: Begin \AtBeginDocument code. +Package caption Info: End \AtBeginDocument code. + [1 + +{C:/Users/rmj2666/AppData/Local/MiKTeX/2.9/pdftex/config/pdftex.map}] +LaTeX Font Info: Font shape `T1/ptm/bx/n' in size <24.88> not available +(Font) Font shape `T1/ptm/b/n' tried instead on input line 64. + (These_RCE.toc +LaTeX Font Info: Try loading font information for U+msa on input line 3. + +("C:\Program Files (x86)\MiKTeX 2.9\tex\latex\amsfonts\umsa.fd" +File: umsa.fd 2013/01/14 v3.01 AMS symbols A +) +LaTeX Font Info: Try loading font information for U+msb on input line 3. + +("C:\Program Files (x86)\MiKTeX 2.9\tex\latex\amsfonts\umsb.fd" +File: umsb.fd 2013/01/14 v3.01 AMS symbols B +)) +\tf@toc=\write4 + [2 + +] [3] +[4 + +] [5 + +] +LaTeX Font Info: Font shape `T1/ptm/bx/n' in size <14.4> not available +(Font) Font shape `T1/ptm/b/n' tried instead on input line 88. +LaTeX Font Info: Font shape `T1/ptm/bx/n' in size <12> not available +(Font) Font shape `T1/ptm/b/n' tried instead on input line 136. + [6 + +] +<"3D data partitionning btw 2 clusters".pdf, id=32, 614.295pt x 794.97pt> +File: "3D data partitionning btw 2 clusters".pdf Graphic file (type pdf) + + +Package pdftex.def Info: "3D data partitionning btw 2 clusters".pdf used on inp +ut line 156. +(pdftex.def) Requested size: 217.65913pt x 170.709pt. + +<"1D-2D-3D Domain decomposition".pdf, id=33, 614.295pt x 794.97pt> +File: "1D-2D-3D Domain decomposition".pdf Graphic file (type pdf) + + +Package pdftex.def Info: "1D-2D-3D Domain decomposition".pdf used on input line + 161. +(pdftex.def) Requested size: 241.8518pt x 142.26357pt. + +Overfull \hbox (1.90002pt too wide) in paragraph at lines 155--165 +[]$[]$ $[]$ + [] + +[7 <./3D data partitionning btw 2 clusters.pdf> <./1D-2D-3D Domain decompositio +n.pdf + +pdfTeX warning: pdflatex (file ./1D-2D-3D Domain decomposition.pdf): PDF inclus +ion: multiple pdfs with page group included in a single page +>] <"Synchronous iterations model".pdf, id=49, 614.295pt x 794.97pt> +File: "Synchronous iterations model".pdf Graphic file (type pdf) + + +Package pdftex.def Info: "Synchronous iterations model".pdf used on input line +246. +(pdftex.def) Requested size: 1842.88046pt x 2384.90419pt. + +<"Asynchronous iterations model".pdf, id=50, 614.295pt x 794.97pt> +File: "Asynchronous iterations model".pdf Graphic file (type pdf) + + +Package pdftex.def Info: "Asynchronous iterations model".pdf used on input line + 251. +(pdftex.def) Requested size: 1842.88046pt x 2384.90419pt. + +Overfull \hbox (1.90002pt too wide) in paragraph at lines 245--255 +[]$[]$ $[]$ + [] + +[8 <./Synchronous iterations model.pdf> <./Asynchronous iterations model.pdf + +pdfTeX warning: pdflatex (file ./Asynchronous iterations model.pdf): PDF inclus +ion: multiple pdfs with page group included in a single page +>] [9] [10] [11 + +] [12] +<"Weak vs Strong scaling".pdf, id=78, 614.295pt x 794.97pt> +File: "Weak vs Strong scaling".pdf Graphic file (type pdf) + + +Package pdftex.def Info: "Weak vs Strong scaling".pdf used on input line 510. +(pdftex.def) Requested size: 284.52756pt x 368.21373pt. + + +LaTeX Warning: `h' float specifier changed to `ht'. + +[13] [14 <./Weak vs Strong scaling.pdf>] [15] +LaTeX Font Info: Font shape `T1/ptm/bx/n' in size <10> not available +(Font) Font shape `T1/ptm/b/n' tried instead on input line 666. + +<"Architecture des CPU multi-coeurs".pdf, id=94, 614.295pt x 794.97pt> +File: "Architecture des CPU multi-coeurs".pdf Graphic file (type pdf) + + +Package pdftex.def Info: "Architecture des CPU multi-coeurs".pdf used on input +line 697. +(pdftex.def) Requested size: 284.52756pt x 368.21373pt. + [16] +<"MIMD Distributed Memory".pdf, id=98, 614.295pt x 794.97pt> +File: "MIMD Distributed Memory".pdf Graphic file (type pdf) + + +Package pdftex.def Info: "MIMD Distributed Memory".pdf used on input line 714. +(pdftex.def) Requested size: 1842.88046pt x 2384.90419pt. + +<"MIMD Shared memory - SMP".pdf, id=99, 614.295pt x 794.97pt> +File: "MIMD Shared memory - SMP".pdf Graphic file (type pdf) + + +Package pdftex.def Info: "MIMD Shared memory - SMP".pdf used on input line 719. + +(pdftex.def) Requested size: 1842.88046pt x 2384.90419pt. + +<"MIMD Hybride".pdf, id=100, 614.295pt x 794.97pt> +File: "MIMD Hybride".pdf Graphic file (type pdf) + +Package pdftex.def Info: "MIMD Hybride".pdf used on input line 724. +(pdftex.def) Requested size: 1842.88046pt x 2384.90419pt. + +Overfull \hbox (1.90002pt too wide) in paragraph at lines 713--728 +[]$[]$ $[]$ + [] + + +LaTeX Warning: `h' float specifier changed to `ht'. + +[17 <./Architecture des CPU multi-coeurs.pdf>] +<"Evolution de la puissance de calcul mondiale".pdf, id=109, 614.295pt x 794.97 +pt> +File: "Evolution de la puissance de calcul mondiale".pdf Graphic file (type pdf +) + +Package pdftex.def Info: "Evolution de la puissance de calcul mondiale".pdf use +d on input line 767. +(pdftex.def) Requested size: 284.52756pt x 368.21373pt. + + +LaTeX Warning: `h' float specifier changed to `ht'. + +[18 <./MIMD Distributed Memory.pdf> <./MIMD Shared memory - SMP.pdf + +pdfTeX warning: pdflatex (file ./MIMD Shared memory - SMP.pdf): PDF inclusion: +multiple pdfs with page group included in a single page +> <./MIMD Hybride.pdf + +pdfTeX warning: pdflatex (file ./MIMD Hybride.pdf): PDF inclusion: multiple pdf +s with page group included in a single page +>] [19 <./Evolution de la puissance de calcul mondiale.pdf>] +<"UMA architecture".pdf, id=135, 614.295pt x 794.97pt> +File: "UMA architecture".pdf Graphic file (type pdf) + + +Package pdftex.def Info: "UMA architecture".pdf used on input line 838. +(pdftex.def) Requested size: 1842.88046pt x 2384.90419pt. + +<"NUMA architecture".pdf, id=136, 614.295pt x 794.97pt> +File: "NUMA architecture".pdf Graphic file (type pdf) + + +Package pdftex.def Info: "NUMA architecture".pdf used on input line 843. +(pdftex.def) Requested size: 1842.88046pt x 2384.90419pt. + +<"COMA architecture".pdf, id=137, 614.295pt x 794.97pt> +File: "COMA architecture".pdf Graphic file (type pdf) + + +Package pdftex.def Info: "COMA architecture".pdf used on input line 848. +(pdftex.def) Requested size: 1842.88046pt x 2384.90419pt. + +Overfull \hbox (1.90002pt too wide) in paragraph at lines 837--852 +[]$[]$ $[]$ + [] + +[20 <./UMA architecture.pdf> <./NUMA architecture.pdf + +pdfTeX warning: pdflatex (file ./NUMA architecture.pdf): PDF inclusion: multipl +e pdfs with page group included in a single page +> <./COMA architecture.pdf + +pdfTeX warning: pdflatex (file ./COMA architecture.pdf): PDF inclusion: multipl +e pdfs with page group included in a single page +>] [21] [22] [23] [24] [25 + +] [26 + +] [27 + +] [28 + +] [29 + +] [30 + +] +Overfull \hbox (12.67207pt too wide) in paragraph at lines 1160--1162 +\T1/ptm/m/it/10 mance while re-du-cing po-wer consump-tion\T1/ptm/m/n/10 . http + ://www.hpctoday.fr/published/regional/operations/docs/W-HPCperformance- + [] + + +Overfull \hbox (23.05951pt too wide) in paragraph at lines 1165--1166 +[]\T1/ptm/m/n/10 [15] C. HAR-RIS et al. HPC Tech-no-logy Up-date. \T1/ptm/m/it/ +10 Paw-set Su-per-com-pu-ting Cen-ter - Sept 2015\T1/ptm/m/n/10 . http ://www.p +awsey.org.au/wp- + [] + + +Overfull \hbox (86.05052pt too wide) in paragraph at lines 1167--1169 +\T1/ptm/m/it/10 Sec-tion, Oak Ridge, Na-tio-nal La-bo-ra-tory, Oak Ridge\T1/ptm +/m/n/10 . http ://ci-te-seerx.ist.psu.edu/viewdoc/download ?doi=10.1.1.49.3743& +rep=rep1&type=pdf + [] + + +Overfull \hbox (80.11806pt too wide) in paragraph at lines 1170--1172 +\T1/ptm/m/it/10 Com-pu-ter Science Pt.Ravishankar Shukla Uni-ver-sity, Rai-pur, +C.G. \T1/ptm/m/n/10 http ://www.ijcset.net/docs/Volumes/volume2issue10/ijcset20 +12021006.pdf + [] + +[31] (These_RCE.aux) + +LaTeX Warning: There were multiply-defined labels. + + ) +Here is how much of TeX's memory you used: + 16056 strings out of 493673 + 303821 string characters out of 3141524 + 363151 words of memory out of 3000000 + 19079 multiletter control sequences out of 15000+200000 + 41165 words of font info for 48 fonts, out of 3000000 for 9000 + 1025 hyphenation exceptions out of 8191 + 62i,8n,94p,420b,602s stack positions out of 5000i,500n,10000p,200000b,50000s +{C:/Program Files (x86)/MiKTeX 2.9/fonts/enc/dvips/fontname/8r.enc} +Output written on These_RCE.pdf (31 pages, 608894 bytes). +PDF statistics: + 230 PDF objects out of 1000 (max. 8388607) + 0 named destinations out of 1000 (max. 500000) + 78 words of extra memory for PDF output out of 10000 (max. 10000000) + diff --git a/These_RCE.pdf b/These_RCE.pdf new file mode 100644 index 0000000..45a5593 Binary files /dev/null and b/These_RCE.pdf differ diff --git a/These_RCE.synctex.gz b/These_RCE.synctex.gz new file mode 100644 index 0000000..8c0f558 Binary files /dev/null and b/These_RCE.synctex.gz differ diff --git a/These_RCE.tex b/These_RCE.tex new file mode 100644 index 0000000..e22ad09 --- /dev/null +++ b/These_RCE.tex @@ -0,0 +1,1185 @@ +%% LyX 2.1.4 created this file. For more info, see http://www.lyx.org/. +%% Do not edit unless you really know what you are doing. +\documentclass[french]{report} + +% Font type and font size +\usepackage{times} +\fontsize{12}{15} + +%Espacement des paragraphes +\setlength{\parskip}{0.3cm} +%interligne paragraphe : voir spacing ci-dessous +\usepackage{setspace} + +%setting margins +\usepackage +[ + a4paper, + left=2.5cm, + right=1.5cm, + top=2cm, + bottom=2cm, + % use vmargin=2cm to make vertical margins equal to 2cm. + % us hmargin=3cm to make horizontal margins equal to 3cm. + % use margin=3cm to make all margins equal to 3cm. +] +{geometry} + +\usepackage[T1]{fontenc} +\usepackage[latin9]{inputenc} +\usepackage{babel} +\usepackage{amsmath, amsthm, amssymb} + +\usepackage{url} +\DeclareUrlCommand\email{\urlstyle{same}} + +\usepackage[autolanguage,np]{numprint} +\AtBeginDocument{% + \renewcommand*\npunitcommand[1]{\text{#1}} + \npthousandthpartsep{}} + +\usepackage{xspace} +\usepackage[textsize=footnotesize]{todonotes} + +%Affichage des figures +%%%\usepackage{caption} +%\usepackage{wrapfig} +\usepackage{subcaption} +\usepackage{graphicx} + +\newcommand{\MI}{\mathit{MaxIter}} + +%Table des matières +\setcounter{secnumdepth}{3} +\setcounter{tocdepth}{3} + +\begin{document} +\begin{spacing}{1.5} + +Page de garde + +Remerciements + +%Table des matières +\tableofcontents + + +Table des figures + +Table des abréviations + + +Résumé (Mots clefs) + +Abstract (Key words) + +Bibliographie et références + +Annexes + + +\part*{INTRODUCTION} +\newpage + +\part*{PARTIE I : Contexte scientifique et revue de l\textquoteright état de l'art} + +\chapter*{Chapitre 1 : Cadre de travail et contexte scientifique} + +\section*{1.1 Classe des algorithmes itératifs parallèles à large échelle dans une grille de calcul} + +Dans le cadre de ces travaux, nous nous sommes intéressés particulièrement +sur la performance d'une classe d'algorithmes +parallèles dits itératifs. De plus en plus, cette méthode itérative +est utilisée pour résoudre des problèmes dans différents domaines +scientifiques tels que la mécanique, la prévision du temps, le traitement +d'images ou encore l'économie financière. +Elle consiste à appliquer, contrairement à la méthode de résolution +« directe », à partir d'une valeur initiale $X_0$ une +transformation à un vecteur inconnu de rang n par des itérations successives +afin de s'approcher par approximation à la solution +recherchée X{*} avec une valeur résiduelle la plus réduite possible. +\begin{equation} +\label{eq:1} + X^{k+1} = \text{f ( } X^k \text{ ), k = 0,1, \dots{} } +\end{equation} + +où chaque $x_k$ est un vecteur à n dimension et f une fonction de $R^n$ vers +$R^n$. + +La solution du problème sera donc le vecteur X{*} tel que X{*} = f +(X{*}), c'est-à-dire X{*} est un point fixe de f. + +L'exécution en parallèle d'un tel algorithme +consiste au découpage (partitionnement) du problème en plus petits +morceaux (ou blocs) et d'assigner chaque bloc à une +unité de calcul. Chaque processeur tourne le même algorithme de façon +concourante jusqu'à la détection de la convergence +locale qui peut être obtenue soit par l'atteinte d'un +nombre maximum fixé d'itérations soit que la différence +entre les valeurs du vecteur inconnu entre deux itérations successives est devenue +inférieure à la valeur résiduelle convenue. Cette condition de convergence +locale peut être écrite comme suit : +\begin{equation*} + (k\leq \MI) \text{ or } (\|X_l^k - X_l^{k+1}\|_{\infty}\leq\epsilon) +\end{equation*} +La convergence globale sera déclarée lorsque tous les processeurs +ont atteint leur convergence locale. De façon générale, plusieurs +travaux ont démontré la convergence de ces méthodes itératives pour +la résolution de systèmes linéaires ou non linéaires avec un taux +de convergence élevé {[}7, 8{]}. Lors de l'exécution +dans chaque bloc de calcul, l'algorithme peut demander l'échange +de données comme des résultats intermédiaires par exemple entre des +processeurs voisins avant d'entamer une nouvelle itération. +Les sections suivantes vont détailler les notions liées à la résolution +de cet algorithme. + +\subsection{Partitionnement du problème} + +Comme expliqué plus haut et appliquant le principe du "diviser pour regner", le problème de résolution d'un +algorithme itératif parallèle commence par un découpage de la matrice $n \times n$ +en entrée en plus petits blocs dont le nombre dépend du nombre +de processeurs disponibles. On parle de « décomposition de domaine +» en considérant les données en priorité en opposition à la « décomposition +fonctionnelle » où le partitionnement se base sur le calcul : diviser +le calcul en des tâches indépendantes assignées aux processeurs. La +figure Figure~\ref{fig:1.a} présente un exemple de découpage en domaines de la +matrice initiale entre deux clusters constitués chacun de 18 processeurs, soit un total de 36 processeurs. +%\begin{figure}[!t] +%%\centering +% \includegraphics[width=60mm,keepaspectratio]{"3D data partitionning btw 2 clusters"} +%\caption{Découpage d'une matrice tridimensionnelle entre deux clusters formés de 18 processeurs %chacun.} +%\label{fig:1.1} +%\end{figure} + +\begin{figure}[h] +\begin{subfigure}{0.5\textwidth} +\includegraphics[width=0.9\linewidth, height=6cm]{"3D data partitionning btw 2 clusters"} +\caption{Découpage d'une matrice tridimensionnelle entre deux clusters formés de 18 processeurs chacun} +\label{fig:1.a} +\end{subfigure} +\begin{subfigure}{0.5\textwidth} +\includegraphics[width=1\linewidth, height=5cm]{"1D-2D-3D Domain decomposition"} +\caption{Décomposition en domaines 1D, 2D et 3D} +\label{fig:1.b} +\end{subfigure} +\caption{Partitionnement du problème} +%\label{fig:1} +\end{figure} + +%\noindent% +%\begin{minipage}{\linewidth}% to keep image and caption on one page +%\makebox[\linewidth]{% to center the image +% \includegraphics[keepaspectratio=true,scale=0.6]{"3D data partitionning btw 2 clusters"}} +%\captionof{figure}{Découpage d'une matrice tridimensionnelle entre deux clusters formés de 18 %processeurs chacun.}\label{fig:1.1} +%\end{minipage} + +%\begin{wrapfigure}{l}{0.3\textwidth} +%\includegraphics[width=0.8\linewidth]{"3D data partitionning btw 2 clusters"} +%\caption{Découpage d'une matrice tridimensionnelle entre deux clusters.} +%\label{fig:1.1} +%\end{wrapfigure} + +Chaque cluster va prendre en charge un bloc de 18 "sous-domaines". Chaque +processeur $P_i$ tournera l'algorithme sur le cube qui +lui est assigné. Les sous domaines s'échangent des +données par leurs points périphériques {[}9{]} au niveau du cluster mais +aussi entre les clusters en suivant une organisation logique d'un +anneau virtuel dont les n½uds sont les processeurs $P_i$. + +Une fois partitionnée en m blocs, la relation reccurente de l'équation \eqref{eq:1} peut +s'écrire : +\begin{equation} +x_{k+1} = (x_1^k, x_2^k, \dots , x_n^k), k=1,\dots n +\end{equation} +ou en termes de blocs : +\begin{equation} +X_{k+1} = (X_1^k, X_2^k, \dots , X_n^k), k=1,\dots m +\end{equation} +Donc, on peut écrire : +\begin{equation*} +X_{k+1} = F (X_k) +\end{equation*} +\begin{equation} +(X_1^{k+1} ,X_2^{k+1} , \dots{}, X_m^{k+1}) = (F_1(X_k), F_2(X_k), \dots , F_m(X_k)) +\end{equation} +Où : +\begin{equation*} +X_i^{k+1} = F_i (X^k) = Fi ( X_1^k , X_2^k , \dots{} , X_m^k)\>pour \>i=1,\dots,k +\end{equation*} +L'exemple donné montre un partitionnement « naturel +» du problème initial par un découpage uniforme avec des blocs de même taille. Il met en exergue deux facteurs importants +à tenir en compte lors de cette opération : +\begin{itemize} +\item [$\bullet$] essayer de répartir +uniformément la charge assignée à chaque processeur : effectivement, +un déséquilibre de charge entre les unités de calcul peut impacter +négativement la performance globale du système; +\item[$\bullet$] réduire au maximum +les communications entre les processeurs : ces temps d'échange +coûtent aussi chers au niveau de la performance globale. +\end{itemize} +Selon le +type de l'algorithme, on peut faire un classement en +trois catégories {[}21{]} selon le partitionnement ou la décomposition +de domaine choisie (Figure~\ref{fig:1.b} ) : +\begin{itemize} +\item[$\bullet$] 1D où la matrice est découpée +suivant des briques dont deux dimensions de longueur n et la dernière plus courte que n. +\item [$\bullet$] 2D avec des briques dont une dimension est de longueur n et les +deux autres plus courtes que n; +\item [$\bullet$] et enfin, 3D avec des briques dont les +3 dimensions sont plus courtes que n. +\end{itemize} + +\subsection{Modes d'exécution synchrone et asynchrone} + +Lors de l'exécution des algorithmes itératifs parallèles +sur un environnement de type grille de calcul, le temps de communication +résultant des échanges de données entre les unités de calcul est aussi +important que le temps de calcul lui-même. En effet, un ratio montrant +un équilibre entre ces deux temps constitue un des objectifs dès le +partitionnement du problème. Le temps de communication est impacté +sur la façon dont les échanges sont effectués. + +\begin{figure}[h] +\begin{subfigure}{0.5\textwidth} +\includegraphics[width=5cm, height=5cm, scale=3]{"Synchronous iterations model"} +\caption{Modèle de communication synchrone} +\label{fig:2.a} +\end{subfigure} +\begin{subfigure}{0.5\textwidth} +\includegraphics[width=5cm, height=5cm, scale=3]{"Asynchronous iterations model"} +\caption{Modèle de communication asynchrone} +\label{fig:2.b} +\end{subfigure} +\caption{Modèles de communication} +%\label{fig:1} +\end{figure} + +D'une part, ces paquets de données peuvent être transférés +de façon « synchrone » : dans ce cas, une coordination de l'échange +est assurée par les deux parties. A la fin de chaque itération, l'émetteur, +une fois la poignée de main établie, envoie les données et attend +jusqu'à la réception d'un accusé de +réception par le récepteur. L'algorithme même est en +mode synchrone parce qu'une étape de synchronisation +de tous les processeurs est nécessaire avant d'entamer +une nouvelle itération. La figure Figure~\ref{fig:2.a} montre les actions dans +le temps lors d'un échange en mode synchrone entre +deux processeurs. Les flèches montrent la date d'envoi +par $P_1$ et la date de réception du paquet par $P_2$. On parle ici de mode +de communication « bloquante » : la nouvelle itération ne peut commencer +tant que tous les processus n'ont pas fini leurs communications. + +D'autre part, l'échange de données peut +s'effectuer en mode « asynchrone ». Dans ce cas, l'émetteur +peut envoyer de l'information au destinataire à tout +moment et aucune synchronisation n'est nécessaire. +Chaque processeur travaille avec les données qu'il +reçoit au fil du temps. La communication est ici non bloquante. La +conséquence immédiate de ce mode de communication est l'absence +des périodes où le traitement est arrêté (CPU stalled ou idle) parce +qu'il doit attendre l'accusé de réception +du récepteur (Figure~\ref{fig:2.b} ). En mode asynchrone, le temps entre chaque +itération peut varier notablement dû à la différence éventuelle de +la puissance de chaque processeur ou encore de la performance des +différents réseaux de communication utilisés. {[}7{]} montre à travers +des algorithmes itératifs classiques les intérêts de la mise en ½uvre +de communication asynchrone lors de la résolution mais aussi les éventuels +inconvénients. Parmi les avantages de ce mode de communication, la +réduction du temps de synchronisation entre processeurs peut impacter +positivement le temps global d'exécution surtout en +environnement hétérogène. De même, le chevauchement du calcul avec +la communication des données peut aussi améliorer la performance de +l'application. Enfin, un partitionnement lors de de +la décomposition du domaine tenant compte de l'absence +de synchronisation en mode asynchrone peut aussi contribuer à la performance +en répartissant efficacement le calcul. Les inconvénients de l'asynchronisme +peuvent venir de la détection de la convergence globale étant donné +qu'il n'y a pas de synchronisation des +opérations. L'arrêt doit être décidé après une forme +de communication globale à un certain point de l'algorithme +; il peut se faire lors de la communication inévitable entre processus +pour annoncer la convergence locale. Un autre problème est aussi la +tolérance aux pannes quoique cette défaillance peut aussi concerner +le mode synchrone : si un des processus contribuant dans la résolution +du problème se plante, tout le processus itératif peut s'écrouler +si un mécanisme de reprise sur panne est mis en place. + +\section*{1.2 Méthodes de résolution parallèles du problème de Poisson et de +l'algorithme two-stage multisplitting de Krylov} + +\subsection{Algorithme de Jacobi} + +\subsection{Méthode de résolution GMRES} + +Native + +Version « two-stage » + +\subsection{Solveur multisplitting} + +Version simple + +Version améliorée + +\section*{1.3 SIMGRID/SMPI : Simulateur d'exécution d'algorithmes +parallèles MPI dans une grille de calcul} + +\subsection{MPI - Message Passing Interface} + +\subsection{Simulateur SIMGRID} + +\section*{1.4 Motivations} + +\section*{1.5 Conclusion partielle} + + +\chapter*{Chapitre 2 : Etat de l'art et travaux de recherche associés} + +\section*{2.1 Concepts et définitions} + +Dans cette section, des concepts et des définitions relatifs à nos +travaux sont passés en revue. + +\subsection{Performance de l'application parallèle et scalabilité} + +La performance d'une application dans un environnement +distribué peut être définie comme « la capacité de réduire le temps +pour résoudre le problème quand les ressources de calcul augmentent +» {[}20{]}. L'objectif est de minimiser le +temps d'exécution globale de l'application +en ajoutant des ressources supplémentaires (processeurs, mémoire, +\dots ). D'où la notion de « scalabilité » ou "montée +en charge" ou encore "passage à l'echelle" dont l'objectif principal est d'accroitre +la performance quand la complexité ou la taille du problème augmentent. +Comme nous allons voir tout au long de ce chapitre, deux catégories +de facteurs concourent à la difficulté de la prédiction des applications +parallèles en considérant leur performance après la montée en charge +des ressources : d'une part, on peut énumérer les facteurs +liés à l'écosystème d'exécution tels +que le nombre de processeurs, la taille de la mémoire et de sous-système +de stockage, la latence et la bande passante des réseaux de communication +; d'autre part, les facteurs liés au code lui-même +impactent aussi la performance de l'application affectant +ainsi la prédiction : il s'agit par exemple de la fréquence +de la communication et de la synchronisation, la faible parallélisation +mais aussi le mauvais ordonnancement des tâches (équilibrage de charge) +{[}20{]}. + +Afin de quantifier la performance d'un code, plusieurs +métriques ont été définies mais le temps d'exécution +global nécessaire pour atteindre la fin du programme reste le plus +simple. On peut écrire : + +\begin{equation} +\label{eq:5} +T_{exec} = T_{calc} + T_{comm} + T_{surcharge} +\end{equation} +où : +\indent\indent$T_{exec}$ : Temps d'exécution global \\ +\indent\indent$T_{calc}$ : Temps de calcul \\ +\indent\indent$T_{comm}$ : Temps de communication \\ +\indent\indent$T_{surcharge}$ : Temps de surcharge. + + +Le temps de calcul représente le temps pris par le code pour effectuer +des calculs tandis que le temps de communication enregistre le temps +des échanges de données ou d'instructions entre les +processeurs. Le temps de surcharge comprend le temps pris lors des +initialisations telles que la création des threads au début du programme +mais aussi le temps de fermeture de l'application à +la fin. En général, le temps de surcharge est négligeable par rapport +aux temps de calcul et de communication. + +Des métriques liées directement à la performance du processeur sont +bien connues telles que le MIPS (Millions d'instructions +par seconde), FLOPS (Floating Point Operations per second), SPECint +ou encore SPECfp qui sont des benchmarks pour évaluer la performance +du processeur sur des opérations arithmétiques respectivement sur +des entiers ou des nombres réels. Par ailleurs, plusieurs métriques +rapportées à la performance de l'application parallèle +ont été définies mais nous allons retenir les trois les plus utilisées, +à savoir le « speedup », « l'efficacité » du code et +la loi d'Amdahl. + +Le speedup est le rapport entre le temps utilisé pour l'exécution +séquentielle du code et le temps pour son exécution en parallèle. +Ce rapport peut être obtenu aussi comme le ratio entre le temps d'exécution +du code sur un processeur et le temps d'exécution avec +n processeurs. Ainsi, il mesure le gain escompté en résolvant le problème +en parallèle au lieu d'un lancement en séquentiel. +\begin{equation} +\label{eq:6} +S(n) = T_{Exec\_Seq} / T_{Exec\_Par}(n) +\end{equation} +où : +\indent\indent S(n) : speedup pour n processeurs \\ +\indent\indent n : nombre de processeurs \\ +\indent\indent $T_{Exec\_Seq}$ le temps d'exécution en mode séquentiel \\ +\indent\indent $T_{Exec\_Par}$ le temps d'exécution en en parallèle. + +L'efficacité E(n) représente la performance de chaque unité +de calcul. Elle s'obtient en divisant le speedup par +le nombre de processeurs n. On peut aussi l'écrire +comme le rapport entre le temps d'exécution séquentielle +et le temps d'exécution parallèle multiplié par le +nombre de processeurs n. +\begin{equation} +\label{eq:7} +E(n) = S(n) / n \\ += T_{Exec\_Seq} / ( n \times T_{Exec\_Par}(n) ) +\end{equation} + +La loi de Amdahl donne une limite du speedup maximum qu'on +peut obtenir avec un nombre de processeurs n donné. Elle stipule que +si f compris entre 0 et 1 est la fraction du temps de la partie séquentielle +du code, on a : + +\begin{equation} +\label{eq:8} +S(n) \leqslant \dfrac{1}{f+ \dfrac{1-f}{n}} +\end{equation} + +Pour un système parallèle « idéal », le speedup est égal à n et l'efficacité +à 1. Dans la pratique, le speedup est toujours inférieur à n avec +une limite haute dûe à la loi de Amdahl et l'efficacité +a une valeur entre 0 et 1. On peut démontrer que l'efficacité +est une fnction décroissante du nombre de processeurs n tandis qu'elle +est une fonction croissante de la taille du problème. + +Dans le cadre de nos travaux, nous avions introduit une métrique utilisée +lors de la comparaison de différentes variantes d'algorithmes +résolvant le même problème exécutés en différents mode de communication +(synchrone ou asynchrone). Ainsi, le « gain relatif » entre l'exécution +de deux variantes de code résolvant un problème donné est le ratio +entre le temps d'exécution global du premier algorithme +et le temps d'exécution global du deuxième algorithme +selon le mode retenu pour chaque code. + +\begin{equation} +\label{eq:9} +G_{relatif} = T_{Exec\_Algo\_1} / T_{Exec\_Algo\_2} \times {100} +\end{equation} + +\subsection{Taux d'erreur lors de la prédiction} + +Lors de l'exercice de prédiction sur la performance +d'une application parallèle, un modèle est construit +à partir des observations passées des +variables considérées (données empiriques observées)afin de pouvoir prédire les résultats (données calculées) pour des nouvelles valeurs de ces variables. L'objectif +lors de cette modélisation est de minimiser l'écart +entre les valeurs calculées théoriques et les valeurs réelles observées. + +Dans le cadre de la classe des algorithmes numériques itératifs consacrée +à ces travaux, un autre taux d'erreur $\epsilon$ est déterminé +d'avance et qui sert à détecter la convergence locale +de l'algorithme {[}9{]}. A chaque itération, la différence +entre la valeur approchée calculée, solution du problème, et celle obtenue +à l'itération précédente est calculeé : si elle est +inférieure au taux d'erreur accepté, l'algorithme +s'arrête en ayant atteint la convergence sinon, on +repart pour une nouvelle itération. + +A l'itération k, la convergence est atteinte quand +: +\begin{equation*} +(\|X_l^k - X_l^{k+1}\|_{\infty}\leq\epsilon) +\end{equation*} + +\subsection{Weak contre strong scaling} + +Un des objectifs de nos travaux consistent à exécuter les algorithmes +choisis en simulant leur exécution sur des plateformes de plus en +plus larges avec un nombre de processeurs et de cores de plus en plus +grand. Deux modes existent pour cette montée en charge donnant des résultats différents + : le « weak » et le « strong » scaling. + +La différence entre ces deux modes repose sur la variation de la taille +du problème lors de la montée en charge (scaling). Pour le « weak +» scaling, on essaie d'observer le comportement du +programme en gardant le même nombre d'éléments à traiter +par processeur ou core. Dans ce cas, les ressources +de calcul additionnelles +va augmenter proportionnellement à la taille du problème en entrée. Ainsi, la problématique ici est de résoudre un problème de plus grande taille. Par ailleurs, le « strong » scaling +essaie de résoudre un problème donné plus vite. Ainsi, dans ce cas, +la taille du problème en entrée reste constante même si on adjoint +une capacité plus grande aux unités de calcul. +\begin{figure}[h] +\centering +\includegraphics[width=100mm,keepaspectratio]{"Weak vs Strong scaling"} +\caption{Weak vs Strong scaling: Temps d'exécution et Speedup} +\label{fig:3} +\end{figure} + +La figure Figure~\ref{fig:3} montre que le temps d'exécution décroit (resp. reste constant) quand le nombre de processeurs augmente en strong mode (resp. en weak mode). De même, le speedup croit avec le nombre de processeur en strong mode tandis qu'il reste constant en weak mode. + +\section*{2.2 Problématique sur la prédiction à large échelle de la performance des applications} + +La prédiction de la performance des applications parallèles à large +échelle constitue ces dernières années une des préoccupations majeures +des scientifiques et des utilisateurs des systèmes de calcul à haute +performance. En effet, en considérant le coût de lancement nécessaire +mais aussi le temps d'exécution imparti pour une telle +application, il est toujours d'intérêt de disposer +d'un outil ou d'un moyen afin de connaître +le comportement de l'application en montant en charge. Pour cela, il s'agit +d'estimer le temps total d'exécution $T_{exec}$ dans ces conditions. De plus, +dans le cadre d'un calcul sur la grille,l'objectif est de +déterminer la configuration idéale, en termes de blocs et +de nombre de noeuds (processeurs, coeurs) par bloc, pour obtenir le +meilleur coût mais aussi le temps optimal d'exécution +de l'application. + +Dans ce chapitre, dans un premier temps, les problématiques et difficultés +inhérentes à cet exercice de prédiction de la performance des applications +parallèles sont abordées. Ensuite, nous allons passer en revue les +solutions possibles apportées à ces problèmes. + +De prime abord, on peut diviser en deux grands groupes, selon leurs +objectifs, les travaux relatifs à la prédiction de la performance +en environnement parallèle et de calcul à haute performance. + +D'une part, la prédiction peut viser l'objectif +de la conception, le développement et la mise au point de systèmes +qui n'existent pas encore physiquement. Cette catégorie +regroupe entre autres la conception de nouvelles architectures de +matériels (CPU, Mémoire, Stockage) {[}\dots {]} mais aussi par exemple, +la mise en oeuvre d'une nouvelle infrastructure de réseaux +de communication {[}\dots {]}. Plusieurs utilisations peuvent être +exploitées pour ce type de prédiction. En effet, outre le calibrage +de systèmes pour une exécution optimale, il permet le débogage et +la mise au point des applications avec un ensemble de contraintes, +que ce soit matérielles ou logicielles {[}..{]}. Notons tout de suite +que cette dernière application sur le réseau a fait l'objet +de nombreux travaux ces dernières années, permettant de déterminer +ou d'estimer d'avance la performance +et l'efficacité de la solution future projetée et éventuellement +de corriger et d'améliorer les imperfections. + +D'autre part, la prédiction de la performance d'une +application parallèle se porte sur la détermination du temps d'exécution +de la dite application en montant en charge sur une large échelle. +Encore une fois, dans ce cas aussi, on ne dispose pas de l'environnement +d'exécution cible mais on essaie de déterminer quel +serait le temps total, donc le coût imputé au lancement de l'application +sous diverses conditions. Ces dernières sont déterminées par plusieurs +facteurs dont les principaux sont les paramètres d'entrée +de l'application tels que la taille du problème à résoudre +mais aussi les caractéristiques et la puissance globale intrinsèque +de la grille de calcul de lancement : nombre de blocs, de processeurs +/ coeurs, les paramètres de la capacité du réseau de communication +inter et intra-noeuds de la grille, \dots{} Ainsi, une telle prédiction +permet de conduire une analyse « what-if » du comportement de l'application +si par exemple, on va multiplier par 10 ou 100 la taille du problème +en entrée, mais aussi si on double la capacité de l'environnement +cible en ajoutant d'autres blocs à la grille ou en +apportant plus de processeurs dans chaque bloc. Les travaux rapportés +dans cette thèse se focalisent plutôt sur cette seconde catégorie +de prédiction de la performance d'applications spécifiquement +écrites en MPI dans un environnement de grille de calcul. + +\subsection*{Facteurs liés à l'écosystème} + +La prédiction de la performance des applications parallèles approchant +le plus possible de la réalité avec un taux d'erreur +minimal dépend de plusieurs facteurs pouvant avoir des impacts +décisifs sur les résultats. En effet, à titre d'exemple, +la modification de la topologie ou des paramètres de l'infrastructure +du réseau de communication tels que la latence ou la taille de la +bande passante aura inévitablement des conséquences sur la performance +globale de l'application parallèle. En donnant un autre +exemple, il est clair que la montée en charge en augmentant la taille +du problème avec une plus grande capacité de calcul proposant un plus +grand nombre de processeurs ou de coeurs modifiera la performance +de l'application. Ainsi, de façon générale, plusieurs +problématiques se posent quant au lancement d'une application +parallèle dans une grille de calcul mais aussi, plusieurs facteurs +influencent directement le comportement et la performance du système. +Nombreux travaux ont déjà proposé des modèles de prédiction à large +échelle sur la performance du code parallèle avec un taux d'efficacité +plus ou moins acceptable. Certains de ces modèles seront détaillés +dans le paragraphe 2.4. + +Les scientifiques et les utilisateurs désirant lancer l'exécution +d'un programme en environnement parallèle ont tous +été confrontés à la même problématique de mise à disponibilité de +l'environnement d'exécution. En effet, +la réservation des ressources nécessaires pour lancer le système n'est +pas toujours immédiate mais en plus, le coût peut ne pas être négligeable +dans un contexte de rareté des machines super puissantes pourtant +très sollicitées par différents acteurs {[}\dots {]}. Cette problématique +peut être parfois accentuée par la non disponibilité de l'infrastructure +cible parce que justement, les résultats obtenus par le lancement +de l'application qui pourra déterminer les caractéristiques +techniques de l'environnement cible. Ainsi, cette contrainte +majeure doit être levée durant tout le cycle de vie de développement +de l'application. En effet, les coûteux développements +et écritures du code de l'application, les opérations +répétitives lors de sa mise au point ainsi que les tests itératifs +de lancement requièrent un environnement réel disposant de la capacité +nécessaire à ces opérations, ce qui n'est pas évident. +Un autre facteur lié à cette problématique a toujours été aussi l'estimation +à l'avance de cette capacité de calcul nécessaire afin +d'avoir un environnement le plus adéquat afin d'éviter +le gaspillage en cas de surestimation ou l'échec d'exécution +en cas de sous-estimation. Cette estimation concerne les ressources +primaires requises telles que le processeur, la taille mémoire DRAM +et cache ainsi que le sous-système de stockage pour la capacité de +calcul d'une part mais aussi les paramètres du réseau +de communication (local ou distant) pour le temps de communication +et d'échange de messages d'autre part. +L'architecture inhérente à la grille de calcul composée +d'entités reliées par des réseaux distants ajoute une +autre considération pour la communication entre les processus parallèles +sur le caractère hétérogène de l'infrastructure que +ce soit la puissance de calcul des serveurs (différents types de processeurs) +que le type des liaisons existants entre les blocs de la grille (réseaux +hétérogènes). En effet, les environnements complexes de type grille +de calcul actuels sont composés généralement de machines physiques +dotées de processeurs multi-coeurs de différentes architectures (niveau +de cache, latence entre processeurs, \dots ). De plus, en analysant +la structure du réseau de communication dans la grille, on peut distinguer +$(1)$ d'abord, les échanges internes au niveau d'un +élément d'un bloc (entre les coeurs d'un +processeur et entre les processeurs d'un même serveur +physique), (2) ensuite, les échanges « intra-blocs » caractérisant +le trafic entre les différents éléments d'un bloc et +(3) enfin, les échanges « inter-blocs » définissant la communication +entre les blocs de la grille. Tant au niveau de leur topologie qu'en +termes d'efficacité, ces trois niveaux de communication +peuvent présenter des caractéristiques complètement différentes et +hétérogènes. Ainsi, les deux premiers réseaux sont implémentés généralement +dans un contexte de réseau local avec un temps de latence très court +et une bande passante large. Tandis que le réseau de liaison entre +les blocs de la grille peuvent être de type distant (lignes spécialisées +distantes, canaux satellites de communication, réseau de type Internet, +\dots ) donc d'une efficacité moindre en termes de +latence et de bande passante mais aussi sujet à des perturbations +diverses (Figure~\ref{fig:4}). Ces aspects liés à l'architecture +de grille de calcul rendent la prédiction de la performance des applications +parallèles plus difficiles. En effet, une surcharge élevée due à des +perturbations sur le réseau inter-blocs de la grille peut fausser +complètement les résultats de la prédiction du temps de communication +global de l'application. + +\subsubsection{Facteur architecture des processeurs} + +Un autre facteur ayant un impact sur le temps d'exécution +global est d'une part, le modèle d'architecture +des processeurs de calcul et d'autre part, la puissance +intrinsèque de ces derniers. + +La course à la puissance nécessaire aux applications de calcul de +haute performance ne cesse de s'accélérer de plus en +plus vite exigeant une capacité de calcul de plus en plus grande. +C. Willard {[}12{]} résume ce phénomène en disant que lorsqu'un +problème - la conception d'un pont par exemple - +est résolu, la solution trouvée n'est plus utile parce +qu'on ne va pas refaire la conception. On passe généralement +à un problème plus complexe - la conception d'un +autre ouvrage plus complexe par exemple. La conséquence de cette course +(actuellement du pentascale vers l'exascale) a suscité +le développement des architectures de processeurs multi-coeurs dont +l'accroissement de la puissance a dépassé la traditionnelle +loi de Moore (renvoi). De plus, des co-processeurs spécialisés et +autres accélérateurs (GPU : Graphic Processing Units {[}{]}) ont été +adjoints aux processeurs multi-coeurs pour améliorer le temps de calcul. +Une autre architecture variante du multi-coeurs est le MIC (Many Integrated +Core) {[}Intel Xeon Phi{]}. Ce type d'unité de calcul +joue au départ le rôle de co-processeur pour les applications à haute +intensité de calcul. Ainsi, plusieurs c½urs ont été pressés au niveau +du processeur (« socket ») emmenant un parallélisme au niveau de la +puce. La Figure~\ref{fig:4} donne un aperçu de l'architecture +d'un processeur multi-coeurs. +\begin{figure}[h] +\centering +\includegraphics[width=100mm,keepaspectratio]{"Architecture des CPU multi-coeurs"} +\caption{Architecture des CPU multicoeurs} +\label{fig:4} +\end{figure} +La performance d'une +telle entité de calcul repose sur la vitesse d'accès +des c½urs aux données en mémoire. En effet, elle est dotée d'un +bus rapide et une hiérarchie de cache mémoire beaucoup plus rapide +d'accès que la RAM. En termes d'architecture, +la classification de Flynn (1972) {[}{]} a créé quatre catégories +de machines parallèles selon les flots de données et les flots d'instructions: SISD (Single instruction, single data), SIMD (Single instruction, +multiple data), MISD et MIMD (Multiple instruction, multiple data). +Cette dernière classe regroupant les machines parallèles généralistes +actuelles se décline en trois sous-catégories : + +\begin{figure}[h] +\begin{subfigure}{0.5\textwidth} +\includegraphics[width=5cm, height=5cm, scale=3]{"MIMD Distributed Memory"} +\caption{Modèle MIMD Distribué} +\label{fig:5.a} +\end{subfigure} +\begin{subfigure}{0.5\textwidth} +\includegraphics[width=5cm, height=5cm, scale=3]{"MIMD Shared memory - SMP"} +\caption{Modèle MIMD partagé} +\label{fig:5.b} +\end{subfigure} +\begin{subfigure}{0.5\textwidth} +\includegraphics[width=5cm, height=5cm, scale=3]{"MIMD Hybride"} +\caption{Modèle MIMD hybride} +\label{fig:5.c} +\end{subfigure} +\caption{Modèles de mémoire MIMD} +%\label{fig:1} +\end{figure} + + +\begin{itemize} + +\item [$\bullet$] - Machine MIMD à mémoire partagée (Figure~\ref{fig:5.b}) : Les unités de calcul +accède à la mémoire partagée via un réseau d'interconnection +(généralement, de type GigabitEthernet (renvoi) ou Infiniband (renvoi)). +Il existe trois types d'implémentation : le crossbar, +le Omega-Network et le Central Databus. + +\item [$\bullet$] Machine MIMD à mémoire distribuée (Figure~\ref{fig:5.a}) : Chaque unité de +calcul est doté de son espace mémoire propre. Un réseau d'interconnexion +intègre l'ensemble assurant la communication entre +ces unités. Il existe trois types de machines MIMD à mémoire distribuée: les hypercubes, les fat trees et les autres. + +\item [$\bullet$] Machine MIMD hybride (Figure~\ref{fig:5.c}) : Dans ce cas, le système est la +combinaison des deux modèles précédents : un ensemble de processeurs +partage un espace mémoire et ces groupes sont interconnectés par un +réseau. + +\end{itemize} + +A titre d'exemple de machines parallèles, le site Top500.org +{[}14{]} classe suivant différents critères les plus performantes. +Ainsi, la fig. .. montre l'évolution de la puissance +de calcul mondiale dont le top actuel développe un pic de performance +théorique proche de 50 PetaFlops (33 Linpack PetaFlops (renvoi)) avec +3.120.000 cores ( 16 noeuds avec des processeurs de 2x12 cores par +n½ud) et plus de 1.240.000 Gb de mémoire (64 Gb par noeud) avec des +accélérateurs 3 $\times$ Intel Xeon Phi par noeud. Il s'agit +de la machine Tianhe-2 (MilkyWay-2) de la National Super Computer +Center à Guangzhou en Chine {[}15{]}. A la tendance actuelle, l'atteinte +de l'exaflops n'est pas loin. + +\begin{figure}[h] +\centering +\includegraphics[width=100mm,keepaspectratio]{"Evolution de la puissance de calcul mondiale"} +\caption{Evolution de la puissance de calcul mondiale} +\label{fig:6} +\end{figure} + +Pour arriver à de telles puissances, diverses architectures de processeurs +ont vu le jour ces dernières années. Outre l'Intel +Xeon Phi cité plus haut, les processeurs basés sur les circuits intégrés +FPGA (Field Programmable Gate Array) montrent une flexibilité efficace +pour s'adapter par configuration au type d'applications +à traiter {[}14{]}. En effet, cette architecture permet la programmation +de la « matrice de blocs logiques » interconnectée par des liaisons +toutes aussi programmables. Cette possibilité de programmation des +circuits et des interconnexions entraine aussi la réduction de la +consommation d'énergie. Par ailleurs, les unités GPU +(Graphics Processing Unit) sont initialement des co-processeurs produits +par AMD et NVIDIA pour des applications à fort rendu graphique, libérant +ainsi la charge au processeur. Par la suite, elles ont été complètement +programmables et se sont montrées très efficaces pour les algorithmes +vectoriels. + +\subsubsection{Facteur : Mémoire et stockage} + +Les différentes architectures de processeurs parallèles vues plus +haut se trouvent toutes confrontées au problème de chargement de données +à traiter en mémoire. Ainsi, elles se sont dotées de contrôleurs de +mémoire incorporés mais aussi divers niveaux de caches pour faire +face à cette différence de vitesse de traitement entre les processeurs +et les mémoires dynamiques. Par exemple, les machines SIMD utilisent +des registres de communication internes pour communiquer avec les +autres CPUs. Pour les machines de type MIMD où différentes tâches +sont exécutées par chaque processeur à un instant donné entraînant +ainsi une synchronisation obligatoire pour des échanges de données +entre processeurs, ces derniers peuvent exploiter la mémoire partagée +pour effectuer ces transferts ou prévoir des bus dédiés à cette fin +{[}16{]}. + +Par ailleurs, les mémoires, non intégrées au processeur, et les sous-systèmes +de stockage constituent aussi un facteur important ayant un impact +sur le temps d'exécution de l'application +parallèle. En effet, les mémoires externes sont utilisées soit pour +échanger des données entre les CPU, soit pour accéder à la zone mémoire +pour lire, écrire ou mettre à jour des données. Dans ce domaine, en +considérant les architectures parallèles MIMD, on peut classer en +deux grandes catégories selon les modèles de mémoire {[}17{]}: (1) +les multiprocesseurs et (2) les multicomputers (Fig \dots ). La première +catégorie regroupe les machines à mémoire partagée (« shared memory +») qui se subdivisent en trois classes selon le mode d'accès +des CPU aux mémoires : (1) UMA ou « Uniform Memory Access » où tous +les CPU accèdent une page mémoire physique de façon « uniforme », +avec le même temps d'accès tolérant ainsi la mise à +l'échelle. Dans ce cas, les CPU sont tous connectés +aux mémoires via un bus ((Figure~\ref{fig:6.b})). Un système d'adressage +global est appliqué à l'ensemble des mémoires physiques. +(2) NUMA ou « Non Uniform Memory Access » où les groupes de CPU accèdent +à des mémoires locales à travers des buses et les groupes sont interconnectés +par un réseau de communication ((Figure~\ref{fig:6.a})). Dans ce cas, le temps +d'accès des CPU aux pages mémoires varie selon que +ces dernières sont locales ou distantes. L'espace d'adressage +des mémoires se fait au niveau de chaque groupe de CPU. (3) L'architecture +COMA (« Cache Only Memory Access ») est un hybride avec un modèle +de programmation de mémoire partagée mais une implémentation physique +de mémoire distribué ((Figure~\ref{fig:6.c})). Dans ce cas, chaque noeud détient +une partie du système de l'espace d'adressage. +Le partitionnement des données étant dynamique, la structure COMA +n'associe pas la même adresse à une page physique de +la mémoire. Les mémoires locales dans ce cas de figure jouent finalement +un rôle de cache au processeur. + +\begin{figure}[h] +\begin{subfigure}{0.5\textwidth} +\includegraphics[width=5cm, height=5cm, scale=3]{"UMA architecture"} +\caption{Architecture UMA} +\label{fig:6.a} +\end{subfigure} +\begin{subfigure}{0.5\textwidth} +\includegraphics[width=5cm, height=5cm, scale=3]{"NUMA architecture"} +\caption{Architecture NUMA} +\label{fig:6.b} +\end{subfigure} +\begin{subfigure}{0.5\textwidth} +\includegraphics[width=5cm, height=5cm, scale=3]{"COMA architecture"} +\caption{Architecture COMA} +\label{fig:6.c} +\end{subfigure} +\caption{Modèles de mémoire MIMD} +%\label{fig:1} +\end{figure} + +Malgré que dans le cadre de nos travaux, nous n'avions +pas eu une contrainte particulière en termes de système de stockage, +une brève revue des problématiques liées à ce sous-système en environnement +de calcul parallèle est présentée parce qu'il peut +influencer à large echelle sur la prédiction de la performance de +l'application. Les systèmes traditionnels ont opté +pour des architectures NFS (Network File System) ou de type NAS (Network +Attached Storage) ou encore de type SAN (Storage Access Network). +Malgré que les systèmes de stockage NFS et NAS sont relativement faciles +à mettre en oeuvre, l'inconvénient majeur est qu'ils +présentent un point de défaillance unique (SPOF) et ont des difficultés +de monter en échelle. Pour le système SAN, les données sont stockées +dans des baies de stockage accessibles par les unités de calcul à +travers un réseau basé sur des canaux de fibres et des adapteurs de +haut débit (HBA) ; ce qui rend le coût de l'implémentation rapidement +excessif dès que le nombre de noeuds augmente. Dans un environnement +d'applications parallèles, le réseau de communication +doit avoir une très haute performance pour répondre aux besoins d'échange +mais aussi d'accès aux données. En plus, il doit +avoir la flexibilité et la capacité de monter en échelle suivant la +demande du système. Ces caractéristiques requis sont accentués par +la variabilité des besoins en entrées/sorties des applications HPC: dans le même lot d'applications exécutées, certaines +accèdent à des données de manière séquentielle tandis que d'autres +demandent des entrées/sorties aléatoires fortement sensibles. Les +solutions apportées dénommées « système de fichiers parallèle » reposent +sur la conception d'une architecture répondant à ces +prérequis. Dans ce type de système de fichiers, les blocs de données +sont répartis par morceaux dans différents serveurs et dans différentes +locations du système de stockage. On peut ainsi accroitre le débit +de stockage et d'extraction au fur et à mesure que +le nombre de serveurs ou de baies de stockage augmentent.L'architecture sera réalisée par: + +\begin{itemize} +\item [$\bullet$] l'introduction d'une couche de « noeuds +de services de fichiers » entre les noeuds de calcul et les baies de +stockage des données. Ces noeuds sont reliés en clusters via un réseau +rapide de type Infiniband. + +\item [$\bullet$] L'ajout des «serveurs de metadata » (MDS : MetaData +Server) qui gèrent les métadonnées accessibles à partir des « baies +de stockage des métadonnées » (MDA) avant d'extraire +les données proprement dites sur les baies de stockage en arrière-plan. +\end{itemize} + +Les métriques utilisées pour caractériser une telle architecture sont +le nombre nominal d'entrées/sorties par seconde (IOPS) +d'une part et le débit de la bande passante du réseau +reliant les différents composants (Gb/s) d'autre part. +Plusieurs solutions globalement efficaces ont été avancées respectant +cette architecture. On peut citer les « systèmes de fichiers ouverts +» tels que pNFS (Parallel NFS), GFS, XFS, PVFS (Clemson University), +MogileFS {[}\dots {]} mais Lustre {[}\dots {]} présenté dans la figure +\dots{} est largement utilisé en environnement de calcul parallèle +: au moins, la moitié des clusters « top 10 » utilise ce modèle et +plusieurs laboratoires l'ont aussi adopté (Pacific +Northwest National Lab (PNNL), Lawrence Livermore National Lab (LLNL) +mais aussi Los Alamos National Lab (LANL). Lustre utilise les OST +(«Object Storage Targets ») dans les serveurs de fichiers (en opposition +au « Block Storage Device ») pour assurer la cohérence et la résilience +du système de fichiers. A titre indicatif, le cluster de PNNL {[}19{]} +avec 1800 processeurs Itanium délivrant jusqu'à 11 +TFlops utilise Lustre avec une capacité de stockage de 53 Toctets +avec une bande passante de 3.2 Gbits/s. Chaque n½ud du cluster peut +accéder au serveur parallèle Lustre avec un débit de 650 Mb/s. + +La mise en ½uvre des systèmes de fichiers parallèles pour les calculs +à haute performance s'approche des technologies utilisées +en entreprise pour exploiter les applications à données intensives +traitant de très grandes masses de données. En effet, les « sciences +de données », « big data », « analytics » (business intelligence, +Datamart, Data Mining) demandent des accès très rapides à des grands +volumes de données variées, structurées ou non structurées, pour en +extraire une information utile. Pour cela, le principe « d'apporter +le calcul auprès des données » (« Bring the compute to the data ») +est appliqué en lieu et place du traditionnel « extraire et charger +en mémoire les données du système de stockage pour traitement par +l'unité de calcul ». Hadoop {[}\dots {]}, une plateforme +de traitement de « big data » la plus utilisée, combine dans la même +machine physique les « n½uds de calcul » et les « n½uds de données +». Cet ensemble d'outils ayant une architecture fortement +distribuée utilise le mécanisme de transfert des données du système +de stockage « globalement partagé et persistent » ayant une large +capacité vers le système de fichier local avant traitement. + +\subsubsection{Facteur : Réseaux de communication} + +Dans un contexte d'exécution parallèle et distribuée +des applications, la communication entre les processus de calcul pour +échange de données ou d'instructions est critique et +peut constituer un goulot d'étranglement pour le temps +d'exécution et la montée en charge de l'applicaiton. +En effet, la performance globale quantifiée par le temps d'exécution +de l'application dépend fortement de la nature et de +la typologie des réseaux de communication. Il a été mis en exergue +dans les paragraphes précédents l'importance du trafic +de données entre chaque unité de calcul et les différentes couches +de mémoire vive utilisées par le système. Dans un environnement de +grilles de calcul, de clusters ou de P2P, d'autres +types de réseaux de communication influencent cette performance. + +%Ethernet, Infiniband (56 à 100 Gb/s), Omni-path {[}15{]} + +%Facteurs influençant le temps de communication : Type de comm (point +%to point, collective comme broadcast, scatter, gather, reduce) + +\subsection{Facteurs liés au code de l'application} + +Outre ces problématiques liées directement à l'environnement +de lancement, plusieurs autres facteurs liés au code de l'application +lors de son exécution peuvent influencer le comportement du système +rendant aussi la prédiction de la performance complexe et difficile. +Ces facteurs liés au comportement du code lors de son exécution en +parallèle vont influencer la performance globale en impactant le temps +de calcul et le temps de communication des données entre les unités +de calcul. + +\subsubsection{Facteur : Taille du problème} + +Parmi les facteurs impactant le temps de calcul, la taille du problème +peut avoir une grande influence sur le temps de calcul surtout en +strong scaling. En effet, dans ce mode de scalabilité, la +taille du problème étant fixe alors qu'on augmente +la puissance de calcul par l'ajout de processeurs et +coeurs supplémentaires, le temps de calcul va varier en fonction de +ces changements. En mode weak scaling où la taille du problème +augmente dans la même proportion que l'accroissement +du nombre de processeurs / coeurs, le temps de calcul global attendu +reste théoriquement plus ou moins constant. La taille du problème +qui ne cesse d'augmenter pour le besoin des applications +parallèles constitue un élément impactant le temps total d'exécution +du code. + +\subsubsection{Performance de la parallélisation} + +Dans cette section, la notion de "performance de la parallélisation" est intrduite pour caractériser la performance d'un code une fois executé en mode parallèle. C. Rosas et Al. {[}\dots {]} +définit cette mesure ($\eta$Parallel) comme étant le produit des trois facteurs fondamentaux "normalisés" suivants dont chaque facteur est quantifié par une valeur entre 0 et 1 : + +\begin{equation} +\label{eq:10} + \eta Parallel =LB \times Ser \times Trf +\end{equation} +Où : + +\begin{itemize} +\item [$\bullet$] L'efficacité de la « répartition des charges » LB ("Load Balancing") est définie comme étant « la perte d'efficacité potentielle» sur le temps de calcul de chaque processus. Elle est mesurée comme +étant le rapport entre le temps de calcul moyen par processeur et +le temps de calcul maximum enregistré sur l'ensemble +des processeurs participants: + +\begin{equation} +\label{eq:11} +LB = {[} \sum \limits_{k=1}^p eff_k) / p {]} / max(eff_k) +\end{equation} +où : p est le nombre de processeurs et $eff_k$ ("Efficiency") le temps de calcul utilisé par le processeur k. + +\item [$\bullet$] L'efficacité de la « sérialisation » : Elle représente +l'inefficacité causée par les « dépendances dans le +code » qui se traduit par la nécessité d'échanger des +données entre les processeurs. Ces dernières peuvent impacter de façon +importante la performance du code parallèle. Ce facteur est mesuré comme étant +le temps maximum enregistré pour tous les processeurs présents lors de l'exécution +du code en faisant abstraction du temps des échanges: on considère comme si on est en présence d'une architecture à « communication instantanée » c'est-à-dire un réseau avec une bande +passante infinie et une latence égale à 0. Dans ce cas, ideal ($eff_i$) est l'efficacité du processeurs i sans le temps de communication. + +\begin{equation} +\label{eq:12} +Ser = max ( ideal( eff_i ) ) +\end{equation} + +\item [$\bullet$] L'efficacité du « transfert » de données : La montée +en charge de la taille du problème impactera la taille des données +à échanger entre les processus. Ce facteur est défini comme étant +la perte de performance globale due aux transferts des données. En +prenant en compte le temps de communication, il est mesuré comme le +ratio entre le maximum entre les temps relatifs d'exécution +des processus concurrents (rapport entre le temps d'exécution $T_i$ +d'un processus et le temps total réel d'exécution T +du code) et l'efficacité de la sérialisation Ser : + +\begin{equation} +\label{eq:12} +Trf = max( T_i/T ) / Ser +\end{equation} + +\end{itemize} + +Les auteurs ont montré que cette mesure de la performance de la parallélisation +est indépendante du temps absolu total d'exécution. +Pour les algorithmes itératifs, cette métrique ne dépend pas du nombre +d'itérations avant l'arrêt de l'algorithme +: le temps d'exécution d'une itération +reste constant. + +Cette quantification de la performance de la parallèlisation du code +repose sur les trois paramètres suivants appelés aussi « inhibiteurs +de la performance » qui décrivent selon {[}12{]} la "sensibilité"{} +du code : (1) la sensibilité à la fréquence CPU, (2) la sensibilité +à la bande passante mémoire et enfin (3) le temps consacré aux communications +et les entrées / sorties. Selon l'algorithme considéré +ou l'aspect scientifique du code, l'application +peut être influencée par ces paramètres. L'analyse +du code par le profiling et l'optimisation pourront +aider à cette sensibilité du code et à améliorer la performance de +sa parallèlisation. + +Dans le cadre de ces travaux, à plus large échelle, c'est-à-dire +en augmentant la taille du problème en entrée comme la capacité de +calcul disponible, les facteurs suivants vont influencer de plus en +plus le temps d'exécution de l'application +impactant ainsi la performance de la parallélisation du code. Selon +{[}18{]}, même si la surcharge engendrée par la parallélisation du +code (« surcharge due à la parallélisation ») ainsi que celle naturellement +subie par le système comme dans une exécution séquentielle (« surcharge +système ») peuvent ne pas être négligeables, on constate +comme précédemment que les facteurs liés à « l'oisivité +» des processeurs ainsi que la communication entre les différentes +couches mémoires (DRAM, cache, « mémoire d'attraction +» (renvoi) ) peuvent peser lourdement à grande échelle sur la performance +globale de l'application. La surcharge due à la parallélisation +provient de l'initialisation par processeur pour une +exécution parallèle (qui n'existe pas lors d'une +exécution séquentielle). Le partitionnement des tâches mais aussi les tâches +de vérrouillage et de déverrouillage lors d'une entrée +et de sortie d'une section critique du code contribue +à l'importance de ce facteur. La surcharge système +comme les défauts de pages, l'interruption horloge, +le mécanisme de fork/join, \dots{} peut être accentuée par rapport +à une exécution séquentielle surtout pour les programmes à haut degré +de parallélisme parce que ces actions sont inhérentes à un processeur +et l'augmentation du nombre de processeurs lors d'une +exécution parallèle peut engendrer une surcharge système non négligeable. +Toutefois, comme avancé plus haut, ces surcharges peuvent ne pas être +significatives comparées au temps perdu suite à l'oisivité +(idle) des blocs de calcul. Cette dernière est surtout due à une parallélisation +insuffisante ou encore par une répartition des charges non optimale. +Enfin, le facteur communication nécessaire pour le thread courant +de chercher des données qui ne sont pas localisées dans ses mémoires +caches locales peut affecter dramatiquement la performance de la parallélisation +du programme. En effet, pendant cette recherche, l'unité +de calcul reste bloqué (stalled). + + +%\section*{Solutions apportées} + + +\section*{2.3 Techniques de profiling et instrumentation des applications parallèles} + + +\section*{2.4 Méthodes de prédiction de la performance de l'application parallèle} + + +\section*{2.5 Conclusion partielle} + +\part*{PARTIE II - Travaux de contributions, résultats et perspectives} + +\chapter*{Chapitre 3 : Comparaison par simulation à large échelle de la performance de deux algorithmes itératifs parallèles en mode asynchrone} + +\section*{3.1 Protocoles et expérimentations} + +\section*{3.2 Résultats} + +\section*{3.3 Conclusion partielle} + +\chapter*{Chapitre 4 : Simulation avec SIMGRID de l\textquoteright exécution des solveurs linéaires en mode synchrone et asynchrone sur un environnement multi-coeurs simulés} + +\section*{4.1 Protocoles et expérimentations} + +\section*{4.2 Résultats} + +\section*{4.3 Conclusion partielle} + +\chapter*{Chapitre 5 : Modèle de prédiction de la performance à large échelle d'un algorithme itératif parallèle} + +\section*{5.1 Approche et méthodologie} + +\section*{5.2 Expérimentations et résultats} + +\section*{5.3 Conclusion partielle} + +\chapter*{Chapitre 6 : Conclusion générale et perspectives} + +\section*{6.1 Conclusion générale} + +\section*{6.2 Travaux futurs et perspectives} + + +\newpage + +\part*{BIBLIOGRAPHIE ET REFERENCES} + +{[}6{]} J.M. BAHI, S. CONTASSOT-VIVIER, R. COUTURIER. Interest of the asynchronism in parallel iterative algorithms on meta-clusters. \textit{LIFC - Université de Belford-Montbéliard}. + +{[}7{]} T.P. COLLIGNON and M.B. van GIJZEN. Fast iterative solution of large sparse linear systems on geographically separated clusters. \textit{The International Journal of High Performance Computing Applications} 25(4) 440\textendash 450. + +{[}8{]} D. BERTSEKAS and J. TSITSIKLIS. Parallel and Distributed Computation, Numerical +Methods. \textit{Prentice Hall Englewood Cliffs N. J., 1989}. + +{[}9{]} C. E. RAMAMONJISOA, L. Z. KHODJAV, D. LAIYMANI, A. Giersch and R. Couturier. Simulation of Asynchronous Iterative Algorithms Using SimGrid. \textit{2014 Femto-ST Institute - DISC Department - Université de Franche-Comté, IUT de Belfort-Montbéliard} + +{[}10{]} M. J. VOSS and R. EIGEMANN. Reducing Parallel Overheads Through Dynamic +Serialization. \textit{Purdue University School of Electrical and Computer Engineering}. + +{[}11{]} K. J. BARKER, K. DAVIS, A. HOISIE, D. J. KERBYSON, M. LANG, S. PAKIN and J. C. SANCHO. Using performance modeling to design large-scale systems. \textit{Los Alamos National Laboratory(LANL), New Mexico}. + +{[}12{]} M. DUBOIS and X. VIGOUROUX. Unleash your HPC performance with Bull. +\textit{Maximizing computing performance while reducing power consumption}. http://www.hpctoday.fr/published/regional/operations/docs/W-HPCperformance-en1.pdf + +{[}14{]} Site du top500. http://www.top500.org + +{[}15{]} C. HARRIS et al. HPC Technology Update. \textit{Pawset Supercomputing Center - Sept 2015}. http://www.pawsey.org.au/wp-content/uploads/2015/09/Pawsey\_HPC\_Technology\_Update\_20150923.pdf + +{[}16{]} A. J. van der STEEN, J. J. DONGARRA. Overview of Recent Supercomputers. +\textit{Academic Computing Centre Utrecht, the Netherlands, Department of Computer Science, University of Tennessee, Knoxville, Mathematical Sciences Section, Oak Ridge, National Laboratory, Oak Ridge}. http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.49.3743\&rep=rep1\&type=pdf + +{[}17{]} V. RAJPUT , S. KUMAR, V.K.PATLE. Performance Analysis of UMA and NUMA Models". +\textit{School of Studies in Computer Science Pt.Ravishankar Shukla University, Raipur,C.G.} http://www.ijcset.net/docs/Volumes/volume2issue10/ijcset2012021006.pdf + +{[}18{]} D. NGUYEN, Raj VASWANI and J. ZAHORIAN. Parallel Application Characterization for +Multiprocessor Scheduling Policy Design. \textit{Department of Computer Science and Engineering - University of Washington, Seattle, USA}. + +{[}19{]} M. EWAN. Exploring Clustered Parallel File Systems and Object Storage. +\textit{2012}. https://software.intel.com/en-us/articles/exploring-clustered-parallel-file-systems-and-object-storage + +{[}20{]} F. SILVA, R. ROCHA: Parallel and Distributed Programming - Performance Metrics. \textit{DCC-FCUP}. + +{[}21{]} G. BALLARD et Al. Communication Optimal Parallel Multiplication +of Sparse Random Matrices". \textit{UC Berkeley, INRIA Paris Rocquencourt, Tel-Aviv University}. http://www.eecs.berkeley.edu/\textasciitilde{}odedsc/papers/spaa13-sparse.pdf + +\end{spacing} +\end{document} diff --git a/These_RCE.toc b/These_RCE.toc new file mode 100644 index 0000000..f55548a --- /dev/null +++ b/These_RCE.toc @@ -0,0 +1,18 @@ +\select@language {french} +\select@language {french} +\contentsline {subsection}{\numberline {0.0.1}Partitionnement du probl\`eme}{7} +\contentsline {subsection}{\numberline {0.0.2}Modes d'ex\'ecution synchrone et asynchrone}{8} +\contentsline {subsection}{\numberline {0.0.3}Algorithme de Jacobi}{9} +\contentsline {subsection}{\numberline {0.0.4}M\'ethode de r\'esolution GMRES}{9} +\contentsline {subsection}{\numberline {0.0.5}Solveur multisplitting}{9} +\contentsline {subsection}{\numberline {0.0.6}MPI - Message Passing Interface}{10} +\contentsline {subsection}{\numberline {0.0.7}Simulateur SIMGRID}{10} +\contentsline {subsection}{\numberline {0.0.8}Performance de l'application parall\`ele et scalabilit\'e}{11} +\contentsline {subsection}{\numberline {0.0.9}Taux d'erreur lors de la pr\'ediction}{13} +\contentsline {subsection}{\numberline {0.0.10}Weak contre strong scaling}{13} +\contentsline {subsubsection}{\numberline {0.0.10.1}Facteur architecture des processeurs}{16} +\contentsline {subsubsection}{\numberline {0.0.10.2}Facteur : M\'emoire et stockage}{18} +\contentsline {subsubsection}{\numberline {0.0.10.3}Facteur : R\'eseaux de communication}{21} +\contentsline {subsection}{\numberline {0.0.11}Facteurs li\'es au code de l'application}{22} +\contentsline {subsubsection}{\numberline {0.0.11.1}Facteur : Taille du probl\`eme}{22} +\contentsline {subsubsection}{\numberline {0.0.11.2}Performance de la parall\'elisation}{22} diff --git a/UMA architecture.pdf b/UMA architecture.pdf new file mode 100644 index 0000000..b003c1e Binary files /dev/null and b/UMA architecture.pdf differ diff --git a/Weak vs Strong scaling.pdf b/Weak vs Strong scaling.pdf new file mode 100644 index 0000000..076fb05 Binary files /dev/null and b/Weak vs Strong scaling.pdf differ