path: root/parallel/the-aphid-parallel.ps

%!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