path: root/parallel/brockington96taxonomy.ps

%!PS-Adobe-2.0
%%Creator: dvips 5.55 Copyright 1986, 1994 Radical Eye Software
%%Title: taxonomy.dvi
%%CreationDate: Wed Jun 12 00:05:43 1996
%%Pages: 14
%%PageOrder: Ascend
%%BoundingBox: 0 0 612 792
%%EndComments
%DVIPSCommandLine: dvips taxonomy
%DVIPSParameters: dpi=300, comments removed
%DVIPSSource:  TeX output 1996.06.12:0003
%%BeginProcSet: tex.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]{ch-image}imagemask restore}B /D{/cc X dup type /stringtype ne{]}
if nn /base get cc ctr put nn /BitMaps get S ctr S sf 1 ne{dup dup
length 1 sub dup 2 index S get sf div put}if put /ctr ctr 1 add N}B /I{
cc 1 add D}B /bop{userdict /bop-hook known{bop-hook}if /SI save N @rigin
0 0 moveto /V matrix currentmatrix dup 1 get dup mul exch 0 get dup mul
add .99 lt{/QV}{/RV}ifelse load def pop pop}N /eop{SI restore showpage
userdict /eop-hook known{eop-hook}if}N /@start{userdict /start-hook
known{start-hook}if pop /VResolution X /Resolution X 1000 div /DVImag X
/IE 256 array N 0 1 255{IE S 1 string dup 0 3 index put cvn put}for
65781.76 div /vsize X 65781.76 div /hsize X}N /p{show}N /RMat[1 0 0 -1 0
0]N /BDot 260 string N /rulex 0 N /ruley 0 N /v{/ruley X /rulex X V}B /V
{}B /RV statusdict begin /product where{pop product dup length 7 ge{0 7
getinterval dup(Display)eq exch 0 4 getinterval(NeXT)eq or}{pop false}
ifelse}{false}ifelse end{{gsave TR -.1 .1 TR 1 1 scale rulex ruley false
RMat{BDot}imagemask grestore}}{{gsave TR -.1 .1 TR rulex ruley scale 1 1
false RMat{BDot}imagemask grestore}}ifelse B /QV{gsave 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
TeXDict begin 40258431 52099146 1000 300 300
(/usr/maligne2/grad/brock/Writing/taxonomy/taxonomy.dvi)
@start /Fa 2 101 df<00200060006000C000C000C00180018001800300030003000600
06000C000C000C00180018001800300030003000600060006000C000C000C0000B1D7E95
11>61 D<007C000C0018001800180018003007B00C7010703060606060606060C0C0C0C8
C0C841C862D03C700E147E9311>100 D E /Fb 4 81 df<7FFFC0FFFFC07FFFC01C01C0
1C01C01C01C01C01C01C00001C00001C1C001C1C001FFC001FFC001FFC001C1C001C1C00
1C00001C00E01C00E01C00E01C00E01C00E07FFFE0FFFFE07FFFE013197F9816>69
D<7E1FC0FF3FE07F1FC01D07001D87001D87001D87001DC7001DC7001CC7001CC7001CE7
001CE7001CE7001C67001C67001C77001C77001C37001C37001C37001C17007F1F00FF9F
007F0F0013197F9816>78 D<1FFC003FFE007FFF00780F00F00780E00380E00380E00380
E00380E00380E00380E00380E00380E00380E00380E00380E00380E00380E00380F00780
F00780780F007FFF003FFE001FFC0011197E9816>I<7FF800FFFE007FFF001C0F801C03
801C03C01C01C01C01C01C01C01C03C01C03801C0F801FFF001FFE001FF8001C00001C00
001C00001C00001C00001C00001C00007F0000FF80007F000012197F9816>I
E /Fc 21 123 df<000FE0200070186001C00460030003E0060001E00E0000E01C000060
38000060380000207800002070000020F0000000F0000000F0000000F0000000F0000000
F0000000F0000000F0000000700000207800002038000020380000201C0000400E000040
060000800300010001C0060000701800000FE0001B1E7D9C21>67
D<FFF00FF80F0007C00F0003000F0002000F0004000F0008000F0010000F0060000F0080
000F0100000F0200000F0700000F0F80000F1780000F23C0000F43E0000F81E0000F00F0
000F00F8000F0078000F003C000F001E000F001F000F000F000F0007800F0007C00F0007
E0FFF03FFC1E1C7D9B23>75 D<FFFFE0000F0078000F001C000F000E000F0007000F0007
800F0007800F0007800F0007800F0007800F0007000F000E000F001C000F0078000FFFE0
000F0000000F0000000F0000000F0000000F0000000F0000000F0000000F0000000F0000
000F0000000F0000000F000000FFF00000191C7D9B1F>80 D<7FFFFFC0700F01C0600F00
C0400F0040400F0040C00F0020800F0020800F0020800F0020000F0000000F0000000F00
00000F0000000F0000000F0000000F0000000F0000000F0000000F0000000F0000000F00
00000F0000000F0000000F0000000F0000000F0000001F800003FFFC001B1C7D9B21>84
D<FFE07FF03FC01F000F800F001F000F0006000F000F8004000F000F8004000F800F8004
0007801FC00800078013C00800078013C0080003C033E0100003C021E0100003C021E010
0001E061F0200001E040F0200001E040F0200000F040F8400000F08078400000F0807840
000078807C80000079003C80000079003C8000003D003F0000003E001F0000003E001F00
00001E001E0000001C000E0000001C000E0000000C000C00000008000400002A1D7E9B2E
>87 D<7FFFFC7C00787000786000F06001E04001E04003C0400780400780000F00001E00
001E00003C0000780000780000F00001E00001E00403C0040780040780040F000C1E0008
1E00083C00187800387800F8FFFFF8161C7D9B1C>90 D<00200000700000700000700000
B80000B80000B800011C00011C00011C00020E00020E0004070004070007FF0008038008
03800803801801C03803C0FE0FF815157F9419>97 D<FFFF801C03801C00801C00801C00
401C00401C10401C10001C10001C30001FF0001C30001C10001C10201C10201C00201C00
601C00401C00C01C01C0FFFFC013157F9417>101 D<00FC200782600E01E01C00E03800
60780020700020F00020F00000F00000F00000F00FF8F000E0F000E07000E07800E03800
E01C00E00E00E007836000FC2015157E941B>103 D<FF8FF81C01C01C01C01C01C01C01
C01C01C01C01C01C01C01C01C01C01C01FFFC01C01C01C01C01C01C01C01C01C01C01C01
C01C01C01C01C01C01C0FF8FF815157F9419>I<FF801C001C001C001C001C001C001C00
1C001C001C001C001C001C001C001C001C001C001C001C00FF8009157F940D>I<FF83F8
1C01E01C01801C01001C02001C04001C08001C10001C30001C70001CB8001D1C001E1C00
1C0E001C07001C07801C03801C01C01C01E01C01F0FF83FC16157F941A>107
D<FFC0001C00001C00001C00001C00001C00001C00001C00001C00001C00001C00001C00
001C00001C00801C00801C00801C01801C01001C03001C0700FFFF0011157F9415>I<FC
03F81E00E01E004017004013804013C04011C04010E040107040107040103840101C4010
1C40100E401007401007C01003C01001C01000C03800C0FE004015157F9419>110
D<01F800070E000C03001C03803801C07801E07000E0F000F0F000F0F000F0F000F0F000
F0F000F0F000F07000E07801E03801C01C03801E0780070E0001F80014157E941A>I<FF
F8001C0E001C07801C03801C03C01C03C01C03C01C03801C07801C0E001FF8001C1C001C
0E001C07001C07001C07001C07801C07841C07C41C03CCFF80F816157F9419>114
D<FF83F81C00E01C00401C00401C00401C00401C00401C00401C00401C00401C00401C00
401C00401C00401C00401C00400C00C00E008006010003860000FC0015157F9419>117
D<FF0FF87E3C01E03C3801C0181C02E0101C02E0101C02E0100E0470200E0470200E0470
2007083840070838400708384003901C8003901C8003901C8001E00F0001E00F0001E00F
0000C0060000C0060000C006001F157F9423>119 D<FF87F01E03800E03000F02000704
0003840003C80001D00000F00000F00000700000780000BC00011C00010E00020F000407
000403800C03C03C03C0FE07F815157F9419>I<FF80FE1E00780E00200F004007004003
808003C18001C10000E20000E200007400007C0000380000380000380000380000380000
380000380000380001FF001715809419>I<FFFEF01CC01CC0388038807080E000E001C0
01C00380070007000E020E021C02380238067006701EFFFE0F157E9415>I
E /Fd 2 26 df<0000300000F00001C0000700001E0000780001E0000380000E00003C00
00F00000F000003800000E000007800001E000007800001C000007000003C00000F00000
300000000000000000000000000000000000007FFFE0FFFFF0141E7D951B>20
D<0F00043FC0047FE004F0F00CC03C3C801FF8800FF08003C00000000F00043FC0047FE0
04F0F00CC03C3C801FF8800FF08003C016117E901B>25 D E /Fe
22 122 df<7FF0FFE00C027F890E>45 D<000020000000300000007000000070000000F0
000000F0000001F00000037800000278000006780000047800000C780000087C0000183C
0000103C0000203C0000203C0000403C0000403E0000FFFE0000801E0001001E0001001E
0002001E0002000F0004000F0004000F001E001F00FF80FFF01C1D7F9C1F>65
D<0007F010001C0C300070026000C001E0038000E0070000E00E0000600E0000601C0000
403C00004038000040780000007800000078000000F0000000F0000000F0000000F000FF
F0F0000F80F0000780F0000F0070000F0070000F0038000F0038000F001C001F000C001E
000600660003818200007E00001C1E7C9C21>71 D<0FFFFC0000F80F0000F0038000F003
C000F001C000F001C000F001C001E003C001E003C001E003C001E0038001E0070001E00E
0003C03C0003FFE00003C0000003C0000003C0000003C000000780000007800000078000
000780000007800000078000000F0000000F800000FFF000001A1C7E9B1C>80
D<003F0400C0CC0180380300380600180E00180E00180E00181E00101E00001F00000F80
000FF80007FF0003FF8001FFC0003FE00003E00001E00000E00000E04000E04000E04000
E04000C06001C0E00180F00300CC0E0083F800161E7E9C17>83 D<1FFFFFF03C07C0F030
07803020078020600780204007802040078020400F0020800F0020000F0000000F000000
0F0000000F0000001E0000001E0000001E0000001E0000001E0000001E0000003C000000
3C0000003C0000003C0000003C0000003C000000780000007C00001FFFE0001C1C7C9B1E
>I<07F0001C18001E0C001C0E00180E00000E00000E0001FE000F0E001C1C00301C0070
1C00E01C40E01C40E03C40E05C80709D803F0E0012127D9115>97
D<01F8071C0C1E181C38183000700070007000E000E000E000600060047008301018200F
C00F127D9112>99 D<01F8070C0C061C073803300370037FFF7000E000E000E000600060
02300430081C3007C010127E9112>101 D<000F800039C00061C000E3C001C18001C000
01C00001C0000380000380000380003FF800038000038000070000070000070000070000
0700000700000E00000E00000E00000E00000E00000E00001C00001E0000FFC000121D7F
9C0D>I<000038003CCC00C69C0183080383800703800703800703800703800707000306
00038C0004F0000400000C00000C00000FFE0007FF800FFFC01801C02000C06000E0C000
C0C000C0600180200300180E0007F000161C809215>I<07E00001E00001C00001C00001
C00001C00001C00001C000038000038000038000038F8003B0C003C0E00780E00780E007
00E00700E00700E00700E00E01C00E01C00E01C00E01C00E01C00E01C01C03801E03C0FF
9FF0141D7F9C17>I<00C001C001C0018000000000000000000000000000001F80078003
800700070007000700070007000E000E000E000E000E000E001C001E00FF800A1D7F9C0C
>I<07E001E001C001C001C001C001C001C0038003800380038003800380070007000700
0700070007000E000E000E000E000E000E001C001E00FF800B1D7F9C0C>108
D<1F8FC0FC00079061060003E07607000780780700078078070007007007000700700700
070070070007007007000E00E00E000E00E00E000E00E00E000E00E00E000E00E00E000E
00E00E001C01C01C001E01E01E00FF8FF8FF8021127F9124>I<1F8F8007B0C003C0E007
80E00780E00700E00700E00700E00700E00E01C00E01C00E01C00E01C00E01C00E01C01C
03801E03C0FF9FF014127F9117>I<00FC000307000E01801C01C03800C03000C07000E0
7000E07000E0E001C0E001C0E001C0600180600380700700380E001C180007E00013127E
9115>I<1F9C07EE03CF078E078C07000700070007000E000E000E000E000E000E001C00
1E00FFC010127F9110>114 D<03F20C0E18061004300438043E001FE00FF007F8003C40
1C400C400C6018E010D0608FC00F127F9110>I<020002000200060006000C001C003C00
FFE01C001C00380038003800380038003800700070407040704070407080708031001E00
0B1A7C9910>I<1FE3FC07C1E003818001C10001C20000E40000EC000078000070000038
00007800009C00011E00020E000407000C07003C0780FE1FF016127F9116>120
D<0FF0FE03C03801C03001C02001C06001C04001E08000E08000E10000E10000E2000072
00007400007C00007800007000003000002000002000004000004000708000F10000F100
00E60000780000171A809116>I E /Ff 2 13 df<07C0000C3040101040201880601880
C00C80C00D00C00E00800E00800C00C01C00C02C0060C4803F0300120E7E8D17>11
D<000F0000308000C0C00080400100600200C00400C0040080040180083F00083E000801
00080180100180100180100180100180300300300300300600280C0044180043E0004000
00400000800000800000800000800000131D7F9614>I E /Fg 13
118 df<60F0F0600404798312>46 D<03E007F01E18381C30FC71FE739EE30EE70EE70E
E70EE70EE30C739C71F830F038001E0E07FE03F80F147F9312>64
D<3F807FC070E0207000700FF03FF07870E070E070E07070F03FFE1F3E0F0E7E8D12>97
D<F800F80038003800380038003BE03FF03C38381C380C380E380E380E380E380C381C3C
383FF01BC00F147F9312>I<07F01FF8383870106000E000E000E000E000600070383838
1FF007E00D0E7E8D12>I<07801FE0387070706038E038FFF8FFF8E0006000703838381F
F007C00D0E7E8D12>101 D<F800F80038003800380038003BFC3BFC38F039E03BC03F80
3F803FC03DE038E038703838FC7EFC7E0F147F9312>107 D<FF00FF0007000700070007
00070007000700070007000700070007000700070007000700FFF8FFF80D147E9312>I<
0F803FE038E07070E038E038E038E038E038F078707038E03FE00F800D0E7E8D12>111
D<FCF8FDFC1F1C1E081E001C001C001C001C001C001C001C00FFC0FFC00E0E7E8D12>
114 D<1FF03FF06070C070E0007F003FE00FF000786018E018F030FFE0DFC00D0E7E8D12
>I<06000E000E000E007FF8FFF80E000E000E000E000E000E000E000E380E380E3807F0
03C00D127F9112>I<F8F8F8F838383838383838383838383838383838383838781FFE0F
BE0F0E7F8D12>I E /Fh 73 123 df<00FCF807839C0E079C1C07081C07001C07001C07
001C07001C0700FFFFE01C07001C07001C07001C07001C07001C07001C07001C07001C07
001C07001C07001C0700FF1FE01617809615>11 D<00FC000782000E07001C07001C0200
1C00001C00001C00001C0000FFFF001C07001C07001C07001C07001C07001C07001C0700
1C07001C07001C07001C07001C0700FF1FE01317809614>I<60C0F1E0F1E070E0102010
2020402040408040800B0A7F9612>34 D<01C0000320000610000E10000E10000E10000E
20000E40000E80000780FE0700380700200B802013804031C04061E08060E100E07100E0
3A00E01C02700E0238370C0FC1F817177F961B>38 D<0102040C1818303070606060E0E0
E0E0E0E0E0E0E0E060606070303018180C04020108227D980E>40
D<8040203018180C0C0E060606070707070707070707070606060E0C0C18183020408008
227E980E>I<020002000200C218F2783AE00F800F803AE0F278C2180200020002000D0E
7E9812>I<00300000300000300000300000300000300000300000300000300000300000
3000FFFFFCFFFFFC00300000300000300000300000300000300000300000300000300000
300000300016187E931B>I<60F0F070101020204040040A7D830A>I<FF80FF8009028087
0C>I<60F0F06004047D830A>I<0008001800300030003000600060006000C000C000C001
8001800180030003000600060006000C000C000C00180018001800300030003000600060
006000C000C0000D217E9812>I<07C018303018701C600C600CE00EE00EE00EE00EE00E
E00EE00EE00EE00E600C600C701C30181C7007C00F157F9412>I<03000700FF00070007
000700070007000700070007000700070007000700070007000700070007007FF00C157E
9412>I<0F8030E040708030C038E0384038003800700070006000C00180030006000C08
080810183FF07FF0FFF00D157E9412>I<0FE030306018701C701C001C00180038006007
E000300018000C000E000EE00EE00EC00C401830300FE00F157F9412>I<003000300070
00F001F001700270047008701870107020704070C070FFFE0070007000700070007003FE
0F157F9412>I<20303FE03FC0240020002000200020002F8030E0207000300038003840
38E038E0388030406020C01F000D157E9412>I<01F00608080C181C301C70006000E000
E3E0EC30F018F00CE00EE00EE00E600E600E300C3018183007C00F157F9412>I<40007F
FE7FFC7FF8C008801080200040008000800100010003000200060006000E000E000E000E
000E0004000F167E9512>I<07E018302018600C600C700C78183E101F600FC00FF018F8
607C601EC00EC006C006C004600C38300FE00F157F9412>I<07C0183030186018E00CE0
0CE00EE00EE00E601E301E186E0F8E000E000C001C70187018603020C01F800F157F9412
>I<60F0F06000000000000060F0F060040E7D8D0A>I<FFFFFCFFFFFC0000000000000000
00000000000000000000FFFFFCFFFFFC160A7E8C1B>61 D<001000003800003800003800
005C00005C00005C00008E00008E00008E0001070001070003078002038002038007FFC0
0401C00401C00800E00800E01800E03800F0FE03FE17177F961A>65
D<FFFE001C03801C00E01C00601C00701C00701C00701C00701C00E01C01C01FFF801FFF
C01C00E01C00701C00301C00381C00381C00381C00381C00701C00E01C01C0FFFF001517
7F9619>I<00FC100383300E00B01C0070380030300030700010600010E00010E00000E0
0000E00000E00000E00000E000106000107000103000203800201C00400E008003830000
FC0014177E9619>I<FFFF001C01C01C00E01C00301C00381C00181C001C1C000C1C000E
1C000E1C000E1C000E1C000E1C000E1C000E1C000C1C001C1C001C1C00381C00301C0060
1C01C0FFFF0017177F961B>I<FFFFE01C00E01C00601C00201C00101C00101C00101C04
001C04001C04001C0C001FFC001C0C001C04001C04081C04081C00081C00181C00101C00
101C00301C00F0FFFFF015177F9618>I<FFFFE01C00E01C00601C00201C00101C00101C
00101C04001C04001C04001C0C001FFC001C0C001C04001C04001C04001C00001C00001C
00001C00001C00001C0000FFC00014177F9617>I<007E080381980600580C0038180018
300018700008700008E00008E00000E00000E00000E00000E003FEE00038700038700038
3000381800380C00380600380380D8007F0817177E961C>I<FF83FE1C00701C00701C00
701C00701C00701C00701C00701C00701C00701C00701FFFF01C00701C00701C00701C00
701C00701C00701C00701C00701C00701C0070FF83FE17177F961A>I<FFE00E000E000E
000E000E000E000E000E000E000E000E000E000E000E000E000E000E000E000E000E000E
00FFE00B177F960D>I<0FFC00E000E000E000E000E000E000E000E000E000E000E000E0
00E000E000E000E000E0E0E0E0E0C1C061801F000E177E9612>I<FF80FE1C00781C0060
1C00401C00801C01001C06001C08001C10001C38001C78001C9C001D0E001E0E001C0700
1C03801C01C01C01C01C00E01C00701C00781C007CFF80FF18177F961B>I<FFC0001C00
001C00001C00001C00001C00001C00001C00001C00001C00001C00001C00001C00001C00
001C00201C00201C00201C00601C00601C00401C00C01C03C0FFFFC013177F9616>I<FE
0003F81E0003C0170005C0170005C0170005C0138009C0138009C011C011C011C011C011
C011C010E021C010E021C0107041C0107041C0107041C0103881C0103881C0101D01C010
1D01C0100E01C0100E01C0380E01C0FE040FF81D177F9620>I<FC00FE1E00381F001017
001013801011C01011C01010E010107010103810103810101C10100E10100F1010071010
03901001D01001D01000F0100070100030380030FE001017177F961A>I<00FC00030300
0E01C01C00E0380070300030700038600018E0001CE0001CE0001CE0001CE0001CE0001C
E0001C7000387000383000303800701C00E00E01C003030000FC0016177E961B>I<FFFE
001C03801C00C01C00601C00701C00701C00701C00701C00601C00C01C03801FFE001C00
001C00001C00001C00001C00001C00001C00001C00001C00001C0000FF800014177F9618
>I<FFFC001C03801C00C01C00E01C00701C00701C00701C00701C00E01C00C01C03801F
FE001C07801C01C01C00E01C00E01C00E01C00E01C00E01C00E11C00E11C0072FF803C18
177F961A>82 D<0FC4302C601C400CC004C004C004E00070007F003FE00FF801FC001C00
0E0006800680068006C004E008D81087E00F177E9614>I<7FFFF8603818403808403808
803804803804803804003800003800003800003800003800003800003800003800003800
00380000380000380000380000380000380007FFC016177F9619>I<FF80FE1C00381C00
101C00101C00101C00101C00101C00101C00101C00101C00101C00101C00101C00101C00
101C00101C00101C00100E0020060020030040018180007E0017177F961A>I<FF80FE3C
00381C00101C00100E00200E002007004007004007004003808003808003C18001C10001
C10000E20000E20000F60000740000740000380000380000380000100017177F961A>I<
FF07FC3F803C01E00E001C00E004001C00E004001C017004000E017008000E017008000E
023808000702381000070238100007041C100003841C200003841C200003880E200001C8
0E400001C80E400001D80F400000F007800000F007800000F00780000060030000006003
0000006003000021177F9624>I<FFC03F801E001C000F00080007001000078030000380
200001C0400001E0400000E0800000F1800000710000003A0000003E0000001C0000001C
0000001C0000001C0000001C0000001C0000001C0000001C0000001C000000FF80001917
80961A>89 D<204020404080408081008100E1C0F1E0F1E060C00B0A7B9612>92
D<1FC0386038301038003803F81E3830387038E039E039E07970FF1F1E100E7F8D12>97
D<FC00001C00001C00001C00001C00001C00001C00001C00001C00001CF8001F06001C03
001C03801C01801C01C01C01C01C01C01C01C01C01801C03801C03001B0E0010F8001217
809614>I<07F01838303870106000E000E000E000E000600070083008183007C00D0E7F
8D10>I<007E00000E00000E00000E00000E00000E00000E00000E00000E0007CE001C3E
00300E00700E00600E00E00E00E00E00E00E00E00E00600E00700E00301E00182E0007CF
C012177F9614>I<0FC0186030307038E018FFF8E000E000E000600070083010183007C0
0D0E7F8D10>I<03E006700E701C201C001C001C001C001C00FF801C001C001C001C001C
001C001C001C001C001C001C001C00FF800C1780960B>I<0F9E18E33060707070707070
306018C02F80200060003FE03FF83FFC600EC006C006C006600C38380FE010157F8D12>
I<FC00001C00001C00001C00001C00001C00001C00001C00001C00001C7C001D8E001E07
001C07001C07001C07001C07001C07001C07001C07001C07001C07001C0700FF9FE01317
809614>I<183C3C1800000000007C1C1C1C1C1C1C1C1C1C1C1C1CFF081780960A>I<FC00
001C00001C00001C00001C00001C00001C00001C00001C00001C3F801C1C001C18001C20
001C40001CC0001FE0001CF0001C70001C78001C3C001C1E001C1E00FF3FC01217809613
>107 D<FC001C001C001C001C001C001C001C001C001C001C001C001C001C001C001C00
1C001C001C001C001C001C00FF80091780960A>I<FC7C1F001D8E63801E0781C01C0701
C01C0701C01C0701C01C0701C01C0701C01C0701C01C0701C01C0701C01C0701C01C0701
C0FF9FE7F81D0E808D1E>I<FC7C001D8E001E07001C07001C07001C07001C07001C0700
1C07001C07001C07001C07001C0700FF9FE0130E808D14>I<07C018303018600C600CE0
0EE00EE00EE00EE00E701C3018183007C00F0E7F8D12>I<FCF8001F0E001C03001C0380
1C01801C01C01C01C01C01C01C01C01C01801C03801C07001F0E001CF8001C00001C0000
1C00001C00001C0000FF80001214808D14>I<07C2001C2600381E00700E00600E00E00E
00E00E00E00E00E00E00600E00700E00301E001C2E0007CE00000E00000E00000E00000E
00000E00007FC012147F8D13>I<FCF01D381E381C101C001C001C001C001C001C001C00
1C001C00FF800D0E808D0E>I<1F4060C0C040C040E000FF007F801FC001E080608060C0
60E0C09F000B0E7F8D0E>I<080008000800180018003800FF8038003800380038003800
3800380038403840384038401C800F000A147F930E>I<FC3F001C07001C07001C07001C
07001C07001C07001C07001C07001C07001C07001C0F000E170003E7E0130E808D14>I<
FE1F3C0E3C0C1C081C080E100E100720072003C003C003C001800180100E7F8D13>I<FC
FE7C3838383838101C3C201C3C201C4C200E4E400E4E400E864007878007878007038003
0300030300160E7F8D19>I<FE3F3C181C100E20074007C0038001C002E004F008701838
383CFC7F100E7F8D13>I<FE1F3C0E3C0C1C081C080E100E100720072003C003C003C001
80018001000100E200E200A400780010147F8D13>I<FFF0C0E080E081C0838087800700
0E001E081C08381870107030FFF00D0E7F8D10>I E /Fi 1 50 df<0C003C00CC000C00
0C000C000C000C000C000C000C000C000C000C000C00FF8009107E8F0F>49
D E /Fj 1 4 df<01800180018001804182F18F399C0FF003C003C00FF0399CF18F4182
018001800180018010127E9215>3 D E /Fk 12 113 df<00F000030C000E06041C0704
380708300708700790700790E003A0E003A0E003C0E00380E00380E00380600780601B88
3061900F80E016127E911B>11 D<0001F000061800080C00100C00200E00400E00800E00
801C01001C010018010038020FF00210C0020FE002003004003004003004003804003808
00700800700800700800E01800E01800C0140180140300230E0020F80020000020000040
000040000040000040000080000080000017257F9C17>I<01FFFF80003C01E000380070
003800380038001C0038001C0070001C0070001E0070001E0070001E00E0001E00E0001E
00E0001E00E0001E01C0003C01C0003C01C0003C01C000380380007803800070038000F0
038000E0070001C0070003800700070007001C000E007800FFFFC0001F1C7E9B22>68
D<01FFFFF8003C0078003800180038001000380010003800100070001000700010007010
100070100000E0200000E0200000E0600000FFE00001C0400001C0400001C0400001C040
0003808040038000400380008003800080070001000700010007000300070006000E003E
00FFFFFC001D1C7E9B1F>I<01FC00FF80001C001C00002E001800002E001000002E0010
00002700100000470020000043002000004380200000438020000081C040000081C04000
0081C040000080E040000100E08000010070800001007080000100708000020039000002
00390000020039000002001D000004001E000004000E000004000E00000C000E00001C00
040000FF80040000211C7E9B21>78 D<0003F800000E0E000038038000E001C001C001C0
038000E0070000E00F0000F01E0000F01C0000F03C0000F03C0000F0780000F0780000F0
780000F0F00001E0F00001E0F00001E0F00003C0F00003C0F0000780F0000780F0000F00
70000E0070001C00380038003C0070001C01C0000707800001FC00001C1E7E9C20>I<01
FFFE00003C03C0003800E0003800F00038007000380070007000F0007000F0007000F000
7001E000E001C000E0078000E01E0000FFF00001C0300001C0180001C01C0001C01C0003
801C0003801C0003801C0003801C0007003C0007003C0807003C0807003C100F001E10FF
E00E20000007C01D1D7E9B20>82 D<000FC100303300400F008006018006030006030006
06000406000407000007000007800003F00001FF0000FFC0003FE00003E00000F0000070
0000300000302000302000306000606000606000C0600080F00300CC060083F800181E7E
9C19>I<3F00070007000E000E000E000E001C001C001C001C0039E03A303C1838187018
701C701C701CE038E038E038E030E070E060E0C061C023001E000E1D7E9C12>98
D<0007E00000E00000E00001C00001C00001C00001C000038000038000038000038001E7
000717000C0F00180F00380E00300E00700E00700E00E01C00E01C00E01C00E01C00E038
80E03880E038806078803199001E0E00131D7E9C16>100 D<0FC00001C00001C0000380
000380000380000380000700000700000700000700000E07000E18800E21C00E23C01C47
801C83001D00001E00003F800039C00038E00038E00070E10070E10070E10070E200E062
00603C00121D7E9C16>107 D<07078009C86008D03008E03011C03011C03801C03801C0
380380700380700380700380600700E00700C00701800783000E86000E78000E00000E00
001C00001C00001C00001C00003C0000FF8000151A819115>112
D E /Fl 53 122 df<0020004001800380030006000E001C001C003C0038003800780078
007800F800F000F000F000F000F000F000F000F000F000F800780078007800380038003C
001C001C000E000600030003800180004000200B297C9E13>40 D<800040003000380018
000C000E000700070007800380038003C003C003C003E001E001E001E001E001E001E001
E001E001E003E003C003C003C0038003800780070007000E000C00180038003000400080
000B297D9E13>I<FFE0FFE0FFE0FFE00B047F8A10>45 D<78FCFCFCFC7806067D850D>I<
00600001E0000FE000FFE000F3E00003E00003E00003E00003E00003E00003E00003E000
03E00003E00003E00003E00003E00003E00003E00003E00003E00003E00003E00003E000
03E0007FFF807FFF80111B7D9A18>49 D<07F8001FFE00383F80780FC0FC07C0FC07E0FC
03E0FC03E07803E00007E00007C00007C0000F80001F00001E0000380000700000E00001
80600300600600600800E01FFFC03FFFC07FFFC0FFFFC0FFFFC0131B7E9A18>I<03F800
1FFE003C1F003C0F807C07C07E07C07C07C03807C0000F80000F80001E00003C0003F800
001E00000F800007C00007C00007E03007E07807E0FC07E0FC07E0FC07C0780F80781F00
1FFE0007F800131B7E9A18>I<000180000380000780000F80001F80003F80006F8000CF
80008F80018F80030F80060F800C0F80180F80300F80600F80C00F80FFFFF8FFFFF8000F
80000F80000F80000F80000F80000F8001FFF801FFF8151B7F9A18>I<1801801FFF001F
FE001FFC001FF8001FC00018000018000018000018000019F8001E0E00180F8010078000
07C00007E00007E00007E07807E0F807E0F807E0F807C0F007C0600F80381F001FFE0007
F000131B7E9A18>I<6000007FFFE07FFFE07FFFC07FFF807FFF80E00300C00600C00C00
C0180000300000300000600000E00000E00001E00001C00003C00003C00003C00003C000
07C00007C00007C00007C00007C00007C000038000131C7D9B18>55
D<03F8000FFE001E0F803807803803C07803C07803C07E03C07F83807FC7003FFE001FFC
000FFE0007FF801DFF80387FC0781FE0F007E0F003E0F001E0F001E0F001E07801C07803
803E07801FFE0003F800131B7E9A18>I<03F8000FFE001E0F003C07807807807803C0F8
03C0F803C0F803E0F803E0F803E0F803E07807E03807E03C0BE00E1BE003E3E00003E000
03C00003C03807C07C07807C0700780F00383C001FF8000FE000131B7E9A18>I<000380
00000380000007C0000007C0000007C000000FE000000FE000001FF000001BF000001BF0
000031F8000031F8000061FC000060FC0000E0FE0000C07E0000C07E0001803F0001FFFF
0003FFFF8003001F8003001F8006000FC006000FC00E000FE00C0007E0FFC07FFEFFC07F
FE1F1C7E9B24>65 D<FFFFF800FFFFFF000FC01F800FC00FC00FC007C00FC007E00FC007
E00FC007E00FC007E00FC007E00FC007C00FC00F800FC03F000FFFFE000FC00F800FC007
C00FC007E00FC003E00FC003F00FC003F00FC003F00FC003F00FC003F00FC007E00FC007
E00FC01FC0FFFFFF00FFFFFC001C1C7E9B22>I<001FE02000FFF8E003F80FE007C003E0
0F8001E01F0000E03E0000E03E0000607E0000607C000060FC000000FC000000FC000000
FC000000FC000000FC000000FC000000FC0000007C0000607E0000603E0000603E0000C0
1F0000C00F80018007C0030003F80E0000FFFC00001FE0001B1C7D9B22>I<FFFFF800FF
FFFF000FC01FC00FC007E00FC001F00FC001F80FC000F80FC000FC0FC0007C0FC0007C0F
C0007E0FC0007E0FC0007E0FC0007E0FC0007E0FC0007E0FC0007E0FC0007E0FC0007C0F
C0007C0FC0007C0FC000F80FC000F80FC001F00FC007E00FC01FC0FFFFFF00FFFFF8001F
1C7E9B25>I<FFFFFF00FFFFFF000FC01F000FC007000FC003000FC003800FC003800FC1
81800FC181800FC181800FC180000FC380000FFF80000FFF80000FC380000FC180000FC1
80000FC180600FC180600FC000E00FC000C00FC000C00FC001C00FC001C00FC003C00FC0
0F80FFFFFF80FFFFFF801B1C7E9B1F>I<FFFFFF00FFFFFF000FC01F000FC007000FC003
000FC003800FC003800FC001800FC181800FC181800FC180000FC180000FC380000FFF80
000FFF80000FC380000FC180000FC180000FC180000FC180000FC000000FC000000FC000
000FC000000FC000000FC00000FFFF0000FFFF0000191C7E9B1E>I<000FF008007FFE38
01FC07F807E001F80F8000781F0000783F0000383E0000387E0000187C000018FC000000
FC000000FC000000FC000000FC000000FC000000FC007FFFFC007FFF7C0001F87E0001F8
3E0001F83F0001F81F0001F80F8001F807E001F801FC07F8007FFE78000FF818201C7D9B
26>I<FFFC3FFFFFFC3FFF0FC003F00FC003F00FC003F00FC003F00FC003F00FC003F00F
C003F00FC003F00FC003F00FC003F00FFFFFF00FFFFFF00FC003F00FC003F00FC003F00F
C003F00FC003F00FC003F00FC003F00FC003F00FC003F00FC003F00FC003F00FC003F0FF
FC3FFFFFFC3FFF201C7E9B25>I<FFFFFFFF07E007E007E007E007E007E007E007E007E0
07E007E007E007E007E007E007E007E007E007E007E007E007E007E007E0FFFFFFFF101C
7F9B12>I<07FFF007FFF0001F80001F80001F80001F80001F80001F80001F80001F8000
1F80001F80001F80001F80001F80001F80001F80001F80001F80001F80301F80781F80FC
1F80FC1F80FC1F00783E00387C000FF000141C7F9B19>I<FFFC07FFFFFC07FF0FC000E0
0FC001C00FC003800FC006000FC00C000FC038000FC070000FC0E0000FC1C0000FC3C000
0FC7E0000FCFE0000FFBF0000FF3F8000FE1F8000FC0FC000FC0FE000FC07E000FC03F00
0FC01F800FC01FC00FC00FC00FC007E00FC007F0FFFC3FFFFFFC3FFF201C7E9B25>I<FF
FF00FFFF000FC0000FC0000FC0000FC0000FC0000FC0000FC0000FC0000FC0000FC0000F
C0000FC0000FC0000FC0000FC0000FC0030FC0030FC0030FC0070FC0070FC0060FC00E0F
C01E0FC07EFFFFFEFFFFFE181C7E9B1D>I<FFC00003FFFFE00007FF0FE00007F00DF000
0DF00DF0000DF00DF0000DF00CF80019F00CF80019F00C7C0031F00C7C0031F00C3E0061
F00C3E0061F00C1F00C1F00C1F00C1F00C1F00C1F00C0F8181F00C0F8181F00C07C301F0
0C07C301F00C03E601F00C03E601F00C01FC01F00C01FC01F00C01FC01F00C00F801F00C
00F801F0FFC0701FFFFFC0701FFF281C7E9B2D>I<FFE003FFFFE003FF0FF000300FF800
300DFC00300CFE00300C7E00300C3F00300C1F80300C1FC0300C0FE0300C07F0300C03F0
300C01F8300C01FC300C00FE300C007F300C003F300C001FB00C001FF00C000FF00C0007
F00C0003F00C0001F00C0000F00C0000F0FFC00070FFC00030201C7E9B25>I<003FE000
01F07C0003C01E000F800F801F0007C01E0003C03E0003E07E0003F07C0001F07C0001F0
FC0001F8FC0001F8FC0001F8FC0001F8FC0001F8FC0001F8FC0001F8FC0001F87C0001F0
7E0003F07E0003F03E0003E03F0007E01F0007C00F800F8003C01E0001F07C00003FE000
1D1C7D9B24>I<FFFFF800FFFFFE000FC03F800FC00F800FC007C00FC007E00FC007E00F
C007E00FC007E00FC007E00FC007C00FC007C00FC00F800FC03F000FFFFC000FC000000F
C000000FC000000FC000000FC000000FC000000FC000000FC000000FC000000FC000000F
C00000FFFC0000FFFC00001B1C7E9B21>I<FFFFF00000FFFFFE00000FC03F00000FC00F
80000FC007C0000FC007E0000FC007E0000FC007E0000FC007E0000FC007E0000FC007C0
000FC00F80000FC03E00000FFFF000000FC07C00000FC03E00000FC03F00000FC01F8000
0FC01F80000FC01F80000FC01F80000FC01F80000FC01F80000FC01F81800FC01F81800F
C00FC180FFFC07C300FFFC01FE00211C7E9B24>82 D<07F8201FFEE03C07E07801E07000
E0F000E0F00060F00060F80000FE0000FFE0007FFE003FFF003FFF800FFFC007FFE0007F
E00003F00001F00000F0C000F0C000F0C000E0E000E0F001C0FC03C0EFFF0083FC00141C
7D9B1B>I<7FFFFFE07FFFFFE0781F81E0701F80E0601F8060E01F8070C01F8030C01F80
30C01F8030C01F8030001F8000001F8000001F8000001F8000001F8000001F8000001F80
00001F8000001F8000001F8000001F8000001F8000001F8000001F8000001F8000001F80
0007FFFE0007FFFE001C1C7E9B21>I<FFFC03FFFFFC03FF0FC000300FC000300FC00030
0FC000300FC000300FC000300FC000300FC000300FC000300FC000300FC000300FC00030
0FC000300FC000300FC000300FC000300FC000300FC000300FC0003007C0003007C00060
03E000E001F001C000FC0780007FFE00000FF800201C7E9B25>I<FFFC7FFE0FFCFFFC7F
FE0FFC0FC007E000C00FC007F000C00FE003F001C007E003F0018007E007F8018003F007
F8030003F007F8030003F80CFC070001F80CFC060001F81CFE060001FC187E0E0000FC18
7E0C0000FC387F0C00007E303F1800007E303F1800007F601FB800003F601FB000003FE0
1FF000003FC00FF000001FC00FE000001FC00FE000000F8007C000000F8007C000000F00
03C0000007000380000007000380002E1C7F9B31>87 D<0FF8001C1E003E0F803E07803E
07C01C07C00007C0007FC007E7C01F07C03C07C07C07C0F807C0F807C0F807C0780BC03E
13F80FE1F815127F9117>97 D<FF0000FF00001F00001F00001F00001F00001F00001F00
001F00001F00001F00001F3F801FE1E01F80701F00781F003C1F003C1F003E1F003E1F00
3E1F003E1F003E1F003E1F003C1F003C1F00781F80701EC1E01C3F00171D7F9C1B>I<03
FC000E0E001C1F003C1F00781F00780E00F80000F80000F80000F80000F80000F8000078
00007801803C01801C03000E0E0003F80011127E9115>I<000FF0000FF00001F00001F0
0001F00001F00001F00001F00001F00001F00001F001F9F00F07F01C03F03C01F07801F0
7801F0F801F0F801F0F801F0F801F0F801F0F801F07801F07801F03C01F01C03F00F0FFE
03F9FE171D7E9C1B>I<01FC000F07001C03803C01C07801C07801E0F801E0F801E0FFFF
E0F80000F80000F800007800007C00603C00601E00C00F038001FC0013127F9116>I<00
7F0001E38003C7C00787C00F87C00F83800F80000F80000F80000F80000F8000FFF800FF
F8000F80000F80000F80000F80000F80000F80000F80000F80000F80000F80000F80000F
80000F80000F80007FF8007FF800121D809C0F>I<03F8F00E0F381E0F381C07303C0780
3C07803C07803C07801C07001E0F000E0E001BF8001000001800001800001FFF001FFFC0
0FFFE01FFFF07801F8F00078F00078F000787000707800F01E03C007FF00151B7F9118>
I<FF0000FF00001F00001F00001F00001F00001F00001F00001F00001F00001F00001F0F
C01F31E01F40F01F80F81F80F81F00F81F00F81F00F81F00F81F00F81F00F81F00F81F00
F81F00F81F00F81F00F8FFE7FFFFE7FF181D7F9C1B>I<1E003F003F003F003F001E0000
0000000000000000000000FF00FF001F001F001F001F001F001F001F001F001F001F001F
001F001F001F00FFE0FFE00B1E7F9D0E>I<FF00FF001F001F001F001F001F001F001F00
1F001F001F001F001F001F001F001F001F001F001F001F001F001F001F001F001F001F00
FFE0FFE00B1D7F9C0E>108 D<FF0FC07E00FF31E18F001F40F207801F80FC07C01F80FC
07C01F00F807C01F00F807C01F00F807C01F00F807C01F00F807C01F00F807C01F00F807
C01F00F807C01F00F807C01F00F807C01F00F807C0FFE7FF3FF8FFE7FF3FF825127F9128
>I<FF0FC0FF31E01F40F01F80F81F80F81F00F81F00F81F00F81F00F81F00F81F00F81F
00F81F00F81F00F81F00F81F00F8FFE7FFFFE7FF18127F911B>I<01FC000F07801C01C0
3C01E07800F07800F0F800F8F800F8F800F8F800F8F800F8F800F87800F07800F03C01E0
1E03C00F078001FC0015127F9118>I<FF3F80FFE1E01F80F01F00781F007C1F003C1F00
3E1F003E1F003E1F003E1F003E1F003E1F003C1F007C1F00781F80F01FC1E01F3F001F00
001F00001F00001F00001F00001F0000FFE000FFE000171A7F911B>I<FE3E00FE47001E
8F801E8F801E8F801F07001F00001F00001F00001F00001F00001F00001F00001F00001F
00001F0000FFF000FFF00011127F9114>114 D<1FD830786018E018E018F000FF807FE0
7FF01FF807FC007CC01CC01CE01CE018F830CFC00E127E9113>I<030003000300030007
0007000F000F003FFCFFFC1F001F001F001F001F001F001F001F001F001F0C1F0C1F0C1F
0C0F08079803F00E1A7F9913>I<FF07F8FF07F81F00F81F00F81F00F81F00F81F00F81F
00F81F00F81F00F81F00F81F00F81F00F81F00F81F01F80F01F80786FF01F8FF18127F91
1B>I<FFC1FCFFC1FC1F00601F80E00F80C00FC0C007C18007C18003E30003E30001F600
01F60001FE0000FC0000FC0000780000780000300016127F9119>I<FFC1FCFFC1FC1F00
601F80E00F80C00FC0C007C18007C18003E30003E30001F70001F60000FE0000FC0000FC
00007800007800003000003000007000706000F86000F8C000F980007300003E0000161A
7F9119>121 D E /Fm 2 51 df<0C001C00EC000C000C000C000C000C000C000C000C00
0C000C000C000C000C000C000C00FFC00A137D9211>49 D<1F0060C06060F070F0306030
00700070006000C001C00180020004000810101020207FE0FFE00C137E9211>I
E /Fn 68 123 df<0001FC000703000C03001C07001C0300180000380000380000380000
380000700007FFFC00701C00701C00701C00E03800E03800E03800E03800E07001C07001
C07001C07001C0E201C0E201C0E20380E4038064038038038000030000070000060000C6
0000E40000CC00007000001825819C17>12 D<E0E0E070301018080508749C15>18
D<03070E1C3860C0800808729C15>I<183C3C3C0404080810204080060C779C0D>39
D<00030006000800180030006000C000C0018003000300060006000C000C001C00180018
00380030003000700070006000600060006000E000E000E000E000E00060006000600060
00600020003000100008000800102A7B9E11>I<001000100008000C0004000600060006
00060006000700070007000700070006000600060006000E000E000C000C001C00180018
0038003000300060006000C000C001800300030006000C00180010006000C000102A809E
11>I<0030000060000060000060001841803C47000ECE0007B80001E00003C0000EF000
39B800711E00C10C000300000300000300000600001112799E15>I<1838783808081010
20404080050C7D830D>44 D<FFC0FFC0FFC00A037D890F>I<3078F06005047C830D>I<00
3C0000C6000183000303000603000603800E03800C03801C03801C030038070038070038
0700380700700E00700E00700E00700E00E01C00E01C00E01C00E03800E03800E03000C0
6000E0600060C0007180001E0000111D7B9B15>48 D<00020006000C001C007C039C0038
003800380038007000700070007000E000E000E000E001C001C001C001C0038003800380
03800780FFF00F1C7C9B15>I<003C0000C3000101800201800201C00441C00441C00841
C00841C00841C01083801083801107000E0600000C0000180000300000C0000100000600
000800001001001002002002004006007E0C00C7F80083F80080E000121D7C9B15>I<00
3E0000C1800101800200C00400C00440C00841C00841C00841C008838007038000070000
0E0001F800003800000C00000C00000E00000E00000E00000E00700E00E01C00801C0080
380080300040600021C0001F0000121D7C9B15>I<0001800001C0000380000380000380
000300000700000700000600000E00000C00001C00001800001800003000003000006000
00400000C600018E00010E00020E00061C000C1C00181C003F1C0040F800803F00003800
00380000700000700000700000700000E00000600012247E9B15>I<00C06000FFC001FF
8001FE00010000010000020000020000020000020000047800058C000606000406000806
00000700000700000600000E00000E00700E00700C00E01C008018008038004030004060
0021C0001F0000131D7C9B15>I<001E000061000081800180800300C00300C006018006
018006018007030007860003CC0003F00001F000037800063C00081E00180E00300E0060
0600600600600600C00C00C00C00C0180060100060200030C0000F0000121D7C9B15>56
D<003C0000C6000183000303000603000E03000C03801C03801C03001C03003807003807
00380700380F00380E00181E00181E000C6C00079C00001C000018000038000030000060
00E0C000E0C0008180008600007C0000111D7B9B15>I<060F0F06000000000000000000
003078F06008127C910D>I<000018000000180000003800000038000000780000007800
0000B8000001B800000138000002380000023C0000041C0000041C0000081C0000181C00
00101C0000201C0000201C00007FFC0000401C0000801C0001801C0001001C0002001C00
02001C0004000E000C000E001C001E00FF00FFC01A1D7E9C1F>65
D<01FFFE00003C0780003803C0003801C0003801C0003801C0007001C0007003C0007003
C00070078000E0070000E00E0000E03C0000FFF80001C01C0001C00E0001C00F0001C00F
0003800F0003800F0003800F0003800F0007001E0007001C0007003C00070078000E01E0
00FFFF80001A1C7D9B1D>I<0003F020001E0C60003002E000E003C001C001C0038001C0
070000C00E0000801E0000801C0000803C0000803C000000780000007800000078000000
F0000000F0000000F0000000F0000000F0000400F0000400F0000400F000080070000800
7000100038002000180040000C0180000706000001F800001B1E7A9C1E>I<01FFFE0000
3C0780003801C0003801C0003800E0003800E0007000F00070007000700070007000F000
E000F000E000F000E000F000E000F001C001E001C001E001C001E001C001C0038003C003
800380038007800380070007000E0007001C0007003800070070000E01C000FFFF00001C
1C7D9B1F>I<01FFFFE0003C00E000380060003800400038004000380040007000400070
0040007020400070200000E0400000E0400000E0C00000FFC00001C0800001C0800001C0
800001C0800003810100038001000380020003800200070004000700040007000C000700
18000E007800FFFFF0001B1C7D9B1C>I<01FFFFC0003C01C0003800C000380080003800
80003800800070008000700080007020800070200000E0400000E0400000E0C00000FFC0
0001C0800001C0800001C0800001C0800003810000038000000380000003800000070000
000700000007000000070000000F000000FFF000001A1C7D9B1B>I<0003F020001E0C60
003002E000E003C001C001C0038001C0070000C00E0000801E0000801C0000803C000080
3C000000780000007800000078000000F0000000F0000000F001FFC0F0001E00F0001C00
F0001C00F0001C00F0001C00700038007000380038003800180078000C00900007071000
01F800001B1E7A9C20>I<01FFCFFE003C01E0003801C0003801C0003801C0003801C000
70038000700380007003800070038000E0070000E0070000E0070000FFFF0001C00E0001
C00E0001C00E0001C00E0003801C0003801C0003801C0003801C00070038000700380007
003800070038000F007800FFE7FF001F1C7D9B1F>I<01FFC0003C000038000038000038
0000380000700000700000700000700000E00000E00000E00000E00001C00001C00001C0
0001C0000380000380000380000380000700000700000700000700000F0000FFE000121C
7E9B10>I<007FF0000780000700000700000700000700000E00000E00000E00000E0000
1C00001C00001C00001C0000380000380000380000380000700000700000700000700060
E000E0E000C0C00081C0008380004700003C0000141D7B9B16>I<01FFC0FF003C003C00
3800300038004000380080003801000070020000700400007010000070200000E0400000
E0C00000E1C00000E5C00001C8E00001D0E00001E0E00001C07000038070000380700003
803800038038000700380007001C0007001C0007001C000F001E00FFE0FF80201C7D9B20
>I<01FFE0003C0000380000380000380000380000700000700000700000700000E00000
E00000E00000E00001C00001C00001C00001C00003800803800803800803801007001007
00300700600700E00E03C0FFFFC0151C7D9B1A>I<01FE0007F8003E000780002E000F00
002E001700002E001700002E002700004E002E00004E004E00004E004E00004E008E0000
8E011C00008E011C00008E021C00008E021C000107043800010704380001070838000107
1038000207107000020720700002072070000207407000040740E000040780E000040700
E0000C0700E0001C0601E000FF861FFC00251C7D9B25>I<01FC03FE001C0070003C0060
002E0040002E0040002E0040004700800047008000470080004380800083810000838100
008181000081C1000101C2000101C2000100E2000100E2000200E4000200740002007400
020074000400380004003800040038000C0018001C001000FF8010001F1C7D9B1F>I<01
FFFC00003C070000380380003801C0003801C0003801C0007003C0007003C0007003C000
70038000E0078000E0070000E00E0000E0380001FFE00001C0000001C0000001C0000003
800000038000000380000003800000070000000700000007000000070000000F000000FF
E000001A1C7D9B1C>80 D<01FFF800003C0E000038070000380380003803800038038000
700780007007800070078000700F0000E00E0000E01C0000E0700000FFC00001C0C00001
C0600001C0700001C07000038070000380700003807000038070000700F0000700F04007
00F0400700F0800F007880FFE0790000001E001A1D7D9B1E>82 D<000F8400304C00403C
00801801001803001803001806001006001006000007000007000003E00003FC0001FF00
007F800007C00001C00001C00000C00000C02000C02000C0600180600180600300600200
F00400CC180083E000161E7D9C17>I<1FFFFFC01C0701C0300E00C0200E0080600E0080
400E0080401C0080801C0080801C0080001C000000380000003800000038000000380000
0070000000700000007000000070000000E0000000E0000000E0000000E0000001C00000
01C0000001C0000001C0000003C000007FFE00001A1C799B1E>I<7FF0FF800F001C000E
0018000E0010000E0010000E0010001C0020001C0020001C0020001C0020003800400038
004000380040003800400070008000700080007000800070008000E0010000E0010000E0
010000E0020000E0020000E0040000E00400006008000030300000104000000F80000019
1D779B1F>I<FF803FC01C000F001C0004001C0008001C0008001C0010001C0010001C00
20001C0040001C0040001E0080000E0080000E0100000E0200000E0200000E0400000E04
00000E0800000E1800000E1000000E200000072000000740000007C00000078000000700
00000700000006000000060000001A1D779B1F>I<FF83FF0FF03C007001C03800700180
3800F001003800F0020038017002003801700400380270040038027008001C047008001C
047010001C087010001C087020001C107020001C107040001C207040001C207080001C40
7180001C407100001C807200001D807200001D007400001E007400001E007800001C0078
00001C00700000180070000018006000001000600000241D779B29>I<FFC00FE00E0007
800E0006000F000400070008000700180007801000038020000380400003C0800001C180
0001C1000001E2000000E4000000EC000000F80000007000000070000000E0000000E000
0000E0000000E0000001C0000001C0000001C0000001C00000038000003FF800001B1C78
9B1F>89 D<00FFFF8000F0070001C00E0001801E0001001C0001003800020070000200E0
000201C0000001C0000003800000070000000E0000001C0000001C000000380000007000
0000E0080001C0100001C0100003801000070020000E0020001C0060003C00C0003801C0
0070078000FFFF8000191C7D9B19>I<020006001B0031006080C0800906759C15>94
D<03CC063C0C3C181C3838303870387038E070E070E070E070E0E2C0E2C0E261E462643C
380F127B9115>97 D<3F00070007000E000E000E000E001C001C001C001C0039C03E6038
3038307038703870387038E070E070E070E060E0E0C0C0C1C0618063003C000D1D7B9C13
>I<01F007080C08181C3838300070007000E000E000E000E000E000E008E010602030C0
1F000E127B9113>I<001F80000380000380000700000700000700000700000E00000E00
000E00000E0003DC00063C000C3C00181C00383800303800703800703800E07000E07000
E07000E07000E0E200C0E200C0E20061E4006264003C3800111D7B9C15>I<01E007100C
1018083810701070607F80E000E000E000E000E000E0086010602030C01F000D127B9113
>I<0003C0000670000C70001C60001C00001C0000380000380000380000380000380003
FF8000700000700000700000700000700000E00000E00000E00000E00000E00001C00001
C00001C00001C00001C000038000038000038000030000030000070000C60000E60000CC
00007800001425819C0D>I<00F3018F030F06070E0E0C0E1C0E1C0E381C381C381C381C
383830383038187818F00F700070007000E000E0C0C0E1C0C3007E00101A7D9113>I<0F
C00001C00001C0000380000380000380000380000700000700000700000700000E78000E
8C000F0E000E0E001C0E001C0E001C0E001C0E00381C00381C00381C0038380070388070
3880707080707100E03200601C00111D7D9C15>I<018003800100000000000000000000
00000000001C002600470047008E008E000E001C001C001C003800380071007100710072
0072003C00091C7C9B0D>I<0FC00001C00001C000038000038000038000038000070000
0700000700000700000E0F000E11000E23800E43801C83001C80001D00001E00003F8000
39C00038E00038E00070E20070E20070E20070E400E06400603800111D7D9C13>107
D<1F800380038007000700070007000E000E000E000E001C001C001C001C003800380038
0038007000700070007000E400E400E400E40068003800091D7C9C0B>I<3C1E07802663
18C04683A0E04703C0E08E0380E08E0380E00E0380E00E0380E01C0701C01C0701C01C07
01C01C070380380E0388380E0388380E0708380E0710701C0320300C01C01D127C9122>
I<3C3C002646004687004707008E07008E07000E07000E07001C0E001C0E001C0E001C1C
00381C40381C40383840383880701900300E0012127C9117>I<01E007180C0C180C380C
300E700E700EE01CE01CE01CE018E038E030E06060C031801E000F127B9115>I<078700
04D98008E0C008E0C011C0E011C0E001C0E001C0E00381C00381C00381C0038180070380
0703000707000706000E8C000E70000E00000E00001C00001C00001C00001C00003C0000
FF8000131A7F9115>I<03C4062C0C3C181C3838303870387038E070E070E070E070E0E0
C0E0C0E061E063C03DC001C001C0038003800380038007803FF00E1A7B9113>I<3C3C26
C2468747078E068E000E000E001C001C001C001C0038003800380038007000300010127C
9112>I<01F006080C080C1C18181C001F001FC00FF007F0007800386030E030C0308060
60C01F000E127D9111>I<00C001C001C001C00380038003800380FFE00700070007000E
000E000E000E001C001C001C001C00384038403840388019000E000B1A7D990E>I<1E03
00270700470700470700870E00870E000E0E000E0E001C1C001C1C001C1C001C1C003838
803838801838801839001C5900078E0011127C9116>I<1E06270E470E4706870287020E
020E021C041C041C041C0818083808181018200C4007800F127C9113>I<1E0183270387
4703874703838707018707010E07010E07011C0E021C0E021C0E021C0E04180C04181C04
181C081C1C100C263007C3C018127C911C>I<070E0019910010E38020E38041C30041C0
0001C00001C000038000038000038000038000070200670200E70400CB04008B080070F0
0011127D9113>I<1E03270747074707870E870E0E0E0E0E1C1C1C1C1C1C1C1C38383838
183818381C7007F00070007000E0E0C0E1C0818047003C00101A7C9114>I<038207C20F
EC08381008001000200040008001000200040008081008383067F043E081C00F127D9111
>I E /Fo 18 90 df<FFFCFFFCFFFCFFFC0E047F8C13>45 D<0000700000000070000000
00F800000000F800000000F800000001FC00000001FC00000003FE00000003FE00000003
FE00000006FF000000067F0000000E7F8000000C3F8000000C3F800000183FC00000181F
C00000381FE00000300FE00000300FE00000600FF000006007F00000E007F80000FFFFF8
0000FFFFF800018001FC00018001FC00038001FE00030000FE00030000FE000600007F00
0600007F00FFE00FFFF8FFE00FFFF825227EA12A>65 D<0003FE0080001FFF818000FF01
E38001F8003F8003E0001F8007C0000F800F800007801F800007803F000003803F000003
807F000001807E000001807E00000180FE00000000FE00000000FE00000000FE00000000
FE00000000FE00000000FE00000000FE000000007E000000007E000001807F000001803F
000001803F000003801F800003000F8000030007C000060003F0000C0001F800380000FF
00F000001FFFC0000003FE000021227DA128>67 D<FFFFFFFCFFFFFFFC07F000FC07F000
3C07F0001C07F0000C07F0000E07F0000E07F0000607F0180607F0180607F0180607F018
0007F0380007F0780007FFF80007FFF80007F0780007F0380007F0180007F0180007F018
0307F0180307F0000307F0000607F0000607F0000607F0000E07F0000E07F0001E07F000
3E07F001FCFFFFFFFCFFFFFFFC20227EA125>69 D<FFFFFFF8FFFFFFF807F001F807F000
7807F0003807F0001807F0001C07F0001C07F0000C07F0000C07F0180C07F0180C07F018
0007F0180007F0380007F0780007FFF80007FFF80007F0780007F0380007F0180007F018
0007F0180007F0180007F0000007F0000007F0000007F0000007F0000007F0000007F000
0007F00000FFFFE000FFFFE0001E227EA123>I<0003FE0040001FFFC0C0007F00F1C001
F8003FC003F0000FC007C00007C00FC00003C01F800003C03F000001C03F000001C07F00
0000C07E000000C07E000000C0FE00000000FE00000000FE00000000FE00000000FE0000
0000FE00000000FE00000000FE000FFFFC7E000FFFFC7F00001FC07F00001FC03F00001F
C03F00001FC01F80001FC00FC0001FC007E0001FC003F0001FC001FC003FC0007F80E7C0
001FFFC3C00003FF00C026227DA12C>I<FFFF83FFFEFFFF83FFFE07F0001FC007F0001F
C007F0001FC007F0001FC007F0001FC007F0001FC007F0001FC007F0001FC007F0001FC0
07F0001FC007F0001FC007F0001FC007F0001FC007FFFFFFC007FFFFFFC007F0001FC007
F0001FC007F0001FC007F0001FC007F0001FC007F0001FC007F0001FC007F0001FC007F0
001FC007F0001FC007F0001FC007F0001FC007F0001FC007F0001FC007F0001FC0FFFF83
FFFEFFFF83FFFE27227EA12C>I<FFFFE0FFFFE003F80003F80003F80003F80003F80003
F80003F80003F80003F80003F80003F80003F80003F80003F80003F80003F80003F80003
F80003F80003F80003F80003F80003F80003F80003F80003F80003F80003F80003F80003
F800FFFFE0FFFFE013227FA115>I<FFFFE000FFFFE00007F0000007F0000007F0000007
F0000007F0000007F0000007F0000007F0000007F0000007F0000007F0000007F0000007
F0000007F0000007F0000007F0000007F0000007F0000007F0000007F0001807F0001807
F0001807F0001807F0003807F0003807F0007007F0007007F000F007F001F007F007F0FF
FFFFF0FFFFFFF01D227EA122>76 D<FFF000000FFFFFF800001FFF07F800001FE006FC00
0037E006FC000037E006FC000037E0067E000067E0067E000067E0063F0000C7E0063F00
00C7E0061F800187E0061F800187E0060FC00307E0060FC00307E0060FC00307E00607E0
0607E00607E00607E00603F00C07E00603F00C07E00601F81807E00601F81807E00601F8
1807E00600FC3007E00600FC3007E006007E6007E006007E6007E006003FC007E006003F
C007E006001F8007E006001F8007E006001F8007E006000F0007E0FFF00F00FFFFFFF006
00FFFF30227EA135>I<FFF8001FFEFFFC001FFE07FC0000C007FE0000C006FF0000C006
7F8000C0063FC000C0061FE000C0060FE000C0060FF000C00607F800C00603FC00C00601
FE00C00600FE00C00600FF00C006007F80C006003FC0C006001FE0C006000FF0C0060007
F0C0060007F8C0060003FCC0060001FEC0060000FFC00600007FC00600007FC00600003F
C00600001FC00600000FC006000007C006000003C006000003C0FFF00001C0FFF00000C0
27227EA12C>I<0007FC0000003FFF800000FC07E00003F001F80007E000FC000FC0007E
001F80003F001F80003F003F00001F803F00001F807F00001FC07E00000FC07E00000FC0
FE00000FE0FE00000FE0FE00000FE0FE00000FE0FE00000FE0FE00000FE0FE00000FE0FE
00000FE0FE00000FE07E00000FC07F00001FC07F00001FC03F00001F803F80003F801F80
003F000FC0007E0007E000FC0003F001F80000FC07E000003FFF80000007FC000023227D
A12A>I<FFFFFF00FFFFFFE007F007F007F001FC07F000FC07F0007E07F0007E07F0007F
07F0007F07F0007F07F0007F07F0007F07F0007E07F0007E07F000FC07F001FC07F007F0
07FFFFE007FFFF0007F0000007F0000007F0000007F0000007F0000007F0000007F00000
07F0000007F0000007F0000007F0000007F0000007F00000FFFF8000FFFF800020227EA1
26>I<FFFFFE0000FFFFFFC00007F007F00007F001F80007F000FC0007F0007E0007F000
7F0007F0007F0007F0007F0007F0007F0007F0007F0007F0007F0007F0007E0007F000FC
0007F001F80007F007F00007FFFFC00007FFFF800007F00FE00007F007F00007F003F800
07F001FC0007F001FC0007F001FC0007F001FC0007F001FC0007F001FC0007F001FC0007
F001FC0007F001FC0607F000FE0607F000FF0CFFFF803FF8FFFF800FF027227EA12A>82
D<01FC0407FF8C1F03FC3C007C7C003C78001C78001CF8000CF8000CFC000CFC0000FF00
00FFE0007FFF007FFFC03FFFF01FFFF80FFFFC03FFFE003FFE0003FF00007F00003F0000
3FC0001FC0001FC0001FE0001EE0001EF0003CFC003CFF00F8C7FFE080FF8018227DA11F
>I<7FFFFFFF807FFFFFFF807E03F80F807803F807807003F803806003F80180E003F801
C0E003F801C0C003F800C0C003F800C0C003F800C0C003F800C00003F800000003F80000
0003F800000003F800000003F800000003F800000003F800000003F800000003F8000000
03F800000003F800000003F800000003F800000003F800000003F800000003F800000003
F800000003F800000003F800000003F8000003FFFFF80003FFFFF80022227EA127>I<7F
FFC1FFF07FFFC1FFF003FC000C0001FE00180000FE00380000FF007000007F806000003F
80C000003FC1C000001FE38000000FE30000000FF700000007FE00000003FC00000003FC
00000001FE00000000FE00000000FF00000000FF80000001FFC0000001BFC00000031FE0
0000070FF000000E0FF000000C07F800001803FC00003803FC00003001FE00006000FF00
00E000FF0001C0007F800180003FC0FFFC03FFFEFFFC03FFFE27227FA12A>88
D<FFFF800FFEFFFF800FFE07F80000C007F80001C003FC00018001FE00030001FE000700
00FF00060000FF000C00007F801C00003FC01800003FC03000001FE07000000FF0600000
0FF0E0000007F8C0000003FD80000003FF80000001FF00000001FE00000000FE00000000
FE00000000FE00000000FE00000000FE00000000FE00000000FE00000000FE00000000FE
00000000FE00000000FE00000000FE0000001FFFF000001FFFF00027227FA12A>I
E /Fp 83 128 df<007E1F0001C1B1800303E3C00703C3C00E03C1800E01C0000E01C000
0E01C0000E01C0000E01C0000E01C000FFFFFC000E01C0000E01C0000E01C0000E01C000
0E01C0000E01C0000E01C0000E01C0000E01C0000E01C0000E01C0000E01C0000E01C000
0E01C0000E01C0000E01C0007F87FC001A1D809C18>11 D<007E0001C1800301800703C0
0E03C00E01800E00000E00000E00000E00000E0000FFFFC00E01C00E01C00E01C00E01C0
0E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C0
7F87F8151D809C17>I<007FC001C1C00303C00703C00E01C00E01C00E01C00E01C00E01
C00E01C00E01C0FFFFC00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01
C00E01C00E01C00E01C00E01C00E01C00E01C00E01C07FCFF8151D809C17>I<003F07E0
0001C09C18000380F018000701F03C000E01E03C000E00E018000E00E000000E00E00000
0E00E000000E00E000000E00E00000FFFFFFFC000E00E01C000E00E01C000E00E01C000E
00E01C000E00E01C000E00E01C000E00E01C000E00E01C000E00E01C000E00E01C000E00
E01C000E00E01C000E00E01C000E00E01C000E00E01C000E00E01C007FC7FCFF80211D80
9C23>I<E0E0F070380C0406077B9C15>18 D<1C1C3C3870C0800607779C15>I<6060F0F0
F8F86868080808080808101010102020404080800D0C7F9C15>34
D<60F0F8680808081010204080050C7C9C0C>39 D<004000800100020006000C000C0018
001800300030007000600060006000E000E000E000E000E000E000E000E000E000E000E0
00E000600060006000700030003000180018000C000C00060002000100008000400A2A7D
9E10>I<800040002000100018000C000C000600060003000300038001800180018001C0
01C001C001C001C001C001C001C001C001C001C001C00180018001800380030003000600
06000C000C00180010002000400080000A2A7E9E10>I<01800180018001804182F18F39
9C0FF003C003C00FF0399CF18F4182018001800180018010127E9E15>I<60F0F0701010
101020204080040C7C830C>44 D<FFE0FFE00B0280890E>I<60F0F06004047C830C>I<00
010003000600060006000C000C000C0018001800180030003000300060006000C000C000
C0018001800180030003000300060006000C000C000C0018001800180030003000300060
0060006000C000C00010297E9E15>I<03C00C301818300C300C700E60066006E007E007
E007E007E007E007E007E007E007E007E007E007E00760066006700E300C300C18180C30
07E0101D7E9B15>I<030007003F00C70007000700070007000700070007000700070007
000700070007000700070007000700070007000700070007000F80FFF80D1C7C9B15>I<
07C01830201C400C400EF00FF80FF807F8077007000F000E000E001C001C003800700060
00C00180030006010C01180110023FFE7FFEFFFE101C7E9B15>I<07E01830201C201C78
1E780E781E381E001C001C00180030006007E00030001C001C000E000F000F700FF80FF8
0FF80FF00E401C201C183007E0101D7E9B15>I<000C00000C00001C00003C00003C0000
5C0000DC00009C00011C00031C00021C00041C000C1C00081C00101C00301C00201C0040
1C00C01C00FFFFC0001C00001C00001C00001C00001C00001C00001C0001FFC0121C7F9B
15>I<300C3FF83FF03FC020002000200020002000200023E024302818301C200E000E00
0F000F000F600FF00FF00FF00F800E401E401C2038187007C0101D7E9B15>I<00F0030C
06040C0E181E301E300C700070006000E3E0E430E818F00CF00EE006E007E007E007E007
E007600760077006300E300C18180C3003E0101D7E9B15>I<4000007FFF807FFF007FFF
0040020080040080040080080000100000100000200000600000400000C00000C00001C0
000180000180000380000380000380000380000780000780000780000780000780000780
00030000111D7E9B15>I<03E00C301008200C20066006600660067006780C3E083FB01F
E007F007F818FC307E601E600FC007C003C003C003C00360026004300C1C1007E0101D7E
9B15>I<03C00C301818300C700C600EE006E006E007E007E007E007E0076007700F300F
18170C2707C700060006000E300C780C78187010203030C00F80101D7E9B15>I<60F0F0
600000000000000000000060F0F06004127C910C>I<60F0F06000000000000000000000
60F0F0701010101020204080041A7C910C>I<7FFFFFC0FFFFFFE0000000000000000000
0000000000000000000000000000000000000000000000FFFFFFE07FFFFFC01B0C7E8F20
>61 D<0FE03038401CE00EF00EF00EF00E000C001C0030006000C0008001800100010001
000100010001000000000000000000000003000780078003000F1D7E9C14>63
D<000600000006000000060000000F0000000F0000000F00000017800000178000001780
000023C0000023C0000023C0000041E0000041E0000041E0000080F0000080F0000180F8
000100780001FFF80003007C0002003C0002003C0006003E0004001E0004001E000C001F
001E001F00FF80FFF01C1D7F9C1F>65 D<FFFFC00F00F00F00380F003C0F001C0F001E0F
001E0F001E0F001E0F001C0F003C0F00780F01F00FFFE00F00780F003C0F001E0F000E0F
000F0F000F0F000F0F000F0F000F0F001E0F001E0F003C0F0078FFFFE0181C7E9B1D>I<
001F808000E0618001801980070007800E0003801C0003801C0001803800018078000080
7800008070000080F0000000F0000000F0000000F0000000F0000000F0000000F0000000
F0000000700000807800008078000080380000801C0001001C0001000E00020007000400
0180080000E03000001FC000191E7E9C1E>I<FFFFC0000F00F0000F003C000F000E000F
0007000F0007000F0003800F0003C00F0001C00F0001C00F0001E00F0001E00F0001E00F
0001E00F0001E00F0001E00F0001E00F0001E00F0001C00F0001C00F0003C00F0003800F
0007800F0007000F000E000F001C000F007000FFFFC0001B1C7E9B20>I<FFFFFC0F003C
0F000C0F00040F00040F00060F00020F00020F02020F02000F02000F02000F06000FFE00
0F06000F02000F02000F02000F02010F00010F00020F00020F00020F00060F00060F000C
0F003CFFFFFC181C7E9B1C>I<FFFFF80F00780F00180F00080F00080F000C0F00040F00
040F02040F02000F02000F02000F06000FFE000F06000F02000F02000F02000F02000F00
000F00000F00000F00000F00000F00000F00000F8000FFF800161C7E9B1B>I<001F8080
00E0618001801980070007800E0003801C0003801C000180380001807800008078000080
70000080F0000000F0000000F0000000F0000000F0000000F0000000F000FFF0F0000F80
700007807800078078000780380007801C0007801C0007800E00078007000B8001801180
00E06080001F80001C1E7E9C21>I<FFF3FFC00F003C000F003C000F003C000F003C000F
003C000F003C000F003C000F003C000F003C000F003C000F003C000F003C000FFFFC000F
003C000F003C000F003C000F003C000F003C000F003C000F003C000F003C000F003C000F
003C000F003C000F003C000F003C00FFF3FFC01A1C7E9B1F>I<FFF00F000F000F000F00
0F000F000F000F000F000F000F000F000F000F000F000F000F000F000F000F000F000F00
0F000F000F000F00FFF00C1C7F9B0F>I<1FFF00F8007800780078007800780078007800
78007800780078007800780078007800780078007800787078F878F878F878F0F040E021
C01F00101D7F9B15>I<FFF03FE00F000F000F000C000F0008000F0010000F0020000F00
40000F0080000F0100000F0200000F0400000F0E00000F1F00000F2F00000F2780000F47
80000F83C0000F01E0000F01E0000F00F0000F00F8000F0078000F003C000F003C000F00
1E000F001F000F001F80FFF07FF01C1C7E9B20>I<FFF8000F80000F00000F00000F0000
0F00000F00000F00000F00000F00000F00000F00000F00000F00000F00000F00000F0000
0F00000F00080F00080F00080F00180F00180F00100F00300F00700F01F0FFFFF0151C7E
9B1A>I<FF8000FF800F8000F8000F8000F8000BC00178000BC00178000BC001780009E0
02780009E002780008F004780008F004780008F004780008780878000878087800087808
7800083C107800083C107800083C107800081E207800081E207800081E207800080F4078
00080F40780008078078000807807800080780780008030078001C03007800FF8307FF80
211C7E9B26>I<FF007FC00F800E000F8004000BC0040009E0040009E0040008F0040008
F8040008780400083C0400083C0400081E0400080F0400080F0400080784000807C40008
03C4000801E4000801E4000800F40008007C0008007C0008003C0008003C0008001C0008
000C001C000C00FF8004001A1C7E9B1F>I<003F800000E0E0000380380007001C000E00
0E001C0007003C00078038000380780003C0780003C0700001C0F00001E0F00001E0F000
01E0F00001E0F00001E0F00001E0F00001E0F00001E0700001C0780003C0780003C03800
03803C0007801C0007000E000E0007001C000380380000E0E000003F80001B1E7E9C20>
I<FFFF800F00E00F00780F003C0F001C0F001E0F001E0F001E0F001E0F001E0F001C0F00
3C0F00780F00E00FFF800F00000F00000F00000F00000F00000F00000F00000F00000F00
000F00000F00000F0000FFF000171C7E9B1C>I<003F800000E0E0000380380007001C00
0E000E001C0007003C00078038000380780003C0780003C0700001C0F00001E0F00001E0
F00001E0F00001E0F00001E0F00001E0F00001E0F00001E0700001C0780003C0780003C0
380003803C0E07801C1107000E208E0007205C0003A0780000F0E020003FE02000006020
00003060000038E000003FC000003FC000001F8000000F001B257E9C20>I<FFFF00000F
01E0000F0078000F003C000F001C000F001E000F001E000F001E000F001E000F001C000F
003C000F0078000F01E0000FFF00000F03C0000F00E0000F00F0000F0078000F0078000F
0078000F0078000F0078000F0078000F0078100F0078100F0038100F003C20FFF01C2000
0007C01C1D7E9B1F>I<07E0801C1980300580700380600180E00180E00080E00080E000
80F00000F800007C00007FC0003FF8001FFE0007FF0000FF80000F800007C00003C00001
C08001C08001C08001C0C00180C00180E00300D00200CC0C0083F800121E7E9C17>I<7F
FFFFC0700F01C0600F00C0400F0040400F0040C00F0020800F0020800F0020800F002000
0F0000000F0000000F0000000F0000000F0000000F0000000F0000000F0000000F000000
0F0000000F0000000F0000000F0000000F0000000F0000000F0000000F0000001F800003
FFFC001B1C7F9B1E>I<FFF07FC00F000E000F0004000F0004000F0004000F0004000F00
04000F0004000F0004000F0004000F0004000F0004000F0004000F0004000F0004000F00
04000F0004000F0004000F0004000F0004000F0004000F00040007000800078008000380
10000180100000C020000070C000001F00001A1D7E9B1F>I<FFE00FF01F0003C00F0001
800F0001000F800300078002000780020003C0040003C0040003C0040001E0080001E008
0001F0080000F0100000F0100000F830000078200000782000003C4000003C4000003C40
00001E8000001E8000001F8000000F0000000F00000006000000060000000600001C1D7F
9B1F>I<FFE0FFE0FF1F001F003C1E001E00180F001F00100F001F00100F001F00100780
1F00200780278020078027802003C027804003C043C04003C043C04003E043C04001E081
E08001E081E08001E081E08000F100F10000F100F10000F100F100007900FA00007A007A
00007A007A00003E007C00003C003C00003C003C00003C003C0000180018000018001800
0018001800281D7F9B2B>I<FFF007FC0F8001E00780008007C0018003C0010003E00200
01F0020000F0040000F8040000780800007C1800003C1000001E2000001F2000000F4000
000FC0000007800000078000000780000007800000078000000780000007800000078000
000780000007800000078000007FF8001E1C809B1F>89 D<7FFFF07C01F07001E06003C0
6003C0400780400F80400F00401E00001E00003C00007C0000780000F00000F00001E000
03E00003C0100780100780100F00101F00301E00203C00203C00607800E0F803E0FFFFE0
141C7E9B19>I<08081010202040404040808080808080B0B0F8F8787830300D0C7A9C15>
92 D<1FC000307000783800781C00301C00001C00001C0001FC000F1C00381C00701C00
601C00E01C40E01C40E01C40603C40304E801F870012127E9115>97
D<FC00001C00001C00001C00001C00001C00001C00001C00001C00001C00001C00001C7C
001D86001E03001C01801C01C01C00C01C00E01C00E01C00E01C00E01C00E01C00E01C00
C01C01C01C01801E030019060010F800131D7F9C17>I<07E00C301878307870306000E0
00E000E000E000E000E00060007004300418080C3007C00E127E9112>I<003F00000700
00070000070000070000070000070000070000070000070000070003E7000C1700180F00
300700700700600700E00700E00700E00700E00700E00700E00700600700700700300700
180F000C370007C7E0131D7E9C17>I<03E00C301818300C700E6006E006FFFEE000E000
E000E00060007002300218040C1803E00F127F9112>I<00F8018C071E061E0E0C0E000E
000E000E000E000E00FFE00E000E000E000E000E000E000E000E000E000E000E000E000E
000E000E000E007FE00F1D809C0D>I<00038003C4C00C38C01C3880181800381C00381C
00381C00381C001818001C38000C300013C0001000003000001800001FF8001FFF001FFF
803003806001C0C000C0C000C0C000C06001803003001C0E0007F800121C7F9215>I<FC
00001C00001C00001C00001C00001C00001C00001C00001C00001C00001C00001C7C001C
87001D03001E03801C03801C03801C03801C03801C03801C03801C03801C03801C03801C
03801C03801C03801C0380FF9FF0141D7F9C17>I<18003C003C00180000000000000000
00000000000000FC001C001C001C001C001C001C001C001C001C001C001C001C001C001C
001C001C00FF80091D7F9C0C>I<00C001E001E000C00000000000000000000000000000
0FE000E000E000E000E000E000E000E000E000E000E000E000E000E000E000E000E000E0
00E000E000E060E0F0C0F1C061803E000B25839C0D>I<FC00001C00001C00001C00001C
00001C00001C00001C00001C00001C00001C00001C3FC01C0F001C0C001C08001C10001C
20001C40001CE0001DE0001E70001C78001C38001C3C001C1C001C0E001C0F001C0F80FF
9FE0131D7F9C16>I<FC001C001C001C001C001C001C001C001C001C001C001C001C001C
001C001C001C001C001C001C001C001C001C001C001C001C001C001C00FF80091D7F9C0C
>I<FC7E07E0001C838838001D019018001E01E01C001C01C01C001C01C01C001C01C01C
001C01C01C001C01C01C001C01C01C001C01C01C001C01C01C001C01C01C001C01C01C00
1C01C01C001C01C01C001C01C01C00FF8FF8FF8021127F9124>I<FC7C001C87001D0300
1E03801C03801C03801C03801C03801C03801C03801C03801C03801C03801C03801C0380
1C03801C0380FF9FF014127F9117>I<03F0000E1C00180600300300700380600180E001
C0E001C0E001C0E001C0E001C0E001C06001807003803003001806000E1C0003F0001212
7F9115>I<FC7C001D86001E03001C01801C01C01C00C01C00E01C00E01C00E01C00E01C
00E01C00E01C01C01C01C01C01801E03001D06001CF8001C00001C00001C00001C00001C
00001C00001C0000FF8000131A7F9117>I<03C1000C3300180B00300F00700700700700
E00700E00700E00700E00700E00700E00700600700700700300F00180F000C370007C700
000700000700000700000700000700000700000700003FE0131A7E9116>I<FCE01D301E
781E781C301C001C001C001C001C001C001C001C001C001C001C001C00FFC00D127F9110
>I<1F9030704030C010C010E010F8007F803FE00FF000F880388018C018C018E010D060
8FC00D127F9110>I<04000400040004000C000C001C003C00FFE01C001C001C001C001C
001C001C001C001C001C101C101C101C101C100C100E2003C00C1A7F9910>I<FC1F801C
03801C03801C03801C03801C03801C03801C03801C03801C03801C03801C03801C03801C
03801C07800C07800E1B8003E3F014127F9117>I<FF07E03C03801C01001C01000E0200
0E020007040007040007040003880003880003D80001D00001D00000E00000E00000E000
00400013127F9116>I<FF3FCFE03C0F03801C0701801C0701001C0B01000E0B82000E0B
82000E1182000711C4000711C4000720C40003A0E80003A0E80003C0680001C0700001C0
700001803000008020001B127F911E>I<7F8FF00F03800F030007020003840001C80001
D80000F00000700000780000F800009C00010E00020E000607000403801E07C0FF0FF815
12809116>I<FF07E03C03801C01001C01000E02000E0200070400070400070400038800
03880003D80001D00001D00000E00000E00000E000004000004000008000008000F08000
F10000F300006600003C0000131A7F9116>I<7FFC70386038407040F040E041C003C003
8007000F040E041C043C0C380870087038FFF80E127F9112>I<FFFFF01401808B15>I<60
60F0F0F0F060600C047C9C15>127 D E end
%%EndProlog
%%BeginSetup
%%Feature: *Resolution 300dpi
TeXDict begin

%%EndSetup
%%Page: 1 1
1 0 bop 1929 50 a Fp(1)52 195 y Fo(A)19 b(T)-5 b(AX)n(ONOMY)20
b(OF)f(P)-5 b(ARALLEL)19 b(GAME-TREE)f(SEAR)n(CH)h(ALGORITHMS)766
274 y Fn(Mark)c(G.)g(Br)n(o)n(ckington)1165 259 y Fm(1)799
353 y Fp(Edmon)o(ton,)d(Alb)q(erta)0 496 y Fl(1)48 b(INTR)o(ODUCTION)0
617 y Fp(In)14 b(the)h(last)f(t)o(w)o(en)o(t)o(y)h(y)o(ears,)f(a)g(n)o
(um)o(b)q(er)g(of)g(articles)g(and)h(theses)h(ha)o(v)o(e)e(b)q(een)h
(written)g(that)f(con)o(tain)g(inno)o(v)n(ativ)o(e)f(parallel)0
666 y(game-tree)i(searc)o(h)i(algorithms.)k(The)c(authors)f(of)f(the)h
(parallel)f(algorithms)e(ha)o(v)o(e)j(sho)o(wn)f(ho)o(w)h(their)g(w)o
(ork)f(is)h(unique)0 716 y(and)11 b(in)o(teresting.)18
b(In)11 b(some)f(cases,)j(this)e(has)h(b)q(een)g(sho)o(wn)f(b)o(y)g
(classifying)g(other)g(algorithms)e(b)o(y)i(listing)f(implemen)o
(tation)0 766 y(details)h(\(Bal)g(and)g(v)n(an)f(Renesse,)j(1986;)d
(Ciancarini,)g(1994\).)17 b(T)m(o)10 b(the)i(author's)f(kno)o(wledge,)g
(no)f(attempt)h(has)g(b)q(een)h(made)0 816 y(to)j(classify)g(the)h
(algorithms)d(based)j(solely)e(on)h(their)h(algorithmic)d(prop)q
(erties.)23 b(A)15 b(taxonom)o(y)e(w)o(ould)i(mak)o(e)f(it)g(easy)i(to)
0 866 y(ascertain)i(what)e(has)h(and)g(has)g(not)g(b)q(een)g
(accomplished)f(in)h(parallel)e(game-tree)i(searc)o(h.)28
b(The)17 b(presen)o(tation)h(of)e(this)0 916 y(t)o(yp)q(e)e(of)g
(taxonom)o(y)d(is)j(the)g(main)e(con)o(tribution)i(of)f(this)h(pap)q
(er.)0 994 y(The)19 b(taxonom)o(y)c(will)i(b)q(e)i(brok)o(en)f(in)o(to)
g(t)o(w)o(o)f(ma)r(jor)g(categories:)27 b Fk(\013\014)r
Fp(-based)19 b(algorithms,)e(and)h(algorithms)d(based)k(on)0
1044 y(other)c(searc)o(h)h(paradigms)d(\()p Fk(S)r(S)r(S)r
Fj(\003)p Fp(,)j Fk(E)r(R)p Fp(,)e(and)h(theoretical)g(metho)q(ds\).)20
b(F)m(or)14 b(the)h(former)f(category)m(,)g(a)g(table)h(is)f(giv)o(en)g
(to)0 1094 y(isolate)i(the)h(fundamen)o(tal)e(di\013erences)j(b)q(et)o
(w)o(een)g(the)g(algorithms.)23 b(The)17 b(table)g(is)f(divided)g(in)o
(to)g(t)o(w)o(o)g(parts:)24 b(the)17 b(\014rst)0 1144
y(part)g(con)o(tains)g(c)o(haracteristics)i(of)e(the)h
Fk(\013\014)r Fp(-based)g(algorithms,)d(while)i(the)g(second)i(part)e
(con)o(tains)g(details)g(ab)q(out)g(an)0 1194 y(implemen)o(tatio)o(n)9
b(of)i(eac)o(h)i(algorithm.)h(Section)f(2)e(describ)q(es)j(the)f(v)n
(arious)e(columns)f(giv)o(en)i(in)f(the)h(table,)g(and)g(then)g(giv)o
(es)0 1243 y(some)h(brief)h(details)g(on)f(the)i(algorithms)c(con)o
(tained)j(therein.)0 1322 y(The)j(algorithms)e(based)i(on)g(other)g
(searc)o(h)h(paradigms)d(are)j(giv)o(en)e(in)g(Section)h(3.)27
b(Due)17 b(to)g(the)g(v)n(aried)g(nature)g(of)f(the)0
1372 y(metho)q(ds,)c(a)h(brief)g(description)h(is)f(giv)o(en)f(for)h
(eac)o(h)h(of)e(the)i(algorithms)d(and)i(no)f(attempt)h(has)g(b)q(een)h
(made)e(to)h(categorize)0 1422 y(them)h(to)g(the)h(same)f(exten)o(t)h
(as)g(the)g Fk(\013\014)r Fp(-based)h(algorithms.)h(The)e(implemen)o
(tation)c(details)j(ha)o(v)o(e)h(not)f(b)q(een)i(organized)0
1472 y(in)o(to)e(a)g(table,)g(since)h(some)e(of)h(the)h(algorithms)d
(giv)o(en)i(are)h(of)f(a)g(theoretical)h(nature)g(and)f(ha)o(v)o(e)g
(not)h(b)q(een)g(implemen)o(ted)0 1522 y(or)f(sim)o(ulated.)0
1600 y(The)g(\014nal)g(section)g(deals)g(with)g(some)f(conclusions)h
(that)g(can)g(b)q(e)h(dra)o(wn)e(from)f(the)j(taxonom)o(y)m(.)0
1744 y Fl(2)48 b Fk(\013\014)r Fl(-BASED)15 b(P)l(ARALLEL)g(GAME-TREE)i
(SEAR)o(CH)0 1864 y Fp(This)e(section)h(discusses)h(algorithms)c(based)
i(on)g Fk(\013\014)j Fp(and)d(will)e(b)q(e)j(split)f(in)o(to)f(four)h
(subsections.)23 b(Sections)16 b(2.1)e(and)h(2.2)0 1914
y(will)e(b)q(e)i(used)h(to)e(describ)q(e)j(the)e(columns)e(in)h(T)m
(ables)g(1)h(and)f(2,)g(resp)q(ectiv)o(ely)m(.)21 b(The)15
b(description)g(of)f(the)i(algorithms)c(has)0 1964 y(b)q(een)i(divided)
e(in)o(to)g(t)o(w)o(o)g(eras.)18 b(Section)13 b(2.3)f(co)o(v)o(ers)h(w)
o(ork)f(\014rst)i(submitted)e(up)g(to)h(June,)g(1987.)j(Most)d(of)f
(the)h(w)o(ork)g(from)0 2014 y(this)k(era)g(describ)q(es)i(algorithms)c
(to)h(b)q(e)i(used)f(on)g(a)g(limited)d(n)o(um)o(b)q(er)i(of)h(pro)q
(cessors.)29 b(Section)17 b(2.4)f(co)o(v)o(ers)h(w)o(ork)g(that)0
2064 y(w)o(as)f(\014rst)i(submitted)e(on)g(or)g(after)h(July)m(,)f
(1987.)25 b(The)17 b(ma)r(jorit)o(y)d(of)i(the)i(algorithms)c(from)h
(this)h(era)h(are)g(designed)g(for)0 2113 y(implemen)o(tatio)o(n)12
b(on)j(massiv)o(ely-parallel)c(hardw)o(are)k(systems,)g(whic)o(h)f(w)o
(ere)i(una)o(v)n(ailable)d(to)h(most)g(researc)o(hers)j(b)q(efore)0
2163 y(1987.)0 2302 y Fl(2.1)48 b(Comparison)14 b(of)h(the)g
Fk(\013\014)j Fl(Algorithms)0 2408 y Fp(T)m(able)13 b(1)h(summarizes)e
(and)i(classi\014es)g(the)h(v)n(arious)e Fk(\013\014)r
Fp(-based)i(algorithms,)c(and)j(is)f(divided)h(in)o(to)f(\014v)o(e)h
(columns.)0 2487 y(The)j(\014rst)g(column)d(giv)o(es)j(the)f(name)g(of)
f(the)i(algorithm,)d(and)i(the)h(reference)h(that)f(con)o(tains)f(the)h
(most)e(details)h(ab)q(out)0 2537 y(the)f(algorithm.)k(F)m(or)14
b(example,)g(the)h(Y)m(oung)f(Brothers)j(W)m(ait)c(concept)j(has)f(b)q
(een)h(describ)q(ed)h(in)d(man)o(y)f(pap)q(ers,)j(but)f(all)0
2587 y(of)e(the)i(algorithm's)c(details)j(are)g(lo)q(cated)g(in)f(F)m
(eldmann's)f(thesis)j(\(1993\).)p 0 2626 780 2 v 46 2652
a Fi(1)64 2664 y Fh(Departmen)o(t)8 b(of)j(Computing)e(Science,)h(Univ)
o(ersit)o(y)g(of)h(Alb)q(erta,)f(Edmon)o(ton,)f(Alb)q(erta,)h(Canada,)g
(T6G)i(2H1.)0 2704 y(Email:)i Fg([email protected])o(lb)o(ert)o(a.c)o(a)p
eop
%%Page: 2 2
2 1 bop 0 50 a Fp(2)603 b(ICCA)14 b(Journal)f(Submission)601
b(June)15 b(12,)e(1996)p 56 488 1827 2 v 56 498 V 55
538 2 40 v 317 526 a Fh(Algorithm)p 735 538 V 283 w(Date)e(First)p
944 538 V 70 w(Pro)q(cessor)p 1182 538 V 1182 538 V 133
w(P)o(arallelism)p 1532 538 V 1532 538 V 138 w(Sync)o(hroniza)o(tion)p
1882 538 V 55 577 V 308 565 a(\(Reference\))p 735 577
V 278 w(Describ)q(ed)p 944 577 V 62 w(Hierarc)o(h)o(y/)p
1182 577 V 1182 577 V 121 w(P)o(ossible)f(A)o(t)p 1532
577 V 1532 577 V 146 w(Done)h(A)o(t)h(These)p 1882 577
V 55 616 V 735 616 V 944 616 V 1006 605 a(Con)o(trol)p
1182 616 V 1182 616 V 136 w(These)f(No)q(des)p 1532 616
V 1532 616 V 204 w(No)q(des)p 1882 616 V 55 656 V 735
656 V 944 656 V 970 644 a(Distribution)p 1182 656 V 1532
656 V 1882 656 V 56 658 1827 2 v 56 668 V 55 707 2 40
v 81 695 a(P)o(arallel)e(Aspiration)h(Searc)o(h)p 735
707 V 319 w(1978)p 944 707 V 133 w(Static/)p 1182 707
V 88 w(Ro)q(ot)h(\()p Ff(\013\014)h Fh(windo)o(w\))p
1532 707 V 62 w(Ro)q(ot)p 1882 707 V 55 746 V 81 735
a(\(Baudet,)d(1978\))p 735 746 V 944 746 V 663 w(Cen)o(tralized)p
1182 746 V 1532 746 V 1882 746 V 56 748 1827 2 v 55 787
2 40 v 81 776 a(Mandatory)g(W)m(ork)i(First)p 735 787
V 372 w(1979)p 944 787 V 133 w(Static/)p 1182 787 V 88
w(T)o(yp)q(e)g(1+3+Left-)p 1532 787 V 94 w(Bad)g(T)o(yp)q(e)g(2)p
1882 787 V 55 827 V 81 815 a(\(Akl,)g(Barnard)e(and)i(Doran,)f(1982\))p
735 827 V 944 827 V 395 w(Cen)o(tralized)p 1182 827 V
54 w(most)g(c)o(hild)h(of)g(3)p 1532 827 V 1882 827 V
56 829 1827 2 v 55 868 2 40 v 81 856 a(T)m(ree)g(Splitting)p
735 868 V 509 w(1980)p 944 868 V 133 w(Static/)p 1182
868 V 88 w(T)m(op)g(k-ply)p 1532 868 V 199 w(Ro)q(ot)p
1882 868 V 55 907 V 81 896 a(\(Fink)o(el)f(and)g(Fish)o(burn,)g(1982\))
p 735 907 V 944 907 V 460 w(Cen)o(tralized)p 1182 907
V 1532 907 V 1882 907 V 56 909 1827 2 v 55 949 2 40 v
81 937 a(PV-Split)p 735 949 V 588 w(1981)p 944 949 V
133 w(Static/)p 1182 949 V 88 w(T)o(yp)q(e)h(1)p 1532
949 V 241 w(T)o(yp)q(e)g(1)p 1882 949 V 55 988 V 81 976
a(\(Marsland)e(and)i(Campb)q(ell,)e(1982\))p 735 988
V 944 988 V 402 w(Cen)o(tralized)p 1182 988 V 1532 988
V 1882 988 V 56 990 1827 2 v 55 1029 2 40 v 81 1017 a(Key)i(No)q(de)p
735 1029 V 570 w(1983)p 944 1029 V 133 w(Static/)p 1182
1029 V 88 w(T)o(yp)q(e)g(1+3+Left-)p 1532 1029 V 94 w(Bad)g(T)o(yp)q(e)
g(2)p 1882 1029 V 55 1069 V 81 1057 a(\(Lindstrom,)d(1983\))p
735 1069 V 944 1069 V 615 w(Cen)o(tralized)p 1182 1069
V 54 w(most)i(c)o(hild)h(of)g(3)p 1532 1069 V 1882 1069
V 56 1070 1827 2 v 55 1110 2 40 v 81 1098 a(UIDP)m(ABS)p
735 1110 V 566 w(1986)p 944 1110 V 133 w(Static/)p 1182
1110 V 88 w(Ro)q(ot)p 1532 1110 V 273 w(None)p 1882 1110
V 55 1149 V 81 1137 a(\(Newb)q(orn,)f(1988\))p 735 1149
V 944 1149 V 635 w(Cen)o(tralized)p 1182 1149 V 1532
1149 V 1882 1149 V 56 1151 1827 2 v 55 1190 2 40 v 81
1178 a(DPVS)p 735 1190 V 601 w(01/1987)p 944 1190 V 81
w(Dynamic/)p 1182 1190 V 64 w(T)o(yp)q(e)h(1+3+2)p 1532
1190 V 151 w(T)o(yp)q(e)g(1+3+Bad)g(2)p 1882 1190 V 55
1230 V 81 1218 a(\(Sc)o(hae\013er,)d(1989\))p 735 1230
V 944 1230 V 637 w(Cen)o(tralized)p 1182 1230 V 1532
1230 V 1882 1230 V 56 1231 1827 2 v 55 1271 2 40 v 81
1259 a(EPVS)p 735 1271 V 604 w(06/1987)p 944 1271 V 81
w(Dynamic/)p 1182 1271 V 64 w(T)o(yp)q(e)j(1+3)p 1532
1271 V 196 w(T)o(yp)q(e)g(1+3)p 1882 1271 V 55 1310 V
81 1298 a(\(Hy)o(att,)f(Suter)g(and)h(Nelson,)f(1989\))p
735 1310 V 944 1310 V 398 w(Cen)o(tralized)p 1182 1310
V 1532 1310 V 1882 1310 V 56 1312 1827 2 v 55 1351 2
40 v 81 1339 a(W)m(a)o(yco)q(ol)p 735 1351 V 592 w(1987)p
944 1351 V 109 w(Dynamic/)p 1182 1351 V 64 w(All,)h(except)f(T)o(yp)q
(e)h(2)p 1532 1351 V 63 w(No)q(des)g(with)g(TT)p 1882
1351 V 55 1391 V 81 1379 a(\(F)m(elten)f(and)g(Otto,)h(1988\))p
735 1391 V 944 1391 V 527 w(Distributed)p 1182 1391 V
53 w(with)g(no)g(TT)i(en)o(try)p 1532 1391 V 76 w(&)f(no)f(cuto\013)p
1882 1391 V 56 1392 1827 2 v 55 1432 2 40 v 81 1420 a(Y)m(oung)f
(Brothers)g(W)m(ait)p 735 1432 V 369 w(10/1987)p 944
1432 V 81 w(Dynamic/)p 1182 1432 V 64 w(T)o(yp)q(e)h(1+3+Bad)g(2)p
1532 1432 V 77 w(T)o(yp)q(e)g(1+Bad)g(2)p 1882 1432 V
55 1471 V 81 1459 a(\(F)m(eldmann,)d(1993\))p 735 1471
V 944 1471 V 623 w(Distributed)p 1182 1471 V 1532 1471
V 1882 1471 V 56 1473 1827 2 v 55 1512 2 40 v 81 1500
a(Dynamic)h(T)m(ree)i(Splitting)p 735 1512 V 360 w(1988)p
944 1512 V 109 w(Dynamic/)p 1182 1512 V 64 w(T)o(yp)q(e)g(1+3+Bad)g(2)p
1532 1512 V 77 w(T)o(yp)q(e)g(1+Bad)g(2)p 1882 1512 V
55 1552 V 81 1540 a(\(Hy)o(att,)f(1988\))p 735 1552 V
944 1552 V 685 w(Distributed)p 1182 1552 V 1532 1552
V 1882 1552 V 56 1553 1827 2 v 55 1593 2 40 v 81 1581
a(Bound-and-)o(Bran)o(c)o(h)p 735 1593 V 403 w(08/1988)p
944 1593 V 81 w(Dynamic/)p 1182 1593 V 64 w(T)o(yp)q(e)h(1+3+Bad)g(2)p
1532 1593 V 77 w(T)o(yp)q(e)g(1+Bad)g(2)p 1882 1593 V
55 1632 V 81 1620 a(\(F)m(erguson)e(and)i(Korf,)g(1988\))p
735 1632 V 944 1632 V 486 w(Distributed)p 1182 1632 V
1532 1632 V 1882 1632 V 56 1634 1827 2 v 55 1673 2 40
v 81 1661 a(Dela)o(y)o(ed)e(Branc)o(h)h(T)m(ree)i(Expansion)p
735 1673 V 226 w(1990)p 944 1673 V 133 w(Static/)p 1182
1673 V 88 w(T)o(yp)q(e)f(1+3)p 1532 1673 V 196 w(Bad)g(T)o(yp)q(e)g(2)p
1882 1673 V 55 1713 V 81 1701 a(\(Hsu,)g(1990\))p 735
1713 V 944 1713 V 714 w(Cen)o(tralized)p 1182 1713 V
1532 1713 V 1882 1713 V 56 1714 1827 2 v 55 1754 2 40
v 81 1742 a(F)m(ron)o(tier)e(Splitting)p 735 1754 V 454
w(1993)p 944 1754 V 109 w(Dynamic/)p 1182 1754 V 64 w(All)p
1532 1754 V 304 w(Ro)q(ot)p 1882 1754 V 55 1793 V 81
1781 a(\(Lu,)h(1993\))p 735 1793 V 944 1793 V 733 w(Distributed)p
1182 1793 V 1532 1793 V 1882 1793 V 56 1795 1827 2 v
55 1834 2 40 v 81 1823 a Ff(\013\014)r Fh(*)p 735 1834
V 661 w(1993)p 944 1834 V 109 w(Dynamic/)p 1182 1834
V 64 w(T)o(yp)q(e)h(1+3)p 1532 1834 V 196 w(T)o(yp)q(e)g(1+3+Bad)g(2)p
1882 1834 V 55 1874 V 81 1862 a(\(Da)o(vid,)e(1993\))p
735 1874 V 944 1874 V 683 w(Distributed)p 1182 1874 V
1532 1874 V 1882 1874 V 56 1875 1827 2 v 55 1915 2 40
v 81 1903 a(CABP)p 735 1915 V 624 w(1994)p 944 1915 V
133 w(Static/)p 1182 1915 V 88 w(T)o(yp)q(e)i(1+3)p 1532
1915 V 196 w(Bad)g(T)o(yp)q(e)g(2)p 1882 1915 V 55 1954
V 81 1943 a(\(Cung,)f(1994\))p 735 1954 V 944 1954 V
692 w(Cen)o(tralized)p 1182 1954 V 1532 1954 V 1882 1954
V 56 1956 1827 2 v 55 1995 2 40 v 81 1984 a(Jam)o(b)q(oree)p
735 1995 V 574 w(1994)p 944 1995 V 109 w(Dynamic/)p 1182
1995 V 64 w(T)o(yp)q(e)h(1+3+Bad)g(2)p 1532 1995 V 77
w(T)o(yp)q(e)g(1+Bad)g(2)p 1882 1995 V 55 2035 V 81 2023
a(\(Kuszmaul,)e(1994\))p 735 2035 V 944 2035 V 621 w(Distributed)p
1182 2035 V 1532 2035 V 1882 2035 V 56 2037 1827 2 v
55 2076 2 40 v 81 2064 a(ABD)o(AD)o(A)p 735 2076 V 569
w(1995)p 944 2076 V 109 w(Dynamic/)p 1182 2076 V 64 w(T)o(yp)q(e)i
(1+3+Bad)g(2)p 1532 2076 V 77 w(T)o(yp)q(e)g(1+Bad)g(2)p
1882 2076 V 55 2115 V 81 2104 a(\(W)m(eill,)f(1995\))p
735 2115 V 944 2115 V 696 w(Distributed)p 1182 2115 V
1532 2115 V 1882 2115 V 56 2117 1827 2 v 55 2157 2 40
v 81 2145 a(Dynamic)f(Multiple)h(PV-Split)p 735 2157
V 297 w(1995)p 944 2157 V 109 w(Dynamic/)p 1182 2157
V 64 w(No)q(des)h(within)p 1532 2157 V 145 w(No)q(des)g(within)p
1882 2157 V 55 2196 V 81 2184 a(\(Marsland)e(and)i(Gao,)f(1995\))p
735 2196 V 944 2196 V 487 w(Distributed)p 1182 2196 V
53 w(PV)i(set)p 1532 2196 V 244 w(PV)g(set)p 1882 2196
V 56 2198 1827 2 v 55 2237 2 40 v 81 2225 a(APHID)p 735
2237 V 608 w(1996)p 944 2237 V 133 w(Static/)p 1182 2237
V 88 w(T)m(op)f(k-ply)p 1532 2237 V 199 w(None)p 1882
2237 V 55 2276 V 81 2265 a(\(Bro)q(c)o(kingto)o(n)e(and)h(Sc)o
(hae\013er,)f(1996\))p 735 2276 V 944 2276 V 368 w(Cen)o(tralized)p
1182 2276 V 1532 2276 V 1882 2276 V 56 2278 1827 2 v
56 2288 V 312 2363 a Fp(T)m(able)14 b(1:)j(Comparison)12
b(of)i(P)o(arallel)e Fk(\013\014)r Fp(-based)j(Game-T)m(ree)e(Searc)o
(h)h(Algorithms)p eop
%%Page: 3 3
3 2 bop 467 50 a Fe(A)14 b(T)m(axonom)o(y)d(of)i(P)o(arallel)g(Game-T)m
(ree)g(Searc)o(h)h(Algorithms)465 b Fp(3)0 195 y(The)18
b(second)h(column)e(giv)o(es)g(the)i(date)f(that)g(the)g(algorithm)d(w)
o(as)j(\014rst)h(published)f(or)g(receiv)o(ed)h(b)o(y)e(a)h(journal.)29
b(This)0 245 y(information)11 b(has)j(b)q(een)h(used)g(to)f(order)g
(the)h(algorithms)c(in)o(to)i(c)o(hronological)g(order.)0
324 y(The)20 b(third)g(column)f(con)o(tains)h(information)d(on)j(b)q
(oth)g(the)h(pro)q(cessor)g(hierarc)o(h)o(y)g(and)f(the)g(distribution)
g(of)f(con)o(trol)0 374 y(within)12 b(the)h(algorithm.)i
Fn(Pr)n(o)n(c)n(essor)e(Hier)n(ar)n(chy)e Fp(categorizes)j(algorithms)c
(based)j(on)g(the)g(rigidit)o(y)e(of)h(the)h(pro)q(cessor)h(tree.)0
423 y(If)g(the)g(pro)q(cessor)i(tree)f(is)f Fn(static)p
Fp(,)f(one)h(or)g(more)f(pro)q(cessors)j(are)f(designated)f(as)g
(masters,)g(and)f(con)o(trol)h(the)h(other)f(sla)o(v)o(e)0
473 y(pro)q(cessors.)20 b(This)14 b(hierarc)o(h)o(y)g(is)g(\014xed)g
(throughout)g(a)f(searc)o(h)i(of)e(the)i(game-tree.)i(A)d
Fn(dynamic)h Fp(pro)q(cessor)g(tree)g(c)o(hanges)0 523
y(based)f(on)g(the)g(distribution)f(of)h(busy)g(and)f(idle)g(pro)q
(cessors.)21 b Fn(Contr)n(ol)14 b(Distribution)f Fp(describ)q(es)j
(whether)f(the)f(con)o(trol)g(of)0 573 y(the)i(algorithm)c(is)j
Fn(c)n(entr)n(alize)n(d)g Fp(on)g(a)g(small)e(n)o(um)o(b)q(er)h(of)h
(masters)g(\(e.g.)21 b(PV-Split\),)15 b(or)g(could)g(b)q(e)h
Fn(distribute)n(d)f Fp(amongst)0 623 y(all)e(pro)q(cessors)j(\(e.g.)i
(Y)m(oung)13 b(Brothers)i(W)m(ait\).)0 702 y(The)e(fourth)g(column)f
(describ)q(es)j(the)e(t)o(ypical)f(no)q(des)i(of)e(the)i(game-tree)f
(where)h(parallelism)c(could)j(o)q(ccur.)19 b(The)13
b(descrip-)0 751 y(tion)f(is)h(based)g(on)g(the)g(classi\014cation)f
(of)g(the)i(minim)o(al)9 b(game-tree)j(b)o(y)h(Kn)o(uth)g(and)f(Mo)q
(ore)h(\(1975\).)k(Note)c(that)g(the)g(t)o(yp)q(e)0 801
y(2)h(\(cut)h(no)q(des\))g(ha)o(v)o(e)f(b)q(een)h(di\013eren)o(tiated)g
(in)o(to)f(t)o(w)o(o)f(sub-classes.)21 b(When)14 b(a)g(t)o(yp)q(e)h(2)e
(no)q(de)i(has)f(not)g(b)q(een)i(pruned)f(after)0 851
y(searc)o(hing)f(the)h(\014rst)g(mo)o(v)o(e,)d(this)i(no)q(de)g(is)g
(called)g(a)g Fn(b)n(ad)h(typ)n(e)g(2)f Fp(no)q(de)h(due)f(to)g(its)g
(incorrect)h(mo)o(v)o(e)e(ordering.)18 b(Similarly)l(,)0
901 y Fn(go)n(o)n(d)e(typ)n(e)f(2)g Fp(no)q(des)g(are)g(considered)h
(to)e(b)q(e)h(t)o(yp)q(e)g(2)f(no)q(des)h(that)g(cause)g(a)f(cuto\013)h
(after)g(examining)d(the)j(\014rst)g(mo)o(v)o(e)e(\(i.e.)0
951 y(the)h(mo)o(v)o(e)f(ordering)h(is)f(correct\).)0
1029 y(F)m(or)i(example,)g(PV-Split)g(only)g(implem)o(en)o(ts)f
(parallelism)f(at)i(t)o(yp)q(e)h(1)g(\(principal)f(v)n(ariation\))f(no)
q(des,)i(while)f(the)i(Y)m(oung)0 1079 y(Brothers)e(W)m(ait)e
(algorithms)e(allo)o(w)h(for)h(parallelism)e(at)j(t)o(yp)q(e)g(1,)f(t)o
(yp)q(e)h(3)g(\(all)e(no)q(des\))j(and)f(bad)f(t)o(yp)q(e)h(2)g(no)q
(des.)19 b(A)o(t)13 b(go)q(o)q(d)0 1129 y(t)o(yp)q(e)j(2)f(no)q(des,)i
(the)f(Y)m(oung)f(Brothers)i(W)m(ait)d(algorithm)f(will)h(searc)o(h)j
(the)f(\014rst)g(mo)o(v)o(e,)e(ac)o(hiev)o(e)i(a)f(cuto\013,)h(and)g
(none)g(of)0 1179 y(the)e(other)h(c)o(hildren)f(will)e(b)q(e)j(ev)n
(aluated.)0 1258 y(The)g(\014fth)g(column)e(indicates)i(whic)o(h)f(no)q
(des)i(of)e(the)h(game-tree)f(migh)o(t)f(ha)o(v)o(e)h(parallelism)e
(constrained)k(b)o(y)e(w)o(aiting)f(for)0 1308 y(the)f(\014rst)h
Fk(k)f Fp(c)o(hildren)g(to)g(b)q(e)g(ev)n(aluated.)17
b(F)m(or)12 b(example,)e(bad)i(t)o(yp)q(e)g(2)f(no)q(des)i(are)f(sync)o
(hronization)g(p)q(oin)o(ts)f(for)h(Akl)f Fn(et.)h(al)p
Fp('s)0 1357 y(Mandatory)f(W)m(ork)g(First)g(algorithm,)e(while)i(t)o
(yp)q(e)h(1)f(and)g(bad)h(t)o(yp)q(e)g(2)f(no)q(des)h(are)g(sync)o
(hronization)f(p)q(oin)o(ts)h(for)f(F)m(erguson)0 1407
y(and)j(Korf)s('s)g(Bound-and-Branc)o(h)g(algorithm.)0
1554 y Fl(2.2)48 b(Comparison)14 b(of)h(the)g Fk(\013\014)j
Fl(Implemen)o(tati)o(ons)0 1662 y Fp(T)m(able)13 b(2)h(summarizes)e(an)
i(implem)o(en)o(tation)d(of)i(eac)o(h)i(algorithm)c(giv)o(en)i(in)h(T)m
(able)f(1.)0 1741 y(The)j(\014rst)g(column)d(giv)o(es)i(the)h(name)e
(of)g(the)i(algorithm,)c(and)j(the)h(reference)i(to)d(the)g(pap)q(er)h
(that)f(con)o(tains)g(the)h(details)0 1790 y(ab)q(out)e(the)i(implem)o
(en)o(tation.)h(In)e(some)e(cases,)j(this)e(pap)q(er)i(ma)o(y)c(b)q(e)j
(di\013eren)o(t)h(than)e(the)i(pap)q(er)f(whic)o(h)f(b)q(est)i(describ)
q(es)0 1840 y(the)e(algorithm.)0 1919 y(The)f(second)g(column)e
(describ)q(es)k(the)e(underlying)f(hardw)o(are)h(used)g(to)f(host)h
(the)g(selected)h(implemen)o(tation.)g(A)f(soft)o(w)o(are)0
1969 y Fn(simulation)h Fp(of)f(hardw)o(are)h(is)g(denoted)h(in)e(this)h
(column.)0 2048 y(The)k(third)g(column)e(describ)q(es)j(the)f(t)o(yp)q
(e)h(of)e(game-trees)g(explored)h(b)o(y)f(the)i(algorithm.)26
b(If)17 b(the)h(game-trees)g(are)g(not)0 2098 y(generated)12
b(b)o(y)f(game-pla)o(ying)d(programs,)i(they)i(are)f(considered)h(to)f
(b)q(e)h Fn(arti\014cial)g(tr)n(e)n(es)p Fp(.)k(In)11
b(terms)g(of)f(a)o(v)o(erage)h(branc)o(hing)0 2147 y(factor,)i(c)o
(hess)j(trees)f(are)g(wider)f(than)g(Othello)f(trees,)i(and)f(b)q(oth)g
(are)g(wider)g(than)g(c)o(hec)o(k)o(ers)i(trees.)0 2226
y(The)j(fourth)g(column)e(denotes)i(whic)o(h)g(of)f(the)h(sequen)o
(tial)g(game-tree)f(searc)o(hing)h(algorithms)d(w)o(as)j(parallelized:)
27 b Fk(\013\014)0 2276 y Fp(\(Brudno,)21 b(1963;)g(Kn)o(uth)f(and)f
(Mo)q(ore,)i(1975\),)e(PVS)h(\(Marsland,)g(1983\))f(or)g(NegaScout)h
(\(Reinfeld,)g(1983\).)34 b(Some)0 2326 y(programs)17
b(are)i(more)e(e\016cien)o(t)h(when)h(using)f(a)g(di\013eren)o(t)h
(sequen)o(tial)f(algorithm,)e(dep)q(ending)j(on)f(the)h(nature)g(of)e
(the)0 2376 y(ev)n(aluation)g(function)i(and)g(the)g(strength)h(of)e
(the)i(mo)o(v)o(e)d(ordering)i(tec)o(hniques)h(in)e(the)i(sequen)o
(tial)f(program.)31 b(Th)o(us,)0 2425 y(the)18 b(c)o(hoice)g(of)e
(sequen)o(tial)i(algorithm)c(to)j(compare)g(the)h(parallel)e(algorithm)
e(against)j(is)g(a)g(factor)g(to)g(consider)h(when)0
2475 y(ev)n(aluating)12 b(a)i(parallel)f(algorithm's)e(results.)0
2554 y(The)k(\014fth)g(column)f(describ)q(es)j(what)e(t)o(yp)q(e)h(of)e
(transp)q(osition)h(table)g(has)g(b)q(een)h(implemen)o(ted)d(for)i(the)
g(algorithm.)k(E\016-)0 2604 y(cien)o(t)c(sharing)f(of)g(transp)q
(osition)g(table)h(information)c(is)j(crucial)h(to)f(the)h(p)q
(erformance)f(of)g(a)g(parallel)g(game-tree)g(searc)o(h)0
2654 y(algorithm.)g(The)d(t)o(w)o(o)f(main)e(metho)q(ds)h(are)i(a)f
Fn(distribute)n(d)f Fp(message-passing)h(transp)q(osition)g(table)g
(and)g(a)g Fn(shar)n(e)n(d-memory)0 2704 y Fp(transp)q(osition)k
(table.)k(Sp)q(ecial)c(hardw)o(are)g(is)g(required)g(to)g(implemen)o(t)
d(a)j(shared-memory)e(transp)q(osition)i(table,)f(but)h(is)p
eop
%%Page: 4 4
4 3 bop 0 50 a Fp(4)603 b(ICCA)14 b(Journal)f(Submission)601
b(June)15 b(12,)e(1996)p 9 508 1921 2 v 9 518 V 8 557
2 40 v 270 545 a Fh(Algorithm)p 688 557 V 321 w(Hardw)o(are)p
961 557 V 143 w(T)m(est)p 1192 557 V 110 w(Sequen)o(tial)p
1405 557 V 84 w(T)m(rans-)p 1624 557 V 1624 557 V 146
w(Sp)q(eedup)p 1928 557 V 8 597 V 261 585 a(\(Reference\))p
688 597 V 348 w(Used)p 961 597 V 153 w(Domain)p 1192
597 V 80 w(Algorithm)p 1405 597 V 73 w(P)o(osition)p
1624 597 V 1624 597 V 125 w(Obtained)p 1928 597 V 8 636
V 688 636 V 961 636 V 1192 636 V 1405 636 V 1473 624
a(T)m(able)p 1624 636 V 1928 636 V 9 638 1921 2 v 9 648
V 8 687 2 40 v 34 675 a(P)o(arallel)d(Aspiration)f(Searc)o(h)p
688 687 V 304 w(Sim)o(ulation)p 961 687 V 97 w(Arti\014cial)p
1192 687 V 130 w Ff(\013\014)p 1405 687 V 159 w Fh(none)p
1624 687 V 96 w Fd(\024)i Fh(6)g(for)g(large)f(n)p 1928
687 V 8 727 V 34 715 a(\(Baudet,)f(1978\))p 688 727 V
961 727 V 771 w(T)m(rees)p 1192 727 V 1405 727 V 1624
727 V 530 w(\(sim)o(ulated\))p 1928 727 V 9 728 1921
2 v 8 768 2 40 v 34 756 a(Mandatory)g(W)m(ork)i(First)p
688 768 V 357 w(Sim)o(ulation)p 961 768 V 97 w(Arti\014cial)p
1192 768 V 130 w Ff(\013\014)p 1405 768 V 148 w Fh(\\score)p
1624 768 V 85 w Fd(\024)g Fh(6)g(for)g(large)f(n)p 1928
768 V 8 807 V 34 795 a(\(Akl,)h(Barnard)f(and)g(Doran,)g(1982\))p
688 807 V 961 807 V 503 w(T)m(rees)p 1192 807 V 1405
807 V 349 w(table")p 1624 807 V 85 w(\(sim)o(ulated\))p
1928 807 V 9 809 1921 2 v 8 848 2 40 v 34 836 a(T)m(ree)h(Splitting)p
688 848 V 506 w(LSI-11)f(&)p 961 848 V 114 w(Chec)o(k)o(ers)p
1192 848 V 130 w Ff(\013\014)p 1405 848 V 159 w Fh(none)p
1624 848 V 96 w(2.34)h(\(n=3\))p 1928 848 V 8 888 V 34
876 a(\(Fink)o(el)f(and)g(Fish)o(burn,)g(1982\))p 688
888 V 274 w(Sim)o(ulation)p 961 888 V 1192 888 V 1405
888 V 1624 888 V 737 w(5.12)h(\(n=27,sim\))p 1928 888
V 9 889 1921 2 v 8 929 2 40 v 34 917 a(PV-Split)p 688
929 V 611 w(Sun)g(3)p 961 929 V 163 w(Chess)p 1192 929
V 142 w(PVS)p 1405 929 V 145 w(lo)q(cal)p 1624 929 V
97 w(3.75)g(\(n=5\))p 1928 929 V 8 968 V 34 956 a(\(Marsland,)e
(Olafsson)g(and)h(Sc)o(hae\013er,)e(1985\))p 688 968
V 95 w(Net)o(w)o(ork)p 961 968 V 1192 968 V 1405 968
V 1624 968 V 1928 968 V 9 970 1921 2 v 8 1009 2 40 v
34 998 a(Key)j(No)q(de)p 688 1009 V 555 w(Sim)o(ulation)p
961 1009 V 97 w(Arti\014cial)p 1192 1009 V 130 w Ff(\013\014)p
1405 1009 V 159 w Fh(none)p 1624 1009 V 96 w(12.57)g(\(n=20\))p
1928 1009 V 8 1049 V 34 1037 a(\(Lindstrom,)e(1983\))p
688 1049 V 961 1049 V 722 w(T)m(rees)p 1192 1049 V 1405
1049 V 1624 1049 V 1928 1049 V 9 1050 1921 2 v 8 1090
2 40 v 34 1078 a(UIDP)m(ABS)p 688 1090 V 530 w(Data)h(General)p
961 1090 V 102 w(Chess)p 1192 1090 V 155 w Ff(\013\014)p
1405 1090 V 159 w Fh(lo)q(cal)p 1624 1090 V 97 w(3.94)h(\(n=8\))p
1928 1090 V 8 1129 V 34 1117 a(\(Newb)q(orn,)f(1988\))p
688 1129 V 420 w(\(mixed)f(pro)q(cs.\))p 961 1129 V 1192
1129 V 1405 1129 V 1624 1129 V 1928 1129 V 9 1131 1921
2 v 8 1170 2 40 v 34 1159 a(DPVS)p 688 1170 V 650 w(Sun)i(3)p
961 1170 V 163 w(Chess)p 1192 1170 V 95 w(NegaScout)p
1405 1170 V 52 w(TT.)i(Mgr)e(-)p 1624 1170 V 54 w(7.64)g(\(n=19\))p
1928 1170 V 8 1210 V 34 1198 a(\(Sc)o(hae\013er,)d(1989\))p
688 1210 V 469 w(Net)o(w)o(ork)p 961 1210 V 1192 1210
V 1405 1210 V 555 w(messages)p 1624 1210 V 1928 1210
V 9 1212 1921 2 v 8 1251 2 40 v 34 1239 a(EPVS)p 688
1251 V 637 w(Sequen)o(t)p 961 1251 V 144 w(Chess)p 1192
1251 V 155 w Ff(\013\014)p 1405 1251 V 145 w Fh(shared)p
1624 1251 V 82 w(5.93)j(\(n=16\))p 1928 1251 V 8 1290
V 34 1279 a(\(Hy)o(att,)f(Suter)g(and)h(Nelson,)g(1989\))p
688 1290 V 233 w(Balance)p 961 1290 V 1192 1290 V 1405
1290 V 565 w(memory)p 1624 1290 V 1928 1290 V 9 1292
1921 2 v 8 1331 2 40 v 34 1320 a(W)m(a)o(yco)q(ol)p 688
1331 V 576 w(Hyp)q(ercub)q(e)p 961 1331 V 122 w(Chess)p
1192 1331 V 155 w Ff(\013\014)p 1405 1331 V 111 w Fh(distributed)p
1624 1331 V 46 w(101)g(\(n=256\))p 1928 1331 V 8 1371
V 34 1359 a(\(F)m(elten)f(and)g(Otto,)i(1988\))p 688
1371 V 961 1371 V 1192 1371 V 1405 1371 V 1043 w(messages)p
1624 1371 V 1928 1371 V 9 1373 1921 2 v 8 1412 2 40 v
34 1400 a(Y)m(oung)f(Brothers)e(W)m(ait)p 688 1412 V
371 w(T)m(ransputers)p 961 1412 V 113 w(Chess)p 1192
1412 V 95 w(NegaScout)p 1405 1412 V 48 w(distributed)p
1624 1412 V 46 w(142)i(\(n=256\))p 1928 1412 V 8 1451
V 34 1440 a(\(F)m(eldmann,)e(1993\))p 688 1451 V 961
1451 V 1192 1451 V 1405 1451 V 1139 w(messages)p 1624
1451 V 63 w(344)i(\(n=1024\))p 1928 1451 V 9 1453 1921
2 v 8 1493 2 40 v 34 1481 a(Dynamic)e(T)m(ree)j(Splitting)p
688 1493 V 366 w(Sequen)o(t)p 961 1493 V 144 w(Chess)p
1192 1493 V 155 w Ff(\013\014)p 1405 1493 V 145 w Fh(shared)p
1624 1493 V 82 w(8.81)f(\(n=16\))p 1928 1493 V 8 1532
V 34 1520 a(\(Hy)o(att,)f(1988\))p 688 1532 V 521 w(Balance)p
961 1532 V 1192 1532 V 1405 1532 V 565 w(memory)p 1624
1532 V 1928 1532 V 9 1534 1921 2 v 8 1573 2 40 v 34 1561
a(Bound-and-Br)o(anc)n(h)p 688 1573 V 413 w(Hyp)q(ercub)q(e)p
961 1573 V 109 w(Othello)p 1192 1573 V 142 w Ff(\013\014)p
1405 1573 V 111 w Fh(distributed)p 1624 1573 V 46 w(12)h(\(n=32\))p
1928 1573 V 8 1613 V 34 1601 a(\(F)m(erguson)e(and)i(Korf,)g(1988\))p
688 1613 V 961 1613 V 1192 1613 V 1405 1613 V 1003 w(messages)p
1624 1613 V 1928 1613 V 9 1614 1921 2 v 8 1654 2 40 v
34 1642 a(Dela)o(y)o(ed)f(Branc)o(h)g(T)m(ree)h(Expansion)p
688 1654 V 211 w(Sim)o(ulation)p 961 1654 V 121 w(Chess)p
1192 1654 V 155 w Ff(\013\014)p 1405 1654 V 159 w Fh(none)p
1624 1654 V 96 w(350)g(\(n=1000,)p 1928 1654 V 8 1693
V 34 1681 a(\(Hsu,)g(1990\))p 688 1693 V 961 1693 V 1192
1693 V 1405 1693 V 1624 1693 V 1434 w(sim)o(ulated\))p
1928 1693 V 9 1695 1921 2 v 8 1734 2 40 v 34 1722 a(F)m(ron)o(tier)f
(Splitting)p 688 1734 V 482 w(BBN)p 961 1734 V 146 w(Chec)o(k)o(ers)p
1192 1734 V 70 w(NegaScout)p 1405 1734 V 82 w(shared)p
1624 1734 V 82 w(3.32)h(\(n=16\))p 1928 1734 V 8 1774
V 34 1762 a(\(Lu,)g(1993\))p 688 1774 V 568 w(TC2000)p
961 1774 V 1192 1774 V 1405 1774 V 566 w(memory)p 1624
1774 V 1928 1774 V 9 1775 1921 2 v 8 1815 2 40 v 34 1803
a Ff(\013\014)r Fh(*)p 688 1815 V 637 w(T)m(ransputers)p
961 1815 V 113 w(Chess)p 1192 1815 V 95 w(NegaScout)p
1405 1815 V 48 w(distributed)p 1624 1815 V 46 w(6.5)g(\(n=8+8TT\))p
1928 1815 V 8 1854 V 34 1842 a(\(Da)o(vid,)f(1993\))p
688 1854 V 961 1854 V 1192 1854 V 1405 1854 V 1199 w(messages)p
1624 1854 V 1928 1854 V 9 1856 1921 2 v 8 1895 2 40 v
34 1883 a(CABP)p 688 1895 V 631 w(Sequen)o(t)p 961 1895
V 120 w(Arti\014cial)p 1192 1895 V 130 w Ff(\013\014)p
1405 1895 V 145 w Fh(shared)p 1624 1895 V 82 w(4.6)h(\(n=9\))p
1928 1895 V 8 1935 V 34 1923 a(\(Cung,)f(1994\))p 688
1935 V 528 w(Balance)p 961 1935 V 149 w(T)m(rees)p 1192
1935 V 1405 1935 V 334 w(memory)p 1624 1935 V 1928 1935
V 9 1936 1921 2 v 8 1976 2 40 v 34 1964 a(Jam)o(b)q(oree)p
688 1976 V 598 w(CM-5)p 961 1976 V 164 w(Chess)p 1192
1976 V 95 w(NegaScout)p 1405 1976 V 48 w(distributed)p
1624 1976 V 46 w Fd(\031)p Fh(50)i(\(n=512\))p 1928 1976
V 8 2015 V 34 2003 a(\(Kuszmaul,)d(1994\))p 688 2015
V 961 2015 V 1192 2015 V 1405 2015 V 1138 w(messages)p
1624 2015 V 1928 2015 V 9 2017 1921 2 v 8 2056 2 40 v
34 2044 a(ABD)o(AD)o(A)p 688 2056 V 593 w(CM-5)p 961
2056 V 164 w(Chess)p 1192 2056 V 95 w(NegaScout)p 1405
2056 V 48 w(distributed)p 1624 2056 V 46 w(15.85)i(\(n=32\))p
1928 2056 V 8 2096 V 34 2084 a(\(W)m(eill,)f(1996\))p
688 2096 V 961 2096 V 754 w(\(&)i(Othello\))p 1192 2096
V 1405 2096 V 277 w(messages)p 1624 2096 V 1928 2096
V 9 2097 1921 2 v 8 2137 2 40 v 34 2125 a(Dynamic)d(Multiple)h
(PV-Split)p 688 2137 V 298 w(AP-1000)p 961 2137 V 116
w(Arti\014cial)p 1192 2137 V 117 w(PVS)p 1405 2137 V
145 w(none)p 1624 2137 V 96 w Fd(\031)p Fh(32)i(\(n=64\))p
1928 2137 V 8 2176 V 34 2164 a(\(Marsland)e(and)g(Gao,)h(1995\))p
688 2176 V 961 2176 V 594 w(T)m(rees)p 1192 2176 V 1405
2176 V 1624 2176 V 1928 2176 V 9 2178 1921 2 v 8 2217
2 40 v 34 2205 a(APHID)p 688 2217 V 618 w(Sparc)f(2)p
961 2217 V 149 w(Chess)p 1192 2217 V 95 w(NegaScout)p
1405 2217 V 96 w(lo)q(cal)p 1624 2217 V 97 w(6.04)h(\(n=16\))p
1928 2217 V 8 2257 V 34 2245 a(\(Bro)q(c)o(kington)d(and)j(Sc)o
(hae\013er,)d(1995\))p 688 2257 V 200 w(Net)o(w)o(ork)p
961 2257 V 1192 2257 V 1405 2257 V 1624 2257 V 1928 2257
V 9 2258 1921 2 v 9 2268 V 262 2343 a Fp(T)m(able)13
b(2:)18 b(Comparison)12 b(of)h(P)o(arallel)g Fk(\013\014)r
Fp(-based)i(Game-T)m(ree)e(Searc)o(h)h(Implemen)o(tations)p
eop
%%Page: 5 5
5 4 bop 467 50 a Fe(A)14 b(T)m(axonom)o(y)d(of)i(P)o(arallel)g(Game-T)m
(ree)g(Searc)o(h)h(Algorithms)465 b Fp(5)0 195 y(generally)15
b(faster)g(than)g(distributed)h(transp)q(osition)e(tables)i(based)f(on)
g(message)f(passing.)21 b(Lo)q(cal)15 b(transp)q(osition)g(tables)0
245 y(are)h(main)o(tained)d(separately)i(on)g(eac)o(h)h(pro)q(cessor,)h
(but)e(no)g(transp)q(osition)g(table)g(information)e(is)i(shared)h(b)q
(et)o(w)o(een)g(the)0 295 y(pro)q(cessors.)0 374 y(The)h(\014nal)e
(column)g(giv)o(es)h(the)g Fn(sp)n(e)n(e)n(dup)h Fp(of)f(the)g
(implemen)o(tation)d(on)j(a)g(large)f(n)o(um)o(b)q(er)h(of)f(pro)q
(cessors.)27 b(There)18 b(will)c(b)q(e)0 423 y(a)19 b(tendency)h(to)f
(read)g(do)o(wn)f(this)h(column)f(and)g(use)i(the)f(absolute)g(sp)q
(eedup)i(or)e(relativ)o(e)f(e\016ciencies)i(to)f(determine)0
473 y(something)d(ab)q(out)h(a)g(pair)g(of)g(algorithms.)26
b(It)18 b(is)f(v)o(ery)h(hard)f(and)g(misleading)e(to)i(compare)g(t)o
(w)o(o)g(algorithms)e(in)i(this)0 523 y(manner.)g(There)e(are)f(\014v)o
(e)h(ma)r(jor)d(concerns)j(when)g(comparing)d(sp)q(eedup)j(n)o(um)o(b)q
(ers.)0 602 y(The)i(\014rst)g(concern)h(deals)e(with)g(sim)o(ulation)e
(results.)27 b(It)16 b(is)g(often)h(di\016cult)f(to)g(determine)g(ho)o
(w)g(a)g(parallel)g(algorithm)0 652 y(will)c(b)q(eha)o(v)o(e)j(on)e(a)h
(large)g(n)o(um)o(b)q(er)f(of)g(mac)o(hines,)g(due)h(to)g(o)o(v)o
(er-simpli\014cation)d(of)i(the)i(sim)o(ulation)c(mo)q(del)h(b)q(eing)i
(used.)0 731 y(The)j(second)g(ma)r(jor)d(concern)k(deals)e(with)g(the)g
(test)h(domain.)23 b(Arti\014cial)15 b(trees)j(rarely)e(re\015ect)i
(the)e(unique)h(prop)q(erties)0 780 y(of)12 b(searc)o(hing)i(a)f(real)g
(c)o(hess/c)o(hec)o(k)o(ers/Othe)q(llo)h(tree,)g(and)f(migh)o(t)e(b)q
(e)j(geared)f(to)o(w)o(ards)g(illustrating)f(the)i(strength)g(of)e(the)
0 830 y(parallel)h(algorithm)e(\(Plaat)i Fn(et.)19 b(al)p
Fp(,)13 b(1996\).)0 909 y(The)19 b(third)g(ma)r(jor)f(concern)i(is)f
(that)g(w)o(e)g(cannot)g(tak)o(e)g(the)g(real)g(trees)i(at)e(face)g(v)n
(alue)f(either,)j(since)e(the)h(sequen)o(tial)0 959 y(algorithm)11
b(used)j(to)f(generate)i(the)f(tree)g(ma)o(y)e(not)h(b)q(e)h(an)f
(e\016cien)o(t)h(searc)o(her)h(\(with)e(resp)q(ect)j(to)d(the)h(minim)o
(al)c(tree)15 b(size\).)0 1009 y(This)f(could)f(b)q(e)h(caused)h(b)o(y)
e(lea)o(ving)g(out)g(k)o(ey)h(mo)o(v)o(e)e(ordering)h(tec)o(hniques,)i
(suc)o(h)f(as)g(a)f(su\016cien)o(tly)h(large)f(transp)q(osition)0
1059 y(table,)g(iterativ)o(e)g(deep)q(ening)h(or)f(killer)f(mo)o(v)o
(es.)k(A)d(p)q(o)q(or)g(searc)o(her)i(will)d(yield)g(more)g(opp)q
(ortunities)h(for)g(parallelism,)d(and)0 1108 y(ma)o(y)i(increase)j
(the)g(sp)q(eedup)g(ac)o(hiev)o(ed)f(b)o(y)g(the)g(algorithm.)0
1187 y(The)h(fourth)f(concern)i(deals)f(with)f(the)h(v)n(aried)f(branc)
o(hing)g(factor)h(of)e(the)i(game-trees)g(in)f(di\013eren)o(t)h(test)h
(domains.)i(The)0 1237 y(a)o(v)o(erage)f(branc)o(hing)f(factor)g(in)h
(c)o(hess)h(\(38\))e(is)g(higher)h(than)f(the)i(a)o(v)o(erage)e(branc)o
(hing)h(factor)f(in)g(c)o(hec)o(k)o(ers)j(\(8)d(for)g(non-)0
1287 y(capture)h(p)q(ositions\).)25 b(T)m(aking)14 b(capture)j(p)q
(ositions)f(in)o(to)g(accoun)o(t,)g(the)h(a)o(v)o(erage)f(branc)o(hing)
g(factor)g(of)f(c)o(hec)o(k)o(ers)j(is)e(less)0 1337
y(than)f(3)g(\(Lu,)g(1993\).)21 b(The)15 b(breadth)h(of)e(c)o(hec)o(k)o
(ers)j(trees)g(yield)e(sp)q(eedups)i(that)e(are)g(m)o(uc)o(h)f(smaller)
g(in)h(magnitude)e(than)0 1386 y(the)h(same)f(algorithm)f(implem)o(en)o
(ted)g(on)i(a)g(c)o(hess)h(program.)0 1465 y(The)h(\014nal)g(concern)h
(deals)f(with)g(the)h(sp)q(eed)g(of)f(the)g(pro)q(cessor)i(v)o(ersus)f
(the)g(sp)q(eed)h(of)d(the)i(net)o(w)o(ork.)24 b(If)16
b(the)h(algorithm)0 1515 y(w)o(as)i(tested)i(on)e(slo)o(w)g(pro)q
(cessors)i(with)e(a)g(fast)g(net)o(w)o(ork)h(linking)d(them,)i(the)h
(algorithm)d(ma)o(y)g(not)i(yield)g(the)h(same)0 1565
y(p)q(erformance)14 b(when)g(using)g(faster)g(pro)q(cessors)i(and/or)e
(a)f(slo)o(w)o(er)h(net)o(w)o(ork.)0 1644 y(In)f(short,)g(it)g(is)g
(nearly)g(imp)q(ossible)e(to)i(ob)r(jectiv)o(ely)g(compare)f(sp)q
(eedups)j(or)e(e\016ciencies)i(for)d(the)i(di\013eren)o(t)g(implemen)o
(ta-)0 1694 y(tions)g(giv)o(en)f(in)h(T)m(able)f(2.)0
1882 y Fl(2.3)48 b(Descriptio)o(ns)13 b(of)i(Earlier)f(Algorithms)f
(\(1979-June)g(1987\))0 1998 y Fp(Baudet's)20 b(w)o(ork)f(\(1978\))g
(describ)q(ed)i(a)e(metho)q(d)g(of)g(doing)f Fn(p)n(ar)n(al)r(lel)h
(aspir)n(ation)h(se)n(ar)n(ch)p Fp(.)34 b(Aspiration)19
b(searc)o(h)i(can)e(b)q(e)0 2048 y(describ)q(ed)e(as)f(the)g(shrinking)
f(of)g(the)h(initial)d Fk(\013\014)18 b Fp(windo)o(w)d(to)g(a)g(small)e
(range.)23 b(If)15 b(the)h(minima)o(x)d(v)n(alue)h(lies)i(within)e(the)
0 2098 y(smaller)g(range,)i(the)h(correct)g(minima)o(x)c(v)n(alue)i
(could)h(b)q(e)g(returned)i(while)d(visiting)g(less)h(leaf)g(no)q(des)g
(than)g(w)o(ould)f(ha)o(v)o(e)0 2147 y(b)q(een)g(visited)f(b)o(y)g
(using)f(the)i(larger)e(range.)0 2226 y(In)k(Baudet's)g(w)o(ork,)g(the)
g(initial)e Fk(\013\014)k Fp(windo)o(w)d(is)h(sub)q(divided)g(in)o(to)f
Fk(p)h Fp(disjoin)o(t)e(windo)o(ws,)i(where)h Fk(p)e
Fp(is)h(the)g(n)o(um)o(b)q(er)g(of)0 2276 y(pro)q(cessors)h(used.)25
b(Eac)o(h)16 b(pro)q(cessor)i(searc)o(hes)g(the)f(game-tree)e(with)h
(those)g(smaller)f(windo)o(ws.)24 b(When)16 b(a)f(pro)q(cessor)j(is)0
2326 y(\014nished,)e(it)f(can)h(use)g(the)h(result)f(of)f(the)h(searc)o
(h)h(\(if)e(it)g(is)g(a)h(fail)e(lo)o(w)g(or)i(fail)e(high\))h(to)g
(further)i(reduce)g(the)f(size)g(of)f(the)0 2376 y(windo)o(ws)c
(examined.)16 b(Once)d(a)f(pro)q(cessor)i(determines)e(the)g(minim)o
(ax)d(v)n(alue,)i(all)f(pro)q(cessors)k(are)f(stopp)q(ed)f(immediately)
l(.)0 2455 y(Akl,)f(Barnard)g(and)g(Doran)f(\(1982\))g(w)o(ere)i(the)f
(\014rst)h(to)f(prop)q(ose)g(and)g(sim)o(ulate)e(a)i
Fn(mandatory)h(work)g(\014rst)e Fp(algorithm.)15 b(The)0
2504 y(idea)f(of)g(the)h(algorithm)d(is)i(to)g(explore)h(in)f(parallel)
f(those)i(lea)o(v)o(es)g(that)f(w)o(ould)g(b)q(e)h(examined)e(if)h(the)
h(tree)h(w)o(as)e(p)q(erfectly)0 2554 y(ordered.)19 b(There)c(are)f(t)o
(w)o(o)g(categories)g(of)f(no)q(des)i(that)f(corresp)q(ond)h(to)f(the)g
(cut)h(and)e(all)g(no)q(des)h(from)e(the)j(minim)o(al)10
b(tree.)0 2604 y(Left-hand)15 b(no)q(des)h(are)f(similar)d(to)j(all)f
(no)q(des,)i(and)e(all)g(of)g(their)i(successors)h(are)f(ev)n(aluated)f
(at)f(di\013eren)o(t)i(pro)q(cessors)h(in)0 2654 y(parallel.)23
b(Righ)o(t-hand)15 b(no)q(des)i(are)f(similar)e(to)i(cut)g(no)q(des,)h
(and)f(only)g(one)g(successor)i(pro)q(cess)g(can)e(b)q(e)h(spa)o(wned)g
(from)0 2704 y(them)c(at)h(a)f(time.)p eop
%%Page: 6 6
6 5 bop 0 50 a Fp(6)603 b(ICCA)14 b(Journal)f(Submission)601
b(June)15 b(12,)e(1996)0 195 y(The)h(\014rst)h(branc)o(h)f(to)g(b)q(e)g
(ev)n(aluated)g(from)e(a)i(righ)o(t-hand)f(no)q(de)h(migh)o(t)e
(establish)i(a)f(score)j(that)d(signi\014es)h(a)g(cuto\013.)19
b(The)0 245 y(pro)q(cess)d(con)o(trolling)e(a)g(righ)o(t-hand)g(no)q
(de)h(is)f(forced)h(to)g(stall)f(and)g(\014nd)h(out)f(the)h(v)n(alue)f
(of)g(the)i(sibling)d(left-hand)h(no)q(de.)0 295 y(Once)20
b(this)f(sibling)f(left-hand)g(no)q(de)h(has)g(a)g(v)n(alue,)g(the)g(t)
o(w)o(o)f(v)n(alues)h(are)g(compared)f(and)h(the)g(program)f
(determines)0 345 y(whether)g(or)f(not)g(the)h(righ)o(t-hand)e(no)q(de)
h(can)h(b)q(e)f(pruned)h(based)g(on)e(the)i(\014rst)g(branc)o(h)f(that)
g(w)o(as)g(searc)o(hed.)29 b(If)17 b(there)0 394 y(is)e(no)f(cuto\013)i
(y)o(et)f(for)f(the)i(righ)o(t-hand)e(no)q(de,)h(the)g(subsequen)o(t)i
(branc)o(hes)f(in)e(the)i(righ)o(t-hand)e(no)q(de)h(are)g(examined)f
(one)0 444 y(after)i(the)g(other)h(sequen)o(tially)m(.)22
b(This)16 b(will)e(stop)i(when)g(the)g(righ)o(t-hand)f(no)q(de)i(gets)f
(pruned,)h(or)e(the)h(righ)o(t-hand)g(no)q(de)0 494 y(establishes)c(a)f
(v)n(alue)f(higher)h(than)g(the)h(sibling)d(left-hand)i(no)q(de)g
(after)g(exploring)g(all)e(branc)o(hes.)19 b(This)11
b(allo)o(ws)e(the)j(sc)o(heme)0 544 y(to)g(determine)f(most)g(of)g(the)
i(direct)f(shallo)o(w)f(cuto\013s)h(that)g(w)o(ould)f(o)q(ccur)i(in)e
(the)i(sequen)o(tial)f Fk(\013\014)i Fp(algorithm,)9
b(but)j(neglects)0 594 y(some)h(of)g(the)i(deep)g(cuto\013s)f(p)q
(ossible.)0 672 y(Fink)o(el)k(and)h(Fish)o(burn)g(\(1982\))f(in)o(tro)q
(duced)h(the)h(concept)g(of)e Fn(tr)n(e)n(e)g(splitting)p
Fp(.)32 b(In)19 b(their)g(algorithm,)e(a)h(static)i(tree)g(of)0
722 y(pro)q(cessors)c(is)e(o)o(v)o(erlaid)f(on)g(top)h(of)g(a)f
(game-tree.)18 b(The)c(ro)q(ot)g(of)g(the)g(game-tree)g(is)g(giv)o(en)f
(to)h(the)g(ro)q(ot)g(of)g(the)g(pro)q(cessor)0 772 y(tree.)19
b(The)14 b(pro)q(cessor)h(ro)q(ot)f(generates)h(all)d(the)i(mo)o(v)o
(es)e(at)i(ply)f(1)g(of)g(the)h(game-tree,)f(and)g(hands)h(them)e(o)o
(v)o(er)i(to)f(the)h(\014rst)0 822 y(ply)h(of)f(the)i(pro)q(cessor)h
(tree.)23 b(This)15 b(pro)q(cess)i(con)o(tin)o(ues)f(un)o(til)e(w)o(e)h
(reac)o(h)h(the)g(lea)o(v)o(es)f(of)g(the)h(pro)q(cessor)h(tree,)f
(where)g(the)0 872 y(pro)q(cessors)g(execute)f(the)g(sequen)o(tial)e
Fk(\013\014)j Fp(algorithm)11 b(to)j(the)g(required)h(searc)o(h)f
(depth.)19 b(The)14 b(no)q(des)h(in)e(the)h(\014rst)g
Fk(k)h Fp(lev)o(els)0 922 y(of)c(the)i(tree,)g(where)g
Fk(k)f Fp(is)g(the)g(depth)h(of)e(the)i(pro)q(cessor)g(tree,)g(can)f(b)
q(e)h(ev)n(aluated)e(in)h(parallel.)k(The)c(only)f(sync)o(hronization)0
971 y(p)q(oin)o(t)i(o)q(ccurs)j(at)d(the)i(ro)q(ot)f(of)f(the)i(tree)g
(b)q(et)o(w)o(een)g(searc)o(hes)h(at)e(di\013eren)o(t)g(depths.)0
1050 y(The)20 b Fn(PV-Split)f Fp(algorithm)e(\(Campb)q(ell,)h(1981;)j
(Marsland)e(and)g(Campb)q(ell,)g(1982\))f(is)i(a)f(natural)g(extension)
h(of)f(tree)0 1100 y(splitting,)12 b(based)i(on)g(the)g(regular)g
(structure)h(of)e(the)h(minima)o(l)c(game-tree)k(as)f(w)o(e)h(tra)o(v)o
(el)f(along)g(the)h(principal)f(v)n(ariation)0 1150 y(\(PV\).)19
b(The)g(\014rst)h(stage)f(of)g(the)g(algorithm)e(in)o(v)o(olv)o(es)h(a)
g(recursiv)o(e)j(call)d(to)h(itself)f(as)h(it)g(tra)o(v)o(els)g(do)o
(wn)f(the)i(principal)0 1200 y(v)n(ariation.)g(Once)c(the)g(left)f
(subtree)i(of)d(a)h(PV)g(no)q(de)h(has)f(b)q(een)h(examined,)e(all)g
(of)g(the)i(other)f(subtrees)j(b)q(elo)o(w)c(that)i(PV)0
1249 y(no)q(de)d(are)g(searc)o(hed)h(in)e(parallel)f(using)h(tree)i
(splitting.)j(After)c(all)e(of)h(the)h(subtrees)i(ha)o(v)o(e)d(b)q(een)
h(explored,)g(that)g(PV)g(no)q(de)0 1299 y(can)h(return)i(a)e(score)h
(to)f(the)h(PV)f(no)q(de)h(ab)q(o)o(v)o(e)f(it.)k(A)o(t)c(an)o(y)g(one)
h(time,)d(only)h(one)i(no)q(de's)f(subtrees)i(are)f(b)q(eing)f
(examined)0 1349 y(in)f(parallel)g(b)o(y)h(the)g(PV-Split)g(algorithm.)
0 1428 y(In)e(the)h(original)e(implem)o(en)o(tation)e(\(Marsland)j(and)
h(Campb)q(ell,)d(1982\),)h(the)i(PV-Split)f(algorithm)d(did)j(not)g
(use)h(minima)o(l)0 1478 y(windo)o(ws)g(or)g(other)h(searc)o(h)h
(enhancemen)o(t)e(tec)o(hniques)i(common)c(in)h(game-pla)o(ying)f
(programs.)16 b(T)m(o)d(sim)o(ulate)e(these)k(or-)0 1528
y(dering)f(tec)o(hniques,)g(strongly-ordered)g(game-trees)g(w)o(ere)g
(arti\014cially)e(created.)20 b(The)14 b(PV-Split)f(algorithm)e(w)o(as)
i(sho)o(wn)0 1577 y(to)i(ha)o(v)o(e)h(a)f(b)q(etter)i(sp)q(eedup)g
(than)f(tree)g(splitting)f(for)g(the)h(sim)o(ulated)e(strongly-ordered)
i(trees.)25 b(There)17 b(are)f(n)o(umerous)0 1627 y(published)f(exp)q
(erimen)o(ts)g(with)f(the)i(PV-Split)e(algorithm)e(\(Marsland)j(and)g
(P)o(op)q(o)o(wic)o(h,)f(1985;)g(Newb)q(orn,)h(1985;)f(Mars-)0
1677 y(land,)h(Olafsson)h(and)g(Sc)o(hae\013er,)h(1985\).)23
b(The)16 b(b)q(est)h(rep)q(orted)h(e\016ciency)f(in)e(these)i(implemen)
o(tations)c(w)o(as)j(a)f(sp)q(eedup)0 1727 y(of)f(3.75)g(on)h(5)g(pro)q
(cessors)i(for)d(Marsland,)h(Olafsson)g(and)f(Sc)o(hae\013er)j
(\(1985\).)j(The)c(ma)r(jor)d(problem)h(in)g(the)i(implemen-)0
1777 y(tation)g(of)g(PV-Split)g(is)h(a)f(large)g(sync)o(hronization)h
(o)o(v)o(erhead,)g(since)g(man)o(y)e(pro)q(cessors)k(are)e(often)g
(forced)g(to)f(w)o(ait)g(for)0 1826 y(long)d(p)q(erio)q(ds)i(of)f(time)
e(while)i(the)h(last)f(unev)n(aluated)g(branc)o(h)g(of)g(a)g(PV)g(no)q
(de)h(is)f(ev)n(aluated.)k(Newb)q(orn)d(suggested)h(that)0
1876 y(idle)f(pro)q(cessors)j(should)d(assist)h(those)g(pro)q(cessors)i
(that)e(are)g(still)e(busy)i(b)o(y)g(creating)f(a)h(new)g(split)f(no)q
(de)h(that)f(the)h(idle)0 1926 y(pro)q(cessors)g(can)e(w)o(ork)g(on)f
(\(Newb)q(orn,)i(1985\).)0 2005 y(The)c Fn(Key)h(No)n(de)g
Fp(metho)q(d)e(\(Lindstrom,)f(1983\))h(attempts)h(a)f(di\013eren)o(t)i
(metho)q(d)e(for)h(attac)o(king)f(the)h(tree.)18 b(The)12
b(mandatory)0 2055 y(w)o(ork)g(\014rst)h(tree)g(is)f(dynamically)d(ev)o
(olv)o(ed)j(and)g(stored)h(within)e(a)h(cen)o(tralized)h(message)f
(queue.)18 b(Eac)o(h)13 b(pro)q(cessor)h(tak)o(es)e(a)0
2105 y(message)h(from)e(the)j(queue,)g(creates)h(new)f(messages)f
(based)h(on)f(the)h(t)o(yp)q(e)g(of)e(message,)h(and)g(adds)g(the)h
(information)d(in)o(to)0 2154 y(the)j(tree,)g(as)g(required.)k(F)m(or)
13 b(example,)f(if)h(a)g(message)g(is)g(sen)o(t)h(to)f(a)g(leaf)g(no)q
(de)h(within)e(the)i(tree,)h(the)f(no)q(de)f(is)h(ev)n(aluated,)0
2204 y(and)h(the)h(v)n(alue)f(is)h(sen)o(t)g(to)g(the)g(paren)o(t.)23
b(A)o(t)16 b(t)o(yp)q(e)g(1)f(and)g(t)o(yp)q(e)h(3)g(no)q(des,)g
(messages)g(for)f(eac)o(h)h(of)f(the)h(c)o(hildren)g(can)f(b)q(e)0
2254 y(sen)o(t)h(out)f(at)g(the)h(same)e(time)g(\(yielding)g(nearly)h
(ideal)f(parallelism\).)20 b(Sync)o(hronization)15 b(o)q(ccurs)h(at)f
(bad)g(t)o(yp)q(e)h(2)f(no)q(des,)0 2304 y(where)g(eac)o(h)f(mo)o(v)o
(e)f(is)g(tried)i(in)e(turn)h(in)g(an)g(attempt)f(to)g(\014nd)h(the)h
(cuto\013.)0 2383 y(The)j(Key)h(No)q(de)f(metho)q(d)f(w)o(as)h(sim)o
(ulated)e(using)i(arti\014cial)f(trees,)j(where)f(the)f(score)i(of)d
(the)h(paren)o(t)h(w)o(as)f(similar)d(to)0 2433 y(the)g(score)g(of)f
(the)h(c)o(hildren.)k(The)c(metho)q(d)e(w)o(as)h(compared)g(against)f
(the)i(classical)f Fk(\013\014)j Fp(algorithm.)f(In)e(the)h(sim)o
(ulation,)0 2482 y(eac)o(h)f(message)f(w)o(as)h(assumed)f(to)g(b)q(e)h
(pro)q(cessed)i(in)d(unit)g(time,)f(and)h(some)g(e\013orts)h(w)o(ere)h
(made)d(to)h(sim)o(ulate)f(con)o(ten)o(tion)0 2532 y(for)j(the)g(no)q
(des)h(within)e(the)h(tree.)22 b(Ov)o(er)16 b(10)e(test)i(runs,)g(the)f
(Key)h(No)q(de)f(metho)q(d)f(ac)o(hiev)o(ed)h(a)g(sp)q(eedup)h(of)e
(12.57)g(on)g(20)0 2582 y(pro)q(cessors,)i(using)d(a)h(tree)h(depth)g
(of)e(5)g(and)h(a)g(breadth)g(of)g(4.)0 2661 y(Newb)q(orn's)f(\(1988\))
f(algorithm,)d Fn(Unsynchr)n(onize)n(d)15 b(Iter)n(atively)d(De)n(ep)n
(ening)j(Par)n(al)r(lel)e(A)o(lpha-Beta)g(Se)n(ar)n(ch)p
Fp(,)g(w)o(as)f(the)h(\014rst)p eop
%%Page: 7 7
7 6 bop 467 50 a Fe(A)14 b(T)m(axonom)o(y)d(of)i(P)o(arallel)g(Game-T)m
(ree)g(Searc)o(h)h(Algorithms)465 b Fp(7)0 195 y(attempt)13
b(to)g(async)o(hronously)h(start)g(the)g(next)g(lev)o(el)f(of)g(an)g
(iterativ)o(ely)g(deep)q(ened)i(searc)o(h)g(instead)f(of)f(sync)o
(hronizing)g(at)0 245 y(the)i(ro)q(ot)e(of)h(the)g(game-tree.)k(The)c
(mo)o(v)o(es)f(from)f(the)j(ro)q(ot)f(p)q(osition)f(are)h(partitioned)g
(among)d(the)k(pro)q(cessors,)h(and)d(the)0 295 y(pro)q(cessors)j
(searc)o(h)g(their)e(o)o(wn)g(subset)h(of)f(the)h(mo)o(v)o(es)d(with)i
(iterativ)o(e)g(deep)q(ening.)20 b(Eac)o(h)15 b(pro)q(cessor)g(is)f
(giv)o(en)g(the)h(same)0 345 y(initial)e(windo)o(w,)g(but)h(some)g(of)g
(the)h(pro)q(cessors)i(ma)o(y)12 b(ha)o(v)o(e)j(c)o(hanged)f(their)h
(windo)o(ws,)f(based)h(on)f(the)h(searc)o(h)h(results)g(of)0
394 y(their)e(mo)o(v)o(es.)k(The)c(UIDP)m(ABS)h(algorithm)c(then)k(com)
o(bines)e(the)i(results)g(once)g(a)f(predetermined)g(time)f(limit)f
(has)i(b)q(een)0 444 y(reac)o(hed.)19 b(Some)11 b(of)g(the)i(mo)o(v)o
(es)e(ma)o(y)f(ha)o(v)o(e)i(b)q(een)h(ev)n(aluated)f(to)g(larger)g
(depths)h(than)f(those)h(on)f(other)h(pro)q(cessors,)h(whic)o(h)0
494 y(ma)o(y)e(yield)h(a)h(b)q(etter)h(qualit)o(y)e(mo)o(v)o(e)f(c)o
(hoice.)0 573 y(Sc)o(hae\013er's)h Fn(Dynamic)h(PV-Split)e
Fp(algorithm)d(\(1989\))i(is)h(an)f(enhancemen)o(t)i(that)f(allo)o(ws)e
(for)i(dynamic)e(pro)q(cessor)k(trees)f(in)0 623 y(the)f(PV-Split)e
(framew)o(ork.)16 b(Instead)c(of)e(the)i(\014xed)f(pro)q(cessor)i(tree)
g(mec)o(hanism)8 b(that)j(w)o(as)g(used)h(in)f(PV-Split,)g(pro)q
(cessors)0 672 y(in)h(Dynamic)f(PV-Split)h(\(DPVS\))h(are)h(allo)o(w)o
(ed)d(to)i(dynamically)c(attac)o(h)k(themselv)o(es)g(to)g(other)g(busy)
g(pro)q(cessors,)i(whic)o(h)0 722 y(eac)o(h)21 b(run)g(the)g(PV-Split)e
(algorithm.)35 b(This)20 b(allo)o(ws)g(for)g(parallelism)d(along)i(the)
i(pseudo-principal)f(v)n(ariation)f(\(the)0 772 y(leftmost)g(branc)o
(h\))i(b)q(eing)f(searc)o(hed)h(b)o(y)f(an)o(y)g(pro)q(cessor,)j(and)d
(allo)o(ws)f(for)h(m)o(ultiple)e(split)h(no)q(des.)38
b(The)21 b(pro)q(cess)h(of)0 822 y(c)o(ho)q(osing)11
b(the)i(new)f(split)f(no)q(de)h(started)h(b)o(y)e(allo)q(cating)f
(branc)o(hes)j(at)f(t)o(yp)q(e)g(1)f(or)h(t)o(yp)q(e)g(3)f(no)q(des,)i
(and)e(allo)o(w)o(ed)g(parallelism)0 872 y(at)k(t)o(yp)q(e)h(2)f(no)q
(des)h(once)g(the)g(branc)o(hes)h(from)d(all)g(t)o(yp)q(e)i(1)f(and)g
(3)g(no)q(des)h(w)o(ere)h(allo)q(cated.)22 b(All)14 b(requests)k(for)d
(w)o(ork)g(w)o(en)o(t)0 922 y(through)e(a)g(Con)o(troller)f(pro)q
(cess,)i(whic)o(h)f(w)o(as)g(used)h(to)e(balance)h(the)h(dynamic)d(pro)
q(cessor)k(tree)f(amongst)d(the)j(pro)q(cessors)0 971
y(that)g(had)g(the)g(most)f(w)o(ork)g(to)h(do,)f(as)h(w)o(ell)f(as)h
(assign)g(w)o(ork)g(from)e(the)i(curren)o(t)i(no)q(de)e(on)g(the)g
(principal)f(v)n(ariation.)0 1050 y(Unfortunately)m(,)j(the)h(increase)
h(in)d(searc)o(h)j(o)o(v)o(erhead)f(comp)q(ensated)f(for)g(the)h
(decrease)i(in)d(sync)o(hronization)g(o)o(v)o(erhead.)0
1100 y(The)e(searc)o(h)h(o)o(v)o(erhead)g(arose)f(from)e(additional)g
(pro)q(cessors,)k(once)e(they)h(had)e(b)q(een)i(reassigned,)g
(attempting)d(to)i(searc)o(h)0 1150 y(some)c(subtrees)i(without)f(the)g
(b)q(ene\014t)h(of)d(the)j(ordering)e(information)e(from)h(the)i(searc)
o(hed)h(sibling)d(subtrees.)19 b(By)11 b(allo)o(wing)0
1200 y(a)f(shared)h(T)m(able)f(Manager)g(to)g(handle)g(all)f(transp)q
(osition)h(table)g(requests,)j(along)c(with)h(a)g(mec)o(hanism)d(for)j
(rebroadcasting)0 1249 y(history)19 b(table)h(information,)d(the)j(sp)q
(eedup)h(for)e Fc(P)l(araPhoenix)j Fp(w)o(as)d(impro)o(v)o(ed)f(to)h
(7.64)g(on)g(19)g(pro)q(cessors.)37 b(The)0 1299 y(mec)o(hanism)12
b(describ)q(ed)k(in)e(the)h(pap)q(er)g(tap)q(ered)h(o\013)e(once)h
(more)f(than)g(10)g(pro)q(cessors)j(w)o(ere)e(in)o(v)o(olv)o(ed;)e(the)
i(o)o(v)o(erhead)g(of)0 1349 y(going)e(through)h(a)f(single)h(T)m(able)
f(Manager)h(increased)h(linearly)e(as)h(more)f(pro)q(cessors)j(w)o(ere)
f(added.)0 1428 y(The)c Fn(Enhanc)n(e)n(d)i(PV-Split)d
Fp(algorithm)e(\(Hy)o(att,)i(1988;)g(Hy)o(att,)h(Suter)g(and)g(Nelson,)
g(1989\))e(is)h(a)g(di\013eren)o(t)i(t)o(yp)q(e)f(of)f(dynamic)0
1478 y(allo)q(cation)f(to)h(the)h(PV-Split)f(algorithm.)k(In)d(the)g
(Enhanced)g(PV-Split)f(\(EPVS\))i(algorithm,)c(when)j(a)f(pro)q(cessor)
i(b)q(ecame)0 1528 y(idle,)j(all)e(of)i(the)h(other)g(pro)q(cessors)h
(w)o(ere)f(stopp)q(ed)g(and)f(a)g(new)h(split)f(no)q(de)g(w)o(ould)f(b)
q(e)i(created)h(t)o(w)o(o)e(ply)f(further)i(do)o(wn)0
1577 y(the)f(tree)g(of)e(one)h(of)g(the)g(busy)g(pro)q(cessors.)21
b(All)13 b(pro)q(cessors)j(w)o(ould)d(then)i(start)f(to)g(w)o(ork)g(on)
g(the)g(smaller)f(subtree.)20 b(The)0 1627 y(transp)q(osition)14
b(table)g(ensured)h(that)f(the)h(smaller)d(subtree)k(had)d(not)h(b)q
(een)h(explored)f(y)o(et.)0 1706 y(Using)i(a)g(Sequen)o(t)h(Balance)f
(21000)f(computer,)h(the)h(sp)q(eedup)g(of)f(EPVS)h(w)o(as)f(5.93)e(on)
i(16)g(pro)q(cessors.)27 b(On)16 b(the)h(same)0 1756
y(mac)o(hine)d(and)h(test)h(set,)g(PV-Split)f(ac)o(hiev)o(ed)g(a)g(sp)q
(eedup)i(of)e(4.57)f(on)h(16)f(pro)q(cessors.)24 b(The)16
b(authors)g(p)q(oin)o(t)e(out)h(at)g(the)0 1806 y(end)e(of)f(their)h
(pap)q(er)g(that)f(the)h(a)o(v)o(erage)g(branc)o(hing)f(factor)h(of)e
(a)i(c)o(hess)h(tree)f(is)g(38;)e(their)i(algorithm)d(could)i(not)h
(use)g(64)f(or)0 1856 y(more)g(pro)q(cessors)j(e\013ectiv)o(ely)f
(since)g(all)e(pro)q(cessors)j(co-ordinate)e(at)g(one)h(split)e(no)q
(de)i(at)f(an)o(y)f(giv)o(en)h(time.)j(Th)o(us,)d(to)g(use)0
1905 y(massiv)o(ely)e(parallel)h(arc)o(hitectures)k(\(with)d(h)o
(undreds)h(or)f(thousands)h(of)f(pro)q(cessors\),)i(a)e(greater)h(n)o
(um)o(b)q(er)f(of)f(split)h(no)q(des)0 1955 y(m)o(ust)g(b)q(e)h(a)o(v)n
(ailable)e(for)i(parallel)e(w)o(ork.)0 2116 y Fl(2.4)48
b(The)15 b(Adv)o(en)o(t)f(Of)i(Massiv)o(e)f(P)o(aralleli)o(sm)e(\(July)
h(1987-presen)o(t\))0 2226 y Fp(F)m(elten)19 b(and)g(Otto)h(\(1988\))e
(implemen)o(ted)f(the)j(\014rst)g(parallel)e Fk(\013\014)j
Fp(algorithm)c(that)i(pla)o(y)o(ed)g(c)o(hess)h(on)f(more)f(than)h(32)0
2276 y(pro)q(cessors.)k(Their)15 b Fc(W)-5 b(a)m(yCool)17
b Fp(program)c(decided)j(on)f(the)h(t)o(yp)q(e)f(of)f(parallelism)e(to)
j(b)q(e)h(applied)e(at)h(a)f(no)q(de)i(based)f(on)0 2326
y(whether)f(there)f(w)o(as)f(a)h(transp)q(osition)f(table)g(en)o(try)h
(in)f(the)h(system.)k(If)12 b(a)g(transp)q(osition)g(table)g(en)o(try)h
(w)o(as)f(a)o(v)n(ailable,)e(the)0 2376 y(mo)o(v)o(e)j(stored)i(w)o
(ould)e(lik)o(ely)g(b)q(e)i(the)g(b)q(est)g(mo)o(v)o(e,)e(and)h(it)g(w)
o(as)g(w)o(orth)g(w)o(aiting)f(for)h(a)g(b)q(ound)g(to)h(b)q(e)f
(returned)i(from)d(that)0 2425 y(transp)q(osition)h(table)g(mo)o(v)o
(e.)j(Once)f(that)e(b)q(ound)g(had)g(b)q(een)h(returned)h(\(assuming)d
(that)h(the)h(no)q(de)f(is)g(not)g(immediately)0 2475
y(pruned\),)d(all)d(of)h(the)i(other)f(successors)i(could)e(b)q(e)g
(explored)g(in)f(parallel.)15 b(If)10 b(there)h(is)e(no)g(transp)q
(osition)h(table)f(information,)0 2525 y(all)k(subtrees)j(could)d(b)q
(e)i(computed)e(in)h(parallel.)0 2604 y(The)f(pro)q(cessors)h(are)f
(hierarc)o(hically)e(organized)h(in)o(to)g(a)g(tree)h(structure)h(at)e
(the)h(start)g(of)f(the)g(searc)o(h,)h(but)g(this)f(pro)q(cessor)0
2654 y(tree)19 b(w)o(ould)e(b)q(e)h(restructured)j(as)c(necessary)m(.)
31 b(The)18 b(sc)o(heme)g(relied)g(on)g(a)f(globally)e(shared)k(transp)
q(osition)f(table)f(and)0 2704 y(a)f(load)f(balancing)g(sc)o(heme)i
(that)f(is)g(similar)e(to)i(the)g(one)h(used)g(in)f(EPVS.)g(The)h(load)
e(balancing)g(sc)o(heme)h(reorganized)p eop
%%Page: 8 8
8 7 bop 0 50 a Fp(8)603 b(ICCA)14 b(Journal)f(Submission)601
b(June)15 b(12,)e(1996)0 195 y(searc)o(hers)j(in)o(to)d(new)i(teams)e
(that)h(searc)o(h)h(a)e(\\hot)h(sp)q(ot")g(in)f(parallel.)0
274 y(F)m(eldmann)8 b Fn(et.)17 b(al)k Fp(implem)o(en)o(ted)8
b(a)h(parallel)g Fk(\013\014)j Fp(algorithm)7 b(on)i(a)h(large)f(net)o
(w)o(ork)h(of)f(T)m(ransputers)i(for)e(the)h(c)o(hess)i(program)0
324 y Fc(Zugzw)l(ang)g Fp(\(V)m(orn)o(b)q(erger)g(and)g(Monien,)f
(1987;)g(F)m(eldmann)e Fn(et.)18 b(al)p Fp(,)11 b(1989;)g(F)m(eldmann,)
f(1993\).)16 b(The)c(algorithm)d(in)o(v)o(olv)o(es)0
374 y(the)j(use)g(of)e(the)i Fn(Y)m(oung)h(Br)n(others)e(Wait)i(Conc)n
(ept)e Fp(\(YBW)o(C\))h(to)f(determine)g(when)g(no)q(des)h(can)f(b)q(e)
h(giv)o(en)f(out)g(in)f(a)h(parallel)0 423 y(manner.)0
502 y(In)19 b(a)g(game-tree)g(that)g(has)h(near)f(p)q(erfect)i
(ordering,)f(there)h(is)e(a)g(high)g(probabilit)o(y)e(that)i(a)g(no)q
(de)h(is)f(an)g(all)f(no)q(de)i(if)0 552 y(w)o(e)e(ev)n(aluate)g(the)h
(leftmost)d(branc)o(h)j(and)f(w)o(e)g(ha)o(v)o(e)g(not)g(pruned)h(the)f
(searc)o(h)h(b)q(elo)o(w)f(that)g(no)q(de.)31 b(The)19
b(basic)f(Y)m(oung)0 602 y(Brothers)g(W)m(ait)c(Concept)j(states)h
(that)e(the)h(leftmost)d(branc)o(h)j(\(the)g(eldest)g(brother\))g(m)o
(ust)e(b)q(e)i(ev)n(aluated)f(b)q(efore)g(an)o(y)0 652
y(other)c(branc)o(hes)h(\(the)g(y)o(oung)e(brothers\))i(can)f(b)q(e)g
(distributed)g(to)g(other)g(pro)q(cessors.)19 b(This)12
b(is)f(not)h(necessarily)h(limited)c(to)0 702 y(the)15
b(principal)f(v)n(ariation)f(\(i.e.)20 b(PV-Split\))14
b(or)h(a)f(pseudo-principal)h(v)n(ariation)e(\(i.e.)20
b(DPVS)15 b(or)f(EPVS\);)h(it)g(can)f(happ)q(en)0 751
y(at)h(an)o(y)g(no)q(de)g(within)g(the)g(game-tree.)22
b(The)15 b(algorithm)e(giv)o(en)h(in)h(T)m(ables)g(1)g(and)f(2)h(is)g
(YBW)o(C*.)22 b(This)15 b(v)n(ariation)e(do)q(es)0 801
y(not)j(w)o(ait)f(for)h(y)o(oung)g(brothers)h(at)f(t)o(yp)q(e)h(3)f(no)
q(des)h(and)f(forces)h(sequen)o(tial)f(ev)n(aluation)f(of)g(all)g
(\\reasonable")h(mo)o(v)o(es)f(at)0 851 y(t)o(yp)q(e)f(2)g(no)q(des,)g
(as)g(describ)q(ed)i(in)d(F)m(eldmann's)f(Ph.D.)h(thesis)i(\(1993\).)0
930 y(Hy)o(att)f(in)o(tro)q(duced)g Fn(Dynamic)i(T)m(r)n(e)n(e)e
(Splitting)f Fp(\(DTS\))h(in)f(his)h(Ph.D.)f(thesis)h(\(1988\).)j(One)e
(pro)q(cessor)h(is)d(giv)o(en)h(the)g(ro)q(ot)0 980 y(p)q(osition)h
(and)g(the)h(others)g(m)o(ust)f(try)h(to)f(\014nd)g(a)h(pro)q(cessor)h
(that)e(has)h(w)o(ork)f(to)g(steal.)23 b(If)15 b(a)g(pro)q(cessor)j
(has)d(w)o(ork,)g(DTS)0 1029 y(hands)k(out)f(a)h(branc)o(h)g(from)d
(the)k(lo)o(w)o(est)e(t)o(yp)q(e)h(3)f(no)q(de.)33 b(T)o(yp)q(e)19
b(1)f(no)q(des)h(that)g(ha)o(v)o(e)f(b)q(ound)h(information)d(\(i.e.)31
b(the)0 1079 y(leftmost)13 b(c)o(hild)h(has)g(b)q(een)h(ev)n(aluated\))
f(are)h(considered)h(as)e(t)o(yp)q(e)h(3)f(no)q(des.)19
b(F)m(ailing)12 b(this,)i(the)h(pro)q(cessor)h(will)d(hand)h(out)0
1129 y(an)o(y)f(no)q(de)h(from)e(a)i(t)o(yp)q(e)g(1)f(no)q(de)h(that)g
(do)q(es)g(not)g(ha)o(v)o(e)f(an)o(y)h(b)q(ound)f(information.)i
(Finally)m(,)c(the)k(pro)q(cessor)g(w)o(ould)e(hand)0
1179 y(out)e(branc)o(hes)h(from)d(t)o(yp)q(e)i(2)f(no)q(des)i(that)f
(ha)o(v)o(e)f(not)h(b)q(een)h(pruned)f(after)g(the)h(\014rst)f(c)o
(hild)f(has)h(b)q(een)h(completely)e(ev)n(aluated.)0
1229 y(This)17 b(mak)o(es)f(the)i(algorithm)d(similar)g(\(in)h
(parallelization)g(and)h(sync)o(hronization)g(c)o(haracteristics\))i
(to)e(YBW)o(C*,)h(but)0 1279 y(allo)q(cates)c(the)g(w)o(ork)g(in)f(a)h
(di\013eren)o(t)h(order)f(than)g(YBW)o(C*)g(w)o(ould.)0
1357 y(In)c(the)g(implemen)o(tation,)d(split)i(p)q(oin)o(ts)h(w)o(ere)g
(placed)g(in)f(shared)i(memory)c(so)j(that)g(other)g(pro)q(cessors)i
(had)e(an)f(opp)q(ortunit)o(y)0 1407 y(to)16 b(tak)o(e)g(branc)o(hes)h
(without)f(a)g(pro)q(cessor)h(con)o(tin)o(ually)e(lo)q(oking)f(for)i(w)
o(ork)g(to)g(do.)24 b(Using)16 b(a)f(Sequen)o(t)i(Balance)g(21000,)0
1457 y(DTS)d(generated)h(an)e(a)o(v)o(erage)h(sp)q(eed-up)i(of)d(8.81)g
(o)o(v)o(er)g(16)h(pro)q(cessors.)0 1536 y Fn(Bound-and-Br)n(anch)f
Fp(\(F)m(erguson)e(and)g(Korf,)g(1988\))e(is)i(a)f(pro)q(cessor)j(allo)
q(cation)c(sc)o(heme)i(in)f(the)i(Distributed)f(T)m(ree)g(Searc)o(h)0
1586 y(framew)o(ork)d({)i(a)g(general)g(framew)o(ork)e(for)i
(distributed)h(searc)o(h)g({)f(to)f(searc)o(h)j Fk(\013\014)g
Fp(trees)f(generated)h(b)o(y)e(an)f(Othello)h(program.)0
1636 y(If)k(no)h(cuto\013)g(b)q(ound)g(exists)g(at)f(a)h(no)q(de,)g
(all)e(pro)q(cessors)k(are)e(assigned)g(to)f(the)h(\014rst)h(c)o(hild)e
(to)g(generate)i(a)f(cuto\013)g(b)q(ound)0 1685 y(as)j(quic)o(kly)f(as)
h(p)q(ossible.)29 b(If)18 b(a)f(cuto\013)i(b)q(ound)e(exists,)i(or)f
(has)g(b)q(een)h(established)f(b)o(y)g(completing)e(the)i(searc)o(h)h
(of)e(the)0 1735 y(\014rst)e(c)o(hild,)f(the)h(pro)q(cessors)h(are)f
(allo)q(cated)f(in)g(a)g(breadth-\014rst)i(manner)d(to)h(all)g
(remaining)e(c)o(hildren.)20 b(E\013ectiv)o(ely)m(,)14
b(this)0 1785 y(sc)o(heme)f(giv)o(es)g(the)g(same)f(parallelism)e(and)j
(sync)o(hronization)g(pattern)h(describ)q(ed)g(in)f(the)g(YBW)o(C*)g
(algorithm.)i(F)m(or)d(the)0 1835 y(Bound-and-Branc)o(h)f(pro)q(cessor)
h(allo)q(cation)d(sc)o(heme,)h(F)m(erguson)h(and)f(Korf)g(get)h(sp)q
(eedups)h(of)e(12)f(while)h(studying)g(Othello)0 1885
y(trees)16 b(using)e(a)h(32-pro)q(cessor)g(h)o(yp)q(ercub)q(e.)22
b(The)15 b(searc)o(h)h(is)e(facilitated)g(b)o(y)g(a)h(distributed)g
(\\game-tree)f(represen)o(tation")0 1934 y(whic)o(h)g(is)g(similar)d
(to)j(a)f(transp)q(osition)h(table,)f(and)h(iterativ)o(e)g(deep)q
(ening.)0 2013 y(Hsu)i(describ)q(ed)h(a)e Fn(queue)n(d)i(pr)n(o)n(c)n
(essor)f(arr)n(ay)g(mo)n(del)f Fp(for)g(implemen)o(ting)d(a)j(parallel)
g Fk(\013\014)i Fp(algorithm)c(within)i(the)h(second)0
2063 y(v)o(ersion)g(of)f(Deep)h(Though)o(t)f(\(1990\).)23
b(The)16 b(host)g(w)o(orkstation)f(tra)o(v)o(erses)i(the)g(tree)f
(according)g(to)g(the)g(algorithm)d(un)o(til)0 2113 y(the)h
(parallelization)e(horizon)i(is)f(reac)o(hed.)20 b(The)14
b(subproblems)f(are)i(then)f(placed)g(on)g(to)f(a)h(queue)g(that)g(can)
g(b)q(e)h(accessed)0 2163 y(b)o(y)g(a)h(large)f(n)o(um)o(b)q(er)g(of)g
(sp)q(ecialized)h(VLSI)g(pro)q(cessors.)25 b(All)15 b(of)g(the)h(pro)q
(cessors)i(are)e(connected)h(b)o(y)e(the)h(same)f(bus)h(to)0
2213 y(this)i(queue.)31 b(The)18 b(pro)q(cessors)i(tak)o(e)e(a)o(w)o(a)
o(y)f(the)i(subproblems)e(placed)h(on)g(the)g(queue,)i(run)e(the)g
(silicon-enco)q(ded)h Fk(\013\014)0 2262 y Fp(routine)c(on)f(the)i(c)o
(hip,)e(and)h(return)h(the)f(results)h(to)f(another)g(queue)g(on)g(the)
g(bus)g(that)g(go)q(es)g(in)g(to)f(the)i(host)f(pro)q(cessor.)0
2312 y(The)f(results)h(are)g(then)f(added)g(to)g(the)h(tree)g(represen)
o(tation)g(in)f(the)g(host)g(computer.)0 2391 y(Hsu)i(also)f(in)o(tro)q
(duced)h(the)g Fn(delaye)n(d)h(br)n(anch)g(tr)n(e)n(e)e(exp)n(ansion)i
Fp(\(DBTE\))f(algorithms)d(in)i(his)h(thesis.)23 b(These)17
b(algorithms)0 2441 y(generate)f(t)o(w)o(o)e(queues)i(of)e(no)q(des.)20
b(The)15 b(\014rst)h(queue)f(is)g(a)f(set)h(of)f(no)q(des)i(that)e
(corresp)q(ond)i(to)f(the)g Fk(\013\014)i Fp(minim)o(al)11
b(tree,)k(in)0 2491 y(a)e(left-to-righ)o(t)f(order.)19
b(The)14 b(second)g(queue)g(con)o(tains)f(no)q(des)h(that)g(are)g(not)f
(in)g(the)g Fk(\013\014)j Fp(minim)o(al)10 b(tree,)k(b)q(ecause)h(of)e
(p)q(o)q(or)0 2540 y(mo)o(v)o(e)g(ordering)h(at)g(t)o(yp)q(e)h(2)f(no)q
(des.)21 b(The)15 b(minim)o(al)c(tree)k(queue)g(is)g(used)g(only)f
(when)g(the)h(queue)h(of)d(additional)g(w)o(ork)h(at)0
2590 y(failed)f(t)o(yp)q(e)h(2)g(no)q(des)h(is)e(empt)o(y)m(.)k(This)d
(setup)h(allo)o(ws)d(for)i(parallelism)d(at)j(t)o(yp)q(e)g(1)g(and)f(3)
h(no)q(des.)0 2669 y(There)d(is)g(a)f(family)d(of)j(DBTE)g(algorithms)e
(based)j(on)f(the)h(c)o(hoice)g(of)f(CUT)g(no)q(des)h(to)f(re-expand.)
18 b(One)11 b(of)f(the)h(algorithms,)p eop
%%Page: 9 9
9 8 bop 467 50 a Fe(A)14 b(T)m(axonom)o(y)d(of)i(P)o(arallel)g(Game-T)m
(ree)g(Searc)o(h)h(Algorithms)465 b Fp(9)0 195 y(the)13
b(Leftmost)e(First)h(algorithm,)e(is)i(sho)o(wn)g(to)g(b)q(e)g
(asymptotically)e(optimal)f(on)j(b)q(est-\014rst)i(trees)g(as)e(w)o
(ell)g(as)g(dominating)0 245 y(w)o(eak)f Fk(\013\014)i
Fp(\(a)e(v)o(ersion)h(of)e(the)i Fk(\013\014)h Fp(algorithm)c(whic)o(h)
h(only)h(has)g(shallo)o(w)f(cuto\013s\).)18 b(The)12
b(Leftmost)e(First)h(algorithm)e(causes)0 295 y(sync)o(hronization)j
(to)f(o)q(ccur)i(at)e(bad)g(t)o(yp)q(e)h(2)g(no)q(des.)18
b(Sim)o(ulations)9 b(rep)q(ort)j(that)g(a)f(sp)q(eedup)i(of)e(350)g
(with)g(1000)g(pro)q(cessors)0 345 y(is)j(p)q(ossible,)f(once)i(the)f
(mac)o(hine)f(is)h(completely)e(constructed.)0 423 y(Lu)19
b(\(1993\))g(implemen)o(ted)e(a)i(pair)g(of)g(impro)o(v)o(emen)o(ts)e
(to)i(the)i(basic)e(PV-Split)g(algorithm)e(for)i(use)h(in)f(the)h(c)o
(hec)o(k)o(ers)0 473 y(program)13 b Fc(Chinook)p Fp(.)21
b(T)m(o)14 b(prev)o(en)o(t)i(starv)n(ation)e(when)h(exploring)f(c)o
(hec)o(k)o(ers)i(trees,)g(whic)o(h)f(ha)o(v)o(e)f(an)h(a)o(v)o(erage)f
(branc)o(hing)0 523 y(factor)d(of)g(3)g(instead)h(of)f(the)h(38)e
(found)h(in)g(c)o(hess)i(trees,)g Fn(fr)n(ontier)f(splitting)e
Fp(w)o(as)h(prop)q(osed)i(and)e(tested.)19 b(F)m(ron)o(tier)11
b(splitting)0 573 y(creates)18 b(m)o(ultiple)d(split)h(no)q(des)h
(further)h(up)f(the)g(v)n(ariation)e(b)q(eing)h(explored)h(b)o(y)g(the)
g(Con)o(troller)f(pro)q(cess)j(as)d(they)i(are)0 623
y(required.)33 b(This)18 b(is)h(di\013eren)o(t)g(than)f(algorithms)f
(lik)o(e)g(YBW)o(C*,)i(whic)o(h)g(concen)o(trate)h(on)e(creating)h(new)
g(split)f(no)q(des)0 672 y(underneath)g(the)g(curren)o(t)g(split)e(no)q
(de.)28 b(Split)16 b(no)q(des)i(are)f(created)h(\014rst)g(at)f(all)e
(no)q(des)j(and)f(only)f(at)g(cut)i(no)q(des)f(when)0
722 y(there)e(is)g(no)e(parallelism)f(left)i(at)g(an)o(y)g(all)f(no)q
(des.)19 b(The)c(dra)o(wbac)o(k)f(is)g(that)g(the)h(searc)o(h)g(migh)o
(t)d(b)q(e)j(started)h(without)d(an)o(y)0 772 y(b)q(ound)j
(information.)23 b(Essen)o(tially)m(,)15 b(this)i(remo)o(v)o(es)f(the)g
(sync)o(hronization)h(for)f(a)g(giv)o(en)g(depth)h(searc)o(h,)g(and)f
(allo)o(ws)f(for)0 822 y(parallelism)c(at)j(an)o(y)f(no)q(de)i(within)e
(the)h(tree.)0 901 y(An)h(implemen)o(tati)o(on)d(of)i(dynamic)f(load)h
(balancing,)f(similar)f(to)j(the)g(EPVS)g(metho)q(d,)f(w)o(as)g(also)g
(presen)o(ted.)23 b Fn(Str)n(aggler)0 951 y(pr)n(e)n(emption)13
b Fp(gathers)g(a)f(group)h(of)f(idle)g(pro)q(cessors)j(and)e(assigns)f
(them)g(to)h(a)f(subtree)j(that)d(has)h(b)q(een)h(w)o(ork)o(ed)f(on)f
(b)o(y)h(one)0 1000 y(pro)q(cessor)j(for)f(a)f(long)f(p)q(erio)q(d)i
(of)f(time.)19 b(Both)c(of)f(the)h(impro)o(v)o(em)o(en)o(ts)e(w)o(ere)i
(tested)h(and)f(the)g(sp)q(eedup)h(on)e(the)h(test)h(set)0
1050 y(impro)o(v)o(ed)11 b(from)g(1.92)h(on)h(16)f(pro)q(cessors)k(for)
c(the)i(basic)f(PV-Split)f(algorithm)f(to)i(3.31)e(on)i(16)g(pro)q
(cessors.)20 b(The)13 b(a)o(v)o(erage)0 1100 y(branc)o(hing)f(factor)h
(of)f(the)h(trees)h(b)q(eing)f(explored)g(w)o(as)f(2.78;)g(although)f
(the)j(magnitude)d(of)h(the)h(increase)h(w)o(as)e(small,)e(the)0
1150 y(fact)k(that)g(the)g(sp)q(eedup)i(is)e(larger)f(than)h(the)h
(branc)o(hing)e(factor)h(is)g(signi\014can)o(t.)0 1229
y(Da)o(vid's)d Fk(\013\014)r Fp(*)i(\(1993\))f(is)g(a)h(new)g(t)o(yp)q
(e)g(of)f(arc)o(hitecture)i(for)f(dealing)e(whic)o(h)i(requires)h(a)e
(shared)i(transp)q(osition)e(table.)18 b(All)0 1279 y(pro)q(cessors)f
(start)e(at)g(the)g(ro)q(ot)g(of)f(the)i(tree)g(and)e(start)h(tra)o(v)o
(elling)f(do)o(wn)g(the)i(tree.)21 b(Ho)o(w)o(ev)o(er,)15
b(the)h(pro)q(cessors)h(explore)0 1328 y(di\013eren)o(t)12
b(parts)g(of)f(the)g(tree)i(based)f(on)f(results)h(from)d(the)j(shared)
g(transp)q(osition)g(table.)17 b(Eac)o(h)11 b(en)o(try)h(con)o(tains)f
(a)g(coun)o(ter)0 1378 y(of)17 b(ho)o(w)f(man)o(y)g(pro)q(cessors)j
(are)e(exploring)g(the)h(subtree)h(ro)q(oted)e(at)g(that)g(no)q(de.)29
b(Th)o(us,)17 b(the)h(pro)q(cessor)h(can)f(disco)o(v)o(er)0
1428 y(whic)o(h)c(no)q(des)g(ha)o(v)o(e)g(b)q(een)h(ev)n(aluated.)0
1507 y(A)h(depth-limited)f(searc)o(h)i(is)f(executed)i(at)d(non-PV)i
(no)q(des)f(to)g(determine)g(whether)i(the)e(no)q(de)h(is)f(a)f(t)o(yp)
q(e)i(2)f(or)g(a)f(t)o(yp)q(e)0 1557 y(3)i(no)q(de.)27
b(T)o(yp)q(e)17 b(2)g(no)q(des)g(are)g(searc)o(hed)i(sequen)o(tially)m
(,)d(as)h(in)f(other)i(algorithms.)24 b(A)o(t)17 b(t)o(yp)q(e)h(3)e(no)
q(des,)i(the)f(n)o(um)o(b)q(er)g(of)0 1606 y(pro)q(cessors)g(allo)o(w)o
(ed)c(to)h(explore)g(a)g(subtree)i(is)f(limited)d(b)o(y)i(a)g(constan)o
(t)h(factor)f(of)g(the)g(n)o(um)o(b)q(er)g(of)g(pro)q(cessors)i(that)f
(are)0 1656 y(curren)o(tly)i(at)f(the)g(t)o(yp)q(e)g(3)g(no)q(de.)24
b(F)m(or)16 b(the)g(purp)q(oses)i(of)d Fk(\013\014)r
Fp(*,)h(once)g(the)h(leftmost)d(c)o(hild)i(of)f(a)h(t)o(yp)q(e)g(1)g
(no)q(de)g(has)g(b)q(een)0 1706 y(ev)n(aluated,)e(the)i(t)o(yp)q(e)f(1)
g(no)q(de)g(e\013ectiv)o(ely)h(b)q(ecomes)f(a)g(t)o(yp)q(e)g(3)g(no)q
(de.)21 b(Once)16 b(a)f(pro)q(cessor)i(has)e(visited)g(a)f(no)q(de,)h
(it)g(ma)o(y)0 1756 y(not)h(go)g(bac)o(k)h(ab)q(o)o(v)o(e)f(that)h(no)q
(de)f(un)o(til)g(the)h(no)q(de)g(is)f(ev)n(aluated)h(\(i.e.)25
b(the)17 b(correct)h Fk(\013\014)h Fp(information)14
b(is)i(kno)o(wn)g(ab)q(out)0 1806 y(the)g(v)n(alue)f(at)g(that)g(no)q
(de\).)24 b(This)15 b(means)f(that)i(as)f(so)q(on)h(as)f(one)h(pro)q
(cessor)h(has)f(\\ev)n(aluated")e(the)i(ro)q(ot,)g(the)g(searc)o(h)g
(is)0 1856 y(completed.)h(One)c(adv)n(an)o(tage)e(of)h(the)g
Fk(\013\014)r Fp(*)h(algorithm)c(is)j(the)h(parallel)e(co)q(de)i(in)o
(v)o(olv)o(es)e(only)g(a)h(small)e(n)o(um)o(b)q(er)i(of)f(c)o(hanges)0
1905 y(to)16 b(the)h(sequen)o(tial)f(co)q(de)h(\(W)m(eill,)e(1995\).)24
b(In)16 b(his)h(thesis,)g(Da)o(vid)e(ac)o(hiev)o(ed)h(a)g(sp)q(eedup)i
(of)e(6.5)f(on)h(16)g(T)m(ransputers.)26 b(8)0 1955 y(of)14
b(the)i(T)m(ransputers)g(w)o(ere)f(used)h(to)f(con)o(trol)f(the)i
(shared)g(transp)q(osition)e(table,)h(while)f(the)h(other)h(8)e(w)o
(ere)i(used)g(as)f(tree)0 2005 y(searc)o(hers.)0 2084
y Fn(CABP)g Fp(is)h(an)f(algorithm)d(b)o(y)k(Cung)f(\(1994\),)f(based)i
(on)g(the)g(Deep)g(Though)o(t)f(design)g(presen)o(ted)j(b)o(y)d(Hsu)h
(\(1990\).)22 b(The)0 2134 y(algorithm)8 b(w)o(as)j(designed)g(for)f(a)
h(shared)g(memory)e(system,)h(and)h(main)o(tains)d(a)j(shared)g
(\\score)h(tree")g(for)e(the)h(en)o(tire)h(game-)0 2183
y(tree)18 b(and)f(the)h(t)o(w)o(o)e(lists)h(of)g(w)o(ork:)24
b(critical)17 b(no)q(des)g(one)h(ply)e(ab)q(o)o(v)o(e)h(the)h(lea)o(v)o
(es,)f(and)g(non-critical)f(c)o(hildren)i(of)e(failed)0
2233 y(cut-no)q(des.)j(A)o(t)13 b(failed)f(cut-no)q(des,)h(the)h
(non-critical)e(c)o(hildren)h(are)g(added)g(to)g(the)g(list)f
Fk(k)i Fp(at)f(a)f(time.)17 b(\(In)12 b(the)i(sim)o(ulation)0
2283 y(results)e(giv)o(en)e(in)g(the)h(thesis,)g Fk(k)i
Fp(=)f(1.\))k(In)11 b(his)f(Ph.D.)g(thesis,)h(Cung)g(sho)o(ws)f(the)h
(CABP)h(algorithm)7 b(generating)k(a)f(sp)q(eedup)0 2333
y(of)i(4.6)g(on)h(strongly-ordered)h(trees)g(with)f(a)g(branc)o(hing)g
(factor)f(of)h(40)f(using)h(9)g(pro)q(cessors)i(on)e(a)f(Sequen)o(t)i
(Balance)f(8000.)0 2412 y(Kuszmaul)f(\(1994\))h(presen)o(ts)i
Fn(Jamb)n(or)n(e)n(e)e(se)n(ar)n(ch)g Fp(in)g(his)g(Ph.D.)f(thesis)i
(as)f(an)g(algorithm)e(for)h(testing)i(MIMD)f(sc)o(heduling)0
2462 y(algorithms)e(on)j(the)g(CM-5.)k(Jam)o(b)q(oree)13
b(searc)o(h)i(is)f(a)f(parallelization)f(of)h(NegaScout)h(searc)o(h)h
(whic)o(h)f(b)q(eha)o(v)o(es)g(with)g(only)0 2511 y(a)f(few)g(minor)f
(di\013erences)j(to)f(the)g(w)o(ork)f(done)g(b)o(y)g(F)m(eldmann)f
Fn(et.)18 b(al)13 b Fp(on)g(the)h(Y)m(oung)f(Brothers)i(W)m(ait)d
(algorithm.)j(In)e(the)0 2561 y(Y)m(oung)h(Brothers)i(W)m(ait)e
(algorithm,)d(when)16 b(a)e(subtree)j(is)d(giv)o(en)g(to)h(a)f(pro)q
(cessor)j(and)d(the)i(searc)o(h)g(fails)d(high,)h(the)h(sla)o(v)o(e)0
2611 y(pro)q(cessor)j(immediately)c(pro)q(ceeds)k(to)f(w)o(ork)f(out)h
(the)g(v)n(alue)f(with)g(the)h(full)f(searc)o(h)h(windo)o(w)f(without)h
(informing)c(the)0 2661 y(master)h(pro)q(cessor.)23 b(In)15
b(Jam)o(b)q(oree)g(searc)o(h,)h(a)f(fail)e(high)h(v)n(alue)g(is)h
(returned)i(to)e(the)g(master)g(pro)q(cessor.)23 b(This)15
b(prev)o(en)o(ts)p eop
%%Page: 10 10
10 9 bop 0 50 a Fp(10)592 b(ICCA)14 b(Journal)f(Submission)591
b(June)15 b(12,)e(1996)0 195 y(an)o(y)i(y)o(ounger)i(subtrees)h(from)c
(executing)j(a)e(full)g(windo)o(w)g(searc)o(h)i(un)o(til)e(the)i(new)f
(b)q(ound)g Fk(\013)g Fp(can)g(b)q(e)h(established)g(b)o(y)e(a)0
245 y(full)e(windo)o(w)g(searc)o(h.)0 324 y(W)m(eill)c(in)o(tro)q
(duced)j(an)e(impro)o(v)o(emen)o(t)f(to)h(the)i Fk(\013\014)r
Fp(*)f(algorithm)d(in)i(his)h(Ph.D.)f(thesis)i(\(1995\).)k(W)m(eill)9
b(suggested)k(and)d(tested)0 374 y(a)g(decision)h(metho)q(d)f(based)i
(on)e(the)i(Y)m(oung)e(Brothers)i(W)m(ait,)d(instead)j(of)e(the)h
(depth-limited)e(searc)o(h)j(and)f(constan)o(t)g(factor)0
423 y(at)i(t)o(yp)q(e)h(3)f(no)q(des)h(tested)g(b)o(y)f(Da)o(vid.)k(A)o
(t)c(an)o(y)g(no)q(de)g(in)g(the)h Fk(\013\014)r Fp(*)f(algorithm,)d
(if)j(the)g(leftmost)f(c)o(hild)h(isn't)g(ev)n(aluated,)f(all)0
473 y(pro)q(cessors)18 b(m)o(ust)d(ev)n(aluate)g(the)i(leftmost)d(c)o
(hild.)23 b(Once)17 b(the)f(leftmost)f(c)o(hild)g(is)h(ev)n(aluated,)f
(pro)q(cessors)j(are)e(allo)q(cated)0 523 y(to)i(non-ev)n(aluated)f
(idle)g(c)o(hildren)h(\014rst,)h(and)e(then)i(allo)q(cated)e(in)g(a)h
(balanced)f(manner)g(to)h(the)g(other)g(non-ev)n(aluated)0
573 y(c)o(hildren)13 b(in)g(the)g(tree.)19 b(Although)12
b(b)q(oth)h Fk(\013\014)r Fp(*)g(and)g(YBW)o(C*)g(use)h(the)f(same)f
(decision)h(metho)q(d)f(for)h(allo)o(wing)d(or)j(den)o(ying)0
623 y(parallelism,)g Fk(\013\014)r Fp(*)j(uses)g(a)g(shared)g(transp)q
(osition)g(table)f(to)g(k)o(eep)i(the)f(pro)q(cessors)i(w)o(orking)c
(on)i(di\013eren)o(t)g(parts)g(of)f(the)0 672 y(tree,)g(while)e(YBW)o
(C*)h(uses)h(master-sla)o(v)o(e)e(relationships.)0 751
y(In)g(a)g(later)g(pap)q(er)h(\(W)m(eill,)d(1996\),)h(the)i(com)o
(bined)e(metho)q(d)g(w)o(as)h(called)g Fn(A)o(lpha-B)o(^)-20
b(eta)15 b(Distribut)o(\023)-20 b(e)13 b(ave)n(c)i(Dr)n(oit)e(d'A)1828
742 y(^)1830 751 y(inesse)p Fp(,)0 801 y(or)k(ABD)o(AD)o(A.)f(He)i(sho)
o(w)o(ed)f(that)g(ABD)o(AD)o(A)g(yields)f(greater)i(sp)q(eedups)h(than)
e(YBW)o(C)g(on)g(a)f(CM-5)h(when)g(studying)0 851 y(c)o(hess)j(trees.)
35 b(ABD)o(AD)o(A)19 b(also)g(yields)f(similar)f(sp)q(eedups)k(to)e
(YBW)o(C)g(when)g(studying)g Fk(\013\014)i Fp(trees)g(generated)f(b)o
(y)f(an)0 901 y(Othello)14 b(program.)0 980 y Fn(Dynamic)i(Multiple)e
(Princip)n(al)g(V)m(ariation)g(Splitting)g Fp(\(DM-PVSplit\))f(is)h(a)g
(v)n(ariation)e(of)h(the)h(PV-Split)g(algorithm)d(that)0
1029 y(allo)o(ws)18 b(for)h(greater)h(parallelism)c(near)k(the)f(start)
h(of)f(a)g(searc)o(h)h(\(Marsland)f(and)g(Gao,)g(1995\).)33
b(T)m(o)18 b(understand)i(the)0 1079 y(algorithm,)12
b(it)i(is)h(necessary)i(to)d(de\014ne)i(the)g Fn(PV)f(set)p
Fp(.)21 b(The)15 b(ro)q(ot)g(is)g(a)f(mem)o(b)q(er)f(of)i(the)g(PV)g
(set.)22 b(A)o(t)15 b(subsequen)o(t)h(lev)o(els,)0 1129
y(no)q(des)f(are)f(part)g(of)g(the)g(PV)h(set)g(if)e(the)h(paren)o(t)h
(is)f(a)g(mem)o(b)q(er)e(of)h(the)i(PV)f(set,)h(and)f(they)g(are)h
(generated)g(b)o(y)f(the)g(\014rst)h Fk(k)0 1179 y Fp(candidate)g(mo)o
(v)o(es)f(in)h(the)g(mo)o(v)o(e)f(list)h(of)f(the)i(paren)o(t.)22
b(The)16 b(determination)d(of)i Fk(k)h Fp(is)f(giv)o(en)f(b)o(y)h(a)g
(function,)g(not)g(a)g(\014xed)0 1229 y(n)o(um)o(b)q(er.)i(Th)o(us,)c
(the)g(PV)g(set)h(is)e(a)h(righ)o(t-pruned)g(v)o(ersion)g(of)f(the)h
(game-tree.)18 b(An)13 b(appropriate)f(c)o(hoice)i(of)e(the)h
(heuristic)0 1279 y(guess)h(allo)o(ws)d(for)i(greater)g(parallelism)d
(without)j(adv)o(ersely)g(increasing)g(the)g(searc)o(h)h(o)o(v)o
(erhead,)f(since)h(the)f(correct)i(mo)o(v)o(e)0 1328
y(at)g(a)g(PV)h(set)g(no)q(de)g(is)g(highly)e(lik)o(ely)g(to)h(app)q
(ear)h(in)f(its)g(PV)h(set)g(c)o(hildren.)23 b(By)16
b(alw)o(a)o(ys)e(selecting)i(only)f(one)h(candidate)0
1378 y(mo)o(v)o(e,)10 b(DM-PVSplit)h(generalizes)h(in)o(to)f(PV-Split.)
17 b(Since)12 b(the)g(PV)g(set)h(do)q(es)f(not)f(resp)q(ect)j(the)f
(structure)g(of)e(the)h(minima)o(l)0 1428 y(tree,)18
b(the)f(last)g(t)o(w)o(o)f(columns)f(in)i(T)m(able)e(2)i(re\015ect)h
(this)f(b)o(y)f(referring)i(to)e(the)h(PV)g(set,)h(and)f(not)f(Kn)o
(uth)h(and)g(Mo)q(ore's)0 1478 y(classi\014cation)d(of)f(minim)o(al)d
(tree)15 b(no)q(des.)0 1557 y(The)c(algorithm)e(is)h(designed)i(for)f
(use)g(on)g(strongly)g(ordered)h(trees.)19 b(In)11 b(the)g(pap)q(er,)h
(Marsland)f(and)f(Gao)g(sho)o(w)h(the)h(results)0 1606
y(of)i(an)g(exp)q(erimen)o(t)g(where)i(DM-PVSplit)d(generates)j(a)e(sp)
q(eedup)i(of)e(appro)o(ximately)e(32)i(o)o(v)o(er)g(64)g(pro)q
(cessors,)i(using)e(an)0 1656 y(arti\014cially)e(generated)k(tree)f(of)
e(width)h(32)f(and)h(depth)g(8.)0 1735 y Fn(Asynchr)n(onous)21
b(Par)n(al)r(lel)f(Hier)n(ar)n(chic)n(al)f(Iter)n(ative)g(De)n(ep)n
(ening)i Fp(is)f(an)g(attempt)f(to)h(extend)g(the)h(ideas)f(of)f(Newb)q
(orn's)0 1785 y(UIDP)m(ABS)c(algorithm)e(for)i(use)h(on)f(a)g(net)o(w)o
(ork)h(of)f(w)o(orkstations,)g(where)h(the)g(cost)g(of)f(comm)o
(unicatio)o(n)e(is)i(prohibitiv)o(e)0 1835 y(\(Bro)q(c)o(kington)j(and)
f(Sc)o(hae\013er,)i(1996\).)28 b(Instead)19 b(of)e(using)g(a)g(single)g
(ply)g(of)g(the)h(game-tree)f(to)h(generate)g(w)o(ork)g(lists,)0
1885 y(APHID)h(uses)h(a)f(truncated)h(game-tree)e(of)h(user-de\014ned)i
(depth,)f(and)f(all)e(lea)o(v)o(es)i(of)f(the)i(truncated)g(game-tree)f
(are)0 1934 y(allo)q(cated)c(to)g(sla)o(v)o(e)g(pro)q(cessors.)24
b(The)16 b(master)e(pro)q(cessors)k(within)c(the)i(hierarc)o(h)o(y)g
(con)o(tin)o(ually)d(searc)o(h)k(the)f(truncated)0 1984
y(game-tree)g(to)g(add,)f(delete)j(and)d(up)q(date)i(the)g(priorit)o(y)
e(of)g(w)o(ork)h(for)g(the)g(sla)o(v)o(es.)25 b(The)16
b(sla)o(v)o(e)g(pro)q(cessors)i(searc)o(h)g(their)0 2034
y(w)o(ork)12 b(lists)f(with)h(minim)o(al)c(sync)o(hronization)k(from)e
(the)j(master.)k(The)12 b(sla)o(v)o(es)g(determine)g(their)g(o)o(wn)f
(w)o(ork)h(sc)o(hedule)h(and)0 2084 y(inform)e(the)k(master)e(pro)q
(cessors)j(of)d(the)h(searc)o(h)h(results.)k(Sla)o(v)o(e)13
b(pro)q(cessors)j(can)e(con)o(tin)o(ue)g(searc)o(hing)g(the)g(next)g
(lev)o(el)g(of)0 2134 y(the)g(iterativ)o(e)g(deep)q(ening)h(searc)o(h)g
(sp)q(eculativ)o(ely)f(if)f(they)i(ha)o(v)o(e)e(no)h(w)o(ork)g(left)f
(to)h(do)g(at)f(the)i(curren)o(t)g(lev)o(el.)0 2213 y(The)e(APHID)f
(algorithm)e(has)j(b)q(een)g(implemen)o(ted)d(as)j(a)f(game-indep)q
(enden)o(t)g(library)g(that)g(can)h(b)q(e)g(easily)f(inserted)i(in)o
(to)0 2262 y(a)e(sequen)o(tial)g(game-pla)o(ying)c(program.)16
b(The)d(library)e(has)h(b)q(een)h(tested)g(on)f(b)q(oth)g
Fc(Key)m(ano)i Fp(\(an)e(Othello)g(program\))e(and)0
2312 y Fc(TheTurk)k Fp(\(a)g(c)o(hess)h(program\).)h(A)o(t)e(time)e(of)
h(writing,)g(the)h(APHID)g(algorithm)d(ac)o(hiev)o(es)j(sp)q(eedups)h
(of)e(8.41)g(and)g(6.02)0 2362 y(for)h Fc(Key)m(ano)i
Fp(and)d Fc(TheTurk)i Fp(\(resp)q(ectiv)o(ely\))g(on)f(a)g(net)o(w)o
(ork)g(of)f(16)g(Sparc-2)h(w)o(orkstations.)0 2529 y
Fl(3)48 b(OTHER)16 b(SEAR)o(CH)g(P)l(ARADIGMS)f(F)o(OR)g(P)l(ARALLEL)g
(GAME-TREE)i(SEAR)o(CH)0 2654 y Fp(Although)e(the)h(emphasis)f(has)h(b)
q(een)h(on)e Fk(\013\014)r Fp(-based)h(metho)q(ds,)g(there)g(are)h
(other)f(searc)o(h)h(strategies)f(that)g(can)g(b)q(e)g(used)0
2704 y(to)e(generate)i(the)f(minima)o(x)d(v)n(alue.)19
b(They)c(ha)o(v)o(e)g(b)q(een)g(sub)q(divided)g(in)o(to)f(three)i
(subsections.)22 b(The)15 b(\014rst)g(will)e(deal)h(with)p
eop
%%Page: 11 11
11 10 bop 456 50 a Fe(A)14 b(T)m(axonom)o(y)d(of)j(P)o(arallel)e
(Game-T)m(ree)h(Searc)o(h)i(Algorithms)454 b Fp(11)0
195 y(parallel)11 b(algorithms)g(based)i(on)f(the)h(original)e(form)o
(ulation)e(of)j Fk(S)r(S)r(S)r Fj(\003)p Fp(.)20 b(The)13
b(second)h(subsection)f(will)f(deal)g(with)g(the)h Fk(E)r(R)0
245 y Fp(metho)q(d,)f(while)g(the)h(\014nal)f(subsection)i(will)d(deal)
i(v)o(ery)g(brie\015y)g(with)f(purely)h(theoretical)g(mo)q(dels)f(for)g
(game-tree)g(searc)o(h.)0 450 y Fl(3.1)48 b(P)o(arallel)13
b(Searc)o(h)h(based)h(on)g Fk(S)r(S)r(S)r Fj(\003)0 569
y Fp(Sto)q(c)o(kman)g(\(1979\))h(in)o(tro)q(duced)h(the)g
Fk(S)r(S)r(S)r Fj(\003)h Fp(algorithm.)23 b(Initially)m(,)14
b(it)i(w)o(as)g(b)q(eliev)o(ed)h(that)f(the)h(algorithm)d(dominated)0
619 y Fk(\013\014)19 b Fp(in)d(the)h(sense)h(that)f Fk(S)r(S)r(S)r
Fj(\003)i Fp(will)c(not)h(searc)o(h)i(a)e(no)q(de)h(if)f
Fk(\013\014)i Fp(did)f(not)f(searc)o(h)i(it.)25 b(A)17
b(p)q(erceiv)o(ed)h(problem)d(with)h(the)0 669 y(algorithm)e(is)j(that)
g(a)g(list)f(structure)k(\(the)d Fb(OPEN)f Fp(list\))h(m)o(ust)f(b)q(e)
i(main)o(tained,)d(whic)o(h)i(could)f(gro)o(w)h(to)g
Fk(b)1713 654 y Fa(d=)p Fm(2)1783 669 y Fp(elemen)o(ts,)0
719 y(where)f Fk(b)e Fp(is)h(the)g(branc)o(hing)g(factor)g(and)f
Fk(d)h Fp(is)f(the)i(depth)f(of)f(the)i(tree)g(to)f(b)q(e)g(searc)o
(hed.)22 b(This)15 b(space)h(requiremen)o(t)f(w)o(as,)0
769 y(at)e(the)g(time,)e(considered)j(to)f(b)q(e)g(to)q(o)g(large)f
(for)g(a)h(practical)f(c)o(hess-pla)o(ying)h(program.)j(F)m
(urthermore,)c(ev)o(en)i(if)e(the)h(space)0 818 y(requiremen)o(t)18
b(w)o(as)f(not)h(a)g(problem,)f(the)h(main)o(tenance)f(of)g(the)i
Fb(OPEN)d Fp(list)i(slo)o(w)o(ed)f(do)o(wn)h(the)g(algorithm)d(to)j
(mak)o(e)e(it)0 868 y(slo)o(w)o(er)e(than)g Fk(\013\014)i
Fp(in)d(practice.)0 947 y(A)f(theoretical)g(parallel)f
Fk(S)r(S)r(S)r Fj(\003)j Fp(algorithm)9 b(w)o(as)i(prop)q(osed)i
(\(Campb)q(ell,)d(1981;)h(Campb)q(ell)e(and)j(Marsland,)f(1983\),)g
(based)0 997 y(on)i(breaking)g(the)g(tree)i(in)o(to)d(stages)i(to)f
(reduce)i(the)e(cost)h(of)f(main)o(taini)o(ng)d(the)k
Fb(OPEN)e Fp(list.)17 b(A)o(t)d(the)f(end)h(of)e(a)h(stage)h(in)e(the)0
1047 y(searc)o(h,)j(the)f(no)q(de)h(w)o(ould)e(b)q(e)i(handed)f(to)g(a)
g(sla)o(v)o(e)g(pro)q(cessor)i(in)d(the)i(tree)g(hierarc)o(h)o(y)m(.)k
(This)14 b(limited)e(the)i(depth)h Fk(d)p Fp(,)f(th)o(us)0
1097 y(prev)o(en)o(ting)i(the)h Fb(OPEN)e Fp(list)h(from)e(b)q(ecoming)
h(to)q(o)h(large.)25 b(The)16 b(staged)h Fk(S)r(S)r(S)r
Fj(\003)h Fp(algorithm)c(is)h(sho)o(wn)i(to)f(b)q(e)g(marginally)0
1146 y(faster)f(than)e(either)i(tree)g(splitting)e(or)h(PV-Split)f(on)h
(randomly)e(ordered)j(trees)g(in)f(Campb)q(ell's)e(w)o(ork.)0
1225 y(Leifk)o(er)k(and)g(Kanal)f(\(1985\))g(prop)q(ose)i(the)f(HYBRID)
g(algorithm)d(that)j(is)g(based)g(on)g(the)g(problem)f(heap)h(from)e
Fk(S)r(S)r(S)r Fj(\003)p Fp(,)0 1275 y(but)20 b(con)o(tains)f(no)g
(details)g(p)q(ertaining)g(to)g(an)g(implemen)o(tation.)31
b(V)m(orn)o(b)q(erger)20 b(and)f(Monien)g(presen)o(ted)j(the)e(results)
0 1325 y(of)14 b(a)h(parallel)f Fk(S)r(S)r(S)r Fj(\003)j
Fp(algorithm)c(\(1987\),)h(but)h(the)h(results)g(w)o(ere)g(disapp)q
(oin)o(ting)d(when)j(compared)e(to)h(the)h(parallel)e
Fk(\013\014)0 1375 y Fp(algorithm)9 b(\(later)i(to)g(b)q(e)h(called)f
(\\Y)m(oung)f(Brothers)j(W)m(ait"\).)i(Their)d(implemen)o(tatio)o(n)d
(of)h(parallel)g Fk(S)r(S)r(S)r Fj(\003)k Fp(on)d(a)f(lo)q(cal)h(area)0
1424 y(net)o(w)o(ork)j(of)f(PCs)i(had)e(a)h(searc)o(h)h(o)o(v)o(erhead)
f(of)g(o)o(v)o(er)f(300)h(p)q(ercen)o(t)h(when)g(using)e(16)h(pro)q
(cessors.)20 b(Dideric)o(h)14 b(describ)q(ed)h(an)0 1474
y(implemen)o(tatio)o(n)c(of)j(Sync)o(hronized)h(Distributed)f(State)g
(Space)h(Searc)o(h)g(\()p Fk(S)r(D)q(S)r(S)r(S)s Fj(\003)p
Fp(\))h(\(1992\))e(and)f(ac)o(hiev)o(ed)i(a)e(sp)q(eedup)0
1524 y(of)g(11.40)g(using)g(32)h(pro)q(cessors,)h(searc)o(hing)g(a)e(5)
h(ply)f(tree)i(with)f(a)f(branc)o(hing)h(factor)g(of)f(16.)0
1603 y(There)k(are)f(some)e(other)i Fk(S)r(S)r(S)r Fj(\003)i
Fp(algorithms)13 b(b)o(y)i(Hiromoto)f Fn(et)i(al.)23
b Fp(\(1987\),)14 b(Kraas)i(\(1990\),)f(and)g(Shinghal)f(and)i(Sh)o(v)o
(ed)0 1653 y(\(1991\),)f(and)h(all)f(of)g(the)i(w)o(ork)e(deals)h(with)
g(ho)o(w)f(to)h(parallelize)f(w)o(ork)h(based)g(on)g(the)h
Fb(OPEN)e Fp(list.)23 b(Although)16 b(the)g(w)o(ork)0
1703 y(has)g(sho)o(wn)f(some)g(promise)f(in)i(eliminating)c(the)k
(di\016culties)f(of)g(dealing)g(with)g(an)g(ordered)i(problem)d(heap,)i
(all)e(of)h(the)0 1752 y(w)o(ork)i(on)f(handling)g(the)i
Fb(OPEN)e Fp(list)g(has)h(b)q(een)h(made)e(obsolete.)28
b(This)17 b(is)g(due)g(to)g(the)g(rev)o(elation)g(that)g
Fk(S)r(S)r(S)r Fj(\003)i Fp(can)e(b)q(e)0 1802 y(implemen)o(ted)e(as)i
(a)g(series)h(of)f(n)o(ull-windo)o(w)e Fk(\013\014)k
Fp(calls,)e(using)g(a)g(transp)q(osition)g(table)g(in)f(the)i(place)f
(of)g(the)g Fb(OPEN)f Fp(list)0 1852 y(\(Plaat,)d(1995\).)0
2057 y Fl(3.2)48 b(P)o(arallel)13 b(Searc)o(h)h(based)h(on)g
Fk(E)r(R)0 2176 y Fp(Stein)o(b)q(erg)g(and)f(Solomon)d(\(1990\))j
(presen)o(ted)i(the)e Fk(E)r(R)g Fp(metho)q(d)g(of)f(searc)o(hing)i
(game-trees.)j Fk(E)r(R)c Fp(stands)h(for)f(Ev)n(aluate-)0
2226 y(Refute,)20 b(and)f(it)g(attempts)f(to)h(ev)n(aluate)g(some)f
(mandatory)g(w)o(ork)g(b)q(efore)i(attempting)e(to)h(refute)h(the)g
(other)f(mo)o(v)o(es)0 2276 y(within)e(the)g(tree.)30
b(A)o(t)17 b(a)g(no)q(de)h(to)f(b)q(e)h(ev)n(aluated)f(\(an)g(e-no)q
(de\))h(within)f(the)h(tree,)g(the)g Fk(E)r(R)f Fp(algorithm)e(ev)n
(aluates)i(the)0 2326 y(elder)g(grandc)o(hildren)f(\(concurren)o(tly)m
(,)h(if)f(p)q(ossible\),)h(and)f(then)g(c)o(ho)q(oses)i(the)f(c)o(hild)
e(with)h(largest)h(elder)g(grandc)o(hild)e(to)0 2376
y(b)q(e)f(the)g(e-c)o(hild.)k(This)13 b(e-c)o(hild)g(is)g(ev)n
(aluated,)g(and)g(then)i(the)f(other)g(c)o(hildren)f(of)g(the)h(e-no)q
(de)g(are)g(refuted.)19 b(The)14 b(metho)q(d)0 2425 y(is)f(less)h
(e\016cien)o(t)g(at)g(searc)o(hing)f(trees)i(than)f(the)g
Fk(\013\014)i Fp(algorithm)10 b(since)15 b(it)e(misses)g(some)f(deep)j
(cuto\013s.)j(F)m(urthermore,)13 b(the)0 2475 y(algorithm)e(w)o(as)j
(not)g(tested)h(with)f(iterativ)o(e)g(deep)q(ening)h(or)e(minima)o(l)e
(windo)o(ws)i(when)i(refuting)e(e-no)q(des.)0 2554 y(The)21
b Fk(E)r(R)f Fp(metho)q(d)g(and)h(PV-Split)f(w)o(ere)h(implemen)o(ted)e
(as)h(problem-heap)g(algorithms)e(on)i(a)h(Sequen)o(t)g(Symmetry)0
2604 y(m)o(ultipro)q(cessor.)k(Stein)o(b)q(erg)17 b(and)f(Solomon)e
(found)i(that)h(they)g(ac)o(hiev)o(ed)f(a)h(b)q(etter)h(e\016ciency)f
(with)f(the)h(parallel)e Fk(E)r(R)0 2654 y Fp(algorithm)10
b(than)j(with)f(PV-Split.)17 b(The)c Fk(E)r(R)f Fp(metho)q(d)g(ac)o
(hiev)o(ed)h(a)f(sp)q(eedup)j(of)d(10)g(with)g(16)g(pro)q(cessors,)j
(and)d(a)g(sp)q(eedup)0 2704 y(of)h(14.7)g(with)g(27)h(pro)q(cessors.)p
eop
%%Page: 12 12
12 11 bop 0 50 a Fp(12)592 b(ICCA)14 b(Journal)f(Submission)591
b(June)15 b(12,)e(1996)0 195 y Fl(3.3)48 b(Theoretical)13
b(P)o(arallel)g(Searc)o(h)i(Metho)q(ds)0 303 y Fp(There)i(are)g(a)f(n)o
(um)o(b)q(er)g(of)f(theoretical)i(algorithms)d(that,)i(to)h(the)f
(author's)h(kno)o(wledge,)f(ha)o(v)o(en't)g(b)q(een)h(programmed.)0
353 y(Karp)c(and)g(Zhang)h(\(1989\))e(and)h(Alth\177)-21
b(ofer)13 b(\(1993\))f(ha)o(v)o(e)h(prop)q(osed)h(algorithms)d(that)j
(will)d(yield)i(linear)g(sp)q(eedups)i(in)d(the)0 402
y(n)o(um)o(b)q(er)17 b(of)f(pro)q(cessors,)k(giv)o(en)d(trees)i(of)e
Fk(O)q Fp(\()p Fk(N)12 b Fp(log)6 b Fk(N)f Fp(\))18 b(or)f
Fk(O)q Fp(\()p Fk(N)5 b Fp(\))17 b(depth,)i(resp)q(ectiv)o(ely)m(.)29
b(Bro)q(der)19 b Fn(et)f(al.)28 b Fp(\(1990\))17 b(ha)o(v)o(e)0
452 y(sho)o(wn)12 b(that)g(for)g(an)o(y)f(parallel)g(tree)i(searc)o
(hing)f(algorithm,)e(there)j(exists)g(a)e(tree)i(instance)g(that)f(do)q
(es)h(not)f(run)g(in)g(p)q(olylog)0 502 y(parallel)18
b(run-time.)32 b(Bro)q(der)20 b Fn(et)f(al.)33 b Fp(also)18
b(sho)o(w)h(and)g(pro)o(v)o(e)g(an)g(upp)q(er)h(b)q(ound)f(on)f(the)i
(run-time)e(of)g(the)h(P)o(arHop)q(e)0 552 y(algorithm.)0
703 y Fl(4)48 b(CONCLUSIONS)0 825 y Fp(The)19 b(taxonom)o(y)d(giv)o(en)
i(in)g(section)h(2)f(sho)o(ws)h(that)f(there)i(are)f(a)f(n)o(um)o(b)q
(er)g(of)f(algorithms)f(whic)o(h)j(are)g(similar)c(to)k(one)0
875 y(another.)29 b(There)19 b(are)f(only)e(subtle)i(di\013erences)i(b)
q(et)o(w)o(een)f(a)e(large)g(n)o(um)o(b)q(er)g(of)g(the)h
Fk(\013\014)r Fp(-based)g(algorithms.)27 b(Most)18 b(of)0
925 y(these)h(di\013erences)g(are)e(due)h(to)f(the)h(di\013eren)o(t)g
(arc)o(hitectures)h(and)e(game)f(trees)i(studied.)29
b(This)17 b(comparison)e(is)i(easily)0 974 y(made)c(through)h(the)g
(separation)g(of)f(the)i(implemen)o(tatio)o(n)c(and)j(algorithmic)d
(details.)0 1053 y(As)17 b(the)h(n)o(um)o(b)q(er)e(of)g(pro)q(cessors)j
(a)o(v)n(ailable)c(to)i(the)g(programmers)e(has)i(increased,)h(dynamic)
e(algorithms)e(ha)o(v)o(e)j(tak)o(en)0 1103 y(the)i(place)f(of)g(the)h
(earlier)f(algorithms)e(whic)o(h)i(o\013ered)i(limited)c(parallelism)f
(on)j(a)g(large)g(n)o(um)o(b)q(er)g(of)g(pro)q(cessors.)33
b(It)0 1153 y(is)16 b(the)h(author's)g(b)q(elief)f(that)h(sp)q
(eculativ)o(e)g(parallelism)d(is)i(necessary)j(to)d(yield)g
(near-linear)g(p)q(erformance)h(on)f(parallel)0 1203
y(arc)o(hitectures,)g(and)d(is)h(the)h(sub)r(ject)g(of)e(on-going)g
(researc)o(h)i(at)f(the)h(Univ)o(ersit)o(y)e(of)h(Alb)q(erta.)0
1354 y Fl(5)48 b(A)o(CKNO)o(WLEDGEMENTS)0 1476 y Fp(The)19
b(author)g(w)o(ould)g(lik)o(e)f(to)h(thank)f(Yngvi)h(Bjornsson,)h
(Rainer)f(F)m(eldmann,)f(Y)m(ao)q(qing)f(Gao,)i(Andreas)h(Junghanns,)0
1526 y(T)m(on)o(y)14 b(Marsland,)f(Ask)o(e)j(Plaat,)d(Jonathan)h(Sc)o
(hae\013er,)i(Jean-Christophe)g(W)m(eill)c(and)j(the)g(editorial)e
(sta\013)i(of)f(the)h(ICCA)0 1575 y(Journal)d(for)g(their)h(helpful)f
(commen)o(ts)f(on)h(the)i(revisions)e(of)g(this)h(pap)q(er.)18
b(The)13 b(author)g(is)f(b)q(eing)h(funded)g(b)o(y)f(an)g(NSER)o(C)0
1625 y(P)o(ostgraduate)i(Sc)o(holarship,)g(for)f(whic)o(h)h(the)g
(author)g(is)g(extremely)g(grateful.)0 1704 y(The)g(author)g(w)o(ould)f
(appreciate)i(an)o(y)e(corrections,)i(suggestions)g(and)e(impro)o(v)o
(emen)o(ts)f(that)i(y)o(ou)f(ma)o(y)f(ha)o(v)o(e.)0 1847
y Fl(References)21 1953 y Fp(Akl,)j(S.)h(G.,)f(Barnard,)h(D.)f(T.,)h
(and)g(Doran,)f(R.)g(J.)h(\(1982\).)23 b(Design,)16 b(Analysis)g(and)f
(Implemen)o(tation)e(of)i(a)h(P)o(arallel)21 1994 y(T)m(ree)g(Searc)o
(h)h(Algorithm.)k Fn(IEEE)c(T)m(r)n(ansactions)g(on)g(Pattern)g(A)o
(nalysis)f(and)h(Machine)h(Intel)r(ligenc)n(e)p Fp(,)e(V)m(ol.)e(P)m
(AMI-4,)21 2036 y(No.)f(2,)g(pp.)h(192{203.)21 2119 y(Alth\177)-21
b(ofer,)13 b(I.)f(\(1993\).)17 b(A)c(P)o(arallel)f(Game)g(T)m(ree)i
(Searc)o(h)g(Algorithm)d(with)i(a)g(Linear)g(Sp)q(eedup.)18
b Fn(Journal)c(of)h(A)o(lgorithm)p Fp(,)21 2161 y(V)m(ol.)d(15,)h(pp.)g
(175{198.)21 2245 y(Bal,)f(H.)h(E.)g(and)f(v)n(an)h(Renesse,)h(R.)e
(\(1986\).)k(A)d(Summary)e(of)h(P)o(arallel)g(Alpha-Beta)h(Searc)o(h)h
(Results.)j Fn(ICCA)d(Journal)p Fp(,)21 2286 y(V)m(ol.)e(9,)h(No.)g(3,)
h(pp.)f(146{149.)21 2370 y(Baudet,)j(G.)f(M.)g(\(1978\).)22
b Fn(The)16 b(Design)h(and)g(Analysis)f(of)h(Algorithms)e(for)h
(Asynchr)n(onous)h(Multipr)n(o)n(c)n(essors)p Fp(.)22
b(Ph.D.)21 2412 y(thesis,)14 b(Carnegie)g(Mellon)f(Univ)o(ersit)o(y)m
(,)g(Pittsburgh,)h(P)m(A.)k(Av)n(ailable)12 b(as)i(T)m(ec)o(h.)g(Rept.)
g(CMU-CS-78-116.)21 2495 y(Bro)q(c)o(kington,)g(M.)g(G.)f(and)i(Sc)o
(hae\013er,)g(J.)f(\(1996\).)19 b(APHID)c(Game-Tree)e(Searc)o(h.)21
b(Presen)o(ted)c(at)d Fn(A)n(dvanc)n(es)i(in)f(Com-)21
2537 y(puter)f(Chess)h(8)p Fp(,)f(Maastric)o(h)o(t.)21
2621 y(Bro)q(der,)19 b(A.,)f(Karlin,)g(A.,)g(Ragha)o(v)n(an,)e(P)m(.,)i
(and)g(Upfal,)f(E.)h(\(1990\).)29 b(On)18 b(the)g(Parallel)f(Complexit)
o(y)e(of)j(Ev)n(aluating)21 2662 y(Game-Trees.)g(T)m(ec)o(hnical)c(Rep)
q(ort)h(RR)e(RJ)h(7729,)f(IBM)h(T.)g(J.)g(W)m(atson)g(Researc)o(h)h
(Cen)o(ter,)g(Y)m(orkto)o(wn)e(Heigh)o(ts,)h(New)21 2704
y(Y)m(ork.)p eop
%%Page: 13 13
13 12 bop 456 50 a Fe(A)14 b(T)m(axonom)o(y)d(of)j(P)o(arallel)e
(Game-T)m(ree)h(Searc)o(h)i(Algorithms)454 b Fp(13)21
195 y(Brudno,)17 b(A.)f(L.)g(\(1963\).)26 b(Bounds)17
b(and)f(V)m(aluations)g(for)g(Abridging)g(the)h(Searc)o(h)g(for)g
(Estimates.)25 b Fn(Pr)n(oblems)17 b(of)g(Cy-)21 237
y(b)n(ernetics)p Fp(,)d(V)m(ol.)f(10,)h(pp.)g(225{241.)19
b(T)m(ranslation)14 b(of)g(Russian)h(original)d(in)j
Fn(Pr)n(oblemy)g(Kib)n(ernetiki)p Fp(,)f(10:141{150,)d(Ma)o(y)21
278 y(1963.)21 356 y(Campb)q(ell,)i(M.)j(S.)f(\(1981\).)22
b Fn(A)o(lgorithms)16 b(for)g(the)g(Par)n(al)r(lel)g(Se)n(ar)n(ch)g(of)
h(Game)g(Tr)n(e)n(es)p Fp(.)22 b(M.Sc.)15 b(thesis,)h(Departmen)o(t)g
(of)21 397 y(Computing)f(Science,)k(Univ)o(ersit)o(y)e(of)f(Alb)q
(erta,)i(Edmon)o(ton,)e(Alta.)28 b(Av)n(ailable)15 b(as)j(T)m(ec)o(h.)f
(Rep.)f(TR)h(81-8,)g(Dept.)g(of)21 439 y(Computing)12
b(Science.)21 516 y(Campb)q(ell,)e(M.)h(S.)g(and)h(Marsland,)g(T.)f(A.)
g(\(1983\).)j(A)e(Comparison)e(of)h(Minimax)e(T)m(ree)k(Searc)o(h)f
(Algorithms.)h Fn(A)o(rti\014cial)21 557 y(Intel)r(ligenc)n(e)p
Fp(,)g(V)m(ol.)f(20,)h(pp.)h(347{367.)21 635 y(Ciancarini,)g(P)m(.)h
(\(1994\).)22 b(Distributed)16 b(Searc)o(hes:)23 b(A)16
b(Basis)g(for)f(Comparison.)21 b Fn(ICCA)16 b(Journal)p
Fp(,)f(V)m(ol.)f(17,)h(No.)g(4,)g(pp.)21 676 y(194{206.)21
754 y(Cung,)h(V.-D.)f(\(1994\).)24 b Fn(Contribution)17
b(\022)-21 b(a)18 b(l'A)o(lgorithmique)d(Non)j(Num)o(\023)-20
b(erique)17 b(Par)n(al)r(l)o(\022)-20 b(ele:)22 b(Explor)n(ation)17
b(d'Esp)n(ac)n(es)h(de)21 795 y(R)n(e)n(cher)n(che)p
Fp(.)g(Ph.D.)13 b(thesis,)h(Univ)o(ersit)o(\023)-20 b(e)15
b(P)o(aris)f(VI.)21 873 y(Da)o(vid,)f(V.)h(\(1993\).)20
b Fn(A)o(lgorithmique)15 b(p)n(ar)n(al)r(l)o(\022)-20
b(ele)15 b(sur)g(les)g(arbr)n(es)g(de)h(d)o(\023)-20
b(ecision)16 b(et)g(r)n(aisonnement)g(en)g(temps)g(c)n(ontr)n(aint)f(-)
21 914 y(Etude)g(et)g(applic)n(ation)g(au)g(minimax)p
Fp(.)j(Ph.D.)13 b(thesis,)i(ENSAE,)f(T)m(oulouse,)f(F)m(rance.)21
992 y(Dideric)o(h,)f(C.)g(G.)g(\(1992\).)j(Ev)n(aluation)c(des)i(P)o
(erformances)g(de)g(l'Algorithm)o(e)d(SSS*)j(a)o(v)o(ec)g(Phases)g(de)g
(Sync)o(hronisation)21 1033 y(sur)j(une)g(Mac)o(hine)f(P)o(arall)o
(\022)-20 b(ele)15 b(\022)-21 b(a)15 b(M)o(\023)-20 b(emoires)14
b(Distribu)o(\023)-20 b(ees.)23 b(T)m(ec)o(hnical)15
b(Rep)q(ort)h(LITH-99,)e(Swiss)i(F)m(ederal)f(Institute)i(of)21
1075 y(T)m(ec)o(hnology)m(,)12 b(Lausanne,)i(Switzerland.)21
1152 y(F)m(eldmann,)26 b(R.)f(\(1993\).)53 b Fn(Spielb)n(aumsuche)27
b(mit)e(massiv)h(p)n(ar)n(al)r(lelen)f(Systemen)p Fp(.)54
b(Ph.D.)25 b(thesis,)k(Univ)o(ersit\177)-21 b(at-)21
1194 y(Gesam)o(tho)q(c)o(hsc)o(h)o(ule)13 b(P)o(aderb)q(orn,)i(P)o
(aderb)q(orn,)f(German)o(y)m(.)21 1271 y(F)m(eldmann,)j(R.,)h(Monien,)h
(B.,)g(Mysliwietz,)g(P)m(.,)f(and)g(V)m(orn)o(b)q(erger,)i(O.)e
(\(1989\).)31 b(Distributed)19 b(Game)e(T)m(ree)i(Searc)o(h.)21
1312 y Fn(ICCA)14 b(Journal)p Fp(,)f(V)m(ol.)g(12,)f(No.)i(2,)f(pp.)g
(65{73.)21 1390 y(F)m(elten,)g(E.)g(W.)g(and)h(Otto,)f(S.)g(W.)g
(\(1988\).)k(Chess)d(on)g(a)f(Hyp)q(ercub)q(e.)19 b(In)14
b(G.)f(F)m(o)o(x,)f(editor,)h Fn(Pr)n(o)n(c)n(e)n(e)n(dings)i(of)f(The)
h(Thir)n(d)21 1431 y(Confer)n(enc)n(e)e(on)i(Hyp)n(er)n(cub)n(e)e
(Concurr)n(ent)h(Computers)f(and)i(Applic)n(ations)p
Fp(,)d(v)o(olume)f(I)q(I-Applications,)g(pp.)i(1329{1341,)21
1473 y(P)o(assadena,)h(CA.)21 1550 y(F)m(erguson,)g(C.)f(and)h(Korf,)f
(R.)h(E.)f(\(1988\).)18 b(Distributed)c(T)m(ree)h(Searc)o(h)g(and)f
(its)g(Application)f(to)g(Alpha-Beta)h(Pruning.)21 1592
y(In)g Fn(Pr)n(o)n(c)n(e)n(e)n(dings)g(of)h(AAAI-88)p
Fp(,)e(pp.)h(128{132,)e(Sain)o(t)h(P)o(aul,)g(MN.)21
1669 y(Fink)o(el,)f(R.)g(A.)h(and)g(Fish)o(burn,)g(J.)g(P)m(.)g
(\(1982\).)j(P)o(arallelism)11 b(in)h(Alpha-Beta)i(Searc)o(h.)k
Fn(A)o(rti\014cial)13 b(Intel)r(ligenc)n(e)p Fp(,)f(V)m(ol.)g(19,)21
1711 y(No.)h(1,)g(pp.)h(89{106.)21 1788 y(Hiromoto,)i(U.,)j(Masafumi,)d
(Y.,)j(Masaharu,)g(I.,)f(and)g(T)m(oshihide,)g(I.)f(\(1987\).)30
b(P)o(arallel)18 b(Searc)o(hes)h(of)f(Game)e(T)m(rees.)21
1830 y Fn(Systems)f(and)h(Computers)e(in)h(Jap)n(an)p
Fp(,)f(V)m(ol.)e(18,)h(No.)g(8,)h(pp.)f(97{109.)21 1907
y(Hsu,)20 b(F.-h.)e(\(1990\).)31 b Fn(L)n(ar)n(ge)19
b(Sc)n(ale)h(Par)n(al)r(lelization)e(of)h(A)o(lpha-Beta)h(Se)n(ar)n
(ch:)28 b(A)o(n)19 b(A)o(lgorithmic)g(and)h(A)o(r)n(chite)n(ctur)n(al)
21 1949 y(Study)p Fp(.)28 b(Ph.D.)16 b(thesis,)i(Carnegie)f(Mellon)f
(Univ)o(ersit)o(y)m(,)h(Pittsburgh,)h(U.S.A.)26 b(Also)17
b(T)m(ec)o(h.)f(Rept.)h(CMU-CS-90-108,)21 1990 y(Carnegie)d(Mellon)f
(Univ)o(ersit)o(y)m(,)g(F)m(eb.)g(1990.)21 2067 y(Hy)o(att,)i(R.)g(M.)g
(\(1988\).)22 b Fn(A)16 b(High-Performanc)n(e)g(Par)n(al)r(lel)g(A)o
(lgorithm)f(T)m(o)h(Se)n(ar)n(ch)h(Depth-F)m(rist)e(Game)i(T)m(r)n(e)n
(es)p Fp(.)22 b(Ph.D.)21 2109 y(thesis,)14 b(Univ)o(ersit)o(y)g(of)f
(Alabama,)e(Birmingham,)f(U.S.A.)21 2186 y(Hy)o(att,)15
b(R.)f(M.,)h(Suter,)h(B.)f(W.,)f(and)h(Nelson,)h(H.)f(L.)f(\(1989\).)22
b(A)15 b(P)o(arallel)f(Alpha/Beta)h(T)m(ree)h(Searc)o(hing)g
(Algorithm.)21 2228 y Fn(Par)n(al)r(lel)e(Computing)p
Fp(,)f(V)m(ol.)g(10,)g(No.)g(3,)g(pp.)g(299{308.)21 2305
y(Karp,)i(R.)f(M.)h(and)g(Zhang,)g(Y.)g(\(1989\).)22
b(On)15 b(Parallel)f(Ev)n(aluation)g(of)h(Game)e(Trees.)24
b(In)15 b Fn(Pr)n(o)n(c)n(e)n(e)n(dings)h(of)g(SP)m(AA)g('89)p
Fp(,)21 2347 y(pp.)d(409{420,)f(New)i(Y)m(ork,)f(NY.)h(A)o(CM)g(Press.)
21 2424 y(Kn)o(uth,)f(D.)f(E.)g(and)h(Mo)q(ore,)g(R.)f(W.)f(\(1975\).)
16 b(An)d(Analysis)f(of)g(Alpha-Beta)h(Pruning.)j Fn(A)o(rti\014cial)d
(Intel)r(ligenc)n(e)p Fp(,)f(V)m(ol.)g(6,)21 2466 y(No.)h(3,)g(pp.)h
(293{326.)21 2543 y(Kraas,)e(H.-J.)f(\(1990\).)j Fn(Zur)f(Par)n(al)r
(lelisierung)f(des)h(SSS*-A)o(lgorithmus)p Fp(.)i(Ph.D.)c(thesis,)i(TU)
f(of)f(Braunsc)o(h)o(w)o(eig,)i(Braun-)21 2585 y(sc)o(h)o(w)o(eig,)g
(German)o(y)m(.)21 2662 y(Kuszmaul,)h(B.)h(C.)f(\(1994\).)21
b Fn(Synchr)n(onize)n(d)c(MIMD)g(Computing)p Fp(.)k(Ph.D.)15
b(thesis,)g(Massac)o(h)o(usetts)i(Institute)f(of)f(T)m(ec)o(h-)21
2704 y(nology)m(,)c(Cam)o(bridge,)h(MA.)p eop
%%Page: 14 14
14 13 bop 0 50 a Fp(14)592 b(ICCA)14 b(Journal)f(Submission)591
b(June)15 b(12,)e(1996)21 195 y(Leifk)o(er,)f(D.)g(B.)h(and)f(Kanal,)g
(L.)g(N.)h(\(1985\).)i(A)e(Hybrid)f(SSS*/Alpha-Beta)h(Algorithm)d(for)i
(P)o(arallel)g(Searc)o(h)i(of)e(Game)21 237 y(T)m(rees.)19
b(In)14 b Fn(Pr)n(o)n(c)n(e)n(e)n(dings)g(of)h(IJCAI-85)p
Fp(,)e(pp.)h(1044{1046.)21 311 y(Lindstrom,)d(G.)g(\(1983\).)k(The)e
(Key)h(No)q(de)f(Metho)q(d:)18 b(A)12 b(Highly-P)o(arallel)e
(Alpha-Beta)j(Algorithm.)g(T)m(ec)o(hnical)g(Rep)q(ort)21
353 y(UUCS)h(83-101,)e(Univ)o(ersit)o(y)i(of)f(Utah,)g(Departmen)o(t)h
(of)f(Computer)g(Science,)i(Salt)e(Lak)o(e)h(Cit)o(y)m(,)e(UT.)21
428 y(Lu,)20 b(C.-P)m(.)e(P)m(.)g(\(1993\).)33 b Fn(Par)n(al)r(lel)19
b(Se)n(ar)n(ch)h(of)g(Narr)n(ow)e(Game)i(Tr)n(e)n(es)p
Fp(.)33 b(M.Sc.)19 b(thesis,)i(Departmen)o(t)d(of)h(Computing)21
469 y(Science,)c(Univ)o(ersit)o(y)e(of)h(Alb)q(erta,)g(Edmon)o(ton,)d
(Canada.)21 544 y(Marsland,)j(T.)h(A.)g(\(1983\).)21
b(Relativ)o(e)14 b(E\016ciency)h(of)g(Alpha-Beta)g(Implemen)o(tations.)
k(In)c Fn(Pr)n(o)n(c)n(e)n(e)n(dings)h(of)g(IJCAI-83)p
Fp(,)21 585 y(pp.)d(763{766,)f(Karlsruhe,)i(German)o(y)m(.)21
660 y(Marsland,)k(T.)f(A.)h(and)f(Campb)q(ell,)g(M.)g(S.)g(\(1982\).)29
b(Parallel)17 b(Searc)o(h)i(of)e(Strongly)g(Ordered)j(Game)c(Trees.)31
b Fn(A)o(CM)21 702 y(Computing)15 b(Surveys)p Fp(,)f(V)m(ol.)e(14,)h
(No.)g(4,)g(pp.)h(533{551.)21 776 y(Marsland,)h(T.)f(A.)h(and)g(Gao,)f
(Y.)h(\(1995\).)22 b(Sp)q(eculativ)o(e)15 b(P)o(arallelism)e(Impro)o(v)
o(es)h(Searc)o(h?)30 b(T)m(ec)o(hnical)15 b(Rep)q(ort)h(95{05,)21
818 y(Departmen)o(t)d(of)g(Computing)f(Science,)j(Univ)o(ersit)o(y)f
(of)f(Alb)q(erta,)h(Edmon)o(ton,)e(Alta.)21 892 y(Marsland,)19
b(T.)g(A.,)g(Olafsson,)h(M.,)g(and)e(Sc)o(hae\013er,)k(J.)d(\(1985\).)
32 b(Multipro)q(cessor)21 b(Tree-Searc)o(h)g(Exp)q(erimen)o(ts.)33
b(In)21 934 y(D.)13 b(Beal,)g(editor,)h Fn(A)n(dvanc)n(es)h(in)g
(Computer)g(Chess)g(4)p Fp(,)e(pp.)h(37{51.)e(P)o(ermagon)h(Press,)i
(Oxford.)21 1009 y(Marsland,)j(T.)f(A.)h(and)f(P)o(op)q(o)o(wic)o(h,)h
(F.)f(\(1985\).)29 b(Parallel)17 b(Game-Tree)g(Searc)o(h.)31
b Fn(IEEE)19 b(T)m(r)n(ansactions)f(on)h(Pattern)21 1050
y(A)o(nalysis)14 b(and)i(Machine)g(Intel)r(ligenc)n(e)p
Fp(,)d(V)m(ol.)f(P)m(AMI-7,)h(No.)h(4,)f(pp.)g(442{452.)21
1125 y(Newb)q(orn,)g(M.)e(M.)h(\(1985\).)i(A)f(P)o(arallel)e(Searc)o(h)
i(Chess)g(Program.)h(In)e Fn(Pr)n(o)n(c)n(e)n(e)n(dings)h(of)g(the)h(A)
o(CM)f(A)o(nnual)h(Confer)n(enc)n(e)p Fp(,)21 1166 y(pp.)f(272{277.)21
1241 y(Newb)q(orn,)h(M.)f(M.)h(\(1988\).)j(Unsync)o(hronized)e
(Iterativ)o(e)f(Deep)q(ening)h(P)o(arallel)d(Alpha-Beta)i(Searc)o(h.)19
b Fn(IEEE)c(T)m(r)n(ansac-)21 1283 y(tions)g(on)g(Pattern)g(A)o
(nalysis)f(and)i(Machine)g(Intel)r(ligenc)n(e)p Fp(,)d(V)m(ol.)f(P)m
(AMI-10,)h(No.)g(5,)g(pp.)h(687{694.)21 1357 y(Plaat,)g(A.,)h(Sc)o
(hae\013er,)h(J.,)f(Pijls,)f(W.,)g(and)h(de)h(Bruin,)f(A.)g(\(1995\).)
20 b(Best-First)d(Fixed-Depth)f(Game-T)m(ree)d(Searc)o(h)j(in)21
1399 y(Practice.)j(In)14 b Fn(Pr)n(o)n(c)n(e)n(e)n(dings)h(of)f
(IJCAI-95)p Fp(,)f(v)o(olume)f(1,)i(pp.)f(273{279,)f(Mon)o(treal,)h
(Queb)q(ec.)21 1474 y(Plaat,)h(A.,)g(Sc)o(hae\013er,)i(J.,)e(Pijls,)g
(W.,)f(and)i(de)g(Bruin,)g(A.)f(\(1996\).)20 b(Best-First)c
(Fixed-Depth)f(Minimax)d(Algorithms.)21 1515 y(T)m(o)h(app)q(ear)h(in)g
Fn(A)o(rti\014cial)f(Intel)r(ligenc)n(e)p Fp(.)21 1590
y(Reinefeld,)g(A.)h(\(1983\).)k(An)c(Impro)o(v)o(emen)o(t)e(to)i(the)h
(Scout)g(Tree-Searc)o(h)h(Algorithm.)g Fn(ICCA)e(Journal)p
Fp(,)g(V)m(ol.)f(6,)g(No.)h(4,)21 1631 y(pp.)f(4{14.)21
1706 y(Sc)o(hae\013er,)19 b(J.)e(\(1989\).)28 b(Distributed)18
b(Game-T)m(ree)e(Searc)o(hing.)29 b Fn(Journal)18 b(of)g(Par)n(al)r
(lel)g(and)h(Distribute)n(d)e(Computing)p Fp(,)21 1748
y(V)m(ol.)12 b(6,)h(No.)g(2,)h(pp.)f(90{114.)21 1822
y(Shinghal,)f(R.)i(and)g(Sh)o(v)o(ed,)g(S.)g(\(1991\).)k(Prop)q(osed)e
(Mo)q(di\014cations)e(to)g(P)o(arallel)f(State)i(Space)g(Searc)o(h)g
(of)f(Game)e(T)m(rees.)21 1864 y Fn(International)j(Journal)g(of)f
(Pattern)h(R)n(e)n(c)n(o)n(gnition)g(and)h(A)o(rti\014cial)e(Intel)r
(ligenc)n(e)p Fp(,)f(V)m(ol.)f(5,)h(No.)h(5,)f(pp.)g(809{833.)21
1939 y(Stein)o(b)q(erg,)e(I.)e(R.)h(and)g(Solomon,)d(M.)j(\(1990\).)h
(Searc)o(hing)g(Game)d(Trees)k(in)d(P)o(arallel.)i(In)f
Fn(Pr)n(o)n(c)n(c)n(e)n(dings)h(of)h(the)f(1990)h(Inter-)21
1980 y(national)j(Confer)n(enc)n(e)f(on)h(Par)n(al)r(lel)e(Pr)n(o)n(c)n
(essing)h(\(vol.)g(3\))p Fp(,)g(pp.)f(9{17,)f(Univ)o(ersit)o(y)h(P)o
(ark,)g(P)m(A.)g(P)o(enn.)g(State)h(Univ)o(ersit)o(y)21
2022 y(Press.)21 2096 y(Sto)q(c)o(kman,)f(G.)i(C.)f(\(1979\).)21
b(A)16 b(Minimax)c(Algorithm)h(Better)k(than)e(Alpha-Beta?)30
b Fn(A)o(rti\014cial)14 b(Intel)r(ligenc)n(e)p Fp(,)h(V)m(ol.)f(12,)21
2138 y(pp.)f(179{196.)21 2213 y(V)m(orn)o(b)q(erger,)18
b(O.)f(and)f(Monien,)i(B.)e(\(1987\).)27 b(P)o(arallel)16
b(Alpha-Beta)h(v)o(ersus)h(Parallel)e(SSS*.)27 b(In)17
b Fn(Pr)n(o)n(c)n(e)n(e)n(dings)g(of)h(the)21 2254 y(IFIP)d(Confer)n
(enc)n(e)g(on)g(Distribute)n(d)f(Pr)n(o)n(c)n(essing)p
Fp(,)g(pp.)f(613{625.)f(North)i(Holland.)21 2329 y(W)m(eill,)k(J.-C.)g
(\(1995\).)32 b Fn(Pr)n(o)n(gr)n(ammes)18 b(d')o(\023)-20
b(eche)n(cs)20 b(de)g(championnat:)29 b(ar)n(chite)n(ctur)n(e)19
b(lo)n(giciel)r(le)f(synth)o(\022)-20 b(ese)20 b(de)g(fonctions)21
2370 y(d')o(\023)-20 b(evaluations,)15 b(p)n(ar)n(al)r(l)o(\023)-20
b(elisme)13 b(de)j(r)n(e)n(cher)n(che)p Fp(.)h(Ph.D.)c(thesis,)h(Univ)o
(ersit)o(\023)-20 b(e)15 b(P)o(aris)f(8.)21 2445 y(W)m(eill,)d(J.-C.)h
(\(1996\).)k(The)e(ABD)o(AD)o(A)f(Distributed)g(Minimax-Searc)o(h)f
(Algorithm.)i Fn(ICCA)g(Journal)p Fp(,)e(V)m(ol.)g(19,)g(No.)h(1,)21
2487 y(pp.)g(3{16.)p eop
%%Trailer
end
userdict /end-hook known{end-hook}if
%%EOF