%!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 df11 DI 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 df110 D E /Fe 23 119 df<1380EA0100120212065AA25AA25AA35AA412E0 AC1260A47EA37EA27EA27E12027EEA0080092A7C9E10>40 D<7E12407E12307EA27EA27E A37EA41380AC1300A41206A35AA25AA25A12205A5A092A7E9E10>I<1306ADB612E0A2D8 0006C7FCAD1B1C7E9720>43 D<5A1207123F12C71207B3A5EAFFF80D1C7C9B15>49 DI< 130CA2131C133CA2135C13DC139CEA011C120312021204120C1208121012301220124012 C0B512C038001C00A73801FFC0121C7F9B15>52 D<007FB512C0B612E0C9FCA8B612E06C 14C01B0C7E8F20>61 D97 D 100 DI<12FC121CAA137C1387EA1D03001E1380121CAD 38FF9FF0141D7F9C17>104 D<1218123CA21218C7FCA712FC121CB0EAFF80091D7F9C0C> I<12FC121CB3A9EAFF80091D7F9C0C>108 D<39FC7E07E0391C838838391D019018001E EBE01C001C13C0AD3AFF8FF8FF8021127F9124>IIII<3803E080EA0E19EA1805EA3807EA7003A212E0A61270A2EA38071218EA0E1B EA03E3EA0003A7EB1FF0141A7F9116>III<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 df0 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 DI<90B512E09038F001C03901C003809038800700 EB000E141E0002131C5C5CC75A495A495A49C7FC5B131E131C5BEB7002495AEA01C0EA03 8048485A5A000E1318485B48137048485AB5FC1B1C7E9B1C>90 D97 D100 D103 D110 D<001C13C0EA27011247A238870380A2120EA2381C0700A438180E20A3EA1C1E380C2640 3807C38013127E9118>117 D<001CEBC080392701C1C0124714C03987038040A2120EA2 391C070080A3EC0100EA1806A2381C0E02EB0F04380E13083803E1F01A127E911E>119 D122 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 df102 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 df11 DI 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