From: Sébastien Miquée Date: Fri, 22 Jan 2010 14:09:05 +0000 (+0100) Subject: Correction typos et remise en forme. X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/interreg4.git/commitdiff_plain/a4d32c2405b3bac006e911ab9fb20910ffb183c9 Correction typos et remise en forme. --- diff --git a/pdsec2010/pdsec2010.aux b/pdsec2010/pdsec2010.aux index fdb9da9..c255b10 100644 --- a/pdsec2010/pdsec2010.aux +++ b/pdsec2010/pdsec2010.aux @@ -29,13 +29,13 @@ \citation{dag1,dag2,dag3,dag4} \citation{tig1,tig2} \newlabel{sec:benef}{{II}{3}{Benefits of mapping\relax }{section*.1}{}} +\@writefile{lot}{\contentsline {table}{\numberline {I}{\ignorespaces Effects of a simple tasks mapping algorithm on application's execution time}}{3}{table.1}} +\newlabel{tab:benef}{{I}{3}{Effects of a simple tasks mapping algorithm on application's execution time\relax }{table.1}{}} \@writefile{toc}{\contentsline {section}{\numberline {III}Problem description}{3}{section.3}} \newlabel{sec:pb}{{III}{3}{Problem description\relax }{section.3}{}} \@writefile{toc}{\contentsline {subsection}{\numberline {\unhbox \voidb@x \hbox {III-A}}Model formalization}{3}{subsection.3.1}} \newlabel{sec:pbmodel}{{\unhbox \voidb@x \hbox {III-A}}{3}{Model formalization\relax }{subsection.3.1}{}} \newlabel{sec:pbmodelapp}{{\unhbox \voidb@x \hbox {III-A}1}{3}{Application modeling\relax }{subsubsection.3.1.1}{}} -\@writefile{lot}{\contentsline {table}{\numberline {I}{\ignorespaces Effects of a simple tasks mapping algorithm on application's execution time}}{3}{table.1}} -\newlabel{tab:benef}{{I}{3}{Effects of a simple tasks mapping algorithm on application's execution time\relax }{table.1}{}} \@writefile{toc}{\contentsline {subsubsection}{\numberline {\unhbox \voidb@x \hbox {III-A}1}Application modeling}{3}{subsubsection.3.1.1}} \@writefile{lof}{\contentsline {figure}{\numberline {2}{\ignorespaces An example of a TIG of a nine tasks application}}{3}{figure.2}} \newlabel{fig:tig}{{2}{3}{An example of a TIG of a nine tasks application\relax }{figure.2}{}} @@ -77,8 +77,6 @@ \@writefile{toc}{\contentsline {subsubsection}{\numberline {\unhbox \voidb@x \hbox {V-B}2}Edge-cuts optimization}{6}{subsubsection.5.2.2}} \@writefile{toc}{\contentsline {subsection}{\numberline {\unhbox \voidb@x \hbox {V-C}}Experiments}{6}{subsection.5.3}} \newlabel{sec:experiments}{{\unhbox \voidb@x \hbox {V-C}}{6}{Experiments\relax }{subsection.5.3}{}} -\newlabel{sec:xphetero}{{\unhbox \voidb@x \hbox {V-C}1}{6}{About heterogeneity\relax }{subsubsection.5.3.1}{}} -\@writefile{toc}{\contentsline {subsubsection}{\numberline {\unhbox \voidb@x \hbox {V-C}1}About heterogeneity}{6}{subsubsection.5.3.1}} \@writefile{lot}{\contentsline {table}{\numberline {II}{\ignorespaces Gains in time of the execution of the class E of the CG application on Arc1.1 using 64 nodes}}{7}{table.2}} \newlabel{tab:exph1E}{{II}{7}{Gains in time of the execution of the class E of the CG application on Arc1.1 using 64 nodes\relax }{table.2}{}} \@writefile{lot}{\contentsline {table}{\numberline {III}{\ignorespaces Gains in time of the execution of the class F of the CG application on Arc1.2 using 128 nodes}}{7}{table.3}} diff --git a/pdsec2010/pdsec2010.log b/pdsec2010/pdsec2010.log index de2d8c8..af6a623 100644 --- a/pdsec2010/pdsec2010.log +++ b/pdsec2010/pdsec2010.log @@ -1,18 +1,9 @@ -This is pdfTeXk, Version 3.1415926-1.40.9 (Web2C 7.5.7) (format=pdflatex 2009.10.27) 22 JAN 2010 10:58 +This is pdfTeX, Version 3.1415926-1.40.10 (TeX Live 2009/Debian) (format=pdflatex 2010.1.19) 22 JAN 2010 15:08 entering extended mode + restricted \write18 enabled. %&-line parsing enabled. -**pdsec2010 -(./pdsec2010.tex -LaTeX2e <2005/12/01> -Babel and hyphenation patterns for english, usenglishmax, dumylang, noh -yphenation, german-x-2008-06-18, ngerman-x-2008-06-18, ancientgreek, ibycus, ar -abic, basque, bulgarian, catalan, pinyin, coptic, croatian, czech, danish, dutc -h, esperanto, estonian, farsi, finnish, french, galician, german, ngerman, mono -greek, greek, hungarian, icelandic, indonesian, interlingua, irish, italian, la -tin, lithuanian, mongolian, mongolian2a, bokmal, nynorsk, polish, portuguese, r -omanian, russian, sanskrit, serbian, slovak, slovenian, spanish, swedish, turki -sh, ukenglish, ukrainian, uppersorbian, welsh, loaded. -(./IEEEtran.cls +**\input pdsec2010.tex +(./pdsec2010.tex (./IEEEtran.cls Document Class: IEEEtran 2007/03/05 V1.7a by Michael Shell -- See the "IEEEtran_HOWTO" manual for usage information. -- http://www.michaelshell.org/tex/ieeetran/ @@ -23,7 +14,7 @@ Document Class: IEEEtran 2007/03/05 V1.7a by Michael Shell \@IEEEtrantmptoksA=\toks14 LaTeX Font Info: Try loading font information for OT1+ptm on input line 373. -(/usr/local/texlive/2008/texmf-dist/tex/latex/psnfss/ot1ptm.fd +(/usr/share/texmf-texlive/tex/latex/psnfss/ot1ptm.fd File: ot1ptm.fd 2001/06/04 font definitions for OT1/ptm. ) -- Using 8.5in x 11in (letter) paper. @@ -96,22 +87,22 @@ LaTeX Font Info: Font shape `OT1/ptm/bx/it' in size <24> not available \@IEEEtmpitemindent=\dimen116 \c@IEEEbiography=\count90 \@IEEEtranrubishbin=\box26 -) (/usr/local/texlive/2008/texmf-dist/tex/latex/base/fontenc.sty +) (/usr/share/texmf-texlive/tex/latex/base/fontenc.sty Package: fontenc 2005/09/27 v1.99g Standard LaTeX package -(/usr/local/texlive/2008/texmf-dist/tex/latex/base/t1enc.def +(/usr/share/texmf-texlive/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 43. ) LaTeX Font Info: Try loading font information for T1+ptm on input line 100. -(/usr/local/texlive/2008/texmf-dist/tex/latex/psnfss/t1ptm.fd +(/usr/share/texmf-texlive/tex/latex/psnfss/t1ptm.fd File: t1ptm.fd 2001/06/04 font definitions for T1/ptm. )) -(/usr/local/texlive/2008/texmf-dist/tex/latex/ucs/ucs.sty +(/usr/share/texmf-texlive/tex/latex/ucs/ucs.sty Package: ucs 2004/10/17 UCS: Unicode input support -(/usr/local/texlive/2008/texmf-dist/tex/latex/ucs/data/uni-global.def +(/usr/share/texmf-texlive/tex/latex/ucs/data/uni-global.def File: uni-global.def 2004/10/17 UCS: Unicode global data ) \uc@secondtry=\count91 @@ -119,79 +110,79 @@ File: uni-global.def 2004/10/17 UCS: Unicode global data \uc@combtoksb=\toks16 \uc@temptokena=\toks17 ) -(/usr/local/texlive/2008/texmf-dist/tex/latex/base/inputenc.sty -Package: inputenc 2006/05/05 v1.1b Input encoding file +(/usr/share/texmf-texlive/tex/latex/base/inputenc.sty +Package: inputenc 2008/03/30 v1.1d Input encoding file \inpenc@prehook=\toks18 \inpenc@posthook=\toks19 -(/usr/local/texlive/2008/texmf-dist/tex/latex/ucs/utf8x.def +(/usr/share/texmf-texlive/tex/latex/ucs/utf8x.def File: utf8x.def 2004/10/17 UCS: Input encoding UTF-8 )) -(/usr/local/texlive/2008/texmf-dist/tex/latex/lm/lmodern.sty -Package: lmodern 2007/01/14 v1.3 Latin Modern Fonts +(/usr/share/texmf/tex/latex/lm/lmodern.sty +Package: lmodern 2009/10/30 v1.6 Latin Modern Fonts LaTeX Font Info: Overwriting symbol font `operators' in version `normal' -(Font) OT1/cmr/m/n --> OT1/lmr/m/n on input line 13. +(Font) OT1/cmr/m/n --> OT1/lmr/m/n on input line 22. LaTeX Font Info: Overwriting symbol font `letters' in version `normal' -(Font) OML/cmm/m/it --> OML/lmm/m/it on input line 14. +(Font) OML/cmm/m/it --> OML/lmm/m/it on input line 23. LaTeX Font Info: Overwriting symbol font `symbols' in version `normal' -(Font) OMS/cmsy/m/n --> OMS/lmsy/m/n on input line 15. +(Font) OMS/cmsy/m/n --> OMS/lmsy/m/n on input line 24. LaTeX Font Info: Overwriting symbol font `largesymbols' in version `normal' -(Font) OMX/cmex/m/n --> OMX/lmex/m/n on input line 16. +(Font) OMX/cmex/m/n --> OMX/lmex/m/n on input line 25. LaTeX Font Info: Overwriting symbol font `operators' in version `bold' -(Font) OT1/cmr/bx/n --> OT1/lmr/bx/n on input line 17. +(Font) OT1/cmr/bx/n --> OT1/lmr/bx/n on input line 26. LaTeX Font Info: Overwriting symbol font `letters' in version `bold' -(Font) OML/cmm/b/it --> OML/lmm/b/it on input line 18. +(Font) OML/cmm/b/it --> OML/lmm/b/it on input line 27. LaTeX Font Info: Overwriting symbol font `symbols' in version `bold' -(Font) OMS/cmsy/b/n --> OMS/lmsy/b/n on input line 19. +(Font) OMS/cmsy/b/n --> OMS/lmsy/b/n on input line 28. LaTeX Font Info: Overwriting symbol font `largesymbols' in version `bold' -(Font) OMX/cmex/m/n --> OMX/lmex/m/n on input line 20. +(Font) OMX/cmex/m/n --> OMX/lmex/m/n on input line 29. LaTeX Font Info: Overwriting math alphabet `\mathbf' in version `normal' -(Font) OT1/cmr/bx/n --> OT1/lmr/bx/n on input line 22. +(Font) OT1/cmr/bx/n --> OT1/lmr/bx/n on input line 31. LaTeX Font Info: Overwriting math alphabet `\mathsf' in version `normal' -(Font) OT1/cmss/m/n --> OT1/lmss/m/n on input line 23. +(Font) OT1/cmss/m/n --> OT1/lmss/m/n on input line 32. LaTeX Font Info: Overwriting math alphabet `\mathit' in version `normal' -(Font) OT1/cmr/m/it --> OT1/lmr/m/it on input line 24. +(Font) OT1/cmr/m/it --> OT1/lmr/m/it on input line 33. LaTeX Font Info: Overwriting math alphabet `\mathtt' in version `normal' -(Font) OT1/cmtt/m/n --> OT1/lmtt/m/n on input line 25. +(Font) OT1/cmtt/m/n --> OT1/lmtt/m/n on input line 34. LaTeX Font Info: Overwriting math alphabet `\mathbf' in version `bold' -(Font) OT1/cmr/bx/n --> OT1/lmr/bx/n on input line 26. +(Font) OT1/cmr/bx/n --> OT1/lmr/bx/n on input line 35. LaTeX Font Info: Overwriting math alphabet `\mathsf' in version `bold' -(Font) OT1/cmss/bx/n --> OT1/lmss/bx/n on input line 27. +(Font) OT1/cmss/bx/n --> OT1/lmss/bx/n on input line 36. LaTeX Font Info: Overwriting math alphabet `\mathit' in version `bold' -(Font) OT1/cmr/bx/it --> OT1/lmr/bx/it on input line 28. +(Font) OT1/cmr/bx/it --> OT1/lmr/bx/it on input line 37. LaTeX Font Info: Overwriting math alphabet `\mathtt' in version `bold' -(Font) OT1/cmtt/m/n --> OT1/lmtt/m/n on input line 29. +(Font) OT1/cmtt/m/n --> OT1/lmtt/m/n on input line 38. ) -(/usr/local/texlive/2008/texmf-dist/tex/latex/graphics/color.sty +(/usr/share/texmf-texlive/tex/latex/graphics/color.sty Package: color 2005/11/14 v1.0j Standard LaTeX Color (DPC) -(/usr/local/texlive/2008/texmf/tex/latex/config/color.cfg +(/etc/texmf/tex/latex/config/color.cfg File: color.cfg 2007/01/18 v1.5 color configuration of teTeX/TeXLive ) Package color Info: Driver file: pdftex.def on input line 130. -(/usr/local/texlive/2008/texmf-dist/tex/latex/pdftex-def/pdftex.def -File: pdftex.def 2008/09/08 v0.04l Graphics/color for pdfTeX +(/usr/share/texmf-texlive/tex/latex/pdftex-def/pdftex.def +File: pdftex.def 2009/08/25 v0.04m Graphics/color for pdfTeX \Gread@gobject=\count92 )) -(/usr/local/texlive/2008/texmf-dist/tex/latex/amsmath/amsmath.sty +(/usr/share/texmf-texlive/tex/latex/amsmath/amsmath.sty Package: amsmath 2000/07/18 v2.13 AMS math features \@mathmargin=\skip44 For additional information on amsmath, use the `?' option. -(/usr/local/texlive/2008/texmf-dist/tex/latex/amsmath/amstext.sty +(/usr/share/texmf-texlive/tex/latex/amsmath/amstext.sty Package: amstext 2000/06/29 v2.01 -(/usr/local/texlive/2008/texmf-dist/tex/latex/amsmath/amsgen.sty +(/usr/share/texmf-texlive/tex/latex/amsmath/amsgen.sty File: amsgen.sty 1999/11/30 v2.0 \@emptytoks=\toks20 \ex@=\dimen117 )) -(/usr/local/texlive/2008/texmf-dist/tex/latex/amsmath/amsbsy.sty +(/usr/share/texmf-texlive/tex/latex/amsmath/amsbsy.sty Package: amsbsy 1999/11/29 v1.2d \pmbraise@=\dimen118 ) -(/usr/local/texlive/2008/texmf-dist/tex/latex/amsmath/amsopn.sty +(/usr/share/texmf-texlive/tex/latex/amsmath/amsopn.sty Package: amsopn 1999/12/14 v2.01 operator names ) \inf@bad=\count93 @@ -232,81 +223,83 @@ LaTeX Font Info: Redeclaring font encoding OMS on input line 568. LaTeX Info: Redefining \[ on input line 2666. LaTeX Info: Redefining \] on input line 2667. ) -(/usr/local/texlive/2008/texmf-dist/tex/latex/amsfonts/amsfonts.sty -Package: amsfonts 2001/10/25 v2.2f +(/usr/share/texmf-texlive/tex/latex/amsfonts/amsfonts.sty +Package: amsfonts 2009/06/22 v3.00 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 132. +(Font) U/euf/m/n --> U/euf/b/n on input line 96. ) -(/usr/local/texlive/2008/texmf-dist/tex/generic/babel/babel.sty +(/usr/share/texmf-texlive/tex/generic/babel/babel.sty Package: babel 2008/07/06 v3.8l The Babel package -(/usr/local/texlive/2008/texmf-dist/tex/generic/babel/english.ldf +(/usr/share/texmf-texlive/tex/generic/babel/english.ldf Language: english 2005/03/30 v3.3o English support from the babel system -(/usr/local/texlive/2008/texmf-dist/tex/generic/babel/babel.def +(/usr/share/texmf-texlive/tex/generic/babel/babel.def File: babel.def 2008/07/06 v3.8l Babel common definitions \babel@savecnt=\count105 \U@D=\dimen126 ) +\l@british = a dialect from \language\l@english +\l@UKenglish = a dialect from \language\l@english \l@canadian = a dialect from \language\l@american \l@australian = a dialect from \language\l@british \l@newzealand = a dialect from \language\l@british )) -(/usr/local/texlive/2008/texmf-dist/tex/latex/graphics/graphicx.sty +(/usr/share/texmf-texlive/tex/latex/graphics/graphicx.sty Package: graphicx 1999/02/16 v1.0f Enhanced LaTeX Graphics (DPC,SPQR) -(/usr/local/texlive/2008/texmf-dist/tex/latex/graphics/keyval.sty +(/usr/share/texmf-texlive/tex/latex/graphics/keyval.sty Package: keyval 1999/03/16 v1.13 key=value parser (DPC) \KV@toks@=\toks25 ) -(/usr/local/texlive/2008/texmf-dist/tex/latex/graphics/graphics.sty -Package: graphics 2006/02/20 v1.0o Standard LaTeX Graphics (DPC,SPQR) +(/usr/share/texmf-texlive/tex/latex/graphics/graphics.sty +Package: graphics 2009/02/05 v1.0o Standard LaTeX Graphics (DPC,SPQR) -(/usr/local/texlive/2008/texmf-dist/tex/latex/graphics/trig.sty +(/usr/share/texmf-texlive/tex/latex/graphics/trig.sty Package: trig 1999/03/16 v1.09 sin cos tan (DPC) ) -(/usr/local/texlive/2008/texmf/tex/latex/config/graphics.cfg -File: graphics.cfg 2007/01/18 v1.5 graphics configuration of teTeX/TeXLive +(/etc/texmf/tex/latex/config/graphics.cfg +File: graphics.cfg 2009/08/28 v1.8 graphics configuration of TeX Live ) -Package graphics Info: Driver file: pdftex.def on input line 90. +Package graphics Info: Driver file: pdftex.def on input line 91. ) \Gin@req@height=\dimen127 \Gin@req@width=\dimen128 ) -(/usr/local/texlive/2008/texmf-dist/tex/latex/hyperref/hyperref.sty -Package: hyperref 2009/02/22 v6.78p Hypertext links for LaTeX +(/usr/share/texmf-texlive/tex/latex/hyperref/hyperref.sty +Package: hyperref 2009/10/09 v6.79a Hypertext links for LaTeX -(/usr/local/texlive/2008/texmf-dist/tex/generic/oberdiek/ifpdf.sty -Package: ifpdf 2007/12/12 v1.6 Provides the ifpdf switch (HO) +(/usr/share/texmf-texlive/tex/generic/oberdiek/ifpdf.sty +Package: ifpdf 2009/04/10 v2.0 Provides the ifpdf switch (HO) Package ifpdf Info: pdfTeX in pdf mode detected. ) -(/usr/local/texlive/2008/texmf-dist/tex/generic/oberdiek/ifvtex.sty +(/usr/share/texmf-texlive/tex/generic/oberdiek/ifvtex.sty Package: ifvtex 2008/11/04 v1.4 Switches for detecting VTeX and its modes (HO) Package ifvtex Info: VTeX not detected. ) -(/usr/local/texlive/2008/texmf-dist/tex/generic/ifxetex/ifxetex.sty +(/usr/share/texmf-texlive/tex/generic/ifxetex/ifxetex.sty Package: ifxetex 2009/01/23 v0.5 Provides ifxetex conditional ) -(/usr/local/texlive/2008/texmf-dist/tex/latex/oberdiek/hycolor.sty -Package: hycolor 2008/09/08 v1.4 Code for color options of hyperref/bookmark (H +(/usr/share/texmf-texlive/tex/latex/oberdiek/hycolor.sty +Package: hycolor 2009/10/02 v1.5 Code for color options of hyperref/bookmark (H O) -(/usr/local/texlive/2008/texmf-dist/tex/latex/oberdiek/xcolor-patch.sty -Package: xcolor-patch 2008/09/08 xcolor patch +(/usr/share/texmf-texlive/tex/latex/oberdiek/xcolor-patch.sty +Package: xcolor-patch 2009/10/02 xcolor patch )) \@linkdim=\dimen129 \Hy@linkcounter=\count106 \Hy@pagecounter=\count107 -(/usr/local/texlive/2008/texmf-dist/tex/latex/hyperref/pd1enc.def -File: pd1enc.def 2009/02/22 v6.78p Hyperref: PDFDocEncoding definition (HO) +(/usr/share/texmf-texlive/tex/latex/hyperref/pd1enc.def +File: pd1enc.def 2009/10/09 v6.79a Hyperref: PDFDocEncoding definition (HO) ) -(/usr/local/texlive/2008/texmf-dist/tex/generic/oberdiek/etexcmds.sty +(/usr/share/texmf-texlive/tex/generic/oberdiek/etexcmds.sty Package: etexcmds 2007/12/12 v1.2 Prefix for e-TeX command names (HO) -(/usr/local/texlive/2008/texmf-dist/tex/generic/oberdiek/infwarerr.sty +(/usr/share/texmf-texlive/tex/generic/oberdiek/infwarerr.sty Package: infwarerr 2007/09/09 v1.2 Providing info/warning/message (HO) ) Package etexcmds Info: Could not find \expanded. @@ -314,57 +307,68 @@ Package etexcmds Info: Could not find \expanded. (etexcmds) that some package has redefined \expanded. (etexcmds) In the latter case, load this package earlier. ) -(/usr/local/texlive/2008/texmf/tex/latex/config/hyperref.cfg +(/etc/texmf/tex/latex/config/hyperref.cfg File: hyperref.cfg 2002/06/06 v1.2 hyperref configuration of TeXLive ) -(/usr/local/texlive/2008/texmf-dist/tex/latex/oberdiek/kvoptions.sty -Package: kvoptions 2007/10/18 v3.0 Keyval support for LaTeX options (HO) -) -Package hyperref Info: Hyper figures OFF on input line 2935. -Package hyperref Info: Link nesting OFF on input line 2940. -Package hyperref Info: Hyper index ON on input line 2943. -Package hyperref Info: Plain pages OFF on input line 2950. -Package hyperref Info: Backreferencing OFF on input line 2955. +(/usr/share/texmf-texlive/tex/latex/oberdiek/kvoptions.sty +Package: kvoptions 2009/08/13 v3.4 Keyval support for LaTeX options (HO) + +(/usr/share/texmf-texlive/tex/generic/oberdiek/kvsetkeys.sty +Package: kvsetkeys 2009/07/30 v1.5 Key value parser with default handler suppor +t (HO) +)) +Package hyperref Info: Hyper figures OFF on input line 2975. +Package hyperref Info: Link nesting OFF on input line 2980. +Package hyperref Info: Hyper index ON on input line 2983. +Package hyperref Info: Plain pages OFF on input line 2990. +Package hyperref Info: Backreferencing OFF on input line 2995. Implicit mode ON; LaTeX internals redefined -Package hyperref Info: Bookmarks ON on input line 3145. -(/usr/local/texlive/2008/texmf-dist/tex/latex/ltxmisc/url.sty +Package hyperref Info: Bookmarks ON on input line 3191. +(/usr/share/texmf-texlive/tex/latex/ltxmisc/url.sty \Urlmuskip=\muskip11 Package: url 2006/04/12 ver 3.3 Verb mode for urls, etc. ) -LaTeX Info: Redefining \url on input line 3382. +LaTeX Info: Redefining \url on input line 3428. -(/usr/local/texlive/2008/texmf-dist/tex/generic/oberdiek/bitset.sty +(/usr/share/texmf-texlive/tex/generic/oberdiek/bitset.sty Package: bitset 2007/09/28 v1.0 Data type bit set (HO) -(/usr/local/texlive/2008/texmf-dist/tex/generic/oberdiek/intcalc.sty +(/usr/share/texmf-texlive/tex/generic/oberdiek/intcalc.sty Package: intcalc 2007/09/27 v1.1 Expandable integer calculations (HO) ) -(/usr/local/texlive/2008/texmf-dist/tex/generic/oberdiek/bigintcalc.sty +(/usr/share/texmf-texlive/tex/generic/oberdiek/bigintcalc.sty Package: bigintcalc 2007/11/11 v1.1 Expandable big integer calculations (HO) -(/usr/local/texlive/2008/texmf-dist/tex/generic/oberdiek/pdftexcmds.sty -Package: pdftexcmds 2007/12/12 v0.3 LuaTeX support for pdfTeX utility functions +(/usr/share/texmf-texlive/tex/generic/oberdiek/pdftexcmds.sty +Package: pdftexcmds 2009/09/23 v0.6 LuaTeX support for pdfTeX utility functions (HO) -Package pdftexcmds Info: LuaTeX not detected on input line 139. -))) -(/usr/local/texlive/2008/texmf-dist/tex/generic/oberdiek/kvsetkeys.sty -Package: kvsetkeys 2007/09/29 v1.3 Key value parser with default handler suppor -t (HO) + +(/usr/share/texmf-texlive/tex/generic/oberdiek/ifluatex.sty +Package: ifluatex 2009/04/17 v1.2 Provides the ifluatex switch (HO) +Package ifluatex Info: LuaTeX not detected. ) +(/usr/share/texmf-texlive/tex/generic/oberdiek/ltxcmds.sty +Package: ltxcmds 2009/08/05 v1.0 Some LaTeX kernel commands for general use (HO +) +) +Package pdftexcmds Info: LuaTeX not detected. +Package pdftexcmds Info: \pdf@primitive is available. +Package pdftexcmds Info: \pdf@ifprimitive is available. +))) \Fld@menulength=\count108 \Field@Width=\dimen130 \Fld@charsize=\dimen131 \Field@toks=\toks26 -Package hyperref Info: Hyper figures OFF on input line 4299. -Package hyperref Info: Link nesting OFF on input line 4304. -Package hyperref Info: Hyper index ON on input line 4307. -Package hyperref Info: backreferencing OFF on input line 4314. -Package hyperref Info: Link coloring OFF on input line 4319. -Package hyperref Info: Link coloring with OCG OFF on input line 4324. -Package hyperref Info: PDF/A mode OFF on input line 4329. - -(/usr/local/texlive/2008/texmf-dist/tex/generic/oberdiek/atbegshi.sty +Package hyperref Info: Hyper figures OFF on input line 4377. +Package hyperref Info: Link nesting OFF on input line 4382. +Package hyperref Info: Hyper index ON on input line 4385. +Package hyperref Info: backreferencing OFF on input line 4392. +Package hyperref Info: Link coloring OFF on input line 4397. +Package hyperref Info: Link coloring with OCG OFF on input line 4402. +Package hyperref Info: PDF/A mode OFF on input line 4407. + +(/usr/share/texmf-texlive/tex/generic/oberdiek/atbegshi.sty Package: atbegshi 2008/07/31 v1.9 At begin shipout hook (HO) ) \Hy@abspage=\count109 @@ -372,18 +376,18 @@ Package: atbegshi 2008/07/31 v1.9 At begin shipout hook (HO) \c@Hfootnote=\count111 ) *hyperref using default driver hpdftex* -(/usr/local/texlive/2008/texmf-dist/tex/latex/hyperref/hpdftex.def -File: hpdftex.def 2009/02/22 v6.78p Hyperref driver for pdfTeX +(/usr/share/texmf-texlive/tex/latex/hyperref/hpdftex.def +File: hpdftex.def 2009/10/09 v6.79a Hyperref driver for pdfTeX \Fld@listcount=\count112 ) -(/usr/local/texlive/2008/texmf-dist/tex/latex/algorithm2e/algorithm2e.sty +(/usr/share/texmf-texlive/tex/latex/algorithm2e/algorithm2e.sty Package: algorithm2e 2005/10/04 v3.9 algorithms environments \c@AlgoLine=\count113 -(/usr/local/texlive/2008/texmf-dist/tex/latex/base/ifthen.sty +(/usr/share/texmf-texlive/tex/latex/base/ifthen.sty Package: ifthen 2001/05/26 v1.1c Standard LaTeX ifthen package (DPC) ) -(/usr/local/texlive/2008/texmf-dist/tex/latex/tools/xspace.sty +(/usr/share/texmf-texlive/tex/latex/tools/xspace.sty Package: xspace 2006/05/08 v1.12 Space after command names (DPC,MH) ) ******************************************************** @@ -412,10 +416,10 @@ subscribe by emailing sympa@lirmm.fr with 'subscribe ' \c@algocf=\count115 \algocf@algoframe=\box32 \algocf@algobox=\box33 -) (/usr/local/texlive/2008/texmf-dist/tex/latex/cite/cite.sty -LaTeX Info: Redefining \cite on input line 149. -LaTeX Info: Redefining \nocite on input line 214. -Package: cite 2003/11/04 v 4.01 +) (/usr/share/texmf-texlive/tex/latex/cite/cite.sty +LaTeX Info: Redefining \cite on input line 285. +LaTeX Info: Redefining \nocite on input line 356. +Package: cite 2009/08/29 v 5.2 ) ** ATTENTION: Overriding command lockouts (line 84). (./pdsec2010.aux) @@ -436,13 +440,13 @@ LaTeX Font Info: ... okay on input line 87. LaTeX Font Info: Checking defaults for PD1/pdf/m/n on input line 87. LaTeX Font Info: ... okay on input line 87. LaTeX Font Info: Try loading font information for T1+lmr on input line 87. - (/usr/local/texlive/2008/texmf-dist/tex/latex/lm/t1lmr.fd -File: t1lmr.fd 2007/01/14 v1.3 Font defs for Latin Modern + (/usr/share/texmf/tex/latex/lm/t1lmr.fd +File: t1lmr.fd 2009/10/30 v1.6 Font defs for Latin Modern ) -(/usr/local/texlive/2008/texmf-dist/tex/latex/ucs/ucsencs.def +(/usr/share/texmf-texlive/tex/latex/ucs/ucsencs.def File: ucsencs.def 2003/11/29 Fixes to fontencodings LGR, T3 ) -(/usr/local/texlive/2008/texmf-dist/tex/context/base/supp-pdf.tex +(/usr/share/texmf-texlive/tex/context/base/supp-pdf.mkii [Loading MPS to PDF converter (version 2006.09.02).] \scratchcounter=\count116 \scratchdimen=\dimen135 @@ -456,49 +460,48 @@ File: ucsencs.def 2003/11/29 Fixes to fontencodings LGR, T3 \everyMPtoPDFconversion=\toks28 ) Package hyperref Info: Link coloring OFF on input line 87. - (/usr/local/texlive/2008/texmf-dist/tex/latex/hyperref/nameref.sty + (/usr/share/texmf-texlive/tex/latex/hyperref/nameref.sty Package: nameref 2007/05/29 v2.31 Cross-referencing by name of section -(/usr/local/texlive/2008/texmf-dist/tex/latex/oberdiek/refcount.sty +(/usr/share/texmf-texlive/tex/latex/oberdiek/refcount.sty Package: refcount 2008/08/11 v3.1 Data extraction from references (HO) ) \c@section@level=\count121 ) LaTeX Info: Redefining \ref on input line 87. LaTeX Info: Redefining \pageref on input line 87. - -(./pdsec2010.out) (./pdsec2010.out) + (./pdsec2010.out) +(./pdsec2010.out) \@outlinefile=\write3 \openout3 = `pdsec2010.out'. \AtBeginShipoutBox=\box35 - -(/usr/local/texlive/2008/texmf-dist/tex/latex/ucs/data/uni-0.def + (/usr/share/texmf-texlive/tex/latex/ucs/data/uni-0.def File: uni-0.def 2004/10/17 UCS: Unicode data U+0000..U+00FF ) LaTeX Font Info: Try loading font information for OT1+lmr on input line 111. -(/usr/local/texlive/2008/texmf-dist/tex/latex/lm/ot1lmr.fd -File: ot1lmr.fd 2007/01/14 v1.3 Font defs for Latin Modern +(/usr/share/texmf/tex/latex/lm/ot1lmr.fd +File: ot1lmr.fd 2009/10/30 v1.6 Font defs for Latin Modern ) LaTeX Font Info: Try loading font information for OML+lmm on input line 111. -(/usr/local/texlive/2008/texmf-dist/tex/latex/lm/omllmm.fd -File: omllmm.fd 2007/01/14 v1.3 Font defs for Latin Modern +(/usr/share/texmf/tex/latex/lm/omllmm.fd +File: omllmm.fd 2009/10/30 v1.6 Font defs for Latin Modern ) LaTeX Font Info: Try loading font information for OMS+lmsy on input line 111 . -(/usr/local/texlive/2008/texmf-dist/tex/latex/lm/omslmsy.fd -File: omslmsy.fd 2007/01/14 v1.3 Font defs for Latin Modern +(/usr/share/texmf/tex/latex/lm/omslmsy.fd +File: omslmsy.fd 2009/10/30 v1.6 Font defs for Latin Modern ) LaTeX Font Info: Try loading font information for OMX+lmex on input line 111 . -(/usr/local/texlive/2008/texmf-dist/tex/latex/lm/omxlmex.fd -File: omxlmex.fd 2007/01/14 v1.3 Font defs for Latin Modern +(/usr/share/texmf/tex/latex/lm/omxlmex.fd +File: omxlmex.fd 2009/10/30 v1.6 Font defs for Latin Modern ) LaTeX Font Info: External font `lmex10' loaded for size (Font) <9> on input line 111. @@ -508,83 +511,40 @@ LaTeX Font Info: External font `lmex10' loaded for size (Font) <5> on input line 111. LaTeX Font Info: Try loading font information for U+msa on input line 111. -(/usr/local/texlive/2008/texmf-dist/tex/latex/amsfonts/umsa.fd -File: umsa.fd 2002/01/19 v2.2g AMS font definitions +(/usr/share/texmf-texlive/tex/latex/amsfonts/umsa.fd +File: umsa.fd 2009/06/22 v3.00 AMS symbols A ) LaTeX Font Info: Try loading font information for U+msb on input line 111. -(/usr/local/texlive/2008/texmf-dist/tex/latex/amsfonts/umsb.fd -File: umsb.fd 2002/01/19 v2.2g AMS font definitions +(/usr/share/texmf-texlive/tex/latex/amsfonts/umsb.fd +File: umsb.fd 2009/06/22 v3.00 AMS symbols B ) - + File: images/IACA.pdf Graphic file (type pdf) -[1{/usr/local/texlive/2008/texmf-var/fonts/map/pdftex/updmap/pdftex.map} +[1{/var/lib/texmf/fonts/map/pdftex/updmap/pdftex.map} <./images/IACA.pdf>] LaTeX Font Info: External font `lmex10' loaded for size -(Font) <10> on input line 253. +(Font) <10> on input line 252. LaTeX Font Info: External font `lmex10' loaded for size -(Font) <7> on input line 253. - - -LaTeX Warning: Reference `fig:jaceP2P-v2' on page 2 undefined on input line 367 -. +(Font) <7> on input line 252. [2] LaTeX Font Info: External font `lmex10' loaded for size (Font) <8> on input line 480. - - -LaTeX Warning: `!h' float specifier changed to `!ht'. - - + File: images/tig.pdf Graphic file (type pdf) -Underfull \hbox (badness 2027) in paragraph at lines 561--580 -\T1/lmr/m/n/10 be ex-e-cuted si-mul-ta-ne-ously. Tem-po-ral de-pen-den-cies - [] - - -Underfull \hbox (badness 2189) in paragraph at lines 561--580 -\T1/lmr/m/n/10 la-beled with weights de-scrib-ing com-pu-ta-tional and - [] - - -Underfull \hbox (badness 10000) in paragraph at lines 561--580 - - [] - -[3 <./images/tig.pdf>] -Underfull \hbox (badness 10000) in paragraph at lines 604--613 -\T1/lmr/m/n/10 ac-cord-ing as fol-lows. All com-put-ing nodes are - [] - - -Underfull \hbox (badness 3919) in paragraph at lines 604--613 -\T1/lmr/m/n/10 in the same node level. When com-put-ing nodes - [] - - -Underfull \hbox (badness 3568) in paragraph at lines 604--613 -\T1/lmr/m/n/10 can com-mu-ni-cate to one an-other with the same - [] - - -Underfull \hbox (badness 10000) in paragraph at lines 604--613 -\T1/lmr/m/n/10 level and com-mu-ni-cate through the ar-chi-tec-ture - [] - - -Underfull \hbox (badness 10000) in paragraph at lines 604--613 - - [] - -[4] [5] (/usr/local/texlive/2008/texmf-dist/tex/latex/ucs/data/uni-32.def +[3 <./images/tig.pdf>] [4] [5] +(/usr/share/texmf-texlive/tex/latex/ucs/data/uni-32.def File: uni-32.def 2004/10/17 UCS: Unicode data U+2000..U+20FF -) -[6] [7] (./pdsec2010.bbl +) [6] +Underfull \vbox (badness 1946) has occurred while \output is active [] + + [7] +(./pdsec2010.bbl Underfull \hbox (badness 10000) in paragraph at lines 104--106 []\T1/lmr/m/n/9 The NAS Par-al-lel Bench-marks. [] @@ -606,42 +566,34 @@ Before submitting the final camera ready copy, remember to: uses only Type 1 fonts and that every step in the generation process uses the appropriate paper size. -[8] (./pdsec2010.aux) - -LaTeX Warning: There were undefined references. - - ) +[8] (./pdsec2010.aux) ) Here is how much of TeX's memory you used: - 8316 strings out of 493876 - 118397 string characters out of 1150567 - 234275 words of memory out of 3000000 - 11357 multiletter control sequences out of 10000+50000 - 204534 words of font info for 129 fonts, out of 3000000 for 5000 - 714 hyphenation exceptions out of 8191 - 36i,9n,38p,333b,709s stack positions out of 5000i,500n,10000p,200000b,50000s -{/usr/local/texlive/2008/texmf-dist/fonts/enc/dvips/lm/lm-ec.enc}{/usr/local/ -texlive/2008/texmf-dist/fonts/enc/dvips/lm/lm-mathex.enc}{/usr/local/texlive/20 -08/texmf-dist/fonts/enc/dvips/lm/lm-mathit.enc}{/usr/local/texlive/2008/texmf-d -ist/fonts/enc/dvips/lm/lm-rm.enc}{/usr/local/texlive/2008/texmf-dist/fonts/enc/ -dvips/lm/lm-mathsy.enc} - -Output written on pdsec2010.pdf (8 pages, 396493 bytes). + 8406 strings out of 495061 + 118323 string characters out of 1182621 + 234992 words of memory out of 3000000 + 11351 multiletter control sequences out of 15000+50000 + 204526 words of font info for 129 fonts, out of 3000000 for 9000 + 28 hyphenation exceptions out of 8191 + 38i,9n,38p,344b,709s stack positions out of 5000i,500n,10000p,200000b,50000s +{/usr/share/texmf/fonts/enc/dvips/lm/lm-ec.enc}{/usr/sha +re/texmf/fonts/enc/dvips/lm/lm-mathsy.enc}{/usr/share/texmf/fonts/enc/dvips/lm/ +lm-mathit.enc}{/usr/share/texmf/fonts/enc/dvips/lm/lm-mathex.enc}{/usr/share/te +xmf/fonts/enc/dvips/lm/lm-rm.enc} +Output written on pdsec2010.pdf (8 pages, 387637 bytes). PDF statistics: - 304 PDF objects out of 1000 (max. 8388607) - 57 named destinations out of 1000 (max. 131072) - 183 words of extra memory for PDF output out of 10000 (max. 10000000) + 299 PDF objects out of 1000 (max. 8388607) + 56 named destinations out of 1000 (max. 500000) + 163 words of extra memory for PDF output out of 10000 (max. 10000000) diff --git a/pdsec2010/pdsec2010.out b/pdsec2010/pdsec2010.out index 3e5503a..646e83c 100644 --- a/pdsec2010/pdsec2010.out +++ b/pdsec2010/pdsec2010.out @@ -15,6 +15,5 @@ \BOOKMARK [3][-]{subsubsection.5.2.1}{A Simple Mapping algorithm}{subsection.5.2} \BOOKMARK [3][-]{subsubsection.5.2.2}{Edge-cuts optimization}{subsection.5.2} \BOOKMARK [2][-]{subsection.5.3}{Experiments}{section.5} -\BOOKMARK [3][-]{subsubsection.5.3.1}{About heterogeneity}{subsection.5.3} \BOOKMARK [1][-]{section.6}{Conclusion and future works}{} \BOOKMARK [1][-]{section*.2}{References}{} diff --git a/pdsec2010/pdsec2010.pdf b/pdsec2010/pdsec2010.pdf index 1e51d54..c2be623 100644 Binary files a/pdsec2010/pdsec2010.pdf and b/pdsec2010/pdsec2010.pdf differ diff --git a/pdsec2010/pdsec2010.tex b/pdsec2010/pdsec2010.tex index d2bf510..eb27bdf 100644 --- a/pdsec2010/pdsec2010.tex +++ b/pdsec2010/pdsec2010.tex @@ -130,7 +130,7 @@ and the region of Franche-Comté} \begin{IEEEkeywords} Mapping algorithms; Distributed clusters; Parallel iterative -asynchronous algorithms; Heterogeneous distributed architectures +asynchronous algorithms; Heterogeneous distributed architectures. \end{IEEEkeywords} @@ -159,15 +159,15 @@ computation capacity differences between clusters of each site. In order to efficiently use this massive distributed computation power, numerous numerical algorithms have been modified. These algorithms can be broadly classified into two categories. First, -\textit{Direct methods}, which give the exact solution of the problem +\textit{direct methods}, which give the exact solution of the problem using a finite number of operations (e.g. Cholesky, -LU\ldots. These methods cannot be applied to all kinds of -numerical problems. In general, they are not well adapted to very +LU\dots). These methods cannot be applied to all kinds of +numerical problems. Generally, they are not well adapted to very large problems. Then \textit{iterative methods}, that repeat the same instructions until a desired approximation of the solution is reached -- we say that the algorithm has converged. Iterative algorithms constitute the only known approach to solving some kinds of problems -and they are easier to parallelize than direct methods. The Jacobi or +and are easier to parallelize than direct methods. The Jacobi or Conjugate Gradient algorithms are examples of such iterative methods. % \myitemize{5} @@ -182,9 +182,9 @@ methods. In the rest of this paper we only focus on iterative methods. Now to parallelize this kind of algorithm, two classes of parallel iterative -models can be described. In \textit{The synchronous iteration model} +models can be described. In the \textit{synchronous iteration model} after each iteration a node sends its results to its neighbors and -waits for the reception of all dependency messages from its neighbors +waits for the reception of all dependency messages from them to start the next iteration. This results in large idle times and is equivalent to a global synchronization of nodes after each iteration. These synchronizations can strongly penalize the overall @@ -195,15 +195,14 @@ application will be blocked. In the same way, if a machine fails, all the computation will be blocked. \begin{figure}[h!] - \vspace{0.1cm} \centering \includegraphics[width=7.4cm]{images/IACA} \caption{Two processors computing in the Asynchronous Iteration - Asynchronous Communication (AIAC) model} \label{fig:AIAC} \end{figure} +\vspace{-0.2cm} - -In the\textit{The asynchronous iteration model} a node sends its +In the \textit{asynchronous iteration model} a node sends its results to its neighbors and starts immediately the next iteration with the last received data. These data could be data from previous iterations, because the most recent data has not arrived in time or @@ -232,7 +231,7 @@ As we aim to solve very large problems on heterogeneous distributed architectures, in the rest of this study we only focus on the asynchronous iteration model. In order to efficiently use such algorithms on distributed clusters architectures, it is essential to -map the tasks of the application to the best sub-sets of nodes of the +map the application's tasks to the best sub-sets of nodes of the target architecture. This mapping procedure must take into account parameters such as network heterogeneity, computing nodes heterogeneity and tasks heterogeneity in order to minimize the overall @@ -304,8 +303,9 @@ The JaceP2P-V2 architecture, is composed of three main entities: % \label{fig:jaceP2P-v2} % \end{figure} -\myitemize{5} -\item The first entity is the ``super-node'' %(represented by a big +\myitemize{3} +%\begin{itemize} +\item The first entity is the ``super-node''. %(represented by a big %circle in Figure \ref{fig:jaceP2P-v2}). Super-nodes form a circular network and store, in registers, the identifiers of all the computing nodes that are connected to the @@ -331,17 +331,16 @@ The JaceP2P-V2 architecture, is composed of three main entities: of time, it declares that this computing node is dead and deletes its identifier from the register. -\item The second entity is the ``spawner'' +\item The second entity is the ``spawner''. %(represented by a square in % Figure \ref{fig:jaceP2P-v2}). -When a user wants to execute a - parallel application that requires $N$ computing nodes, he or she - launches a spawner. The spawner contacts a super-node to reserve the - $N$ computing nodes plus some extra nodes. When the spawner receives - the list of nodes from the super-node, it transforms the extra - nodes into spawners (for fault tolerance and scalability reasons) - and stores the identifiers of the rest of the nodes in its own - register. + When a user wants to execute a parallel application that requires + $N$ computing nodes, he or she launches a spawner. This one contacts + a super-node to reserve the $N$ computing nodes plus some extra + nodes. When it receives the list of nodes from the super-node, it + transforms the extra nodes into spawners (for fault tolerance and + scalability reasons) and stores the identifiers of the rest of the + nodes in its own register. % Once the extra nodes are transformed into spawners, they % form a circular network and they receive the register containing the % identifiers of the computing nodes. @@ -363,12 +362,13 @@ Then each spawner becomes % of the dead node and continues the computing task from that % checkpoint. -\item The third entity is the ``daemon'', or the computing node, - (represented in Figure \ref{fig:jaceP2P-v2} by a hashed small circle - if it is idle and by a white small circle if it is executing an - application). Once launched, it connects to a super-node and waits - for a task to execute. Once they begin executing an application they - form a circular network which is only used in the failure detection +\item The third entity is the ``daemon'', or the computing node. +% (represented in Figure \ref{fig:jaceP2P-v2} by a hashed small circle +% if it is idle and by a white small circle if it is executing an +% application). + Once launched, it connects to a super-node and waits for a task to + execute. Once they begin executing an application daemons form a + circular network which is only used in the failure detection mechanism. Each daemon can communicate directly with the daemons whose identifiers are in its register. At the end of a task, the daemons reconnect to a super-node. @@ -378,7 +378,7 @@ To be able to execute asynchronous iterative applications, JaceP2P-V2 has an asynchronous messaging mechanism and to resist daemons' failures, it implements a distributed backup mechanism called the uncoordinated distributed checkpointing. For more details on the -JaceP2P-V2 platform, readers can refer to \cite{jaceP2P-v2}. +JaceP2P-V2 platform, interested readers can refer to \cite{jaceP2P-v2}. % This method allows daemons to % save their data on neighboring daemons without any user @@ -398,21 +398,21 @@ JaceP2P-V2 platform, readers can refer to \cite{jaceP2P-v2}. % on distributed architectures. +\vspace*{0.2cm} \subsubsection*{Benefits of mapping} \label{sec:benef} -In the JaceP2P-V2 environment, presented in the previous section, -there is no effective mapping solution. Indeed, when a user wants to -launch an application, the spawner emits a request to the super-node, -which is in charge of available daemons. Basically, the super-node -returns the amount of requested computing nodes by choosing in its own -list. +In the previously described JaceP2P-V2 environment there is no +effective mapping solution. Indeed, when a user wants to launch an +application, the spawner emits a request to the super-node, which is +in charge of available daemons. Basically, the super-node returns the +amount of requested computing nodes by choosing in its own list. %, %if there are sufficient daemons connected on it, or in other %super-nodes lists, in addition of its one. In this method, the super-node only cares about the amount of -requested nodes, it returns in general nodes in the order of their +requested nodes and it returns in general nodes in the order of their connection to the platform -- there is no specific selection. Distributed architectures such as distributed clusters, %as can be seen @@ -454,7 +454,7 @@ efficient to assign tasks communicating with each other on the same cluster, in order to improve communications. But, as we use very large problems, it is quite impossible to find clusters containing as many computing nodes as requested. So we have to dispatch tasks over -several clusters. That implies a nedd to deal with heterogeneity in clusters +several clusters. That implies a need to deal with heterogeneity in clusters computing power and heterogeneity in network. We should make a trade-off between both components in order to take the best part of each one to improve the overall performance. @@ -463,7 +463,7 @@ of each one to improve the overall performance. %benefits of mapping solutions on the applications execution time. In order to check if a tasks mapping algorithm would provide -performance improvement in JaceP2P-V2 environment, we have evaluated +performance improvement in the JaceP2P-V2 environment, we have evaluated the contributions of a simple mapping algorithm, which is described in section \ref{sec:sma}. These experiments used the NPB Kernel CG application described in section \ref{sec:cg}, with two problem sizes @@ -490,6 +490,7 @@ Table \ref{tab:benef}. \caption{Effects of a simple tasks mapping algorithm on application's execution time} \label{tab:benef} + \vspace{-0.5cm} \end{table} As can be seen in Table \ref{tab:benef}, the effects of a @@ -576,8 +577,9 @@ the execution of tasks are not explicitly addressed: all the tasks are considered simultaneously executable and communications can take place at any time during the computation. That is why vertices and edges are labeled with weights -describing computational and communication costs.\\ - +describing computational and communication costs. + +\vspace*{0.2cm} \subsubsection{Architecture modeling} \label{sec:pbmodelarchi} @@ -595,7 +597,7 @@ representing a distributed clusters architecture, where $N = of undirectional edges. The vertices represent the computing nodes and the edges represent the links between them. An edge $L_i \in L$ is an unordered pair $(N_x,N_y) \in N$, representing a communication link -between nodes $x$ and $y$. Let be $|C|$ the number of clusters in the +between nodes $N_x$ and $N_y$. Let be $|C|$ the number of clusters in the architecture containing computing nodes. A function $WN : N \rightarrow R^+$ gives the computational power of nodes and $WL : L \rightarrow R^+$ gives the communication latency of links. We define @@ -609,8 +611,9 @@ addition, like in the Grid'5000 testbed, if computing nodes seemly have the same computational power with a low communication latency, a cluster of these nodes can be defined. All participating clusters, including computing nodes, are in the same architecture level and -communicate through the architecture network.\\ +communicate through the architecture network. +\vspace*{0.2cm} \subsubsection{Mapping functions} \label{sec:pbmodelmapping} @@ -732,15 +735,15 @@ task assignment problem \cite{npcomp}, and is thus NP-complete. %In the previous section we have determined that we need to use TIG %model based mapping algorithms to address our problem. In the literature of the TIG mapping, we can find many algorithms, -which can be divided into two categories. In the \textit{Edge-cuts - optimization} class of algorithms, yhe aim is to minimize the use of the -penalizing links between clusters. As tasks are depending on -neighbors, which are called dependencies, the goal is to choose nodes -where distance, in term of network, is small, to improve -communications between tasks. Here we can cite Metis\cite{metis}, -Chaco\cite{chaco} and PaGrid\cite{pagrid} which are libraries -containing such kind of algorithms. The main drawback of edge-cuts -algorithms is that they do not tackle the computing nodes +which can be divided into two categories. First, in the +\textit{Edge-cuts optimization} class of algorithms, the aim is to +minimize the use of the penalizing links between clusters. As tasks +are depending on neighbors, which are called dependencies, the goal is +to choose nodes where distance, in term of network, is small to +improve communications between tasks. Here we can cite +Metis\cite{metis}, Chaco\cite{chaco} and PaGrid\cite{pagrid} which are +libraries containing such kind of algorithms. The main drawback of +edge-cuts algorithms is that they do not tackle the computing nodes heterogeneity issues. They only focus on communication overheads. % The Figure \ref{fig:edge} shows % that the optimization is on edges of communications, which are @@ -752,10 +755,10 @@ heterogeneity issues. They only focus on communication overheads. % \caption{The edge-cuts optimization} % \label{fig:edge} % \end{figure} -In the \textit{Execution time optimization} class of algorithms the -aim is to minimize the whole execution time of the application. They -look for nodes which can provide the small execution time of tasks -using their computational power. Here we can cite +Then, in the \textit{Execution time optimization} class of algorithms +the aim is to minimize the whole execution time of the +application. They look for nodes which can provide the small execution +time of tasks using their computational power. Here we can cite FastMap\cite{fastmap} and MiniMax\cite{minimax} as such kind of algorithms. QM\cite{qm_these} is also an algorithm of this category, but it aims to find for each task the node which can provide the best @@ -774,11 +777,12 @@ application level The two classes of algorithms may fit with our goals, because in our model we have both the computational power of nodes and communication -costs may influence the applications performance. We can also cite -partitioning tools like Scotch \cite{scotch} which aims at privileging -the load balancing of their partitioning schemes. Nevertheless, to the -best of our knowledge, none of the existing algorithms take into -consideration the specificities of the AIAC model (see next section). +costs which may influence the applications performance. We can also +cite partitioning tools like Scotch \cite{scotch} which aims at +privileging the load balancing of their partitioning +schemes. Nevertheless, to the best of our knowledge, none of the +existing algorithms take into consideration the specificities of the +AIAC model (see next section). %specifically address the AIAC mapping problem. %As the existing mapping algorithms are not designed to fit %with the AIAC mapping problem. @@ -943,7 +947,7 @@ of which their neighbors are mapped on. So, in this algorithm all nodes are first sorted in descending order according to their computation power, and all tasks are mapped on these nodes according to their identifier (they are also marked as -``moveable'', that means that each task can be moved from a node to +``moveable''; it means that each task can be moved from a node to another). As in the original QM algorithm, AIAC QM keeps track of the \textit{number of rounds} $r$ ($r > 0$), that all tasks have been searched for a better node. This allows to reduce at each round the @@ -962,7 +966,7 @@ map the task on nodes that are neighbors of nodes of which the dependencies of $t_i$ are mapped on. This is one of the major modification to the original QM algorithm. It introduces a little part of ``edge-cuts'' optimization. In the original version, it tries to -map the task $t_i$ on the same node of one as its dependencies. As +map the task $t_i$ on the same node of one of its dependencies. As explain in \ref{sec:specAIACmapping}, this is not an acceptable solution in our case. Instead, the algorithm now searches to map task $t_i$ on nodes which are near the ones its dependencies are mapped @@ -980,7 +984,7 @@ considered in this round, $r$ is incremented. The complexity of the AIAC QM algorithm is about $O(n^2 \cdot t \cdot ln(r))$. This complexity is the same as the original algorithm (details are given in \cite{qm_these}, with an increase of a factor -$n$, corresponding to the edge-cuts part. +$n$, corresponding to the edge-cuts part). \section{Experimentation} \label{sec:expe} @@ -1013,11 +1017,11 @@ horizontal rectangle parts. Each of these parts is assigned to a processor -- so the size of data depends on the matrix size but also on the number of participating -nodes. In this way, a processor is in charge of computing its $X Sub$ -part by solving the following subsystem: $ASub \times XSub = BSub - -DepLeft \times XLeft - DepRight \times XRight$ +nodes. In this way, a processor is in charge of computing its {\small $X Sub$} +part by solving the following subsystem: {\small $ASub \times XSub = BSub - +DepLeft \times XLeft - DepRight \times XRight$}. -After solving $XSub$, the result must be sent to other +After solving {\small $XSub$}, the result must be sent to other processors which depend on it. % \begin{figure}[h!] @@ -1059,8 +1063,8 @@ processors which depend on it. For more details about this method, interested readers are invited to see \cite{book_raph}. In our benchmark, the sequential solver part of the multisplitting method is the Conjugate Gradient, using the -MTJ\cite{mtj} library. Its implementation is multi-threaded, so it -benefits from multi-core processors. +MTJ\cite{mtj} library. Its implementation is multi-threaded, to +benefit from multi-core processors. We point out here that this benchmark is a typical AIAC application. In our study, we consider that the computational costs of @@ -1187,6 +1191,8 @@ task is assigned to a particular computing node of the chosen cluster. %on distributed clusters architectures, with a gain over $30\%$ on %execution, as experiments described in section \ref{sec:benef}. +\vspace*{0.2cm} + \subsubsection{Edge-cuts optimization} \label{sec:edgcutalgo} @@ -1354,10 +1360,11 @@ size $5,000,000$ (named ``class F'') using 128 nodes. -\subsubsection{About heterogeneity} -\label{sec:xphetero} +%\subsubsection{About heterogeneity} +%\label{sec:xphetero} -The first experiments concern the study of the impact of the +%The first experiments concern the study of the impact of the +Our experiments concern the study of the impact of the heterogeneity of the computing nodes on the mapping results. Heterogeneity is an important factor in high performance computing in the grid all the more so when using the asynchronous