-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 <v3.8l> 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/
\@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.
\@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
\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
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.
(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
\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)
)
********************************************************
\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)
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
\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.
(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
)
-<images/IACA.pdf, id=86, 456.70625pt x 113.42375pt>
+<images/IACA.pdf, id=79, 456.70625pt x 113.42375pt>
File: images/IACA.pdf Graphic file (type pdf)
<use images/IACA.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'.
-
-<images/tig.pdf, id=135, 314.17375pt x 309.155pt>
+ <images/tig.pdf, id=125, 314.17375pt x 309.155pt>
File: images/tig.pdf Graphic file (type pdf)
<use images/tig.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.
[]
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}</usr/local/texlive/2008/texmf-dist/fonts/type1/public/l
-m/lmbx10.pfb></usr/local/texlive/2008/texmf-dist/fonts/type1/public/lm/lmbx12.p
-fb></usr/local/texlive/2008/texmf-dist/fonts/type1/public/lm/lmbx9.pfb></usr/lo
-cal/texlive/2008/texmf-dist/fonts/type1/public/lm/lmbxi10.pfb></usr/local/texli
-ve/2008/texmf-dist/fonts/type1/public/lm/lmcsc10.pfb></usr/local/texlive/2008/t
-exmf-dist/fonts/type1/public/lm/lmex10.pfb></usr/local/texlive/2008/texmf-dist/
-fonts/type1/public/lm/lmmi10.pfb></usr/local/texlive/2008/texmf-dist/fonts/type
-1/public/lm/lmmi5.pfb></usr/local/texlive/2008/texmf-dist/fonts/type1/public/lm
-/lmmi7.pfb></usr/local/texlive/2008/texmf-dist/fonts/type1/public/lm/lmmi8.pfb>
-</usr/local/texlive/2008/texmf-dist/fonts/type1/public/lm/lmr10.pfb></usr/local
-/texlive/2008/texmf-dist/fonts/type1/public/lm/lmr7.pfb></usr/local/texlive/200
-8/texmf-dist/fonts/type1/public/lm/lmr8.pfb></usr/local/texlive/2008/texmf-dist
-/fonts/type1/public/lm/lmr9.pfb></usr/local/texlive/2008/texmf-dist/fonts/type1
-/public/lm/lmri10.pfb></usr/local/texlive/2008/texmf-dist/fonts/type1/public/lm
-/lmri9.pfb></usr/local/texlive/2008/texmf-dist/fonts/type1/public/lm/lmsy10.pfb
-></usr/local/texlive/2008/texmf-dist/fonts/type1/public/lm/lmsy7.pfb>
-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}</usr/share/texmf/fonts/type1/public/lm/lmbx12
+.pfb></usr/share/texmf/fonts/type1/public/lm/lmbx9.pfb></usr/share/texmf/fonts/
+type1/public/lm/lmbxi10.pfb></usr/share/texmf/fonts/type1/public/lm/lmcsc10.pfb
+></usr/share/texmf/fonts/type1/public/lm/lmex10.pfb></usr/share/texmf/fonts/typ
+e1/public/lm/lmmi10.pfb></usr/share/texmf/fonts/type1/public/lm/lmmi5.pfb></usr
+/share/texmf/fonts/type1/public/lm/lmmi7.pfb></usr/share/texmf/fonts/type1/publ
+ic/lm/lmmi8.pfb></usr/share/texmf/fonts/type1/public/lm/lmmi9.pfb></usr/share/t
+exmf/fonts/type1/public/lm/lmr10.pfb></usr/share/texmf/fonts/type1/public/lm/lm
+r7.pfb></usr/share/texmf/fonts/type1/public/lm/lmr8.pfb></usr/share/texmf/fonts
+/type1/public/lm/lmr9.pfb></usr/share/texmf/fonts/type1/public/lm/lmri10.pfb></
+usr/share/texmf/fonts/type1/public/lm/lmri9.pfb></usr/share/texmf/fonts/type1/p
+ublic/lm/lmsy10.pfb></usr/share/texmf/fonts/type1/public/lm/lmsy7.pfb></usr/sha
+re/texmf/fonts/type1/public/lm/lmsy9.pfb>
+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)
\begin{IEEEkeywords}
Mapping algorithms; Distributed clusters; Parallel iterative
-asynchronous algorithms; Heterogeneous distributed architectures
+asynchronous algorithms; Heterogeneous distributed architectures.
\end{IEEEkeywords}
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}
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
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
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
% \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
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.
% 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.
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
% 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
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.
%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
\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
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}
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
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}
%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
% \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
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.
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
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
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}
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!]
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
%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}
-\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
