diff options
Diffstat (limited to 'parallel/the-aphid-parallel.ps')
| -rwxr-xr-x | parallel/the-aphid-parallel.ps | 3515 |
1 files changed, 3515 insertions, 0 deletions
diff --git a/parallel/the-aphid-parallel.ps b/parallel/the-aphid-parallel.ps new file mode 100755 index 0000000..71e3ce2 --- /dev/null +++ b/parallel/the-aphid-parallel.ps @@ -0,0 +1,3515 @@ +%!PS-Adobe-2.0 +%%Creator: dvipsk 5.58f Copyright 1986, 1994 Radical Eye Software +%%Title: aphidcut.dvi +%%Pages: 5 +%%PageOrder: Ascend +%%BoundingBox: 0 0 612 792 +%%DocumentFonts: Times-Bold Times-Roman Times-Italic Helvetica-Bold +%%+ Courier +%%EndComments +%DVIPSCommandLine: dvips aphidcut +%DVIPSParameters: dpi=300, compressed, comments removed +%DVIPSSource: TeX output 1996.07.17:1230 +%%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 round sub abs 0.00001 lt{round}if} +forall round exch round exch]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 sub]/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 userdict +/eop-hook known{eop-hook}if showpage}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 newpath 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: texps.pro +TeXDict begin /rf{findfont dup length 1 add dict begin{1 index /FID ne 2 +index /UniqueID ne and{def}{pop pop}ifelse}forall[1 index 0 6 -1 roll +exec 0 exch 5 -1 roll VResolution Resolution div mul neg 0 0]/Metrics +exch def dict begin Encoding{exch dup type /integertype ne{pop pop 1 sub +dup 0 le{pop}{[}ifelse}{FontMatrix 0 get div Metrics 0 get div def} +ifelse}forall Metrics /Metrics currentdict end def[2 index currentdict +end definefont 3 -1 roll makefont /setfont load]cvx def}def +/ObliqueSlant{dup sin S cos div neg}B /SlantFont{4 index mul add}def +/ExtendFont{3 -1 roll mul exch}def /ReEncodeFont{/Encoding exch def}def +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 true 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 (aphidcut.dvi) +@start /Fa 2 13 df<EA01F038070C08380C0E10EA1807123000701320126000E01340 +A214801400A3EA601B383063A0380F81C015107F8F19>11 D<EB03C0EB0C301310EB2038 +13401380EA0100A2000213701460EB1FC0131138041F60EB0070A35AA31460001813E014 +C0EB018038140300EA230EEA20F890C7FCA25AA45A1521809916>I +E /Fb 61[12 12 70[15 17 17 1[17 19 10 15 15 1[19 19 19 +27 10 2[10 19 19 10 17 19 17 19 19 13[19 2[23 2[31 2[17 +12 3[23 27 25 1[23 6[12 5[19 6[12 9 4[12 39[{}38 37.500000 +/Times-Italic rf /Fc 55[12 5[12 16[19 54[17 19 19 27 +19 19 10 15 12 1[19 19 19 29 10 19 1[10 19 19 12 17 19 +17 19 17 3[12 1[12 3[35 27 27 23 21 25 1[21 27 1[33 1[27 +15 12 27 27 21 23 27 25 25 27 6[10 19 19 19 19 19 19 +19 19 19 19 1[9 12 9 2[12 12 40[{}65 37.500000 /Times-Roman +rf /Fd 1 111 df<EA30F8EA590C124E129C12981218A2EA301813191331A2EA6032131C +100D7F8C15>110 D E /Fe 23 119 df<1380EA0100120212065AA25AA25AA35AA412E0 +AC1260A47EA37EA27EA27E12027EEA0080092A7C9E10>40 D<7E12407E12307EA27EA27E +A37EA41380AC1300A41206A35AA25AA25A12205A5A092A7E9E10>I<1306ADB612E0A2D8 +0006C7FCAD1B1C7E9720>43 D<5A1207123F12C71207B3A5EAFFF80D1C7C9B15>49 +D<EA07C0EA1830EA201CEA400C130EEAF00F12F81307A21270EA000F130EA2131CA21338 +1370136013C0EA0180EA0300EA0601120C1218EA1002EA3FFE127F12FF101C7E9B15>I< +130CA2131C133CA2135C13DC139CEA011C120312021204120C1208121012301220124012 +C0B512C038001C00A73801FFC0121C7F9B15>52 D<007FB512C0B612E0C9FCA8B612E06C +14C01B0C7E8F20>61 D<EA1FC0EA3070EA78387F12301200A2EA01FCEA0F1C1238127012 +6000E01340A3EA603C38304E80381F870012127E9115>97 D<EB1F801303AAEA03F3EA0E +0BEA1807EA30031270126012E0A6126012701230EA1807EA0E1B3803E3F0141D7F9C17> +100 D<EA07E0EA0C30EA1818EA300CEA700EEA600612E0EAFFFEEAE000A41260EA700212 +30EA1804EA0C18EA03E00F127F9112>I<12FC121CAA137C1387EA1D03001E1380121CAD +38FF9FF0141D7F9C17>104 D<1218123CA21218C7FCA712FC121CB0EAFF80091D7F9C0C> +I<12FC121CB3A9EAFF80091D7F9C0C>108 D<39FC7E07E0391C838838391D019018001E +EBE01C001C13C0AD3AFF8FF8FF8021127F9124>I<EAFC7CEA1C87EA1D03001E1380121C +AD38FF9FF014127F9117>I<EA03F0EA0E1CEA1806487E00701380EA600100E013C0A600 +601380EA700300301300EA1806EA0E1CEA03F012127F9115>I<EAFC7CEA1D87381E0180 +001C13C0EB00E0A21470A614E0A2EB01C0001E1380381D0700EA1CFC90C7FCA7B47E141A +7F9117>I<3803E080EA0E19EA1805EA3807EA7003A212E0A61270A2EA38071218EA0E1B +EA03E3EA0003A7EB1FF0141A7F9116>I<EAFCE0EA1D38EA1E78A2EA1C301300ACEAFFC0 +0D127F9110>I<EA1F90EA2070EA4030EAC010A212E0EAF800EA7F80EA3FE0EA0FF0EA00 +F8EA8038131812C0A2EAE010EAD060EA8FC00D127F9110>I<1204A4120CA2121C123CEA +FFE0EA1C00A91310A5120CEA0E20EA03C00C1A7F9910>I<38FC1F80EA1C03AD1307120C +EA0E1B3803E3F014127F9117>I<38FF07E0383C0380381C0100A2EA0E02A2EA0F06EA07 +04A2EA0388A213C8EA01D0A2EA00E0A3134013127F9116>I E /Ff +173[25 82[{}1 41.666668 /Courier rf /Fg 134[23 2[23 25 +14 23 16 1[25 25 25 1[12 2[12 25 25 14 23 25 23 1[23 +13[28 2[28 32 3[30 1[12 30 1[25 1[30 2[30 13[23 23 23 +2[12 46[{}31 41.666668 /Helvetica-Bold rf /Fh 137[23 +1[15 18 20 1[25 23 25 38 13 2[13 25 1[15 20 2[25 23 12[30 +25 2[28 36 1[43 3[18 36 3[33 2[33 12[23 23 23 23 2[11 +46[{}29 45.833332 /Times-Bold rf /Fi 134[17 1[24 2[9 +13 11 1[17 17 17 26 9 2[9 17 17 11 15 17 2[15 12[20 35[17 +1[8 11 8 44[{}22 33.333332 /Times-Roman rf /Fj 1 50 df<1218127812981218 +AC12FF08107D8F0F>49 D E /Fk 2 4 df<B61280A219027D8A20>0 +D<1203A4EAC30CEAE31CEA7338EA1FE0EA0780A2EA1FE0EA7338EAE31CEAC30CEA0300A4 +0E127D9215>3 D E /Fl 1 49 df<1204120EA2121CA31238A212301270A21260A212C0 +A2070F7F8F0A>48 D E /Fm 1 50 df<120C121C12EC120CAFEAFFC00A137D9211>49 +D E /Fn 69[18 8[21 1[23 23 3[18 47[18 21 21 30 21 21 +12 16 14 21 21 21 21 32 12 21 12 12 21 21 14 18 21 18 +21 18 3[14 1[14 1[30 1[39 30 30 25 23 28 1[23 30 30 37 +25 30 16 14 30 30 23 25 30 28 28 30 5[12 12 21 21 21 +21 21 21 21 21 21 21 12 10 14 10 2[14 14 14 1[35 37[{}76 +41.666668 /Times-Roman rf /Fo 10 123 df<13F8EA030C380E0604EA1C0738380308 +0030138800701390A200E013A0A214C01480A3EA6007EB0B8838307190380F80E016127E +911B>11 D<EB01F0EB0618EB080C1310EB200E13401380141CEA01001418143838020FF0 +EB10C0EB0FE0EB00305AA21438A2481370A314E01218EB01C000141380EB0300EA230EEA +20F890C7FCA25AA45AA217257F9C17>I<90B512E09038F001C03901C003809038800700 +EB000E141E0002131C5C5CC75A495A495A49C7FC5B131E131C5BEB7002495AEA01C0EA03 +8048485A5A000E1318485B48137048485AB5FC1B1C7E9B1C>90 D<EA01E3EA0717EA0C0F +1218EA380E12301270A2485AA4EB3880A3EA607838319900EA1E0E11127E9116>97 +D<EB07E01300A2EB01C0A4EB0380A43801E700EA0717EA0C0F1218EA380E12301270A248 +5AA4EB3880A3EA607838319900EA1E0E131D7E9C16>100 D<EB38C013C5EA0183EA0303 +000713801206120EA2381C0700A4130EA3EA0C1EEA047CEA039CEA001CA25B1260EAF030 +1370EAE0C0007FC7FC121A809114>103 D<EA3C1F384E6180384681C0EA4701128F128E +120EA2381C0380A3EB070000381310A2130E1420387006403830038014127E9119>110 +D<001C13C0EA27011247A238870380A2120EA2381C0700A438180E20A3EA1C1E380C2640 +3807C38013127E9118>117 D<001CEBC080392701C1C0124714C03987038040A2120EA2 +391C070080A3EC0100EA1806A2381C0E02EB0F04380E13083803E1F01A127E911E>119 +D<EA0381EA07C1EA0FF6EA081CEA1008EA0010132013401380EA010012025AEA08041210 +EA3C18EA67F8EA43F0EA81E010127E9113>122 D E /Fp 133[16 +18 1[28 18 21 12 16 16 1[21 21 21 30 12 18 1[12 21 21 +12 18 21 18 21 21 7[23 1[35 2[23 1[25 1[25 30 5[14 30 +3[30 1[25 25 18[10 14 10 2[14 14 40[{}39 41.666668 /Times-Italic +rf /Fq 135[25 36 1[28 17 19 22 1[28 25 28 41 14 28 1[14 +28 25 17 22 28 22 28 25 9[50 2[33 1[36 1[30 6[19 39 1[30 +33 36 36 1[36 11[25 25 25 25 25 2[12 46[{}38 50.000000 +/Times-Bold rf /Fr 2 104 df<EB03C0EB1E0013385B5BB1485A485A000FC7FC12F812 +0FEA03806C7E6C7EB113707F131EEB03C012317DA419>102 D<12F8120FEA03806C7E6C +7EB113707F131EEB03C0EB1E0013385B5BB1485A485A000FC7FC12F812317DA419>I +E /Fs 134[25 2[25 25 14 19 17 1[25 25 25 39 14 25 14 +14 25 25 17 22 25 22 25 22 11[36 30 28 5[44 2[19 1[36 +36 1[30 36 33 33 36 46 9[25 3[25 25 2[12 1[12 44[{}40 +50.000000 /Times-Roman rf /Ft 2 13 df<EB0FC0EB70709038C038013803801C3907 +001E02000E130E001E130F001C1404123C00381408127815105A15201540A21580481400 +A3127014170030EB67043918018788380C0E033903F000F0201A7D9925>11 +D<EC03F0EC0C1CEC300EEC4006EC8007EB010013025B150F5BA249130E151E49131C1538 +15309038403F60EC41C0EC3F60EC0070491338A3153C48C7FCA400021478A31570000614 +F015E0140115C00009EB0380EC07003808800EEB401C38103070EB0FC090C8FCA25AA45A +A45AA220367FA921>I E /Fu 139[20 1[27 2[30 1[50 17 2[17 +33 30 1[27 1[27 1[30 12[40 33 2[37 6[23 47 3[43 2[43 +65[{}18 59.999973 /Times-Bold rf end +%%EndProlog +%%BeginSetup +%%Feature: *Resolution 300dpi +TeXDict begin + +%%EndSetup +%%Page: 1 1 +1 0 bop 400 187 a Fu(The)14 b(APHID)h(Parallel)d Ft(\013\014)19 +b Fu(Sear)o(ch)14 b(Algorithm)487 345 y Fs(Mark)e(G.)h(Brockington)e +(and)i(Jonathan)f(Schaef)o(fer)368 403 y(Department)g(of)g(Computing)f +(Science,)i(University)f(of)g(Alberta)567 461 y(Edmonton,)h(Alberta)f +(T6G)g(2H1)h(Canada)602 519 y Fr(f)p Fs(brock,)f(jonathan)p +Fr(g)p Fs(@cs.ualberta.ca)308 694 y Fq(Abstract)-41 794 +y Fp(This)j(paper)g(intr)n(oduces)h(the)f(APHID)i(\(Asynchr)n(onous)f +(Par)o(-)-91 844 y(allel)g(Hierar)n(chical)i(Iterative)f(Deepening\))g +(game-tr)n(ee)h(sear)n(ch)-91 894 y(algorithm.)36 b(APHID)19 +b(r)n(epr)n(esents)i(a)d(departur)n(e)h(fr)n(om)g(the)f(ap-)-91 +944 y(pr)n(oaches)12 b(used)f(in)g(practice.)17 b(Instead)11 +b(of)g(parallelism)e(based)j(on)-91 993 y(the)k(minimal)f(sear)n(ch)j +(tr)n(ee,)i(APHID)d(uses)g(a)g(truncated)e(game-)-91 +1043 y(tr)n(ee)f(and)f(all)g(of)g(the)g(leaves)h(of)f(that)g(tr)n(ee)h +(ar)n(e)h(sear)n(ched)g(in)e(par)o(-)-91 1093 y(allel.)24 +b(APHID)14 b(has)g(been)g(pr)n(ogrammed)g(as)g(an)f(easy)i(to)e(imple-) +-91 1143 y(ment,)c(game-independent)f Fo(\013\014)k Fp(library)n(,)d +(and)f(has)h(been)h(tested)f(on)-91 1193 y(several)g(game-playing)d(pr) +n(ograms.)13 b(Results)8 b(for)g(an)g(Othello)e(pr)n(o-)-91 +1242 y(gram)h(ar)n(e)h(pr)n(esented)g(her)n(e.)14 b(The)8 +b(algorithm)t(yields)f(good)g(parallel)-91 1292 y(performance)k(on)f(a) +g(network)h(of)f(workstations,)f(without)g(using)g(a)-91 +1342 y(shar)n(ed)i(transposition)c(table.)-91 1485 y +Fq(1.)13 b(Intr)o(oduction)-41 1567 y Fn(The)f(alpha-beta)g(\()p +Fo(\013\014)r Fn(\))g(minimax)g(tree)g(search)h(algorithm)e(has)-91 +1612 y(proven)h(to)h(be)g(a)h(dif)o(\256cult)e(algorithm)f(to)i +(parallelize.)22 b(Although)-91 1658 y(simulations)8 +b(predict)g(excellent)h(parallel)g(performance,)i(most)e(re-)-91 +1704 y(sults)k(are)h(based)g(on)f(an)h(unreasonable)g(set)f(of)g +(assumptions.)24 b(In)-91 1749 y(practice,)12 b(knowing)d(where)j(to)e +(initiate)g(parallel)g(activity)g(is)h(dif)o(\256-)-91 +1795 y(cult)g(since)g(the)h(result)e(of)i(searching)f(one)h(node)f(at)g +(a)h(branch)g(may)-91 1841 y(obviate)d(the)h(parallel)g(work)g(of)g +(the)g(other)g(branches.)-41 1886 y(In)d(real-world)f(implementations,) +h(such)h(as)g(high)e(performance)-91 1932 y(chess,)20 +b(checkers)f(and)e(Othello)f(game-playing)h(programs,)i(the)-91 +1978 y(programs)13 b(suf)o(fer)h(from)f(three)h(major)f(sources)h(of)g +(parallel)f(inef-)-91 2023 y(\256ciency)e(\(a)f(similar)g(model)g(is)g +(presented)h(in)e([6]\).)-41 2069 y(The)15 b(\256rst)f(is)g +Fp(synchr)n(onization)f(over)o(head)p Fn(.)27 b(The)15 +b(search)g(typ-)-91 2115 y(ically)g(has)g(many)h(synchronization)e +(points)g(where)i(there)f(is)h(no)-91 2160 y(work)d(available,)i(which) +f(results)g(in)f(a)h(high)f(percentage)i(of)f(idle)-91 +2206 y(time.)-41 2252 y(The)c(second)f(is)g Fp(parallelization)d(over)o +(head)p Fn(.)15 b(This)9 b(is)g(the)g(over)o(-)-91 2297 +y(head)g(of)f(incorporating)e(the)j(parallel)f(algorithm,)g(which)g +(includes)-91 2343 y(the)i(handling)g(of)g(communication,)h(and)g +(maintaining)e(structures)-91 2389 y(to)g(allow)h(for)g(allocation)f +(of)h(work.)-41 2434 y(The)i(third)d(is)i Fp(sear)n(ch)i(over)o(head)p +Fn(.)18 b(Search)12 b(trees)g(are)g(really)f(di-)-91 +2480 y(rected)k(graphs.)26 b(W)m(ork)13 b(performed)h(on)g(one)h +(processor)f(may)h(be)-91 2526 y(useful)c(to)h(the)g(computations)f(of) +g(another)h(processor)n(.)19 b(If)12 b(this)f(in-)-91 +2571 y(formation)c(is)h(not)g(available,)h(unnecessary)h(search)f(may)g +(be)g(done.)-41 2617 y(These)j(overheads)g(are)h(not)d(independent)h +(of)g(each)i(other)n(.)k(For)-91 2662 y(example,)24 b(increased)e +(communication)e(can)i(help)e(reduce)h(the)987 694 y(search)13 +b(overhead.)20 b(Reducing)11 b(the)h(number)f(of)h(synchronization)987 +740 y(points)i(can)j(increase)g(the)e(search)i(overhead.)31 +b(In)16 b(practice,)i(the)987 786 y(right)7 b(balance)i(between)g +(these)g(sources)h(of)e(program)g(inef)o(\256ciency)987 +831 y(is)13 b(dif)o(\256cult)f(to)g(\256nd,)i(and)f(one)g(usually)f +(performs)h(many)h(experi-)987 877 y(ments)c(to)g(\256nd)g(the)g(right) +f(trade-of)o(fs)h(to)f(maximize)i(performance.)1037 924 +y(Many)g(parallel)g Fo(\013\014)j Fn(algorithms)c(have)i(appeared)g(in) +f(the)g(liter)o(-)987 970 y(ature)g(\(a)g(more)g(complete)f(list)g(is)g +(available)h(elsewhere)g([1]\).)k(The)987 1015 y(PV)l(-Split)10 +b(algorithm)g(recognized)h(that)g(some)h(nodes)f(exist)g(in)g(the)987 +1061 y(search)h(tree)f(where,)h(having)e(searched)j(the)e(\256rst)f +(branch)h(sequen-)987 1107 y(tially)m(,)c(the)g(remaining)g(branches)h +(can)g(be)f(searched)i(in)e(parallel)g([5)o(].)987 1152 +y(Initiating)h(parallelism)i(along)h(the)f(best)h(line)f(of)h(play)m(,) +g(the)f Fp(princi-)987 1198 y(pal)i(variation)p Fn(,)h(was)g(ef)o +(fective)h(for)f(a)g(small)g(number)g(of)g(proces-)987 +1244 y(sors,)g(although)d(variations)h(on)h(this)f(scheme)j(seemed)f +(limited)e(to)987 1289 y(speedups)f(of)g(less)h(than)f(8)g([7].)1037 +1336 y(The)15 b(idea)f(can)h(be)f(generalized)h(to)e(other)h(nodes)g +(in)g(the)g(tree.)987 1382 y(At)f(nodes)g(where)h(the)g(\256rst)f +(branch)h(has)f(been)h(searched)h(and)f(no)987 1427 y(cut-of)o(f)h +(occurred,)i(the)e(rest)g(can)h(likely)e(be)i(searched)h(in)d(paral-) +987 1473 y(lel.)32 b(It)16 b(is)g(a)g(trade-of)o(f)g(\261)g(increased)i +(parallelism)e(versus)g(addi-)987 1519 y(tional)h(search)i(overhead,)i +(since)e(one)f(of)g(these)g(parallel)g(tasks)987 1564 +y(could)10 b(cause)h(a)g(cut-of)o(f.)j(This)c(idea)h(has)g(been)g +(tried)f(by)g(a)g(number)987 1610 y(of)h(researchers,)j(such)d(as)h +(Jamboree)g(search)h([4)o(])e(and)h(ABDADA)987 1656 y([9].)26 +b(The)15 b(best-known)e(instance)h(of)g(this)g(type)g(of)g(algorithm)f +(is)987 1701 y(called)8 b Fp(Y)l(oung)g(Br)n(others)h(W)l(ait)e +Fn(\(YBW\))h(and)g(was)h(implemented)f(in)987 1747 y(the)k +Fo(Z)s(ug)q(z)r(w)q(ang)i Fn(chess)g(program)e([3].)21 +b(YBW)12 b(achieved)h(a)g(344-)987 1793 y(fold)c(speedup)i(using)e(a)i +(network)e(of)h(1024)f(T)o(ransputers.)1037 1839 y(This)h(class)h(of)e +(algorithms)g(cannot)h(achieve)h(a)g(linear)e(speedup)987 +1885 y(primarily)i(due)i(to)f(synchronization)f(overhead;)i(the)f +(search)i(tree)987 1931 y(may)k(have)g(thousands)f(of)g +(synchronization)f(points)h(and)g(there)987 1976 y(are)10 +b(numerous)g(occasions)g(where)g(the)g(processes)h(are)f(starved)g(for) +987 2022 y(work.)21 b(The)14 b(algorithms)d(have)j(low)e(search)i +(overhead,)g(with)e(the)987 2068 y(absolute)c(performance)i(being)e +(strongly)f(linked)h(to)g(the)g(quality)g(of)987 2113 +y(the)i(move)h(ordering)e(within)f(the)i(game-tree.)1037 +2160 y(This)f(paper)h(introduces)f(the)h(Asynchronous)f(Parallel)g +(Hierar)o(-)987 2206 y(chical)g(Iterative)g(Deepening)g(\(APHID\))g +(game-tree)h(search)g(algo-)987 2252 y(rithm.)26 b(The)15 +b(algorithm)f(represents)h(a)g(departure)f(from)h(the)f(ap-)987 +2297 y(proaches)j(used)g(in)g(practice.)34 b(In)16 b(contrast)h(to)f +(other)g(schemes,)987 2343 y(APHID)e(de\256nes)g(a)g(frontier)f(\(a)h +(\256xed)f(number)h(of)g(moves)g(away)987 2389 y(from)e(the)g(root)f +(of)g(the)h(search)i(tree\),)f(and)f(all)f(nodes)h(at)g(the)g(fron-)987 +2434 y(tier)c(are)i(done)f(in)f(parallel.)14 b(Each)c(worker)f(process) +g(is)g(assigned)g(an)987 2480 y(equal)h(number)f(of)g(frontier)f(nodes) +i(to)f(search.)15 b(The)10 b(workers)g(con-)987 2526 +y(tinually)d(search)j(these)g(nodes)f(deeper)h(and)f(deeper)n(,)i +(never)e(having)987 2571 y(to)h(synchronize)g(with)f(a)h(controlling)e +(master)j(process.)k(The)c(mas-)987 2617 y(ter)c(process)h(repeatedly)f +(searches)i(to)e(the)g(frontier)f(to)g(get)i(the)f(latest)987 +2663 y(search)12 b(results.)i(In)d(this)e(way)m(,)j(there)f(is)f(ef)o +(fectively)h(no)f(idle)g(time;)p eop +%%Page: 2 2 +2 1 bop -91 42 a Fn(search)14 b(inef)o(\256ciencies)g(are)f(primarily)f +(due)h(to)g(search)h(overhead.)-91 87 y(APHID')n(s)c(performance)h +(does)g(not)e(rely)h(on)g(the)h(implementation)-91 133 +y(of)h(a)i(distributed)c(transposition)h(table,)j(which)e(makes)i(the)f +(algo-)-91 178 y(rithm)g(suitable)g(for)g(loosely-coupled)f +(architectures)i(\(such)f(as)i(a)-91 224 y(network)c(of)h +(workstations\),)f(as)i(well)f(as)g(tightly-coupled)d(archi-)-91 +270 y(tectures.)-41 323 y(Unlike)f(some)i(parallel)f +Fo(\013\014)j Fn(algorithms,)d(APHID)g(is)h(designed)-91 +369 y(to)e(\256t)g(into)f(a)i(sequential)e Fo(\013\014)k +Fn(structure.)i(APHID)8 b(has)h(been)g(imple-)-91 415 +y(mented)k(as)h(a)g(game-independent)f(library)g(of)g(routines.)22 +b(These,)-91 460 y(combined)10 b(with)f(application-dependent)f +(routines)h(that)h(the)g(user)-91 506 y(supplies,)k(allow)f(a)h +(sequential)f Fo(\013\014)j Fn(program)d(to)g(be)h(easily)f(con-)-91 +551 y(verted)7 b(to)f(a)i(parallel)f(program.)13 b(Although)5 +b(most)i(parallel)f Fo(\013\014)k Fn(pro-)-91 597 y(grams)d(take)g +(months)g(to)f(develop,)h(the)g(game-independent)g(library)-91 +643 y(allows)14 b(users)h(to)f(integrate)g(parallelism)g(into)g(their)g +(application)-91 688 y(with)9 b(only)g(a)i(few)g(hours)e(of)h(work.)-91 +807 y Fq(2.)j(The)f(APHID)h(Algorithm)-41 913 y Fn(Y)l(oung)g(Brothers) +h(W)m(ait)g(and)g(other)g(similar)g(algorithms)g(suf-)-91 +959 y(fer)f(from)h(three)f(serious)h(problems.)23 b(First,)14 +b(the)f(numerous)h(syn-)-91 1004 y(chronization)8 b(points)h(and)h +(occasions)g(where)g(there)g(is)g(little)e(or)i(no)-91 +1050 y(work)e(to)h(be)g(done)g(in)f(parallel)h(result)f(in)h(idle)f +(time.)14 b(This)8 b(suggests)-91 1096 y(that)h(a)h(new)g(algorithm)e +(must)h(strive)g(to)g(reduce)h(or)g(eliminate)f(syn-)-91 +1141 y(chronization)i(and)h(small)h(work)e(lists.)20 +b(Second,)14 b(the)e(chaotic)g(na-)-91 1187 y(ture)h(of)f(a)i +(work-stealing)d(scheduler)i(requires)g(algorithms)f(such)-91 +1233 y(as)i(YBW)g(and)g(Jamboree)h(to)e(use)h(a)g(shared)g +(transposition)d(table)-91 1278 y(to)c(achieve)h(good)e(move)i +(ordering)e(and)h(reasonable)h(performance.)-91 1324 +y(ABDADA)j(requires)g(a)h(shared)g(transposition)d(table)i(to)g +(function)-91 1370 y(correctly)m(.)33 b(Third,)17 b(the)g(program)f +(may)h(initiate)e(parallelism)h(at)-91 1415 y(nodes)8 +b(which)f(are)i(better)e(done)h(sequentially)m(.)k(For)c(example,)h +(hav-)-91 1461 y(ing)d(searched)i(the)f(\256rst)g(branch)g(at)g(a)g +(node)g(and)g(not)f(achieved)i(a)g(cut-)-91 1507 y(of)o(f,)g(Y)l(oung)f +(Brothers)f(W)m(ait)i(\(in)f(its)g(simplest)g(form\))g(permits)g(all)h +(of)-91 1552 y(the)g(remaining)g(branches)h(to)f(be)h(searched)g(in)f +(parallel.)13 b(However)n(,)-91 1598 y(if)d(the)g(second)h(branch,)h +(for)e(example,)i(causes)g(a)f(cut-of)o(f,)f(then)h(all)-91 +1644 y(the)c(parallel)g(work)g(has)h(been)g(wasted.)13 +b(This)8 b(suggests)f(parallelism)-91 1689 y(should)i(only)h(be)h +(initiated)e(at)i(nodes)g(where)g(there)g(is)f(a)i(very)e(high)-91 +1735 y(probability)d(that)j(all)g(branches)h(must)f(be)g(considered.) +-41 1788 y(This)g(section)h(introduces)f(the)h(Asynchronous)f(Parallel) +g(Hier)o(-)-91 1834 y(archical)h(Iterative)g(Deepening)g(\(APHID\))f +(game-tree)i(searching)-91 1880 y(algorithm.)k(APHID)11 +b(has)h(been)g(designed)f(to)g(address)h(the)f(above)-91 +1925 y(three)f(issues.)k(The)c(algorithm)f(is)g(asynchronous)h(in)f +(nature;)g(it)g(re-)-91 1971 y(moves)15 b(all)f(synchronization)f +(points)g(from)i(the)f Fo(\013\014)j Fn(search)f(and)-91 +2017 y(from)11 b(iterative)g(deepening.)18 b(Also,)12 +b(parallelism)g(is)f(only)g(applied)-91 2062 y(at)e(nodes)g(that)f +(have)i(a)f(high)f(probability)e(of)j(needing)f(parallelism.)-91 +2108 y(The)g(top)f Fp(plies)128 2093 y Fm(1)154 2108 +y Fn(of)h(a)g(game-tree)h(near)f(the)f(root)g(vary)g(infrequently)-91 +2154 y(between)13 b(steps)h(of)f(iterative)f(deepening.)23 +b(This)13 b(relative)g(invari-)-91 2199 y(ance)f(of)f(the)g(top)f +(portion)g(of)h(the)g(game-tree)h(is)f(exploited)f(by)g(the)-91 +2245 y(APHID)g(algorithm.)-41 2298 y(In)k(its)h(simplest)g(form,)h +(APHID)f(can)h(be)g(viewed)f(as)h(a)f(mas-)-91 2344 y(ter/slave)8 +b(program)g(although,)g(as)h(discussed)g(later)n(,)g(it)f(can)h(be)f +(gen-)-91 2390 y(eralized)19 b(to)e(a)i(hierarchical)f(processor)h +(tree.)38 b(For)18 b(a)h(depth)f Fo(d)-91 2435 y Fn(search,)9 +b(the)f(master)g(is)g(responsible)f(for)g(the)g(top)g +Fo(d)640 2420 y Fl(0)659 2435 y Fn(ply)g(of)g(the)h(tree,)-91 +2481 y(and)i(the)g(remaining)g Fo(d)e Fk(\000)h Fo(d)312 +2466 y Fl(0)334 2481 y Fn(ply)g(are)i(searched)g(in)f(parallel)g(by)f +(the)-91 2527 y(slaves.)p -91 2585 394 2 v -49 2611 a +Fj(1)-31 2623 y Fi(The)e(ply)h(of)f(a)h(node)f(is)h(its)g(depth)f +(within)h(the)f(game-tree,)g(starting)h(with)g(ply)g(0)-91 +2662 y(at)g(the)g(root)g(of)g(the)g(game-tree.)987 42 +y Fh(2.1.)k(Operation)g(of)f(the)h(Master)g(in)g(APHID)1037 +123 y Fn(The)f(master)h(is)f(responsible)f(for)g(searching)h(the)g(top) +f Fo(d)1850 107 y Fl(0)1873 123 y Fn(ply)g(of)987 168 +y(the)15 b(tree.)29 b(It)15 b(repeatedly)g(traverses)h(this)e(tree)i +(until)d(the)i(correct)987 214 y(minimax)10 b(value)h(has)g(been)g +(determined.)16 b(The)11 b(master)h(is)e(execut-)987 +259 y(ing)f(a)h(normal)g Fo(\013\014)i Fn(search,)f(with)e(the)g +(exception)h(that)f(APHID)g(en-)987 305 y(forces)15 b(an)g +(arti\256cial)f(search)i(horizon)e(at)g Fo(d)1639 290 +y Fl(0)1665 305 y Fn(ply)g(from)h(the)f(root.)987 351 +y(Each)j(leaf)g(node)f(in)f(the)i(master)r(')n(s)f Fo(d)1556 +336 y Fl(0)1583 351 y Fn(ply)g(game-tree)h(is)f(being)987 +396 y(asynchronously)c(searched)i(by)f(the)g(slaves.)23 +b(Before)13 b(describing)987 442 y(the)d(master)r(')n(s)g(stopping)e +(condition,)g(we)i(must)g(\256rst)g(describe)g(how)987 +488 y(the)g(master)h(searches)h(the)e Fo(d)1403 473 y +Fl(0)1425 488 y Fn(ply)f(tree.)1037 534 y(When)f(the)h(master)g +(reaches)h(a)f(leaf)g(of)f(the)g Fo(d)1678 519 y Fl(0)1698 +534 y Fn(ply)g(tree,)h(it)f(uses)h(a)987 580 y(reliable)h(or)f +(approximate)h(value)g(for)f(the)h(leaf,)h(depending)e(on)h(the)987 +626 y(information)f(available.)15 b(If)c(a)g Fo(d)e Fk(\000)h +Fo(d)1532 610 y Fl(0)1554 626 y Fn(ply)g(search)i(result)e(is)h(avail-) +987 671 y(able)e(from)f(the)h(slave,)h(that)e(will)f(be)i(used.)14 +b(However)n(,)c(if)e(the)g Fo(d)d Fk(\000)g Fo(d)1960 +656 y Fl(0)987 717 y Fn(ply)k(result)g(is)h(not)f(available,)h(then)g +(the)f(algorithm)g(uses)h(the)g(deep-)987 762 y(est)e(search)i(result)d +(that)h(has)g(been)h(returned)e(by)h(the)g(slave)h(to)e(gener)o(-)987 +808 y(ate)h(a)g(guessed)f(minimax)g(value.)14 b(Any)6 +b(node)i(where)f(we)h(are)g(forced)987 854 y(to)i(guess)g(are)h(marked) +g(as)g Fp(uncertain)p Fn(.)1037 900 y(As)g(values)f(get)h(backed)g(up)g +(the)f(tree,)i(the)e(master)i(maintains)e(a)987 946 y(count)i(of)g(how) +g(many)g(uncertain)g(nodes)g(have)h(been)g(visited)e(in)h(a)987 +992 y(pass)f(over)g(the)f(tree.)16 b(As)11 b(long)e(as)i(the)g(score)g +(at)g(any)g(of)f(the)h(leaves)987 1037 y(is)g(uncertain,)h(the)f +(master)h(must)f(do)g(another)g(pass)h(over)f(the)h(tree.)987 +1083 y(Once)c(the)f(master)i(has)e(a)h(reliable)f(value)h(for)f(all)g +(the)g(leaves)h(in)f(its)g Fo(d)1960 1068 y Fl(0)987 +1129 y Fn(ply)f(tree,)j(the)e(search)h(of)f(the)g Fo(d)g +Fn(ply)f(tree)i(is)f(complete.)13 b(The)8 b(control-)987 +1174 y(ling)g(program)h(would)f(then)g(proceed)i(to)e(the)h(next)g +(iteration)e(by)i(in-)987 1220 y(crementing)g Fo(d)g +Fn(and)h(asking)f(the)g(master)h(to)f(search)h(the)f(tree)h(again.)1037 +1266 y(The)15 b(slaves)g(are)g(responsible)f(for)f(setting)h(their)f +(own)h(search)987 1312 y(windows,)j(based)g(on)g(information)d(from)i +(the)h(master)n(.)33 b(Some-)987 1358 y(times,)9 b(the)g(information)e +(returned)h(by)g(the)h(slave)g(may)g(not)f(be)h(use-)987 +1403 y(ful)j(to)g(the)h(master)n(.)22 b(For)13 b(example,)i(a)e(slave)g +(can)h(tell)e(the)h(master)987 1449 y(that)e(the)h(score)h(of)f(a)h +(given)e(node)h(is)g(less)h(than)f(30,)g(but)g(the)g(mas-)987 +1495 y(ter)e(may)g(want)f(to)h(know)f(if)g(the)g(score)i(is)e(in)h +(between)g(-5)f(and)h(5.)k(In)987 1540 y(this)9 b(case,)j(a)f(\252bad)f +(bound\272)f(search)j(is)d(generated,)i(and)f(the)g(search)987 +1586 y(window)e(parameters,)k Fo(\013)d Fn(and)h Fo(\014)r +Fn(,)h(must)e(be)h(communicated)h(to)e(the)987 1631 y(slave)j +(processor)n(.)18 b(Any)11 b(nodes)h(where)g(we)g(are)h(waiting)d(for)h +(\252bad)987 1677 y(bound\272)d(information)g(are)h(considered)g(as)h +(uncertain)f(by)g(the)g(mas-)987 1723 y(ter)n(,)k(even)g(though)e(we)i +(have)g(a)g(score)g(bound)e(for)h(the)g Fo(d)g Fk(\000)g +Fo(d)1894 1708 y Fl(0)1918 1723 y Fn(ply)987 1768 y(search.)24 +b(Eventually)m(,)14 b(the)f(slave)h(will)e(return)g(updated)h(informa-) +987 1814 y(tion)7 b(that)i(is)f(consistent)g(with)g(both)g(the)g +(original)f(information)g(and)987 1860 y(the)j(search)h(window)f +(requested.)987 1941 y Fh(2.2.)i(The)g(APHID)f(T)l(able)1037 +2022 y Fn(If)h(a)i(node)e(is)h(visited)e(by)i(the)f(master)i(for)e(the) +h(\256rst)f(time,)i(it)e(is)987 2067 y(statically)d(allocated)h(to)f(a) +i(slave)f(processor)n(.)k(This)c(information)e(is)987 +2113 y(recorded)13 b(in)g(a)h(table,)g(the)f Fp(APHID)h(table)p +Fn(,)f(that)f(is)h(shared)h(by)f(all)987 2159 y(processors.)j(Figure)10 +b(1)h(shows)f(an)i(example)f(of)g(how)f(the)g(APHID)987 +2204 y(table)g(would)f(be)i(or)o(ganized)f(at)g(a)h(given)f(point)f(in) +g(time.)1037 2251 y(The)f(APHID)g(table)f(is)g(partitioned)f(into)g +(two)h(parts:)12 b(one)c(which)987 2296 y(only)j(the)g(master)i(can)g +(write)e(to,)h(and)g(one)g(which)f(only)g(the)h(slave)987 +2342 y(that)e(has)g(been)h(assigned)g(that)e(piece)i(of)f(work)g(can)h +(write)f(to.)k(Any)987 2388 y(attempt)e(to)f(write)h(into)e(the)i +(table)g(generates)h(a)g(message)h(that)d(in-)987 2433 +y(forms)e(the)f(slave)h(or)g(the)f(master)i(process)f(of)f(the)h +(update)g(to)f(the)g(in-)987 2479 y(formation.)k(The)d(master)h(and)e +(slave)h(only)e(read)i(their)f(local)g(copies)987 2525 +y(of)k(the)h(information;)e(there)i(are)g(no)f(explicit)f(messages)k +(sent)d(be-)987 2570 y(tween)e(the)h(master)g(and)f(the)g(slave)h +(asking)e(for)h(information.)1037 2617 y(The)18 b(master)r(')n(s)f +(half)g(of)g(the)g(table)g(is)g(illustrated)e(above)j(the)987 +2662 y(dashed)12 b(line)e(in)h(Figure)g(1.)18 b(For)11 +b(each)h(leaf)g(that)f(has)h(been)g(visited)p eop +%%Page: 3 3 +3 2 bop -85 0 a + 15345564 14208860 8420065 17234821 28417720 35653713 startTexFig + -85 0 a +%%BeginDocument: draw2.ps + +/arrowHeight 10 def +/arrowWidth 5 def + +/IdrawDict 51 dict def +IdrawDict begin + +/reencodeISO { +dup dup findfont dup length dict begin +{ 1 index /FID ne { def }{ pop pop } ifelse } forall +/Encoding ISOLatin1Encoding def +currentdict end definefont +} def + +/ISOLatin1Encoding [ +/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef +/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef +/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef +/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef +/space/exclam/quotedbl/numbersign/dollar/percent/ampersand/quoteright +/parenleft/parenright/asterisk/plus/comma/minus/period/slash +/zero/one/two/three/four/five/six/seven/eight/nine/colon/semicolon +/less/equal/greater/question/at/A/B/C/D/E/F/G/H/I/J/K/L/M/N +/O/P/Q/R/S/T/U/V/W/X/Y/Z/bracketleft/backslash/bracketright +/asciicircum/underscore/quoteleft/a/b/c/d/e/f/g/h/i/j/k/l/m +/n/o/p/q/r/s/t/u/v/w/x/y/z/braceleft/bar/braceright/asciitilde +/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef +/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef +/.notdef/dotlessi/grave/acute/circumflex/tilde/macron/breve +/dotaccent/dieresis/.notdef/ring/cedilla/.notdef/hungarumlaut +/ogonek/caron/space/exclamdown/cent/sterling/currency/yen/brokenbar +/section/dieresis/copyright/ordfeminine/guillemotleft/logicalnot +/hyphen/registered/macron/degree/plusminus/twosuperior/threesuperior +/acute/mu/paragraph/periodcentered/cedilla/onesuperior/ordmasculine +/guillemotright/onequarter/onehalf/threequarters/questiondown +/Agrave/Aacute/Acircumflex/Atilde/Adieresis/Aring/AE/Ccedilla +/Egrave/Eacute/Ecircumflex/Edieresis/Igrave/Iacute/Icircumflex +/Idieresis/Eth/Ntilde/Ograve/Oacute/Ocircumflex/Otilde/Odieresis +/multiply/Oslash/Ugrave/Uacute/Ucircumflex/Udieresis/Yacute +/Thorn/germandbls/agrave/aacute/acircumflex/atilde/adieresis +/aring/ae/ccedilla/egrave/eacute/ecircumflex/edieresis/igrave +/iacute/icircumflex/idieresis/eth/ntilde/ograve/oacute/ocircumflex +/otilde/odieresis/divide/oslash/ugrave/uacute/ucircumflex/udieresis +/yacute/thorn/ydieresis +] def +/Helvetica reencodeISO def + +/none null def +/numGraphicParameters 17 def +/stringLimit 65535 def + +/Begin { +save +numGraphicParameters dict begin +} def + +/End { +end +restore +} def + +/SetB { +dup type /nulltype eq { +pop +false /brushRightArrow idef +false /brushLeftArrow idef +true /brushNone idef +} { +/brushDashOffset idef +/brushDashArray idef +0 ne /brushRightArrow idef +0 ne /brushLeftArrow idef +/brushWidth idef +false /brushNone idef +} ifelse +} def + +/SetCFg { +/fgblue idef +/fggreen idef +/fgred idef +} def + +/SetCBg { +/bgblue idef +/bggreen idef +/bgred idef +} def + +/SetF { +/printSize idef +/printFont idef +} def + +/SetP { +dup type /nulltype eq { +pop true /patternNone idef +} { +dup -1 eq { +/patternGrayLevel idef +/patternString idef +} { +/patternGrayLevel idef +} ifelse +false /patternNone idef +} ifelse +} def + +/BSpl { +0 begin +storexyn +newpath +n 1 gt { +0 0 0 0 0 0 1 1 true subspline +n 2 gt { +0 0 0 0 1 1 2 2 false subspline +1 1 n 3 sub { +/i exch def +i 1 sub dup i dup i 1 add dup i 2 add dup false subspline +} for +n 3 sub dup n 2 sub dup n 1 sub dup 2 copy false subspline +} if +n 2 sub dup n 1 sub dup 2 copy 2 copy false subspline +patternNone not brushLeftArrow not brushRightArrow not and and { ifill } if +brushNone not { istroke } if +0 0 1 1 leftarrow +n 2 sub dup n 1 sub dup rightarrow +} if +end +} dup 0 4 dict put def + +/Circ { +newpath +0 360 arc +patternNone not { ifill } if +brushNone not { istroke } if +} def + +/CBSpl { +0 begin +dup 2 gt { +storexyn +newpath +n 1 sub dup 0 0 1 1 2 2 true subspline +1 1 n 3 sub { +/i exch def +i 1 sub dup i dup i 1 add dup i 2 add dup false subspline +} for +n 3 sub dup n 2 sub dup n 1 sub dup 0 0 false subspline +n 2 sub dup n 1 sub dup 0 0 1 1 false subspline +patternNone not { ifill } if +brushNone not { istroke } if +} { +Poly +} ifelse +end +} dup 0 4 dict put def + +/Elli { +0 begin +newpath +4 2 roll +translate +scale +0 0 1 0 360 arc +patternNone not { ifill } if +brushNone not { istroke } if +end +} dup 0 1 dict put def + +/Line { +0 begin +2 storexyn +newpath +x 0 get y 0 get moveto +x 1 get y 1 get lineto +brushNone not { istroke } if +0 0 1 1 leftarrow +0 0 1 1 rightarrow +end +} dup 0 4 dict put def + +/MLine { +0 begin +storexyn +newpath +n 1 gt { +x 0 get y 0 get moveto +1 1 n 1 sub { +/i exch def +x i get y i get lineto +} for +patternNone not brushLeftArrow not brushRightArrow not and and { ifill } if +brushNone not { istroke } if +0 0 1 1 leftarrow +n 2 sub dup n 1 sub dup rightarrow +} if +end +} dup 0 4 dict put def + +/Poly { +3 1 roll +newpath +moveto +-1 add +{ lineto } repeat +closepath +patternNone not { ifill } if +brushNone not { istroke } if +} def + +/Rect { +0 begin +/t exch def +/r exch def +/b exch def +/l exch def +newpath +l b moveto +l t lineto +r t lineto +r b lineto +closepath +patternNone not { ifill } if +brushNone not { istroke } if +end +} dup 0 4 dict put def + +/Text { +ishow +} def + +/idef { +dup where { pop pop pop } { exch def } ifelse +} def + +/ifill { +0 begin +gsave +patternGrayLevel -1 ne { +fgred bgred fgred sub patternGrayLevel mul add +fggreen bggreen fggreen sub patternGrayLevel mul add +fgblue bgblue fgblue sub patternGrayLevel mul add setrgbcolor +eofill +} { +eoclip +originalCTM setmatrix +pathbbox /t exch def /r exch def /b exch def /l exch def +/w r l sub ceiling cvi def +/h t b sub ceiling cvi def +/imageByteWidth w 8 div ceiling cvi def +/imageHeight h def +bgred bggreen bgblue setrgbcolor +eofill +fgred fggreen fgblue setrgbcolor +w 0 gt h 0 gt and { +l b translate w h scale +w h true [w 0 0 h neg 0 h] { patternproc } imagemask +} if +} ifelse +grestore +end +} dup 0 8 dict put def + +/istroke { +gsave +brushDashOffset -1 eq { +[] 0 setdash +1 setgray +} { +brushDashArray brushDashOffset setdash +fgred fggreen fgblue setrgbcolor +} ifelse +brushWidth setlinewidth +originalCTM setmatrix +stroke +grestore +} def + +/ishow { +0 begin +gsave +fgred fggreen fgblue setrgbcolor +/fontDict printFont printSize scalefont dup setfont def +/descender fontDict begin 0 [FontBBox] 1 get FontMatrix end +transform exch pop def +/vertoffset 1 printSize sub descender sub def { +0 vertoffset moveto show +/vertoffset vertoffset printSize sub def +} forall +grestore +end +} dup 0 3 dict put def +/patternproc { +0 begin +/patternByteLength patternString length def +/patternHeight patternByteLength 8 mul sqrt cvi def +/patternWidth patternHeight def +/patternByteWidth patternWidth 8 idiv def +/imageByteMaxLength imageByteWidth imageHeight mul +stringLimit patternByteWidth sub min def +/imageMaxHeight imageByteMaxLength imageByteWidth idiv patternHeight idiv +patternHeight mul patternHeight max def +/imageHeight imageHeight imageMaxHeight sub store +/imageString imageByteWidth imageMaxHeight mul patternByteWidth add string def +0 1 imageMaxHeight 1 sub { +/y exch def +/patternRow y patternByteWidth mul patternByteLength mod def +/patternRowString patternString patternRow patternByteWidth getinterval def +/imageRow y imageByteWidth mul def +0 patternByteWidth imageByteWidth 1 sub { +/x exch def +imageString imageRow x add patternRowString putinterval +} for +} for +imageString +end +} dup 0 12 dict put def + +/min { +dup 3 2 roll dup 4 3 roll lt { exch } if pop +} def + +/max { +dup 3 2 roll dup 4 3 roll gt { exch } if pop +} def + +/midpoint { +0 begin +/y1 exch def +/x1 exch def +/y0 exch def +/x0 exch def +x0 x1 add 2 div +y0 y1 add 2 div +end +} dup 0 4 dict put def + +/thirdpoint { +0 begin +/y1 exch def +/x1 exch def +/y0 exch def +/x0 exch def +x0 2 mul x1 add 3 div +y0 2 mul y1 add 3 div +end +} dup 0 4 dict put def + +/subspline { +0 begin +/movetoNeeded exch def +y exch get /y3 exch def +x exch get /x3 exch def +y exch get /y2 exch def +x exch get /x2 exch def +y exch get /y1 exch def +x exch get /x1 exch def +y exch get /y0 exch def +x exch get /x0 exch def +x1 y1 x2 y2 thirdpoint +/p1y exch def +/p1x exch def +x2 y2 x1 y1 thirdpoint +/p2y exch def +/p2x exch def +x1 y1 x0 y0 thirdpoint +p1x p1y midpoint +/p0y exch def +/p0x exch def +x2 y2 x3 y3 thirdpoint +p2x p2y midpoint +/p3y exch def +/p3x exch def +movetoNeeded { p0x p0y moveto } if +p1x p1y p2x p2y p3x p3y curveto +end +} dup 0 17 dict put def + +/storexyn { +/n exch def +/y n array def +/x n array def +n 1 sub -1 0 { +/i exch def +y i 3 2 roll put +x i 3 2 roll put +} for +} def + +/SSten { +fgred fggreen fgblue setrgbcolor +dup true exch 1 0 0 -1 0 6 -1 roll matrix astore +} def + +/FSten { +dup 3 -1 roll dup 4 1 roll exch +newpath +0 0 moveto +dup 0 exch lineto +exch dup 3 1 roll exch lineto +0 lineto +closepath +bgred bggreen bgblue setrgbcolor +eofill +SSten +} def + +/Rast { +exch dup 3 1 roll 1 0 0 -1 0 6 -1 roll matrix astore +} def + + +/arrowhead { +0 begin +transform originalCTM itransform +/taily exch def +/tailx exch def +transform originalCTM itransform +/tipy exch def +/tipx exch def +/dy tipy taily sub def +/dx tipx tailx sub def +/angle dx 0 ne dy 0 ne or { dy dx atan } { 90 } ifelse def +gsave +originalCTM setmatrix +tipx tipy translate +angle rotate +newpath +arrowHeight neg arrowWidth 2 div moveto +0 0 lineto +arrowHeight neg arrowWidth 2 div neg lineto +patternNone not { +originalCTM setmatrix +/padtip arrowHeight 2 exp 0.25 arrowWidth 2 exp mul add sqrt brushWidth mul +arrowWidth div def +/padtail brushWidth 2 div def +tipx tipy translate +angle rotate +padtip 0 translate +arrowHeight padtip add padtail add arrowHeight div dup scale +arrowheadpath +ifill +} if +brushNone not { +originalCTM setmatrix +tipx tipy translate +angle rotate +arrowheadpath +istroke +} if +grestore +end +} dup 0 9 dict put def + +/arrowheadpath { +newpath +arrowHeight neg arrowWidth 2 div moveto +0 0 lineto +arrowHeight neg arrowWidth 2 div neg lineto +} def + +/leftarrow { +0 begin +y exch get /taily exch def +x exch get /tailx exch def +y exch get /tipy exch def +x exch get /tipx exch def +brushLeftArrow { tipx tipy tailx taily arrowhead } if +end +} dup 0 4 dict put def + +/rightarrow { +0 begin +y exch get /tipy exch def +x exch get /tipx exch def +y exch get /taily exch def +x exch get /tailx exch def +brushRightArrow { tipx tipy tailx taily arrowhead } if +end +} dup 0 4 dict put def + + +%I Idraw 10 Grid 6 6 + + +Begin +%I b u +%I cfg u +%I cbg u +%I f u +%I p u +%I t +[ 0.799705 0 0 0.799705 0 0 ] concat +/originalCTM matrix currentmatrix def + +Begin %I Pict +%I b u +%I cfg u +%I cbg u +%I f u +%I p u +%I t +[ 1 0 0 1 5.99997 0 ] concat + +Begin %I Text +%I cfg Black +0 0 0 SetCFg +%I f -*-helvetica-medium-r-normal-*-12-*-*-*-*-*-*-* +Helvetica 12 SetF +%I t +[ 1 0 0 1 342 674 ] concat +%I +[ +(Master) +] Text +End + +Begin %I Pict +%I b u +%I cfg u +%I cbg u +%I f u +%I p u +%I t +[ 1 0 0 1 8 26 ] concat + +Begin %I Text +%I cfg Black +0 0 0 SetCFg +%I f -*-helvetica-medium-r-normal-*-12-*-*-*-*-*-*-* +Helvetica 12 SetF +%I t +[ 1 0 0 1 315 543.5 ] concat +%I +[ +(1) +] Text +End + +Begin %I Elli +%I b 65535 +1 0 0 [] 0 SetB +%I cfg Black +0 0 0 SetCFg +%I cbg White +1 1 1 SetCBg +none SetP %I p n +%I t +[ 0.5 -0 -0 0.5 278 428 ] concat +%I +80 224 12 12 Elli +End + +End %I eop + +Begin %I Pict +%I b u +%I cfg u +%I cbg u +%I f u +%I p u +%I t +[ 1 0 0 1 -4 26 ] concat + +Begin %I Elli +%I b 65535 +1 0 0 [] 0 SetB +%I cfg Black +0 0 0 SetCFg +%I cbg White +1 1 1 SetCBg +none SetP %I p n +%I t +[ 0.5 -0 -0 0.5 278 428 ] concat +%I +128 224 12 12 Elli +End + +Begin %I Text +%I cfg Black +0 0 0 SetCFg +%I f -*-helvetica-medium-r-normal-*-12-*-*-*-*-*-*-* +Helvetica 12 SetF +%I t +[ 1 0 0 1 339 543.5 ] concat +%I +[ +(2) +] Text +End + +End %I eop + +Begin %I Pict +%I b u +%I cfg u +%I cbg u +%I f u +%I p u +%I t +[ 1 0 0 1 -10 26 ] concat + +Begin %I Elli +%I b 65535 +1 0 0 [] 0 SetB +%I cfg Black +0 0 0 SetCFg +%I cbg White +1 1 1 SetCBg +none SetP %I p n +%I t +[ 0.5 -0 -0 0.5 278 428 ] concat +%I +164 224 12 12 Elli +End + +Begin %I Text +%I cfg Black +0 0 0 SetCFg +%I f -*-helvetica-medium-r-normal-*-12-*-*-*-*-*-*-* +Helvetica 12 SetF +%I t +[ 1 0 0 1 357 544 ] concat +%I +[ +(3) +] Text +End + +End %I eop + +Begin %I Pict +%I b u +%I cfg u +%I cbg u +%I f u +%I p u +%I t +[ 1 0 0 1 -16 26 ] concat + +Begin %I Elli +%I b 65535 +1 0 0 [] 0 SetB +%I cfg Black +0 0 0 SetCFg +%I cbg White +1 1 1 SetCBg +none SetP %I p n +%I t +[ 0.5 -0 -0 0.5 278 428 ] concat +%I +200 224 12 12 Elli +End + +Begin %I Text +%I cfg Black +0 0 0 SetCFg +%I f -*-helvetica-medium-r-normal-*-12-*-*-*-*-*-*-* +Helvetica 12 SetF +%I t +[ 1 0 0 1 375 544 ] concat +%I +[ +(4) +] Text +End + +End %I eop + +Begin %I Pict +%I b u +%I cfg u +%I cbg u +%I f u +%I p u +%I t +[ 1 0 0 1 -22 26 ] concat + +Begin %I Elli +%I b 65535 +1 0 0 [] 0 SetB +%I cfg Black +0 0 0 SetCFg +%I cbg White +1 1 1 SetCBg +none SetP %I p n +%I t +[ 0.5 -0 -0 0.5 278 428 ] concat +%I +236 224 12 12 Elli +End + +Begin %I Text +%I cfg Black +0 0 0 SetCFg +%I f -*-helvetica-medium-r-normal-*-12-*-*-*-*-*-*-* +Helvetica 12 SetF +%I t +[ 1 0 0 1 393 544 ] concat +%I +[ +(5) +] Text +End + +End %I eop + +Begin %I Pict +%I b u +%I cfg u +%I cbg u +%I f u +%I p u +%I t +[ 1 0 0 1 104 26 ] concat + +Begin %I Elli +%I b 65535 +1 0 0 [] 0 SetB +%I cfg Black +0 0 0 SetCFg +%I cbg White +1 1 1 SetCBg +none SetP %I p n +%I t +[ 0.5 -0 -0 0.5 278 428 ] concat +%I +32 224 12 12 Elli +End + +Begin %I Text +%I cfg Black +0 0 0 SetCFg +%I f -*-helvetica-medium-r-normal-*-12-*-*-*-*-*-*-* +Helvetica 12 SetF +%I t +[ 1 0 0 1 291 543.5 ] concat +%I +[ +(7) +] Text +End + +End %I eop + +Begin %I Pict +%I b u +%I cfg u +%I cbg u +%I f u +%I p u +%I t +[ 1 0 0 1 -28 26 ] concat + +Begin %I Elli +%I b 65535 +1 0 0 [] 0 SetB +%I cfg Black +0 0 0 SetCFg +%I cbg White +1 1 1 SetCBg +none SetP %I p n +%I t +[ 0.5 -0 -0 0.5 278 428 ] concat +%I +272 224 12 12 Elli +End + +Begin %I Text +%I cfg Black +0 0 0 SetCFg +%I f -*-helvetica-medium-r-normal-*-12-*-*-*-*-*-*-* +Helvetica 12 SetF +%I t +[ 1 0 0 1 411 544 ] concat +%I +[ +(6) +] Text +End + +End %I eop + +Begin %I Line +%I b 65535 +1 0 0 [] 0 SetB +%I cfg Black +0 0 0 SetCFg +%I cbg White +1 1 1 SetCBg +none SetP %I p n +%I t +[ 0.5 -0 -0 0.5 278 428 ] concat +%I +68 260 164 452 Line +%I 2 +End + +Begin %I Line +%I b 65535 +1 0 0 [] 0 SetB +%I cfg Black +0 0 0 SetCFg +%I cbg White +1 1 1 SetCBg +none SetP %I p n +%I t +[ 0.5 -0 -0 0.5 278 428 ] concat +%I +68 260 272 260 Line +%I 2 +End + +Begin %I Line +%I b 65535 +1 0 0 [] 0 SetB +%I cfg Black +0 0 0 SetCFg +%I cbg White +1 1 1 SetCBg +none SetP %I p n +%I t +[ 0.5 -0 -0 0.5 278 428 ] concat +%I +164 452 272 260 Line +%I 2 +End + +Begin %I Pict +%I b u +%I cfg u +%I cbg u +%I f u +%I p u +%I t +[ 1 0 0 1 -71.5 99 ] concat + +Begin %I Elli +%I b 65535 +1 0 0 [] 0 SetB +%I cfg Black +0 0 0 SetCFg +%I cbg White +1 1 1 SetCBg +none SetP %I p n +%I t +[ 0.5 -0 -0 0.5 278 428 ] concat +%I +308 224 12 12 Elli +End + +Begin %I Text +%I cfg Black +0 0 0 SetCFg +%I f -*-helvetica-medium-r-normal-*-12-*-*-*-*-*-*-* +Helvetica 12 SetF +%I t +[ 1 0 0 1 428.5 544 ] concat +%I +[ +(R) +] Text +End + +End %I eop + +Begin %I Text +%I cfg Black +0 0 0 SetCFg +%I f -*-helvetica-medium-r-normal-*-12-*-*-*-*-*-*-* +Helvetica 12 SetF +%I t +[ 1 0 0 1 284 612.5 ] concat +%I +[ +(d') +] Text +End + +Begin %I Line +%I b 65535 +1 0 0 [] 0 SetB +%I cfg Black +0 0 0 SetCFg +%I cbg White +1 1 1 SetCBg +none SetP %I p n +%I t +[ 0.5 -0 -0 0.5 226 395 ] concat +%I +148 518 100 518 Line +%I 2 +End + +Begin %I Line +%I b 65535 +1 0 0 [] 0 SetB +%I cfg Black +0 0 0 SetCFg +%I cbg White +1 1 1 SetCBg +none SetP %I p n +%I t +[ 0.5 -0 -0 0.5 226 395 ] concat +%I +148 326 100 326 Line +%I 2 +End + +Begin %I Line +%I b 65535 +1 0 1 [] 0 SetB +%I cfg Black +0 0 0 SetCFg +%I cbg White +1 1 1 SetCBg +none SetP %I p n +%I t +[ 0.5 -0 -0 0.5 226 395 ] concat +%I +124 446 124 506 Line +%I 2 +End + +Begin %I Line +%I b 65535 +1 0 1 [] 0 SetB +%I cfg Black +0 0 0 SetCFg +%I cbg White +1 1 1 SetCBg +none SetP %I p n +%I t +[ 0.5 -0 -0 0.5 226 395 ] concat +%I +124 410 124 338 Line +%I 2 +End + +End %I eop + +Begin %I Pict +%I b u +%I cfg u +%I cbg u +%I f u +%I p u +%I t +[ 1 0 0 1 12 -24 ] concat + +Begin %I Elli +%I b 65535 +1 0 0 [] 0 SetB +%I cfg Black +0 0 0 SetCFg +%I cbg White +1 1 1 SetCBg +none SetP %I p n +%I t +[ 0.5 -0 -0 0.5 278 428 ] concat +%I +128 224 12 12 Elli +End + +Begin %I Text +%I cfg Black +0 0 0 SetCFg +%I f -*-helvetica-medium-r-normal-*-12-*-*-*-*-*-*-* +Helvetica 12 SetF +%I t +[ 1 0 0 1 339 543.5 ] concat +%I +[ +(2) +] Text +End + +End %I eop + +Begin %I Pict +%I b u +%I cfg u +%I cbg u +%I f u +%I p u +%I t +[ 1 0 0 1 114 -24 ] concat + +Begin %I Elli +%I b 65535 +1 0 0 [] 0 SetB +%I cfg Black +0 0 0 SetCFg +%I cbg White +1 1 1 SetCBg +none SetP %I p n +%I t +[ 0.5 -0 -0 0.5 278 428 ] concat +%I +164 224 12 12 Elli +End + +Begin %I Text +%I cfg Black +0 0 0 SetCFg +%I f -*-helvetica-medium-r-normal-*-12-*-*-*-*-*-*-* +Helvetica 12 SetF +%I t +[ 1 0 0 1 357 544 ] concat +%I +[ +(3) +] Text +End + +End %I eop + +Begin %I Pict +%I b u +%I cfg u +%I cbg u +%I f u +%I p u +%I t +[ 1 0 0 1 -108 -24 ] concat + +Begin %I Elli +%I b 65535 +1 0 0 [] 0 SetB +%I cfg Black +0 0 0 SetCFg +%I cbg White +1 1 1 SetCBg +none SetP %I p n +%I t +[ 0.5 -0 -0 0.5 278 428 ] concat +%I +200 224 12 12 Elli +End + +Begin %I Text +%I cfg Black +0 0 0 SetCFg +%I f -*-helvetica-medium-r-normal-*-12-*-*-*-*-*-*-* +Helvetica 12 SetF +%I t +[ 1 0 0 1 375 544 ] concat +%I +[ +(4) +] Text +End + +End %I eop + +Begin %I Pict +%I b u +%I cfg u +%I cbg u +%I f u +%I p u +%I t +[ 1 0 0 1 -6.00003 -24 ] concat + +Begin %I Elli +%I b 65535 +1 0 0 [] 0 SetB +%I cfg Black +0 0 0 SetCFg +%I cbg White +1 1 1 SetCBg +none SetP %I p n +%I t +[ 0.5 -0 -0 0.5 278 428 ] concat +%I +236 224 12 12 Elli +End + +Begin %I Text +%I cfg Black +0 0 0 SetCFg +%I f -*-helvetica-medium-r-normal-*-12-*-*-*-*-*-*-* +Helvetica 12 SetF +%I t +[ 1 0 0 1 393 544 ] concat +%I +[ +(5) +] Text +End + +End %I eop + +Begin %I Pict +%I b u +%I cfg u +%I cbg u +%I f u +%I p u +%I t +[ 1 0 0 1 96 -24 ] concat + +Begin %I Elli +%I b 65535 +1 0 0 [] 0 SetB +%I cfg Black +0 0 0 SetCFg +%I cbg White +1 1 1 SetCBg +none SetP %I p n +%I t +[ 0.5 -0 -0 0.5 278 428 ] concat +%I +272 224 12 12 Elli +End + +Begin %I Text +%I cfg Black +0 0 0 SetCFg +%I f -*-helvetica-medium-r-normal-*-12-*-*-*-*-*-*-* +Helvetica 12 SetF +%I t +[ 1 0 0 1 411 544 ] concat +%I +[ +(6) +] Text +End + +End %I eop + +Begin %I Pict +%I b u +%I cfg u +%I cbg u +%I f u +%I p u +%I t +[ 1 0 0 1 -84 -24 ] concat + +Begin %I Text +%I cfg Black +0 0 0 SetCFg +%I f -*-helvetica-medium-r-normal-*-12-*-*-*-*-*-*-* +Helvetica 12 SetF +%I t +[ 1 0 0 1 315 543.5 ] concat +%I +[ +(1) +] Text +End + +Begin %I Elli +%I b 65535 +1 0 0 [] 0 SetB +%I cfg Black +0 0 0 SetCFg +%I cbg White +1 1 1 SetCBg +none SetP %I p n +%I t +[ 0.5 -0 -0 0.5 278 428 ] concat +%I +80 224 12 12 Elli +End + +End %I eop + +Begin %I Pict +%I b u +%I cfg u +%I cbg u +%I f u +%I p u +%I t +[ 1 0 0 1 12 -24 ] concat + +Begin %I Elli +%I b 65535 +1 0 0 [] 0 SetB +%I cfg Black +0 0 0 SetCFg +%I cbg White +1 1 1 SetCBg +none SetP %I p n +%I t +[ 0.5 -0 -0 0.5 278 428 ] concat +%I +32 224 12 12 Elli +End + +Begin %I Text +%I cfg Black +0 0 0 SetCFg +%I f -*-helvetica-medium-r-normal-*-12-*-*-*-*-*-*-* +Helvetica 12 SetF +%I t +[ 1 0 0 1 291 543.5 ] concat +%I +[ +(7) +] Text +End + +End %I eop + +Begin %I Line +%I b 65520 +1 0 0 [12 4] 0 SetB +%I cfg Black +0 0 0 SetCFg +%I cbg White +1 1 1 SetCBg +none SetP %I p n +%I t +[ 1.21519 0 0 0.046875 83.0438 492.703 ] concat +%I +100 241 376 241 Line +%I 1 +End + +Begin %I Text +%I cfg Black +0 0 0 SetCFg +%I f -*-helvetica-medium-r-normal-*-12-*-*-*-*-*-*-* +Helvetica 12 SetF +%I t +[ 1 0 0 1 162 515 ] concat +%I +[ +(APHID) +] Text +End + +Begin %I Text +%I cfg Black +0 0 0 SetCFg +%I f -*-helvetica-medium-r-normal-*-12-*-*-*-*-*-*-* +Helvetica 12 SetF +%I t +[ 1 0 0 1 162 503 ] concat +%I +[ +(Table) +] Text +End + +Begin %I Text +%I cfg Black +0 0 0 SetCFg +%I f -*-helvetica-medium-r-normal-*-12-*-*-*-*-*-*-* +Helvetica 12 SetF +%I t +[ 1 0 0 1 222 497 ] concat +%I +[ +(-1/4) +] Text +End + +Begin %I Text +%I cfg Black +0 0 0 SetCFg +%I f -*-helvetica-medium-r-normal-*-12-*-*-*-*-*-*-* +Helvetica 12 SetF +%I t +[ 1 0 0 1 258 497 ] concat +%I +[ +(+2/3) +] Text +End + +Begin %I Text +%I cfg Black +0 0 0 SetCFg +%I f -*-helvetica-medium-r-normal-*-12-*-*-*-*-*-*-* +Helvetica 12 SetF +%I t +[ 1 0 0 1 297.5 497 ] concat +%I +[ +(?/0) +] Text +End + +Begin %I Rect +%I b 65535 +1 0 0 [] 0 SetB +%I cfg Black +0 0 0 SetCFg +%I cbg White +1 1 1 SetCBg +none SetP %I p n +%I t +[ 0.5 0 0 0.5 148 395 ] concat +%I +136 170 352 266 Rect +End + +Begin %I Text +%I cfg Black +0 0 0 SetCFg +%I f -*-helvetica-medium-r-normal-*-12-*-*-*-*-*-*-* +Helvetica 12 SetF +%I t +[ 1 0 0 1 342 497 ] concat +%I +[ +(+5/5) +] Text +End + +Begin %I Text +%I cfg Black +0 0 0 SetCFg +%I f -*-helvetica-medium-r-normal-*-12-*-*-*-*-*-*-* +Helvetica 12 SetF +%I t +[ 1 0 0 1 498 497 ] concat +%I +[ +(+1/3) +] Text +End + +Begin %I Line +%I b 65535 +1 0 0 [] 0 SetB +%I cfg Black +0 0 0 SetCFg +%I cbg White +1 1 1 SetCBg +none SetP %I p n +%I t +[ 1 0 0 1 130 131 ] concat +%I +140 331 98 217 Line +%I 1 +End + +Begin %I Line +%I b 65535 +1 0 0 [] 0 SetB +%I cfg Black +0 0 0 SetCFg +%I cbg White +1 1 1 SetCBg +none SetP %I p n +%I t +[ 1 0 0 1 130 131 ] concat +%I +140 331 170 235 Line +%I 1 +End + +Begin %I Line +%I b 65535 +1 0 0 [] 0 SetB +%I cfg Black +0 0 0 SetCFg +%I cbg White +1 1 1 SetCBg +none SetP %I p n +%I t +[ 1 0 0 1 130 131 ] concat +%I +98 217 110 229 Line +%I 1 +End + +Begin %I Line +%I b 65535 +1 0 0 [] 0 SetB +%I cfg Black +0 0 0 SetCFg +%I cbg White +1 1 1 SetCBg +none SetP %I p n +%I t +[ 1 0 0 1 130 131 ] concat +%I +110 229 116 217 Line +%I 1 +End + +Begin %I Line +%I b 65535 +1 0 0 [] 0 SetB +%I cfg Black +0 0 0 SetCFg +%I cbg White +1 1 1 SetCBg +none SetP %I p n +%I t +[ 1 0 0 1 130 131 ] concat +%I +116 217 122 247 Line +%I 1 +End + +Begin %I Line +%I b 65535 +1 0 0 [] 0 SetB +%I cfg Black +0 0 0 SetCFg +%I cbg White +1 1 1 SetCBg +none SetP %I p n +%I t +[ 1 0 0 1 130 131 ] concat +%I +122 247 140 235 Line +%I 1 +End + +Begin %I Line +%I b 65535 +1 0 0 [] 0 SetB +%I cfg Black +0 0 0 SetCFg +%I cbg White +1 1 1 SetCBg +none SetP %I p n +%I t +[ 1 0 0 1 130 131 ] concat +%I +140 235 146 247 Line +%I 1 +End + +Begin %I Line +%I b 65535 +1 0 0 [] 0 SetB +%I cfg Black +0 0 0 SetCFg +%I cbg White +1 1 1 SetCBg +none SetP %I p n +%I t +[ 1 0 0 1 130 131 ] concat +%I +146 247 152 229 Line +%I 1 +End + +Begin %I Line +%I b 65535 +1 0 0 [] 0 SetB +%I cfg Black +0 0 0 SetCFg +%I cbg White +1 1 1 SetCBg +none SetP %I p n +%I t +[ 1 0 0 1 130 131 ] concat +%I +152 229 158 247 Line +%I 1 +End + +Begin %I Line +%I b 65535 +1 0 0 [] 0 SetB +%I cfg Black +0 0 0 SetCFg +%I cbg White +1 1 1 SetCBg +none SetP %I p n +%I t +[ 1 0 0 1 130 131 ] concat +%I +158 247 170 235 Line +%I 1 +End + +Begin %I Text +%I cfg Black +0 0 0 SetCFg +%I f -*-helvetica-medium-r-normal-*-12-*-*-*-*-*-*-* +Helvetica 12 SetF +%I t +[ 1 0 0 1 246 341 ] concat +%I +[ +(Slave 1) +] Text +End + +Begin %I Pict +%I b u +%I cfg u +%I cbg u +%I f u +%I p u +%I t +[ 1 0 0 1 12 0 ] concat + +Begin %I Line +%I b 65535 +1 0 0 [] 0 SetB +%I cfg Black +0 0 0 SetCFg +%I cbg White +1 1 1 SetCBg +none SetP %I p n +%I t +[ 0.5 0 0 0.5 234 263 ] concat +%I +288 398 204 194 Line +%I 2 +End + +Begin %I Line +%I b 65535 +1 0 0 [] 0 SetB +%I cfg Black +0 0 0 SetCFg +%I cbg White +1 1 1 SetCBg +none SetP %I p n +%I t +[ 0.5 0 0 0.5 234 263 ] concat +%I +204 194 240 218 Line +%I 2 +End + +Begin %I Line +%I b 65535 +1 0 0 [] 0 SetB +%I cfg Black +0 0 0 SetCFg +%I cbg White +1 1 1 SetCBg +none SetP %I p n +%I t +[ 0.5 0 0 0.5 234 263 ] concat +%I +240 218 252 230 Line +%I 2 +End + +Begin %I Line +%I b 65535 +1 0 0 [] 0 SetB +%I cfg Black +0 0 0 SetCFg +%I cbg White +1 1 1 SetCBg +none SetP %I p n +%I t +[ 0.5 0 0 0.5 234 263 ] concat +%I +252 230 264 218 Line +%I 2 +End + +Begin %I Line +%I b 65535 +1 0 0 [] 0 SetB +%I cfg Black +0 0 0 SetCFg +%I cbg White +1 1 1 SetCBg +none SetP %I p n +%I t +[ 0.5 0 0 0.5 234 263 ] concat +%I +264 218 276 182 Line +%I 2 +End + +Begin %I Line +%I b 65535 +1 0 0 [] 0 SetB +%I cfg Black +0 0 0 SetCFg +%I cbg White +1 1 1 SetCBg +none SetP %I p n +%I t +[ 0.5 0 0 0.5 234 263 ] concat +%I +276 182 288 206 Line +%I 2 +End + +Begin %I Line +%I b 65535 +1 0 0 [] 0 SetB +%I cfg Black +0 0 0 SetCFg +%I cbg White +1 1 1 SetCBg +none SetP %I p n +%I t +[ 0.5 0 0 0.5 234 263 ] concat +%I +288 206 300 230 Line +%I 2 +End + +Begin %I Line +%I b 65535 +1 0 0 [] 0 SetB +%I cfg Black +0 0 0 SetCFg +%I cbg White +1 1 1 SetCBg +none SetP %I p n +%I t +[ 0.5 0 0 0.5 234 263 ] concat +%I +300 230 312 206 Line +%I 2 +End + +Begin %I Line +%I b 65535 +1 0 0 [] 0 SetB +%I cfg Black +0 0 0 SetCFg +%I cbg White +1 1 1 SetCBg +none SetP %I p n +%I t +[ 0.5 0 0 0.5 234 263 ] concat +%I +312 206 324 230 Line +%I 2 +End + +Begin %I Line +%I b 65535 +1 0 0 [] 0 SetB +%I cfg Black +0 0 0 SetCFg +%I cbg White +1 1 1 SetCBg +none SetP %I p n +%I t +[ 0.5 0 0 0.5 234 263 ] concat +%I +288 398 348 230 Line +%I 2 +End + +Begin %I Line +%I b 65535 +1 0 0 [] 0 SetB +%I cfg Black +0 0 0 SetCFg +%I cbg White +1 1 1 SetCBg +none SetP %I p n +%I t +[ 0.5 0 0 0.5 234 263 ] concat +%I +324 230 348 230 Line +%I 2 +End + +Begin %I Text +%I cfg Black +0 0 0 SetCFg +%I f -*-helvetica-medium-r-normal-*-12-*-*-*-*-*-*-* +Helvetica 12 SetF +%I t +[ 1 0 0 1 354 341 ] concat +%I +[ +(Slave 2) +] Text +End + +Begin %I Pict +%I b u +%I cfg u +%I cbg u +%I f u +%I p u +%I t +[ 1 0 0 1 35.5 -97.5 ] concat + +Begin %I Elli +%I b 65535 +1 0 0 [] 0 SetB +%I cfg Black +0 0 0 SetCFg +%I cbg White +1 1 1 SetCBg +none SetP %I p n +%I t +[ 0.5 -0 -0 0.5 278 428 ] concat +%I +128 224 12 12 Elli +End + +Begin %I Text +%I cfg Black +0 0 0 SetCFg +%I f -*-helvetica-medium-r-normal-*-12-*-*-*-*-*-*-* +Helvetica 12 SetF +%I t +[ 1 0 0 1 339 543.5 ] concat +%I +[ +(2) +] Text +End + +End %I eop + +End %I eop + +Begin %I Line +%I b 65535 +1 0 0 [] 0 SetB +%I cfg Black +0 0 0 SetCFg +%I cbg White +1 1 1 SetCBg +none SetP %I p n +%I t +[ 0.5 0 0 0.5 362 230 ] concat +%I +188 248 212 284 Line +%I 2 +End + +Begin %I Line +%I b 65535 +1 0 0 [] 0 SetB +%I cfg Black +0 0 0 SetCFg +%I cbg White +1 1 1 SetCBg +none SetP %I p n +%I t +[ 0.5 0 0 0.5 362 230 ] concat +%I +212 284 236 248 Line +%I 2 +End + +Begin %I Line +%I b 65535 +1 0 0 [] 0 SetB +%I cfg Black +0 0 0 SetCFg +%I cbg White +1 1 1 SetCBg +none SetP %I p n +%I t +[ 0.5 0 0 0.5 362 230 ] concat +%I +236 248 248 296 Line +%I 2 +End + +Begin %I Line +%I b 65535 +1 0 0 [] 0 SetB +%I cfg Black +0 0 0 SetCFg +%I cbg White +1 1 1 SetCBg +none SetP %I p n +%I t +[ 0.5 0 0 0.5 362 230 ] concat +%I +248 296 272 260 Line +%I 2 +End + +Begin %I Line +%I b 65535 +1 0 0 [] 0 SetB +%I cfg Black +0 0 0 SetCFg +%I cbg White +1 1 1 SetCBg +none SetP %I p n +%I t +[ 0.5 0 0 0.5 362 230 ] concat +%I +272 260 284 296 Line +%I 2 +End + +Begin %I Line +%I b 65535 +1 0 0 [] 0 SetB +%I cfg Black +0 0 0 SetCFg +%I cbg White +1 1 1 SetCBg +none SetP %I p n +%I t +[ 0.5 0 0 0.5 362 230 ] concat +%I +284 296 308 272 Line +%I 2 +End + +Begin %I Line +%I b 65535 +1 0 0 [] 0 SetB +%I cfg Black +0 0 0 SetCFg +%I cbg White +1 1 1 SetCBg +none SetP %I p n +%I t +[ 0.5 0 0 0.5 362 230 ] concat +%I +308 272 320 296 Line +%I 2 +End + +Begin %I Line +%I b 65535 +1 0 0 [] 0 SetB +%I cfg Black +0 0 0 SetCFg +%I cbg White +1 1 1 SetCBg +none SetP %I p n +%I t +[ 0.5 0 0 0.5 362 230 ] concat +%I +260 464 320 296 Line +%I 2 +End + +Begin %I Line +%I b 65535 +1 0 0 [] 0 SetB +%I cfg Black +0 0 0 SetCFg +%I cbg White +1 1 1 SetCBg +none SetP %I p n +%I t +[ 0.5 0 0 0.5 362 230 ] concat +%I +260 464 188 248 Line +%I 2 +End + +Begin %I Text +%I cfg Black +0 0 0 SetCFg +%I f -*-helvetica-medium-r-normal-*-12-*-*-*-*-*-*-* +Helvetica 12 SetF +%I t +[ 1 0 0 1 468 341 ] concat +%I +[ +(Slave 3) +] Text +End + +Begin %I Pict +%I b u +%I cfg u +%I cbg u +%I f u +%I p u +%I t +[ 1 0 0 1 78 -97 ] concat + +Begin %I Elli +%I b 65535 +1 0 0 [] 0 SetB +%I cfg Black +0 0 0 SetCFg +%I cbg White +1 1 1 SetCBg +none SetP %I p n +%I t +[ 0.5 -0 -0 0.5 278 428 ] concat +%I +272 224 12 12 Elli +End + +Begin %I Text +%I cfg Black +0 0 0 SetCFg +%I f -*-helvetica-medium-r-normal-*-12-*-*-*-*-*-*-* +Helvetica 12 SetF +%I t +[ 1 0 0 1 411 544 ] concat +%I +[ +(6) +] Text +End + +End %I eop + +Begin %I Pict +%I b u +%I cfg u +%I cbg u +%I f u +%I p u +%I t +[ 1 0 0 1 -24.5 -99 ] concat + +Begin %I Elli +%I b 65535 +1 0 0 [] 0 SetB +%I cfg Black +0 0 0 SetCFg +%I cbg White +1 1 1 SetCBg +none SetP %I p n +%I t +[ 0.5 -0 -0 0.5 278 428 ] concat +%I +32 224 12 12 Elli +End + +Begin %I Text +%I cfg Black +0 0 0 SetCFg +%I f -*-helvetica-medium-r-normal-*-12-*-*-*-*-*-*-* +Helvetica 12 SetF +%I t +[ 1 0 0 1 291 543.5 ] concat +%I +[ +(7) +] Text +End + +End %I eop + +Begin %I Line +%I b 65535 +1 0 0 [] 0 SetB +%I cfg Black +0 0 0 SetCFg +%I cbg White +1 1 1 SetCBg +none SetP %I p n +%I t +[ 0.5 0 0 0.5 130 296 ] concat +%I +100 320 148 320 Line +%I 2 +End + +Begin %I Line +%I b 65535 +1 0 0 [] 0 SetB +%I cfg Black +0 0 0 SetCFg +%I cbg White +1 1 1 SetCBg +none SetP %I p n +%I t +[ 0.5 0 0 0.5 130 296 ] concat +%I +100 164 148 164 Line +%I 2 +End + +Begin %I Text +%I cfg Black +0 0 0 SetCFg +%I f -*-helvetica-medium-r-normal-*-12-*-*-*-*-*-*-* +Helvetica 12 SetF +%I t +[ 1 0 0 1 180.5 421.5 ] concat +%I +[ +(d-d') +] Text +End + +Begin %I Line +%I b 65535 +1 0 1 [] 0 SetB +%I cfg Black +0 0 0 SetCFg +%I cbg White +1 1 1 SetCBg +none SetP %I p n +%I t +[ 0.5 0 0 0.5 130 296 ] concat +%I +124 224 124 176 Line +%I 2 +End + +Begin %I Line +%I b 65535 +1 0 1 [] 0 SetB +%I cfg Black +0 0 0 SetCFg +%I cbg White +1 1 1 SetCBg +none SetP %I p n +%I t +[ 0.5 0 0 0.5 130 296 ] concat +%I +124 260 124 308 Line +%I 2 +End + +Begin %I Text +%I cfg Black +0 0 0 SetCFg +%I f -*-helvetica-medium-r-normal-*-12-*-*-*-*-*-*-* +Helvetica 12 SetF +%I t +[ 1 0 0 1 378 497 ] concat +%I +[ +(+4/5) +] Text +End + +Begin %I Pict +%I b u +%I cfg u +%I cbg u +%I f u +%I p u +%I t +[ 1 0 0 1 -30 -36 ] concat + +Begin %I Elli +%I b 65535 +1 0 0 [] 0 SetB +%I cfg Black +0 0 0 SetCFg +%I cbg White +1 1 1 SetCBg +none SetP %I p n +%I t +[ 0.5 -0 -0 0.5 278 362 ] concat +%I +356 380 12 12 Elli +End + +Begin %I Text +%I cfg Black +0 0 0 SetCFg +%I f -*-helvetica-medium-r-normal-*-12-*-*-*-*-*-*-* +Helvetica 12 SetF +%I t +[ 1 0 0 1 453 555.5 ] concat +%I +[ +(8) +] Text +End + +End %I eop + +Begin %I Text +%I cfg Black +0 0 0 SetCFg +%I f -*-helvetica-medium-r-normal-*-12-*-*-*-*-*-*-* +Helvetica 12 SetF +%I t +[ 1 0 0 1 414 497 ] concat +%I +[ +(-3/1) +] Text +End + +Begin %I Text +%I cfg Black +0 0 0 SetCFg +%I f -*-helvetica-medium-r-normal-*-12-*-*-*-*-*-*-* +Helvetica 12 SetF +%I t +[ 1 0 0 1 462 497 ] concat +%I +[ +(<0/4) +] Text +End + +Begin %I Rect +%I b 65535 +1 0 0 [] 0 SetB +%I cfg Black +0 0 0 SetCFg +%I cbg White +1 1 1 SetCBg +none SetP %I p n +%I t +[ 1 -0 -0 1 168 230 ] concat +%I +288 250 360 298 Rect +End + +Begin %I Rect +%I b 65535 +1 0 0 [] 0 SetB +%I cfg Black +0 0 0 SetCFg +%I cbg White +1 1 1 SetCBg +none SetP %I p n +%I t +[ 1 -0 -0 1 174 230 ] concat +%I +162 250 270 298 Rect +End + +End %I eop + +showpage + + +end +%%EndDocument + + endTexFig + -7 966 a Fg(Figure)13 b(1.)e(A)g(Snapshot)i(of)f(an)g(APHID)e(Sear)o +(ch)-91 1095 y Fn(by)d(the)g(master)n(,)j(there)d(is)h(an)f(entry)g(in) +g(the)g(APHID)h(table.)13 b(Informa-)-91 1140 y(tion)6 +b(maintained)i(on)f(the)h(leaves)g(includes)g(the)f(moves)i(required)e +(to)-91 1186 y(generate)j(the)g(leaf)g(positions)e(from)h(the)h(root)f +Ff(R)p Fn(,)h(the)g(approximate)-91 1232 y(location)e(of)i(the)g(leaf)g +(in)f(the)h(tree)g(\(which)f(is)h(used)g(by)f(the)h(slave)g(to)-91 +1277 y(prioritize)h(work\),)j(whether)f(this)f(leaf)i(was)g(touched)f +(on)f(the)i(last)-91 1323 y(pass)f(that)e(the)h(master)h(executed,)h +(and)e(the)g(number)g(of)g(the)g(slave)-91 1369 y(that)d(the)i(leaf)f +(was)h(allocated)f(to.)-41 1414 y(In)g(our)g(example,)j(we)e(can)h(see) +g(that)e(there)h(are)g(approximately)-91 1460 y(the)k(same)j(number)d +(of)h(leaves)g(which)g(have)g(been)g(allocated)g(to)-91 +1506 y(each)e(slave.)24 b(Note)14 b(that)e(there)i(is)f(an)h +(additional)d(leaf,)k(8,)g(that)d(is)-91 1551 y(not)e(represented)h(in) +g(the)g(master)r(')n(s)g Fo(d)454 1536 y Fl(0)476 1551 +y Fn(ply)f(search)i(tree.)17 b(This)11 b(leaf)-91 1597 +y(node)d(has)i(been)f(visited)f(on)g(a)h(previous)f(pass)i(of)e(the)h +Fo(d)705 1582 y Fl(0)725 1597 y Fn(ply)f(search)-91 1643 +y(tree,)14 b(but)d(was)j(not)d(touched)i(on)f(the)g(latest)h(pass.)21 +b(However)n(,)14 b(the)-91 1688 y(information)7 b(that)i(the)g(slave)h +(has)g(generated)f(may)h(be)g(needed)g(in)f(a)-91 1734 +y(later)h(pass)h(of)f(the)g(tree)g(and)h(is)f(not)f(deleted)i(by)e(the) +i(master)n(.)-41 1779 y(Leaves)h(are)g(allocated)e(to)g(the)h(slaves)g +(in)f(a)i(round-robin)c(man-)-91 1825 y(ner)n(.)30 b(Although)13 +b(there)j(may)g(be)g(better)f(methods)g(of)g(allocating)-91 +1871 y(leaves,)c(it)e(has)i(been)f(found)f(that)h(this)f(is)h(a)g +(reasonable)h(method)f(of)-91 1916 y(balancing)g(the)g(work)f(on)h(a)h +(small)f(number)h(of)f(processors.)-41 1962 y(The)f(slave')n(s)g(part)f +(of)g(the)g(table,)i(illustrated)c(by)i(the)h(area)h(below)-91 +2008 y(the)e(dashed)g(line,)g(contains)f(information)f(on)i(the)g +(result)f(of)g(search-)-91 2053 y(ing)j(the)h(position)e(to)i(various)f +(depths)h(of)g(search.)18 b(The)12 b(\252best\272)g(in-)-91 +2099 y(formation)i(and)i(the)f(ply)g(to)g(which)g(the)g(leaf)h(was)g +(examined)g(is)-91 2145 y(given)10 b(underneath)h(each)i(leaf)e(node)h +(in)e(the)h(tree.)18 b(For)11 b(leaf)h(1,)f(the)-91 2190 +y(score)i(returned)f(is)g(-1)g(with)f(a)i(search)h(depth)e(of)g(4.)20 +b(Leaf)14 b(3)e(illus-)-91 2236 y(trates)e(that)f(the)h(score)h +(information)d(returned)h(by)h(the)g(slave)g(is)g(not)-91 +2282 y(necessarily)h(an)h(exact)f(number)n(.)16 b(The)c(slaves)f +(maintain)f(an)i(upper)-91 2327 y(bound)7 b(and)i(a)g(lower)g(bound)e +(on)i(the)f(score)i(for)e(each)i(ply)e(of)g(search)-91 +2373 y(depth.)17 b(The)12 b(score)h(is)e(known)g(to)g(be)h(exact)g +(when)g(the)f(upper)g(and)-91 2419 y(lower)f(bounds)f(are)i(the)f +(same.)-91 2495 y Fh(2.3.)i(Operation)g(of)f(Sla)o(ve)g(in)g(APHID)-41 +2571 y Fn(A)e(slave)g(process)h(essentially)e(executes)i(the)f(same)h +(code)f(that)g(a)-91 2617 y(sequential)i Fo(\013\014)k +Fn(searcher)e(would.)18 b(The)13 b(process)f(simply)g(repeats)-91 +2662 y(the)i(following)d(steps)j(until)e(the)i(master)h(tells)e(it)g +(that)g(the)h(search)987 42 y(is)d(complete.)16 b(The)c(slave)g(looks)e +(in)g(its)h(portion)e(of)h(its)h(local)g(copy)987 87 +y(of)i(the)g(APHID)g(table,)g(and)h(\256nds)e(the)h(highest)f(priority) +f(node)i(to)987 133 y(search.)19 b(The)12 b(slave)g(then)f(executes)i +(the)e(search,)i(and)f(reports)f(the)987 178 y(result)d(back)i(to)e +(the)h(master)g(\(getting)e(an)j(update)e(to)g(its)h(APHID)g(ta-)987 +224 y(ble)h(in)g(return\).)1037 270 y(The)16 b(work)f(selection)h +(criterion)f(is)g(primarily)g(based)h(on)g(the)987 315 +y(depth)11 b(to)g(which)h(the)f(slave)h(has)h(already)f(searched)h(a)f +(node.)19 b(The)987 361 y(secondary)13 b(criterion,)f(if)g(the)h +(primary)f(criterion)f(is)h(the)h(same,)i(is)987 407 +y(based)10 b(on)f(the)h(location)e(of)i(the)f(node)h(within)d(the)j +(master)r(')n(s)g(game-)987 452 y(tree.)24 b(This)13 +b(secondary)h(criterion)f(is)g(necessary)i(since)f(it)f(is)g(usu-)987 +498 y(ally)d(bene\256cial)h(to)f(generate)h(the)g(results)f(in)g(a)h +(left-to-right)d(order)987 544 y(for)g(the)g(master)n(.)14 +b(Children)6 b(of)i(nodes)h(are)g(usually)e(considered)h(in)g(a)987 +589 y(best-to-worst)f(ordering,)h(implying)f(that)h(the)h(left-most)f +(branches)987 635 y(at)j(a)g(node)g(have)g(a)g(higher)f(probability)e +(of)j(being)f(useful)g(than)h(the)987 681 y(right-most)d(ones.)1037 +726 y(A)h(node)g(that)g(has)h(a)g(priority)d(of)i(zero)h(\(because)h +(it)d(is)h(no)g(longer)987 772 y(part)16 b(of)g(the)h(master)r(')n(s)f +(tree\))h(will)e(not)h(be)h(selected)g(for)f(further)987 +818 y(search.)e(For)8 b(Slave)f(2,)i(we)f(notice)f(that)g(Leaf)h(8)g +(would)e(be)i(searched)987 863 y(if)g(it)f(had)h(been)h(touched)e(by)h +(the)g(master)n(.)14 b(Leaf)9 b(8)f(is)g(ignored)f(by)h(the)987 +909 y(scheduling)j(algorithm)f(because)k(it)d(is)g(not)h(currently)e +(part)i(of)g(the)987 955 y(master)r(')n(s)e(tree.)1037 +1000 y(Before)i(a)h(search)g(can)g(be)f(executed,)i(an)f +Fo(\013\014)h Fn(search)g(window)987 1046 y(must)c(be)h(generated)g(by) +f(the)h(slave.)k(The)c(master)h(continually)c(ad-)987 +1092 y(vises)16 b(the)f(slaves)h(of)f(the)h(leaf)r(')n(s)g(location)e +(within)g(the)h(master)r(')n(s)987 1137 y(tree,)i(and)e(the)f(likely)g +(value)h(of)g(the)f(root)g(of)h(the)g(master)r(')n(s)g(tree.)987 +1183 y(Although)f(the)i(width)f(of)h(the)g(search)i(window)d(is)h +(application-)987 1229 y(dependent,)8 b(one)g(normally)f(wants)g(to)h +(center)g(the)f(window)g(around)987 1274 y(this)g(hypothesized)g(root)g +(value,)i(plus)e(or)h(minus)g(a)g(factor)g(to)g(re\257ect)987 +1320 y(the)i(uncertainty)f(in)h(it.)1037 1366 y(There)h(are)g(three)f +(types)g(of)g(update)f(messages)k(that)c(a)i(slave)f(re-)987 +1411 y(ceives)f(from)g(the)f(master:)13 b(a)c(new)g(piece)g(of)f(work)g +(has)h(been)g(added)987 1457 y(to)h(the)h(slave)g(processor)r(')n(s)g +(APHID)f(table,)i(the)e(location)g(of)h(a)g(leaf)987 +1503 y(node)c(within)f(the)h(master)r(')n(s)g(tree)h(has)g(changed)g +(\(changing)e(the)h(sec-)987 1548 y(ondary)14 b(work)g(scheduling)f +(criterion\),)i(and)g(a)g(noti\256cation)e(of)h(a)987 +1594 y(\252bad)e(bound\272)f(on)g(a)h(node.)18 b(The)12 +b(bad)g(bound)f(message)i(alerts)f(the)987 1640 y(slave)e(that)f(a)h +(position')n(s)e(search)i(information)e(is)i(not)e(suf)o(\256cient)i +(to)987 1685 y(save)j(the)f(node)g(from)f(being)h(uncertain.)19 +b(In)12 b(this)f(case,)j(the)e(slave)987 1731 y(must)d(re-search)i(the) +e(node)g(with)g(the)g Fo(\013\014)j Fn(search)e(window)e(sent)i(by)987 +1777 y(the)g(master)h(to)f(the)g(ply)f(requested.)1037 +1822 y(As)16 b(a)h(performance)g(improvement,)g(we)g(want)f(to)f(force) +i(the)987 1868 y(slave)12 b(to)e(always)i(work)e(on)h(nodes)g(for)g +(the)g(current)g(search)h(depth)987 1914 y(of)e(the)h(master)n(.)k +(When)c(all)g(the)f(slave')n(s)h(work)f(has)h(been)g(searched)987 +1959 y(to)e(the)h(required)f(depth,)g(rather)h(than)g(becoming)f(idle,) +h(it)f(starts)g(re-)987 2005 y(searching)h(its)g(nodes)g(an)h +(additional)d(ply)i(deeper)n(,)i(in)d(anticipation)987 +2051 y(of)h(the)g(next)g(iteration)e(\(depth)i Fo(d)e +Fe(+)i(1)p Fn(\).)j(When)e(this)e(is)h(happening,)987 +2096 y(the)k(slave)g(routinely)e(checks)j(the)f(communication)g +(channel)g(for)987 2142 y(messages)e(from)d(the)h(master)n(.)k(If)c +(the)f(slave)h(receives)h(a)g(new)f(piece)987 2188 y(of)f(work)f(to)g +(do)h(at)g Fo(d)d Fk(\000)g Fo(d)1344 2173 y Fl(0)1364 +2188 y Fn(ply)i(or)h(less,)h(the)f(search)h(is)f(immediately)987 +2233 y(aborted)h(and)h(control)e(is)i(returned)f(to)g(the)g(slave')n(s) +h(scheduling)f(al-)987 2279 y(gorithm.)987 2357 y Fh(2.4.)i +(Implementation)1037 2434 y Fn(The)c(APHID)f(algorithm)e(has)j(been)g +(written)e(as)i(an)f(application-)987 2480 y(independent)k(library)g +(of)h(C)h(routines.)19 b(The)13 b(library)e(was)i(written)987 +2526 y(to)g(provide)f(minimal)h(intervention)e(into)h(a)i(working)e +(version)h(of)987 2571 y(sequential)f Fo(\013\014)j Fn(or)d(its)g +(common)h(variants.)20 b(Since)13 b(the)f(library)g(is)987 +2617 y(application-independent,)f(a)j(potential)e(user)h(must)g(write)f +(a)i(few)987 2662 y(application-dependent)c(routines)h(\(such)h(as)g +(move)g(format,)h(how)p eop +%%Page: 4 4 +4 3 bop -132 0 a + 16813814 11840716 3289088 3289088 50651955 36443095 startTexFig + -132 0 a +%%BeginDocument: graph2.ps +/gnudict 40 dict def +gnudict begin +/Color false def +/Solid false def +/gnulinewidth 5.000 def +/vshift -46 def +/dl {10 mul} def +/hpt 31.5 def +/vpt 31.5 def +/M {moveto} bind def +/L {lineto} bind def +/R {rmoveto} bind def +/V {rlineto} bind def +/vpt2 vpt 2 mul def +/hpt2 hpt 2 mul def +/Lshow { currentpoint stroke M + 0 vshift R show } def +/Rshow { currentpoint stroke M + dup stringwidth pop neg vshift R show } def +/Cshow { currentpoint stroke M + dup stringwidth pop -2 div vshift R show } def +/DL { Color {setrgbcolor Solid {pop []} if 0 setdash } + {pop pop pop Solid {pop []} if 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 +/P { stroke [] 0 setdash + currentlinewidth 2 div sub M + 0 currentlinewidth V stroke } def +/D { stroke [] 0 setdash 2 copy vpt add M + hpt neg vpt neg V hpt vpt neg V + hpt vpt V hpt neg vpt V closepath stroke + P } def +/A { stroke [] 0 setdash vpt sub M 0 vpt2 V + currentpoint stroke M + hpt neg vpt neg R hpt2 0 V stroke + } def +/B { stroke [] 0 setdash 2 copy exch hpt sub exch vpt add M + 0 vpt2 neg V hpt2 0 V 0 vpt2 V + hpt2 neg 0 V closepath stroke + P } def +/C { stroke [] 0 setdash exch hpt sub exch vpt add M + hpt2 vpt2 neg V currentpoint stroke M + hpt2 neg 0 R hpt2 vpt2 V stroke } def +/T { stroke [] 0 setdash 2 copy vpt 1.12 mul add M + hpt neg vpt -1.62 mul V + hpt 2 mul 0 V + hpt neg vpt 1.62 mul V closepath stroke + P } def +/S { 2 copy A C} def +end +gnudict begin +gsave +50 50 translate +0.100 0.100 scale +0 setgray +/Helvetica findfont 140 scalefont setfont +newpath +LTa +840 351 M +6129 0 V +840 351 M +0 4618 V +LTb +840 351 M +63 0 V +6066 0 R +-63 0 V +756 351 M +(0) Rshow +840 1275 M +63 0 V +6066 0 R +-63 0 V +-6150 0 R +(2) Rshow +840 2198 M +63 0 V +6066 0 R +-63 0 V +-6150 0 R +(4) Rshow +840 3122 M +63 0 V +6066 0 R +-63 0 V +-6150 0 R +(6) Rshow +840 4045 M +63 0 V +6066 0 R +-63 0 V +-6150 0 R +(8) Rshow +840 4969 M +63 0 V +6066 0 R +-63 0 V +-6150 0 R +(10) Rshow +840 351 M +0 63 V +0 4555 R +0 -63 V +840 211 M +(0) Cshow +2372 351 M +0 63 V +0 4555 R +0 -63 V +0 -4695 R +(5) Cshow +3905 351 M +0 63 V +0 4555 R +0 -63 V +0 -4695 R +(10) Cshow +5437 351 M +0 63 V +0 4555 R +0 -63 V +0 -4695 R +(15) Cshow +6969 351 M +0 63 V +0 4555 R +0 -63 V +0 -4695 R +(20) Cshow +840 351 M +6129 0 V +0 4618 V +-6129 0 V +840 351 L +140 2660 M +currentpoint gsave translate 90 rotate 0 0 M +(Speedup) Cshow +grestore +3904 71 M +(Number of Processors) Cshow +LT0 +6486 4766 M +(Linear) Rshow +6570 4766 M +252 0 V +1146 813 M +307 462 V +306 461 V +307 462 V +306 462 V +307 462 V +306 462 V +307 461 V +306 462 V +307 462 V +LT1 +6486 4626 M +(d=7) Rshow +6570 4626 M +252 0 V +2066 610 M +1226 55 V +5743 605 L +6654 4626 D +2066 610 D +3292 665 D +5743 605 D +LT2 +6486 4486 M +(d=8) Rshow +6570 4486 M +252 0 V +2066 785 M +3292 993 L +5743 868 L +6654 4486 A +2066 785 A +3292 993 A +5743 868 A +LT3 +6486 4346 M +(d=9) Rshow +6570 4346 M +252 0 V +2066 1048 M +1226 554 V +2451 0 V +6654 4346 B +2066 1048 B +3292 1602 B +5743 1602 B +LT4 +6486 4206 M +(d=10) Rshow +6570 4206 M +252 0 V +2066 1159 M +1226 804 V +2451 600 V +6654 4206 C +2066 1159 C +3292 1963 C +5743 2563 C +LT5 +6486 4066 M +(d=11) Rshow +6570 4066 M +252 0 V +2066 1298 M +1226 909 V +5743 3681 L +6654 4066 T +2066 1298 T +3292 2207 T +5743 3681 T +LT6 +6486 3926 M +(d=12) Rshow +6570 3926 M +252 0 V +2066 1307 M +3292 2420 L +5743 4235 L +6654 3926 S +2066 1307 S +3292 2420 S +5743 4235 S +stroke +grestore +end +showpage +%%EndDocument + + endTexFig + 35 816 a Fg(Figure)13 b(2.)e(APHID)g(Speedups)i(in)e(K)o(e)o(y)o(ano) +-91 955 y Fn(to)g(make/unmake)h(moves,)h(position)d(format,)i(setting)e +(a)i(window)-91 1001 y(for)h(a)h(slave')n(s)g(search,)i +Fp(etc)p Fn(.\).)25 b(APHID')n(s)13 b(message)i(passing)f(was)-91 +1046 y(written)7 b(using)g(PVM)h([8)o(])g(to)g(allow)f(for)h(the)g +(maximum)g(portability)-91 1092 y(among)i(available)g(hardware.)-41 +1140 y(T)m(o)j(parallelize)h(a)g(sequential)f Fo(\013\014)j +Fn(program,)e(the)f(user)h(modi-)-91 1186 y(\256es)d(their)f +(sequential)g(search)h(routine)f(to)g(add)g(approximately)g(20)-91 +1231 y(lines)e(of)h(code.)14 b(This)9 b(search)h(routine)e(functions)g +(as)h(the)g(search)h(al-)-91 1277 y(gorithm)g(for)g(both)g(the)h +(master)h(and)g(the)f(slave)g(processes.)18 b(There)-91 +1323 y(are)10 b(a)f(few)h(additional)d(procedure)i(calls)h(that)e(have) +i(to)e(be)i(added)f(to)-91 1368 y(the)h(iterative)g(deepening)h +(routine)e(that)h(calls)h(the)f(search)i(routine.)-91 +1414 y(A)d(complete)h(explanation)e(of)h(the)g(current)h(APHID)f +(interface)h(can)-91 1460 y(be)g(found)g(elsewhere)h([2].)-91 +1563 y Fq(3.)i(Experiments)-41 1653 y Fn(The)e(APHID)g +(game-independent)f(library)g(was)h(inserted)g(into)-91 +1699 y(the)d(Othello)f(program,)i(Keyano,)g(which)f(has)h(frequently)e +(\256nished)-91 1744 y(in)f(the)h(top)f(\256ve)i(in)e(international)f +(computer)i(Othello)f(tournaments)-91 1790 y(over)k(the)g(last)g(three) +g(years.)-41 1838 y(T)m(o)e(test)g(the)g(algorithm,)g(Keyano)g(was)h +(programmed)g(to)e(search)-91 1884 y(with)13 b(its)g(midgame)i(search)g +(algorithm)e(to)g(a)i(depth)e(of)h Fo(d)24 b Fe(=)h(12)-91 +1929 y Fn(ply)m(,)14 b(with)e(the)h(master)h(controlling)d(the)i(top)f +Fo(d)607 1914 y Fl(0)640 1929 y Fe(=)22 b(4)13 b Fn(ply)f(of)h(the)-91 +1975 y(tree.)25 b(The)14 b(search)h(depth)e(is)g(typical)g(of)h(what)f +(the)h(parallel)f(pro-)-91 2021 y(gram)c(could)g(achieve)h(within)d +(the)i(tight)e(time)i(constraints)f(of)h(Oth-)-91 2066 +y(ello)i(competitions)f(\(typically)g(30)h(minutes)g(per)h(game\).)19 +b(Deeper)-91 2112 y(searches)d(will)d(yield)h(better)g(speedups,)j(but) +c(are)j(not)d(indicative)-91 2158 y(of)e(what)h(can)g(be)g(achieved)h +(in)e(real)h(time.)19 b(The)12 b(74)f(positions)f(ex-)-91 +2203 y(amined)j(were)g(the)f(positions)f(from)h(move)h(2)f(to)g(move)h +(38)f(in)f(the)-91 2249 y(two)f(games)j(of)e(the)g(1994)f(W)m(orld)g +(Championship)g(\256nal)h(between)-91 2295 y(David)f(Shaman)h(and)f +(Emmanuel)h(Caspard.)-41 2343 y(Parallel)j(tests)h(were)g(run)g(on)f +(4,)i(8)f(and)f(16)h(workstations)e(on)-91 2389 y(a)i(network)e(of)i +(SparcStation)e(IPC)h(computers)h(with)e(12)h(MB)h(of)-91 +2434 y(RAM,)7 b(running)f(the)i(SunOS)f(4.1.4)h(operating)e(system.)14 +b(The)8 b(com-)-91 2480 y(puters)g(are)i(linked)e(with)g(1)h(segment)h +(of)f(10)f(base)i(2)f(\(thin)f(net\))h(Eth-)-91 2526 +y(ernet.)16 b(One)11 b(workstation)e(in)h(each)i(experiment)f(was)h +(completely)-91 2571 y(occupied)7 b(by)f(the)h(master)g(process,)i +(while)d(the)h(other)f(workstations)-91 2617 y(each)16 +b(ran)f(a)g(slave)g(process.)28 b(Figure)15 b(2)f(illustrates)g(the)g +(average)-91 2662 y(speedups)d(for)f(7)h(to)f(12)h(ply)f(searches.)18 +b(The)11 b(graph)g(shows)f(that)h(as)947 0 y + 16813814 11840716 3289088 3289088 50651955 36443095 startTexFig + 947 0 a +%%BeginDocument: graph1.ps +/gnudict 40 dict def +gnudict begin +/Color false def +/Solid false def +/gnulinewidth 5.000 def +/vshift -46 def +/dl {10 mul} def +/hpt 31.5 def +/vpt 31.5 def +/M {moveto} bind def +/L {lineto} bind def +/R {rmoveto} bind def +/V {rlineto} bind def +/vpt2 vpt 2 mul def +/hpt2 hpt 2 mul def +/Lshow { currentpoint stroke M + 0 vshift R show } def +/Rshow { currentpoint stroke M + dup stringwidth pop neg vshift R show } def +/Cshow { currentpoint stroke M + dup stringwidth pop -2 div vshift R show } def +/DL { Color {setrgbcolor Solid {pop []} if 0 setdash } + {pop pop pop Solid {pop []} if 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 +/P { stroke [] 0 setdash + currentlinewidth 2 div sub M + 0 currentlinewidth V stroke } def +/D { stroke [] 0 setdash 2 copy vpt add M + hpt neg vpt neg V hpt vpt neg V + hpt vpt V hpt neg vpt V closepath stroke + P } def +/A { stroke [] 0 setdash vpt sub M 0 vpt2 V + currentpoint stroke M + hpt neg vpt neg R hpt2 0 V stroke + } def +/B { stroke [] 0 setdash 2 copy exch hpt sub exch vpt add M + 0 vpt2 neg V hpt2 0 V 0 vpt2 V + hpt2 neg 0 V closepath stroke + P } def +/C { stroke [] 0 setdash exch hpt sub exch vpt add M + hpt2 vpt2 neg V currentpoint stroke M + hpt2 neg 0 R hpt2 vpt2 V stroke } def +/T { stroke [] 0 setdash 2 copy vpt 1.12 mul add M + hpt neg vpt -1.62 mul V + hpt 2 mul 0 V + hpt neg vpt 1.62 mul V closepath stroke + P } def +/S { 2 copy A C} def +end +gnudict begin +gsave +50 50 translate +0.100 0.100 scale +0 setgray +/Helvetica findfont 140 scalefont setfont +newpath +LTa +840 351 M +6129 0 V +840 351 M +0 4618 V +LTb +840 351 M +63 0 V +6066 0 R +-63 0 V +756 351 M +(0) Rshow +840 1121 M +63 0 V +6066 0 R +-63 0 V +-6150 0 R +(20) Rshow +840 1890 M +63 0 V +6066 0 R +-63 0 V +-6150 0 R +(40) Rshow +840 2660 M +63 0 V +6066 0 R +-63 0 V +-6150 0 R +(60) Rshow +840 3430 M +63 0 V +6066 0 R +-63 0 V +-6150 0 R +(80) Rshow +840 4199 M +63 0 V +6066 0 R +-63 0 V +-6150 0 R +(100) Rshow +840 4969 M +63 0 V +6066 0 R +-63 0 V +-6150 0 R +(120) Rshow +840 351 M +0 63 V +0 4555 R +0 -63 V +840 211 M +(0) Cshow +2372 351 M +0 63 V +0 4555 R +0 -63 V +0 -4695 R +(5) Cshow +3905 351 M +0 63 V +0 4555 R +0 -63 V +0 -4695 R +(10) Cshow +5437 351 M +0 63 V +0 4555 R +0 -63 V +0 -4695 R +(15) Cshow +6969 351 M +0 63 V +0 4555 R +0 -63 V +0 -4695 R +(20) Cshow +840 351 M +6129 0 V +0 4618 V +-6129 0 V +840 351 L +140 2660 M +currentpoint gsave translate 90 rotate 0 0 M +(Percent Overhead) Cshow +grestore +3904 71 M +(Number of Processors) Cshow +LT0 +6486 4766 M +(Search Overhead) Rshow +6570 4766 M +252 0 V +2066 1556 M +1226 46 V +2451 23 V +6654 4766 D +2066 1556 D +3292 1602 D +5743 1625 D +LT1 +6486 4626 M +(Speculative Search) Rshow +6570 4626 M +252 0 V +2066 659 M +3292 978 L +2451 674 V +6654 4626 A +2066 659 A +3292 978 A +5743 1652 A +LT2 +6486 4486 M +(Parallelization Overhead) Rshow +6570 4486 M +252 0 V +2066 563 M +1226 73 V +5743 778 L +6654 4486 B +2066 563 B +3292 636 B +5743 778 B +LT3 +6486 4346 M +(Master Overhead) Rshow +6570 4346 M +252 0 V +2066 2210 M +3292 1209 L +5743 809 L +6654 4346 C +2066 2210 C +3292 1209 C +5743 809 C +LT4 +6486 4206 M +(Total Overhead) Rshow +6570 4206 M +252 0 V +2066 3938 M +3292 3376 L +2451 446 V +6654 4206 T +2066 3938 T +3292 3376 T +5743 3822 T +stroke +grestore +end +showpage +%%EndDocument + + endTexFig + 1214 816 a Fg(Figure)h(3.)g(12)f(Pl)o(y)h(Overheads)987 +956 y Fn(the)e(depth)g(of)g(the)g(search)h(increases,)h(so)e(does)h +(the)f(speedup.)1037 1005 y(The)f(overheads)g(in)f(the)h(algorithm)e +(are)i(illustrated)e(in)h(Figure)h(3)987 1051 y(as)k(percentages)f(of)g +(the)g(sequential)f(time)h(required)f(to)h(search)h(all)987 +1097 y(74)g(positions.)21 b(The)14 b Fp(total)d(over)o(head)j +Fn(represents)g(the)f(additional)987 1142 y(computing)6 +b(time)h(required)f(by)h(the)g(parallel)f(algorithm)g(to)h(achieve)987 +1188 y(the)j(same)i(result:)990 1303 y Fe(total)d(o)o(v)o(erhead)j(=) +1305 1275 y(\(parallel)d(time)17 b Fk(\003)h Fe(n\))9 +b Fk(\000)h Fe(sequen)o(tial)f(time)p 1305 1293 658 2 +v 1499 1331 a(sequen)o(tial)h(time)987 1420 y Fn(where)h +Fo(n)g Fn(is)g(the)g(number)f(of)h(processors.)16 b(The)c(total)d +(overhead)j(is)987 1466 y(also)h(a)h(sum)f(of)g(the)g(four)f +(overheads:)19 b(master)14 b(overhead,)g(paral-)987 1511 +y(lelization)6 b(overhead,)j(speculative)e(search)i(and)e(search)i +(overhead.)1037 1560 y(The)f Fp(master)h(over)o(head)f +Fn(is)g(the)g(approximate)g(penalty)f(incurred)987 1606 +y(by)k(having)g(a)h(single)f(processor)h(being)f(allocated)h +(completely)f(to)987 1651 y(the)g(handling)f(of)h(the)g(master)n(.)18 +b(This)12 b(is)f(not)g(simply)1771 1635 y Fm(1)p 1769 +1642 21 2 v 1769 1666 a Fd(n)1795 1651 y Fn(,)h(but)e(is)i(the)987 +1697 y(time)e(taken)g(away)g(by)g(the)f(master:)14 b(the)c(parallel)f +(time)h(divided)f(by)987 1743 y(the)h(sequential)g(time.)1037 +1792 y(The)j Fp(parallelization)d(over)o(head)k Fn(is)e(the)h(penalty)f +(incurred)h(by)987 1837 y(the)c(APHID)g(library)f(on)g(the)h(speed)h +(of)e(the)h(slaves.)14 b(Keyano)c(visits)987 1883 y(approximately)e +(8700)h(nodes)g(per)h(second)f(on)g(a)h(single)f(SparcSta-)987 +1929 y(tion)g(IPC.)h(Using)f(the)h(APHID)g(library)m(,)g(the)g(slaves)h +(were)g(visiting)987 1974 y(7600)c(nodes)g(per)g(second.)14 +b(The)8 b(dif)o(ference)g(between)g(this)f(rate)g(and)987 +2020 y(the)j(sequential)g(program')n(s)f(node)h(rate)h(is)f(derived)g +(partially)f(from)987 2066 y(the)14 b(overhead)g(of)g(using)f(PVM,)i +(and)f(partially)e(from)i(the)g(work-)987 2111 y(scheduling)c +(algorithm)f(on)h(each)i(slave.)k(In)10 b(the)h(authors')f(experi-)987 +2157 y(ence,)15 b(this)d(parallelization)g(overhead)i(is)e(similar)h +(to)f(implemen-)987 2203 y(tations)i(of)h(YBW)g(on)g(equivalent)f +(hardware)h(\(the)g(results)g(have)987 2248 y(not)9 b(been)h(presented) +g(here)g(because)h(Keyano)f(has)g(been)g(rewritten)987 +2294 y(since)h(the)f(original)e(experiment)i(with)g(YBW)g(in)f(1994\).) +1037 2343 y(The)16 b Fp(sear)n(ch)h(over)o(head)g Fn(starts)f(at)g +(30\045)f(and)g(increases)j(very)987 2389 y(gradually)11 +b(as)h(we)h(increase)g(from)f(4)g(to)f(16)h(processors.)19 +b(Most)12 b(of)987 2434 y(the)c(search)i(overhead)e(is)g(incurred)g(by) +g(attempting)f(to)h(do)g(searches)987 2480 y(before)16 +b(the)f(correct)h(search)h(window)d(is)h(available.)30 +b(Thus,)18 b(the)987 2526 y(slaves)12 b(use)g Fo(\013\014)j +Fn(search)e(windows)d(that)i(are)g(lar)o(ger)g(than)f(those)h(in)987 +2571 y(the)g(sequential)f(program.)19 b(Part)12 b(of)g(the)g(search)h +(overhead)g(is)e(due)987 2617 y(to)f(information)f(de\256ciency)m(,)j +(since)f(there)g(is)g(no)f(common)h(shared)987 2662 y(data)f(between)h +(the)f(slave)h(processes.)p eop +%%Page: 5 5 +5 4 bop -41 42 a Fn(Since)13 b(we)g(only)f(search)h(each)h(position)d +(to)h(12)g(ply)m(,)i(the)e(asyn-)-91 87 y(chronous)c(nature)g(of)h(the) +f(slaves)h(will)f(result)f(in)i(some)g(work)f(being)-91 +133 y(done)k(at)g(13)g(ply)g(\(or)g(more\).)20 b(The)13 +b Fp(speculative)f(sear)n(ch)i Fn(line)d(rep-)-91 178 +y(resents)f(the)f(amount)g(of)g(additional)e(search)k(beyond)d(what)i +(the)f(se-)-91 224 y(quential)d(algorithm)f(would)h(have)h(done.)13 +b(However)n(,)8 b(in)f(our)f(exper)o(-)-91 270 y(iments,)11 +b(the)h(speculative)f(search)h(results)f(were)h(not)e(used)i(so)f(that) +-91 315 y(the)e(parallel)f(program)h(produces)g(the)g(identical)f +(results)h(as)h(the)f(se-)-91 361 y(quential)i(version,)i(verifying)f +(APHID')n(s)g(correctness.)22 b(In)13 b(a)g(real)-91 +407 y(tournament)f(game,)i(this)e(speculative)g(search)i(could)e(be)h +(used)g(to)-91 452 y(look)e(an)i(extra)g(move)g(ahead)g(on)g(some)g +(key)g(variations,)f(since)h(it)-91 498 y(is)e(highly)e(likely)h(that)h +(the)g(moves)g(extended)g(a)h(ply)e(ahead)i(would)-91 +544 y(be)g(in)f(the)g(left-most)g(branches)h(of)f(the)h(tree.)18 +b(Note)11 b(that)g(other)g(al-)-91 589 y(gorithms,)e(such)h(as)h(Y)l +(oung)e(Brothers)g(W)m(ait,)h(have)g(processors)h(go)-91 +635 y(idle)d(when)h(there)g(is)f(no)h(work)f(left)g(to)g(do)h(on)f(the) +h(current)f(iteration.)-41 683 y(W)m(eill)15 b(tested)h(YBW)g(and)g +(ABDADA)g(on)g(a)h(CM-5)e(using)h(a)-91 728 y(dif)o(ferent)f(Othello)f +(program)h([9)o(].)30 b(YBW)15 b(achieved)i(a)f(9.5-fold)-91 +774 y(speedup)d(and)g(ABDADA)g(achieved)g(a)h(1)n(1-fold)e(speedup)h +(on)g(16)-91 820 y(processors.)26 b(Although)12 b(the)h(APHID)h +(results)g(are)h(not)e(as)i(good,)-91 865 y(they)i(were)i(achieved)f +(without)e(a)i(shared)h(transposition)c(table.)-91 911 +y(Both)c(ABDADA)g(and)h(YBW)g(will)f(get)g(poor)g(performance)i(on)f(a) +-91 957 y(network)6 b(of)h(workstations,)f(since)i(the)f(shared)h +(transposition)t(table)-91 1002 y(is)i(critical)g(to)f(the)h +(performance)h(of)f(the)g(algorithms.)-41 1050 y(Other)f(results)g(for) +h(parallel)f(search)i(algorithms)d(on)i(a)g(network)-91 +1095 y(of)h(workstations)g(have)h(been)g(presented)h(for)e(the)h(game)h +(of)e(chess)-91 1141 y([7)o(].)19 b(There)13 b(is)e(more)i(parallelism) +e(available)h(in)f(the)h(wider)f(chess)-91 1187 y(trees,)e(which)e +(results)h(in)f(better)h(speedups)g(in)f(comparison)h(to)f(Oth-)-91 +1232 y(ello)f([9].)13 b(Although,)6 b(a)i(distributed)d(transposition)t +(table)i(was)h(used)-91 1278 y(to)k(improve)g(the)h(performance)g(of)g +(the)f(parallel)g(chess)i(searches,)-91 1324 y(a)h(speedup)g(of)f(7)h +(was)g(possible)f(on)g(16)h(processors.)27 b(These)16 +b(re-)-91 1369 y(sults)10 b(were)i(extrapolated)e(to)h(a)g(speedup)h +(of)e(8)h(on)g(32)g(processors.)-91 1415 y(The)i(bene\256cial)h(ef)o +(fects)f(of)g(the)g(distributed)d(transposition)g(table)-91 +1461 y(are)h(derived)f(primarily)f(in)h(the)g(top)g(plies)g(of)g(the)g +(search)i(tree,)f(and)-91 1506 y(these)h(bene\256ts)g(are)h(duplicated) +e(in)h(APHID)f(by)h(maintaining)e(the)-91 1552 y(top)f +Fo(d)-6 1537 y Fl(0)16 1552 y Fn(ply)g(exclusively)h(on)g(the)g(master) +h(processor)n(.)-41 1600 y(The)d(APHID)h(algorithm)d(can)j(support)e(a) +i(shared)g(transposition)-91 1645 y(table,)17 b(but)e(the)g(algorithm)f +(does)i(not)f(depend)g(on)h(its)f(presence.)-91 1691 +y(Thus,)i(the)e(algorithm)f(gets)i(good)e(performance)i(on)f(a)h +(loosely-)-91 1737 y(coupled)8 b(network)g(of)g(workstations)f(and)h +(will)f(perform)i(even)g(bet-)-91 1782 y(ter)h(on)g(tightly-coupl)o(ed) +e(processors.)-91 1883 y Fq(4.)13 b(Conclusions)e(and)h(Futur)o(e)g(W)m +(ork)-41 1972 y Fn(The)k(APHID)f(algorithm)e(yields)i(good)f(speedups)i +(on)f(a)h(net-)-91 2018 y(work)7 b(of)g(workstations)e(without)g(the)i +(necessity)h(of)f(a)h(shared)g(trans-)-91 2063 y(position)h(table.)16 +b(Although)10 b(the)h(authors)f(are)i(pleased)g(with)e(these)-91 +2109 y(preliminary)f(results,)h(a)h(lot)e(of)h(work)g(is)g(left)f(to)h +(be)h(done.)-41 2156 y(The)20 b(load)e(balancing)h(of)g(the)g(APHID)h +(algorithm)d(has)j(not)-91 2202 y(been)10 b(addressed)g(in)e(this)h +(paper)n(.)14 b(More)9 b(intelligent)e(schemes)k(than)-91 +2248 y(round-robin)e(allocation)i(of)h(work)f(are)i(currently)e(being)h +(investi-)-91 2293 y(gated.)-41 2341 y(Our)7 b(current)f +(implementation)g(of)h(APHID)g(uses)h(a)g(\256xed-depth)-91 +2387 y(horizon)i(for)g(the)h(master)r(')n(s)g(tree.)17 +b(All)11 b(positions)e(are)j(not)e(equal)h(in)-91 2432 +y(the)i(amount)g(of)g(search)i(ef)o(fort)d(they)h(require.)23 +b(APHID)14 b(is)f(being)-91 2478 y(generalized)i(to)e(support)g(a)i +(dynamically)f(changing)g(horizon)f(in)-91 2524 y(the)d(master)n(.)-41 +2571 y(The)17 b(results)g(reported)g(here)g(are)h(based)g(on)f(a)h +(simple)e(mas-)-91 2617 y(ter/slave)j(relationship.)39 +b(As)20 b(the)f(number)g(of)g(processors)h(in-)-91 2663 +y(creases,)29 b(the)23 b(master)g(increasingly)g(becomes)h(a)g +(bottleneck.)987 42 y(APHID)11 b(has)g(been)g(generalized)h(to)e(work)g +(in)h(a)g(hierarchical)g(pro-)987 87 y(cess)i(tree.)19 +b(Mid-level)11 b(processes)i(would)e(behave)h(as)h(a)f(slave)g(to-)987 +133 y(ward)f(their)f(master)n(,)i(and)f(as)h(a)f(master)h(toward)e +(their)g(slaves.)17 b(The)987 178 y(scalability)6 b(of)i(the)g +(algorithm)e(has)i(yet)g(to)f(be)h(demonstrated)g(on)f(ar)o(-)987 +224 y(chitectures)i(of)g(more)h(than)e(16)h(processors,)h(due)g(to)e +(resource)i(lim-)987 270 y(itations.)1037 315 y(Perhaps)g(the)g +(biggest)e(contribution)f(of)i(APHID)h(is)g(that)f(it)f(eas-)987 +361 y(ily)13 b(\256ts)h(into)f(an)h(existing)f(sequential)h +Fo(\013\014)i Fn(program.)26 b(As)14 b(a)h(val-)987 407 +y(idation)h(of)i(this,)h(APHID)f(has)h(been)f(integrated)f(into)g(a)h +(chess)987 452 y(and)e(checkers)h(program)f(with)f(one)i(afternoon)e +(of)h(ef)o(fort.)31 b(The)987 498 y(application-dependent)11 +b(code)j(is)f(roughly)f(150)h(lines,)h(and)f(took)987 +544 y(less)f(than)f(an)h(hour)f(to)g(write.)17 b(Although)10 +b(all)h(of)g(the)h(programs)f(in)987 589 y(the)i(original)e(testing)h +(were)i(designed)f(at)h(the)f(University)e(of)i(Al-)987 +635 y(berta,)f(the)g(second)f(stage)h(of)f(the)h(experiment)f(will)f +(be)i(to)f(release)987 681 y(the)18 b(code)g(to)g(interested)f(members) +i(of)f(the)g(high-performance)987 726 y(games)11 b(community)f(outside) +f(of)h(the)g(University)f(of)h(Alberta.)987 822 y Fq(5.)j +(Acknowledgements)1037 905 y Fn(The)i(authors)f(would)g(like)g(to)h +(thank)f(the)g(other)h(members)h(of)987 951 y(the)10 +b(GAMES)h(group)e(at)h(the)g(University)f(of)h(Alberta)g(for)f(their)h +(as-)987 996 y(sistance)h(and)g(constructive)f(criticisms:)k(Yngvi)c +(Bjornsson,)g(An-)987 1042 y(dreas)15 b(Junghanns,)h(Y)l(aoqing)e(Gao,) +i(T)m(ony)f(Marsland)f(and)h(Aske)987 1088 y(Plaat.)h(The)c(authors)e +(would)g(also)h(like)f(to)h(thank)f(the)h(anonymous)987 +1133 y(referees)k(whose)g(comments)f(were)h(valuable)f(in)f(improving)g +(the)987 1179 y(presentation)8 b(of)h(the)g(original)f(paper)n(.)14 +b(This)9 b(work)g(was)h(supported)987 1225 y(by)g(the)h(Natural)f +(Sciences)i(and)f(Engineering)f(Research)i(Council)987 +1270 y(of)e(Canada.)987 1366 y Fq(Refer)o(ences)992 1449 +y Fc([1])21 b(M.)16 b(G.)g(Brockington.)44 b(A)16 b(T)m(axonomy)e(of)h +(Parallel)h(Game-Tree)1056 1494 y(Search)8 b(Algorithms.)14 +b Fb(ICCA)c(Journal)p Fc(,)d(1996.)13 b(In)c(press.)992 +1538 y([2])21 b(M.)10 b(G.)f(Brockington)g(and)f(J.)h(Schaef)o(fer)n(.) +k(The)8 b(APHID)i(Parallel)f Fa(\013\014)1056 1584 y +Fc(Search)j(Algorithm.)33 b(T)m(echnical)12 b(Report)g(96-07,)i +(Department)e(of)1056 1629 y(Computing)d(Science,)e(University)j(of)f +(Alberta,)h(July)e(1996.)992 1673 y([3])21 b(R.)12 b(Feldmann.)26 +b Fb(Spielbaumsuche)9 b(mit)k(massiv)d(parallelen)h(Syste-)1056 +1719 y(men)p Fc(.)24 b(PhD)11 b(thesis,)g(Universit)r(\310)-14 +b(at-Gesamthochschule)8 b(Paderborn,)1056 1764 y(Paderborn,)g(Germany)n +(,)h(May)f(1993.)992 1808 y([4])21 b(B.)7 b(C.)f(Kuszmaul.)h +Fb(Synchr)o(onize)o(d)t(MIMD)g(Computing)p Fc(.)g(PhD)f(thesis,)1056 +1854 y(M.I.T)m(.,)11 b(Cambridge,)e(MA,)h(1994.)992 1897 +y([5])21 b(T)m(.)c(A.)g(Marsland)e(and)h(M.)h(S.)f(Campbell.)49 +b(Parallel)16 b(Search)f(of)1056 1943 y(Strongly)f(Ordered)g(Game)g +(Trees.)39 b Fb(ACM)14 b(Computing)g(Surveys)p Fc(,)1056 +1989 y(14\(4\):533\261551,)8 b(1982.)992 2032 y([6])21 +b(T)m(.)11 b(A.)g(Marsland,)f(M.)h(Olafsson,)f(and)g(J.)g(Schaef)o(fer) +n(.)19 b(Multiproces-)1056 2078 y(sor)9 b(Tree-Search)e(Experiments.)12 +b(In)e(D.)f(Beal,)g(editor)o(,)g Fb(Advances)d(in)1056 +2124 y(Computer)g(Chess)f(4)p Fc(,)j(pp.)e(37\26151.)g(Permagon)g +(Press,)g(Oxford,)i(1985.)992 2167 y([7])21 b(J.)8 b(Schaef)o(fer)n(.)i +(Distributed)d(game-tree)g(searching.)i Fb(Journal)d(of)i(Par)o(-)1056 +2213 y(allel)i(and)e(Distributed)h(Computing)p Fc(,)g(6\(2\):90\2611)o +(14,)f(1989.)992 2257 y([8])21 b(V)-5 b(.)23 b(Sunderam.)76 +b(PVM:)22 b(A)h(Framework)e(for)i(Parallel)f(Dis-)1056 +2302 y(tributed)10 b(Computing.)j Fb(Concurr)o(ency)o(:)d(Practice)e +(and)h(Experience)p Fc(,)1056 2348 y(2\(4\):315\261339,)f(Dec.)h(1990.) +992 2392 y([9])21 b(J.-C.)13 b(W)m(eill.)32 b Fb(Pr)o(ogrammes)9 +b(d')r(\302)-14 b(echecs)11 b(de)h(championnat:)17 b(ar)o(chi-)1056 +2437 y(tectur)o(e)e(logicielle)h(synth)r(\301)-14 b(ese)14 +b(de)h(fonctions)g(d')r(\302)-14 b(evaluations,)17 b(par)o(-)1056 +2483 y(all)r(\302)-14 b(elisme)9 b(de)g(r)o(echer)o(c)o(he)p +Fc(.)h(PhD)f(thesis,)g(Universit)r(\302)-14 b(e)9 b(Paris)g(8,)g(1995.) +p eop +%%Trailer +end +userdict /end-hook known{end-hook}if +%%EOF |