%!PS-Adobe-2.0 %%Creator: dvips 5.523 Copyright 1986, 1994 Radical Eye Software %%Title: paper.dvi %%CreationDate: Tue Jun 7 15:34:52 1994 %%Pages: 8 %%PageOrder: Ascend %%BoundingBox: 0 0 612 792 %%EndComments %DVIPSCommandLine: dvips2 paper.dvi -o %DVIPSParameters: dpi=300, compressed, comments removed %DVIPSSource: TeX output 1994.06.07:1533 %%BeginProcSet: /home/sampson4/publisher/ps/resolution300.ps %@(#)resolution300.ps 1.4 9/3/92 /SetResolution { /setres where { /setres get exec }{ pop } ifelse } def 300 SetResolution %%EndProcSet %%BeginProcSet: texc.pro /TeXDict 250 dict def TeXDict begin /N{def}def /B{bind def}N /S{exch}N /X{S N}B /TR{translate}N /isls false N /vsize 11 72 mul N /hsize 8.5 72 mul N /landplus90{false}def /@rigin{isls{[0 landplus90{1 -1}{-1 1} ifelse 0 0 0]concat}if 72 Resolution div 72 VResolution div neg scale isls{landplus90{VResolution 72 div vsize mul 0 exch}{Resolution -72 div hsize mul 0}ifelse TR}if Resolution VResolution vsize -72 div 1 add mul TR matrix currentmatrix dup dup 4 get round 4 exch put dup dup 5 get round 5 exch put setmatrix}N /@landscape{/isls true N}B /@manualfeed{ statusdict /manualfeed true put}B /@copies{/#copies X}B /FMat[1 0 0 -1 0 0]N /FBB[0 0 0 0]N /nn 0 N /IE 0 N /ctr 0 N /df-tail{/nn 8 dict N nn begin /FontType 3 N /FontMatrix fntrx N /FontBBox FBB N string /base X array /BitMaps X /BuildChar{CharBuilder}N /Encoding IE N end dup{/foo setfont}2 array copy cvx N load 0 nn put /ctr 0 N[}B /df{/sf 1 N /fntrx FMat N df-tail}B /dfs{div /sf X /fntrx[sf 0 0 sf neg 0 0]N df-tail}B /E{ pop nn dup definefont setfont}B /ch-width{ch-data dup length 5 sub get} B /ch-height{ch-data dup length 4 sub get}B /ch-xoff{128 ch-data dup length 3 sub get sub}B /ch-yoff{ch-data dup length 2 sub get 127 sub}B /ch-dx{ch-data dup length 1 sub get}B /ch-image{ch-data dup type /stringtype ne{ctr get /ctr ctr 1 add N}if}B /id 0 N /rw 0 N /rc 0 N /gp 0 N /cp 0 N /G 0 N /sf 0 N /CharBuilder{save 3 1 roll S dup /base get 2 index get S /BitMaps get S get /ch-data X pop /ctr 0 N ch-dx 0 ch-xoff ch-yoff ch-height sub ch-xoff ch-width add ch-yoff setcachedevice ch-width ch-height true[1 0 0 -1 -.1 ch-xoff sub ch-yoff .1 add]/id ch-image N /rw ch-width 7 add 8 idiv string N /rc 0 N /gp 0 N /cp 0 N{ rc 0 ne{rc 1 sub /rc X rw}{G}ifelse}imagemask restore}B /G{{id gp get /gp gp 1 add N dup 18 mod S 18 idiv pl S get exec}loop}B /adv{cp add /cp X}B /chg{rw cp id gp 4 index getinterval putinterval dup gp add /gp X adv}B /nd{/cp 0 N rw exit}B /lsh{rw cp 2 copy get dup 0 eq{pop 1}{dup 255 eq{pop 254}{dup dup add 255 and S 1 and or}ifelse}ifelse put 1 adv} B /rsh{rw cp 2 copy get dup 0 eq{pop 128}{dup 255 eq{pop 127}{dup 2 idiv S 128 and or}ifelse}ifelse put 1 adv}B /clr{rw cp 2 index string putinterval adv}B /set{rw cp fillstr 0 4 index getinterval putinterval adv}B /fillstr 18 string 0 1 17{2 copy 255 put pop}for N /pl[{adv 1 chg} {adv 1 chg nd}{1 add chg}{1 add chg nd}{adv lsh}{adv lsh nd}{adv rsh}{ adv rsh nd}{1 add adv}{/rc X nd}{1 add set}{1 add clr}{adv 2 chg}{adv 2 chg nd}{pop nd}]dup{bind pop}forall N /D{/cc X dup type /stringtype ne{] }if nn /base get cc ctr put nn /BitMaps get S ctr S sf 1 ne{dup dup length 1 sub dup 2 index S get sf div put}if put /ctr ctr 1 add N}B /I{ cc 1 add D}B /bop{userdict /bop-hook known{bop-hook}if /SI save N @rigin 0 0 moveto /V matrix currentmatrix dup 1 get dup mul exch 0 get dup mul add .99 lt{/QV}{/RV}ifelse load def pop pop}N /eop{SI restore showpage userdict /eop-hook known{eop-hook}if}N /@start{userdict /start-hook known{start-hook}if pop /VResolution X /Resolution X 1000 div /DVImag X /IE 256 array N 0 1 255{IE S 1 string dup 0 3 index put cvn put}for 65781.76 div /vsize X 65781.76 div /hsize X}N /p{show}N /RMat[1 0 0 -1 0 0]N /BDot 260 string N /rulex 0 N /ruley 0 N /v{/ruley X /rulex X V}B /V {}B /RV statusdict begin /product where{pop product dup length 7 ge{0 7 getinterval dup(Display)eq exch 0 4 getinterval(NeXT)eq or}{pop false} ifelse}{false}ifelse end{{gsave TR -.1 -.1 TR 1 1 scale rulex ruley false RMat{BDot}imagemask grestore}}{{gsave TR -.1 -.1 TR rulex ruley scale 1 1 false RMat{BDot}imagemask grestore}}ifelse B /QV{gsave transform round exch round exch itransform moveto rulex 0 rlineto 0 ruley neg rlineto rulex neg 0 rlineto fill grestore}B /a{moveto}B /delta 0 N /tail{dup /delta X 0 rmoveto}B /M{S p delta add tail}B /b{S p tail} B /c{-4 M}B /d{-3 M}B /e{-2 M}B /f{-1 M}B /g{0 M}B /h{1 M}B /i{2 M}B /j{ 3 M}B /k{4 M}B /w{0 rmoveto}B /l{p -4 w}B /m{p -3 w}B /n{p -2 w}B /o{p -1 w}B /q{p 1 w}B /r{p 2 w}B /s{p 3 w}B /t{p 4 w}B /x{0 S rmoveto}B /y{ 3 2 roll p a}B /bos{/SS save N}B /eos{SS restore}B end %%EndProcSet %%BeginProcSet: special.pro TeXDict begin /SDict 200 dict N SDict begin /@SpecialDefaults{/hs 612 N /vs 792 N /ho 0 N /vo 0 N /hsc 1 N /vsc 1 N /ang 0 N /CLIP 0 N /rwiSeen false N /rhiSeen false N /letter{}N /note{}N /a4{}N /legal{}N}B /@scaleunit 100 N /@hscale{@scaleunit div /hsc X}B /@vscale{@scaleunit div /vsc X}B /@hsize{/hs X /CLIP 1 N}B /@vsize{/vs X /CLIP 1 N}B /@clip{ /CLIP 2 N}B /@hoffset{/ho X}B /@voffset{/vo X}B /@angle{/ang X}B /@rwi{ 10 div /rwi X /rwiSeen true N}B /@rhi{10 div /rhi X /rhiSeen true N}B /@llx{/llx X}B /@lly{/lly X}B /@urx{/urx X}B /@ury{/ury X}B /magscale true def end /@MacSetUp{userdict /md known{userdict /md get type /dicttype eq{userdict begin md length 10 add md maxlength ge{/md md dup length 20 add dict copy def}if end md begin /letter{}N /note{}N /legal{} N /od{txpose 1 0 mtx defaultmatrix dtransform S atan/pa X newpath clippath mark{transform{itransform moveto}}{transform{itransform lineto} }{6 -2 roll transform 6 -2 roll transform 6 -2 roll transform{ itransform 6 2 roll itransform 6 2 roll itransform 6 2 roll curveto}}{{ closepath}}pathforall newpath counttomark array astore /gc xdf pop ct 39 0 put 10 fz 0 fs 2 F/|______Courier fnt invertflag{PaintBlack}if}N /txpose{pxs pys scale ppr aload pop por{noflips{pop S neg S TR pop 1 -1 scale}if xflip yflip and{pop S neg S TR 180 rotate 1 -1 scale ppr 3 get ppr 1 get neg sub neg ppr 2 get ppr 0 get neg sub neg TR}if xflip yflip not and{pop S neg S TR pop 180 rotate ppr 3 get ppr 1 get neg sub neg 0 TR}if yflip xflip not and{ppr 1 get neg ppr 0 get neg TR}if}{noflips{TR pop pop 270 rotate 1 -1 scale}if xflip yflip and{TR pop pop 90 rotate 1 -1 scale ppr 3 get ppr 1 get neg sub neg ppr 2 get ppr 0 get neg sub neg TR}if xflip yflip not and{TR pop pop 90 rotate ppr 3 get ppr 1 get neg sub neg 0 TR}if yflip xflip not and{TR pop pop 270 rotate ppr 2 get ppr 0 get neg sub neg 0 S TR}if}ifelse scaleby96{ppr aload pop 4 -1 roll add 2 div 3 1 roll add 2 div 2 copy TR .96 dup scale neg S neg S TR}if}N /cp {pop pop showpage pm restore}N end}if}if}N /normalscale{Resolution 72 div VResolution 72 div neg scale magscale{DVImag dup scale}if 0 setgray} N /psfts{S 65781.76 div N}N /startTexFig{/psf$SavedState save N userdict maxlength dict begin /magscale false def normalscale currentpoint TR /psf$ury psfts /psf$urx psfts /psf$lly psfts /psf$llx psfts /psf$y psfts /psf$x psfts currentpoint /psf$cy X /psf$cx X /psf$sx psf$x psf$urx psf$llx sub div N /psf$sy psf$y psf$ury psf$lly sub div N psf$sx psf$sy scale psf$cx psf$sx div psf$llx sub psf$cy psf$sy div psf$ury sub TR /showpage{}N /erasepage{}N /copypage{}N /p 3 def @MacSetUp}N /doclip{ psf$llx psf$lly psf$urx psf$ury currentpoint 6 2 roll newpath 4 copy 4 2 roll moveto 6 -1 roll S lineto S lineto S lineto closepath clip newpath moveto}N /endTexFig{end psf$SavedState restore}N /@beginspecial{SDict begin /SpecialSave save N gsave normalscale currentpoint TR @SpecialDefaults count /ocount X /dcount countdictstack N}N /@setspecial {CLIP 1 eq{newpath 0 0 moveto hs 0 rlineto 0 vs rlineto hs neg 0 rlineto closepath clip}if ho vo TR hsc vsc scale ang rotate rwiSeen{rwi urx llx sub div rhiSeen{rhi ury lly sub div}{dup}ifelse scale llx neg lly neg TR }{rhiSeen{rhi ury lly sub div dup scale llx neg lly neg TR}if}ifelse CLIP 2 eq{newpath llx lly moveto urx lly lineto urx ury lineto llx ury lineto closepath clip}if /showpage{}N /erasepage{}N /copypage{}N newpath }N /@endspecial{count ocount sub{pop}repeat countdictstack dcount sub{ end}repeat grestore SpecialSave restore end}N /@defspecial{SDict begin} N /@fedspecial{end}B /li{lineto}B /rl{rlineto}B /rc{rcurveto}B /np{ /SaveX currentpoint /SaveY X N 1 setlinecap newpath}N /st{stroke SaveX SaveY moveto}N /fil{fill SaveX SaveY moveto}N /ellipse{/endangle X /startangle X /yrad X /xrad X /savematrix matrix currentmatrix N TR xrad yrad scale 0 0 1 startangle endangle arc savematrix setmatrix}N end %%EndProcSet TeXDict begin 40258431 52099146 1000 300 300 (/tmp_mnt/home/delilah1/payne/iCC/ISUG/paper.dvi) @start /Fa 24 121 df<127012F8A312700505788416>46 DI< 13F8EA03FC487EEA0F07381C3F80EA387FEA78FF3871C3C0A2EAE381A73871C380A23878 FF00EA387EEA1C3C380F03C0EA07FF6C1300EA00FC12197E9816>64 D97 D<127E12FE127E120EA4133E13FF000F1380EB83C0EB 00E0120E1470A614E0EA0F01EB83C0EBFF80000E1300EA063C1419809816>II<133F5B7F1307A4EA03C7EA0FF748B4FCEA3C1F487EEA700712E0A6EA700FA2 EA3C1F381FFFE0380FE7F03807C7E014197F9816>I I<131FEB7F8013FFEA01E7EBC30013C0A2EA7FFFB5FCA2EA01C0ACEA3FFE487E6C5A1119 7F9816>I<3803E3C03807F7E0EA0FFF381C1CC038380E00A56C5AEA0FF8485AEA1BE000 38C7FC1218EA1FFC13FF481380387803C038E000E0A4387001C0EA7C07383FFF80380FFE 00EA03F8131C7F9116>I<127E12FE127E120EA4133C13FEEA0FFFEB87801303120EAA38 7FC7F038FFE7F8387FC7F01519809816>II<13301378A213301300A4EA1FF8A3EA0038B3EA6070 EAF0F0EAFFE0EA7FC0EA3F800D237E9916>I 108 D<38F9C38038FFEFC0EBFFE0EA3C78A2EA3870AA38FE7CF8A2EB3C781512809116> II112 D<38FF0FC0EB3FE0137F3807 F040EBC0005BA290C7FCA8EAFFFCA313127F9116>114 DI<12035AA4EA7FFFB5FCA20007C7FCA75BEB0380A3EB8700EA03FE6C5A6C 5A11177F9616>I<387E1F80EAFE3FEA7E1FEA0E03AB130F380FFFF03807FBF83803E3F0 1512809116>I<387F1FC000FF13E0007F13C0381C0700EA1E0FEA0E0EA36C5AA4EA03B8 A3EA01F0A26C5A13127F9116>I<38FF1FE013BF131F38380380A413E33819F300A213B3 EA1DB7A4EA0F1EA313127F9116>I<387F1FC0133F131F380F1C00EA073CEA03B813F012 016C5A12017FEA03B8EA073C131CEA0E0E387F1FC038FF3FE0387F1FC013127F9116>I E /Fb 2 121 df<126012F0A2126004047D830B>58 D120 D E /Fc 30 117 df<13FCEA0182EA0703EA0607EA0E0290C7FCA5B5FCEA0E07AE387F0F E0131A809915>12 D<1380EA010012025A120C120812185AA35AA412E0AA1260A47EA37E 1208120C12047E7EEA008009267D9B0F>40 D<7E12407E7E12181208120C7EA37EA41380 AA1300A41206A35A1208121812105A5A5A09267E9B0F>I<130CACB61280A2D8000CC7FC AC191A7E951E>43 D<126012F0A2126004047D830B>46 D48 D<12035AB4FC1207B3A2EAFFF00C187D9713>III<1330A2137013F0A2EA0170120312021204120C1208121012301220124012C0B5 FCEA0070A6EA07FF10187F9713>II< EA01E0EA0610EA0C18EA1838123013001270126012E0EAE7C0EAE860EAF030131812E013 1CA31260A2EA701812301330EA1860EA07C00E187E9713>I<1240EA7FFE13FCA2EA4008 EA8010A21320EA0040A213801201A213005AA45AA612020F197E9813>III77 D83 D<007FB5FC38701C0700401301A200C0148000801300A300001400B13803FFE0191A7F99 1C>I97 D<12FC121CA913F8EA1F0EEA1E07381C0380130114C0A6EB03 801400EA1E07EA1B0CEA10F0121A7F9915>II<137E130EA9EA03CEEA0C3EEA380E1230 127012E0A612601270EA381EEA1C2E3807CFC0121A7F9915>II<12FC 121CB3A6EAFF80091A80990A>108 D110 DII114 DI<1204A3120CA2121C123CEAFFC0EA 1C00A81320A5EA0E40EA03800B177F960F>I E /Fd 2 46 df<1302131E137EEA01FE12 0F12FFA2120F1201EA007E131E1302110C7E852A>27 D<7E12F012FCB4FC13E013FEA213 E0130012FC12F012800F0C67852A>45 D E /Fe 2 122 df<38FF0FF0A2381E0700EA0F 06EA078CEA03D813F86C5A1200487E13BCEA031E1207EA0E0F381C078038FE0FF0A21411 7F9017>120 D<38FF03F0A2381E0180A2EA1F03000F13005BEA0786A2EA03CCA2EA01FC 5BA26C5AA21360A2EA70C012F812F95B0073C7FC123C14187F9017>I E /Ff 6 52 df<12021204120812101230122012601240A212C0A81240A2126012201230 1210120812041202071A7F920C>40 D<128012401220121012181208120C1204A21206A8 1204A2120C120812181210122012401280071A7E920C>I<121FEA3180EA60C0EA4040EA C060A8EA4040EA60C0EA3180EA1F000B107F8F0F>48 D<120C123C12CC120CACEAFF8009 107E8F0F>I<121FEA6180EA40C0EA806012C01200A213C0EA0180EA030012065AEA1020 1220EA7FC012FF0B107F8F0F>I<121FEA2180EA60C0A2120013801201EA0F00EA008013 40136012C0A2EA8040EA6080EA1F000B107F8F0F>I E /Fg 1 81 df80 D E /Fh 6 68 df<140C141814381430146014E014C01301EB0380A2EB 0700A2130EA25BA25BA21378137013F0A25B1201A2485AA4485AA3120F90C7FCA35AA212 1EA3123EA4123CA3127CA81278A212F8B1164B748024>48 D<12C01260127012307E121C 120C120E7EA26C7EA26C7EA26C7EA21370A213781338133CA2131C131EA27FA4EB0780A3 14C01303A314E0A21301A314F0A41300A314F8A81478A2147CB1164B7F8024>I<12F8B1 1278A2127CA8123CA3123EA4121EA3121FA27EA37F1207A36C7EA46C7EA212007FA21370 13781338A27FA27FA27FA2EB0380A2EB01C0130014E01460143014381418140C164B7482 24>64 D<147CB11478A214F8A814F0A31301A414E0A31303A214C0A313071480A3EB0F00 A4131EA2131C133CA2133813781370A25BA2485AA2485AA248C7FCA2120E120C121C1218 5A127012605A164B7F8224>I<12F8B3A9051B748024>I<12F8B3A9051B6E8024>I E /Fi 1 1 df0 D E /Fj 4 113 df<1206120712061200A412 38124CA2128C12981218A2123012321262A21264123808147F930C>105 D<1360137013601300A4EA0380EA04C01360EA08C0A21200A2EA0180A4EA0300A4126612 E65A12780C1A81930E>I<123E12065AA45A137013B8EA1938EA3230EA34001238123E12 631310A3EAC320EAC1C00D147E9312>I112 D E /Fk 6 62 df<12011202120412081210123012201260A2124012C0AA12401260A212 20123012101208120412021201081E7E950D>40 D<12801240122012101208120C120412 06A212021203AA12021206A21204120C12081210122012401280081E7E950D>I<120FEA 30C0EA6060A2EA4020EAC030A9EA4020EA6060A2EA30C0EA0F000C137E9211>48 D<120C121C12EC120CAFEAFFC00A137D9211>I<121FEA60C01360EAF07013301260EA00 70A2136013C012011380EA02005AEA08101210EA2020EA7FE012FF0C137E9211>I<387F FFE0B512F0C8FCA6B512F06C13E0140A7E8B19>61 D E /Fl 31 119 df45 D<127812FCA4127806067D850D>I<1360EA01E0120F 12FF12F31203B3A2387FFF80A2111B7D9A18>49 DI66 D<90381FE0209038FFF8E03803F80F3807C003380F800148C7 FC123E1560127E127C00FC1400A8007C1460127E123E15C07E390F8001803907C0030038 03F80E3800FFFCEB1FE01B1C7D9B22>I76 DI79 DI<3807F820381FFEE0EA3C07EA7801EA700012F01460A26C1300 12FEEAFFE0EA7FFE6C7E1480000F13C06C13E0EA007FEB03F01301130012C0A214E07E38 F001C0EAFC0338EFFF00EA83FC141C7D9B1B>83 D<007FB512E0A238781F810070138000 60146000E0147000C01430A400001400B03807FFFEA21C1C7E9B21>I97 DIIII<3803F8F0380E0F38121E381C0730003C 1380A4001C1300EA1E0FEA0E0EEA1BF80010C7FC1218A2EA1FFF14C06C13E04813F03878 01F838F00078A300701370007813F0381E03C03807FF00151B7F9118>103 DI<12 1E123FA4121EC7FCA6B4FCA2121FAEEAFFE0A20B1E7F9D0E>I107 DI<39FF0FC07E903831E18F3A1F40 F20780D980FC13C0A2EB00F8AB3AFFE7FF3FF8A225127F9128>I<38FF0FC0EB31E0381F 40F0EB80F8A21300AB38FFE7FFA218127F911B>II<38FF3F80EBE1E0381F80F0EB0078147C143C143EA6143C147C1478EB80F0EBC1E0EB 3F0090C7FCA6EAFFE0A2171A7F911B>I114 DI<1203A45AA25AA2 EA3FFC12FFEA1F00A9130CA4EA0F08EA0798EA03F00E1A7F9913>I<38FF07F8A2EA1F00 AC1301120F380786FFEA01F818127F911B>I<38FFC1FCA2381F0060EB80E0000F13C013 C03807C180A23803E300A2EA01F6A213FE6C5AA21378A2133016127F9119>I E /Fm 10 122 df<13F0EA030C380E0604EA1C0700381308123000701390A238E003A0A2 14C01480A3EA6007EB1B8838306190380F80E016127E911B>11 DI<126012F0A2126004047C830C>58 D<126012F0A212701210A41220A212401280040C 7C830C>I<1307130FA213061300A61370139CEA010C1202131C12041200A21338A41370 A413E0A4EA01C01261EAF180EAF30012E6127C1024809B11>106 DI110 D<380707803809C8603808D03013E0EA11C014381201A2 38038070A31460380700E014C0EB0180EB8300EA0E86137890C7FCA25AA4123CB47E151A 819115>112 D<380787803808C8403810F0C03820F1E0EBE3C03840E1803800E000A248 5AA43863808012F3EB810012E5EA84C6EA787813127E9118>120 D<001C13C0EA27011247A238870380A2120EA2381C0700A4EA180EA3EA1C1EEA0C3CEA07 DCEA001C1318EA6038EAF0305B485AEA4180003EC7FC121A7E9114>I E /Fn 39 123 df<12181238127812381208A21210A212201240A21280050C7D830D>44 DI<1230127812F0126005047C830D>I<13021306130C131C137C EA039CEA0038A41370A413E0A4EA01C0A4EA0380A41207EAFFF00F1C7C9B15>49 D<130FEB308013C0EA0183120390C7FC1206120E120C121C13F0EA3B18EA3C0C12381278 EA700EA3EA601C12E0A35BA25BEA60605BEA2180001EC7FC111D7B9B15>54 D<3809C0403817E080121F383C6100EA3027EA601AEA40061304EA800C1308EA00181310 13305BA35BA212015B1203A290C7FC5AA3120EA2120C121D799B15>I<131E1361EB8180 EA0180380300C0A238060180A3380703001386EA03CC13F01201EA0378EA063CEA081EEA 180E1230EA6006A3485AA25BEA60105BEA30C0000FC7FC121D7C9B15>I<133C13C6EA01 83EA03031206120E000C1380121C1400A2485AA35B130EEA181EA2EA0C6CEA079CEA001C 1318133813305BEAE0C0A2EA81800086C7FC127C111D7B9B15>I<903803F02090381E0C 6090383002E09038E003C03801C001EA038048C7FC000E1480121E121C123C15005AA35A A41404A35C12705C6C5B00185B6C485AD80706C7FCEA01F81B1E7A9C1E>67 D<3801FFFE39003C078090383801C0A2EC00E0A24913F01570A215F05BA43901C001E0A3 15C0380380031580140715003807000E5C5C5C380E01C0B5C7FC1C1C7D9B1F>I<3801FF C038003C001338A45BA45BA4485AA4485AA448C7FCA45AEAFFE0121C7E9B10>73 DI77 D<3801FFFC38003C079038380380EC01C0A3 EB7003A31580EBE0071500140E14383801FFE001C0C7FCA3485AA448C8FCA45AEAFFE01A 1C7D9B1C>80 D83 D<3AFF83FF0FF03A3C007001C00038158002F013001502EB 01705D13025DEA1C045D13085D13105D13205DEB407192C7FCEB8072121DEB0074121E14 78121C1470121814601210241D779B29>87 D97 D<123F1207A2120EA45AA4EA39C0EA3E60EA3830A2EA7038A4EAE070A3136013E0EAC0C0 12C1EA6180EA6300123C0D1D7B9C13>IIIII<13F3EA01 8FEA030FEA0607EA0E0E120C121CA2EA381CA413381230A2EA187813F0EA0F701200A213 E0A2EAC0C012E1EAC300127E101A7D9113>II< EA01801203EA0100C7FCA7121C12261247A2128EA2120E5AA35AA21271A31272A2123C09 1C7C9B0D>I107 DI<393C 1E078039266318C0394683A0E0384703C0008E1380A2120EA2391C0701C0A3EC0380D838 0E1388A2EC0708151039701C032039300C01C01D127C9122>II< EA01E0EA0718EA0C0C12181238EA300E1270A2EAE01CA31318133813301360EA60C0EA31 80EA1E000F127B9115>II114 DI<13C01201A3EA0380A4EAFFE0EA0700A3120E A45AA4EA3840A31380EA1900120E0B1A7D990E>II<381E01833827038712 47148338870701A2120EA2381C0E02A31404EA180C131C1408001C1310380C26303807C3 C018127C911C>119 DIII E /Fo 1 14 df13 D E /Fp 1 100 df99 D E /Fq 46 122 df<13FF3803C180380783C0EA0F03A2EB0180 90C7FCA2B512C0A2EA0F03AB383F87F0A21417809617>12 D<127012F8A312781208A212 10A212201240050B7D840B>44 DI<127012F8A3127005057D84 0B>I49 DII<131813 38137813F81201EA037812021206120C12181230126012C0B51280A238007800A43807FF 80A211157F9414>III<1260EA7FFFA213FE13FCEAE01812C01330EA006013C01201A2 EA0380A31207A6EA030010167E9514>I57 D67 D69 D<39FFF1FFE0A2390F803E00A8EBFFFEA2EB803E A939FFF1FFE0A21B177E9620>72 DI<39FF F83FE0A2390F800E005C14305CEB81C0EB83800187C7FC138F139FEBBF80EBE7C013C7EB 83E0EB81F0801380147C80143F39FFF8FFE0A21B177E9620>75 D77 D<39FF807FE013C0390FE0060013F0120DEA0CF8137C13 7E133E131FEB0F8614C6EB07E61303EB01F6EB00FEA2147E143E141EA238FFC00E14061B 177E9620>I80 D82 D<3807F080EA1FFDEA380FEA700312 F01301A26CC7FCB47EEA7FF8EA3FFE6C7E00071380EA007FEB0FC01307EAC003A300E013 8038F80F00EADFFEEA87F812177E9617>I<007FB5FCA238783E0F0060130300E0148000 C01301A3000090C7FCAD3807FFF0A219177F961C>I97 D<12FCA2123CA6EA3DFCEA3F07383C038014C0130114E0A514C013031480383B0F00EA31 F813177E9617>IIIIII<12FCA2123CA6137CEA3D8EEA3E0FA2123CA938FF3FC0A2 12177E9617>I<1238127CA312381200A412FCA2123CAB12FFA208187F970B>I<12FCA212 3CB312FFA208177F960B>108 D<39FC7E0FC039FD8730E0393E07C0F0A2003C1380A939 FF1FE3FCA21E0F7E8E23>II< EA07F0EA1C1C487E487EA200F01380A500701300A2EA380E6C5AEA07F0110F7F8E14>I< EAFDFCEAFF0F383C038014C0130114E0A514C01303EB0780383F0F00EA3DF8003CC7FCA4 B4FCA213157E8E17>IIII<1206A3120EA2121EEA3FE012FFEA1E 00A71330A4EA0E20EA07C00C157F9410>II<38FF0FC0A2383C0700EA1E06A26C5AA2EA0798A213F86C5AA26C5AA26C5A12 0F7F8E15>I<39FE3F8FC0A2393C0E0300383E0F07381E1F06A2380F3F8C1333EBB3DC38 07E1D8A2000313F013C0A2380180601A0F7F8E1D>I<38FE1FC0A2381E0C006C5AEA07B8 13F06C5A1201487E1378EA063C120E487E38FC1FC0A2120F7F8E15>I<38FF0FC0A2383C 0300EA1E06A26C5AA2EA0798A2EA03F85BA26C5AA26C5AA21261EAF18012F348C7FC123C 12157F8E15>I E /Fr 1 4 df<120CA2EA8C40EAEDC0EA7F80EA0C00EA7F80EAEDC0EA8C 40EA0C00A20A0B7D8B10>3 D E /Fs 45 122 df<13181378EA01F812FFA21201B3A738 7FFFE0A213207C9F1C>49 DI<13FE3807FFC0380F07E038 1E03F0123FEB81F8A3EA1F0314F0120014E0EB07C0EB1F803801FE007F380007C0EB01F0 14F8EB00FCA2003C13FE127EB4FCA314FCEA7E01007813F8381E07F0380FFFC03801FE00 17207E9F1C>I<14E013011303A21307130F131FA21337137713E7EA01C71387EA030712 07120E120C12181238127012E0B512FEA2380007E0A7EBFFFEA217207E9F1C>I<001013 20381E01E0381FFFC0148014005B13F8EA1BC00018C7FCA4EA19FCEA1FFF381E0FC03818 07E01303000013F0A214F8A21238127C12FEA200FC13F0A2387007E0003013C0381C1F80 380FFF00EA03F815207D9F1C>II<126012 78387FFFFEA214FC14F8A214F038E0006014C038C00180EB0300A2EA00065B131C131813 381378A25BA31201A31203A76C5A17227DA11C>I<13FE3803FFC0380601E0380C00705A 14381238123C123FEB8078EBE070381FF8E0EBFFC06C13806C13C06C13E04813F0381E7F F8383C1FFCEA7807EB01FEEAF000143E141EA2141C7E007813387E381F01F0380FFFC000 01130017207E9F1C>II<1470A214F8A3497E A2497EA3EB06FF80010E7FEB0C3FA201187F141F01387FEB300FA201607F140701E07F90 B5FCA239018001FCA200038090C7FCA20006147FA23AFFE00FFFF8A225227EA12A>65 DIIIII72 DI79 D82 D<3801FC043807FF8C381F03FC383C007C007C133C0078 131CA200F8130CA27E1400B4FC13E06CB4FC14C06C13F06C13F86C13FC000313FEEA003F EB03FFEB007F143FA200C0131FA36C131EA26C133C12FCB413F838C7FFE0008013801822 7DA11F>I<007FB61280A2397E03F80F00781407007014030060140100E015C0A200C014 00A400001500B3A20003B512F8A222227EA127>I87 D97 DII I<13FE3807FF80380F87C0381E01E0003E13F0EA7C0014F812FCA2B5FCA200FCC7FCA312 7CA2127E003E13186C1330380FC0703803FFC0C6130015167E951A>I I<3803FC1E380FFF7F381F0F8F383E07CF383C03C0007C13E0A5003C13C0EA3E07381F0F 80EBFF00EA13FC0030C7FCA21238383FFF806C13F06C13F84813FCEA380048133E00F013 1EA40078133C007C137C383F01F8380FFFE00001130018217E951C>II<121C123F5A A37E121CC7FCA7B4FCA2121FB2EAFFE0A20B247EA310>I107 DI<3AFF07F007 F090391FFC1FFC3A1F303E303E01401340496C487EA201001300AE3BFFE0FFE0FFE0A22B 167E9530>I<38FF07E0EB1FF8381F307CEB403CEB803EA21300AE39FFE1FFC0A21A167E 951F>I<13FE3807FFC0380F83E0381E00F0003E13F848137CA300FC137EA7007C137CA2 6C13F8381F01F0380F83E03807FFC03800FE0017167E951C>I<38FF0FE0EB3FF8381FF0 7CEB803E497E1580A2EC0FC0A8EC1F80A29038803F00EBC03EEBE0FCEB3FF8EB0FC090C8 FCA8EAFFE0A21A207E951F>I114 DI<487EA41203A21207A2120F123FB5FCA2EA0F80ABEB8180A5EB8300EA 07C3EA03FEEA00F811207F9F16>I<38FF01FEA2381F003EAF147E14FE380F81BE3907FF 3FC0EA01FC1A167E951F>I<39FFE01FE0A2390F800600A2EBC00E0007130CEBE01C0003 1318A26C6C5AA26C6C5AA2EB7CC0A2137F6D5AA26DC7FCA2130EA21B167F951E>I<3AFF E7FF07F8A23A1F007800C0D80F80EB0180147CA23A07C07E030014DE01E05B0003EBDF06 EBE18FD801F15B01F3138C9038FB079C000014D8EBFE03017E13F0A2EB7C01013C5BEB38 0001185B25167F9528>I<39FFE07FC0A2390F801C006C6C5A6C6C5AEBF0606C6C5A3800 F980137F6DC7FC7F80497E1337EB63E0EBC1F03801C0F848487E3807007E000E133E39FF 80FFE0A21B167F951E>I<39FFE01FE0A2390F800600A2EBC00E0007130CEBE01C000313 18A26C6C5AA26C6C5AA2EB7CC0A2137F6D5AA26DC7FCA2130EA2130CA25B1278EAFC3813 305BEA69C0EA7F80001FC8FC1B207F951E>I E /Ft 75 124 df11 D<137E3801C180EA0301380703C0120EEB018090C7FCA5B512C0EA0E01B0387F87F8 151D809C17>II<90383F07E03901C09C18380380F0D80701133C000E13E00100131892C7FCA5B612 FC390E00E01CB03A7FC7FCFF80211D809C23>I<126012F012F812681208A31210A21220 12401280050C7C9C0C>39 D<13401380EA0100120212065AA25AA25AA212701260A312E0 AC1260A312701230A27EA27EA27E12027EEA008013400A2A7D9E10>I<7E12407E7E1218 7EA27EA27EA213801201A313C0AC1380A312031300A21206A25AA25A12105A5A5A0A2A7E 9E10>I<1306ADB612E0A2D80006C7FCAD1B1C7E9720>43 D<126012F0A212701210A412 20A212401280040C7C830C>II<126012F0A2126004047C830C> I<130113031306A3130CA31318A31330A31360A213C0A3EA0180A3EA0300A31206A25AA3 5AA35AA35AA35AA210297E9E15>II<12035A123F12 C71207B3A4EA0F80EAFFF80D1C7C9B15>III<130CA2131C133CA2135C13DC139CEA011C1203120212 04120C1208121012301220124012C0B512C038001C00A73801FFC0121C7F9B15>II<13F0EA030CEA0604EA0C0E EA181E1230130CEA7000A21260EAE3E0EAE430EAE818EAF00C130EEAE0061307A51260A2 EA7006EA300E130CEA1818EA0C30EA03E0101D7E9B15>I<1240387FFF801400A2EA4002 485AA25B485AA25B1360134013C0A212015BA21203A41207A66CC7FC111D7E9B15>I I I<126012F0A212601200AA126012F0A2126004127C910C>I<126012F0A212601200AA12 6012F0A212701210A41220A212401280041A7C910C>I<007FB512C0B612E0C9FCA8B612 E06C14C01B0C7E8F20>61 D<1306A3130FA3EB1780A3EB23C0A3EB41E0A3EB80F0A20001 7FEB0078EBFFF83803007C0002133CA20006133E0004131EA2000C131F121E39FF80FFF0 1C1D7F9C1F>65 DI<90381F8080EBE0 613801801938070007000E13035A14015A00781300A2127000F01400A8007014801278A2 12386CEB0100A26C13026C5B380180083800E030EB1FC0191E7E9C1E>III I<90381F8080EBE0613801801938070007000E13035A14015A00781300A2127000F01400 A6ECFFF0EC0F80007013071278A212387EA27E6C130B380180113800E06090381F80001C 1E7E9C21>I<39FFF3FFC0390F003C00ACEBFFFCEB003CAD39FFF3FFC01A1C7E9B1F>III76 DIIII82 D<3807E080EA1C19EA3005EA7003EA600112E01300A36C13007E127C EA7FC0EA3FF8EA1FFEEA07FFC61380130FEB07C0130313011280A300C01380A238E00300 EAD002EACC0CEA83F8121E7E9C17>I<007FB512C038700F010060130000401440A200C0 14201280A300001400B1497E3803FFFC1B1C7F9B1E>I<39FFF07FC0390F000E001404B3 A26C5B138000035B12016C6C5AEB70C0011FC7FC1A1D7E9B1F>I<39FFE00FF0391F0003 C06CEB018015006D5A00071302A26C6C5AA36C6C5AA213F000005BA2EBF830EB7820A26D 5AA36D5AA2131F6DC7FCA21306A31C1D7F9B1F>I<3AFFE0FFE0FF3A1F001F003C001E01 1E13186C011F1310A3D807801420EC2780A2D803C01440EC43C0A213E00001903881E080 A33A00F100F100A3017913FA017A137AA2013E137C013C133CA301181318A3281D7F9B2B >I<12FEA212C0B3B312FEA207297C9E0C>91 D<12FEA21206B3B312FEA20729809E0C> 93 D97 D<12FC121CAA137CEA1D86EA1E03381C018014 C0130014E0A614C013011480381E0300EA1906EA10F8131D7F9C17>II< 133F1307AAEA03E7EA0C17EA180F487E1270126012E0A61260127012306C5AEA0C373807 C7E0131D7E9C17>II<13F8EA018CEA071E1206EA0E0C 1300A6EAFFE0EA0E00B0EA7FE00F1D809C0D>II<12FC121CAA137C13 87EA1D03001E1380121CAD38FF9FF0141D7F9C17>I<1218123CA21218C7FCA712FC121C B0EAFF80091D7F9C0C>I<13C0EA01E0A2EA00C01300A7EA0FE01200B3A21260EAF0C012 F1EA6180EA3E000B25839C0D>I<12FC121CAAEB3FC0EB0F00130C13085B5B5B13E0121D EA1E70EA1C781338133C131C7F130F148038FF9FE0131D7F9C16>I<12FC121CB3A9EAFF 80091D7F9C0C>I<39FC7E07E0391C838838391D019018001EEBE01C001C13C0AD3AFF8F F8FF8021127F9124>II< EA03F0EA0E1CEA1806487E00701380EA600100E013C0A600601380EA700300301300EA18 06EA0E1CEA03F012127F9115>IIIII<1204A4120CA2121C123CEAFFE0EA1C00A91310A5120CEA0E20EA 03C00C1A7F9910>I<38FC1F80EA1C03AD1307120CEA0E1B3803E3F014127F9117>I<38FF 07E0383C0380381C0100A2EA0E02A26C5AA3EA0388A213D8EA01D0A2EA00E0A313401312 7F9116>I<39FF3FCFE0393C0F0380381C07011500130B000E1382A21311000713C4A213 203803A0E8A2EBC06800011370A2EB8030000013201B127F911E>I<387F8FF0380F0380 1400EA0702EA0384EA01C813D8EA00F01370137813F8139CEA010E1202EA060738040380 381E07C038FF0FF81512809116>I<38FF07E0383C0380381C0100A2EA0E02A26C5AA3EA 0388A213D8EA01D0A2EA00E0A31340A25BA212F000F1C7FC12F31266123C131A7F9116> III E /Fu 7 117 df<14E0A2497EA3497EA2EB06FCA2EB0EFEEB0C7EA2497EA201307F141F01 707FEB600FA2496C7E90B5FC4880EB8003A248486C7EA20006801400000E803AFFE00FFF E0A2231F7E9E28>65 D97 DII114 DII E /Fv 56 124 df<127012F812FCA212741204A41208A21210A212201240060F7C840E> 44 DI<127012F8A3127005057C840E>I48 D<13801203120F12F31203B3A9EA07C0EAFFFE0F217C A018>III<1302130613 0EA2131EA2132E134EA2138EA2EA010E1202A21204A212081210A21220A212401280B512 F838000E00A7131F3801FFF015217FA018>I<00101380381E0700EA1FFF5B13F8EA13E0 0010C7FCA613F8EA130EEA1407381803801210380001C0A214E0A4127012F0A200E013C0 1280EA4003148038200700EA1006EA0C1CEA03F013227EA018>I<137EEA01C138030080 380601C0EA0E03121C381801800038C7FCA212781270A2EAF0F8EAF30CEAF4067F00F813 80EB01C012F014E0A51270A3003813C0A238180380001C1300EA0C06EA070CEA01F01322 7EA018>I<12401260387FFFE014C0A23840008038C0010012801302A2485A5BA25B1330 13201360A313E05BA21201A41203A86C5A13237DA118>III<497EA3497EA3EB05E0A2EB0DF01308A2497E1478 A2497EA3497EA3497EA290B5FC3901000780A24814C000021303A24814E01401A2000CEB 00F0A2003EEB01F839FF800FFF20237EA225>65 DI<903807E01090 38381830EBE0063901C0017039038000F048C7FC000E1470121E001C1430123CA2007C14 101278A200F81400A812781510127C123CA2001C1420121E000E14407E6C6C13803901C0 01003800E002EB381CEB07E01C247DA223>II<903807F00890383C0C18EBE0023901C001B839038000F8 48C71278481438121E15185AA2007C14081278A200F81400A7EC1FFF0078EB00F8157812 7C123CA27EA27E7E6C6C13B86C7E3900E0031890383C0C08903807F00020247DA226>71 D<39FFFC3FFF390FC003F039078001E0AE90B5FCEB8001AF390FC003F039FFFC3FFF2022 7EA125>II<3803FFF038001F00 7FB3A6127012F8A2130EEAF01EEA401C6C5AEA1870EA07C014237EA119>I76 DI<39FF8007FF3907C000F81570D805E01320EA04F0A2137813 7C133C7F131F7FEB0780A2EB03C0EB01E0A2EB00F014F81478143C143E141E140FA2EC07 A0EC03E0A21401A21400000E1460121FD8FFE0132020227EA125>III82 D<3803F020380C0C60EA1802383001E0EA70000060136012E0A21420A36C13 00A21278127FEA3FF0EA1FFE6C7E0003138038003FC0EB07E01301EB00F0A214707EA46C 1360A26C13C07E38C8018038C60700EA81FC14247DA21B>I<007FB512F8397807807800 60141800401408A300C0140C00801404A400001400B3A3497E0003B5FC1E227EA123>I< 39FFFC07FF390FC000F86C4813701520B3A5000314407FA2000114806C7E9038600100EB 3006EB1C08EB03F020237EA125>I<3BFFF03FFC03FE3B1F8007E000F86C486C48137017 20A26C6C6C6C1340A32703C002F01380A33B01E004780100A33A00F0083C02A39039F818 3E06903978101E04A2137C90393C200F08A390391E400790A390390F8003E0A36D486C5A A36D5C010213002F237FA132>87 D97 D<120E12FE121E120EAB131FEB61C0EB8060380F0030000E1338143C141C141EA7141C14 3C1438000F1370380C8060EB41C038083F0017237FA21B>II<14E0130F13011300ABEA01F8EA0704EA0C02EA1C01EA38001278127012F0 A7127012781238EA1801EA0C0238070CF03801F0FE17237EA21B>II<133C13C6EA018F1203130FEA0700A9EAFFF8EA07 00B21380EA7FF8102380A20F>I<14703801F19838071E18EA0E0E381C0700A2003C1380 A4001C1300A2EA0E0EEA0F1CEA19F00010C7FCA21218A2EA1FFE380FFFC014E0383800F0 006013300040131812C0A300601330A2003813E0380E03803803FE0015217F9518>I<12 0E12FE121E120EABEB1F80EB60C0EB80E0380F0070A2120EAF38FFE7FF18237FA21B>I< 121C121E123E121E121CC7FCA8120E12FE121E120EB1EAFFC00A227FA10E>II<120E12FE121E120EABEB03FCEB01F014C01480EB02005B5B5B133813F8EA0F1C EA0E1E130E7F1480EB03C0130114E0EB00F014F838FFE3FE17237FA21A>I<120E12FE12 1E120EB3ADEAFFE00B237FA20E>I<390E1FC07F3AFE60E183803A1E807201C03A0F003C 00E0A2000E1338AF3AFFE3FF8FFE27157F942A>I<380E1F8038FE60C0381E80E0380F00 70A2120EAF38FFE7FF18157F941B>III114 DI<1202A41206A3120E121E123EEAFFF8EA0E00AB1304A6EA 07081203EA01F00E1F7F9E13>I<000E137038FE07F0EA1E00000E1370AD14F0A2380601 70380382783800FC7F18157F941B>I<38FFC1FE381E0078000E13301420A26C1340A238 038080A33801C100A2EA00E2A31374A21338A3131017157F941A>I<39FF8FF8FF391E01 E03C001CEBC018120EECE010A239070260201470A239038430401438A23901C81880141C A23900F00D00140FA2EB6006A320157F9423>I<38FF83FE381F01F0380E00C06C138038 0381001383EA01C2EA00E41378A21338133C134E138EEA0187EB0380380201C0000413E0 EA0C00383E01F038FF03FE17157F941A>I<38FFC1FE381E0078000E13301420A26C1340 A238038080A33801C100A2EA00E2A31374A21338A31310A25BA35B12F05B12F10043C7FC 123C171F7F941A>I123 D E /Fw 7 102 df0 D<0040132000C01360006013C03830018038180300EA0C066C5A6C5AEA01B0EA00 E0A2EA01B0EA0318EA060C487E487E38300180386000C04813600040132013147A9320> 2 DI8 D15 D100 DI E /Fx 21 122 df<13031307130E131C1338137013F0EA01E0EA03C0A21207 1380120F13005AA25A123EA2127EA3127CA212FCAC127CA2127EA3123EA2123F7EA27E13 80120713C01203A2EA01E0EA00F013701338131C130E13071303103C7AAC1B>40 D<7E7E7E12707E7E121E7EEA0780A213C0120313E0120113F0A213F81200A213FCA3137C A2137EAC137CA213FCA313F8A2120113F0A213E0120313C012071380A2EA0F00121E121C 5A5A5A5A5A0F3C7BAC1B>I<91393FF00180903903FFFE03010FEBFF8790393FF007DF90 39FF8001FF4848C7127F4848143FD807F0141F000F150F48481407A2485A1603127F5B93 C7FC12FFA9127FA26DEC0380123FA26C7EEE07006C7E0007150ED803FC141E6C6C5C6C6C 6C13F890393FF007E0010FB55A010391C7FC9038003FF829297CA832>67 D73 D76 D<48B47E000713F0380F81F8381FC07EA280D80F801380EA0700C7FCA3EB0FFF90B5FC38 07FC3FEA0FE0EA3F8013005A12FEA4007E137F007F13DF393F839FFC380FFF0F3801FC03 1E1B7E9A21>97 DII101 D<1207EA0FC0EA1FE0123FA3121FEA 0FC0EA0700C7FCA7EAFFE0A3120FB3A3EAFFFEA30F2B7DAA14>105 D108 D<3BFFC07F800FF0903AC1FFE03FFC 903AC383F0707E3B0FC603F8C07F903ACC01F9803F01D8D9FF00138001F05BA201E05BB0 3CFFFE1FFFC3FFF8A3351B7D9A3A>I<38FFC07F9038C1FFC09038C787E0390FCE03F013 D88113F0A213E0B03AFFFE3FFF80A3211B7D9A26>II<38FFE1FE9038E7FF809038 FE07E0390FF803F0496C7E496C7E818181A21680A716005DA25D4A5A01F05B6D485A9038 FE0FE09038E7FF80D9E1FCC7FC01E0C8FCA9EAFFFEA321277E9A26>I<38FFC1F0EBC7FC EBCE3E380FD87FA213F0143E141CEBE000B0B5FCA3181B7E9A1C>114 D<3803FE30380FFFF0EA1E03EA380048137012F0A27E6C1300EAFFE0EA7FFEEBFF806C13 E06C13F0000713F8C6FCEB03FC13000060137C00E0133C7E14387E6C137038FF01E038F7 FFC000C11300161B7E9A1B>I<1370A413F0A312011203A21207381FFFF0B5FCA23807F0 00AD1438A61203EBF870000113603800FFC0EB1F8015267FA51B>I<39FFE03FF8A3000F 1303B214071207140F3A03F03BFF803801FFF338003FC3211B7D9A26>I<3AFFFE03FF80 A33A07F0007000A26D13F000035CEBFC0100015CA26C6C485AA2D97F07C7FCA2148FEB3F 8E14DEEB1FDCA2EB0FF8A36D5AA26D5AA26D5A211B7F9A24>I<3AFFFE03FF80A33A07F0 007000A26D13F000035CEBFC0100015CA26C6C485AA2D97F07C7FCA2148FEB3F8E14DEEB 1FDCA2EB0FF8A36D5AA26D5AA26D5AA2495AA2EA3807007C90C8FCEAFE0F130E131E5BEA 7C78EA3FE0EA0FC021277F9A24>121 D E end %%EndProlog %%BeginSetup %%Feature: *Resolution 300dpi TeXDict begin %%EndSetup %%Page: 1 1 1 0 bop 216 233 a Fx(In)n(terpro)r(cessor)23 b(Collecti)o(v)n(e)d(Comm) n(unication)g(Library)780 307 y(\(In)n(terCom\))1146 286 y Fw(\003)247 428 y Fv(Mik)o(e)15 b(Barnett)734 b(Sat)o(y)o(a)16 b(Gupta)83 b(Da)o(vid)16 b(G.)g(P)o(a)o(yne)34 486 y(Departmen)o(t)e (of)j(Computer)e(Science)514 b(Sup)q(ercomputer)15 b(Systems)g (Division)184 544 y(Univ)o(ersit)o(y)f(of)j(Idaho)832 b(In)o(tel)14 b(Corp)q(oration)104 602 y(Mosco)o(w,)j(Idaho)f (83844-101)q(0)625 b(15201)19 b(N.W.)c(Green)o(brier)f(Pkwy)1344 660 y(Bea)o(v)o(erton,)h(Oregon)i(97006)-7 793 y(Lance)f(Sh)o(uler)82 b(Rob)q(ert)16 b(v)m(an)h(de)f(Geijn)687 b(Jerrell)15 b(W)l(atts)24 852 y(Departmen)o(t)g(of)h(Computer)g(Sciences)420 b(Cen)o(ter)15 b(for)i(High)f(P)o(erformance)e(Computing)24 910 y(The)j(Univ)o(ersit)o(y)c(of)k(T)l(exas)f(at)h(Austin)601 b(The)16 b(Univ)o(ersit)o(y)d(of)k(T)l(exas)112 968 y(Austin,)f(T)l (exas)g(78712{118)q(8)672 b(Austin,)15 b(T)l(exas)h(78758{449)q(7)328 1130 y Fu(Abstract)-7 1228 y Ft(In)21 b(this)g(pap)q(er,)j(w)o(e)d (outline)g(a)g(uni\014ed)g(approac)o(h)g(for)-57 1278 y(building)14 b(a)h(library)f(of)h(collectiv)o(e)g(comm)o(unication)d (op)q(era-)-57 1328 y(tions)f(that)g(p)q(erforms)f(w)o(ell)h(on)f(a)h (cross-section)i(of)d(problems)-57 1377 y(encoun)o(tered)16 b(in)d(real)g(applications.)k(The)d(target)g(arc)o(hitec-)-57 1427 y(ture)i(is)e(a)h(t)o(w)o(o-dimensional)d(mesh)i(with)g(w)o (orm-hole)f(rout-)-57 1477 y(ing,)19 b(but)f(the)i(tec)o(hniques)g (also)e(apply)f(to)i(higher)g(dimen-)-57 1527 y(sional)10 b(meshes)h(and)f(h)o(yp)q(ercub)q(es.)19 b(W)m(e)11 b(stress)h(a)f (general)g(ap-)-57 1577 y(proac)o(h,)i(addressing)i(the)f(need)h(for)e (implemen)o(tations)e(that)-57 1627 y(p)q(erform)h(w)o(ell)g(for)g(v)n (arious)g(sized)h(v)o(ectors)h(and)e(grid)h(dimen-)-57 1676 y(sions,)f(including)g(non-p)q(o)o(w)o(er-of-t)o(w)o(o)f(grids.)18 b(This)12 b(requires)-57 1726 y(the)g(dev)o(elopmen)o(t)e(of)h(general) g(tec)o(hniques)i(for)e(building)f(h)o(y-)-57 1776 y(brid)16 b(algorithms.)23 b(Finally)m(,)14 b(our)i(approac)o(h)g(also)g(supp)q (orts)-57 1826 y(collectiv)o(e)24 b(comm)o(uni)o(cation)d(within)h(a)i (group)f(of)g(no)q(des,)-57 1876 y(whic)o(h)18 b(is)g(required)h(b)o(y) e(man)o(y)f(scalable)i(algorithms.)28 b(Re-)-57 1925 y(sults)14 b(from)e(the)j(In)o(tel)f(P)o(aragon)f(system)h(are)g (included.)-57 2081 y Fs(1)56 b(In)n(tro)r(duction)-7 2179 y Ft(The)15 b(In)o(terpro)q(cessor)j(Collectiv)o(e)d(Comm)o(uni)o (cation)d(\(In-)-57 2228 y(terCom\))21 b(Pro)r(ject)h(is)g(a)f (comprehensiv)o(e)h(study)g(of)e(tec)o(h-)p -57 2263 389 2 v -11 2290 a Fr(\003)7 2302 y Fq(Cop)o(yrigh)o(t)208 2301 y Fp(c)198 2302 y Fo(\015)p Fq(1994)15 b(b)o(y)e(the)f(Institute)g (of)i(Electrical)f(and)-57 2341 y(Electronics)19 b(Engineers,)h(Inc.)36 b(Reprin)o(ted)18 b(with)i(the)e(p)q(er-)-57 2381 y(mission)13 b(of)i(the)e(IEEE)g(from)g(the)g(Pro)q(ceedings)g(of)h(the)f(Scal-)-57 2420 y(able)j(High-P)o(erformance)e(Computing)i(Conference,)h(pages)-57 2460 y(357-364,)c(IEEE)c(Computer)f(So)q(ciet)o(y)i(Press,)g(Kno)o (xville,)i(TN,)-57 2499 y(Ma)o(y)h(23-25,)g(1994.)20 b(P)o(ermission)10 b(to)i(cop)o(y)h(without)f(fee)g(all)g(or)-57 2538 y(part)d(of)i(this)g(material)d(is)j(gran)o(ted)e(pro)o(vided)g (that)h(the)f(copies)-57 2578 y(are)14 b(not)g(made)f(or)i(distributed) d(for)k(direct)d(commercial)g(ad-)-57 2617 y(v)n(an)o(tage,)f(the)g (IEEE)f(cop)o(yrigh)o(t)i(notice)f(and)g(the)f(title)i(of)g(the)-57 2657 y(publication)g(app)q(ear,)f(and)h(notice)h(is)g(giv)o(en)g(that)e (cop)o(ying)j(is)-57 2696 y(b)o(y)i(p)q(ermission)f(of)j(the)d (Institute)g(of)i(Electrical)g(and)e(Elec-)-57 2736 y(tronics)e (Engineers.)20 b(T)m(o)15 b(cop)o(y)g(otherwise,)f(or)h(to)f (republish,)-57 2775 y(requires)f(a)g(fee)g(and)g(sp)q(eci\014c)g(p)q (ermission.)1013 1130 y Ft(niques)f(for)f(a)g(high)f(p)q(erformance)i (implem)o(en)o(tation)d(of)h(com-)1013 1180 y(monly)f(used)j(collectiv) o(e)f(comm)o(unication)d(algorithms.)15 b(It)c(is)1013 1230 y(the)17 b(emphasis)f(on)g(a)g(high)g(p)q(erformance)g(implemen)o (tation)1013 1280 y(that)10 b(sets)i(it)e(aside)g(from)f(the)i(MPI)f (e\013ort)h([6],)f(whic)o(h)g(tries)h(to)1013 1330 y Fn(standar)n(dize)17 b Ft(the)g Fn(interfac)n(e)f Ft(to)h(comm)o(uni)o (cation)d(libraries.)1013 1380 y(Indeed,)g(w)o(e)f(exp)q(ect)h(the)g (fruits)f(of)f(our)h(e\013orts)i(to)d(b)q(e)i(incor-)1013 1429 y(p)q(orated)g(in)o(to)f(implemen)o(tations)e(of)i(the)i(MPI)f (standard.)1063 1496 y(The)g(follo)o(wing)e(collectiv)o(e)j(comm)o (unicatio)o(n)d(op)q(erations)1013 1546 y(ha)o(v)o(e)20 b(b)q(een)h(iden)o(ti\014ed)f(as)g(b)q(eing)g(useful)g(in)f(man)o(y)f (appli-)1013 1596 y(cations:)23 b Fn(br)n(o)n(adc)n(ast,)17 b(sc)n(atter,)g(gather)p Ft(,)f Fn(c)n(ol)r(le)n(ct)p Ft(,)g(and)g Fn(glob)n(al)1013 1645 y(c)n(ombine)p Ft(.)35 b(T)o(ypical)19 b(approac)o(hes)i(to)e(implemen)o(ting)d(suc)o(h)1013 1695 y(collectiv)o(e)23 b(comm)o(unication)d(algorithms)i(are)i (limited)d(to)1013 1745 y(considering)10 b(the)h(case)g(of)e(short)i(v) o(ectors,)g(whic)o(h)f(are)h(treated)1013 1795 y(with)i(one)h(tec)o (hnique,)h(or)f(to)f(considering)h(the)h(case)g(of)e(long)1013 1845 y(v)o(ectors,)g(for)f(whic)o(h)h(v)o(ery)f(di\013eren)o(t)i(tec)o (hniques)f(are)g(appro-)1013 1895 y(priate.)18 b(F)m(or)12 b(a)g(general)h(purp)q(ose)h(library)m(,)d(it)h(is)g(crucial)h(that) 1013 1944 y(an)c(implemen)o(tation)e(p)q(erforms)i(w)o(ell)g(for)g Fn(al)r(l)h Ft(v)o(ector)g(lengths.)1063 2011 y(In)20 b(our)h(previous)g(pap)q(ers)h(on)e(collectiv)o(e)h(comm)o(unica-)1013 2061 y(tion,)12 b(w)o(e)h(studied)g(individual)e(comm)o(uni)o(cation)f (op)q(erations)1013 2111 y(and)19 b(their)h(implem)o(en)o(tation,)d (including)i(p)q(ossible)g(h)o(ybrid)1013 2160 y(approac)o(hes)d([1)o (,)f(2,)g(3)o(,)g(5].)22 b(It)15 b(is)h(through)f(this)g(progression) 1013 2210 y(of)g(studies)h(that)g(w)o(e)g(ha)o(v)o(e)f(disco)o(v)o (ered)i(that)f(all)e(the)i(afore-)1013 2260 y(men)o(tioned)8 b(collectiv)o(e)i(comm)o(unicatio)o(n)d(op)q(erations)j(can)f(b)q(e) 1013 2310 y(built)19 b(from)f(similar)f(primitiv)o(es.)33 b(It)20 b(is)g(this)f(observ)n(ation)1013 2360 y(that)d(has)h(led)f(us) g(to)h(prop)q(ose)g(a)f(uni\014ed)g(approac)o(h)g(to)g(h)o(y-)1013 2409 y(brid)e(design.)1063 2476 y(Finally)m(,)9 b(there)k(is)f(a)f (strong)h(applications)e(need)j(for)e(com-)1013 2526 y(m)o(unication)j(op)q(erations)j(whic)o(h)f(supp)q(ort)h(collectiv)o (e)f(com-)1013 2576 y(m)o(unication)g(within)i(a)g(subset)i(of)d(the)i (no)q(des)h(comprising)1013 2626 y(the)10 b(application.)16 b(Suc)o(h)10 b(a)g(subset)h(of)e(no)q(des)i(could)f(b)q(e)g(a)g(ro)o (w,)1013 2675 y(a)k(column,)f(a)i(blo)q(c)o(k)f(of)g(no)q(des,)h(or)g (simply)e(a)h(list)g(of)h(no)q(des.)1013 2725 y(Our)g(approac)o(h)f (builds)g(on)g(and)g(supp)q(orts)i(suc)o(h)f Fn(gr)n(oup)f Ft(col-)1013 2775 y(lectiv)o(e)g(comm)o(unicatio)o(n.)p eop %%Page: 2 2 2 1 bop -57 117 a Fs(2)56 b(T)-5 b(arget)19 b(Arc)n(hitectures)-7 214 y Ft(Our)39 b(curren)o(t)g(implemen)o(tation)c(assumes)j(a)g(t)o(w) o(o-)-57 264 y(dimensional)15 b(ph)o(ysical)h(mesh)h(of)f(pro)q (cessing)i(no)q(des,)g(with)-57 314 y(bidirectional)27 b(links)h(b)q(et)o(w)o(een)h(no)q(des,)j(and)c(w)o(orm-hole)-57 363 y(\(cut-through\))17 b(routing.)24 b(F)m(urthermore,)15 b(w)o(e)i(assume)e(that)-57 413 y(it)e(is)g(p)q(ossible)g(to)g(mo)q (del)f(the)i(time)e(required)i(for)f(sending)g(a)-57 463 y(message)h(of)f(length)h Fm(n)f Ft(b)o(ytes)i(b)q(et)o(w)o(een)g (an)o(y)f(t)o(w)o(o)f(no)q(des)i(b)o(y)364 549 y Fm(\013)9 b Ft(+)h Fm(n\014)-57 635 y Ft(where)18 b Fm(\013)e Ft(is)g(the)h (latency)g(for)f(sending)h(a)f(message,)g(and)h Fm(\014)-57 685 y Ft(is)h(the)h(comm)o(unicatio)o(n)d(time)g(p)q(er)k(item,)d(in)h (the)h(absence)-57 735 y(of)d(net)o(w)o(ork)g(con\015icts.)26 b(A)17 b(pro)q(cessor)h(can)f(b)q(oth)f(send)h(and)-57 785 y(receiv)o(e)11 b(at)e(the)h(same)e(time.)15 b(But)10 b(it)f(can)h(only)e(send)j(to,)e(or)h(re-)-57 835 y(ceiv)o(e)j(from,)d (one)i(other)h(no)q(de)g(at)f(a)g(giv)o(en)f(time.)16 b(When)d(t)o(w)o(o)-57 884 y(messages)i(tra)o(v)o(erse)g(the)g(same)f (ph)o(ysical)g(link)f(on)h(the)i(com-)-57 934 y(m)o(unication)i(in)o (terconnect,)24 b(w)o(e)d(assume)f(they)h(share)h(the)-57 984 y(bandwidth)14 b(of)f(that)h(link.)-57 1140 y Fs(3)56 b(T)-5 b(arget)19 b(Collectiv)n(e)d(Comm)n(unication)-7 1237 y Ft(W)m(e)11 b(explain)f(the)i(target)g(collectiv)o(e)f(comm)o (unicatio)o(n)e(op-)-57 1287 y(erations)22 b(in)f(the)i(setting)f (where)h(all)e(pro)q(cessors)j(are)e(in-)-57 1337 y(v)o(olv)o(ed)12 b(in)h(the)h(comm)o(unication.)g(There)h(are)e Fm(p)g Ft(pro)q(cessors,)-57 1387 y(lab)q(eled)h Fl(P)118 1393 y Fk(0)137 1387 y Fm(;)7 b(:)g(:)g(:)t(;)g Fl(P)262 1393 y Fj(p)p Fi(\000)p Fk(1)323 1387 y Ft(.)19 b(W)m(e)14 b(use)i Fm(x)e Ft(to)g(represen)o(t)i(a)e(v)o(ector)-57 1436 y(con)o(taining)e Fm(n)i Ft(data)f(items;)f(it)i(is)f(partitioned) g(in)o(to)g(sub)o(v)o(ec-)-57 1486 y(tors,)289 1597 y Fm(x)e Ft(=)368 1502 y Fh(0)368 1575 y(B)368 1601 y(@)446 1533 y Fm(x)470 1539 y Fk(0)462 1578 y Ft(.)462 1594 y(.)462 1611 y(.)425 1661 y Fm(x)449 1667 y Fj(p)p Fi(\000)p Fk(1)531 1502 y Fh(1)531 1575 y(C)531 1601 y(A)-57 1738 y Ft(where)19 b Fm(x)91 1744 y Fj(i)122 1738 y Ft(is)f(of)f(length)h Fm(n)375 1744 y Fj(i)388 1738 y Ft(.)30 b(Similarly)l(,)15 b(v)o(ector)k Fm(y)769 1723 y Fk(\()p Fj(j)r Fk(\))813 1738 y Ft(,)f Fm(j)j Ft(=)-57 1788 y(0)p Fm(;)7 b(:)g(:)g(:)e(;)i(p)h Fw(\000)i Ft(1,)j(con)o(tains)h Fm(n)g Ft(items,)f(and)h(is)g (partitioned)g(con-)-57 1838 y(formal)h(with)i Fm(x)p Ft(.)27 b(The)18 b(op)q(eration)f Fw(\010)g Ft(represen)o(ts)j(an)d (asso-)-57 1888 y(ciativ)o(e)i(and)g(comm)o(utati)o(v)o(e)e(com)o(bine) g(op)q(eration)i(suc)o(h)h(as)-57 1938 y(an)d(elemen)o(t-wise)g (summation)e(or)i(elemen)o(t-wise)g(pro)q(duct)-57 1987 y(of)c(v)o(ectors.)-7 2037 y(The)e(target)h(collectiv)o(e)f(comm)o (unicatio)o(n)d(op)q(erations)k(are)-57 2087 y(giv)o(en)h(in)h(T)m (able)f(1.)-57 2243 y Fs(4)56 b(Building)18 b(Blo)r(c)n(ks)-7 2340 y Ft(The)g(building)f(blo)q(c)o(ks)h(for)g(our)g(library)f (consist)i(of)f(the)-57 2390 y(follo)o(wing)10 b(implemen)o(tatio)o(ns) g(of)j(the)g(op)q(erations)g Fn(for)g(line)n(ar)-57 2440 y(arr)n(ay)h(networks)h(with)f(worm-hole)g(r)n(outing)p Ft(:)-57 2526 y Fl(Short)g(v)o(ector)h(primiti)o(v)o(es.)j Ft(These)34 b(are)e(implemen)o(ta-)26 2576 y(tions)16 b(of)f(the)h(op)q(erations)h(in)e(T)m(able)g(1)h(that)g(\(attempt)26 2626 y(to\))22 b(minim)o(ize)e(the)j(n)o(um)o(b)q(er)e(of)g(startups)j (incurred.)26 2675 y(F)m(or)j(example,)i(the)e(broadcast)h(uses)g(a)f (minim)o(um)26 2725 y(spanning)13 b(tree)h(\(MST\))g(implem)o(en)o (tation)c(that)j(incurs)26 2775 y Fw(d)p Ft(log)98 2785 y Fk(2)117 2775 y Ft(\()p Fm(p)p Ft(\))p Fw(e)h Ft(startups.)1013 117 y Fl(Long)h(v)o(ector)g(primiti)o(v)o(es.)j Ft(A)d(few)h(of)f(the)h (comm)o(unica-)1096 166 y(tion)e(op)q(erations,)i(whic)o(h)e(w)o(e)i (refer)g(to)f(as)g(long)f(v)o(ector)1096 216 y(primitiv)o(es,)f(can)i (b)q(e)g(used)h(as)e(building)g(blo)q(c)o(ks)h(for)f(ef-)1096 266 y(\014cien)o(t)h(implemen)o(tations)d(of)j(all)f(the)h(collectiv)o (e)g(com-)1096 316 y(m)o(unication)d(op)q(erations)k(for)e(long)g(v)o (ectors.)22 b(F)m(or)15 b(long)1096 366 y(v)o(ectors,)d(w)o(e)f (emphasize)f(minim)o(izing)d(the)12 b(p)q(enalt)o(y)e(p)q(er)1096 415 y(item)16 b(of)h(data,)h(eliminating)c(net)o(w)o(ork)k (con\015icts,)h(and)1096 465 y(simplicit)o(y)m(.)24 b(The)18 b(long)e(v)o(ector)i(primitiv)o(es)d(and)i(their)1096 515 y(implemen)o(tatio)o(ns)12 b(are:)1096 581 y Fl(MST)g(scatter.)k Ft(The)11 b(scatter)h(is)e(implemen)o(ted)e(b)o(y)i(re-)1096 631 y(cursiv)o(ely)i(halving)e(the)i(v)o(ector)g(and)f(net)o(w)o(ork,)h (thereb)o(y)1096 681 y(a)o(v)o(oiding)g(all)g(net)o(w)o(ork)i (con\015icts.)1096 746 y Fl(MST)i(gather.)h Ft(The)e(scatter)g(op)q (eration)f(in)f(rev)o(erse.)1096 812 y Fl(Buc)o(k)o(et)i(collect.)k Ft(F)m(or)14 b(this)h(implem)o(en)o(tation)c(of)j(the)1096 862 y(collect,)e(the)g(linear)f(arra)o(y)g(is)g(view)o(ed)h(as)g(a)f (ring.)16 b(Buc)o(k-)1096 912 y(ets)h(are)f(passed)i(b)q(et)o(w)o(een)f (the)g(no)q(des)g(that)f(mo)o(v)o(e)e(the)1096 962 y(sub)o(v)o(ectors)k (to)f(b)q(e)h(collected,)h(lea)o(ving)c(the)j(result)g(on)1096 1012 y(all)d(no)q(des,)j(as)f(illustrated)g(in)f(Fig.)g(1.)27 b(Note)17 b(that)g(no)1096 1061 y(net)o(w)o(ork)d(con\015icts)h(o)q (ccur.)1096 1127 y Fl(Buc)o(k)o(et)h(distrib)o(ute)o(d)e(global)i(com)o (bine.)k Ft(Similar)1096 1177 y(to)c(the)g(buc)o(k)o(et)h(collect,)f (executed)i(in)d(rev)o(erse,)j(where)1096 1227 y(the)12 b(buc)o(k)o(ets)g(are)f(used)h(to)f(accum)o(ulate)f(con)o(tributions.) 1096 1277 y(This)k(is)f(illustrated)h(in)f(Fig)h(2.)1013 1365 y(The)23 b(implemen)o(tations)e(of)h(the)i(short)g(and)f(long)f(v) o(ector)1013 1415 y(primitiv)o(es)16 b(can)i(b)q(e)g(sho)o(wn)g(to)f(b) q(e)h(optimal)d(on)j(linear)f(ar-)1013 1465 y(ra)o(ys.)1063 1515 y(Using)d(the)g(long)f(v)o(ector)i(primitiv)o(es,)d(w)o(e)i(can)h (build)e(e\016-)1013 1564 y(cien)o(t)j(long)e(v)o(ector)j(implem)o(en)o (tations)c(for)i(the)h(other)g(com-)1013 1614 y(m)o(unications:)1013 1695 y Fl(Broadcast.)k Ft(MST)15 b(scatter)j(follo)o(w)o(ed)c(b)o(y)h (buc)o(k)o(et)h(collect.)1096 1745 y(This)d(can)h(b)q(e)g(sho)o(wn)g (to)f(b)q(e)h(asymptotically)d(within)i(a)1096 1795 y(factor)h(of)f(t)o (w)o(o)g(of)h(optimal.)1013 1877 y Fl(Com)o(bine-to-on)o(e.)k Ft(Distributed)24 b(buc)o(k)o(et)h(com)o(bine)d(fol-)1096 1926 y(lo)o(w)o(ed)17 b(b)o(y)g(a)g(MST)h(gather.)29 b(This)17 b(can)h(b)q(e)g(sho)o(wn)f(to)1096 1976 y(b)q(e)f (asymptotically)c(within)j(a)g(factor)g(of)f(t)o(w)o(o)h(of)g(opti-) 1096 2026 y(mal.)1013 2108 y Fl(Com)o(bine-to-all)o(.)j Ft(Distributed)31 b(buc)o(k)o(et)h(com)o(bine)e(fol-)1096 2158 y(lo)o(w)o(ed)19 b(b)o(y)h(a)g(buc)o(k)o(et)h(collect.)37 b(This)20 b(can)g(b)q(e)h(sho)o(wn)1096 2208 y(to)14 b(b)q(e)g(asymptotically)d(optimal.)1013 2364 y Fs(5)56 b(Hybrid)18 b(algorithms)1063 2463 y Ft(W)m(e)12 b(illustrate)g(ho)o(w) g(h)o(ybrid)h(algorithms)d(can)j(b)q(e)g(formed)1013 2513 y(b)o(y)g(\014rst)i(considering)f(a)f(logical)f(t)o(w)o (o-dimensional)f(mesh)j(of)1013 2562 y(no)q(des.)24 b(All)14 b(of)h(the)i(h)o(ybrids)e(are)h(implemen)o(ted)d(using)j(one)1013 2612 y(of)d(the)i(follo)o(wing)c(templates:)1013 2693 y Fl(T)l(emplate)j(1.)1134 2775 y Ft(1.)20 b(P)o(erform)13 b(the)i(op)q(eration)e(within)g(ro)o(ws.)p eop %%Page: 3 3 3 2 bop 243 118 1440 2 v 242 168 2 50 v 268 153 a Fl(Op)q(eration)p 674 168 V 683 168 V 227 w Ft(Before)p 1182 168 V 385 w(After)p 1682 168 V 243 170 1440 2 v 243 180 V 242 229 2 50 v 268 214 a(Broadcast)p 674 229 V 683 229 V 259 w Fm(x)13 b Ft(at)h Fl(P)829 220 y Fj(k)849 214 y Ft(,)g Fm(k)g Ft(giv)o(en)p 1182 229 V 202 w Fm(x)f Ft(at)h(all)f Fl(P)1387 220 y Fj(j)p 1682 229 V 243 231 1440 2 v 242 281 2 50 v 268 266 a Ft(Scatter)p 674 281 V 683 281 V 312 w Fm(x)g Ft(at)h Fl(P)829 272 y Fj(k)849 266 y Ft(,)g Fm(k)g Ft(giv)o(en)p 1182 281 V 202 w Fm(x)1232 272 y Fj(j)1263 266 y Ft(at)f Fl(P)1346 272 y Fj(j)p 1682 281 V 243 283 1440 2 v 242 332 2 50 v 268 317 a Ft(Gather)p 674 332 V 683 332 V 313 w Fm(x)732 323 y Fj(j)763 317 y Ft(at)h Fl(P)847 323 y Fj(j)p 1182 332 V 1208 317 a Fm(x)f Ft(at)h Fl(P)1329 323 y Fj(k)1349 317 y Ft(,)f Fm(k)i Ft(giv)o(en)p 1682 332 V 243 334 1440 2 v 242 384 2 50 v 268 369 a(Collect)p 674 384 V 683 384 V 313 w Fm(x)732 375 y Fj(j)763 369 y Ft(at)f Fl(P)847 375 y Fj(j)p 1182 384 V 1208 369 a Fm(x)f Ft(at)h Fl(P)1329 375 y Fj(j)p 1682 384 V 243 386 1440 2 v 242 439 2 54 v 268 424 a Ft(Com)o(bine-to-one)p 674 439 V 683 439 V 151 w Fm(y)729 409 y Fk(\()p Fj(j)r Fk(\))787 424 y Ft(at)g Fl(P)871 430 y Fj(j)p 1182 439 V 1208 424 a Fw(\010)1240 404 y Fj(p)p Fi(\000)p Fk(1)1240 436 y Fj(i)p Fk(=0)1302 424 y Fm(y)1323 409 y Fk(\()p Fj(i)p Fk(\))1377 424 y Ft(at)g Fl(P)1461 430 y Fj(k)1481 424 y Ft(,)f Fm(k)i Ft(giv)o(en)p 1682 439 V 243 441 1440 2 v 242 494 2 54 v 268 479 a(Com)o(bine-to-all)p 674 494 V 683 494 V 168 w Fm(y)729 464 y Fk(\()p Fj(j)r Fk(\))787 479 y Ft(at)f Fl(P)871 485 y Fj(j)p 1182 494 V 1208 479 a Fw(\010)1240 460 y Fj(p)p Fi(\000)p Fk(1)1240 491 y Fj(i)p Fk(=0)1302 479 y Fm(y)1323 464 y Fk(\()p Fj(i)p Fk(\))1377 479 y Ft(at)g Fl(P)1461 485 y Fj(j)p 1682 494 V 243 496 1440 2 v 242 557 2 61 v 268 539 a Ft(Distributed)g(Com)o(bine)p 674 557 V 683 557 V 57 w Fm(y)729 524 y Fk(\()p Fj(j)r Fk(\))787 539 y Ft(at)g Fl(P)871 545 y Fj(j)p 1182 557 V 1208 539 a Fw(\010)1240 519 y Fj(p)p Fi(\000)p Fk(1)1240 551 y Fj(i)p Fk(=0)1302 539 y Fm(y)1323 518 y Fk(\()p Fj(i)p Fk(\))1322 551 y Fj(j)1377 539 y Ft(at)g Fl(P)1461 545 y Fj(j)p 1682 557 V 243 558 1440 2 v 367 674 a Ft(T)m(able)f(1:)18 b(Summary)11 b(of)i(target)i(collectiv)o(e)f(comm)o(uni)o(cation)d(op)q (erations.)33 1000 y(Figure)j(1:)k(Buc)o(k)o(et)d(collect)f(on)g(four)f (pro)q(cessors.)93 1097 y Fg(P)120 1101 y Ff(0)291 1097 y Fg(P)318 1101 y Ff(1)489 1097 y Fg(P)516 1101 y Ff(2)687 1097 y Fg(P)714 1101 y Ff(3)p 28 1126 801 2 v 28 1480 2 355 v 87 1181 69 2 v 87 1227 2 46 v 101 1210 a Fe(x)124 1214 y Ff(0)p 154 1227 V 87 1229 69 2 v 187 1205 67 2 v 211 1204 a Fd(-)p 285 1247 69 2 v 285 1293 2 46 v 299 1276 a Fe(x)322 1280 y Ff(1)p 352 1293 V 285 1295 69 2 v 385 1271 67 2 v 409 1270 a Fd(-)p 483 1313 69 2 v 483 1359 2 46 v 497 1342 a Fe(x)520 1346 y Ff(2)p 550 1359 V 483 1361 69 2 v 583 1337 67 2 v 607 1336 a Fd(-)p 681 1379 69 2 v 681 1425 2 46 v 695 1408 a Fe(x)718 1412 y Ff(3)p 748 1425 V 681 1427 69 2 v 781 1403 67 2 v 805 1402 a Fd(-)p 826 1480 2 355 v 28 1482 801 2 v 22 1488 813 2 v 22 1843 2 355 v 80 1742 69 2 v 80 1787 2 46 v 94 1771 a Fe(x)117 1775 y Ff(3)p 147 1787 V 80 1789 69 2 v 94 1573 a Fe(x)117 1577 y Ff(0)p 181 1765 67 2 v 205 1764 a Fd(-)292 1639 y Fe(x)315 1643 y Ff(1)p 278 1544 69 2 v 278 1589 2 46 v 292 1573 a Fe(x)315 1577 y Ff(0)p 345 1589 V 278 1591 69 2 v 379 1567 67 2 v 403 1566 a Fd(-)490 1705 y Fe(x)513 1709 y Ff(2)p 476 1610 69 2 v 476 1655 2 46 v 490 1639 a Fe(x)513 1643 y Ff(1)p 543 1655 V 476 1657 69 2 v 577 1633 67 2 v 601 1632 a Fd(-)688 1771 y Fe(x)711 1775 y Ff(3)p 674 1676 69 2 v 674 1721 2 46 v 688 1705 a Fe(x)711 1709 y Ff(2)p 741 1721 V 674 1723 69 2 v 775 1699 67 2 v 799 1698 a Fd(-)p 833 1843 2 355 v 22 1845 813 2 v 22 1850 V 22 2205 2 355 v 94 2133 a Fe(x)117 2137 y Ff(3)p 80 2038 69 2 v 80 2084 2 46 v 94 2067 a Fe(x)117 2071 y Ff(2)p 147 2084 V 80 2086 69 2 v 94 1935 a Fe(x)117 1939 y Ff(0)p 181 2062 67 2 v 205 2061 a Fd(-)p 278 2104 69 2 v 278 2150 2 46 v 292 2133 a Fe(x)315 2137 y Ff(3)p 345 2150 V 278 2152 69 2 v 292 2001 a Fe(x)315 2005 y Ff(1)292 1935 y Fe(x)315 1939 y Ff(0)p 379 2128 67 2 v 403 2127 a Fd(-)p 476 1906 69 2 v 476 1952 2 46 v 490 1935 a Fe(x)513 1939 y Ff(0)p 543 1952 V 476 1954 69 2 v 490 2067 a Fe(x)513 2071 y Ff(2)490 2001 y Fe(x)513 2005 y Ff(1)p 577 1930 67 2 v 601 1929 a Fd(-)688 2133 y Fe(x)711 2137 y Ff(3)688 2067 y Fe(x)711 2071 y Ff(2)p 674 1972 69 2 v 674 2018 2 46 v 688 2001 a Fe(x)711 2005 y Ff(1)p 741 2018 V 674 2020 69 2 v 775 1996 67 2 v 799 1995 a Fd(-)p 833 2205 2 355 v 22 2207 813 2 v 22 2213 V 22 2568 2 355 v 94 2495 a Fe(x)117 2499 y Ff(3)94 2429 y Fe(x)117 2433 y Ff(2)94 2297 y Fe(x)117 2301 y Ff(0)94 2363 y Fe(x)117 2367 y Ff(1)292 2495 y Fe(x)315 2499 y Ff(3)292 2363 y Fe(x)315 2367 y Ff(1)292 2297 y Fe(x)315 2301 y Ff(0)292 2429 y Fe(x)315 2433 y Ff(2)490 2297 y Fe(x)513 2301 y Ff(0)490 2429 y Fe(x)513 2433 y Ff(2)490 2363 y Fe(x)513 2367 y Ff(1)490 2495 y Fe(x)513 2499 y Ff(3)688 2495 y Fe(x)711 2499 y Ff(3)688 2429 y Fe(x)711 2433 y Ff(2)688 2363 y Fe(x)711 2367 y Ff(1)688 2297 y Fe(x)711 2301 y Ff(0)p 833 2568 V 22 2570 813 2 v 1013 975 a Ft(Figure)k(2:)23 b(Buc)o(k)o(et)17 b(distributed)h(global)d(com)o(bine)g(on)h(four)1013 1025 y(pro)q(cessors.)1162 1122 y Fg(P)1189 1126 y Ff(0)1360 1122 y Fg(P)1387 1126 y Ff(1)1558 1122 y Fg(P)1585 1126 y Ff(2)1756 1122 y Fg(P)1783 1126 y Ff(3)p 1098 1150 801 2 v 1098 1505 2 355 v 1158 1441 a Fe(y)1182 1422 y Ff(\(0\))1181 1451 y(3)1158 1375 y Fe(y)1182 1356 y Ff(\(0\))1181 1385 y(2)p 1144 1259 94 2 v 1144 1331 2 73 v 1158 1309 a Fe(y)1182 1290 y Ff(\(0\))1181 1319 y(1)p 1236 1331 V 1144 1333 94 2 v 1158 1243 a Fe(y)1182 1224 y Ff(\(0\))1181 1253 y(0)p 1059 1296 67 2 v 1059 1295 a Fd(\033)1356 1441 y Fe(y)1380 1422 y Ff(\(1\))1379 1451 y(3)p 1342 1325 94 2 v 1342 1397 2 73 v 1356 1375 a Fe(y)1380 1356 y Ff(\(1\))1379 1385 y(2)p 1434 1397 V 1342 1399 94 2 v 1356 1309 a Fe(y)1380 1290 y Ff(\(1\))1379 1319 y(1)1356 1243 y Fe(y)1380 1224 y Ff(\(1\))1379 1253 y(0)p 1257 1362 67 2 v 1257 1361 a Fd(\033)p 1540 1391 94 2 v 1540 1463 2 73 v 1554 1441 a Fe(y)1578 1422 y Ff(\(2\))1577 1451 y(3)p 1632 1463 V 1540 1465 94 2 v 1554 1375 a Fe(y)1578 1356 y Ff(\(2\))1577 1385 y(2)1554 1309 y Fe(y)1578 1290 y Ff(\(2\))1577 1319 y(1)1554 1243 y Fe(y)1578 1224 y Ff(\(2\))1577 1253 y(0)p 1455 1428 67 2 v 1455 1427 a Fd(\033)1752 1441 y Fe(y)1776 1422 y Ff(\(3\))1775 1451 y(3)1752 1375 y Fe(y)1776 1356 y Ff(\(3\))1775 1385 y(2)1752 1309 y Fe(y)1776 1290 y Ff(\(3\))1775 1319 y(1)p 1738 1193 94 2 v 1738 1265 2 73 v 1752 1243 a Fe(y)1776 1224 y Ff(\(3\))1775 1253 y(0)p 1830 1265 V 1738 1267 94 2 v 1653 1230 67 2 v 1653 1229 a Fd(\033)p 1896 1505 2 355 v 1098 1507 801 2 v 1091 1513 813 2 v 1091 1868 2 355 v 1152 1803 a Fe(y)1176 1784 y Ff(\(0\))1175 1813 y(3)p 1121 1687 193 2 v 1121 1760 2 73 v 1135 1737 a Fe(y)1159 1718 y Ff(\(0\))1158 1747 y(2)1202 1737 y Fc(+)r Fe(y)1258 1718 y Ff(\(1\))1257 1747 y(2)p 1312 1760 V 1121 1762 193 2 v 1152 1605 a Fe(y)1176 1586 y Ff(\(0\))1175 1615 y(0)p 1052 1724 67 2 v 1052 1723 a Fd(\033)p 1319 1753 193 2 v 1319 1826 2 73 v 1333 1803 a Fe(y)1357 1784 y Ff(\(1\))1356 1813 y(3)1400 1803 y Fc(+)r Fe(y)1456 1784 y Ff(\(2\))1455 1813 y(3)p 1510 1826 V 1319 1828 193 2 v 1342 1671 a Fe(y)1366 1652 y Ff(\(1\))1365 1681 y(1)1408 1671 y Fc(\))1350 1605 y Fe(y)1374 1586 y Ff(\(1\))1373 1615 y(0)p 1250 1790 67 2 v 1250 1789 a Fd(\033)1548 1737 y Fe(y)1572 1718 y Ff(\(2\))1571 1747 y(2)1548 1671 y Fe(y)1572 1652 y Ff(\(2\))1571 1681 y(1)p 1517 1555 193 2 v 1517 1628 2 73 v 1531 1605 a Fe(y)1555 1586 y Ff(\(2\))1554 1615 y(0)1598 1605 y Fc(+)r Fe(y)1654 1586 y Ff(\(3\))1653 1615 y(0)p 1708 1628 V 1517 1630 193 2 v 1448 1592 67 2 v 1448 1591 a Fd(\033)1746 1803 y Fe(y)1770 1784 y Ff(\(3\))1769 1813 y(3)1746 1737 y Fe(y)1770 1718 y Ff(\(3\))1769 1747 y(2)p 1715 1621 193 2 v 1715 1694 2 73 v 1729 1671 a Fe(y)1753 1652 y Ff(\(3\))1752 1681 y(1)1796 1671 y Fc(+)r Fe(y)1852 1652 y Ff(\(0\))1851 1681 y(1)p 1906 1694 V 1715 1696 193 2 v 1646 1658 67 2 v 1646 1657 a Fd(\033)p 1903 1868 2 355 v 1091 1870 813 2 v 1091 1875 V 1091 2230 2 355 v 1128 2115 179 2 v 1128 2188 2 73 v 1142 2166 a Fe(y)1166 2147 y Ff(\(0\))1165 2175 y(3)1209 2166 y Fc(+)9 b Fb(:)d(:)g(:)p 1305 2188 V 1128 2190 179 2 v 1152 1968 a Fe(y)1176 1949 y Ff(\(0\))1175 1977 y(0)p 1052 2152 67 2 v 1052 2151 a Fd(\033)1350 2034 y Fe(y)1374 2015 y Ff(\(1\))1373 2043 y(1)p 1326 1917 179 2 v 1326 1990 2 73 v 1340 1968 a Fe(y)1364 1949 y Ff(\(1\))1363 1977 y(0)1407 1968 y Fc(+)j Fb(:)d(:)g(:)p 1503 1990 V 1326 1992 179 2 v 1250 1954 67 2 v 1250 1953 a Fd(\033)1548 2100 y Fe(y)1572 2081 y Ff(\(2\))1571 2109 y(2)p 1524 1983 179 2 v 1524 2056 2 73 v 1538 2034 a Fe(y)1562 2015 y Ff(\(2\))1561 2043 y(1)1605 2034 y Fc(+)j Fb(:)d(:)g(:)p 1701 2056 V 1524 2058 179 2 v 1448 2020 67 2 v 1448 2019 a Fd(\033)1746 2166 y Fe(y)1770 2147 y Ff(\(3\))1769 2175 y(3)p 1722 2049 179 2 v 1722 2122 2 73 v 1736 2100 a Fe(y)1760 2081 y Ff(\(3\))1759 2109 y(2)1803 2100 y Fc(+)j Fb(:)d(:)g(:)p 1899 2122 V 1722 2124 179 2 v 1646 2086 67 2 v 1646 2085 a Fd(\033)p 1903 2230 2 355 v 1091 2232 813 2 v 1098 2238 801 2 v 1098 2592 2 355 v 1170 2321 a Fe(y)1193 2325 y Ff(0)1368 2387 y Fe(y)1391 2391 y Ff(1)1566 2453 y Fe(y)1589 2457 y Ff(2)1764 2519 y Fe(y)1787 2523 y Ff(3)p 1896 2592 V 1098 2594 801 2 v eop %%Page: 4 4 4 3 bop 64 117 a Ft(2.)20 b(P)o(erform)13 b(the)h(same)e(op)q(eration)i (within)e(columns)117 166 y(using)i(the)g(results)h(from)e(1.)26 251 y(Examples:)76 336 y Fw(\017)20 b Ft(The)10 b Fl(scatter)e Ft(can)i(b)q(e)g(implemen)o(ted)d(as)j(a)f(scatter)117 386 y(within)16 b(the)i(column)d(con)o(taining)g(the)i(ro)q(ot,)g(fol-) 117 436 y(lo)o(w)o(ed)i(b)o(y)g(indep)q(enden)o(t)h(scatters)h(within)e (eac)o(h)117 486 y(ro)o(w.)25 b(The)17 b(new)f(ro)q(ot)g(for)g(the)h (latter)f(op)q(eration)117 535 y(will)10 b(b)q(e)i(that)g(no)q(de)f(in) g(the)h(ro)o(w)f(whic)o(h)g(lies)h(in)f(the)117 585 y(same)i(column)g (as)h(the)g(original)e(ro)q(ot.)76 653 y Fw(\017)20 b Ft(The)g Fl(collect)d Ft(can)i(b)q(e)g(implemen)o(ted)e(as)i(a)g(col-) 117 703 y(lect)c(within)f(ro)o(ws)h(follo)o(w)o(ed)e(b)o(y)h(a)h (collect)g(of)f(the)117 752 y(results)h(within)f(columns.)-57 837 y Fl(T)l(emplate)g(2.)64 922 y Ft(1.)20 b(P)o(erform)29 b(the)i(\014rst)f(stage)g(of)g(an)f(op)q(eration)117 972 y(within)13 b(ro)o(ws.)64 1039 y(2.)20 b(P)o(erform)12 b(the)h(op)q(eration)f(within)g(columns)f(using)117 1089 y(the)k(results)g(from)d(1.)64 1157 y(3.)20 b(P)o(erform)h(the)i (second)f(stage)h(of)e(an)g(op)q(eration)117 1206 y(within)13 b(ro)o(ws)i(using)e(the)i(results)g(of)e(2.)26 1291 y(Examples:)76 1376 y Fw(\017)20 b Ft(The)i Fl(broadcast)e Ft(can)i(b)q(e)g(implemen)o (ted)d(as)i(a)117 1426 y(scatter)15 b(within)d(ro)o(ws,)h(follo)o(w)o (ed)e(b)o(y)i(a)g(broadcast)117 1476 y(of)h(the)h(results)h(within)e (columns,)e(follo)o(w)o(ed)h(b)o(y)h(a)117 1526 y(collect)g(within)g (ro)o(ws.)76 1593 y Fw(\017)20 b Ft(A)g Fl(com)o(bine-to-)o(all)15 b Ft(can)20 b(b)q(e)f(implemen)o(ted)e(as)117 1643 y(a)j(distributed)h (buc)o(k)o(et)f(com)o(bine)f(within)g(ro)o(ws,)117 1693 y(follo)o(w)o(ed)9 b(b)o(y)i(a)f(com)o(bine-to-all)e(within)i(columns,) 117 1743 y(follo)o(w)o(ed)j(b)o(y)g(a)h(buc)o(k)o(et)g(collect)h (within)e(ro)o(ws.)-57 1828 y(F)m(or)18 b(the)i(op)q(eration)e(within)g (columns,)h(either)g(a)g(short)g(or)-57 1877 y(long)d(v)o(ector)i (strategy)g(can)g(b)q(e)g(emplo)o(y)o(ed,)e(dep)q(ending)h(on)-57 1927 y(whether)d(the)f(\014rst)g(step)g(reduces)i(the)e(v)o(ector)g (length)f(to)h(the)-57 1977 y(p)q(oin)o(t)g(where)i(latency)g (dominates.)-7 2027 y(A)22 b(simple)e(extension)j(of)f(the)g(ab)q(o)o (v)o(e)g(approac)o(h)g(leads)-57 2077 y(to)27 b(general)g(h)o(ybrid)g (algorithms)d(for)j(m)o(ultidim)o(ensional)-57 2127 y(meshes.)i(If)18 b(the)g(no)q(des)g(are)g(view)o(ed)g(as)g(a)f(higher)h(dimen-)-57 2177 y(sional)d(mesh)h(than)h(the)g(ph)o(ysical)f(mesh,)g(di\013eren)o (t)h(strate-)-57 2227 y(gies)10 b(can)g(b)q(e)g(emplo)o(y)o(ed)e(in)h (the)i(di\013eren)o(t)g(dimensions)d(of)h(this)-57 2276 y(logical)15 b(mesh.)26 b(Strategies)17 b(that)g(successiv)o(ely)h (reduce)h(the)-57 2326 y(v)o(ector)c(lengths)f(during)f(initial)f (stages)j(will)d(reduce)j(o)o(v)o(erall)-57 2376 y(time)h(due)i(to)g (bandwidth.)29 b(Ev)o(en)o(tually)m(,)17 b(v)o(ectors)h(b)q(ecome)-57 2426 y(small)9 b(enough)h(and)h(strategies)h(that)f(reduce)h(latency)f (\(short)-57 2476 y(v)o(ector)k(strategies\))g(b)q(ecome)f(more)f (appropriate.)-7 2526 y(Ph)o(ysical)g(linear)g(arra)o(ys)h(in)f(the)i (net)o(w)o(ork)f(lik)o(e)e(ro)o(ws)i(and)-57 2576 y(columns)j(are)i(no) o(w)f(view)o(ed)g(as)g(logical)f(m)o(ultidim)o(ensional)-57 2626 y(arra)o(ys)i(based)g(on)f(the)h(factorization)e(of)h(the)h(ro)o (w)g(and/or)-57 2675 y(column)k(dimension.)49 b(This)24 b(means)g(that)h(during)f(later)-57 2725 y(stages)17 b(net)o(w)o(ork)f(con\015icts)h(will)e(start)h(o)q(ccurring.)26 b(The)16 b(ef-)-57 2775 y(fects)f(of)e(this)h(can)g(b)q(e)g(reduced)h (b)o(y)f(an)f(appropriate)h(c)o(hoice,)1013 117 y(dep)q(ending)h(on)e (the)i(v)o(ector)g(length,)f(on)g(the)h(n)o(um)o(b)q(er)e(of)h(di-)1013 166 y(mensions,)f(on)h(the)h(order)g(of)f(the)g(dimensions,)f(and)h(on) g(the)1013 216 y(strategy)f(for)f(eac)o(h)h(dimension.)j(F)m(or)d (example,)e(alternating)1013 266 y(ph)o(ysical)16 b(directions)h (during)f(stages)h(that)g(utilize)f(a)g(strat-)1013 316 y(egy)i(that)g(shortens)h(the)f(v)o(ector)h(lengths)f(greatly)g (reduces)1013 366 y(the)c(e\013ects)i(of)d(net)o(w)o(ork)i(con\015icts) f(during)g(later)g(stages.)1063 417 y(This)26 b(approac)o(h)g(to)g(h)o (ybrids)g(is)g(illustrated)g(for)g(the)1013 466 y(broadcast)18 b(in)g(Fig.)e(3)i(for)f(12)h(no)q(des)g(when)h(they)f(are)g(log-)1013 516 y(ically)f(view)o(ed)h(as)h(a)e(2)12 b Fw(\002)h Ft(2)f Fw(\002)g Ft(3)18 b(mesh.)31 b(During)17 b(the)i(\014rst)1013 566 y(stage,)j(a)f(scatter)h(is)f(emplo)o(y)o(ed)e(in)h(the)i(\014rst)f (dimension,)1013 616 y(and)e(no)h(net)o(w)o(ork)g(con\015icts)g(o)q (ccur.)37 b(During)19 b(the)h(second)1013 666 y(stage,)c(again)e(a)h (scatter)i(o)q(ccurs,)g(this)f(time)e(in)h(the)h(second)1013 715 y(dimension.)g(In)d(this)g(second)i(step,)f(net)o(w)o(ork)f (con\015icts)h(ma)o(y)1013 765 y(o)q(ccur,)k(dep)q(ending)g(on)f (details)g(of)g(the)h(ph)o(ysical)e(net)o(w)o(ork.)1013 815 y(Finally)m(,)10 b(the)i(v)o(ector)h(is)f(assumed)g(to)g(b)q(e)g (short)h(enough)f(that)1013 865 y(a)17 b(minim)n(um)c(spanning)j(tree)j (broadcast)e(within)g(the)h(\014nal)1013 915 y(dimension)d(is)h (appropriate.)25 b(Net)o(w)o(ork)17 b(con\015icts)g(ma)o(y)e(o)q(c-) 1013 964 y(cur,)d(but)f(the)h(v)o(ectors)g(are)g(no)o(w)f(1/4)f(of)g (the)i(original)d(length.)1013 1014 y(The)i(pro)q(cess)i(is)d (completed)g(b)o(y)h(a)f(collect)h(corresp)q(onding)h(to)1013 1064 y(the)h(second)h(scatter)h(follo)o(w)o(ed)c(b)o(y)i(a)g(collect)g (corresp)q(onding)1013 1114 y(to)j(the)i(\014rst)f(scatter.)29 b Fn(We)18 b(emphasize)g(that)f(this)h(example)1013 1164 y(is)c(me)n(ant)h(only)h(to)f(il)r(lustr)n(ate)e(the)i(me)n(chanism.) 1063 1215 y Ft(In)i(practice,)i(our)e(implemen)o(tatio)o(ns)e(use)j (highly)e(accu-)1013 1264 y(rate)d(mo)q(dels)f(of)h(the)h(exp)q(ected)h (execution)f(time)e(of)g(the)i(dif-)1013 1314 y(feren)o(t)h(c)o (hoices,)f(in)g(com)o(bination)d(with)j(a)g(c)o(heap)g(but)h(e\013ec-) 1013 1364 y(tiv)o(e)k(heuristic,)i(to)f(mak)o(e)e(the)i(sp)q(eci\014c)g (c)o(hoice)g(of)f(h)o(ybrid)1013 1414 y(strategy)m(,)g(based)g(on)f (the)h(v)o(ector)g(length,)g(the)g(n)o(um)o(b)q(er)f(of)1013 1464 y(pro)q(cessors,)e(the)f(history)f(of)f(the)i(h)o(ybrid,)e(and)h (a)g(few)g(para-)1013 1514 y(meters)g(that)g(describ)q(e)h(the)g(comm)o (unicatio)o(n)c(net)o(w)o(ork.)1063 1564 y(It)k(should)f(b)q(e)i(noted) f(that)g(this)g(approac)o(h)g(has)g(a)f(hea)o(vy)1013 1614 y(dep)q(endence)i(on)d(the)h(in)o(teger)g(factorization)f(of)f (the)i(dimen-)1013 1664 y(sions)f(of)g(the)h(ph)o(ysical)f(mesh.)k(As)d (a)f(result,)h(if)f(one)g(or)h(b)q(oth)1013 1714 y(of)c(these)i (dimensions)e(are)h(prime,)f(or)h(ha)o(v)o(e)g(only)f(a)g(few)h(large) 1013 1764 y(in)o(teger)i(factors,)g(the)g(h)o(ybrid)g(algorithms)d (will)i(not)g(b)q(e)i(v)o(ery)1013 1814 y(e\013ectiv)o(e.)1013 1975 y Fs(6)56 b(Exp)r(erime)o(n)n(tal)16 b(Results)1063 2078 y Ft(In)24 b(this)g(section,)k(w)o(e)c(presen)o(t)i(exp)q(erimen)o (tal)e(results)1013 2127 y(from)d(a)h(complete)g(implemen)o(tation)e (of)i(the)h(library)f(for)1013 2177 y(the)13 b(case)h(of)e(collectiv)o (e)h(comm)o(unication)d(within)i(all)g(no)q(des.)1013 2227 y(The)j(exp)q(erimen)o(ts)g(w)o(ere)h(p)q(erformed)e(on)h(a)g (512-no)q(de)f(In)o(tel)1013 2277 y(P)o(aragon,)c(running)f(under)i (OSF)g(release)g(R1.1.)16 b(W)m(e)9 b(presen)o(t)1013 2327 y(data)14 b(from)f(t)o(w)o(o)h(di\013eren)o(t)i(ph)o(ysical)e (mesh)g(partitions:)19 b(the)1013 2376 y(case)h(of)e(a)h(16)12 b Fw(\002)h Ft(32)18 b(mesh,)i(whic)o(h)f(has)g(the)g(considerable)1013 2426 y(adv)n(an)o(tage)14 b(of)g(p)q(o)o(w)o(er-of-t)o(w)o(o)g (dimensions,)f(and)i(a)f(15)9 b Fw(\002)h Ft(30)1013 2476 y(mesh,)21 b(whic)o(h)f(deviates)h(signi\014can)o(tly)f(from)e(a)j (p)q(o)o(w)o(er-of-)1013 2526 y(t)o(w)o(o)14 b(mesh.)21 b(T)m(o)14 b(highligh)o(t)g(the)h(b)q(ene\014ts)i(of)e(the)g(h)o(ybrid) g(al-)1013 2576 y(gorithms,)e(w)o(e)i(presen)o(t)h(data)e(in)g(T)m (able)g(2)h(for)f(three)i(v)o(ector)1013 2626 y(lengths)11 b(that)g(sho)o(ws)h(the)f(time)f(of)h(the)g(di\013eren)o(t)h (algorithms)1013 2675 y(for)g(short,)h(medium,)c(and)j(long)g(v)o (ectors.)19 b(The)13 b(results)g(for)f(a)1013 2725 y(wide)f(range)h(of) f(v)o(ector)h(lengths)g(are)g(presen)o(ted)h(in)e(Figure)h(4.)1013 2775 y(These)h(results)h(indicate)e(that)h(h)o(ybrid)f(algorithms)e(p)q (erform)p eop %%Page: 5 5 5 4 bop 73 318 a Fc(no)q(de)p 212 331 2 46 v 273 320 a(0)116 b(1)g(2)g(3)g(4)g(5)g(6)g(7)g(8)g(9)107 b(10)97 b(11)p 13 333 1900 2 v 38 457 a(step)13 b(1)38 503 y(scatter)p 212 603 2 270 v 263 429 a Fb(x)285 433 y Ff(0)263 474 y Fb(x)285 478 y Ff(1)263 519 y Fb(x)285 523 y Ff(2)263 564 y Fb(x)285 568 y Ff(3)p 259 490 49 2 v 259 580 2 90 v 305 580 V 259 582 49 2 v 305 536 113 2 v 376 535 a Fd(-)p 13 605 1900 2 v 38 729 a Fc(step)g(2)38 774 y(scatter)p 212 875 2 270 v 263 701 a Fb(x)285 705 y Ff(0)263 746 y Fb(x)285 750 y Ff(1)398 791 y Fb(x)420 795 y Ff(2)398 836 y Fb(x)420 840 y Ff(3)p 259 716 49 2 v 259 761 2 45 v 305 761 V 259 763 49 2 v 394 806 V 394 851 2 45 v 440 851 V 394 853 49 2 v 305 740 248 2 v 511 739 a Fd(-)p 440 830 V 646 829 a(-)p 13 876 1900 2 v 38 978 a Fc(step)g(3)38 1023 y(MST)38 1069 y(b)q(cast)p 212 1146 2 270 v 263 972 a Fb(x)285 976 y Ff(0)533 1017 y Fb(x)555 1021 y Ff(1)398 1062 y Fb(x)420 1066 y Ff(2)668 1107 y Fb(x)690 1111 y Ff(3)p 259 943 49 2 v 259 988 2 45 v 305 988 V 259 990 49 2 v 305 967 1058 2 v 1321 966 a Fd(-)p 394 1033 49 2 v 394 1078 2 45 v 440 1078 V 394 1080 49 2 v 440 1057 1058 2 v 1456 1056 a(-)p 529 988 49 2 v 529 1033 2 45 v 575 1033 V 529 1035 49 2 v 575 1012 1058 2 v 1591 1011 a(-)p 664 1078 49 2 v 664 1123 2 45 v 710 1123 V 664 1125 49 2 v 710 1102 1058 2 v 1726 1101 a(-)p 13 1148 1900 2 v 38 1222 a Fc(step)g(4)38 1267 y(MST)38 1313 y(b)q(cast)38 1359 y(\(con)o(t.\))p 212 1418 2 270 v 263 1244 a Fb(x)285 1248 y Ff(0)533 1289 y Fb(x)555 1293 y Ff(1)398 1334 y Fb(x)420 1338 y Ff(2)668 1379 y Fb(x)690 1383 y Ff(3)1343 1244 y Fb(x)1365 1248 y Ff(0)1613 1289 y Fb(x)1635 1293 y Ff(1)1478 1334 y Fb(x)1500 1338 y Ff(2)1748 1379 y Fb(x)1770 1383 y Ff(3)p 259 1215 49 2 v 259 1260 2 45 v 305 1260 V 259 1262 49 2 v 305 1239 518 2 v 781 1238 a Fd(-)p 394 1305 49 2 v 394 1350 2 45 v 440 1350 V 394 1352 49 2 v 440 1329 518 2 v 916 1328 a(-)p 529 1260 49 2 v 529 1305 2 45 v 575 1305 V 529 1307 49 2 v 575 1284 518 2 v 1051 1283 a(-)p 664 1350 49 2 v 664 1395 2 45 v 710 1395 V 664 1397 49 2 v 710 1374 518 2 v 1186 1373 a(-)p 13 1420 1900 2 v 38 1544 a Fc(step)g(5)38 1589 y(collect)p 212 1689 2 270 v 263 1515 a Fb(x)285 1519 y Ff(0)533 1560 y Fb(x)555 1564 y Ff(1)398 1605 y Fb(x)420 1609 y Ff(2)668 1650 y Fb(x)690 1654 y Ff(3)p 259 1486 49 2 v 259 1531 2 45 v 305 1531 V 259 1533 49 2 v 305 1510 225 2 v 489 1509 a Fd(-)p 394 1576 49 2 v 394 1621 2 45 v 440 1621 V 394 1623 49 2 v 440 1600 225 2 v 624 1599 a(-)p 529 1531 49 2 v 529 1576 2 45 v 575 1576 V 529 1578 49 2 v 305 1555 225 2 v 305 1554 a(\033)p 664 1621 49 2 v 664 1666 2 45 v 710 1666 V 664 1668 49 2 v 440 1645 225 2 v 440 1644 a(\033)803 1515 y Fb(x)825 1519 y Ff(0)1073 1560 y Fb(x)1095 1564 y Ff(1)938 1605 y Fb(x)960 1609 y Ff(2)1208 1650 y Fb(x)1230 1654 y Ff(3)p 799 1486 49 2 v 799 1531 2 45 v 845 1531 V 799 1533 49 2 v 845 1510 225 2 v 1029 1509 a Fd(-)p 934 1576 49 2 v 934 1621 2 45 v 980 1621 V 934 1623 49 2 v 980 1600 225 2 v 1164 1599 a(-)p 1069 1531 49 2 v 1069 1576 2 45 v 1115 1576 V 1069 1578 49 2 v 845 1555 225 2 v 845 1554 a(\033)p 1204 1621 49 2 v 1204 1666 2 45 v 1250 1666 V 1204 1668 49 2 v 980 1645 225 2 v 980 1644 a(\033)1343 1515 y Fb(x)1365 1519 y Ff(0)1613 1560 y Fb(x)1635 1564 y Ff(1)1478 1605 y Fb(x)1500 1609 y Ff(2)1748 1650 y Fb(x)1770 1654 y Ff(3)p 1339 1486 49 2 v 1339 1531 2 45 v 1385 1531 V 1339 1533 49 2 v 1385 1510 225 2 v 1569 1509 a Fd(-)p 1474 1576 49 2 v 1474 1621 2 45 v 1520 1621 V 1474 1623 49 2 v 1520 1600 225 2 v 1704 1599 a(-)p 1609 1531 49 2 v 1609 1576 2 45 v 1655 1576 V 1609 1578 49 2 v 1385 1555 225 2 v 1385 1554 a(\033)p 1744 1621 49 2 v 1744 1666 2 45 v 1790 1666 V 1744 1668 49 2 v 1520 1645 225 2 v 1520 1644 a(\033)p 13 1691 1900 2 v 38 1815 a Fc(step)g(6)38 1861 y(collect)p 212 1961 2 270 v 263 1787 a Fb(x)285 1791 y Ff(0)533 1832 y Fb(x)555 1836 y Ff(1)398 1877 y Fb(x)420 1881 y Ff(2)668 1922 y Fb(x)690 1926 y Ff(3)533 1787 y Fb(x)555 1791 y Ff(0)263 1832 y Fb(x)285 1836 y Ff(1)668 1877 y Fb(x)690 1881 y Ff(2)398 1922 y Fb(x)420 1926 y Ff(3)p 259 1758 49 2 v 259 1848 2 90 v 305 1848 V 259 1850 49 2 v 305 1804 90 2 v 354 1803 a Fd(-)p 394 1848 49 2 v 394 1938 2 90 v 440 1938 V 394 1940 49 2 v 305 1894 90 2 v 305 1893 a(\033)p 529 1758 49 2 v 529 1848 2 90 v 575 1848 V 529 1850 49 2 v 575 1804 90 2 v 624 1803 a(-)p 664 1848 49 2 v 664 1938 2 90 v 710 1938 V 664 1940 49 2 v 575 1894 90 2 v 575 1893 a(\033)803 1787 y Fb(x)825 1791 y Ff(0)1073 1832 y Fb(x)1095 1836 y Ff(1)938 1877 y Fb(x)960 1881 y Ff(2)1208 1922 y Fb(x)1230 1926 y Ff(3)1073 1787 y Fb(x)1095 1791 y Ff(0)803 1832 y Fb(x)825 1836 y Ff(1)1208 1877 y Fb(x)1230 1881 y Ff(2)938 1922 y Fb(x)960 1926 y Ff(3)p 799 1758 49 2 v 799 1848 2 90 v 845 1848 V 799 1850 49 2 v 845 1804 90 2 v 894 1803 a Fd(-)p 934 1848 49 2 v 934 1938 2 90 v 980 1938 V 934 1940 49 2 v 845 1894 90 2 v 845 1893 a(\033)p 1069 1758 49 2 v 1069 1848 2 90 v 1115 1848 V 1069 1850 49 2 v 1115 1804 90 2 v 1164 1803 a(-)p 1204 1848 49 2 v 1204 1938 2 90 v 1250 1938 V 1204 1940 49 2 v 1115 1894 90 2 v 1115 1893 a(\033)1343 1787 y Fb(x)1365 1791 y Ff(0)1613 1832 y Fb(x)1635 1836 y Ff(1)1478 1877 y Fb(x)1500 1881 y Ff(2)1748 1922 y Fb(x)1770 1926 y Ff(3)1613 1787 y Fb(x)1635 1791 y Ff(0)1343 1832 y Fb(x)1365 1836 y Ff(1)1748 1877 y Fb(x)1770 1881 y Ff(2)1478 1922 y Fb(x)1500 1926 y Ff(3)p 1339 1758 49 2 v 1339 1848 2 90 v 1385 1848 V 1339 1850 49 2 v 1385 1804 90 2 v 1434 1803 a Fd(-)p 1474 1848 49 2 v 1474 1938 2 90 v 1520 1938 V 1474 1940 49 2 v 1385 1894 90 2 v 1385 1893 a(\033)p 1609 1758 49 2 v 1609 1848 2 90 v 1655 1848 V 1609 1850 49 2 v 1655 1804 90 2 v 1704 1803 a(-)p 1744 1848 49 2 v 1744 1938 2 90 v 1790 1938 V 1744 1940 49 2 v 1655 1894 90 2 v 1655 1893 a(\033)p 13 1963 1900 2 v 77 2107 a Fc(\014nal)p 212 2233 2 270 v 263 2059 a Fb(x)285 2063 y Ff(0)263 2104 y Fb(x)285 2108 y Ff(1)263 2149 y Fb(x)285 2153 y Ff(2)263 2194 y Fb(x)285 2198 y Ff(3)398 2059 y Fb(x)420 2063 y Ff(0)398 2104 y Fb(x)420 2108 y Ff(1)398 2149 y Fb(x)420 2153 y Ff(2)398 2194 y Fb(x)420 2198 y Ff(3)533 2059 y Fb(x)555 2063 y Ff(0)533 2104 y Fb(x)555 2108 y Ff(1)533 2149 y Fb(x)555 2153 y Ff(2)533 2194 y Fb(x)555 2198 y Ff(3)668 2059 y Fb(x)690 2063 y Ff(0)668 2104 y Fb(x)690 2108 y Ff(1)668 2149 y Fb(x)690 2153 y Ff(2)668 2194 y Fb(x)690 2198 y Ff(3)803 2059 y Fb(x)825 2063 y Ff(0)803 2104 y Fb(x)825 2108 y Ff(1)803 2149 y Fb(x)825 2153 y Ff(2)803 2194 y Fb(x)825 2198 y Ff(3)938 2059 y Fb(x)960 2063 y Ff(0)938 2104 y Fb(x)960 2108 y Ff(1)938 2149 y Fb(x)960 2153 y Ff(2)938 2194 y Fb(x)960 2198 y Ff(3)1073 2059 y Fb(x)1095 2063 y Ff(0)1073 2104 y Fb(x)1095 2108 y Ff(1)1073 2149 y Fb(x)1095 2153 y Ff(2)1073 2194 y Fb(x)1095 2198 y Ff(3)1208 2059 y Fb(x)1230 2063 y Ff(0)1208 2104 y Fb(x)1230 2108 y Ff(1)1208 2149 y Fb(x)1230 2153 y Ff(2)1208 2194 y Fb(x)1230 2198 y Ff(3)1343 2059 y Fb(x)1365 2063 y Ff(0)1343 2104 y Fb(x)1365 2108 y Ff(1)1343 2149 y Fb(x)1365 2153 y Ff(2)1343 2194 y Fb(x)1365 2198 y Ff(3)1478 2059 y Fb(x)1500 2063 y Ff(0)1478 2104 y Fb(x)1500 2108 y Ff(1)1478 2149 y Fb(x)1500 2153 y Ff(2)1478 2194 y Fb(x)1500 2198 y Ff(3)1613 2059 y Fb(x)1635 2063 y Ff(0)1613 2104 y Fb(x)1635 2108 y Ff(1)1613 2149 y Fb(x)1635 2153 y Ff(2)1613 2194 y Fb(x)1635 2198 y Ff(3)1748 2059 y Fb(x)1770 2063 y Ff(0)1748 2104 y Fb(x)1770 2108 y Ff(1)1748 2149 y Fb(x)1770 2153 y Ff(2)1748 2194 y Fb(x)1770 2198 y Ff(3)-57 2349 y Ft(Figure)19 b(3:)27 b(Broadcast)20 b(h)o(ybrid:)27 b(In)19 b(Step)g(1)g(and)f(2,)i (scatters)g(within)e(subgroups)i(of)e(t)o(w)o(o)g(no)q(des)h(are)h(p)q (erformed.)32 b(Next,)-57 2399 y(separate)16 b(MST)e(broadcasts)h (within)f(subgroups)h(of)f(three)h(no)q(des)g(are)g(p)q(erformed)f(in)g (Step)h(3)f(and)g(4.)20 b(Finally)m(,)11 b(sim)o(ultaneous)-57 2448 y(collects)h(within)f(subgroups)h(of)f(t)o(w)o(o)g(complete)g(the) h(broadcast.)18 b(Except)12 b(for)f(Step)i(1)e(and)g(6,)g(limited)e (net)o(w)o(ork)j(con\015icts)g(o)q(ccur.)-57 2498 y(The)i(strategy)f(b) q(ene\014ts)i(from)d(the)h(fact)h(that)f(net)o(w)o(ork)g(con\015ict)h (is)f(least)g(when)h(the)f(v)o(ectors)i(sen)o(t)f(are)f(long.)k(Notice) d(that)f(this)-57 2548 y(is)i(one)g(of)f(man)o(y)f(p)q(ossible)j (strategies:)21 b(A)15 b(MST)g(broadcast)g(in)o(v)o(olving)e(all)h(12)g (no)q(des;)i(Scatter)g(in)o(v)o(olving)d(four)h(no)q(des,)i(MST)-57 2598 y(broadcast)e(in)g(groups)g(of)f(three,)i(collect)f(in)g(groups)g (of)f(four;)g(etc.)p eop %%Page: 6 6 6 5 bop -57 117 a Ft(b)q(etter)20 b(than)f(short)g(and)g(long)e(v)o (ector)j(algorithms)c(across)-57 166 y(the)i(range)f(of)g(v)o(ector)h (lengths.)28 b(In)17 b(a)g(v)o(ery)h(few)f(cases)i(the)-57 216 y(short)12 b(or)f(long)f(v)o(ector)i(algorithm)c(p)q(erforms)j (sligh)o(tly)f(b)q(etter)-57 266 y(than)k(the)g(h)o(ybrid)g(algorithm.) h(W)m(e)e(w)o(ould)g(lik)o(e)g(to)h(men)o(tion)-57 316 y(that)e(these)h(results)g(are)f(based)g(on)g(the)g(preliminary)e (heuris-)-57 366 y(tics)k(for)f(determining)f(h)o(ybrid)h(algorithms,)d (whic)o(h)j(are)h(still)-57 415 y(b)q(eing)g(tuned.)p -57 522 1005 2 v -58 571 2 50 v 181 571 V 372 571 V 381 571 V 553 556 a(size)h(in)e(b)o(ytes)p 947 571 V -57 573 1005 2 v -58 623 2 50 v -29 608 a(Op)q(eration)p 181 623 V 53 w(Metho)q(d)p 372 623 V 381 623 V 96 w(256)p 566 623 V 91 w(262144)p 752 623 V 54 w(1048576)p 947 623 V -57 625 1005 2 v -57 634 V -58 684 2 50 v 181 684 V 181 684 V 231 669 a(short)p 372 684 V 381 684 V 83 w(0.00128)p 566 684 V 47 w(0.12401)p 752 684 V 53 w(0.48549)p 947 684 V 182 686 766 2 v -58 734 2 50 v -29 719 a(Broadcast)p 181 734 V 181 734 V 87 w(long)p 372 734 V 381 734 V 90 w(0.02939)p 566 734 V 47 w(0.05426)p 752 734 V 53 w(0.11965)p 947 734 V 182 736 766 2 v -58 784 2 50 v 181 784 V 181 784 V 218 769 a(h)o(ybrid)p 372 784 V 381 784 V 70 w(0.00139)p 566 784 V 47 w(0.03932)p 752 784 V 53 w(0.09957)p 947 784 V -57 786 1005 2 v -58 835 2 50 v 181 835 V 181 835 V 231 820 a(short)p 372 835 V 381 835 V 83 w(0.00338)p 566 835 V 47 w(0.07789)p 752 835 V 53 w(0.29512)p 947 835 V 182 837 766 2 v -58 885 2 50 v -1 870 a(Collect)p 181 885 V 181 885 V 113 w(long)p 372 885 V 381 885 V 90 w(0.02672)p 566 885 V 47 w(0.04358)p 752 885 V 53 w(0.08838)p 947 885 V 182 887 766 2 v -58 935 2 50 v 181 935 V 181 935 V 218 920 a(h)o(ybrid)p 372 935 V 381 935 V 70 w(0.00355)p 566 935 V 47 w(0.03074)p 752 935 V 53 w(0.07469)p 947 935 V -57 937 1005 2 v -58 987 2 50 v 2 972 a(Global)p 181 987 V 181 987 V 107 w(short)p 372 987 V 381 987 V 83 w(0.00676)p 566 987 V 47 w(0.15933)p 752 987 V 53 w(0.60273)p 947 987 V 182 988 766 2 v -58 1036 2 50 v -32 1021 a(Sum-to-all)p 181 1036 V 181 1036 V 79 w(long)p 372 1036 V 381 1036 V 90 w(0.05547)p 566 1036 V 47 w(0.09729)p 752 1036 V 53 w(0.19747)p 947 1036 V 182 1038 766 2 v -58 1086 2 50 v 181 1086 V 181 1086 V 218 1071 a(h)o(ybrid)p 372 1086 V 381 1086 V 70 w(0.00696)p 566 1086 V 47 w(0.07251)p 752 1086 V 53 w(0.17360)p 947 1086 V -57 1088 1005 2 v -58 1138 2 50 v 181 1138 V 181 1138 V 231 1123 a(short)p 372 1138 V 381 1138 V 83 w(0.00119)p 566 1138 V 47 w(0.03927)p 752 1138 V 53 w(0.14828)p 947 1138 V 182 1139 766 2 v -58 1187 2 50 v -2 1172 a(Scatter)p 181 1187 V 181 1187 V 113 w(long)p 372 1187 V 381 1187 V 90 w(0.00269)p 566 1187 V 47 w(0.01161)p 752 1187 V 53 w(0.03431)p 947 1187 V 182 1189 766 2 v -58 1237 2 50 v 181 1237 V 181 1237 V 218 1222 a(h)o(ybrid)p 372 1237 V 381 1237 V 70 w(0.00125)p 566 1237 V 47 w(0.01139)p 752 1237 V 53 w(0.03506)p 947 1237 V -57 1239 1005 2 v -57 1357 a(T)m(able)k(2:)26 b(Time)17 b(\(in)h(sec.\))32 b(for)17 b(the)i(di\013eren)o(t)g(op)q(erations)-57 1407 y(and)c(algorithms)d(for)j(short,)g(in)o(termediate,)f(and)h(long)f(v)o (ec-)-57 1457 y(tor)d(lengths.)17 b(All)11 b(results)h(are)f(for)g(a)f (16)s Fw(\002)s Ft(32)h(mesh)f(of)h(no)q(des.)-57 1666 y Fs(7)56 b(Other)18 b(algorithms)-7 1767 y Ft(It)e(should)f(b)q(e)i (noted)f(that)g(for)f(some)g(of)g(the)h(comm)o(uni-)-57 1817 y(cations,)c(optimal)e(algorithms)h(for)h(long)f(v)o(ectors)j (exist)f(that)-57 1867 y(in)i(theory)h(outp)q(erform)e(our)h(approac)o (h.)23 b(F)m(or)14 b(example,)g(on)-57 1917 y(h)o(yp)q(ercub)q(es)23 b(Ho)d(and)h(Johnsson's)g(EDST)f(broadcast)h([4])-57 1967 y(will)10 b(outp)q(erform)g(our)h(scatter/collect)i(broadcast)f(b) o(y)f(a)f(fac-)-57 2017 y(tor)20 b(of)g(t)o(w)o(o)f(for)h(long)f(v)o (ectors.)38 b(Ho)o(w)o(ev)o(er,)22 b(it)e(is)g(our)g(ex-)-57 2066 y(p)q(erience)d(that)e(suc)o(h)h(pip)q(elined)f(algorithms)e(are)i (generally)-57 2116 y(di\016cult)f(to)h(implemen)o(t)d(and)j(are)g (extremely)f(arc)o(hitecture)-57 2166 y(dep)q(enden)o(t.)31 b(Indeed,)19 b(suc)o(h)f(theoretically)f(sup)q(erior)i(algo-)-57 2216 y(rithms)c(are)h(often)f(outp)q(erformed)h(b)o(y)f(simpler)f (algorithms)-57 2266 y(\(e.g.)20 b(scatter-collect)c(algorithm\))c (when)j(implemen)o(ted)d(on)-57 2315 y(real)20 b(systems.)36 b(This)20 b(has)g(b)q(een)h(our)f(exp)q(erience)i(on)e(the)-57 2365 y(T)m(ouc)o(hstone)11 b(Delta)f(and)g(the)h(In)o(tel)f(P)o (aragon,)g(making)e(these)-57 2415 y(approac)o(hes)16 b(inappropriate)f(for)g(general)g(library)f(dev)o(elop-)-57 2465 y(men)o(t.)-57 2624 y Fs(8)56 b(Curren)n(t)19 b(Status)g(and)g(F) -5 b(uture)19 b(W)-5 b(ork)-7 2725 y Ft(W)m(e)10 b(ha)o(v)o(e)h (implemen)o(ted)d(a)j(complete)f(library)g(for)h(the)g(In-)-57 2775 y(tel)k(P)o(aragon,)e(based)j(on)e(the)h(describ)q(ed)i(tec)o (hniques.)k(This)1013 117 y(library)12 b(exhibits)h(considerably)g(b)q (etter)i(p)q(erformance)e(than)1013 166 y(an)o(y)23 b(other)h (collectiv)o(e)f(comm)o(unication)d(library)j(for)g(the)1013 216 y(P)o(aragon)15 b(w)o(e)h(ha)o(v)o(e)f(seen,)i(and)f(has)g (expanded)g(functional-)1013 266 y(it)o(y)m(.)f(As)10 b(of)f(this)g(writing,)g(the)i(library)d(only)h(allo)o(ws)f(collectiv)o (e)1013 316 y(comm)o(unicatio)o(ns)k(that)i(in)o(v)o(olv)o(e)e(all)h (no)q(des.)1063 366 y(T)m(o)d(p)q(ort)h(the)h(library)e(b)q(et)o(w)o (een)i(platforms,)d(or,)i(more)f(im-)1013 416 y(p)q(ortan)o(tly)m(,)f (to)h(tune)h(it)f(for)g(new)h(op)q(erating)f(system)g(releases,)1013 465 y(it)j(su\016ces)i(to)f(en)o(ter)h(a)e(few)h(parameters)g(that)g (describ)q(e)h(the)1013 515 y(latency)m(,)j(bandwidth,)g(and)g (computation)e(c)o(haracteristics)1013 565 y(of)c(the)i(system.)k (Indeed,)c(w)o(e)f(p)q(orted)h(the)g(library)f(from)e(the)1013 615 y(original)17 b(v)o(ersion,)k(whic)o(h)e(w)o(as)h(designed)g(for)f (the)h(T)m(ouc)o(h-)1013 665 y(stone)f(Delta,)f(to)h(the)g(P)o(aragon)e (b)o(y)h(c)o(hanging)g(only)g(these)1013 714 y(parameters.)1063 764 y(F)m(or)13 b(completeness,)i(w)o(e)f(also)f(ha)o(v)o(e)h(a)g(v)o (ersion)g(tuned)h(for)1013 814 y(the)i(T)m(ouc)o(hstone)h(Delta)e(mesh) h(computer,)f(and)h(a)g(v)o(ersion)1013 864 y(for)12 b(the)i(iPSC/860)e(that)h(has)g(the)g(same)f(functionalit)o(y)m(,)f (but)1013 914 y(uses)k(algorithms)e(more)g(appropriate)i(for)f(h)o(yp)q (ercub)q(es)i(\(in-)1013 964 y(cluding)j(the)h(EDST)g(broadcast\).)36 b(A)19 b(v)o(ersion)h(tuned)g(for)1013 1013 y(the)d(SUNMOS)h(op)q (erating)e(system)h(dev)o(elop)q(ed)g(at)g(Sandia)1013 1063 y(National)12 b(Lab)q(oratory)i(is)g(also)f(under)i(dev)o(elopmen) o(t.)1063 1113 y(There)f(is)g(a)f(strong)g(applications)g(need)h(for)f (library)g(rou-)1013 1163 y(tines)j(that)f(supp)q(ort)h(collectiv)o(e)f (comm)o(unication)d(within)i(a)1013 1213 y(subset)j(of)d(the)i(no)q (des)h(comprising)c(the)j(application)e({)h(col-)1013 1263 y(lectiv)o(e)k(comm)o(unicati)o(on)d(within)i Fn(gr)n(oups)p Ft(.)32 b(Suc)o(h)19 b(a)f(group)1013 1312 y(could)13 b(b)q(e)h(a)g(ro)o(w,)e(a)i(column,)d(a)i(blo)q(c)o(k)h(of)f(no)q(des,) h(or)f(simply)1013 1362 y(a)h(list)g(of)f(no)q(des.)21 b(Our)14 b(approac)o(h)h(builds)f(on)g(and)g(supp)q(orts)1013 1412 y(group)e(collectiv)o(e)h(comm)o(unicatio)o(n.)i(W)m(e)d(exp)q (ect)i(to)f(release)1013 1462 y(an)e(up)q(dated)g(v)o(ersion)g(of)g (the)g(library)g(that)g(allo)o(ws)e(for)i(group)1013 1512 y(collectiv)o(e)j(comm)o(unicati)o(on)d(in)j(the)g(near)g(future.) 1013 1670 y Fs(9)56 b(Conclusion)1063 1770 y Ft(This)16 b(pro)r(ject)i(pro)o(vides)f(the)g(building)f(blo)q(c)o(ks)g(for)h(v)o (ery)1013 1819 y(e\016cien)o(t)e(implem)o(en)o(tations)d(of)h (collectiv)o(e)h(comm)o(unication)1013 1869 y(libraries)i(lik)o(e)f (MPI.)i(The)f(only)g(requiremen)o(t)g(is)g(that)h(rea-)1013 1919 y(sonable)d(algorithms)f(exist)i(for)f(short)h(v)o(ectors)h(and)e (for)g(the)1013 1969 y(building)c(blo)q(c)o(ks)i(used)h(to)f(deriv)o(e) g(algorithms)e(for)i(long)f(v)o(ec-)1013 2019 y(tors.)18 b(Bey)o(ond)11 b(this,)h(w)o(e)g(mak)o(e)e(few)h(restrictions)i(on)e (the)h(un-)1013 2069 y(derlying)h(arc)o(hitecture.)19 b(F)m(or)13 b(example,)f(w)o(e)i(do)f(not)g(require)1013 2118 y(a)18 b(p)q(o)o(w)o(er-of-t)o(w)o(o)f(n)o(um)o(b)q(er)g(of)g(no)q (des.)32 b(Finally)m(,)16 b(the)j(scop)q(e)1013 2168 y(of)e(this)h(pro)r(ject)h(go)q(es)g(b)q(ey)o(ond)f(the)h(deriv)n (ation)e(of)g(h)o(ybrid)1013 2218 y(algorithms)11 b(in)h(that)h(ev)o (en)o(tually)g(our)g(collectiv)o(e)g(comm)o(uni-)1013 2268 y(cations)h(will)e(also)h(op)q(erate)i(within)e(groups.)1013 2426 y Fs(Ac)n(kno)n(wledgemen)n(ts)1063 2526 y Ft(This)e(researc)o(h)i (w)o(as)e(sp)q(onsored)i(in)e(part)h(b)o(y)f(In)o(tel)g(Sup)q(er-)1013 2576 y(computer)i(Systems)g(Division,)e(the)j(In)o(tel)g(Researc)o(h)g (Coun-)1013 2625 y(cil)i(and)g(the)h(Univ)o(ersit)o(y)f(of)g(T)m(exas)h (Cen)o(ter)g(for)f(High)g(P)o(er-)1013 2675 y(formance)d(Computing.) 1063 2725 y(This)i(researc)o(h)j(w)o(as)e(p)q(erformed)g(in)f(part)h (using)g(the)g(In-)1013 2775 y(tel)j(P)o(aragon)f(System)h(and)f(the)i (In)o(tel)f(T)m(ouc)o(hstone)g(Delta)p eop %%Page: 7 7 7 6 bop 294 194 a Ft(Mesh)15 b(size)g(16)8 b Fw(\002)i Ft(32)p 967 208 2 50 v 976 208 V 710 w(Mesh)15 b(size)g(15)9 b Fw(\002)g Ft(30)p -57 210 2058 2 v 364 245 a(Broadcast)p 967 260 2 50 v 976 260 V 853 w(Broadcast)-32 260 y 15392931 11840716 3289088 3289088 26970521 19866091 startTexFig -32 260 a %%BeginDocument: bc16x32.ps /gnudict 40 dict def gnudict begin /Color false def /gnulinewidth 5.000 def /vshift -46 def /dl {10 mul} def /hpt 31.5 def /vpt 31.5 def /vpt2 vpt 2 mul def /hpt2 hpt 2 mul def /Lshow { currentpoint stroke moveto 0 vshift rmoveto show } def /Rshow { currentpoint stroke moveto dup stringwidth pop neg vshift rmoveto show } def /Cshow { currentpoint stroke moveto dup stringwidth pop -2 div vshift rmoveto show } def /DL { Color {setrgbcolor [] 0 setdash pop} {pop pop pop 0 setdash} ifelse } def /BL { stroke gnulinewidth 2 mul setlinewidth } def /AL { stroke gnulinewidth 2 div setlinewidth } def /PL { stroke gnulinewidth setlinewidth } def /LTb { BL [] 0 0 0 DL } def /LTa { AL [1 dl 2 dl] 0 setdash 0 0 0 setrgbcolor } def /LT0 { PL [] 0 1 0 DL } def /LT1 { PL [4 dl 2 dl] 0 0 1 DL } def /LT2 { PL [2 dl 3 dl] 1 0 0 DL } def /LT3 { PL [1 dl 1.5 dl] 1 0 1 DL } def /LT4 { PL [5 dl 2 dl 1 dl 2 dl] 0 1 1 DL } def /LT5 { PL [4 dl 3 dl 1 dl 3 dl] 1 1 0 DL } def /LT6 { PL [2 dl 2 dl 2 dl 4 dl] 0 0 0 DL } def /LT7 { PL [2 dl 2 dl 2 dl 2 dl 2 dl 4 dl] 1 0.3 0 DL } def /LT8 { PL [2 dl 2 dl 2 dl 2 dl 2 dl 2 dl 2 dl 4 dl] 0.5 0.5 0.5 DL } def /M {moveto} def /L {lineto} def /P { stroke [] 0 setdash currentlinewidth 2 div sub moveto 0 currentlinewidth rlineto stroke } def /D { stroke [] 0 setdash 2 copy vpt add moveto hpt neg vpt neg rlineto hpt vpt neg rlineto hpt vpt rlineto hpt neg vpt rlineto closepath stroke P } def /A { stroke [] 0 setdash vpt sub moveto 0 vpt2 rlineto currentpoint stroke moveto hpt neg vpt neg rmoveto hpt2 0 rlineto stroke } def /B { stroke [] 0 setdash 2 copy exch hpt sub exch vpt add moveto 0 vpt2 neg rlineto hpt2 0 rlineto 0 vpt2 rlineto hpt2 neg 0 rlineto closepath stroke P } def /C { stroke [] 0 setdash exch hpt sub exch vpt add moveto hpt2 vpt2 neg rlineto currentpoint stroke moveto hpt2 neg 0 rmoveto hpt2 vpt2 rlineto stroke } def /T { stroke [] 0 setdash 2 copy vpt 1.12 mul add moveto hpt neg vpt -1.62 mul rlineto hpt 2 mul 0 rlineto hpt neg vpt 1.62 mul rlineto closepath stroke P } def /S { 2 copy A C} def end gnudict begin gsave 50 50 translate 0.050 0.050 scale 0 setgray /Courier findfont 140 scalefont setfont newpath LTa LTb 1008 491 M 1071 491 L 6969 491 M 6906 491 L 924 491 M (0.001) Rshow 1008 912 M 1039 912 L 6969 912 M 6938 912 L 924 912 M () Rshow 1008 1159 M 1039 1159 L 6969 1159 M 6938 1159 L 924 1159 M () Rshow 1008 1333 M 1039 1333 L 6969 1333 M 6938 1333 L 924 1333 M () Rshow 1008 1469 M 1039 1469 L 6969 1469 M 6938 1469 L 924 1469 M () Rshow 1008 1580 M 1039 1580 L 6969 1580 M 6938 1580 L 924 1580 M () Rshow 1008 1674 M 1039 1674 L 6969 1674 M 6938 1674 L 924 1674 M () Rshow 1008 1755 M 1039 1755 L 6969 1755 M 6938 1755 L 924 1755 M () Rshow 1008 1826 M 1039 1826 L 6969 1826 M 6938 1826 L 924 1826 M () Rshow 1008 1890 M 1071 1890 L 6969 1890 M 6906 1890 L 924 1890 M (0.01) Rshow 1008 2312 M 1039 2312 L 6969 2312 M 6938 2312 L 924 2312 M () Rshow 1008 2558 M 1039 2558 L 6969 2558 M 6938 2558 L 924 2558 M () Rshow 1008 2733 M 1039 2733 L 6969 2733 M 6938 2733 L 924 2733 M () Rshow 1008 2868 M 1039 2868 L 6969 2868 M 6938 2868 L 924 2868 M () Rshow 1008 2979 M 1039 2979 L 6969 2979 M 6938 2979 L 924 2979 M () Rshow 1008 3073 M 1039 3073 L 6969 3073 M 6938 3073 L 924 3073 M () Rshow 1008 3154 M 1039 3154 L 6969 3154 M 6938 3154 L 924 3154 M () Rshow 1008 3226 M 1039 3226 L 6969 3226 M 6938 3226 L 924 3226 M () Rshow 1008 3290 M 1071 3290 L 6969 3290 M 6906 3290 L 924 3290 M (0.1) Rshow 1008 3711 M 1039 3711 L 6969 3711 M 6938 3711 L 924 3711 M () Rshow 1008 3957 M 1039 3957 L 6969 3957 M 6938 3957 L 924 3957 M () Rshow 1008 4132 M 1039 4132 L 6969 4132 M 6938 4132 L 924 4132 M () Rshow 1008 4268 M 1039 4268 L 6969 4268 M 6938 4268 L 924 4268 M () Rshow 1008 4379 M 1039 4379 L 6969 4379 M 6938 4379 L 924 4379 M () Rshow 1008 4472 M 1039 4472 L 6969 4472 M 6938 4472 L 924 4472 M () Rshow 1008 4553 M 1039 4553 L 6969 4553 M 6938 4553 L 924 4553 M () Rshow 1008 4625 M 1039 4625 L 6969 4625 M 6938 4625 L 924 4625 M () Rshow 1008 4689 M 1071 4689 L 6969 4689 M 6906 4689 L 924 4689 M (1) Rshow 1008 491 M 1008 554 L 1008 4689 M 1008 4626 L 1008 351 M (1) Cshow 1264 491 M 1264 522 L 1264 4689 M 1264 4658 L 1264 351 M () Cshow 1603 491 M 1603 522 L 1603 4689 M 1603 4658 L 1603 351 M () Cshow 1777 491 M 1777 522 L 1777 4689 M 1777 4658 L 1777 351 M () Cshow 1860 491 M 1860 554 L 1860 4689 M 1860 4626 L 1860 351 M (10) Cshow 2116 491 M 2116 522 L 2116 4689 M 2116 4658 L 2116 351 M () Cshow 2455 491 M 2455 522 L 2455 4689 M 2455 4658 L 2455 351 M () Cshow 2629 491 M 2629 522 L 2629 4689 M 2629 4658 L 2629 351 M () Cshow 2711 491 M 2711 554 L 2711 4689 M 2711 4626 L 2711 351 M (100) Cshow 2967 491 M 2967 522 L 2967 4689 M 2967 4658 L 2967 351 M () Cshow 3306 491 M 3306 522 L 3306 4689 M 3306 4658 L 3306 351 M () Cshow 3480 491 M 3480 522 L 3480 4689 M 3480 4658 L 3480 351 M () Cshow 3563 491 M 3563 554 L 3563 4689 M 3563 4626 L 3563 351 M (1000) Cshow 3819 491 M 3819 522 L 3819 4689 M 3819 4658 L 3819 351 M () Cshow 4158 491 M 4158 522 L 4158 4689 M 4158 4658 L 4158 351 M () Cshow 4332 491 M 4332 522 L 4332 4689 M 4332 4658 L 4332 351 M () Cshow 4414 491 M 4414 554 L 4414 4689 M 4414 4626 L 4414 351 M (10000) Cshow 4671 491 M 4671 522 L 4671 4689 M 4671 4658 L 4671 351 M () Cshow 5010 491 M 5010 522 L 5010 4689 M 5010 4658 L 5010 351 M () Cshow 5183 491 M 5183 522 L 5183 4689 M 5183 4658 L 5183 351 M () Cshow 5266 491 M 5266 554 L 5266 4689 M 5266 4626 L 5266 351 M (100000) Cshow 5522 491 M 5522 522 L 5522 4689 M 5522 4658 L 5522 351 M () Cshow 5861 491 M 5861 522 L 5861 4689 M 5861 4658 L 5861 351 M () Cshow 6035 491 M 6035 522 L 6035 4689 M 6035 4658 L 6035 351 M () Cshow 6117 491 M 6117 554 L 6117 4689 M 6117 4626 L 6117 351 M (1e+06) Cshow 6374 491 M 6374 522 L 6374 4689 M 6374 4658 L 6374 351 M () Cshow 6713 491 M 6713 522 L 6713 4689 M 6713 4658 L 6713 351 M () Cshow 6886 491 M 6886 522 L 6886 4689 M 6886 4658 L 6886 351 M () Cshow 6969 491 M 6969 554 L 6969 4689 M 6969 4626 L 6969 351 M (1e+07) Cshow LTb 1008 491 M 6969 491 L 6969 4689 L 1008 4689 L 1008 491 L 140 2590 M currentpoint gsave translate 90 rotate 0 0 moveto (time) Cshow grestore 3988 211 M (problem size in bytes) Cshow LT0 LT0 2711 3957 M (short vec) Rshow 2795 3957 M 3047 3957 L 1777 583 M 1777 583 L 2033 600 L 2290 607 L 2546 581 L 2802 598 L 3059 639 L 3315 666 L 3571 760 L 3828 1139 L 4084 1280 L 4341 1522 L 4597 1861 L 4853 2213 L 5110 2594 L 5366 3005 L 5622 3420 L 5879 3832 L 6135 4250 L 2879 3957 B 1777 583 B 2033 600 B 2290 607 B 2546 581 B 2802 598 B 3059 639 B 3315 666 B 3571 760 B 3828 1139 B 4084 1280 B 4341 1522 B 4597 1861 B 4853 2213 B 5110 2594 B 5366 3005 B 5622 3420 B 5879 3832 B 6135 4250 B LT0 2711 3817 M (long vec) Rshow 2795 3817 M 3047 3817 L 1777 2523 M 1777 2523 L 2033 2523 L 2290 2528 L 2546 2525 L 2802 2527 L 3059 2545 L 3315 2552 L 3571 2556 L 3828 2565 L 4084 2577 L 4341 2565 L 4597 2574 L 4853 2651 L 5110 2691 L 5366 2781 L 5622 2918 L 5879 3099 L 6135 3399 L 2879 3817 T 1777 2523 T 2033 2523 T 2290 2528 T 2546 2525 T 2802 2527 T 3059 2545 T 3315 2552 T 3571 2556 T 3828 2565 T 4084 2577 T 4341 2565 T 4597 2574 T 4853 2651 T 5110 2691 T 5366 2781 T 5622 2918 T 5879 3099 T 6135 3399 T LT0 2711 3677 M (HYBRID bcast) Rshow 2795 3677 M 3047 3677 L 1777 654 M 1777 654 L 2033 633 L 2290 636 L 2546 641 L 2802 650 L 3059 689 L 3315 800 L 3571 878 L 3828 1065 L 4084 1311 L 4341 1491 L 4597 1684 L 4853 1840 L 5110 2025 L 5366 2494 L 5622 2722 L 5879 2976 L 6135 3287 L 2879 3677 C 1777 654 C 2033 633 C 2290 636 C 2546 641 C 2802 650 C 3059 689 C 3315 800 C 3571 878 C 3828 1065 C 4084 1311 C 4341 1491 C 4597 1684 C 4853 1840 C 5110 2025 C 5366 2494 C 5622 2722 C 5879 2976 C 6135 3287 C stroke grestore end showpage %%EndDocument endTexFig 967 1010 2 750 v 976 1010 V 1001 260 a 15392931 11840716 3289088 3289088 26970521 19866091 startTexFig 1001 260 a %%BeginDocument: bc15x30.ps /gnudict 40 dict def gnudict begin /Color false def /gnulinewidth 5.000 def /vshift -46 def /dl {10 mul} def /hpt 31.5 def /vpt 31.5 def /vpt2 vpt 2 mul def /hpt2 hpt 2 mul def /Lshow { currentpoint stroke moveto 0 vshift rmoveto show } def /Rshow { currentpoint stroke moveto dup stringwidth pop neg vshift rmoveto show } def /Cshow { currentpoint stroke moveto dup stringwidth pop -2 div vshift rmoveto show } def /DL { Color {setrgbcolor [] 0 setdash pop} {pop pop pop 0 setdash} ifelse } def /BL { stroke gnulinewidth 2 mul setlinewidth } def /AL { stroke gnulinewidth 2 div setlinewidth } def /PL { stroke gnulinewidth setlinewidth } def /LTb { BL [] 0 0 0 DL } def /LTa { AL [1 dl 2 dl] 0 setdash 0 0 0 setrgbcolor } def /LT0 { PL [] 0 1 0 DL } def /LT1 { PL [4 dl 2 dl] 0 0 1 DL } def /LT2 { PL [2 dl 3 dl] 1 0 0 DL } def /LT3 { PL [1 dl 1.5 dl] 1 0 1 DL } def /LT4 { PL [5 dl 2 dl 1 dl 2 dl] 0 1 1 DL } def /LT5 { PL [4 dl 3 dl 1 dl 3 dl] 1 1 0 DL } def /LT6 { PL [2 dl 2 dl 2 dl 4 dl] 0 0 0 DL } def /LT7 { PL [2 dl 2 dl 2 dl 2 dl 2 dl 4 dl] 1 0.3 0 DL } def /LT8 { PL [2 dl 2 dl 2 dl 2 dl 2 dl 2 dl 2 dl 4 dl] 0.5 0.5 0.5 DL } def /M {moveto} def /L {lineto} def /P { stroke [] 0 setdash currentlinewidth 2 div sub moveto 0 currentlinewidth rlineto stroke } def /D { stroke [] 0 setdash 2 copy vpt add moveto hpt neg vpt neg rlineto hpt vpt neg rlineto hpt vpt rlineto hpt neg vpt rlineto closepath stroke P } def /A { stroke [] 0 setdash vpt sub moveto 0 vpt2 rlineto currentpoint stroke moveto hpt neg vpt neg rmoveto hpt2 0 rlineto stroke } def /B { stroke [] 0 setdash 2 copy exch hpt sub exch vpt add moveto 0 vpt2 neg rlineto hpt2 0 rlineto 0 vpt2 rlineto hpt2 neg 0 rlineto closepath stroke P } def /C { stroke [] 0 setdash exch hpt sub exch vpt add moveto hpt2 vpt2 neg rlineto currentpoint stroke moveto hpt2 neg 0 rmoveto hpt2 vpt2 rlineto stroke } def /T { stroke [] 0 setdash 2 copy vpt 1.12 mul add moveto hpt neg vpt -1.62 mul rlineto hpt 2 mul 0 rlineto hpt neg vpt 1.62 mul rlineto closepath stroke P } def /S { 2 copy A C} def end gnudict begin gsave 50 50 translate 0.050 0.050 scale 0 setgray /Courier findfont 140 scalefont setfont newpath LTa LTb 1008 491 M 1071 491 L 6969 491 M 6906 491 L 924 491 M (0.001) Rshow 1008 912 M 1039 912 L 6969 912 M 6938 912 L 924 912 M () Rshow 1008 1159 M 1039 1159 L 6969 1159 M 6938 1159 L 924 1159 M () Rshow 1008 1333 M 1039 1333 L 6969 1333 M 6938 1333 L 924 1333 M () Rshow 1008 1469 M 1039 1469 L 6969 1469 M 6938 1469 L 924 1469 M () Rshow 1008 1580 M 1039 1580 L 6969 1580 M 6938 1580 L 924 1580 M () Rshow 1008 1674 M 1039 1674 L 6969 1674 M 6938 1674 L 924 1674 M () Rshow 1008 1755 M 1039 1755 L 6969 1755 M 6938 1755 L 924 1755 M () Rshow 1008 1826 M 1039 1826 L 6969 1826 M 6938 1826 L 924 1826 M () Rshow 1008 1890 M 1071 1890 L 6969 1890 M 6906 1890 L 924 1890 M (0.01) Rshow 1008 2312 M 1039 2312 L 6969 2312 M 6938 2312 L 924 2312 M () Rshow 1008 2558 M 1039 2558 L 6969 2558 M 6938 2558 L 924 2558 M () Rshow 1008 2733 M 1039 2733 L 6969 2733 M 6938 2733 L 924 2733 M () Rshow 1008 2868 M 1039 2868 L 6969 2868 M 6938 2868 L 924 2868 M () Rshow 1008 2979 M 1039 2979 L 6969 2979 M 6938 2979 L 924 2979 M () Rshow 1008 3073 M 1039 3073 L 6969 3073 M 6938 3073 L 924 3073 M () Rshow 1008 3154 M 1039 3154 L 6969 3154 M 6938 3154 L 924 3154 M () Rshow 1008 3226 M 1039 3226 L 6969 3226 M 6938 3226 L 924 3226 M () Rshow 1008 3290 M 1071 3290 L 6969 3290 M 6906 3290 L 924 3290 M (0.1) Rshow 1008 3711 M 1039 3711 L 6969 3711 M 6938 3711 L 924 3711 M () Rshow 1008 3957 M 1039 3957 L 6969 3957 M 6938 3957 L 924 3957 M () Rshow 1008 4132 M 1039 4132 L 6969 4132 M 6938 4132 L 924 4132 M () Rshow 1008 4268 M 1039 4268 L 6969 4268 M 6938 4268 L 924 4268 M () Rshow 1008 4379 M 1039 4379 L 6969 4379 M 6938 4379 L 924 4379 M () Rshow 1008 4472 M 1039 4472 L 6969 4472 M 6938 4472 L 924 4472 M () Rshow 1008 4553 M 1039 4553 L 6969 4553 M 6938 4553 L 924 4553 M () Rshow 1008 4625 M 1039 4625 L 6969 4625 M 6938 4625 L 924 4625 M () Rshow 1008 4689 M 1071 4689 L 6969 4689 M 6906 4689 L 924 4689 M (1) Rshow 1008 491 M 1008 554 L 1008 4689 M 1008 4626 L 1008 351 M (1) Cshow 1264 491 M 1264 522 L 1264 4689 M 1264 4658 L 1264 351 M () Cshow 1603 491 M 1603 522 L 1603 4689 M 1603 4658 L 1603 351 M () Cshow 1777 491 M 1777 522 L 1777 4689 M 1777 4658 L 1777 351 M () Cshow 1860 491 M 1860 554 L 1860 4689 M 1860 4626 L 1860 351 M (10) Cshow 2116 491 M 2116 522 L 2116 4689 M 2116 4658 L 2116 351 M () Cshow 2455 491 M 2455 522 L 2455 4689 M 2455 4658 L 2455 351 M () Cshow 2629 491 M 2629 522 L 2629 4689 M 2629 4658 L 2629 351 M () Cshow 2711 491 M 2711 554 L 2711 4689 M 2711 4626 L 2711 351 M (100) Cshow 2967 491 M 2967 522 L 2967 4689 M 2967 4658 L 2967 351 M () Cshow 3306 491 M 3306 522 L 3306 4689 M 3306 4658 L 3306 351 M () Cshow 3480 491 M 3480 522 L 3480 4689 M 3480 4658 L 3480 351 M () Cshow 3563 491 M 3563 554 L 3563 4689 M 3563 4626 L 3563 351 M (1000) Cshow 3819 491 M 3819 522 L 3819 4689 M 3819 4658 L 3819 351 M () Cshow 4158 491 M 4158 522 L 4158 4689 M 4158 4658 L 4158 351 M () Cshow 4332 491 M 4332 522 L 4332 4689 M 4332 4658 L 4332 351 M () Cshow 4414 491 M 4414 554 L 4414 4689 M 4414 4626 L 4414 351 M (10000) Cshow 4671 491 M 4671 522 L 4671 4689 M 4671 4658 L 4671 351 M () Cshow 5010 491 M 5010 522 L 5010 4689 M 5010 4658 L 5010 351 M () Cshow 5183 491 M 5183 522 L 5183 4689 M 5183 4658 L 5183 351 M () Cshow 5266 491 M 5266 554 L 5266 4689 M 5266 4626 L 5266 351 M (100000) Cshow 5522 491 M 5522 522 L 5522 4689 M 5522 4658 L 5522 351 M () Cshow 5861 491 M 5861 522 L 5861 4689 M 5861 4658 L 5861 351 M () Cshow 6035 491 M 6035 522 L 6035 4689 M 6035 4658 L 6035 351 M () Cshow 6117 491 M 6117 554 L 6117 4689 M 6117 4626 L 6117 351 M (1e+06) Cshow 6374 491 M 6374 522 L 6374 4689 M 6374 4658 L 6374 351 M () Cshow 6713 491 M 6713 522 L 6713 4689 M 6713 4658 L 6713 351 M () Cshow 6886 491 M 6886 522 L 6886 4689 M 6886 4658 L 6886 351 M () Cshow 6969 491 M 6969 554 L 6969 4689 M 6969 4626 L 6969 351 M (1e+07) Cshow LTb 1008 491 M 6969 491 L 6969 4689 L 1008 4689 L 1008 491 L 140 2590 M currentpoint gsave translate 90 rotate 0 0 moveto (time) Cshow grestore 3988 211 M (problem size in bytes) Cshow LT0 LT0 2711 3957 M (short vec) Rshow 2795 3957 M 3047 3957 L 1777 605 M 1777 605 L 2033 608 L 2290 604 L 2546 582 L 2802 600 L 3059 632 L 3315 682 L 3571 742 L 3828 1157 L 4084 1296 L 4341 1534 L 4597 1867 L 4853 2220 L 5110 2598 L 5366 3006 L 5622 3421 L 5879 3833 L 6135 4249 L 2879 3957 B 1777 605 B 2033 608 B 2290 604 B 2546 582 B 2802 600 B 3059 632 B 3315 682 B 3571 742 B 3828 1157 B 4084 1296 B 4341 1534 B 4597 1867 B 4853 2220 B 5110 2598 B 5366 3006 B 5622 3421 B 5879 3833 B 6135 4249 B LT0 2711 3817 M (long vec) Rshow 2795 3817 M 3047 3817 L 1777 2485 M 1777 2485 L 2033 2485 L 2290 2484 L 2546 2486 L 2802 2487 L 3059 2505 L 3315 2512 L 3571 2517 L 3828 2529 L 4084 2544 L 4341 2540 L 4597 2563 L 4853 2645 L 5110 2683 L 5366 2763 L 5622 2900 L 5879 3152 L 6135 3457 L 2879 3817 T 1777 2485 T 2033 2485 T 2290 2484 T 2546 2486 T 2802 2487 T 3059 2505 T 3315 2512 T 3571 2517 T 3828 2529 T 4084 2544 T 4341 2540 T 4597 2563 T 4853 2645 T 5110 2683 T 5366 2763 T 5622 2900 T 5879 3152 T 6135 3457 T LT0 2711 3677 M (HYBRID bcast) Rshow 2795 3677 M 3047 3677 L 1777 660 M 1777 660 L 2033 647 L 2290 652 L 2546 649 L 2802 667 L 3059 677 L 3315 785 L 3571 857 L 3828 1247 L 4084 1289 L 4341 1542 L 4597 1800 L 4853 1991 L 5110 2188 L 5366 2393 L 5622 2768 L 5879 3045 L 6135 3377 L 2879 3677 C 1777 660 C 2033 647 C 2290 652 C 2546 649 C 2802 667 C 3059 677 C 3315 785 C 3571 857 C 3828 1247 C 4084 1289 C 4341 1542 C 4597 1800 C 4853 1991 C 5110 2188 C 5366 2393 C 5622 2768 C 5879 3045 C 6135 3377 C stroke grestore end showpage %%EndDocument endTexFig -57 1012 2058 2 v 392 1046 a Ft(Collect)p 967 1061 2 50 v 976 1061 V 906 w(Collect)-32 1061 y 15392931 11840716 3289088 3289088 26970521 19866091 startTexFig -32 1061 a %%BeginDocument: coll16x32.ps /gnudict 40 dict def gnudict begin /Color false def /gnulinewidth 5.000 def /vshift -46 def /dl {10 mul} def /hpt 31.5 def /vpt 31.5 def /vpt2 vpt 2 mul def /hpt2 hpt 2 mul def /Lshow { currentpoint stroke moveto 0 vshift rmoveto show } def /Rshow { currentpoint stroke moveto dup stringwidth pop neg vshift rmoveto show } def /Cshow { currentpoint stroke moveto dup stringwidth pop -2 div vshift rmoveto show } def /DL { Color {setrgbcolor [] 0 setdash pop} {pop pop pop 0 setdash} ifelse } def /BL { stroke gnulinewidth 2 mul setlinewidth } def /AL { stroke gnulinewidth 2 div setlinewidth } def /PL { stroke gnulinewidth setlinewidth } def /LTb { BL [] 0 0 0 DL } def /LTa { AL [1 dl 2 dl] 0 setdash 0 0 0 setrgbcolor } def /LT0 { PL [] 0 1 0 DL } def /LT1 { PL [4 dl 2 dl] 0 0 1 DL } def /LT2 { PL [2 dl 3 dl] 1 0 0 DL } def /LT3 { PL [1 dl 1.5 dl] 1 0 1 DL } def /LT4 { PL [5 dl 2 dl 1 dl 2 dl] 0 1 1 DL } def /LT5 { PL [4 dl 3 dl 1 dl 3 dl] 1 1 0 DL } def /LT6 { PL [2 dl 2 dl 2 dl 4 dl] 0 0 0 DL } def /LT7 { PL [2 dl 2 dl 2 dl 2 dl 2 dl 4 dl] 1 0.3 0 DL } def /LT8 { PL [2 dl 2 dl 2 dl 2 dl 2 dl 2 dl 2 dl 4 dl] 0.5 0.5 0.5 DL } def /M {moveto} def /L {lineto} def /P { stroke [] 0 setdash currentlinewidth 2 div sub moveto 0 currentlinewidth rlineto stroke } def /D { stroke [] 0 setdash 2 copy vpt add moveto hpt neg vpt neg rlineto hpt vpt neg rlineto hpt vpt rlineto hpt neg vpt rlineto closepath stroke P } def /A { stroke [] 0 setdash vpt sub moveto 0 vpt2 rlineto currentpoint stroke moveto hpt neg vpt neg rmoveto hpt2 0 rlineto stroke } def /B { stroke [] 0 setdash 2 copy exch hpt sub exch vpt add moveto 0 vpt2 neg rlineto hpt2 0 rlineto 0 vpt2 rlineto hpt2 neg 0 rlineto closepath stroke P } def /C { stroke [] 0 setdash exch hpt sub exch vpt add moveto hpt2 vpt2 neg rlineto currentpoint stroke moveto hpt2 neg 0 rmoveto hpt2 vpt2 rlineto stroke } def /T { stroke [] 0 setdash 2 copy vpt 1.12 mul add moveto hpt neg vpt -1.62 mul rlineto hpt 2 mul 0 rlineto hpt neg vpt 1.62 mul rlineto closepath stroke P } def /S { 2 copy A C} def end gnudict begin gsave 50 50 translate 0.050 0.050 scale 0 setgray /Courier findfont 140 scalefont setfont newpath LTa LTb 1008 491 M 1071 491 L 6969 491 M 6906 491 L 924 491 M (0.001) Rshow 1008 912 M 1039 912 L 6969 912 M 6938 912 L 924 912 M () Rshow 1008 1159 M 1039 1159 L 6969 1159 M 6938 1159 L 924 1159 M () Rshow 1008 1333 M 1039 1333 L 6969 1333 M 6938 1333 L 924 1333 M () Rshow 1008 1469 M 1039 1469 L 6969 1469 M 6938 1469 L 924 1469 M () Rshow 1008 1580 M 1039 1580 L 6969 1580 M 6938 1580 L 924 1580 M () Rshow 1008 1674 M 1039 1674 L 6969 1674 M 6938 1674 L 924 1674 M () Rshow 1008 1755 M 1039 1755 L 6969 1755 M 6938 1755 L 924 1755 M () Rshow 1008 1826 M 1039 1826 L 6969 1826 M 6938 1826 L 924 1826 M () Rshow 1008 1890 M 1071 1890 L 6969 1890 M 6906 1890 L 924 1890 M (0.01) Rshow 1008 2312 M 1039 2312 L 6969 2312 M 6938 2312 L 924 2312 M () Rshow 1008 2558 M 1039 2558 L 6969 2558 M 6938 2558 L 924 2558 M () Rshow 1008 2733 M 1039 2733 L 6969 2733 M 6938 2733 L 924 2733 M () Rshow 1008 2868 M 1039 2868 L 6969 2868 M 6938 2868 L 924 2868 M () Rshow 1008 2979 M 1039 2979 L 6969 2979 M 6938 2979 L 924 2979 M () Rshow 1008 3073 M 1039 3073 L 6969 3073 M 6938 3073 L 924 3073 M () Rshow 1008 3154 M 1039 3154 L 6969 3154 M 6938 3154 L 924 3154 M () Rshow 1008 3226 M 1039 3226 L 6969 3226 M 6938 3226 L 924 3226 M () Rshow 1008 3290 M 1071 3290 L 6969 3290 M 6906 3290 L 924 3290 M (0.1) Rshow 1008 3711 M 1039 3711 L 6969 3711 M 6938 3711 L 924 3711 M () Rshow 1008 3957 M 1039 3957 L 6969 3957 M 6938 3957 L 924 3957 M () Rshow 1008 4132 M 1039 4132 L 6969 4132 M 6938 4132 L 924 4132 M () Rshow 1008 4268 M 1039 4268 L 6969 4268 M 6938 4268 L 924 4268 M () Rshow 1008 4379 M 1039 4379 L 6969 4379 M 6938 4379 L 924 4379 M () Rshow 1008 4472 M 1039 4472 L 6969 4472 M 6938 4472 L 924 4472 M () Rshow 1008 4553 M 1039 4553 L 6969 4553 M 6938 4553 L 924 4553 M () Rshow 1008 4625 M 1039 4625 L 6969 4625 M 6938 4625 L 924 4625 M () Rshow 1008 4689 M 1071 4689 L 6969 4689 M 6906 4689 L 924 4689 M (1) Rshow 1008 491 M 1008 554 L 1008 4689 M 1008 4626 L 1008 351 M (1) Cshow 1264 491 M 1264 522 L 1264 4689 M 1264 4658 L 1264 351 M () Cshow 1603 491 M 1603 522 L 1603 4689 M 1603 4658 L 1603 351 M () Cshow 1777 491 M 1777 522 L 1777 4689 M 1777 4658 L 1777 351 M () Cshow 1860 491 M 1860 554 L 1860 4689 M 1860 4626 L 1860 351 M (10) Cshow 2116 491 M 2116 522 L 2116 4689 M 2116 4658 L 2116 351 M () Cshow 2455 491 M 2455 522 L 2455 4689 M 2455 4658 L 2455 351 M () Cshow 2629 491 M 2629 522 L 2629 4689 M 2629 4658 L 2629 351 M () Cshow 2711 491 M 2711 554 L 2711 4689 M 2711 4626 L 2711 351 M (100) Cshow 2967 491 M 2967 522 L 2967 4689 M 2967 4658 L 2967 351 M () Cshow 3306 491 M 3306 522 L 3306 4689 M 3306 4658 L 3306 351 M () Cshow 3480 491 M 3480 522 L 3480 4689 M 3480 4658 L 3480 351 M () Cshow 3563 491 M 3563 554 L 3563 4689 M 3563 4626 L 3563 351 M (1000) Cshow 3819 491 M 3819 522 L 3819 4689 M 3819 4658 L 3819 351 M () Cshow 4158 491 M 4158 522 L 4158 4689 M 4158 4658 L 4158 351 M () Cshow 4332 491 M 4332 522 L 4332 4689 M 4332 4658 L 4332 351 M () Cshow 4414 491 M 4414 554 L 4414 4689 M 4414 4626 L 4414 351 M (10000) Cshow 4671 491 M 4671 522 L 4671 4689 M 4671 4658 L 4671 351 M () Cshow 5010 491 M 5010 522 L 5010 4689 M 5010 4658 L 5010 351 M () Cshow 5183 491 M 5183 522 L 5183 4689 M 5183 4658 L 5183 351 M () Cshow 5266 491 M 5266 554 L 5266 4689 M 5266 4626 L 5266 351 M (100000) Cshow 5522 491 M 5522 522 L 5522 4689 M 5522 4658 L 5522 351 M () Cshow 5861 491 M 5861 522 L 5861 4689 M 5861 4658 L 5861 351 M () Cshow 6035 491 M 6035 522 L 6035 4689 M 6035 4658 L 6035 351 M () Cshow 6117 491 M 6117 554 L 6117 4689 M 6117 4626 L 6117 351 M (1e+06) Cshow 6374 491 M 6374 522 L 6374 4689 M 6374 4658 L 6374 351 M () Cshow 6713 491 M 6713 522 L 6713 4689 M 6713 4658 L 6713 351 M () Cshow 6886 491 M 6886 522 L 6886 4689 M 6886 4658 L 6886 351 M () Cshow 6969 491 M 6969 554 L 6969 4689 M 6969 4626 L 6969 351 M (1e+07) Cshow LTb 1008 491 M 6969 491 L 6969 4689 L 1008 4689 L 1008 491 L 140 2590 M currentpoint gsave translate 90 rotate 0 0 moveto (time) Cshow grestore 3988 211 M (problem size in bytes) Cshow LT0 LT0 6117 1890 M (short vec) Rshow 6201 1890 M 6453 1890 L 1777 1211 M 1777 1211 L 2033 1218 L 2290 1217 L 2546 1218 L 2802 1219 L 3059 1231 L 3315 1249 L 3571 1268 L 3828 1336 L 4084 1426 L 4341 1574 L 4597 1778 L 4853 2052 L 5110 2377 L 5366 2755 L 5622 3138 L 5879 3536 L 6135 3947 L 6285 1890 T 1777 1211 T 2033 1218 T 2290 1217 T 2546 1218 T 2802 1219 T 3059 1231 T 3315 1249 T 3571 1268 T 3828 1336 T 4084 1426 T 4341 1574 T 4597 1778 T 4853 2052 T 5110 2377 T 5366 2755 T 5622 3138 T 5879 3536 T 6135 3947 T LT0 6117 1750 M (long vec) Rshow 6201 1750 M 6453 1750 L 1777 2471 M 1777 2471 L 2033 2471 L 2290 2469 L 2546 2472 L 2802 2477 L 3059 2488 L 3315 2490 L 3571 2500 L 3828 2506 L 4084 2518 L 4341 2512 L 4597 2513 L 4853 2580 L 5110 2609 L 5366 2682 L 5622 2785 L 5879 2942 L 6135 3215 L 6285 1750 S 1777 2471 S 2033 2471 S 2290 2469 S 2546 2472 S 2802 2477 S 3059 2488 S 3315 2490 S 3571 2500 S 3828 2506 S 4084 2518 S 4341 2512 S 4597 2513 S 4853 2580 S 5110 2609 S 5366 2682 S 5622 2785 S 5879 2942 S 6135 3215 S LT0 6117 1610 M (HYBRID gcolx) Rshow 6201 1610 M 6453 1610 L 1777 1244 M 1777 1244 L 2033 1244 L 2290 1255 L 2546 1252 L 2802 1263 L 3059 1261 L 3315 1259 L 3571 1289 L 3828 1371 L 4084 1467 L 4341 1645 L 4597 1833 L 4853 1844 L 5110 2055 L 5366 2324 L 5622 2573 L 5879 2902 L 6135 3112 L 6285 1610 C 1777 1244 C 2033 1244 C 2290 1255 C 2546 1252 C 2802 1263 C 3059 1261 C 3315 1259 C 3571 1289 C 3828 1371 C 4084 1467 C 4341 1645 C 4597 1833 C 4853 1844 C 5110 2055 C 5366 2324 C 5622 2573 C 5879 2902 C 6135 3112 C stroke grestore end showpage %%EndDocument endTexFig 967 1811 2 750 v 976 1811 V 1001 1061 a 15392931 11840716 3289088 3289088 26970521 19866091 startTexFig 1001 1061 a %%BeginDocument: coll15x30.ps /gnudict 40 dict def gnudict begin /Color false def /gnulinewidth 5.000 def /vshift -46 def /dl {10 mul} def /hpt 31.5 def /vpt 31.5 def /vpt2 vpt 2 mul def /hpt2 hpt 2 mul def /Lshow { currentpoint stroke moveto 0 vshift rmoveto show } def /Rshow { currentpoint stroke moveto dup stringwidth pop neg vshift rmoveto show } def /Cshow { currentpoint stroke moveto dup stringwidth pop -2 div vshift rmoveto show } def /DL { Color {setrgbcolor [] 0 setdash pop} {pop pop pop 0 setdash} ifelse } def /BL { stroke gnulinewidth 2 mul setlinewidth } def /AL { stroke gnulinewidth 2 div setlinewidth } def /PL { stroke gnulinewidth setlinewidth } def /LTb { BL [] 0 0 0 DL } def /LTa { AL [1 dl 2 dl] 0 setdash 0 0 0 setrgbcolor } def /LT0 { PL [] 0 1 0 DL } def /LT1 { PL [4 dl 2 dl] 0 0 1 DL } def /LT2 { PL [2 dl 3 dl] 1 0 0 DL } def /LT3 { PL [1 dl 1.5 dl] 1 0 1 DL } def /LT4 { PL [5 dl 2 dl 1 dl 2 dl] 0 1 1 DL } def /LT5 { PL [4 dl 3 dl 1 dl 3 dl] 1 1 0 DL } def /LT6 { PL [2 dl 2 dl 2 dl 4 dl] 0 0 0 DL } def /LT7 { PL [2 dl 2 dl 2 dl 2 dl 2 dl 4 dl] 1 0.3 0 DL } def /LT8 { PL [2 dl 2 dl 2 dl 2 dl 2 dl 2 dl 2 dl 4 dl] 0.5 0.5 0.5 DL } def /M {moveto} def /L {lineto} def /P { stroke [] 0 setdash currentlinewidth 2 div sub moveto 0 currentlinewidth rlineto stroke } def /D { stroke [] 0 setdash 2 copy vpt add moveto hpt neg vpt neg rlineto hpt vpt neg rlineto hpt vpt rlineto hpt neg vpt rlineto closepath stroke P } def /A { stroke [] 0 setdash vpt sub moveto 0 vpt2 rlineto currentpoint stroke moveto hpt neg vpt neg rmoveto hpt2 0 rlineto stroke } def /B { stroke [] 0 setdash 2 copy exch hpt sub exch vpt add moveto 0 vpt2 neg rlineto hpt2 0 rlineto 0 vpt2 rlineto hpt2 neg 0 rlineto closepath stroke P } def /C { stroke [] 0 setdash exch hpt sub exch vpt add moveto hpt2 vpt2 neg rlineto currentpoint stroke moveto hpt2 neg 0 rmoveto hpt2 vpt2 rlineto stroke } def /T { stroke [] 0 setdash 2 copy vpt 1.12 mul add moveto hpt neg vpt -1.62 mul rlineto hpt 2 mul 0 rlineto hpt neg vpt 1.62 mul rlineto closepath stroke P } def /S { 2 copy A C} def end gnudict begin gsave 50 50 translate 0.050 0.050 scale 0 setgray /Courier findfont 140 scalefont setfont newpath LTa LTb 1008 491 M 1071 491 L 6969 491 M 6906 491 L 924 491 M (0.001) Rshow 1008 912 M 1039 912 L 6969 912 M 6938 912 L 924 912 M () Rshow 1008 1159 M 1039 1159 L 6969 1159 M 6938 1159 L 924 1159 M () Rshow 1008 1333 M 1039 1333 L 6969 1333 M 6938 1333 L 924 1333 M () Rshow 1008 1469 M 1039 1469 L 6969 1469 M 6938 1469 L 924 1469 M () Rshow 1008 1580 M 1039 1580 L 6969 1580 M 6938 1580 L 924 1580 M () Rshow 1008 1674 M 1039 1674 L 6969 1674 M 6938 1674 L 924 1674 M () Rshow 1008 1755 M 1039 1755 L 6969 1755 M 6938 1755 L 924 1755 M () Rshow 1008 1826 M 1039 1826 L 6969 1826 M 6938 1826 L 924 1826 M () Rshow 1008 1890 M 1071 1890 L 6969 1890 M 6906 1890 L 924 1890 M (0.01) Rshow 1008 2312 M 1039 2312 L 6969 2312 M 6938 2312 L 924 2312 M () Rshow 1008 2558 M 1039 2558 L 6969 2558 M 6938 2558 L 924 2558 M () Rshow 1008 2733 M 1039 2733 L 6969 2733 M 6938 2733 L 924 2733 M () Rshow 1008 2868 M 1039 2868 L 6969 2868 M 6938 2868 L 924 2868 M () Rshow 1008 2979 M 1039 2979 L 6969 2979 M 6938 2979 L 924 2979 M () Rshow 1008 3073 M 1039 3073 L 6969 3073 M 6938 3073 L 924 3073 M () Rshow 1008 3154 M 1039 3154 L 6969 3154 M 6938 3154 L 924 3154 M () Rshow 1008 3226 M 1039 3226 L 6969 3226 M 6938 3226 L 924 3226 M () Rshow 1008 3290 M 1071 3290 L 6969 3290 M 6906 3290 L 924 3290 M (0.1) Rshow 1008 3711 M 1039 3711 L 6969 3711 M 6938 3711 L 924 3711 M () Rshow 1008 3957 M 1039 3957 L 6969 3957 M 6938 3957 L 924 3957 M () Rshow 1008 4132 M 1039 4132 L 6969 4132 M 6938 4132 L 924 4132 M () Rshow 1008 4268 M 1039 4268 L 6969 4268 M 6938 4268 L 924 4268 M () Rshow 1008 4379 M 1039 4379 L 6969 4379 M 6938 4379 L 924 4379 M () Rshow 1008 4472 M 1039 4472 L 6969 4472 M 6938 4472 L 924 4472 M () Rshow 1008 4553 M 1039 4553 L 6969 4553 M 6938 4553 L 924 4553 M () Rshow 1008 4625 M 1039 4625 L 6969 4625 M 6938 4625 L 924 4625 M () Rshow 1008 4689 M 1071 4689 L 6969 4689 M 6906 4689 L 924 4689 M (1) Rshow 1008 491 M 1008 554 L 1008 4689 M 1008 4626 L 1008 351 M (1) Cshow 1264 491 M 1264 522 L 1264 4689 M 1264 4658 L 1264 351 M () Cshow 1603 491 M 1603 522 L 1603 4689 M 1603 4658 L 1603 351 M () Cshow 1777 491 M 1777 522 L 1777 4689 M 1777 4658 L 1777 351 M () Cshow 1860 491 M 1860 554 L 1860 4689 M 1860 4626 L 1860 351 M (10) Cshow 2116 491 M 2116 522 L 2116 4689 M 2116 4658 L 2116 351 M () Cshow 2455 491 M 2455 522 L 2455 4689 M 2455 4658 L 2455 351 M () Cshow 2629 491 M 2629 522 L 2629 4689 M 2629 4658 L 2629 351 M () Cshow 2711 491 M 2711 554 L 2711 4689 M 2711 4626 L 2711 351 M (100) Cshow 2967 491 M 2967 522 L 2967 4689 M 2967 4658 L 2967 351 M () Cshow 3306 491 M 3306 522 L 3306 4689 M 3306 4658 L 3306 351 M () Cshow 3480 491 M 3480 522 L 3480 4689 M 3480 4658 L 3480 351 M () Cshow 3563 491 M 3563 554 L 3563 4689 M 3563 4626 L 3563 351 M (1000) Cshow 3819 491 M 3819 522 L 3819 4689 M 3819 4658 L 3819 351 M () Cshow 4158 491 M 4158 522 L 4158 4689 M 4158 4658 L 4158 351 M () Cshow 4332 491 M 4332 522 L 4332 4689 M 4332 4658 L 4332 351 M () Cshow 4414 491 M 4414 554 L 4414 4689 M 4414 4626 L 4414 351 M (10000) Cshow 4671 491 M 4671 522 L 4671 4689 M 4671 4658 L 4671 351 M () Cshow 5010 491 M 5010 522 L 5010 4689 M 5010 4658 L 5010 351 M () Cshow 5183 491 M 5183 522 L 5183 4689 M 5183 4658 L 5183 351 M () Cshow 5266 491 M 5266 554 L 5266 4689 M 5266 4626 L 5266 351 M (100000) Cshow 5522 491 M 5522 522 L 5522 4689 M 5522 4658 L 5522 351 M () Cshow 5861 491 M 5861 522 L 5861 4689 M 5861 4658 L 5861 351 M () Cshow 6035 491 M 6035 522 L 6035 4689 M 6035 4658 L 6035 351 M () Cshow 6117 491 M 6117 554 L 6117 4689 M 6117 4626 L 6117 351 M (1e+06) Cshow 6374 491 M 6374 522 L 6374 4689 M 6374 4658 L 6374 351 M () Cshow 6713 491 M 6713 522 L 6713 4689 M 6713 4658 L 6713 351 M () Cshow 6886 491 M 6886 522 L 6886 4689 M 6886 4658 L 6886 351 M () Cshow 6969 491 M 6969 554 L 6969 4689 M 6969 4626 L 6969 351 M (1e+07) Cshow LTb 1008 491 M 6969 491 L 6969 4689 L 1008 4689 L 1008 491 L 140 2590 M currentpoint gsave translate 90 rotate 0 0 moveto (time) Cshow grestore 3988 211 M (problem size in bytes) Cshow LT0 LT0 6117 1890 M (short vec) Rshow 6201 1890 M 6453 1890 L 1777 1403 M 1777 1403 L 2033 1409 L 2290 1412 L 2546 1417 L 2802 1406 L 3059 1418 L 3315 1423 L 3571 1448 L 3828 1489 L 4084 1556 L 4341 1674 L 4597 1868 L 4853 2121 L 5110 2413 L 5366 2758 L 5622 3134 L 5879 3533 L 6135 3939 L 6285 1890 T 1777 1403 T 2033 1409 T 2290 1412 T 2546 1417 T 2802 1406 T 3059 1418 T 3315 1423 T 3571 1448 T 3828 1489 T 4084 1556 T 4341 1674 T 4597 1868 T 4853 2121 T 5110 2413 T 5366 2758 T 5622 3134 T 5879 3533 T 6135 3939 T LT0 6117 1750 M (long vec) Rshow 6201 1750 M 6453 1750 L 1777 2421 M 1777 2421 L 2033 2420 L 2290 2418 L 2546 2421 L 2802 2427 L 3059 2439 L 3315 2440 L 3571 2449 L 3828 2461 L 4084 2472 L 4341 2460 L 4597 2469 L 4853 2561 L 5110 2582 L 5366 2642 L 5622 2747 L 5879 2962 L 6135 3242 L 6285 1750 S 1777 2421 S 2033 2420 S 2290 2418 S 2546 2421 S 2802 2427 S 3059 2439 S 3315 2440 S 3571 2449 S 3828 2461 S 4084 2472 S 4341 2460 S 4597 2469 S 4853 2561 S 5110 2582 S 5366 2642 S 5622 2747 S 5879 2962 S 6135 3242 S LT0 6117 1610 M (HYBRID gcolx) Rshow 6201 1610 M 6453 1610 L 1777 1443 M 1777 1443 L 2033 1442 L 2290 1433 L 2546 1431 L 2802 1424 L 3059 1430 L 3315 1456 L 3571 1473 L 3828 1533 L 4084 1579 L 4341 1689 L 4597 1893 L 4853 1922 L 5110 2088 L 5366 2333 L 5622 2626 L 5879 2993 L 6135 3160 L 6285 1610 C 1777 1443 C 2033 1442 C 2290 1433 C 2546 1431 C 2802 1424 C 3059 1430 C 3315 1456 C 3571 1473 C 3828 1533 C 4084 1579 C 4341 1689 C 4597 1893 C 4853 1922 C 5110 2088 C 5366 2333 C 5622 2626 C 5879 2993 C 6135 3160 C stroke grestore end showpage %%EndDocument endTexFig -57 1813 2058 2 v 391 1848 a Ft(Scatter)p 967 1863 2 50 v 976 1863 V 905 w(Scatter)-32 1863 y 15392931 11840716 3289088 3289088 26970521 19866091 startTexFig -32 1863 a %%BeginDocument: scat16x32.ps /gnudict 40 dict def gnudict begin /Color false def /gnulinewidth 5.000 def /vshift -46 def /dl {10 mul} def /hpt 31.5 def /vpt 31.5 def /vpt2 vpt 2 mul def /hpt2 hpt 2 mul def /Lshow { currentpoint stroke moveto 0 vshift rmoveto show } def /Rshow { currentpoint stroke moveto dup stringwidth pop neg vshift rmoveto show } def /Cshow { currentpoint stroke moveto dup stringwidth pop -2 div vshift rmoveto show } def /DL { Color {setrgbcolor [] 0 setdash pop} {pop pop pop 0 setdash} ifelse } def /BL { stroke gnulinewidth 2 mul setlinewidth } def /AL { stroke gnulinewidth 2 div setlinewidth } def /PL { stroke gnulinewidth setlinewidth } def /LTb { BL [] 0 0 0 DL } def /LTa { AL [1 dl 2 dl] 0 setdash 0 0 0 setrgbcolor } def /LT0 { PL [] 0 1 0 DL } def /LT1 { PL [4 dl 2 dl] 0 0 1 DL } def /LT2 { PL [2 dl 3 dl] 1 0 0 DL } def /LT3 { PL [1 dl 1.5 dl] 1 0 1 DL } def /LT4 { PL [5 dl 2 dl 1 dl 2 dl] 0 1 1 DL } def /LT5 { PL [4 dl 3 dl 1 dl 3 dl] 1 1 0 DL } def /LT6 { PL [2 dl 2 dl 2 dl 4 dl] 0 0 0 DL } def /LT7 { PL [2 dl 2 dl 2 dl 2 dl 2 dl 4 dl] 1 0.3 0 DL } def /LT8 { PL [2 dl 2 dl 2 dl 2 dl 2 dl 2 dl 2 dl 4 dl] 0.5 0.5 0.5 DL } def /M {moveto} def /L {lineto} def /P { stroke [] 0 setdash currentlinewidth 2 div sub moveto 0 currentlinewidth rlineto stroke } def /D { stroke [] 0 setdash 2 copy vpt add moveto hpt neg vpt neg rlineto hpt vpt neg rlineto hpt vpt rlineto hpt neg vpt rlineto closepath stroke P } def /A { stroke [] 0 setdash vpt sub moveto 0 vpt2 rlineto currentpoint stroke moveto hpt neg vpt neg rmoveto hpt2 0 rlineto stroke } def /B { stroke [] 0 setdash 2 copy exch hpt sub exch vpt add moveto 0 vpt2 neg rlineto hpt2 0 rlineto 0 vpt2 rlineto hpt2 neg 0 rlineto closepath stroke P } def /C { stroke [] 0 setdash exch hpt sub exch vpt add moveto hpt2 vpt2 neg rlineto currentpoint stroke moveto hpt2 neg 0 rmoveto hpt2 vpt2 rlineto stroke } def /T { stroke [] 0 setdash 2 copy vpt 1.12 mul add moveto hpt neg vpt -1.62 mul rlineto hpt 2 mul 0 rlineto hpt neg vpt 1.62 mul rlineto closepath stroke P } def /S { 2 copy A C} def end gnudict begin gsave 50 50 translate 0.050 0.050 scale 0 setgray /Courier findfont 140 scalefont setfont newpath LTa LTb 1008 491 M 1071 491 L 6969 491 M 6906 491 L 924 491 M (0.001) Rshow 1008 912 M 1039 912 L 6969 912 M 6938 912 L 924 912 M () Rshow 1008 1159 M 1039 1159 L 6969 1159 M 6938 1159 L 924 1159 M () Rshow 1008 1333 M 1039 1333 L 6969 1333 M 6938 1333 L 924 1333 M () Rshow 1008 1469 M 1039 1469 L 6969 1469 M 6938 1469 L 924 1469 M () Rshow 1008 1580 M 1039 1580 L 6969 1580 M 6938 1580 L 924 1580 M () Rshow 1008 1674 M 1039 1674 L 6969 1674 M 6938 1674 L 924 1674 M () Rshow 1008 1755 M 1039 1755 L 6969 1755 M 6938 1755 L 924 1755 M () Rshow 1008 1826 M 1039 1826 L 6969 1826 M 6938 1826 L 924 1826 M () Rshow 1008 1890 M 1071 1890 L 6969 1890 M 6906 1890 L 924 1890 M (0.01) Rshow 1008 2312 M 1039 2312 L 6969 2312 M 6938 2312 L 924 2312 M () Rshow 1008 2558 M 1039 2558 L 6969 2558 M 6938 2558 L 924 2558 M () Rshow 1008 2733 M 1039 2733 L 6969 2733 M 6938 2733 L 924 2733 M () Rshow 1008 2868 M 1039 2868 L 6969 2868 M 6938 2868 L 924 2868 M () Rshow 1008 2979 M 1039 2979 L 6969 2979 M 6938 2979 L 924 2979 M () Rshow 1008 3073 M 1039 3073 L 6969 3073 M 6938 3073 L 924 3073 M () Rshow 1008 3154 M 1039 3154 L 6969 3154 M 6938 3154 L 924 3154 M () Rshow 1008 3226 M 1039 3226 L 6969 3226 M 6938 3226 L 924 3226 M () Rshow 1008 3290 M 1071 3290 L 6969 3290 M 6906 3290 L 924 3290 M (0.1) Rshow 1008 3711 M 1039 3711 L 6969 3711 M 6938 3711 L 924 3711 M () Rshow 1008 3957 M 1039 3957 L 6969 3957 M 6938 3957 L 924 3957 M () Rshow 1008 4132 M 1039 4132 L 6969 4132 M 6938 4132 L 924 4132 M () Rshow 1008 4268 M 1039 4268 L 6969 4268 M 6938 4268 L 924 4268 M () Rshow 1008 4379 M 1039 4379 L 6969 4379 M 6938 4379 L 924 4379 M () Rshow 1008 4472 M 1039 4472 L 6969 4472 M 6938 4472 L 924 4472 M () Rshow 1008 4553 M 1039 4553 L 6969 4553 M 6938 4553 L 924 4553 M () Rshow 1008 4625 M 1039 4625 L 6969 4625 M 6938 4625 L 924 4625 M () Rshow 1008 4689 M 1071 4689 L 6969 4689 M 6906 4689 L 924 4689 M (1) Rshow 1008 491 M 1008 554 L 1008 4689 M 1008 4626 L 1008 351 M (1) Cshow 1264 491 M 1264 522 L 1264 4689 M 1264 4658 L 1264 351 M () Cshow 1603 491 M 1603 522 L 1603 4689 M 1603 4658 L 1603 351 M () Cshow 1777 491 M 1777 522 L 1777 4689 M 1777 4658 L 1777 351 M () Cshow 1860 491 M 1860 554 L 1860 4689 M 1860 4626 L 1860 351 M (10) Cshow 2116 491 M 2116 522 L 2116 4689 M 2116 4658 L 2116 351 M () Cshow 2455 491 M 2455 522 L 2455 4689 M 2455 4658 L 2455 351 M () Cshow 2629 491 M 2629 522 L 2629 4689 M 2629 4658 L 2629 351 M () Cshow 2711 491 M 2711 554 L 2711 4689 M 2711 4626 L 2711 351 M (100) Cshow 2967 491 M 2967 522 L 2967 4689 M 2967 4658 L 2967 351 M () Cshow 3306 491 M 3306 522 L 3306 4689 M 3306 4658 L 3306 351 M () Cshow 3480 491 M 3480 522 L 3480 4689 M 3480 4658 L 3480 351 M () Cshow 3563 491 M 3563 554 L 3563 4689 M 3563 4626 L 3563 351 M (1000) Cshow 3819 491 M 3819 522 L 3819 4689 M 3819 4658 L 3819 351 M () Cshow 4158 491 M 4158 522 L 4158 4689 M 4158 4658 L 4158 351 M () Cshow 4332 491 M 4332 522 L 4332 4689 M 4332 4658 L 4332 351 M () Cshow 4414 491 M 4414 554 L 4414 4689 M 4414 4626 L 4414 351 M (10000) Cshow 4671 491 M 4671 522 L 4671 4689 M 4671 4658 L 4671 351 M () Cshow 5010 491 M 5010 522 L 5010 4689 M 5010 4658 L 5010 351 M () Cshow 5183 491 M 5183 522 L 5183 4689 M 5183 4658 L 5183 351 M () Cshow 5266 491 M 5266 554 L 5266 4689 M 5266 4626 L 5266 351 M (100000) Cshow 5522 491 M 5522 522 L 5522 4689 M 5522 4658 L 5522 351 M () Cshow 5861 491 M 5861 522 L 5861 4689 M 5861 4658 L 5861 351 M () Cshow 6035 491 M 6035 522 L 6035 4689 M 6035 4658 L 6035 351 M () Cshow 6117 491 M 6117 554 L 6117 4689 M 6117 4626 L 6117 351 M (1e+06) Cshow 6374 491 M 6374 522 L 6374 4689 M 6374 4658 L 6374 351 M () Cshow 6713 491 M 6713 522 L 6713 4689 M 6713 4658 L 6713 351 M () Cshow 6886 491 M 6886 522 L 6886 4689 M 6886 4658 L 6886 351 M () Cshow 6969 491 M 6969 554 L 6969 4689 M 6969 4626 L 6969 351 M (1e+07) Cshow LTb 1008 491 M 6969 491 L 6969 4689 L 1008 4689 L 1008 491 L 140 2590 M currentpoint gsave translate 90 rotate 0 0 moveto (time) Cshow grestore 3988 211 M (problem size in bytes) Cshow LT0 LT0 2711 3957 M (short vec) Rshow 2795 3957 M 3047 3957 L 1777 594 M 1777 594 L 2033 594 L 2290 603 L 2546 597 L 2802 601 L 3059 597 L 3315 604 L 3571 628 L 3828 752 L 4084 893 L 4341 1096 L 4597 1320 L 4853 1613 L 5110 1953 L 5366 2341 L 5622 2722 L 5879 3121 L 6135 3529 L 2879 3957 B 1777 594 B 2033 594 B 2290 603 B 2546 597 B 2802 601 B 3059 597 B 3315 604 B 3571 628 B 3828 752 B 4084 893 B 4341 1096 B 4597 1320 B 4853 1613 B 5110 1953 B 5366 2341 B 5622 2722 B 5879 3121 B 6135 3529 B LT0 2711 3817 M (long vec) Rshow 2795 3817 M 3047 3817 L 1777 1072 M 1777 1072 L 2033 1095 L 2290 1085 L 2546 1074 L 2802 1084 L 3059 1092 L 3315 1090 L 3571 1083 L 3828 1089 L 4084 1123 L 4341 1184 L 4597 1247 L 4853 1333 L 5110 1467 L 5366 1724 L 5622 1981 L 5879 2287 L 6135 2640 L 2879 3817 T 1777 1072 T 2033 1095 T 2290 1085 T 2546 1074 T 2802 1084 T 3059 1092 T 3315 1090 T 3571 1083 T 3828 1089 T 4084 1123 T 4341 1184 T 4597 1247 T 4853 1333 T 5110 1467 T 5366 1724 T 5622 1981 T 5879 2287 T 6135 2640 T LT0 2711 3677 M (HYBRID gscat) Rshow 2795 3677 M 3047 3677 L 1777 626 M 1777 626 L 2033 612 L 2290 630 L 2546 638 L 2802 615 L 3059 627 L 3315 631 L 3571 675 L 3828 784 L 4084 928 L 4341 928 L 4597 1013 L 4853 1240 L 5110 1399 L 5366 1710 L 5622 1969 L 5879 2284 L 6135 2653 L 2879 3677 C 1777 626 C 2033 612 C 2290 630 C 2546 638 C 2802 615 C 3059 627 C 3315 631 C 3571 675 C 3828 784 C 4084 928 C 4341 928 C 4597 1013 C 4853 1240 C 5110 1399 C 5366 1710 C 5622 1969 C 5879 2284 C 6135 2653 C stroke grestore end showpage %%EndDocument endTexFig 967 2613 2 750 v 976 2613 V 1001 1863 a 15392931 11840716 3289088 3289088 26970521 19866091 startTexFig 1001 1863 a %%BeginDocument: scat15x30.ps /gnudict 40 dict def gnudict begin /Color false def /gnulinewidth 5.000 def /vshift -46 def /dl {10 mul} def /hpt 31.5 def /vpt 31.5 def /vpt2 vpt 2 mul def /hpt2 hpt 2 mul def /Lshow { currentpoint stroke moveto 0 vshift rmoveto show } def /Rshow { currentpoint stroke moveto dup stringwidth pop neg vshift rmoveto show } def /Cshow { currentpoint stroke moveto dup stringwidth pop -2 div vshift rmoveto show } def /DL { Color {setrgbcolor [] 0 setdash pop} {pop pop pop 0 setdash} ifelse } def /BL { stroke gnulinewidth 2 mul setlinewidth } def /AL { stroke gnulinewidth 2 div setlinewidth } def /PL { stroke gnulinewidth setlinewidth } def /LTb { BL [] 0 0 0 DL } def /LTa { AL [1 dl 2 dl] 0 setdash 0 0 0 setrgbcolor } def /LT0 { PL [] 0 1 0 DL } def /LT1 { PL [4 dl 2 dl] 0 0 1 DL } def /LT2 { PL [2 dl 3 dl] 1 0 0 DL } def /LT3 { PL [1 dl 1.5 dl] 1 0 1 DL } def /LT4 { PL [5 dl 2 dl 1 dl 2 dl] 0 1 1 DL } def /LT5 { PL [4 dl 3 dl 1 dl 3 dl] 1 1 0 DL } def /LT6 { PL [2 dl 2 dl 2 dl 4 dl] 0 0 0 DL } def /LT7 { PL [2 dl 2 dl 2 dl 2 dl 2 dl 4 dl] 1 0.3 0 DL } def /LT8 { PL [2 dl 2 dl 2 dl 2 dl 2 dl 2 dl 2 dl 4 dl] 0.5 0.5 0.5 DL } def /M {moveto} def /L {lineto} def /P { stroke [] 0 setdash currentlinewidth 2 div sub moveto 0 currentlinewidth rlineto stroke } def /D { stroke [] 0 setdash 2 copy vpt add moveto hpt neg vpt neg rlineto hpt vpt neg rlineto hpt vpt rlineto hpt neg vpt rlineto closepath stroke P } def /A { stroke [] 0 setdash vpt sub moveto 0 vpt2 rlineto currentpoint stroke moveto hpt neg vpt neg rmoveto hpt2 0 rlineto stroke } def /B { stroke [] 0 setdash 2 copy exch hpt sub exch vpt add moveto 0 vpt2 neg rlineto hpt2 0 rlineto 0 vpt2 rlineto hpt2 neg 0 rlineto closepath stroke P } def /C { stroke [] 0 setdash exch hpt sub exch vpt add moveto hpt2 vpt2 neg rlineto currentpoint stroke moveto hpt2 neg 0 rmoveto hpt2 vpt2 rlineto stroke } def /T { stroke [] 0 setdash 2 copy vpt 1.12 mul add moveto hpt neg vpt -1.62 mul rlineto hpt 2 mul 0 rlineto hpt neg vpt 1.62 mul rlineto closepath stroke P } def /S { 2 copy A C} def end gnudict begin gsave 50 50 translate 0.050 0.050 scale 0 setgray /Courier findfont 140 scalefont setfont newpath LTa LTb 1008 491 M 1071 491 L 6969 491 M 6906 491 L 924 491 M (0.001) Rshow 1008 912 M 1039 912 L 6969 912 M 6938 912 L 924 912 M () Rshow 1008 1159 M 1039 1159 L 6969 1159 M 6938 1159 L 924 1159 M () Rshow 1008 1333 M 1039 1333 L 6969 1333 M 6938 1333 L 924 1333 M () Rshow 1008 1469 M 1039 1469 L 6969 1469 M 6938 1469 L 924 1469 M () Rshow 1008 1580 M 1039 1580 L 6969 1580 M 6938 1580 L 924 1580 M () Rshow 1008 1674 M 1039 1674 L 6969 1674 M 6938 1674 L 924 1674 M () Rshow 1008 1755 M 1039 1755 L 6969 1755 M 6938 1755 L 924 1755 M () Rshow 1008 1826 M 1039 1826 L 6969 1826 M 6938 1826 L 924 1826 M () Rshow 1008 1890 M 1071 1890 L 6969 1890 M 6906 1890 L 924 1890 M (0.01) Rshow 1008 2312 M 1039 2312 L 6969 2312 M 6938 2312 L 924 2312 M () Rshow 1008 2558 M 1039 2558 L 6969 2558 M 6938 2558 L 924 2558 M () Rshow 1008 2733 M 1039 2733 L 6969 2733 M 6938 2733 L 924 2733 M () Rshow 1008 2868 M 1039 2868 L 6969 2868 M 6938 2868 L 924 2868 M () Rshow 1008 2979 M 1039 2979 L 6969 2979 M 6938 2979 L 924 2979 M () Rshow 1008 3073 M 1039 3073 L 6969 3073 M 6938 3073 L 924 3073 M () Rshow 1008 3154 M 1039 3154 L 6969 3154 M 6938 3154 L 924 3154 M () Rshow 1008 3226 M 1039 3226 L 6969 3226 M 6938 3226 L 924 3226 M () Rshow 1008 3290 M 1071 3290 L 6969 3290 M 6906 3290 L 924 3290 M (0.1) Rshow 1008 3711 M 1039 3711 L 6969 3711 M 6938 3711 L 924 3711 M () Rshow 1008 3957 M 1039 3957 L 6969 3957 M 6938 3957 L 924 3957 M () Rshow 1008 4132 M 1039 4132 L 6969 4132 M 6938 4132 L 924 4132 M () Rshow 1008 4268 M 1039 4268 L 6969 4268 M 6938 4268 L 924 4268 M () Rshow 1008 4379 M 1039 4379 L 6969 4379 M 6938 4379 L 924 4379 M () Rshow 1008 4472 M 1039 4472 L 6969 4472 M 6938 4472 L 924 4472 M () Rshow 1008 4553 M 1039 4553 L 6969 4553 M 6938 4553 L 924 4553 M () Rshow 1008 4625 M 1039 4625 L 6969 4625 M 6938 4625 L 924 4625 M () Rshow 1008 4689 M 1071 4689 L 6969 4689 M 6906 4689 L 924 4689 M (1) Rshow 1008 491 M 1008 554 L 1008 4689 M 1008 4626 L 1008 351 M (1) Cshow 1264 491 M 1264 522 L 1264 4689 M 1264 4658 L 1264 351 M () Cshow 1603 491 M 1603 522 L 1603 4689 M 1603 4658 L 1603 351 M () Cshow 1777 491 M 1777 522 L 1777 4689 M 1777 4658 L 1777 351 M () Cshow 1860 491 M 1860 554 L 1860 4689 M 1860 4626 L 1860 351 M (10) Cshow 2116 491 M 2116 522 L 2116 4689 M 2116 4658 L 2116 351 M () Cshow 2455 491 M 2455 522 L 2455 4689 M 2455 4658 L 2455 351 M () Cshow 2629 491 M 2629 522 L 2629 4689 M 2629 4658 L 2629 351 M () Cshow 2711 491 M 2711 554 L 2711 4689 M 2711 4626 L 2711 351 M (100) Cshow 2967 491 M 2967 522 L 2967 4689 M 2967 4658 L 2967 351 M () Cshow 3306 491 M 3306 522 L 3306 4689 M 3306 4658 L 3306 351 M () Cshow 3480 491 M 3480 522 L 3480 4689 M 3480 4658 L 3480 351 M () Cshow 3563 491 M 3563 554 L 3563 4689 M 3563 4626 L 3563 351 M (1000) Cshow 3819 491 M 3819 522 L 3819 4689 M 3819 4658 L 3819 351 M () Cshow 4158 491 M 4158 522 L 4158 4689 M 4158 4658 L 4158 351 M () Cshow 4332 491 M 4332 522 L 4332 4689 M 4332 4658 L 4332 351 M () Cshow 4414 491 M 4414 554 L 4414 4689 M 4414 4626 L 4414 351 M (10000) Cshow 4671 491 M 4671 522 L 4671 4689 M 4671 4658 L 4671 351 M () Cshow 5010 491 M 5010 522 L 5010 4689 M 5010 4658 L 5010 351 M () Cshow 5183 491 M 5183 522 L 5183 4689 M 5183 4658 L 5183 351 M () Cshow 5266 491 M 5266 554 L 5266 4689 M 5266 4626 L 5266 351 M (100000) Cshow 5522 491 M 5522 522 L 5522 4689 M 5522 4658 L 5522 351 M () Cshow 5861 491 M 5861 522 L 5861 4689 M 5861 4658 L 5861 351 M () Cshow 6035 491 M 6035 522 L 6035 4689 M 6035 4658 L 6035 351 M () Cshow 6117 491 M 6117 554 L 6117 4689 M 6117 4626 L 6117 351 M (1e+06) Cshow 6374 491 M 6374 522 L 6374 4689 M 6374 4658 L 6374 351 M () Cshow 6713 491 M 6713 522 L 6713 4689 M 6713 4658 L 6713 351 M () Cshow 6886 491 M 6886 522 L 6886 4689 M 6886 4658 L 6886 351 M () Cshow 6969 491 M 6969 554 L 6969 4689 M 6969 4626 L 6969 351 M (1e+07) Cshow LTb 1008 491 M 6969 491 L 6969 4689 L 1008 4689 L 1008 491 L 140 2590 M currentpoint gsave translate 90 rotate 0 0 moveto (time) Cshow grestore 3988 211 M (problem size in bytes) Cshow LT0 LT0 2711 3957 M (short vec) Rshow 2795 3957 M 3047 3957 L 1777 625 M 1777 625 L 2033 608 L 2290 634 L 2546 625 L 2802 609 L 3059 624 L 3315 623 L 3571 683 L 3828 781 L 4084 954 L 4341 1154 L 4597 1399 L 4853 1667 L 5110 1995 L 5366 2385 L 5622 2767 L 5879 3170 L 6135 3575 L 2879 3957 B 1777 625 B 2033 608 B 2290 634 B 2546 625 B 2802 609 B 3059 624 B 3315 623 B 3571 683 B 3828 781 B 4084 954 B 4341 1154 B 4597 1399 B 4853 1667 B 5110 1995 B 5366 2385 B 5622 2767 B 5879 3170 B 6135 3575 B LT0 2711 3817 M (long vec) Rshow 2795 3817 M 3047 3817 L 1777 1066 M 1777 1066 L 2033 1064 L 2290 1081 L 2546 1085 L 2802 1086 L 3059 1065 L 3315 1085 L 3571 1094 L 3828 1104 L 4084 1141 L 4341 1196 L 4597 1279 L 4853 1399 L 5110 1524 L 5366 1778 L 5622 2024 L 5879 2380 L 6135 2735 L 2879 3817 T 1777 1066 T 2033 1064 T 2290 1081 T 2546 1085 T 2802 1086 T 3059 1065 T 3315 1085 T 3571 1094 T 3828 1104 T 4084 1141 T 4341 1196 T 4597 1279 T 4853 1399 T 5110 1524 T 5366 1778 T 5622 2024 T 5879 2380 T 6135 2735 T LT0 2711 3677 M (HYBRID gscat) Rshow 2795 3677 M 3047 3677 L 1777 631 M 1777 631 L 2033 631 L 2290 636 L 2546 641 L 2802 645 L 3059 635 L 3315 638 L 3571 671 L 3828 787 L 4084 960 L 4341 1151 L 4597 1389 L 4853 1298 L 5110 1468 L 5366 1738 L 5622 2020 L 5879 2388 L 6135 2749 L 2879 3677 C 1777 631 C 2033 631 C 2290 636 C 2546 641 C 2802 645 C 3059 635 C 3315 638 C 3571 671 C 3828 787 C 4084 960 C 4341 1151 C 4597 1389 C 4853 1298 C 5110 1468 C 5366 1738 C 5622 2020 C 5879 2388 C 6135 2749 C stroke grestore end showpage %%EndDocument endTexFig 325 2729 a Ft(Figure)14 b(4:)k(P)o(erformance)13 b(of)h(the)g(v)n (arious)f(algorithms)f(on)i(the)g(In)o(tel)g(P)o(aragon.)p eop %%Page: 8 8 8 7 bop -57 117 a Ft(System)16 b(op)q(erated)h(b)o(y)f(the)h (California)c(Institute)k(of)f(T)m(ec)o(h-)-57 166 y(nology)g(on)i(b)q (ehalf)f(of)g(the)h(Concurren)o(t)h(Sup)q(ercomputing)-57 216 y(Consortium.)27 b(Access)19 b(to)f(this)f(facilit)o(y)f(w)o(as)h (pro)o(vided)g(b)o(y)-57 266 y(In)o(tel)g(Sup)q(ercomputer)h(Systems)g (Division)d(and)j(the)g(Cali-)-57 316 y(fornia)13 b(Institute)i(of)e(T) m(ec)o(hnology)m(.)-57 478 y Fs(Obtaining)18 b(Do)r(cumen)n(tation)-7 582 y Ft(A)h(n)o(um)o(b)q(er)g(of)f(the)i(men)o(tioned)e(pap)q(ers)j (that)e(inspired)-57 632 y(this)28 b(w)o(ork)g(are)g(a)o(v)n(ailable)e (via)h(anon)o(ymous)g Fa(ftp)g Ft(from)-57 681 y Fa(cs.utexas.edu)21 b Ft(directory)j Fa(pub/rvdg)p Ft(.)46 b(Man)o(uals)23 b(and)-57 731 y(other)29 b(information)c(regarding)k(the)g(In)o(terCom) e(library)-57 781 y(can)h(b)q(e)g(found)f(there)i(as)e(w)o(ell.)59 b(T)m(o)26 b(obtain)h(the)h(In-)-57 831 y(terCom)23 b(library)g(for)h (In)o(tel)g(P)o(aragon)f(systems,)k(con)o(tact)-57 881 y Fa(shuler@cs.utexas.)o(edu)p Ft(.)43 b(F)m(or)22 b(the)i(iPSC/860)e (imple-)-57 930 y(men)o(tation,)12 b(con)o(tact)i Fa (jwatts@chpc.utexas)o(.edu)p Ft(.)-57 1197 y(The)h(b)q(o)q(dy)h(of)e (pap)q(ers)i(related)g(to)f(the)g(implemen)o(tation)d(of)-57 1246 y(comm)o(unication)f(algorithms)h(on)h(v)n(arious)h(arc)o (hitectures)i(is)-57 1296 y(v)n(ast.)38 b(W)m(e)20 b(limit)d(ourselv)o (es)22 b(to)e(listing)g(our)g(o)o(wn)g(pap)q(ers)-57 1346 y(that)15 b(led)g(us)g(to)g(the)g(presen)o(ted)i(approac)o(h,)e (and)g(a)f(few)h(k)o(ey)-57 1396 y(pap)q(ers)i(of)f(others.)26 b(F)m(urther)17 b(references)i(can)e(b)q(e)g(found)f(in)-57 1446 y(the)e(bibliographies)f(of)g(those)i(pap)q(ers.)-57 1608 y Fs(References)-57 1712 y Ft([1])20 b(M.)30 b(Barnett,)36 b(R.)30 b(Little\014eld,)35 b(D.G.)29 b(P)o(a)o(yne,)35 b(and)8 1761 y(R.)14 b(v)n(an)g(de)h(Geijn.)21 b(E\016cien)o(t)15 b(Comm)o(unicati)o(on)d(Primi-)8 1811 y(tiv)o(es)h(on)g(Mesh)h(Arc)o (hitectures)i(with)d(Hardw)o(are)h(Rout-)8 1861 y(ing,)46 b(Sixth)23 b(SIAM)g(Conf.)f(on)g(P)o(ar.)h(Pro)q(c.)g(for)g(Sci.)8 1911 y(Comp.,)11 b(Norfolk,)h(Virginia,)g(Marc)o(h)i(22-24,)f(1993.)-57 2000 y([2])20 b(M.)30 b(Barnett,)36 b(R.)30 b(Little\014eld,)35 b(D.G.)29 b(P)o(a)o(yne,)35 b(and)8 2049 y(R.)26 b(v)n(an)h(de)h (Geijn,)62 b(Global)26 b(Com)o(bine)g(on)h(Mesh)8 2099 y(Arc)o(hitectures)d(with)d(W)m(ormhole)e(Routing,)42 b Fn(7th)22 b(In-)8 2149 y(ternational)16 b(Par)n(al)r(lel)g(Pr)n(o)n (c)n(essing)g(Symp)n(osium)p Ft(,)h(pages)8 2199 y(156{162,)12 b(IEEE)j(Computer)f(So)q(ciet)o(y)g(Press,)i(Newp)q(ort)8 2249 y(Beac)o(h,)e(CA,)f(April)h(13-16,)e(1993.)-57 2338 y([3])20 b(M.)g(Barnett,)j(D.G.)c(P)o(a)o(yne,)k(R.)c(v)n(an)i(de)g (Geijn,)g(and)8 2387 y(J.)e(W)m(atts,)36 b(Broadcasting)20 b(on)g(Meshes)h(with)f(W)m(orm-)8 2437 y(Hole)13 b(Routing,)k Fn(Journal)e(of)f(Par)n(al)r(lel)g(and)i(Distribute)n(d)8 2487 y(Computing)p Ft(,)d(submitted.)-57 2576 y([4])20 b(C.-T.)15 b(Ho)i(and)g(S.)f(L.)h(Johnsson,)29 b(Distributed)17 b(Rout-)8 2626 y(ing)c(Algorithms)e(for)j(Broadcasting)g(and)f(P)o (ersonalized)8 2675 y(Comm)n(unication)e(in)k(Hyp)q(ercub)q(es,)23 b(In)15 b Fn(Pr)n(o)n(c)n(e)n(e)n(dings)g(of)8 2725 y(the)c(1986)h (International)f(Confer)n(enc)n(e)g(on)h(Par)n(al)r(lel)e(Pr)n(o-)8 2775 y(c)n(essing)p Ft(,)j(pages)h(640{648,)e(IEEE,)i(1986.)1013 117 y([5])19 b(R.)12 b(A.)h(v)n(an)f(de)i(Geijn.)h(E\016cien)o(t)f (Global)d(Com)o(bine)g(Op-)1077 166 y(erations.)37 b(In)20 b Fn(Sixth)h(Distribute)n(d)e(Memory)i(Comput-)1077 216 y(ing)16 b(Confer)n(enc)n(e)g(Pr)n(o)n(c)n(e)n(e)n(dings)p Ft(,)e(pages)i(291{294)n(.)e(IEEE)1077 266 y(Computer)g(So)q(ciet)o(y)g (Press,)h(1991.)1013 349 y([6])k(D.)12 b(W.)g(W)m(alk)o(er,)k(The)d (Design)g(of)f(a)h(Standard)g(Message)1077 399 y(P)o(assing)f(In)o (terface)h(for)f(Distributed)g(Memory)f(Concur-)1077 449 y(ren)o(t)j(Computers.)f(to)g(app)q(ear)g(in)g Fn(Par)n(al)r(lel)g (Computing)p Ft(,)1077 498 y(April)f(1994.)f(Upto)h(Date)g(information) d(ab)q(out)j(the)h(MPI)1077 548 y(standard)i(is)e(a)o(v)n(ailable)f (from)g Fa(netlib)p Ft(,)g(directory)j Fa(mpi)p Ft(.)p eop %%Trailer end userdict /end-hook known{end-hook}if %%EOF .