A bunch of chess-related papers.

[typhoon-papers.git] / parallel / dop7.ps

%!PS-Adobe-2.0
%%Creator: dvipsk 5.58f Copyright 1986, 1994 Radical Eye Software
%%Title: dop7.dvi
%%Pages: 14
%%PageOrder: Ascend
%%BoundingBox: 0 0 612 792
%%DocumentFonts: Helvetica Courier Helvetica-Bold Helvetica-Oblique
%%DocumentPaperSizes: Letter
%%EndComments
%DVIPSCommandLine: dvips -o dop7.ps dop7
%DVIPSParameters: dpi=600, comments removed
%DVIPSSource:  TeX output 1998.10.27:1114
%%BeginProcSet: fix-lj4si-ps-bug.pro
/fixcurrentmatrix {
    statusdict /product known {
        statusdict /product get (HP LaserJet 4Si) eq {
            /version where {
                /version get (2011.110) eq {
                    matrix currentmatrix
                    dup dup 0 get 32768 mul round 32768 div 0 exch put
                    dup dup 3 get 32768 mul round 32768 div 3 exch put
                    systemdict /setmatrix get exec
                } if
            } if
        } if 
    } if
} bind def

/setmatrix {
    systemdict /setmatrix get exec
    fixcurrentmatrix
} bind def
%%EndProcSet
%%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 userdict
/eop-hook known{eop-hook}if showpage}N /@start{userdict /start-hook
known{start-hook}if pop /VResolution X /Resolution X 1000 div /DVImag X
/IE 256 array N 0 1 255{IE S 1 string dup 0 3 index put cvn put}for
65781.76 div /vsize X 65781.76 div /hsize X}N /p{show}N /RMat[1 0 0 -1 0
0]N /BDot 260 string N /rulex 0 N /ruley 0 N /v{/ruley X /rulex X V}B /V
{}B /RV statusdict begin /product where{pop product dup length 7 ge{0 7
getinterval dup(Display)eq exch 0 4 getinterval(NeXT)eq or}{pop false}
ifelse}{false}ifelse end{{gsave TR -.1 .1 TR 1 1 scale rulex ruley false
RMat{BDot}imagemask grestore}}{{gsave TR -.1 .1 TR rulex ruley scale 1 1
false RMat{BDot}imagemask grestore}}ifelse B /QV{gsave newpath transform
round exch round exch itransform moveto rulex 0 rlineto 0 ruley neg
rlineto rulex neg 0 rlineto fill grestore}B /a{moveto}B /delta 0 N /tail
{dup /delta X 0 rmoveto}B /M{S p delta add tail}B /b{S p tail}B /c{-4 M}
B /d{-3 M}B /e{-2 M}B /f{-1 M}B /g{0 M}B /h{1 M}B /i{2 M}B /j{3 M}B /k{
4 M}B /w{0 rmoveto}B /l{p -4 w}B /m{p -3 w}B /n{p -2 w}B /o{p -1 w}B /q{
p 1 w}B /r{p 2 w}B /s{p 3 w}B /t{p 4 w}B /x{0 S rmoveto}B /y{3 2 roll p
a}B /bos{/SS save N}B /eos{SS restore}B end
%%EndProcSet
%%BeginFont: Helvetica
% @@psencodingfile@{
%   author = "S. Rahtz, P. MacKay, Alan Jeffrey, B. Horn, K. Berry",
%   version = "0.6",
%   date = "22 June 1996",
%   filename = "8r.enc",
%   email = "kb@@mail.tug.org",
%   address = "135 Center Hill Rd. // Plymouth, MA 02360",
%   codetable = "ISO/ASCII",
%   checksum = "119     662    4424",
%   docstring = "Encoding for TrueType or Type 1 fonts to be used with TeX."
% @}
% 
% Idea is to have all the characters normally included in Type 1 fonts
% available for typesetting. This is effectively the characters in Adobe
% Standard Encoding + ISO Latin 1 + extra characters from Lucida.
% 
% Character code assignments were made as follows:
% 
% (1) the Windows ANSI characters are almost all in their Windows ANSI
% positions, because some Windows users cannot easily reencode the
% fonts, and it makes no difference on other systems. The only Windows
% ANSI characters not available are those that make no sense for
% typesetting -- rubout (127 decimal), nobreakspace (160), softhyphen
% (173). quotesingle and grave are moved just because it's such an
% irritation not having them in TeX positions.
% 
% (2) Remaining characters are assigned arbitrarily to the lower part
% of the range, avoiding 0, 10 and 13 in case we meet dumb software.
% 
% (3) Y&Y Lucida Bright includes some extra text characters; in the
% hopes that other PostScript fonts, perhaps created for public
% consumption, will include them, they are included starting at 0x12.
% 
% (4) Remaining positions left undefined are for use in (hopefully)
% upward-compatible revisions, if someday more characters are generally
% available.
% 
% (5) hyphen appears twice for compatibility with both ASCII and Windows.
% 
/TeXBase1Encoding [
% 0x00 (encoded characters from Adobe Standard not in Windows 3.1)
  /.notdef /dotaccent /fi /fl
  /fraction /hungarumlaut /Lslash /lslash
  /ogonek /ring /.notdef
  /breve /minus /.notdef 
% These are the only two remaining unencoded characters, so may as
% well include them.
  /Zcaron /zcaron 
% 0x10
 /caron /dotlessi 
% (unusual TeX characters available in, e.g., Lucida Bright)
 /dotlessj /ff /ffi /ffl 
 /.notdef /.notdef /.notdef /.notdef
 /.notdef /.notdef /.notdef /.notdef
 % very contentious; it's so painful not having quoteleft and quoteright
 % at 96 and 145 that we move the things normally found there down to here.
 /grave /quotesingle 
% 0x20 (ASCII begins)
 /space /exclam /quotedbl /numbersign
 /dollar /percent /ampersand /quoteright
 /parenleft /parenright /asterisk /plus /comma /hyphen /period /slash
% 0x30
 /zero /one /two /three /four /five /six /seven
 /eight /nine /colon /semicolon /less /equal /greater /question
% 0x40
 /at /A /B /C /D /E /F /G /H /I /J /K /L /M /N /O
% 0x50
 /P /Q /R /S /T /U /V /W
 /X /Y /Z /bracketleft /backslash /bracketright /asciicircum /underscore
% 0x60
 /quoteleft /a /b /c /d /e /f /g /h /i /j /k /l /m /n /o
% 0x70
 /p /q /r /s /t /u /v /w
 /x /y /z /braceleft /bar /braceright /asciitilde
 /.notdef % rubout; ASCII ends
% 0x80
 /.notdef /.notdef /quotesinglbase /florin
 /quotedblbase /ellipsis /dagger /daggerdbl
 /circumflex /perthousand /Scaron /guilsinglleft
 /OE /.notdef /.notdef /.notdef
% 0x90
 /.notdef /.notdef /.notdef /quotedblleft
 /quotedblright /bullet /endash /emdash
 /tilde /trademark /scaron /guilsinglright
 /oe /.notdef /.notdef /Ydieresis
% 0xA0
 /.notdef % nobreakspace
 /exclamdown /cent /sterling
 /currency /yen /brokenbar /section
 /dieresis /copyright /ordfeminine /guillemotleft
 /logicalnot
 /hyphen % Y&Y (also at 45); Windows' softhyphen
 /registered
 /macron
% 0xD0
 /degree /plusminus /twosuperior /threesuperior
 /acute /mu /paragraph /periodcentered
 /cedilla /onesuperior /ordmasculine /guillemotright
 /onequarter /onehalf /threequarters /questiondown
% 0xC0
 /Agrave /Aacute /Acircumflex /Atilde /Adieresis /Aring /AE /Ccedilla
 /Egrave /Eacute /Ecircumflex /Edieresis
 /Igrave /Iacute /Icircumflex /Idieresis
% 0xD0
 /Eth /Ntilde /Ograve /Oacute
 /Ocircumflex /Otilde /Odieresis /multiply
 /Oslash /Ugrave /Uacute /Ucircumflex
 /Udieresis /Yacute /Thorn /germandbls
% 0xE0
 /agrave /aacute /acircumflex /atilde
 /adieresis /aring /ae /ccedilla
 /egrave /eacute /ecircumflex /edieresis
 /igrave /iacute /icircumflex /idieresis
% 0xF0
 /eth /ntilde /ograve /oacute
 /ocircumflex /otilde /odieresis /divide
 /oslash /ugrave /uacute /ucircumflex
 /udieresis /yacute /thorn /ydieresis
] def
%%EndFont
%%BeginProcSet: texps.pro
TeXDict begin /rf{findfont dup length 1 add dict begin{1 index /FID ne 2
index /UniqueID ne and{def}{pop pop}ifelse}forall[1 index 0 6 -1 roll
exec 0 exch 5 -1 roll VResolution Resolution div mul neg 0 0]/Metrics
exch def dict begin Encoding{exch dup type /integertype ne{pop pop 1 sub
dup 0 le{pop}{[}ifelse}{FontMatrix 0 get div Metrics 0 get div def}
ifelse}forall Metrics /Metrics currentdict end def[2 index currentdict
end definefont 3 -1 roll makefont /setfont load]cvx def}def
/ObliqueSlant{dup sin S cos div neg}B /SlantFont{4 index mul add}def
/ExtendFont{3 -1 roll mul exch}def /ReEncodeFont{/Encoding exch def}def
end
%%EndProcSet
%%BeginProcSet: special.pro
TeXDict begin /SDict 200 dict N SDict begin /@SpecialDefaults{/hs 612 N
/vs 792 N /ho 0 N /vo 0 N /hsc 1 N /vsc 1 N /ang 0 N /CLIP 0 N /rwiSeen
false N /rhiSeen false N /letter{}N /note{}N /a4{}N /legal{}N}B
/@scaleunit 100 N /@hscale{@scaleunit div /hsc X}B /@vscale{@scaleunit
div /vsc X}B /@hsize{/hs X /CLIP 1 N}B /@vsize{/vs X /CLIP 1 N}B /@clip{
/CLIP 2 N}B /@hoffset{/ho X}B /@voffset{/vo X}B /@angle{/ang X}B /@rwi{
10 div /rwi X /rwiSeen true N}B /@rhi{10 div /rhi X /rhiSeen true N}B
/@llx{/llx X}B /@lly{/lly X}B /@urx{/urx X}B /@ury{/ury X}B /magscale
true def end /@MacSetUp{userdict /md known{userdict /md get type
/dicttype eq{userdict begin md length 10 add md maxlength ge{/md md dup
length 20 add dict copy def}if end md begin /letter{}N /note{}N /legal{}
N /od{txpose 1 0 mtx defaultmatrix dtransform S atan/pa X newpath
clippath mark{transform{itransform moveto}}{transform{itransform lineto}
}{6 -2 roll transform 6 -2 roll transform 6 -2 roll transform{
itransform 6 2 roll itransform 6 2 roll itransform 6 2 roll curveto}}{{
closepath}}pathforall newpath counttomark array astore /gc xdf pop ct 39
0 put 10 fz 0 fs 2 F/|______Courier fnt invertflag{PaintBlack}if}N
/txpose{pxs pys scale ppr aload pop por{noflips{pop S neg S TR pop 1 -1
scale}if xflip yflip and{pop S neg S TR 180 rotate 1 -1 scale ppr 3 get
ppr 1 get neg sub neg ppr 2 get ppr 0 get neg sub neg TR}if xflip yflip
not and{pop S neg S TR pop 180 rotate ppr 3 get ppr 1 get neg sub neg 0
TR}if yflip xflip not and{ppr 1 get neg ppr 0 get neg TR}if}{noflips{TR
pop pop 270 rotate 1 -1 scale}if xflip yflip and{TR pop pop 90 rotate 1
-1 scale ppr 3 get ppr 1 get neg sub neg ppr 2 get ppr 0 get neg sub neg
TR}if xflip yflip not and{TR pop pop 90 rotate ppr 3 get ppr 1 get neg
sub neg 0 TR}if yflip xflip not and{TR pop pop 270 rotate ppr 2 get ppr
0 get neg sub neg 0 S TR}if}ifelse scaleby96{ppr aload pop 4 -1 roll add
2 div 3 1 roll add 2 div 2 copy TR .96 dup scale neg S neg S TR}if}N /cp
{pop pop showpage pm restore}N end}if}if}N /normalscale{Resolution 72
div VResolution 72 div neg scale magscale{DVImag dup scale}if 0 setgray}
N /psfts{S 65781.76 div N}N /startTexFig{/psf$SavedState save N userdict
maxlength dict begin /magscale true def normalscale currentpoint TR
/psf$ury psfts /psf$urx psfts /psf$lly psfts /psf$llx psfts /psf$y psfts
/psf$x psfts currentpoint /psf$cy X /psf$cx X /psf$sx psf$x psf$urx
psf$llx sub div N /psf$sy psf$y psf$ury psf$lly sub div N psf$sx psf$sy
scale psf$cx psf$sx div psf$llx sub psf$cy psf$sy div psf$ury sub TR
/showpage{}N /erasepage{}N /copypage{}N /p 3 def @MacSetUp}N /doclip{
psf$llx psf$lly psf$urx psf$ury currentpoint 6 2 roll newpath 4 copy 4 2
roll moveto 6 -1 roll S lineto S lineto S lineto closepath clip newpath
moveto}N /endTexFig{end psf$SavedState restore}N /@beginspecial{SDict
begin /SpecialSave save N gsave normalscale currentpoint TR
@SpecialDefaults count /ocount X /dcount countdictstack N}N /@setspecial
{CLIP 1 eq{newpath 0 0 moveto hs 0 rlineto 0 vs rlineto hs neg 0 rlineto
closepath clip}if ho vo TR hsc vsc scale ang rotate rwiSeen{rwi urx llx
sub div rhiSeen{rhi ury lly sub div}{dup}ifelse scale llx neg lly neg TR
}{rhiSeen{rhi ury lly sub div dup scale llx neg lly neg TR}if}ifelse
CLIP 2 eq{newpath llx lly moveto urx lly lineto urx ury lineto llx ury
lineto closepath clip}if /showpage{}N /erasepage{}N /copypage{}N newpath
}N /@endspecial{count ocount sub{pop}repeat countdictstack dcount sub{
end}repeat grestore SpecialSave restore end}N /@defspecial{SDict begin}
N /@fedspecial{end}B /li{lineto}B /rl{rlineto}B /rc{rcurveto}B /np{
/SaveX currentpoint /SaveY X N 1 setlinecap newpath}N /st{stroke SaveX
SaveY moveto}N /fil{fill SaveX SaveY moveto}N /ellipse{/endangle X
/startangle X /yrad X /xrad X /savematrix matrix currentmatrix N TR xrad
yrad scale 0 0 1 startangle endangle arc savematrix setmatrix}N end
%%EndProcSet
TeXDict begin 40258431 52099146 1000 600 600 (dop7.dvi)
@start /Fa 134[45 1[45 45 45 45 45 45 45 45 45 45 45
45 45 1[45 45 45 45 45 45 45 45 45 38[45 10[45 45 46[{
 TeXBase1Encoding ReEncodeFont }26 75.000000 /Courier
rf /Fb 82[25 50[37 37 1[54 37 42 21 37 25 42 42 42 42
62 17 2[17 42 42 21 42 42 37 42 42 12[46 50 54 1[50 58
54 62 42 1[37 21 54 58 46 50 54 54 50 50 6[21 42 42 1[42
42 3[42 2[21 1[21 41[37 2[{ TeXBase1Encoding ReEncodeFont }51
75.000000 /Helvetica-Oblique rf /Fc 3 50 df<7FFFFFFFFFFF80FFFFFFFFFFFFC0
FFFFFFFFFFFFC07FFFFFFFFFFF803204799641>0 D<6000000006F80000000FFC000000
1F7E0000003F3F0000007E1F800000FC0FC00001F807E00003F003F00007E001F8000FC0
00FC001F80007E003F00003F007E00001F80FC00000FC1F8000007E3F0000003F7E00000
01FFC0000000FF800000007F000000007F00000000FF80000001FFC0000003F7E0000007
E3F000000FC1F800001F80FC00003F007E00007E003F0000FC001F8001F8000FC003F000
07E007E00003F00FC00001F81F800000FC3F0000007E7E0000003FFC0000001FF8000000
0F6000000006282874A841>2 D<000FF000000007F000003FFE0000003FFE0000FFFF80
0000FFFF0003FFFFC00003F807C007F07FF00007C001E00F801FF8000F8000F00F0007FC
003E0000701E0003FE007C0000383C0001FF007800001C380000FF80F000001C7000007F
C1F000000E7000003FE3E000000E6000001FF3C00000066000001FF780000006E000000F
FF80000007C0000007FF00000003C0000003FE00000003C0000003FE00000003C0000001
FF00000003C0000000FF80000003C00000007FC0000003C00000007FC0000003C0000000
FFE0000003E0000001FFF000000760000001EFF800000660000003CFF800000670000007
C7FC00000E7000000F83FE00000E3800000F01FF00001C3800001E00FF80003C1C00003E
007FC000780E00007C003FE000F00F0001F0001FF801F0078003E0000FFE0FE003E01FC0
0003FFFFC000FFFF000001FFFF00007FFC0000007FFC00000FE00000000FF00048267BA4
53>49 D E /Fd 82[28 56[28 46 32 1[51 51 51 74 23 2[23
51 1[28 46 1[46 1[46 12[51 55 2[55 8[65 51 3[60 66[{
 TeXBase1Encoding ReEncodeFont }21 83.333336 /Helvetica-Bold
rf /Fe 7 121 df<387CFEFEFE7C3807077A8614>58 D<001F8000007FC00000F0E70003
C03F0007803F000F001F000F001F001E001F003E003E003C003E007C003E007C003E00F8
007C00F8007C00F8007C00F8007C00F000F800F000F830F000F830F000F830F001F060F0
01F0607803F060780EF0C03C1CF9801FF07F8007C01E001C1B7C9924>97
D<000FE0003FF800F81C01E00E03803E07807E0F007E1E007C3E007C3C00007C00007C00
00F80000F80000F80000F80000F00000F00000F00000F00004F0000C7800187800303C00
E01E07C00FFF0003F800171B7C991E>99 D<000FC0007FF000F03803C01C07801C0F001C
1F001C1E001C3E00387C00707C07E07FFF80FFFC00F80000F80000F80000F80000F00000
F00000F0000478000C7800183800303C00E01E07C00FFF0003F800161B7C991F>101
D<00F007C001FC1FF0031E7878061EE03C061FC01C0C1F801E0C1F001E0C3F001E183F00
1F183E001F003E001F007E001F007E003E007C003E007C003E00FC003E00FC007C00F800
7C00F8007801F800F001F800F001F801E001F803C003FC078003FE1F0003E7FC0003E1F0
0007E0000007E0000007C0000007C000000FC000000FC000000F8000001F800000FFF800
00FFF800002025809922>112 D<000FE0007FF800F03C01C00E03C01E07803E07803E07
803C0F80180FE00007FF0007FFC003FFE001FFF000FFF80007F80001F83C00F87E00787E
0078FC00F0F800F07001E07003C03C0F801FFE0007F800171B7C991F>115
D<007C03C001FF0FF007079C300E03B0780C03F0F81803E1F83003E1F83003E1F06007C0
E06007C0000007C0000007C000000F8000000F8000000F8000000F8000001F0000001F00
30381F00307C1F0060FC3E0060FC3E00C0F87E00C0F06F038070C707003F83FE001F01F8
001D1B7D9926>120 D E /Ff 5 94 df<0000600000E00001C0000380000700000E0000
1E00003C0000780000780000F00001E00001E00003C00003C00007C0000780000F80000F
00000F00001F00001E00001E00003E00003E00003E00007C00007C00007C00007C00007C
00007C0000F80000F80000F80000F80000F80000F80000F80000F80000F80000F80000F8
0000F80000F80000F80000F80000F80000F80000F800007C00007C00007C00007C00007C
00007C00003E00003E00003E00001E00001E00001F00000F00000F00000F800007800007
C00003C00003C00001E00001E00000F000007800007800003C00001E00000E0000070000
03800001C00000E0000060135278BD20>40 D<C00000E000007000003800001C00000E00
000F000007800003C00003C00001E00000F00000F000007800007800007C00003C00003E
00001E00001E00001F00000F00000F00000F80000F80000F800007C00007C00007C00007
C00007C00007C00003E00003E00003E00003E00003E00003E00003E00003E00003E00003
E00003E00003E00003E00003E00003E00003E00003E00003E00007C00007C00007C00007
C00007C00007C0000F80000F80000F80000F00000F00001F00001E00001E00003E00003C
00007C0000780000780000F00000F00001E00003C00003C0000780000F00000E00001C00
00380000700000E00000C0000013527CBD20>I<00000030000000000000780000000000
007800000000000078000000000000780000000000007800000000000078000000000000
780000000000007800000000000078000000000000780000000000007800000000000078
000000000000780000000000007800000000000078000000000000780000000000007800
000000000078000000000000780000000000007800000000000078000000000000780000
0000000078000000000000780000007FFFFFFFFFFFF8FFFFFFFFFFFFFCFFFFFFFFFFFFFC
7FFFFFFFFFFFF80000007800000000000078000000000000780000000000007800000000
000078000000000000780000000000007800000000000078000000000000780000000000
007800000000000078000000000000780000000000007800000000000078000000000000
780000000000007800000000000078000000000000780000000000007800000000000078
000000000000780000000000007800000000000078000000000000780000000000003000
000036367BAF41>43 D<FFF8FFF8FFF8FFF8F000F000F000F000F000F000F000F000F000
F000F000F000F000F000F000F000F000F000F000F000F000F000F000F000F000F000F000
F000F000F000F000F000F000F000F000F000F000F000F000F000F000F000F000F000F000
F000F000F000F000F000F000F000F000F000F000F000F000F000F000F000F000F000F000
F000F000F000F000F000F000F000F000F000F000F000F000FFF8FFF8FFF8FFF80D5378BD
17>91 D<FFF8FFF8FFF8FFF8007800780078007800780078007800780078007800780078
007800780078007800780078007800780078007800780078007800780078007800780078
007800780078007800780078007800780078007800780078007800780078007800780078
007800780078007800780078007800780078007800780078007800780078007800780078
007800780078007800780078007800780078FFF8FFF8FFF8FFF80D537FBD17>93
D E /Fg 206[28 49[{ TeXBase1Encoding ReEncodeFont }1
50.000000 /Helvetica rf /Fh 202[32 2[32 32 32 48[{
 TeXBase1Encoding ReEncodeFont }4 58.333336 /Helvetica
rf /Fi 12 117 df<00003FC000000000FFF800000007E07C0000000F801F0000003F00
1F800C007E000F800C00FC0007C01C01F80007E01803F00007E01807E00003E0380FE000
03F0300FC00003F0301FC00003F0703F800003F0603F800003F0E07F800003F0C07F0000
03F1C07F000003F1807F000003F380FF000003F300FE000003F700FE000003FE00FE0000
03FC00FE000003FC00FC000003F800FC000003F000FC000003F000FC000003F000FC0000
03F0007E000007F0007E00000FF0003E00001DF8183F000079F8181F0000E1F8380F8007
C0F83007E03F007CF001FFF8003FC0003FC0000F802E267DA435>11
D<00000001FC0000000007FF800000001E07C00000007801E0000000E001F0000001C000
F80000038000F80000070000F800000E0000FC00001C0000FC0000380000FC0000300000
FC0000700001FC0000600001F80000E00001F80000C00001F80001C00003F80001800003
F00003800003F00003000007E00003000007C0000700000FC0000600001F80000600FFBF
00000E01FFFC00000C0381F800000C03FFFE00000C00FF1F00001C00001F80001800000F
80001800000FC0001800000FC0003800000FC00030000007E00030000007E0003000000F
E0007000000FE0006000000FE0006000000FE0006000000FE000E000001FE000C000001F
C000C000001FC000C000001FC001C000003FC001C000003F8001C000003F8001C000007F
0003C000007F0003C00000FE0003C00000FC0003E00001F80007600003F00006700007E0
000638000FC000061C001F80000E0E003F00000C0780FC00000C01FFF000000C007F8000
001C00000000001800000000001800000000001800000000003800000000003000000000
003000000000003000000000007000000000006000000000006000000000006000000000
00E00000000000C00000000000C000000000002E4B7EBA2F>I<00003FF00001FFF0000F
FFE0003FC000007F000000FC000003F8000007F0000007E000000FE000001FC000001FC0
00003F8000003F8000007FFFFE007FFFFF007FFFFF007F000000FF000000FE000000FE00
0000FE000000FE000000FE0000007E0000007E0000007E0000007E0000003E0000003F00
00001F0000000F8000600FC000E003E003C001F01F00007FFC00000FE0001C257DA322>
15 D<1C007F00FF80FF80FF80FF80FF807F001C000909798817>58
D<1C007F00FF80FF80FFC0FFC0FFC07FC01CC000C000C000C000C001C001800180038003
00070006000E001C003800700060000A19798817>I<0000000C0000001E0000003E0000
003E0000003C0000007C0000007C00000078000000F8000000F8000000F0000001F00000
01F0000001E0000003E0000003E0000003C0000007C0000007C00000078000000F800000
0F8000000F0000001F0000001F0000001E0000003E0000003E0000003C0000007C000000
7C00000078000000F8000000F8000000F0000001F0000001F0000001E0000003E0000003
E0000007C0000007C00000078000000F8000000F8000000F0000001F0000001F0000001E
0000003E0000003E0000003C0000007C0000007C00000078000000F8000000F8000000F0
000001F0000001F0000001E0000003E0000003E0000003C0000007C0000007C000000780
00000F8000000F8000000F0000001F0000001F0000001E0000003E0000003E0000003C00
00007C0000007C00000078000000F8000000F8000000F0000000600000001F537BBD2A>
61 D<00000001FF00000000001FFFF000000000FE01FC00000003F0007E00000007C000
1F8000001F80000FC000003E000007E00000FC000003F00001F8000003F00003F0000001
F80007E0000001F8000FC0000000FC001F80000000FC003F00000000FE007F000000007E
00FE000000007E00FC000000007F01FC000000007F03F8000000007F03F8000000007F07
F0000000007F07F0000000007F0FF0000000007F0FE0000000007F1FE000000000FF1FE0
00000000FF3FC000000000FF3FC000000000FF3FC000000000FF7F8000000001FE7F8000
000001FE7F8000000001FE7F8000000001FEFF8000000003FCFF0000000003FCFF000000
0003FCFF0000000007F8FF0000000007F8FF000000000FF0FF000000000FF0FF00000000
0FE0FF000000001FE0FF000000001FC0FF000000003F807F000000007F807F000000007F
007F00000000FE007F00000001FC003F80000001F8003F80000003F8001F80000007F000
1FC000000FE0000FC000001F800007E000003F000007F000007E000003F00001F8000001
FC0003F00000007E000FC00000003F807F0000000007FFF80000000000FF80000000383D
7CBA3F>79 D<7FFFFC01FFFFF800FFFF80FFFFFC01FFFFF800FFFF80FFFFFC01FFFFF000
FFFF8003FF000007FC00000FF80003FC000007F8000003E00001FC000007F8000003C000
01FC000003F8000003800001FC000003F8000003000001FC000003F8000007000001FC00
0003F8000006000001FC000007F800000C000001FC000007F800000C000001FC00000FF8
000018000001FC00000FF8000018000001FC00001BF8000030000001FC00001BF8000060
000001FC000033F8000060000001FE000073F80000C0000001FE000063F80000C0000000
FE0000C3F8000180000000FE0000C3FC000180000000FE000183FC000300000000FE0001
81FC000700000000FE000301FC000600000000FE000701FC000C00000000FE000601FC00
0C00000000FE000C01FC001800000000FE000C01FC001800000000FE001801FC00300000
0000FE001801FC007000000000FE003001FC006000000000FE003001FC00C000000000FE
006001FC00C000000000FF00E001FC018000000000FF00C001FC0180000000007F018001
FC0300000000007F018001FE0300000000007F030001FE0600000000007F030000FE0E00
000000007F060000FE0C00000000007F0E0000FE1800000000007F0C0000FE1800000000
007F180000FE3000000000007F180000FE3000000000007F300000FE6000000000007F30
0000FEE000000000007F600000FEC000000000007F600000FF8000000000007FC00000FF
8000000000007F800000FF0000000000007F800000FF0000000000003F000000FE000000
0000003F000000FE0000000000003E0000007C0000000000003E00000078000000000000
3C000000780000000000003C000000700000000000003800000070000000000000300000
00600000000000513B7CB84E>87 D<0003F0000001FFF0000001FFF0000001FFF0000000
07F000000007E000000007E000000007E00000000FE00000000FC00000000FC00000000F
C00000001FC00000001F800000001F800000001F800000003F800000003F000000003F00
0000003F000000007F000000007E0007C0007E001FF0007E00783800FE00E0F800FC01C1
FC00FC0383FC00FC0707FC01FC0E07FC01F81C07F801F83803F001F87001E003F8E00000
03F1C0000003F380000003F700000007FE00000007FE00000007FFE0000007E7F800000F
E0FE00000FC07F00000FC03F80000FC01F80001FC01FC0001F800FC0301F800FC0301F80
0FC0703F801FC0603F001F80603F001F80603F001F80E07F001F80C07E001F81C07E000F
81807E000F8380FE00078700FC0003FE00380000F800263B7CB92B>107
D<03E0007F000007F801FFE0000E3C0781F0001C3E1E00F800383F3800FC00303F7000FC
00303FE0007C00703FC0007C00603F80007C00603F80007C00E03F0000FC00C07F0000FC
00C07E0000FC00C07E0000FC00007E0001FC0000FE0001F80000FC0001F80000FC0001F8
0000FC0003F80001FC0003F00001F80003F00001F80007F00001F80007E00003F80007E0
0003F0000FE03003F0000FC03003F0001FC07007F0001F806007E0001F806007E0001F80
E007E0001F00C00FE0001F01C00FC0001F01800FC0001F03800FC0001F07001FC0000F0E
001F800007FC0007000001F0002C267EA432>110 D<000F8003F000001FE00FFC000039
F03C1F000070F8700F8000E0FDE007C000C0FF8007C000C0FF0007E001C0FE0003E00180
FE0003F00180FC0003F00381FC0003F00301FC0003F00301F80003F00301F80003F00003
F80007F00003F80007F00003F00007F00003F00007F00007F0000FF00007F0000FF00007
E0000FE00007E0000FE0000FE0001FE0000FE0001FC0000FC0001FC0000FC0003F80001F
C0003F80001FC0007F00001F80007E00001F8000FE00003F8000FC00003FC001F800003F
C003F000003FE007E000007F700F8000007F383F0000007E1FFC0000007E07E0000000FE
0000000000FE0000000000FC0000000000FC0000000001FC0000000001FC0000000001F8
0000000001F80000000003F80000000003F80000000003F00000000007F000000000FFFF
C0000000FFFFC0000000FFFFC00000002C3583A42A>112 D<0001C0000003E0000007E0
000007E0000007E0000007E000000FE000000FC000000FC000000FC000001FC000001F80
00001F8000001F8000003F8000003F00007FFFFF807FFFFF80FFFFFF80007E0000007E00
00007E000000FE000000FC000000FC000000FC000001FC000001F8000001F8000001F800
0003F8000003F0000003F0000003F0000007F0000007E0000007E0000007E000000FE000
000FC006000FC006000FC00E001FC00C001F801C001F8018001F8038001F8070001F8060
001F80E0000F81C0000787800003FE000000F8000019357EB31E>116
D E /Fj 82[39 53[90 65 71 39 65 45 71 71 71 71 103 32
65 1[32 71 71 39 65 71 65 1[65 12[71 78 84 1[78 90 5[32
84 90 71 1[84 84 84 84 8[65 65 65 65 65 65 65 65 49[{
 TeXBase1Encoding ReEncodeFont }43 116.666672 /Helvetica-Bold
rf /Fk 82[28 24[28 28 24[42 42 42 60 42 46 23 42 28 46
46 46 46 69 18 42 18 18 46 46 23 46 46 42 46 46 3[23
1[23 1[55 1[78 55 60 51 55 60 65 55 65 60 69 46 55 1[23
60 65 51 55 60 60 55 55 5[23 23 46 46 46 46 46 46 46
46 46 46 1[23 1[23 1[32 28 28 18 35[42 42 2[{
 TeXBase1Encoding ReEncodeFont }74 83.333336 /Helvetica
rf /Fl 82[22 51[33 1[48 33 37 18 33 22 1[37 37 37 55
15 33 1[15 37 37 18 37 37 33 37 37 12[41 44 48 1[44 52
48 1[37 2[18 48 52 41 44 48 48 1[44 7[37 37 37 37 37
37 37 37 37 37 18 18 1[18 40[33 33 2[{ TeXBase1Encoding ReEncodeFont }
53 66.666664 /Helvetica rf /Fm 1 4 df<006000007000006000006000406020E060
70F861F07E67E01FFF8007FE0000F00007FE001FFF807E67E0F861F0E060704060200060
0000600000700000600014157B9620>3 D E /Fn 82[25 21[75
42 25[19 1[37 37 37 54 37 42 21 37 25 42 42 42 42 62
17 37 17 17 42 42 21 42 42 37 42 42 3[21 1[21 46 50 1[71
50 54 46 50 54 58 50 58 54 62 42 50 37 21 54 58 46 50
54 54 50 50 6[21 42 42 42 42 42 42 42 42 42 42 21 21
1[21 1[29 25 25 17 35[37 37 2[{ TeXBase1Encoding ReEncodeFont }77
75.000000 /Helvetica rf /Fo 139[25 42 29 14[42 46 42
31[54 65[{ TeXBase1Encoding ReEncodeFont }7 75.000000
/Helvetica-Bold rf /Fp 134[60 3[60 1[60 60 1[60 1[60
60 1[60 3[60 1[60 60 60 1[60 32[60 17[60 46[{
 TeXBase1Encoding ReEncodeFont }15 100.000000 /Courier
rf /Fq 1 4 df<000C0000001E0000001E0000001E0000001E0000001E0000601E018078
1E0780FC0C0FC07F0C3F803F8C7F0007CCF80001FFE000007F8000001E0000007F800001
FFE00007CCF8003F8C7F007F0C3F80FC0C0FC0781E0780601E0180001E0000001E000000
1E0000001E0000001E0000000C00001A1D7C9E23>3 D E /Fr 134[50
2[50 55 28 50 33 1[55 55 55 83 22 2[22 55 1[28 55 55
50 1[55 8[66 94 66 72 1[66 2[66 1[72 83 55 66 1[28 1[78
61 1[72 72 1[66 6[28 55 55 55 55 55 55 55 55 55 55 3[28
2[33 33 40[{ TeXBase1Encoding ReEncodeFont }48 100.000000
/Helvetica rf /Fs 1 4 df<00007000000000F800000000F800000000F800000000F8
00000000F800000000F800000000F800000000F80000000070000078007000F07C007001
F0FF007007F87F80700FF03FE0703FE00FF0707F8003F870FE0000FE73F800003F77E000
000FFF80000003FE00000000F800000003FE0000000FFF8000003F77E00000FE73F80003
F870FE000FF0707F803FE0703FE07F80700FF0FF007007F87C007001F078007000F00000
7000000000F800000000F800000000F800000000F800000000F800000000F800000000F8
00000000F800000000700000252B7AAD32>3 D E /Ft 82[47 50[71
4[78 39 71 47 78 78 78 78 118 31 2[31 78 1[39 78 1[71
78 78 12[86 94 2[94 110 10[102 2[94 65[{ TeXBase1Encoding ReEncodeFont }
25 141.666672 /Helvetica rf end
%%EndProlog
%%BeginSetup
%%Feature: *Resolution 600dpi
TeXDict begin
%%PaperSize: Letter

%%EndSetup
%%Page: 1 1
1 0 bop 181 739 a Ft(State\255of\255the\255Art)43 b(in)d(Parallel)i
(Search)e(T)-16 b(echniques)42 b(for)e(Discrete)1264
967 y(Optimization)h(Problems)2722 915 y Fs(\003)1217
1297 y Fr(Ananth)29 b(Grama)1864 1261 y Fq(\003)1904
1297 y Fr(,)f(and)h(V)n(ipin)g(Kumar)2693 1261 y Fq(\003\003)1209
1551 y(\003)1249 1587 y Fr(Department)g(of)f(Computer)h(Sciences)1015
1733 y(Purdue)h(University)-7 b(,)27 b(W)n(est)h(Lafayette,)g(IN)f
(47907)538 1878 y Fp([email protected])p Fr(,)c(Ph:)40
b(\(765\))29 b(494)g(6964,)g(F)-5 b(AX:)28 b(\(765\))h(494)g(0739)1216
2132 y Fq(\003\003)1291 2169 y Fr(Department)g(of)f(Computer)h(Science)
924 2314 y(University)f(of)g(Minnesota,)h(Minneapolis,)h(MN)e(55455)568
2459 y Fp([email protected])p Fr(,)c(Ph:)39 b(\(612\))29
b(624)g(8023,)g(F)-5 b(AX:)28 b(\(612\))h(625)g(0572)1842
2916 y Fo(Abstract)363 3102 y Fn(Discrete)k(optimization)e(problems)h
(arise)i(in)f(a)h(variety)f(of)h(domains)f(such)h(as)g(VLSI)f(design,)j
(transportation,)251 3216 y(scheduling)18 b(and)j(management,)d(and)i
(design)g(optimization.)28 b(V)l(ery)21 b(often,)f(these)g(problems)g
(are)h(solved)f(using)g(state)251 3331 y(space)29 b(search)h
(techniques.)55 b(Due)30 b(to)g(the)f(high)g(computational)d
(requirements)i(and)h(inherent)f(parallel)f(nature)h(of)251
3445 y(search)21 b(techniques,)f(there)h(has)g(been)g(a)h(great)e(deal)
h(of)h(interest)e(in)h(the)g(development)f(of)h(parallel)e(search)j
(methods)251 3559 y(since)33 b(the)h(dawn)f(of)h(parallel)d(computing.)
68 b(Signi\002cant)32 b(advances)h(have)g(been)g(made)g(in)h(the)f(use)
h(of)g(powerful)251 3673 y(heuristics)21 b(and)g(parallel)e(processing)
i(to)h(solve)g(large)f(scale)h(discrete)f(optimization)e(problems.)33
b(Problem)21 b(instances)251 3787 y(that)j(were)g(considered)f
(computationally)f(intractable)g(only)j(a)g(few)g(years)g(back)g(are)g
(routinely)e(solved)h(currently)g(on)251 3901 y(server\255class)f
(symmetric)h(multi\255processors)d(and)h(small)h(workstation)f
(clusters.)36 b(Parallel)21 b(game\255playing)f(programs)251
4015 y(are)d(challenging)c(the)k(best)g(human)g(minds)g(at)g(games)h
(like)f(chess.)28 b(In)17 b(this)g(paper)l(,)f(we)i(describe)e(the)h
(state)g(of)g(the)g(art)g(in)251 4130 y(parallel)d(algorithms)h(used)i
(for)g(solving)f(discrete)g(optimization)f(problems.)26
b(W)o(e)16 b(address)h(heuristic)e(and)i(non\255heuristic)251
4244 y(techniques)c(for)j(searching)e(graphs)h(as)h(well)f(as)h(trees,)
g(and)f(speedup)f(anomalies)g(in)i(parallel)d(search)i(that)g(are)h
(caused)251 4358 y(by)k(the)g(inherent)e(speculative)g(nature)h(of)h
(search)g(techniques.)p 43 4427 1560 4 v 127 4481 a Fm(\003)163
4504 y Fl(This)f(work)h(is)g(sponsored)g(by)h(the)f(by)g(Army)h
(Research)f(Of)o(\002ce)h(contract)g(DA/DAAG55\25598\2551\2550441,)h
(NSF)d(Grant)i(EIA9876014,)g(and)f(by)g(Army)43 4603
y(High)30 b(Performance)h(Computing)g(Research)f(Center)h(under)f(the)g
(auspices)h(of)f(the)h(Department)g(of)g(the)f(Army)-5
b(,)35 b(Army)c(Research)g(Laboratory)43 4701 y(cooperative)20
b(agreement)g(number)g(DAAH04\25595\2552\2550003/contract)h(number)f
(DAAH04\25595\255C\2550008,)g(the)g(content)g(of)g(which)g(does)f(not)h
(necessarily)43 4800 y(re\003ect)f(the)g(position)f(or)h(the)g(policy)f
(of)h(the)g(government,)g(and)g(no)f(of)o(\002cial)g(endorsement)h
(should)g(be)f(inferred.)1970 5610 y Fk(1)p eop
%%Page: 2 2
2 1 bop 43 345 a Fj(1)116 b(Introduction)43 630 y Fk(The)21
b(generalized)h(discrete)f(optimization)i(problem)f(\(DOP\))e(deals)h
(with)h(minimizing)h(an)e(objective)h(function)g(of)f(a)g(set)g(of)43
755 y(variables)e(that)f(are)h(allowed)g(only)g(discrete)f(values.)31
b(An)19 b(instance)f(of)h(this)f(class)g(is)g(the)h(integer)g
(programming)g(problem)43 879 y(in)26 b(which)g(only)g(integer)g
(solutions)g(are)g(admissible)h(for)e(a)h(linear)h(programming)f
(\(LP\))g(model.)41 b(Other)25 b(instances)g(arise)43
1004 y(in)d(diverse)f(domains)h(such)e(as)h(VLSI)h(design)g
(\(placement)g(of)g(VLSI)g(components)f(on)h(a)f(die)h(to)g(minimize)g
(silicon)g(area\),)43 1128 y(robotics)k(\(robot)h(motion)g(planning\),)
i(and)e(logistics)g(\(visiting)g(all)g(vertices)f(of)g(a)h(graph)g
(while)g(minimizing)i(edge)e(cost\).)43 1253 y(Most)f(such)g(problems)h
(are)g(NP)f(complete;)k(hence)c(their)h(solution)h(time)f(increases)f
(exponentially)i(in)f(the)g(size)f(of)h(the)43 1377 y(problem)h(for)e
(all)i(known)f(algorithms.)44 b(One)27 b(may)f(argue)i(that)f(it)g(is)g
(pointless)g(to)g(apply)g(parallel)i(processing)d(to)h(these)43
1502 y(problems)21 b(since)g(we)g(can)f(never)h(reduce)g(their)g
(worst\255case)e(run)i(time)h(to)f(a)g(polynomial)h(without)g(using)f
(an)g(exponential)43 1626 y(number)37 b(of)f(processors.)69
b(However)-5 b(,)40 b(the)c(average\255time)h(complexity)f(of)h
(heuristic)f(search)f(algorithms)i(for)f(some)43 1751
y(problems)31 b(is)f(polynomial)i([38)q(,)e(46)q(].)54
b(Furthermore,)32 b(there)f(are)f(heuristic)h(search)e(algorithms)i
(that)g(\002nd)g(suboptimal)43 1875 y(solutions)25 b(for)g(speci\002c)f
(problems)h(in)g(polynomial)i(time.)38 b(In)25 b(such)f(cases,)g
(bigger)h(problem)h(instances)e(can)h(be)g(solved)43
2000 y(using)31 b(parallel)h(computers.)55 b(Many)30
b(DOPs)g(\(such)g(as)g(robot)h(motion)g(planning,)k(speech)30
b(understanding,)k(and)d(task)43 2124 y(scheduling\))25
b(require)f(real\255time)i(solutions.)36 b(For)24 b(these)g
(applications,)i(parallel)g(processing)e(may)g(be)h(the)f(only)h(way)f
(to)43 2249 y(obtain)j(acceptable)f(performance.)39 b(Problems)26
b(for)g(which)f(optimal)i(solutions)f(are)g(highly)g(desirable)g(can)g
(sometimes)43 2374 y(be)c(solved)g(for)f(moderate)i(sized)e(instances)g
(in)i(a)f(reasonable)g(amount)h(of)e(time)i(by)e(using)h(parallel)i
(search)d(techniques)43 2498 y(\(for)i(example,)h(VLSI)g
(\003oor\255plan)f(optimization\).)43 2683 y(Due)32 b(to)f(the)h(high)g
(computational)h(requirement)f(and)g(inherent)g(parallel)h(nature)e(of)
h(search)e(techniques,)k(there)d(has)43 2807 y(been)f(great)g(interest)
g(in)g(the)g(development)h(of)f(parallel)h(search)e(methods)h(since)f
(the)h(dawn)g(of)g(parallel)h(computing.)43 2932 y(In)24
b(fact,)g(parallel)h(search)e(programs)h(were)f(among)i(the)f(\002rst)f
(non\255numerical)i(programs)e(written)h(for)g(early)g(generation)43
3056 y(parallel)c(machines)e(such)f(as)h(HEP)h(and)f(C.mmp.)31
b(There)18 b(are)g(many)g(characteristics)f(of)h(search)f(techniques)i
(that)f(make)43 3181 y(their)28 b(parallel)i(formulations)f(very)d(dif)
o(ferent)j(from)e(those)h(of)g(traditional)i(numerical)f(algorithms,)h
(but)e(much)g(closer)f(to)43 3305 y(other)22 b(non\255numerical)g
(algorithms.)32 b(Parallel)24 b(search)c(algorithms)i(rely)f(on)h
(dynamic)f(data)h(structures,)e(which)i(makes)f(it)43
3430 y(dif)o(\002cult)j(to)h(use)f(static)h(work)f(distribution)h
(techniques.)38 b(There)24 b(is)g(potential)j(for)d(speculative)h(work)
f(both)h(in)g(serial)g(and)43 3554 y(parallel)30 b(search)e
(algorithms.)49 b(Hence)28 b(load)i(balancing)f(algorithms)h(for)e
(parallel)i(search)e(must)g(consider)g(qualitative)43
3679 y(information)34 b(as)e(well.)61 b(Some)33 b(search)e(algorithms)i
(require)g(use)f(of)g(large)h(global)h(hash)e(structures,)h(which)g
(can)f(be)43 3803 y(hard)27 b(to)g(implement)i(on)f(losely)f(coupled)h
(parallel)g(architectures.)44 b(T)m(remendous)27 b(advances)f(have)h
(been)h(made)f(both)43 3928 y(in)d(theoretical)h(and)f(applied)h
(aspects)e(of)h(parallel)h(search)e(techniques)h([11)q(].)34
b(These)23 b(techniques)h(have)g(been)g(used)g(to)43
4052 y(solve)19 b(problems)g(that)h(are)f(well)h(beyond)g(the)f(scope)g
(of)g(conventional)h(serial)g(processors.)29 b(In)19
b(this)h(paper)-5 b(,)20 b(we)g(provide)f(a)43 4177 y(brief)i(overview)
g(of)g(commonly)g(used)g(sequential)h(search)e(methods,)h(and)h
(present)e(the)i(state\255of\255the\255art)e(in)h(the)g(parallel)43
4302 y(formulations)j(of)g(various)e(search)g(techniques.)43
4701 y Fj(2)116 b(Overview)32 b(of)g(Search)f(T)-9 b(echniques)43
4986 y Fk(V)k(ery)24 b(often)h(a)f(discrete)g(optimization)i(problem)f
(is)f(formulated)h(as)f(the)h(problem)g(of)f(\002nding)h(a)f(path)g(in)
h(a)f(graph)h(from)f(a)43 5110 y(designated)j(initial)i(node)e(to)f
(one)h(of)g(several)f(possible)g(goals)h([38)q(,)f(20].)42
b(Such)27 b(a)f(graph)h(is)f(called)h(a)g(state)f(space.)42
b(In)43 5235 y(some)22 b(problems,)g(any)g(solution)h(path)f(between)g
(the)h(initial)g(node)g(and)f(a)g(goal)g(node)h(is)e(acceptable,)i
(whereas)f(in)g(other)43 5359 y(problems)f(a)g(cost)f(is)h(associated)g
(with)h(each)e(path)i(and)f(a)g(minimum)i(cost)d(solution)i(is)f
(desired.)32 b(In)21 b(many)g(applications,)1970 5610
y(2)p eop
%%Page: 3 3
3 2 bop 43 344 a Fk(it)29 b(is)g(possible)h(to)f(compute)g(a)g(lower)g
(bound)h(on)f(the)g(cost)f(of)i(a)f(solution)h(path)f(that)g(passes)f
(through)i(a)f(given)g(state.)43 469 y(This)23 b(cost)f(is)h(also)h
(called)g(a)f(heuristic)g(estimate.)43 653 y(T)-5 b(wo)31
b(commonly)g(used)f(techniques)h(for)g(searching)f(state)h(spaces)e
(are)i(depth\255\002rst)e(and)i(best\255\002rst)e(search.)54
b(Depth\255)43 778 y(\002rst)32 b(search)g(techniques)h(start)f(from)h
(an)g(initial)i(state)e(and)g(generate)h(a)f(set)f(of)i(successor)c
(states.)61 b(One)33 b(of)g(these)43 903 y(most)28 b(recently)g
(generated)g(states)g(is)g(then)g(selected)h(for)e(expansion)i(at)f
(each)g(step.)47 b(Many)28 b(variants)g(of)g(this)g(simple)43
1027 y(DFS)34 b(technique)g(exist.)64 b(In)34 b(one)g(such)f(variant,)j
(the)e(successor)d(states)i(of)h(a)g(node)g(are)g(ordered)g(on)f(the)h
(basis)g(of)43 1152 y(their)i(likelihood)h(of)f(yielding)h(a)e
(solution.)70 b(This)36 b(search)e(technique)j(is)e(referred)g(to)g(as)
g(directed\255DFS)h(or)f(ordered)43 1276 y(backtracking.)c(In)20
b(many)g(applications,)j(early)d(branches)g(explored)h(by)f(DFS)g
(techniques)h(may)f(lead)h(to)g(large)g(subtrees)43 1401
y(containing)27 b(no)f(solutions)g(when)g(solutions)h(may)e(be)h
(available)i(close)d(to)h(the)g(root)g(on)g(alternate)g(branches.)40
b(In)26 b(these)43 1525 y(cases,)33 b(it)f(is)g(useful)h(to)f(limit)h
(the)g(depth)f(in)h(terms)e(of)h(cost)g(or)f(number)i(of)f(edges,)i(to)
e(which)g(exhaustive)g(search)f(is)43 1650 y(performed.)j(If)23
b(no)h(desirable)g(solution)h(is)e(found)h(in)g(this)f(limited)j
(search,)c(the)i(limit)h(is)e(revised)g(and)h(search)f(performed)43
1774 y(again.)50 b(The)29 b(limit)h(can)f(be)g(de\002ned)g(in)g(terms)f
(of)h(tree)g(depth)g(\(depth\255bounded)h(DFS\),)e(or)h(in)g(terms)f
(of)h(solution)h(cost)43 1899 y(\(IDA*\).)39 b(In)25
b(depth\255\002rst)f(search,)h(if)h(the)g(lower)f(bound)h(of)g(a)f
(node)h(is)f(larger)g(than)h(the)g(cost)e(of)h(the)h(best)f(solution)h
(found)43 2023 y(thus)17 b(far)-5 b(,)19 b(then)e(the)h(node)f(can)g
(be)g(pruned.)31 b(This)17 b(technique)h(is)f(referred)g(to)g(as)g
(depth\255\002rst)f(branch\255and\255bound)h(\(DFBB\).)43
2208 y(In)j(all)h(algorithms)g(based)f(on)h(the)f(DFS)g(technique,)i
(once)e(a)g(successor)e(node)j Fi(n)e Fk(is)h(selected)h(for)f
(expansion,)h(its)f(sibling)43 2332 y(nodes)29 b(are)f(expanded)h(only)
g(after)g(the)f(entire)i(tree)e(rooted)h(at)g(node)g
Fi(n)f Fk(is)g(expanded,)j(even)d(if)h(successors)d(of)j
Fi(n)f Fk(are)43 2457 y(much)g(less)f(promising)h(than)g(the)g
(siblings)g(of)g Fi(n)p Fk(.)45 b(Thus,)28 b(these)g(algorithms)g(make)
g(use)f(of)h(the)g(heuristic)f(information)43 2581 y(only)21
b(on)g(a)g(local)g(scale)f(to)h(order)g(the)g(successors)d(of)i(a)h
(node.)32 b(DFBB)21 b(and)h(IDA*)f(also)g(make)f(a)h(limited)i(use)d
(of)h(heuristic)43 2706 y(information)j(on)f(a)f(global)i(scale)f(as)f
(they)g(prune)h(a)f(node)h(if)g(it)g(is)g(less)f(promising)h(than)g(a)f
(previously)h(found)g(solution)g(or)43 2830 y(bound.)34
b(As)23 b(we)h(will)g(discuss)f(later)-5 b(,)24 b(this)g(limited)h(use)
e(of)h(heuristics)f(makes)g(it)g(easy)g(to)h(develop)g(parallel)h
(formulations)43 2955 y(of)e(DFS)g(algorithms.)43 3140
y(In)h(contrast)g(to)g(DFS,)g(best\255\002rst)f(search)g(algorithms)i
(expand)f(the)h(most)f(promising)g(node)h(currently)f(available)h(on)g
(the)43 3264 y(search)i(frontier)-5 b(,)30 b(and)f(thus)e(make)h
(complete)h(use)f(of)g(the)g(available)i(heuristic)e(information.)49
b(The)28 b(search)f(frontier)h(is)43 3389 y(maintained)g(as)d(a)g
(priority)h(queue,)h(and)f(is)f(commonly)h(referred)f(to)g(as)g(the)h
(OPEN)g(list)2893 3359 y Fh(1)2930 3389 y Fk(.)39 b(A)26
b(well)h(known)e(algorithm)i(of)43 3513 y(this)i(type)g(is)g(A*,)i
(also)e(referred)f(to)h(as)g(best\255\002rst)e(branch)h(and)i(bound)f
(\(BFBB\).)g(A)h(major)f(price)g(paid)g(for)g(this)g(use)g(of)43
3638 y(heuristic)c(information)h(in)f(a)f(global)i(context)f(is)f(that)
h(BFS)g(requires)f(memory)h(proportional)h(to)e(the)h(size)f(of)h(the)g
(search)43 3762 y(frontier)-5 b(,)38 b(which)c(is)g(often)h
(exponential)h(in)e(the)h(depth)g(of)f(the)g(solution.)67
b(In)34 b(contrast,)i(all)g(DFS)e(algorithms)h(require)43
3887 y(memory)23 b(proportional)h(to)g(the)f(depth)h(of)f(the)h
(solution)g(path.)43 4071 y(In)19 b(many)g(applications,)i(identical)g
(states)d(can)h(be)g(reached)g(from)g(multiple)i(paths.)31
b(Re\255expansion)19 b(of)g(these)g(states)f(can)43 4196
y(be)26 b(avoided)f(if)h(the)g(search)e(technique)i(checks)e(every)g
(generated)i(node)f(for)g(possible)h(replications.)40
b(BFS)25 b(strategies)43 4320 y(support)d(replication)h(checking)e(by)h
(maintaining)i(a)e(list)h(of)f(all)g(the)h(expanded)f(nodes)g(\(and)g
(their)g(costs\))f(on)h(a)g(list)g(called)43 4445 y(CLOSED)384
4415 y Fh(1)421 4445 y Fk(.)31 b(DFS)19 b(based)g(techniques)g(do)h
(not)f(support)g(replication)h(checking,)g(and)f(thus)g(essentially)g
(unroll)h(the)g(graph)43 4569 y(into)28 b(a)f(tree.)44
b(Unrolling)29 b(graphs)d(into)i(trees)f(can)f(have)h(overheads)g
(ranging)h(from)f(a)g(constant)g(factor)f(to)h(exponential)43
4694 y(depending)d(on)f(the)g(structure)f(of)h(the)f(graph.)33
b(In)23 b(the)g(latter)g(case,)f(DFS)h(techniques)g(may)f(be)h
(unsuitable,)h(as)e(they)h(will)43 4819 y(need)28 b(to)g(expand)h(many)
e(more)h(nodes)g(than)g(BFS.)h(Finally)-6 b(,)29 b(simple)g(and)f
(directed)g(DFS)g(are)g(generally)g(used)g(to)g(\002nd)43
4943 y(the)e(\002rst)f(solution)i(that)f(they)g(encounter)g(in)g(the)h
(search)e(space,)h(whereas)f(DFBB,)i(IDA*,)g(and)g(BFS)f(\002nd)g(a)g
(least)g(cost)43 5068 y(solution.)34 b(This)22 b(taxonomy)h(of)h
(search)e(characteristics)g(is)h(illustrated)h(in)g(Figure)f(1.)p
43 5139 1560 4 v 131 5196 a Fg(1)163 5219 y Fl(OPEN)17
b(and)g(CLOSED)g(data)h(structures)g(are)f(called)g(lists)h(for)f
(historical)g(reasons.)26 b(In)18 b(fact,)h(OPEN)e(list)h(is)f
(typically)g(implemented)g(using)g(a)g(heap)43 5318 y(and)h(CLOSED)h
(list)f(is)h(implemented)g(as)f(a)h(hash)f(table.)1970
5610 y Fk(3)p eop
%%Page: 4 4
4 3 bop 43 344 a Fk(Although)36 b(a)e(central)g(component)h(of)f(most)g
(parallel)i(search)d(algorithms)i(is)f(a)g(dynamic)g(load)h(balancing)g
(scheme,)43 469 y(the)j(parallel)g(formulation)h(is)e(impacted)h(by)f
(the)g(nature)h(of)f(the)h(search)e(space,)k(the)e(use)f(of)g
(heuristics,)j(memory)43 593 y(requirements,)20 b(and)f(the)f(desired)h
(solution)g(quality)-6 b(.)32 b(In)18 b(the)h(following)h(sections,)f
(we)f(discuss)f(the)i(parallel)h(formulations)43 718
y(developed)k(for)f(various)g(search)f(algorithms.)205
2054 y @beginspecial 0 @llx 0 @lly 455 @urx 154 @ury
4320 @rwi @setspecial
%%BeginDocument: search.eps
%Magnification: 0.80
/$F2psDict 200 dict def
$F2psDict begin
$F2psDict /mtrx matrix put
/col-1 {0 setgray} bind def
/col0 {0.000 0.000 0.000 srgb} bind def
/col1 {0.000 0.000 1.000 srgb} bind def
/col2 {0.000 1.000 0.000 srgb} bind def
/col3 {0.000 1.000 1.000 srgb} bind def
/col4 {1.000 0.000 0.000 srgb} bind def
/col5 {1.000 0.000 1.000 srgb} bind def
/col6 {1.000 1.000 0.000 srgb} bind def
/col7 {1.000 1.000 1.000 srgb} bind def
/col8 {0.000 0.000 0.560 srgb} bind def
/col9 {0.000 0.000 0.690 srgb} bind def
/col10 {0.000 0.000 0.820 srgb} bind def
/col11 {0.530 0.810 1.000 srgb} bind def
/col12 {0.000 0.560 0.000 srgb} bind def
/col13 {0.000 0.690 0.000 srgb} bind def
/col14 {0.000 0.820 0.000 srgb} bind def
/col15 {0.000 0.560 0.560 srgb} bind def
/col16 {0.000 0.690 0.690 srgb} bind def
/col17 {0.000 0.820 0.820 srgb} bind def
/col18 {0.560 0.000 0.000 srgb} bind def
/col19 {0.690 0.000 0.000 srgb} bind def
/col20 {0.820 0.000 0.000 srgb} bind def
/col21 {0.560 0.000 0.560 srgb} bind def
/col22 {0.690 0.000 0.690 srgb} bind def
/col23 {0.820 0.000 0.820 srgb} bind def
/col24 {0.500 0.190 0.000 srgb} bind def
/col25 {0.630 0.250 0.000 srgb} bind def
/col26 {0.750 0.380 0.000 srgb} bind def
/col27 {1.000 0.500 0.500 srgb} bind def
/col28 {1.000 0.630 0.630 srgb} bind def
/col29 {1.000 0.750 0.750 srgb} bind def
/col30 {1.000 0.880 0.880 srgb} bind def
/col31 {1.000 0.840 0.000 srgb} bind def

end
save
-72.0 233.0 translate
1 -1 scale

/cp {closepath} bind def
/ef {eofill} bind def
/gr {grestore} bind def
/gs {gsave} bind def
/sa {save} bind def
/rs {restore} bind def
/l {lineto} bind def
/m {moveto} bind def
/rm {rmoveto} bind def
/n {newpath} bind def
/s {stroke} bind def
/sh {show} bind def
/slc {setlinecap} bind def
/slj {setlinejoin} bind def
/slw {setlinewidth} bind def
/srgb {setrgbcolor} bind def
/rot {rotate} bind def
/sc {scale} bind def
/sd {setdash} bind def
/ff {findfont} bind def
/sf {setfont} bind def
/scf {scalefont} bind def
/sw {stringwidth} bind def
/tr {translate} bind def
/tnt {dup dup currentrgbcolor
  4 -2 roll dup 1 exch sub 3 -1 roll mul add
  4 -2 roll dup 1 exch sub 3 -1 roll mul add
  4 -2 roll dup 1 exch sub 3 -1 roll mul add srgb}
  bind def
/shd {dup dup currentrgbcolor 4 -2 roll mul 4 -2 roll mul
  4 -2 roll mul srgb} bind def
/$F2psBegin {$F2psDict begin /$F2psEnteredState save def} def
/$F2psEnd {$F2psEnteredState restore end} def

$F2psBegin
10 setmiterlimit
n 0 792 m 0 0 l 612 0 l 612 792 l cp clip
 0.04800 0.04800 sc
7.500 slw
% Polyline
n 6600 2100 m 6675 2100 l 6675 4275 l 6600 4275 l gs col-1 s gr 
% Polyline
n 6600 4500 m 6675 4500 l 6675 4800 l 6600 4800 l gs col-1 s gr 
% Polyline
n 8400 2100 m 8475 2100 l 8475 2475 l 8400 2475 l gs col-1 s gr 
% Polyline
n 8400 2700 m 8475 2700 l 8475 3075 l 8400 3075 l gs col-1 s gr 
% Polyline
n 8400 3300 m 8475 3300 l 8475 4275 l 8400 4275 l gs col-1 s gr 
% Polyline
n 8400 4500 m 8475 4500 l 8475 4800 l 8400 4800 l gs col-1 s gr 
% Polyline
n 9900 2100 m 9975 2100 l 9975 3075 l 9900 3075 l gs col-1 s gr 
% Polyline
n 9900 3300 m 9975 3300 l 9975 4800 l 9900 4800 l gs col-1 s gr 
% Polyline
n 5025 2100 m 5100 2100 l 5100 4275 l 5025 4275 l gs col-1 s gr 
% Polyline
n 5025 4500 m 5100 4500 l 5100 4800 l 5025 4800 l gs col-1 s gr 
/Helvetica ff 180.00 scf sf
1500 2400 m
gs 1 -1 sc (Simple DFS \(Backtracking\)) col-1 sh gr
/Helvetica ff 180.00 scf sf
1500 3000 m
gs 1 -1 sc (Directed DFS \(Ordered Backtracking\)) col-1 sh gr
/Helvetica ff 180.00 scf sf
1500 3600 m
gs 1 -1 sc (Depth-First Branch and Bound) col-1 sh gr
/Helvetica ff 180.00 scf sf
1500 4200 m
gs 1 -1 sc (IDA*) col-1 sh gr
/Helvetica ff 180.00 scf sf
1500 4800 m
gs 1 -1 sc (Best-First Search / A*) col-1 sh gr
/Helvetica ff 180.00 scf sf
6975 3000 m
gs 1 -1 sc (Linear) col-1 sh gr
/Helvetica ff 180.00 scf sf
6975 3240 m
gs 1 -1 sc (in) col-1 sh gr
/Helvetica ff 180.00 scf sf
6975 3480 m
gs 1 -1 sc (Depth) col-1 sh gr
/Helvetica ff 180.00 scf sf
6975 4725 m
gs 1 -1 sc (Exponential) col-1 sh gr
/Helvetica ff 180.00 scf sf
6675 2040 m
gs 1 -1 sc (Requirement) col-1 sh gr
/Helvetica ff 180.00 scf sf
8775 2325 m
gs 1 -1 sc (None) col-1 sh gr
/Helvetica ff 180.00 scf sf
8775 2925 m
gs 1 -1 sc (Local) col-1 sh gr
/Helvetica ff 180.00 scf sf
8775 3750 m
gs 1 -1 sc (Partially) col-1 sh gr
/Helvetica ff 180.00 scf sf
8775 3990 m
gs 1 -1 sc (Global) col-1 sh gr
/Helvetica ff 180.00 scf sf
8775 4725 m
gs 1 -1 sc (Global) col-1 sh gr
/Helvetica ff 180.00 scf sf
8475 1800 m
gs 1 -1 sc (Heuristic) col-1 sh gr
/Helvetica ff 180.00 scf sf
9975 1800 m
gs 1 -1 sc (Solution) col-1 sh gr
/Helvetica ff 180.00 scf sf
9975 2040 m
gs 1 -1 sc (Quality) col-1 sh gr
/Helvetica ff 180.00 scf sf
10275 2625 m
gs 1 -1 sc (Any) col-1 sh gr
/Helvetica ff 180.00 scf sf
10275 2865 m
gs 1 -1 sc (Solution) col-1 sh gr
/Helvetica ff 180.00 scf sf
10275 4050 m
gs 1 -1 sc (Best) col-1 sh gr
/Helvetica ff 180.00 scf sf
10275 4290 m
gs 1 -1 sc (Solution) col-1 sh gr
/Helvetica ff 180.00 scf sf
6675 1800 m
gs 1 -1 sc (Memory) col-1 sh gr
/Helvetica ff 180.00 scf sf
5100 1800 m
gs 1 -1 sc (Nature of) col-1 sh gr
/Helvetica ff 180.00 scf sf
5100 2040 m
gs 1 -1 sc (Search Space) col-1 sh gr
/Helvetica ff 180.00 scf sf
5400 3075 m
gs 1 -1 sc (Tree) col-1 sh gr
/Helvetica ff 180.00 scf sf
5400 3315 m
gs 1 -1 sc (Search) col-1 sh gr
/Helvetica ff 180.00 scf sf
5400 4575 m
gs 1 -1 sc (Graph/Tree) col-1 sh gr
/Helvetica ff 180.00 scf sf
5400 4815 m
gs 1 -1 sc (Search) col-1 sh gr
$F2psEnd
rs
%%EndDocument
 @endspecial 603 2262 a(Figure)h(1:)33 b(V)-6 b(arious)23
b(enumerative)h(search)e(procedures)g(and)i(their)g(characteristics.)43
2701 y Fj(3)116 b(Depth\255First)31 b(Search)43 2986
y Fk(Depth\255\002rst)21 b(search)h(is)h(particularly)f(amenable)i(to)f
(parallel)h(processing)e(primarily)h(because)g(a)f(subtree)h(rooted)f
(at)h(any)43 3110 y(node)h(can)f(be)h(searched)f(relatively)h
(independently)h(of)e(the)h(search)f(at)g(other)h(nodes)f(or)h
(subtrees.)32 b(In)24 b(fact,)f(searching)43 3235 y(dif)o(ferent)39
b(subtrees)g(concurrently)f(requires)h(either)g(no)h(communication)g
(\(e.g.,)j(backtracking,)f(IDA*\))d(or)g(minimal)43 3359
y(communication)33 b(\(e.g.,)g(DFBB\).)f(This)f(is)h(due)g(to)f(the)h
(fact)f(that)h(DFS)g(techniques)g(do)f(not)h(make)g(use)f(of)g
(heuristics)43 3484 y(on)d(a)g(global)i(scale.)46 b(It)28
b(would)h(therefore)f(seem)g(that)h(by)e(statically)h(assigning)h
(nodes)f(in)g(a)g(tree)g(to)h(processors,)e(it)h(is)43
3608 y(possible)22 b(to)g(derive)g(parallel)i(formulations.)33
b(However)-5 b(,)22 b(for)g(most)f(applications,)j(trees)d(generated)i
(by)e(DFS)h(tend)h(to)f(be)43 3733 y(highly)g(irregular)-5
b(,)22 b(and)f(it)g(is)g(very)f(dif)o(\002cult)g(to)h(estimate)h(the)f
(work)f(associated)h(with)g(a)g(node)h(a\255priori.)31
b(Hence,)22 b(any)e(static)43 3857 y(allocation)j(of)e(subtrees)g(to)g
(processors)f(is)h(bound)h(to)f(result)g(in)h(signi\002cant)g(load)g
(imbalance)g(among)g(processors.)30 b(The)43 3982 y(core)25
b(of)g(parallel)i(formulations)g(of)e(DFS)h(algorithms)g(is)f(thus)g(a)
h(dynamic)f(load)h(balancing)h(technique)f(that)g(minimizes)43
4106 y(inter\255processor)c(communication)i(and)g(processor)d(idling.)
43 4291 y(A)26 b(number)g(of)g(load)g(distribution)h(techniques)f(have)
g(been)g(developed)g(for)g(parallel)h(DFS)e([25)q(,)g(41)q(,)g(22)q(,)g
(17)q(,)g(21)q(].)39 b(Load)43 4415 y(balancing)26 b(techniques)f(may)f
(be)h(receiver)f(initiated)j(or)d(sender)g(initiated.)39
b(In)25 b(receiver)f(initiated)i(techniques,)g(when)f(a)43
4540 y(processor)g(becomes)h(idle,)i(it)f(requests)f(a)h(selected)f
(processor)f(for)h(work.)42 b(Many)26 b(dif)o(ferent)h(selection)g
(policies)g(have)43 4665 y(been)19 b(proposed)g(such)f(as)g(use)h(of)g
(a)f(centralized)h(server)-5 b(,)19 b(random)g(polling)i([12],)f
(nearest)e(neighbor)i([25],)g(global)g(round\255)43 4789
y(robin)i([25)q(],)g(and)g(asynchronous)e(round)i(robin)g([12,)g(25].)
32 b(In)22 b(contrast)f(to)h(receiver)f(initiated)i(load)g(balancing,)g
(in)f(sender)43 4914 y(initiated)e(schemes,)e(a)g(processor)f(sends)g
(work)g(to)i(selected)f(processors)e(as)h(it)i(is)e(generated.)32
b(Selection)19 b(strategies)f(for)43 5038 y(sender)h(initiated)i(work)e
(transfers)f(include)j(hierarchical)e(techniques)h(\(with)g
(super\255servers,)d(servers)h(and)h(clients\))g([13)q(],)43
5163 y(random)k(sampling)h([25)q(],)f(and)g(near\255neighbor)h
(techniques)f([41].)33 b(The)22 b(quanta)i(of)f(work)f(farmed)h(out)h
(to)f(processors)d(in)43 5287 y(sender)27 b(and)h(receiver)e(initiated)
j(schemes)e(ranges)g(from)g(a)g(single)h(state)g(\(node)f(in)h(the)g
(tree\))e(to)i(forests)e(of)i(subtrees)1970 5610 y(4)p
eop
%%Page: 5 5
5 4 bop 43 344 a Fk(resulting)21 b(from)g(stack)f(splitting)i([12,)f
(25].)32 b(Schemes)21 b(for)f(fault)i(tolerance)f(using)g
(acknowledgements)h(have)e(also)h(been)43 469 y(built)j(into)g(load)g
(balancing)h(techniques)e([12)q(].)43 653 y(The)34 b(performance)f(and)
h(scalability)g(of)g(these)f(techniques)h(is)f(often)i(dependent)f(on)g
(the)g(underlying)g(architecture.)43 778 y(Many)e(of)g(these)f
(techniques)h(are,)i(in)f(principle)f(scalable,)j(i.e.,)f(they)e
(result)g(in)g(linear)h(speedup)f(on)g(increasing)g(the)43
903 y(number)c(of)f(processors)f Fi(p)h Fk(as)g(long)h(as)f(the)g(size)
g(of)h(the)g(search)e(space)h(grows)f(fast)i(enough)g(with)g
Fi(p)p Fk(.)45 b(It)27 b(is)g(desirable)43 1027 y(that)21
b(this)f(required)h(rate)f(of)h(growth)f(of)h(problem)g(size)f(\(also)g
(referred)g(to)h(as)f(the)g(Isoef)o(\002ciency)f(metric)h([24)q(]\))g
(be)g(as)g(small)43 1152 y(as)k(possible)h(since)g(it)g(allows)g(the)g
(use)f(of)h(a)f(larger)h(number)g(of)g(processors)d(ef)o(fectively)i
(for)h(solving)g(a)f(given)h(problem)43 1276 y(instance.)43
1461 y(The)17 b(irregular)h(and)g(dynamic)f(nature)g(of)h(the)f(search)
g(space)f(makes)h(it)h(dif)o(\002cult)f(to)g(precisely)g(compute)g(the)
h(performance)43 1585 y(and)34 b(scalability)h(of)f(parallel)i(DFS.)e
(However)-5 b(,)37 b(for)d(trees)f(with)i(branching)f(factor)g(greater)
g(than)g(1)25 b Ff(+)f Fi(\017)34 b Fk(\(for)f(a)h(small)43
1710 y(constant)28 b Fi(\017)p Fk(\),)h(it)g(is)g(often)g(possible)g
(to)f(partition)i(the)f(computation)g(associated)g(with)g(a)f
(collection)h(of)g(nodes)g(into)g(two)43 1834 y(parts)21
b(such)h(that)g(the)g(smaller)h(of)f(these)f(two)i(parts)e(can)h(be)g
(guaranteed)h(to)f(have)f(a)h(minimum)i(\002xed)d(constant)h(fraction)
43 1959 y(of)38 b(the)g(computation)h(associated)f(with)g(the)g
(original)i(node.)77 b(This)37 b(property)h(has)f(been)i(used)f(to)g
(derive)f(parallel)43 2083 y(formulations)c(of)g(DFS)f(with)h(isoef)o
(\002ciency)e(of)h Fi(O)r Ff(\()p Fi(p)14 b Fk(log)1856
2043 y Fh(2)1906 2083 y Fi(p)p Ff(\))32 b Fk(on)h(hypercube)f(and)g
Fi(O)r Ff(\()p Fi(p)2866 2053 y Fh(1)p Fe(:)p Fh(5)2969
2083 y Fk(log)15 b Fi(p)p Ff(\))32 b Fk(on)h(mesh)f(connected)43
2208 y(parallel)25 b(computers)d([25)q(].)43 2392 y(The)27
b(parallel)h(formulation)g(of)f(DFS)g(described)g(above)g(can)f(be)h
(applied)i(to)e(DFBB)g(with)g(one)g(minor)h(modi\002cation.)44
b(In)43 2517 y(DFBB,)19 b(we)g(need)h(to)f(keep)g(all)h(the)f
(processors)e(informed)j(of)f(the)g(current)f(best)h(solution.)32
b(On)19 b(a)g(shared)f(address)h(space)43 2641 y(architecture,)29
b(this)f(can)f(be)h(done)h(easily)f(by)f(maintaining)k(a)d(global)h
(best)f(solution)g(in)h(globally)g(accessible)e(memory)-6
b(.)43 2766 y(On)22 b(a)f(message)h(passing)g(computer)-5
b(,)22 b(this)g(can)g(be)g(done)g(by)g(allowing)h(each)f(processor)e
(to)i(maintain)i(the)e(current)f(best)43 2891 y(solution)33
b(known)f(to)g(it.)60 b(Whenever)32 b(a)g(processor)f(\002nds)g(a)h
(solution)h(path)g(better)f(than)h(the)f(current)f(best)h(known,)j(it)
43 3015 y(broadcasts)25 b(it)h(to)g(all)h(the)f(other)g(processors)d
(which)j(update)h(\(if)f(necessary\))d(their)j(current)g(best)f
(solution)i(path.)41 b(Note)43 3140 y(that)20 b(if)h(a)f(processor)s(')
o(s)e(current)h(best)h(solution)h(path)f(is)g(worse)g(than)g(the)g
(global)i(best)e(solution)h(path,)g(then)f(it)h(only)f(af)o(fects)43
3264 y(the)25 b(ef)o(\002ciency)f(of)h(the)h(search)e(but)h(not)h(its)f
(correctness.)36 b(The)25 b(overhead)g(for)g(maintaining)i(the)f
(current)e(best)h(solution)43 3389 y(tends)20 b(to)g(be)h(a)f(small)h
(fraction)f(of)g(the)h(overhead)f(for)g(dynamic)g(load)h(balancing.)32
b(Parallel)22 b(formulations)f(of)g(DFBB)f(have)43 3513
y(been)k(shown)f(to)g(yield)h(near)f(linear)h(speedups)f(for)g(many)g
(problems)h(and)f(architectures)g([45,)g(27,)h(8,)f(7,)g(1].)43
3839 y Fd(T)-6 b(ermination)22 b(of)h(Parallel)h(Search)43
4089 y Fk(If)30 b(only)g(one)g(solution)h(is)f(desired)g(to)g(a)g
(problem)h(instance)f(being)h(solved)e(using)i(depth\255\002rst)d
(search,)j(then)g(as)e(soon)43 4214 y(as)g(any)f(processor)g(\002nds)g
(a)h(solution,)j(search)c(at)h(other)g(processors)e(needs)i(to)g(be)h
(terminated.)51 b(On)29 b(some)f(parallel)43 4338 y(architectures,)23
b(it)h(is)g(possible)g(for)g(one)g(processor)e(to)i(interrupt)g(other)g
(processors)e(and)i(send)g(them)g(a)g(special)g(signal.)43
4463 y(If)29 b(such)f(a)h(mechanism)h(is)e(not)i(available,)i(then)d
(each)g(processor)e(needs)i(to)g(perform)g(a)g(periodic)h(check)e(to)h
(see)f(if)i(a)43 4587 y(solution)24 b(has)f(been)h(found.)43
4772 y(If)c(all)g(the)g(solutions)g(\(or)f(all)h(best)g(solutions\))f
(to)h(a)g(problem)g(instance)g(are)f(desired,)i(then)f(parallel)h(DFS)e
(searches)f(a)i(well)43 4896 y(de\002ned)28 b(portion)h(of)f(the)h
(entire)g(search)e(tree)h(\(determined)h(by)e(the)i(speci\002c)e
(algorithm)i(and)f(heuristic)h(used\).)46 b(Since)43
5021 y(this)22 b(search)e(space)h(is)g(dynamically)h(allocated)h(to)e
(processors,)f(it)i(is)f(not)h(suf)o(\002cient)e(to)i(poll)g(each)f
(processor)f(serially)i(to)43 5146 y(check)f(if)i(they)g(have)f
(exhausted)g(their)h(work.)32 b(The)22 b(reason)g(is)h(that)g(a)f
(processor)f(may)h(pick)g(up)h(work)f(after)g(it)h(has)f(been)43
5270 y(polled.)52 b(Hence)29 b(a)h(distributed)g(termination)h
(detection)f(algorithm)g(is)f(needed)i(to)e(ensure)g(that)h(all)g
(processors)d(have)1970 5610 y(5)p eop
%%Page: 6 6
6 5 bop 43 344 a Fk(indeed)24 b(exhausted)f(the)h(search)e(space)h
([5].)43 744 y Fj(4)116 b(Best\255First)31 b(Search)43
1029 y Fk(Best\255\002rst)k(search)g(techniques)i(are)f(more)g(dif)o
(\002cult)g(to)h(parallelize)h(for)e(the)h(following)h(two)e(reasons:)
58 b(\(i\))36 b(they)g(use)43 1153 y(heuristics)19 b(on)i(a)f(global)h
(scale,)f(making)h(it)f(harder)g(to)g(utilize)h(the)f(full)h(power)f
(of)g(heuristics)f(in)i(a)f(parallel)h(setting;)h(and)e(\(ii\))43
1278 y(they)h(need)h(to)g(maintain)h(the)f(CLOSED)g(list)f(if)h(the)g
(search)f(space)f(is)i(a)f(graph.)32 b(W)o(e)22 b(\002rst)e(discuss)g
(parallel)j(formulations)43 1402 y(of)g(best\255\002rst)f(search)g(in)i
(the)f(context)g(of)g(state\255space)f(trees,)h(and)h(subsequently)f
(discuss)f(the)h(case)g(for)g(graphs.)43 1587 y(BFS)f(methods)g(may)f
(appear)h(inherently)g(serial)g(since)f(they)g(require)h(expansion)g
(of)g(the)f(most)h(promising)g(node)g(on)g(the)43 1711
y(OPEN)27 b(list)h(at)f(each)g(step.)44 b(However)-5
b(,)28 b(it)g(is)f(possible)g(that)h(many)f(nodes)g(on)g(the)g(OPEN)h
(list)f(are)g(equally)h(promising,)43 1836 y(in)f(which)g(case,)h(they)
e(can)h(all)h(be)f(expanded)g(concurrently)-6 b(.)43
b(If)27 b(the)g(number)g(of)g(such)f(\(equally\))i(promising)f(nodes)g
(is)43 1960 y(fewer)22 b(than)h(the)g(number)f(of)h(available)h
(processors,)c(then)j(the)g(other)f(less)g(promising)h(nodes)g
(available)g(on)g(OPEN)g(list)43 2085 y(can)h(be)h(searched)f(by)h(the)
g(idle)g(processors.)35 b(These)25 b(less)f(promising)h(nodes)g(may)f
(not)h(be)g(searched)f(by)h(serial)f(BFS,)43 2209 y(and)29
b(thus)f(form)h(speculative)f(work.)48 b(The)28 b(ef)o(fective)g
(degree)h(of)g(concurrency)d(of)j(such)f(a)g(formulation)i(is)e
(essentially)43 2334 y(equal)22 b(to)g(the)f(average)g(number)h(of)f
(nodes)g(available)i(on)f(the)f(OPEN)h(list)f(such)g(that)g(their)h
(cost)e(is)h(less)g(than)h(that)f(of)h(the)43 2458 y(optimal)f
(solution.)32 b(Since)20 b(the)g(cost)f(of)g(the)h(optimal)h(solution)f
(is)g(unknown,)g(a)g(good)f(strategy)g(is)g(to)h(always)f(expand)h
(only)43 2583 y(the)k Fi(p)p Fk(\255most)f(promising)i(nodes)f
(currently)f(available)j(on)e(the)g(OPEN)g(list;)h(where)f
Fi(p)f Fk(is)h(the)g(number)h(of)f(processors.)32 b(As)43
2707 y(long)24 b(as)f Fi(p)g Fk(is)g(no)h(more)f(than)h(the)g(ef)o
(fective)f(degree)g(of)h(concurrency)-6 b(,)21 b(all)k(processors)c
(will)j(tend)g(to)g(search)e(nodes)i(that)43 2832 y(will)j(also)e(be)h
(searched)f(by)g(serial)h(BFS.)g(The)f(ef)o(fective)g(degree)h(of)g
(concurrency)d(is)i(usually)h(dependent)h(on)f(the)f(size)43
2957 y(of)e(the)g(search)e(space)h(\(larger)h(spaces)e(have)i(higher)g
(degree)g(of)g(concurrency\))d(and)j(the)g(heuristic)g(function)g
(\(stronger)43 3081 y(heuristics)g(lead)h(to)f(smaller)h(degree)f(of)g
(concurrency\).)43 3266 y(The)28 b(basic)g(data)g(structure)f(of)h
(BFS,)h(the)f(OPEN)g(list,)i(is)e(a)g(priority)g(queue)g(that)h(must)f
(support)g(removal)g(of)g(the)g(best)43 3390 y(entry)i(in)g(the)h
(queue)g(and)g(insertion)f(of)h(nodes)f(into)h(the)g(queue.)54
b(The)30 b(data)h(structure)e(most)h(often)h(used)f(for)g(this)g(is)43
3515 y(a)h(heap.)56 b(The)31 b(simplest)g(parallel)i(formulation)f(of)f
(BFS)h(uses)e(multiple)j(processors)28 b(working)j(on)g(a)g(heap)h
(stored)e(in)43 3639 y(globally)h(addressable)e(memory)-6
b(.)51 b(Each)29 b(processor)f(locks)g(the)i(heap)g(and)g(picks)e(out)i
(the)g(current)e(best)h(node.)52 b(The)43 3764 y(heap)32
b(is)g(unlocked)g(and)g(the)g(node)g(is)g(expanded)g(to)g(yield)g(its)g
(children.)58 b(These)32 b(children)g(are)f(reinserted)h(into)h(the)43
3888 y(heap)24 b(with)f(appropriate)h(locking.)32 b(The)23
b(use)g(of)g(a)g(global)i(heap)e(is)g(a)g(source)f(of)h(contention.)33
b(If)23 b(the)h(time)f(taken)g(to)g(lock,)43 4013 y(remove,)h(and)h
(unlock)f(the)g(top)g(element)i(of)e(the)g(heap)h(is)f
Fi(t)1947 4025 y Fe(access)2164 4013 y Fk(and)h(time)g(for)f(expansion)
g(is)g Fi(t)3145 4025 y Fe(exp)3252 4013 y Fk(,)h(then)f(the)h(speedup)
43 4137 y(of)e(the)h(formulation)h(is)e(bounded)h(by)f
Ff(\()p Fi(t)1310 4149 y Fe(access)1522 4137 y Ff(+)18
b Fi(t)1635 4149 y Fe(exp)1742 4137 y Ff(\))p Fi(=t)1846
4149 y Fe(access)2040 4137 y Fk(.)43 4322 y(Many)26 b(techniques)h
(have)g(been)g(developed)g(to)g(ef)o(fectively)f(reduce)g
Fi(t)2327 4334 y Fe(access)2547 4322 y Fk(and)h(thus)f(increase)g(the)h
(available)h(paral\255)43 4446 y(lelism.)33 b(These)22
b(techniques)h(support)g(multiple)h(operations)f(on)g(heaps)f(stored)h
(in)g(shared)f(memory)g(while)i(maintaining)43 4571 y(the)35
b(strict)e(deletion)j(and)f(insertion)g(ordering)g([42].)66
b(The)34 b(performance)h(of)f(these)g(schemes)g(scales)f(to)i(dozens)f
(of)43 4695 y(processors)21 b(but)j(is)f(ultimately)h(limited)h(by)e
(the)g(locking)h(and)f(access)f(times)h(as)g(speci\002ed)g(above.)43
4880 y(Another)k(way)e(of)i(alleviating)h(the)e(contention)h(overhead)f
(associated)g(with)h(a)f(single)h(global)g(heap)g(is)f(to)g(use)g
(multiple)43 5005 y(heaps.)38 b(The)24 b(concept)h(of)g
Fi(p)f Fk(processors)f(sharing)i(a)g(single)g(heap)h(can)e(be)h
(relaxed)g(to)g Fi(k)j Fk(processors)23 b(sharing)i(a)f(heap)43
5129 y(with)g Fi(p=k)i Fk(heaps)d(in)h(all.)35 b(The)23
b(number)h Fi(k)i Fk(is)d(selected)h(by)f(studying)h(the)f(overheads)h
(associated)f(with)h(communication)43 5254 y(and)18 b(locking,)i
(contention,)g(and)e(node)h(expansion)f(time.)32 b(In)18
b(the)g(extreme)g(case,)g(each)g(processor)f(has)g(its)h(own)g(heap.)32
b(A)1970 5610 y(6)p eop
%%Page: 7 7
7 6 bop 43 344 a Fk(simple)20 b(parallel)g(formulation)g(based)f(on)g
(multiple)h(heaps)f(starts)f(with)h(the)g(initial)i(state)d(in)h(a)g
(single)h(heap.)31 b(As)19 b(additional)43 469 y(nodes)i(are)h
(generated,)g(they)f(are)g(farmed)h(out)g(to)f(other)g(heaps)h(\(using)
f(schemes)f(similar)i(to)g(load)g(balancing)g(in)g(DFS\).)43
593 y(Once)17 b(all)i(the)g(heaps)f(have)g(been)g(populated,)j
(processors)16 b(can)h(perform)h(BFS)h(on)f(individual)i(heaps.)31
b(This)17 b(formulation)43 718 y(has)g(a)g(signi\002cant)g(drawback)f
(in)h(that)h(although)g(it)g(balances)f(computation)h(among)f
(processors,)g(it)g(does)g(not)g(guarantee)43 842 y(the)k(quality)h(of)
f(nodes)g(individual)i(processors)c(explore.)32 b(Consequently)-6
b(,)21 b(processors)e(may)i(spend)g(considerable)g(time)43
967 y(exploring)j(parts)f(of)g(the)g(search)g(space)f(that)i(may)f(not)
g(be)h(explored)f(by)g(the)g(serial)h(formulation.)43
1152 y(T)-9 b(o)27 b(alleviate)j(this)d(drawback)g(of)h(excess)e(work)h
(performed)h(by)g(the)g(parallel)h(formulation,)i(one)d(must)f(ensure)h
(that)g(all)43 1276 y(heaps)35 b(have)f(a)h(share)f(of)h(the)g(most)f
(promising)h(nodes)g(globally)h(available.)68 b(This)35
b(process,)h(also)e(referred)h(to)f(as)43 1401 y(quality)22
b(equalization,)i(ensures)d(that)h(the)g(best)f(nodes)h(available)h
(globally)g(are)e(evenly)h(distributed)g(across)e(the)i(heaps.)43
1525 y(Since)27 b(the)g(quality)h(of)f(the)g(nodes)g(changes)f(as)h
(computation)h(proceeds,)f(quality)g(equalization)i(must)e(be)g
(performed)43 1650 y(periodically)-6 b(.)50 b(A)29 b(variety)f(of)h
(triggers)f(and)h(mechanisms)g(have)f(been)i(used)e(for)h(quality)g
(equalization)i([30,)e(6,)g(45,)g(4].)43 1774 y(A)k(simple)g
(triggering)g(mechanism)g(tracks)e(the)i(best)f(node)h(in)g(the)g
(system.)59 b(The)32 b(best)g(node)h(in)g(the)g(local)g(heap)g(is)43
1899 y(compared)21 b(to)g(the)g(best)g(node)g(in)h(the)f(system)f(and)h
(if)g(it)g(is)g(considerably)g(worse,)g(an)g(equalization)i(process)c
(is)i(initiated.)43 2023 y(Alternately)-6 b(,)24 b(an)g(equalization)h
(process)c(may)i(be)h(initiated)h(periodically)-6 b(.)43
2208 y(Quality)26 b(equalization)i(requires)e(movement)h(of)f(nodes)g
(between)h(heaps.)41 b(This)26 b(movement)h(of)f(nodes)g(can)g(be)g
(struc\255)43 2332 y(tured)33 b(\(into)f(a)h(ring,)i(or)d(via)h(a)f
(shared)g(blackboard\))h(or)f(randomized.)61 b(In)32
b(randomized)h(equalization,)k(a)c(processor)43 2457
y(periodically)i(selects)f(a)g(random)h(heap,)i(picks)c(up)i(the)f
(best)g(node)h(from)f(the)h(heap,)i(and)e(inserts)e(it)i(into)g(the)f
(local)43 2581 y(heap.)56 b(Alternately)-6 b(,)33 b(heaps)e(can)f(be)h
(organized)g(into)h(hierarchical)f(structures.)53 b(At)31
b(the)g(lower)g(levels,)i(equalization)43 2706 y(is)28
b(performed)h(more)g(frequently)g(than)g(the)g(higher)g(levels)f(in)h
(the)g(hierarchy)-6 b(.)48 b(Several)29 b(triggering)g(mechanisms)g
(and)43 2830 y(redistribution)c(strategies)f(have)g(been)g(explored)h
([6,)f(47].)35 b(It)24 b(has)g(been)g(shown)g(that)g(these)g(schemes)f
(are)h(capable)h(of)43 2955 y(providing)k(linearly)g(increasing)f
(speedups)h(with)f(number)h(of)f(processors)e(if)j(the)f(problem)h
(size)f(is)g(increased)g(appro\255)43 3080 y(priately)-6
b(.)41 b(Speci\002cally)-6 b(,)26 b(scalable)g(parallel)i(formulations)
e(of)g(best\255\002rst)e(tree)i(search)f(with)h(isoef)o(\002ciency)e
(of)i Fi(O)r Ff(\()p Fi(p)14 b Fk(log)3819 3039 y Fh(2)3869
3080 y Fi(p)p Ff(\))43 3204 y Fk(on)26 b(hypercube)f(architectures)g
(have)h(been)g(developed)h([30].)41 b(Using)25 b(these)h(schemes,)g
(speedups)f(in)i(excess)d(of)i(950)43 3329 y(have)20
b(been)g(demonstrated)g(on)h(1024)f(processor)e(hypercubes)h(in)h(the)g
(context)g(of)g(TSPs)g(formulated)h(as)e(best\255\002rst)f(tree)43
3453 y(search)k(problems)i([6].)43 3779 y Fd(Best\255First)f(Search)h
(of)e(State)h(Space)h(Graphs)43 4029 y Fk(Ef)o(\002cient)19
b(parallel)j(implementation)g(of)e(BFS)g(on)g(state)g(space)f(graphs)g
(requires)h(a)g(distributed)g(mechanism)g(that)g(allows)43
4154 y(many)h(processors)e(to)j(perform)f(duplicate)i(checking)d(or)h
(insertions)h(into)g(the)f(CLOSED)h(list)g(concurrently)-6
b(.)30 b(The)22 b(nature)43 4278 y(of)h(implementation)j(of)e(this)f
(mechanism)g(is)g(dependent)i(on)e(the)h(underlying)g(parallel)g
(architecture.)43 4463 y(In)d(shared)f(address)g(space)g(machines,)h
(insertion)g(of)g(nodes)f(into)i(the)e(closed)h(list)g(requires)f
(locking)h(of)f(the)h(list.)32 b(If)21 b(there)43 4587
y(is)26 b(a)h(single)g(lock)f(associated)g(with)h(the)f(entire)h(list,)
h(the)e(list)h(must)f(be)h(locked)f(approximately)h(as)f(many)g(times)h
(as)f(the)43 4712 y(total)32 b(number)g(of)f(nodes)g(expanded.)57
b(This)31 b(represents)f(a)h(serial)h(bottleneck.)56
b(The)32 b(bottleneck)f(can)g(be)g(alleviated)43 4836
y(by)25 b(associating)g(multiple)i(locks)d(with)i(the)g(closed)f(list.)
38 b(Processors)24 b(lock)g(only)i(relevant)f(parts)g(of)g(the)h
(closed)f(list)g(into)43 4961 y(which)d(the)h(node)g(is)f(being)h
(inserted.)32 b(Message)22 b(passing)g(formulations)i(of)e(this)g
(parallel)i(search)d(technique)i(distribute)43 5086 y(the)35
b(closed)f(list)h(across)e(the)i(processors.)65 b(Each)35
b(processor)e(expands)h(a)h(node)g(and)g(hashes)f(the)h(successors)d
(to)43 5210 y(appropriate)38 b(processors)c(via)j(a)g(message.)73
b(The)37 b(destination)h(processor)d(checks)g(for)i(replication)h(and)f
(sends)f(a)43 5335 y(message)19 b(back)g(specifying)h(whether)f(the)h
(node)g(exists)f(in)h(the)g(closed)f(list)h(or)g(not.)31
b(Such)20 b(a)f(protocol)h(requires)g(two\255way)1970
5610 y(7)p eop
%%Page: 8 8
8 7 bop 43 344 a Fk(cooperation)24 b(between)f(various)f(processors.)31
b(Each)23 b(processor)e(must)i(periodically)g(check)f(for)h(incoming)h
(messages,)43 469 y(process)e(them)h(and)h(send)f(appropriate)h
(responses.)43 653 y(A)29 b(simpler)g(parallel)h(formulation)g(uses)d
(the)i(hash)f(function)h(both)g(for)g(replication)g(checking)f(and)h
(for)f(qualitative)j(and)43 778 y(quantitative)26 b(load)g(balance.)38
b(In)25 b(this)g(formulation,)i(the)e(successors)d(of)j(a)g(node)g(are)
g(hashed)g(to)g(appropriate)g(proces\255)43 903 y(sors.)36
b(The)25 b(destination)h(processor)d(checks)g(for)h(replication)i(as)f
(before.)37 b(However)-5 b(,)25 b(instead)g(of)g(sending)h(a)f
(response)43 1027 y(back,)18 b(it)h(inserts)e(the)i(successor)c(nodes)j
(into)h(its)f(own)g(open)h(list.)31 b(This)17 b(has)h(two)g(main)h
(advantages:)30 b(\(i\))18 b(it)g(eliminates)i(the)43
1152 y(need)f(for)f(a)g(return)g(message)g(and)h(wait)g(at)f(the)h
(source)e(processor;)h(and)h(\(ii\))f(the)h(randomized)g(hash)f
(function)h(serves)d(as)43 1276 y(the)24 b(method)g(for)g(balancing)h
(load)f(qualitatively)h(and)f(quantitatively)-6 b(.)35
b(These)23 b(schemes)g(have)h(been)g(studied)g(by)f(many)43
1401 y(researchers)g([33)q(,)i(30].)38 b(Assuming)26
b(a)f(perfectly)g(random)g(hash)g(function,)i(it)e(has)g(been)h(shown)f
(that)g(if)h(the)f(number)h(of)43 1525 y(nodes)d(originating)i(at)f
(each)f(processor)e(grows)i(as)f Fi(O)r Ff(\()p Fk(log)16
b Fi(p)p Ff(\))p Fk(,)23 b(then)h(each)f(processor)e(will)k(have)e
(asymptotically)g(equal)43 1650 y(number)h(of)f(nodes)g(after)g(the)h
(hash)f(operation)h([33].)43 1834 y(One)31 b(of)g(the)g(major)h
(drawbacks)e(of)h(graph)g(search)f(techniques)h(such)g(as)f(BFS)i(is)f
(that)g(their)g(memory)g(requirement)43 1959 y(grows)c(linearly)h(with)
g(the)g(search)f(space.)44 b(For)27 b(large)h(problems,)h(this)f
(memory)f(requirement)h(becomes)g(prohibitive.)43 2083
y(Many)17 b(limited\255memory)i(variants)e(of)g(heuristic)g(search)g
(have)g(been)h(developed.)31 b(These)17 b(techniques)h(rely)f(on)g
(retraction)43 2208 y(or)28 b(delayed)h(expansion)f(of)g(less)g
(promising)h(nodes)f(to)g(reduce)g(memory)g(requirement.)48
b(In)29 b(the)f(parallel)i(processing)43 2332 y(context,)23
b(retractions)f(lead)i(to)g(additional)h(communication)g(and)e
(indexing)h(for)f(parent\255child)h(relationships)g([9].)43
2732 y Fj(5)116 b(Game)32 b(T)-6 b(ree)32 b(Search)43
3017 y Fk(Min\255max)27 b(techniques)g(such)f(as)h Fi(\013)21
b Fc(\000)f Fi(\014)31 b Fk(game)c(tree)g(search)f(are)g(extensively)h
(used)g(in)g(game\255playing)h(programs.)43 b(In)43 3141
y(this)28 b(algorithm,)j(the)d(minimax)h(value)g(of)f(a)g(node)h(is)f
(determined)h(for)f(a)g(given)h(search)e(window)h Ff([)p
Fi(\013;)14 b(\014)t Ff(])p Fk(.)48 b(This)28 b(window)43
3266 y(serves)19 b(to)h(prune)g(signi\002cant)g(parts)g(of)g(the)g
(tree)g(that)h(do)f(not)g(ef)o(fect)g(the)g(minimax)h(evaluation)h(of)e
(the)g(root.)32 b(Initially)-6 b(,)22 b(this)43 3390
y(window)27 b(is)f(set)g(to)g Ff([)p Fc(\0001)p Fi(;)14
b Fc(1)p Ff(])p Fk(.)41 b(The)26 b(\002rst)e(child)j(of)f(a)g(node)h
(is)f(searched)g(with)g(the)h(same)f(window)g(as)g(the)g(parent.)42
b(The)43 3515 y(window)26 b(of)f(other)h(children)g(is)f(narrowed)g(on)
h(the)f(basis)g(of)h(results)e(from)i(previously)e(visited)i(children.)
39 b(This)25 b(process)43 3639 y(is)f(continued)h(until)g(a)f
(speci\002ed)g(depth)g(is)g(reached,)g(or)g(the)g(branch)g(has)g(no)g
(successors.)32 b(V)-6 b(ariants)24 b(of)h(this)f(algorithm)43
3764 y(are)f(based)g(on)h(iterative)f(deepening,)i(which)f(guides)f
(search)g(based)g(on)g(results)g(from)g(previous)g(iterations.)43
3948 y(Min\255max)31 b(techniques)f(present)g(considerable)h
(challenges)h(for)e(parallel)i(processing.)53 b(Conceptually)-6
b(,)33 b Fi(\013)23 b Fc(\000)f Fi(\014)34 b Fk(game)43
4073 y(tree)20 b(search)f(algorithm)i(can)e(also)h(be)h(viewed)f(as)f
(a)h(depth\255\002rst)f(branch\255and\255bound)h(algorithm)h([23)q(])e
(that)i(searches)d(for)43 4197 y(a)25 b(maximum)g(payof)o(f)f(strategy)
g(among)h(all)h(strategies)f(represented)f(in)h(the)g(game)g(tree.)37
b(However)-5 b(,)25 b(game)g(trees)f(tend)43 4322 y(to)30
b(be)f(strongly)g(ordered.)51 b(Therefore,)31 b(naive)f(parallel)h
(formulations)f(may)f(expand)h(a)f(large)h(number)g(of)f(nodes)h(that)
43 4446 y(are)23 b(not)g(expanded)g(by)g(the)g(serial)g(formulation.)34
b(Second,)24 b(the)f(information)h(about)g(the)f(current)f(best)h
(strategy)f(cannot)43 4571 y(be)27 b(captured)f(by)h(a)f(single)i
(node,)g(as)e(the)h(aim)g(is)g(to)f(\002nd)h(a)f(best)h(winning)h
(strategy)e(rather)g(than)h(a)g(winning)h(position.)43
4695 y(Ef)o(fective)h(propagation)i(of)f(this)g(information)h(to)f
(other)f(processors)f(searching)h(disjoint)i(parts)e(of)h(the)g(search)
f(space)43 4820 y(is)e(much)g(harder)f(compared)h(to)g(sharing)g(of)g
(the)g(cost)f(of)h(current)g(best)f(solution)i(in)f(traditional)i(DFBB)
e(algorithms.)45 b(A)43 4945 y(number)22 b(of)g(researchers)e(have)i
(investigated)h(parallel)g(formulations)g(of)f Fi(\013)16
b Fc(\000)f Fi(\014)26 b Fk([10,)c(34,)g(40].)32 b(The)22
b(problem)h(of)f(excess)43 5069 y(node)f(expansions)g(is)f(handled)i
(by)e(using)h(a)g(prioritized)g(work)f(distribution)i(in)f(which)g(the)
g(tree)g(is)f(expanded)h(left)h(to)f(right)43 5194 y(in)30
b(a)g(sweeping)h(pattern)f(also)g(referred)f(to)h(as)g(the)g(\223Y)-8
b(oung)31 b(Brothers)e(W)m(ait)i(Concept\224.)52 b(Using)30
b(these)g(optimizations)43 5318 y(along)24 b(with)f(dynamic)f(load)i
(balancing,)g(researchers)d(have)h(demonstrated)h(speedups)g(of)f(as)h
(much)f(as)g(two)h(orders)f(of)1970 5610 y(8)p eop
%%Page: 9 9
9 8 bop 43 344 a Fk(magnitude)25 b(on)e(a)g(variety)g(of)g(parallel)i
(platforms.)43 529 y(The)36 b(utility)h(of)f(parallel)i(processing)d
(has)h(been)h(demonstrated)f(in)h(the)f(context)g(of)g(a)g(number)g(of)
h(games,)i(and)d(in)43 653 y(particular)-5 b(,)29 b(Chess.)44
b(W)o(ork)26 b(on)h(large)h(scale)f(parallel)h Fi(\013)22
b Fc(\000)e Fi(\014)31 b Fk(search)26 b(led)i(to)g(the)f(development)h
(of)g(deep)g(thought)g([15])43 778 y(in)37 b(1990.)73
b(This)37 b(program)f(was)g(capable)h(of)g(playing)g(chess)f(at)g
(grandmaster)h(level.)73 b(Subsequent)38 b(advances)d(in)43
903 y(the)30 b(use)f(of)g(dedicated)i(hardware,)g(parallel)f
(processing,)h(and)f(algorithms)g(resulted)f(in)h(the)g(development)g
(of)g(IBM')o(s)43 1027 y(Deep)c(Blue)g([16,)g(14])f(that)h(beat)g(the)g
(reigning)g(world)g(champion)g(Gary)e(Kasparov)-6 b(.)38
b(Feldmann)27 b(et)e(al.)h([40)q(])f(developed)43 1152
y(a)33 b(distributed)g(chess)e(program)i(that)f(is)h(acknowledged)g(to)
f(be)h(one)g(of)f(the)h(best)f(computer)h(chess)e(players)h(based)43
1276 y(entirely)24 b(on)f(general)h(purpose)f(hardware.)43
1675 y Fj(6)116 b(Speedup)31 b(Anomalies)h(in)h(Parallel)f
(Formulations)g(of)g(Search)f(Algorithms)43 1960 y Fk(In)21
b(parallel)i(search)d(algorithms,)j(the)e(speedup)h(can)f(dif)o(fer)g
(greatly)g(from)g(one)h(execution)f(to)h(another)-5 b(.)32
b(This)21 b(is)g(because)43 2085 y(the)32 b(portions)g(of)f(the)h
(search)f(space)g(examined)h(by)g(dif)o(ferent)f(processors)f(are)h
(determined)i(dynamically)f(and)g(can)43 2209 y(be)27
b(dif)o(ferent)g(for)g(dif)o(ferent)g(executions.)44
b(A)27 b(number)g(of)g(researchers)e(have)i(observed)f(and)h(analyzed)g
(the)g(existence)43 2334 y(of)j(these)h(speedup)f(anomalies.)55
b(An)31 b(acceleration)g(anomaly)g(manifests)f(itself)h(in)g(the)f
(form)h(of)f(a)g(speedup)h(greater)43 2458 y(than)e Fi(p)g
Fk(on)g Fi(p)g Fk(processors)e(when)i(parallel)i(search)d(does)g(less)h
(work)f(than)h(the)h(serial)f(search)f(algorithm)i([26)q(,)f(29].)50
b(A)43 2583 y(speedup)18 b(of)f(less)g(than)g Fi(p)p
Fk(,)h(attributed)g(to)g(excess)d(work)h(done)i(by)f(the)g(parallel)i
(formulation)g(compared)e(to)g(the)h(sequential)43 2707
y(formulation,)34 b(is)c(termed)h(as)e(a)i(deceleration)g(anomaly)g
([26)q(,)f(28].)54 b(The)30 b(ratio)h Fi(W)2712 2719
y Fe(p)2751 2707 y Fi(=W)2871 2719 y Fe(s)2906 2707 y
Fk(,)h(where)f Fi(W)3296 2719 y Fe(p)3365 2707 y Fk(and)f
Fi(W)3611 2719 y Fe(s)3677 2707 y Fk(are)h(the)43 2832
y(number)24 b(of)f(nodes)g(searched)g(by)f(parallel)j(and)f(serial)f
(formulations,)h(is)f(called)h(the)g(search)e(overhead)h(factor)-5
b(.)43 3017 y(Speedup)28 b(anomalies)h(can)e(easily)g(occur)f(in)i
(parallel)g(depth\255\002rst)f(search)f(for)h(\002nding)g(any)g
(solution,)j(as)c(certain)i(exe\255)43 3141 y(cution)i(sequences)f(may)
g(\002nd)g(a)h(solution)g(much)f(earlier)h(than)g(others.)51
b(However)-5 b(,)31 b(it)f(appears)f(natural)h(that,)i(on)e(the)43
3266 y(average,)22 b(the)f(search)f(overhead)i(factor)e(for)h(parallel)
i(DFS)e(should)h(always)f(be)g(greater)g(than)h(or)f(equal)h(to)g(one.)
32 b(Other\255)43 3390 y(wise)23 b(the)h(serial)f(search)g(algorithm)h
(is)f(not)h(optimal;)h(i.e.,)f(the)f(emulation)i(of)f(parallel)g(DFS)f
(on)h(a)f(single)h(processor)e(will)43 3515 y(be)k(faster)g(than)h
(sequential)g(DFS.)f(Surprisingly)-6 b(,)28 b(there)e(are)g
(situations,)h(in)g(which)f(parallel)i(DFS)e(can)g(have)g(a)g(search)43
3639 y(overhead)i(factor)f(of)g(less)g(than)h(1)g(on)g(the)f(average,)i
(implying)g(that)f(the)g(serial)f(search)g(algorithm)i(in)f(the)g
(situation)g(is)43 3764 y(suboptimal.)43 b(Kumar)27 b(and)g(Rao)f([43])
h(show)f(that)g(if)h(no)g(heuristic)f(information)i(is)e(available)i
(to)e(order)g(the)h(successors)43 3888 y(of)i(a)f(node,)j(then)d(on)h
(the)g(average,)h(the)e(speedup)h(obtained)h(by)e(parallel)i(DFS)e(is)g
(superlinear)h(if)g(the)g(distribution)h(of)43 4013 y(solutions)d(is)g
(non\255uniform.)43 b(This)27 b(model)g(is)g(validated)h(by)e
(experiments)g(on)h(synthetic)f(state\255space)g(trees)g(modeling)43
4137 y(the)j(hackers)e(problem,)k(the)e(15\255puzzle)f(problem)i(and)f
(the)g Fi(n)p Fk(\255Queens)e(problem.)50 b(In)29 b(all)g(these)g
(experiments,)h(serial)43 4262 y(and)i(parallel)h(DFS)e(do)g(not)h(use)
f(any)g(heuristic)h(ordering,)i(and)d(select)g(successors)e
(arbitrarily)-6 b(.)57 b(The)31 b(basic)g(reason)43 4386
y(for)23 b(this)h(phenomenon)h(is)e(that)h(parallel)h(search)e(can)g
(invest)g(resources)f(into)j(multiple)g(regions)f(of)f(the)h(search)f
(frontier)43 4511 y(concurrently)-6 b(.)35 b(When)26
b(the)e(solution)i(density)e(in)h(dif)o(ferent)g(regions)g(of)f(the)h
(search)f(frontier)g(is)h(non\255uniform)g(and)g(these)43
4635 y(non\255uniformities)32 b(are)f(not)g(known)g(a)g(priori,)i(then)
f(sequential)g(search)e(has)g(an)i(equal)f(chance)g(of)g(searching)g(a)
g(low)43 4760 y(density)19 b(region)h(\(and)f(thus)g(be)h(forced)f(to)g
(expand)h(many)f(nodes\))g(or)g(a)g(high)h(density)f(region.)32
b(On)19 b(the)h(contrary)-6 b(,)18 b(parallel)43 4885
y(search)25 b(can)h(search)f(all)h(regions)g(at)g(the)h(same)f(time,)h
(ensuring)f(that)g(at)g(least)h(some)e(processors)f(are)i(searching)g
(the)43 5009 y(high)e(density)f(regions.)43 5194 y(If)k(good)g
(heuristics)f(are)g(available)i(to)f(order)f(the)g(successors)e(of)j
(nodes)f(in)h(DFS,)g(then)g(the)f(search)g(overhead)g(factor)43
5318 y(of)k(parallel)h(DFS)f(may)g(be)g(greater)g(than)g(one.)53
b(The)30 b(reason)g(is)f(that)i(some)f(processors)d(may)j(search)f
(unpromising)1970 5610 y(9)p eop
%%Page: 10 10
10 9 bop 43 344 a Fk(areas)25 b(of)g(the)h(search)e(space.)38
b(This)25 b(phenomenon)i(is)e(most)g(visible)h(in)g(the)f(context)g(of)
g Fi(\013)20 b Fc(\000)g Fi(\014)29 b Fk(search)24 b(of)i(game)f(trees)
43 469 y(for)f(which)h(strong)e(ordering)i(heuristics)f(are)g
(available.)38 b(Kale)25 b(and)g(Saletore)g([19])g(present)f(a)g
(scheme)g(that)h(combines)43 593 y(the)h(information)h(about)f(the)g
(ordering)h(and)f(depth)g(of)g(nodes)f(to)h(perform)g(load)g(balancing)
h(among)f(processors.)38 b(This)43 718 y(scheme)15 b(largely)g
(maintains)h(the)f(depth\255\002rst)f(heuristic)h(order)f(of)i(search)d
(across)h(processors,)g(and)i(results)e(in)h(consistent)43
842 y(linear)32 b(speedup.)55 b(Even)31 b(in)g(the)g(presence)f(of)h
(good)g(ordering)h(heuristics,)g(parallel)g(DFS)f(may)f(lead)i(to)e
(superlinear)43 967 y(speedup.)i(For)21 b(example,)h(this)f(can)f
(happen)i(if)f(there)g(is)g(a)g(non\255zero)g(probability)h(that)f(the)
g(heuristic)g(can)g(guide)h(search)43 1092 y(to)h(large)h(regions)f
(that)h(do)f(not)h(contain)f(any)g(solutions)h([43].)43
1276 y(In)k(parallel)h(BFS,)g(the)f(search)f(overhead)g(can)h(be)g
(greater)g(than)g(one)g(if)h(some)e(processors)f(expand)i(nodes)g(that)
g(are)43 1401 y(never)f(expanded)h(by)f(serial)h(BFS)g(\(e.g.,)g(nodes)
g(that)g(have)f(higher)h(bound)g(than)g(the)g(cost)f(of)g(the)h
(optimal)h(solution\).)43 1525 y(In)j(fact,)h(it)f(can)f(be)h(shown)f
(that)h(for)f(any)h(given)g(BFS)f(instance,)j(there)e(exists)e(a)i
(constant)f Fi(k)j Fk(such)d(that)h(expanding)43 1650
y(more)25 b(than)g Fi(k)j Fk(nodes)d(in)g(parallel)h(from)f(a)g(global)
h(open)g(list)f(leads)g(to)g(wasted)g(computation)h([26].)38
b(This)24 b(situation)i(gets)43 1774 y(worse)j(with)i(distributed)g
(open)f(lists)g(since)g(expanded)g(nodes)h(have)e(locally)i(minimum)h
(heuristics)d(that)h(are)g(not)h(the)43 1899 y(best)23
b(nodes)g(across)f(all)i(open)g(lists.)43 2083 y(The)29
b(search)f(overhead)g(for)h(parallel)h(BFS)g(can)e(also)h(be)g(less)f
(than)i(one.)49 b(This)29 b(can)f(happen)i(when)f(multiple)i(nodes)43
2208 y(on)c(the)g(open)g(list)h(have)e(identical)i(heuristic)f(values,)
h(but)f(require)g(dif)o(ferent)g(amount)h(of)f(search)e(to)i(detect)g
(a)g(solution)43 2332 y(\(or)h(to)h(\002nd)g(out)g(that)g(the)g(node)h
(does)e(not)i(lead)f(to)g(optimal)i(solution\).)50 b(Hence,)30
b(if)f(a)g(parallel)h(algorithm)h(happens)e(to)43 2457
y(explore)h(the)h(better)g(nodes)f(\002rst,)h(then)g(it)f(can)g(result)
h(in)f(acceleration)h(anomalies,)j(and)c(vice)g(versa.)53
b(It)30 b(is)h(possible)43 2581 y(to)39 b(derive)g(properties)f(of)h
(the)g(heuristic)g(function)g(such)f(that)h(superlinearity)h(ef)o
(fects)d(in)j(parallel)g(BFS)f(are)f(made)43 2706 y(deterministic)24
b([29,)g(32].)43 3105 y Fj(7)116 b(Role)32 b(of)g(Heuristics)43
3390 y Fk(Heuristics)e(form)g(the)h(most)g(important)g(component)g(of)g
(search)f(techniques,)j(and)e(parallel)h(formulations)f(of)g(search)43
3515 y(algorithms)22 b(must)f(be)h(viewed)g(in)g(the)f(context)g(of)h
(these)f(heuristics.)32 b(In)21 b(BFS)h(techniques,)g(heuristics)f
(focus)g(search)f(by)43 3639 y(lowering)j(the)f(ef)o(fective)g
(branching)g(factor)-5 b(.)32 b(In)22 b(DFBB)g(methods,)h(heuristics)e
(provide)h(better)h(bounds,)f(and)g(thus)g(serve)43 3764
y(to)h(prune)h(the)f(search)f(space.)43 3948 y(Often,)f(there)g(is)g(a)
f(tradeof)o(f)h(between)g(the)g(strength)g(of)g(the)g(heuristic)f(and)h
(the)g(ef)o(fective)g(size)f(of)h(search)e(space.)32
b(Better)43 4073 y(heuristics)21 b(result)g(in)h(smaller)g(search)f
(spaces)f(but)i(are)f(also)h(more)f(expensive)g(to)h(compute.)32
b(For)21 b(example,)h(an)g(impor\255)43 4197 y(tant)27
b(application)h(of)e(strong)g(heuristics)g(is)g(in)h(the)g(computation)
g(of)g(bounds)f(for)g(mixed)h(integer)g(programming)g(\(MIP\).)43
4322 y(Mixed)36 b(integer)g(programming)h(has)e(seen)g(signi\002cant)h
(advances)f(over)g(the)g(years)g([18].)70 b(Whereas)35
b(\002fteen)h(years)43 4446 y(back,)c(MIP)f(problems)f(with)h(100)g
(integer)g(variables)g(were)f(considered)g(challenging,)k(today)-6
b(,)32 b(many)f(problems)f(with)43 4571 y(up)25 b(to)g(1000)h(integer)f
(variables)g(can)g(be)g(solved)g(on)g(workstation)f(class)g(machines)h
(using)g(branch\255and\255cut)g(methods.)43 4695 y(Largest)35
b(known)h(instances)f(of)h(TSPs)g(and)g(QAPs)f(have)h(been)g(solved)f
(using)h(branch\255and\255bound)g(with)g(powerful)43
4820 y(heuristics)e([3,)h(35].)66 b(The)34 b(presence)g(of)h(ef)o
(fective)f(heuristics)g(may)g(prune)h(the)f(search)g(space)g
(considerably)-6 b(.)66 b(For)43 4945 y(example,)24 b(when)f(Padberg)h
(and)f(Rinaldi)h(introduced)g(the)f(branch\255and\255cut)f(algorithm)i
(in)g(1987,)f(they)g(used)g(it)g(to)g(solve)43 5069 y(a)i(532)g(city)e
(TSP)-11 b(,)26 b(which)e(was)g(the)h(largest)g(TSP)g(solved)f
(optimally)i(at)f(that)g(time.)37 b(Subsequent)25 b(improvements)g(to)g
(the)43 5194 y(method)d(led)g(to)f(the)g(solution)i(of)e(a)g(a)g(2,392)
h(city)f(problem)g([36)q(].)32 b(More)21 b(recently)-6
b(,)21 b(using)g(cutting)h(planes,)g(problems)f(with)43
5318 y(over)f(7,000)h(cities)g(have)f(been)i(solved)e([18)q(])g(on)h
(serial)g(machines.)32 b(However)-5 b(,)21 b(for)f(many)h(problems)g
(of)f(interest,)i(the)f(re\255)1947 5610 y(10)p eop
%%Page: 11 11
11 10 bop 43 344 a Fk(duced)21 b(search)f(space)g(still)i(requires)f
(the)g(use)g(of)g(parallelism)i([3,)e(35,)g(44,)g(31)q(].)31
b(Use)21 b(of)g(powerful)h(heuristics)e(combined)43 469
y(with)26 b(ef)o(fective)f(parallel)i(processing)d(has)h(enabled)i(the)
f(solution)g(of)g(extremely)f(large)g(problems)h([35].)39
b(For)25 b(example,)43 593 y(QAP)k(problems)f(from)h(the)f(Nugent)h
(and)g(Eschermann)g(test)f(suites)g(with)h(up)f(to)h(4)p
Fi(:)p Fk(8)22 b Fc(\002)f Fk(10)3028 563 y Fh(10)3125
593 y Fk(nodes)28 b(\(Nugent22)h(with)43 718 y(Gilmore\255Lawler)f
(bound\))g(were)f(solved)g(on)g(a)h(NEC)f(Cenju\2553)h(parallel)h
(computer)e(in)h(under)g(nine)g(days)e([3].)45 b(Another)43
842 y(dazzling)31 b(demonstration)h(of)f(this)g(was)g(presented)g(by)f
(the)h(IBM)h(Deep)f(Blue.)57 b(Deep)31 b(blue)h(used)e(a)h(combination)
i(of)43 967 y(dedicated)h(hardware)e(for)h(generating)h(and)f
(evaluating)h(board)f(positions)g(and)h(parallel)g(search)e(of)h(the)g
(game)g(tree)43 1092 y(using)24 b(an)f(IBM)h(SP2)g(to)f(beat)h(the)f
(current)g(world)g(chess)f(champion,)i(Garry)e(Kasparov)g([16)q(,)h
(14].)43 1276 y(Heuristics)g(have)h(several)g(important)g(implications)
i(for)e(exploiting)h(parallelism.)36 b(Strong)25 b(heuristics)e(narrow)
h(the)g(state)43 1401 y(space)18 b(and)h(thus)g(reduce)f(the)h
(concurrency)e(available)j(in)f(the)g(search)f(space.)31
b(Use)18 b(of)h(powerful)g(heuristics)f(pose)h(other)43
1525 y(computational)30 b(challenges)f(for)e(parallel)j(processing)d
(as)h(well.)48 b(For)27 b(example,)j(in)e(branch\255and\255cut)g
(methods,)h(a)f(cut)43 1650 y(generated)e(at)g(a)g(certain)f(state)h
(may)f(be)h(required)g(by)f(other)h(states.)39 b(Therefore,)26
b(in)g(addition)h(to)f(balancing)h(load,)g(the)43 1774
y(parallel)g(branch\255and\255cut)e(formulation)i(must)e(also)h
(partition)h(cuts)e(among)h(processors)d(so)j(that)g(processors)d
(working)43 1899 y(in)h(certain)f(LP)h(domains)f(have)g(access)f(to)h
(the)h(desired)f(cuts)f([2)q(,)h(27,)g(8].)43 2083 y(In)35
b(addition)h(to)f(inter\255node)g(parallelism)h(that)f(has)f(been)h
(discussed)f(until)i(this)e(point,)39 b(intra\255node)c(parallelism)h
(can)43 2208 y(become)21 b(a)h(viable)g(option)g(if)f(the)h(heuristic)f
(is)g(computationally)i(expensive.)31 b(For)21 b(example,)h(the)f
(assignment)h(heuristic)43 2332 y(of)27 b(Pekny)g(et)h(al.)45
b(has)27 b(been)h(ef)o(fectively)f(parallelized)i(for)e(solving)g
(large)h(instances)f(of)g(TSPs)g([35)q(].)44 b(If)28
b(the)f(degree)h(of)43 2457 y(inter\255node)h(parallelism)h(is)d
(small,)j(this)f(form)f(of)g(parallelism)i(provides)d(a)i(desirable)f
(alternative.)49 b(Another)28 b(example)43 2581 y(of)e(this)h(is)f(in)g
(the)h(solution)g(of)g(MIP)f(problems)h(using)f(branch\255and\255cut)g
(methods.)42 b(Branch\255and\255cut)25 b(methods)i(rely)f(on)43
2706 y(LP)f(relaxation)h(for)f(generating)h(lower)f(bounds)g(of)g
(partially)h(instantiated)g(solutions)g(followed)g(by)e(generation)i
(of)f(valid)43 2830 y(inequalities)33 b([18].)55 b(These)30
b(LP)h(relaxations)f(constitute)h(a)g(major)g(part)f(of)h(the)g
(overall)g(computation)g(time.)55 b(Many)31 b(of)43 2955
y(the)25 b(industrial)i(codes)d(rely)h(on)g(Simplex)i(to)e(solve)g(the)
g(LP)h(problem)g(since)f(it)g(can)g(adapt)h(the)f(solution)i(to)e
(added)h(rows)43 3080 y(and)e(columns.)35 b(While)26
b(interior)f(point)f(methods)h(are)f(better)g(suited)g(to)g
(parallelism,)i(they)e(tend)h(to)f(be)g(less)g(ef)o(\002cient)f(for)43
3204 y(reoptimizing)k(LP)f(solutions)g(with)f(added)i(rows)d(and)i
(columns)f(\(in)h(branch\255and\255cut)e(methods\).)40
b(LP)25 b(relaxation)i(using)43 3329 y(Simplex)j(has)e(been)i(shown)e
(to)h(parallelize)i(well)e(on)g(small)h(numbers)e(of)h(processors)e
(but)i(ef)o(forts)f(to)g(scale)h(to)g(larger)43 3453
y(numbers)e(of)h(processors)d(have)i(not)h(been)f(successful.)44
b(LP)27 b(based)h(branch)f(and)g(bound)h(methods)g(have)f(also)g(been)
43 3578 y(used)g(for)f(solving)h(quadratic)g(assignment)g(problems)g
(using)g(iterative)h(solvers)d(such)h(as)g(preconditioned)j(Conjugate)
43 3702 y(Gradient)37 b(to)h(approximately)f(compute)h(the)f(interior)h
(point)g(directions)f([37].)74 b(These)37 b(methods)g(have)g(been)h
(used)43 3827 y(to)30 b(compute)f(lower)h(bounds)g(using)g(linear)g
(programs)f(with)h(over)f(150,000)h(constraints)f(and)h(300,000)h
(variables)e(for)43 3951 y(solving)20 b(QAPs.)32 b(These)19
b(and)i(other)f(iterative)h(solvers)e(parallelize)j(very)c(ef)o
(fectively)i(to)g(a)h(large)f(number)h(of)f(processors.)43
4076 y(A)25 b(general)g(parallel)g(framework)f(for)g(computing)h
(heuristic)f(solutions)h(to)f(problems)h(is)f(presented)g(by)g
(Pramanick)h(and)43 4200 y(Kuhl)f([39)q(].)43 4600 y
Fj(8)116 b(Concluding)32 b(Remarks)43 4885 y Fk(Great)e(advances)g
(have)h(been)h(made)f(in)g(the)g(development)h(of)f(scalable)g
(parallel)i(formulations)f(of)f(various)f(search)43 5009
y(methods)h(in)h(the)f(past)g(two)g(decades.)56 b(Performance)31
b(and)g(scalability)h(of)f(load)h(balancing)g(techniques)g(for)e
(parallel)43 5134 y(depth\255\002rst)36 b(search)g(methods)i(is)f
(largely)g(understood,)k(and)d(it)g(is)f(unlikely)g(that)h(any)f(new)g
(methods)h(will)g(perform)43 5258 y(signi\002cantly)32
b(better)g(than)g(the)g(existing)g(methods.)59 b(Parallel)34
b(best\255\002rst)c(search)g(methods)j(require)f(qualitative)h(load)
1947 5610 y(11)p eop
%%Page: 12 12
12 11 bop 43 344 a Fk(balancing)39 b(in)g(addition)h(to)e(quantitative)
h(load)g(balancing)g(used)f(in)h(depth\255\002rst)e(search,)k(and)d
(are)g(thus)g(harder)g(to)43 469 y(analyze.)h(However)-5
b(,)25 b(many)g(methods)h(for)f(qualitative)i(load)f(balancing)g(have)f
(been)h(developed)g(and)g(shown)f(to)g(have)43 593 y(provably)h(good)i
(performance)e(under)h(a)g(reasonable)g(set)g(of)f(assumptions.)43
b(For)27 b(a)f(wide)i(variety)e(of)h(problems,)g(both)43
718 y(best\255\002rst)33 b(and)i(depth\255\002rst)e(search)h(methods)h
(have)f(shown)h(excellent)g(performance)g(and)g(scalability)g(up)g(to)f
(1024)43 842 y(processors)22 b([45)q(,)i(25)q(,)g(1,)h(40,)f(30)q(,)g
(44)q(].)36 b(Attention)26 b(has)e(now)h(shifted)g(to)g(the)f
(development)i(of)f(software)f(environments)43 967 y(that)g(allow)g
(practitioners)f(to)g(solve)g(real)h(problems)f(on)h(parallel)g
(machines)g([4].)43 1152 y(It)33 b(is)g(important)h(to)f(note)g(that)h
(parallel)g(processing)f(can)f(only)h(provide)h(speed)f(up)g
(proportional)h(to)f(the)g(number)h(of)43 1276 y(processors.)g(Hence,)
24 b(parallel)i(search)d(can)h(be)h(used)f(to)h(solve)f
(signi\002cantly)g(bigger)h(instances)f(of)g(the)h(problem)g(only)43
1401 y(if)i(the)g(search)f(space)g(grows)g(as)h(a)g(small)g(exponent)g
(of)g(problem)h(size.)42 b(Hence,)28 b(challenges)g(remain)f(in)g
(discovering)43 1525 y(better)c(heuristics)g(that)h(reduce)f(the)g
(growth)g(of)h(the)f(search)g(space.)32 b(Indeed,)24
b(for)f(many)g(problems,)g(gains)h(due)f(to)h(new)43
1650 y(powerful)31 b(heuristics)e(may)g(be)i(much)e(higher)i(than)f
(those)g(due)g(to)g(massively)f(parallel)j(formulations)e(using)h
(existing)43 1774 y(heuristics.)h(These)23 b(powerful)h(heuristics)e
(may)h(also)h(of)o(fer)e(new)i(opportunities)g(for)f(exploiting)i
(parallelism.)43 2154 y Fj(References)85 2371 y Fn([1])40
b(S.)19 b(Arvindam,)f(V)o(ipin)f(Kumar)l(,)h(and)g(V)-7
b(.)18 b(Nageshwara)f(Rao.)25 b(Floorplan)16 b(optimization)f(on)k
(multiprocessors.)24 b(In)18 b Fb(Proceedings)f(of)209
2486 y(the)j(1989)f(International)d(Conference)i(on)i(Computer)e
(Design)p Fn(,)h(1989.)85 2625 y([2])40 b(R.)17 b(E.)h(Bixby)-6
b(,)18 b(W)l(.)f(Cook,)g(A.)g(Cox,)h(and)e(E.)h(Lee.)22
b(Parallel)15 b(mixed)i(integer)e(programming.)20 b(T)-8
b(echnical)15 b(Report)h(CRPC)h(TR)h(95554,)209 2739
y(Center)h(for)h(Research)g(on)g(Parallel)d(Computation,)h(Research)h
(Monograph,)f(1995.)85 2878 y([3])40 b(Adrian)20 b(Brungger)l(,)f
(Ambros)i(Marzetta,)g(Jens)h(Clausen,)e(and)g(Michael)h(Perregaard.)28
b(Solving)20 b(large\255scale)f(qap)i(problems)f(in)209
2992 y(parallel)e(with)h(the)h(search)g(library)f(zram.)29
b Fb(Journal)19 b(of)h(Parallel)e(and)h(Distributed)f(Computing)p
Fn(,)g(50:157\226169,)e(1998.)85 3131 y([4])40 b(B.)57
b(L.)g(Cun)f(and)g(C.)i(Roucairol.)123 b(BOB:)57 b(A)g(uni\002ed)f
(platform)f(for)i(implementing)d(branch\255and\255bound)e(like)k
(al\255)209 3246 y(gorithms.)132 b(T)-8 b(echnical)58
b(Report)g(N95/16,)68 b(Universiti)58 b(de)h(V)l(ersailles)f(Saint)h
(Quentin,)67 b(1995.)132 b(A)o(vailable)57 b(from)209
3360 y Fa(http://www.prism.uvsq.fr/english/paralle)o(l/cr/b)o(ob)p
2371 3360 23 4 v 21 w(us.html)p Fn(.)85 3499 y([5])40
b(E.)29 b(W)l(.)f(Dijkstra,)i(W)l(.)e(H.)g(Seijen,)h(and)e(A.)i(J.)g
(M.)g(V)-6 b(an)28 b(Gasteren.)49 b(Derivation)26 b(of)i(a)h
(termination)c(detection)h(algorithm)g(for)i(a)209 3613
y(distributed)18 b(computation.)25 b Fb(Information)18
b(Processing)h(Letters)p Fn(,)g(16\2555:217\226219,)d(1983.)85
3752 y([6])40 b(S.)28 b(Dutt)f(and)f(N.)i(R.)f(Mahapatra.)45
b(Scalable)25 b(load\255balancing)e(strategies)j(for)h(parallel)d(a*)k
(algorithms.)45 b Fb(Journal)26 b(of)h(Parallel)209 3866
y(and)f(Distributed)e(Computing)p Fn(,)h(22\(3\):488\226505,)e(Sept.)i
(1994.)43 b(Special)25 b(Issue)i(on)e(Scalability)g(of)h(Parallel)e
(Algorithms)g(and)209 3981 y(Architectures.)85 4120 y([7])40
b(Jonathan)13 b(Eckstein.)19 b(Parallel)13 b(branch\255and\255bound)d
(methods)k(for)h(mixed\255integer)d(programming)h(on)h(the)h(cm\2555.)
20 b Fb(SIAM)15 b(Journal)209 4234 y(on)20 b(Optimization)p
Fn(,)e(4\(4\):794\226814,)e(1994.)85 4373 y([8])40 b(Jonathan)14
b(Eckstein.)22 b(Distributed)13 b(versus)k(centralized)d(storage)h(and)
g(control)g(for)h(parallel)e(branch)h(and)g(bound:)25
b(Mixed)16 b(integer)209 4487 y(programming)i(on)i(the)g(cm\2555.)28
b Fb(Computational)17 b(Optimization)h(and)h(Applications)p
Fn(,)f(7\(2\):199\226220,)e(1997.)85 4626 y([9])40 b(M.)22
b(Evett,)f(James)h(Hendler)l(,)d(Ambujashka)h(Mahanti,)g(and)g(Dana)g
(Nau.)31 b(PRA*:)f(A)22 b(memory\255limited)d(heuristic)h(search)h
(proce\255)209 4741 y(dure)i(for)h(the)f(connection)e(machine.)37
b(In)24 b Fb(Proceedings)d(of)j(the)f(Third)g(Symposium)g(on)h(the)f
(Frontiers)f(of)i(Massively)g(Parallel)209 4855 y(Computation)p
Fn(,)17 b(pages)j(145\226149,)d(1990.)43 4994 y([10])40
b(Chris)17 b(Ferguson)e(and)h(Richard)g(Korf.)22 b(Distributed)15
b(tree)h(search)h(and)f(its)h(application)d(to)j(alpha\255beta)d
(pruning.)20 b(In)d Fb(Proceedings)209 5108 y(of)j(the)g(1988)f
(National)f(Conference)g(on)i(Arti\002cial)f(Intelligence)p
Fn(,)d(August)k(1988.)43 5247 y([11])40 b(A.)33 b(Ferreira)d(and)i(P)
-10 b(.)33 b(Pardalos,)g(editors.)59 b Fb(Solving)31
b(Combinatorial)e(Optimization)h(Problems)i(in)g(Parallel:)50
b(Methods)31 b(and)209 5361 y(T)-7 b(echniques)p Fn(,)18
b(volume)i(1054)f(of)h Fb(LNCS)g(State\255of\255the\255Art)c(Surveys)p
Fn(.)29 b(Springer\255V)l(erlag,)16 b(1996.)1947 5610
y Fk(12)p eop
%%Page: 13 13
13 12 bop 43 344 a Fn([12])40 b(Raphael)27 b(A.)i(Finkel)e(and)h(Udi)g
(Manber)l(.)50 b(DIB)29 b(\255)g(a)g(distributed)d(implementation)f(of)
j(backtracking.)50 b Fb(ACM)29 b(T)-6 b(ransactions)28
b(of)209 459 y(Programming)18 b(Languages)g(and)h(Systems)p
Fn(,)i(9)g(No.)f(2:235\226256,)c(April)j(1987.)43 606
y([13])40 b(M.)30 b(Furuichi,)f(K.)h(T)-8 b(aki,)31 b(and)d(N.)h
(Ichiyoshi.)52 b(A)29 b(multi\255level)e(load)h(balancing)f(scheme)i
(for)g(OR\255parallel)e(exhaustive)h(search)209 720 y(programs)20
b(on)g(the)h(Multi\255PSI.)28 b(In)20 b Fb(Proceedings)f(of)i(the)f
(Second)g(ACM)h(SIGPLAN)f(Symposium)h(on)f(Principles)f(and)h(Practice)
209 834 y(of)g(Parallel)e(Programming)p Fn(,)g(pages)h(50\22659,)g
(1990.)43 982 y([14])40 b(Scott)19 b(Hamilton)d(and)i(Lee)g(Garber)l(.)
24 b(Deep)18 b(Blue')o(s)f(hardware\255software)e(synergy)-6
b(.)26 b Fb(IEEE)18 b(Computer)p Fn(,)g(30\(10\):29\22635,)c(October)
209 1096 y(1997.)43 1243 y([15])40 b(F)-8 b(.\255H.)21
b(Hsu.)33 b(Large)20 b(scale)i(parallelization)17 b(of)22
b(alpha\255beta)c(search:)31 b(An)22 b(algorithmic)d(and)i
(architectural)f(study)h(with)h(computer)209 1357 y(chess.)29
b(T)-8 b(echnical)18 b(report,)h(Carnegie)f(Mellon)h(University)-6
b(,)20 b(Pittsburgh,)e(P)-6 b(A,)20 b(1990.)27 b(Ph.D.)20
b(Thesis.)43 1505 y([16])40 b(F)-8 b(.\255H.)19 b(Hsu,)h(M.)f(S.)h
(Campbell,)d(and)i(A.)h(J.)g(Hoane.)25 b(Deep)19 b(Blue)f(system)j
(overview)l(.)26 b(In)19 b Fb(Conference)e(proceedings)g(of)i(the)g
(1995)209 1619 y(International)d(Conference)i(on)i(Supercomputing,)d
(Barcelona,)h(Spain)p Fn(,)g(pages)h(240\226244,)f(1995.)43
1766 y([17])40 b(V)o(irendra)24 b(K.)i(Janakiram,)h(Dharma)e(P)-10
b(.)27 b(Agrawal,)f(and)f(Ram)i(Mehrotra.)43 b(A)26 b(randomized)e
(parallel)g(backtracking)h(algorithm.)209 1880 y Fb(IEEE)20
b(T)-6 b(ransactions)19 b(on)h(Computers)p Fn(,)f(C\25537)h(\(12\),)f
(1988.)43 2028 y([18])40 b(L.)28 b(Johnson,)h(G.)g(Nemhauser)l(,)f(and)
g(M.)g(Savelsbergh.)48 b(Progress)27 b(in)h(integer)e(programming:)42
b(An)28 b(exposition.)48 b(T)-8 b(echnical)209 2142 y(report,)35
b(School)c(of)i(Industrial)e(and)h(Systems)i(Engineering,)e(Georgia)f
(Institute)g(of)h(T)-8 b(echnology)i(,)34 b(1997.)60
b(A)o(vailable)31 b(from)209 2256 y Fa(http://akula.isye.gatech.edu/)40
b(mwps/mwps.html)p Fn(.)43 2403 y([19])g(L.)19 b(V)-7
b(.)20 b(Kale)e(and)g(V)-7 b(.)20 b(Saletore.)k(Parallel)17
b(state\255space)h(search)h(for)g(a)g(\002rst)h(solution)d(with)i
(consistent)f(linear)g(speedups.)25 b Fb(Interna\255)209
2517 y(tional)19 b(Journal)f(of)i(Parallel)e(Programming)p
Fn(,)g(3,)i(August)g(1990.)43 2665 y([20])40 b(L.)20
b(N.)h(Kanal)e(and)g(V)o(ipin)g(Kumar)l(.)27 b Fb(Search)20
b(in)g(Arti\002cial)f(Intelligence)p Fn(.)25 b(Springer\255V)l(erlag,)
15 b(New)20 b(Y)-7 b(ork,)21 b(NY)-10 b(,)20 b(1988.)43
2812 y([21])40 b(R.)21 b(Karp)f(and)g(Y)-10 b(.)21 b(Zhang.)28
b(Randomized)18 b(parallel)g(algorithms)h(for)h(backtrack)h(search)g
(and)f(branch\255and\255bound)15 b(computation.)209 2926
y Fb(Journal)k(of)h(ACM)p Fn(,)h(40:765\226789,)16 b(1993.)43
3074 y([22])40 b(George)20 b(Karypis)g(and)g(V)o(ipin)e(Kumar)l(.)29
b(Unstructured)19 b(T)m(ree)h(Search)g(on)g(SIMD)h(Parallel)d
(Computers.)28 b Fb(IEEE)21 b(T)-6 b(ransactions)19 b(on)209
3188 y(Parallel)f(and)h(Distributed)f(Systems)p Fn(,)j(5\(10\),)e
(October)h(1994.)43 3335 y([23])40 b(V)-7 b(.)24 b(Kumar)f(and)g(L.)g
(N.)h(Kanal.)36 b(A)24 b(general)d(branch\255and\255bound)e
(formulations)i(for)j(understanding)19 b(and)k(synthesizing)f(and/or)
209 3449 y(tree)e(search)g(procedures.)26 b Fb(Arti\002cial)20
b(Intelligence)p Fn(,)c(21:179\226198,)g(1983.)43 3597
y([24])40 b(V)o(ipin)23 b(Kumar)l(,)h(Ananth)e(Grama,)j(Anshul)e
(Gupta,)h(and)g(George)e(Karypis.)39 b Fb(Introduction)21
b(to)j(Parallel)e(Computing:)33 b(Algorithm)209 3711
y(Design)19 b(and)h(Analysis)p Fn(.)28 b(Benjamin)18
b(Cummings/)i(Addison)e(W)o(esley)i(\(ISBN)g(0\2558053\2553170\2550\),)
15 b(Redwod)k(City)-6 b(,)21 b(1994.)43 3858 y([25])40
b(V)o(ipin)17 b(Kumar)l(,)h(Ananth)f(Grama,)h(and)g(V)-7
b(.)19 b(Nageshwara)d(Rao.)25 b(Scalable)17 b(load)g(balancing)f
(techniques)g(for)j(parallel)c(computers.)209 3972 y
Fb(Journal)k(of)h(Parallel)e(and)h(Distributed)f(Computing)p
Fn(,)g(22\(1\):60\22679,)e(July)21 b(1994.)43 4120 y([26])40
b(T)-8 b(.)27 b(H.)h(Lai)e(and)h(Sartaj)f(Sahni.)46 b(Anomalies)25
b(in)i(parallel)e(branch)i(and)f(bound)g(algorithms.)45
b Fb(Communications)25 b(of)i(the)g(ACM)p Fn(,)209 4234
y(pages)19 b(594\226602,)f(1984.)43 4381 y([27])40 b(Eva)19
b(K.)h(Lee)e(and)g(John)h(E.)g(Mitchell.)25 b(Computational)15
b(experience)i(of)i(an)f(interior\255point)d(algorithm)i(in)i(a)g
(parallel)d(branch\255and\255)209 4495 y(cut)21 b(framework.)27
b(In)20 b Fb(Proceedings)e(for)i(SIAM)h(Conference)d(on)i(Parallel)d
(Processing)j(for)g(Scienti\002c)f(Computing)p Fn(,)f(1997.)43
4643 y([28])40 b(G.)28 b(J.)g(Li)f(and)g(B.)g(W)l(.)h(W)m(ah.)46
b(Computational)24 b(ef)o(\002ciency)j(of)g(combinatorial)e(or\255tree)
h(searches.)47 b Fb(IEEE)27 b(T)-6 b(rans.)27 b(on)g(Software)209
4757 y(Engineering)p Fn(,)16 b(16\(1\):13\22631,)h(Jan.)j(1990.)43
4904 y([29])40 b(Guo\255Jie)22 b(Li)h(and)f(Benjamin)f(W)l(.)h(W)m(ah.)
35 b(Coping)21 b(with)i(anomalies)e(in)h(parallel)e
(branch\255and\255bound)e(algorithms.)34 b Fb(IEEE)23
b(T)-6 b(rans\255)209 5019 y(actions)20 b(on)g(Computers)p
Fn(,)e(C\22635,)i(June)f(1986.)43 5166 y([30])40 b(N.)18
b(R.)f(Mahapatra)e(and)i(S.)h(Dutt.)k(Scalable)16 b(global)f(and)i
(local)f(hashing)g(strategies)g(for)h(duplicate)e(pruning)g(in)i
(parallel)d(a*)k(graph)209 5280 y(search.)28 b Fb(IEEE)20
b(T)-6 b(rans.)20 b(Parallel)e(and)i(Distributed)d(Systems)p
Fn(,)k(8\(7\),)f(July)g(1997.)1947 5610 y Fk(13)p eop
%%Page: 14 14
14 13 bop 43 344 a Fn([31])40 b(B.)19 b(Mans,)g(T)-8
b(.)18 b(Mautor)l(,)g(and)g(C.)h(Roucairol.)k(A)c(parallel)d(depth)i
(\002rst)h(search)g(branch)e(and)h(bound)f(for)h(the)g(quadratic)f
(assignment)209 459 y(problem.)27 b Fb(European)18 b(Journal)g(of)i
(Operational)d(Research)p Fn(,)j(81\(3\):617\226628,)15
b(1995.)43 606 y([32])40 b(B.)21 b(Mans)g(and)e(C.)i(Roucairol.)27
b(Performances)19 b(of)h(parallel)e(branch)i(and)f(bound)g(algorithms)g
(with)h(best\255\002rst)g(search.)29 b Fb(Discrete)209
720 y(Applied)18 b(Mathematics)p Fn(,)h(66\(1\):57\22676,)e(April)i
(1996.)43 867 y([33])40 b(G.)19 b(Manzini)f(and)g(M.)h(Somalvico.)25
b(Probabilistic)16 b(performance)h(analysis)h(of)h(heuristic)e(search)i
(using)f(parallel)e(hash)i(tables.)25 b(In)209 982 y
Fb(Proceedings)18 b(of)i(the)g(International)c(Symposium)k(on)g
(Arti\002cial)f(Intelligence)e(and)i(Mathematics)p Fn(,)g(1990.)43
1129 y([34])40 b(T)-8 b(.)16 b(A.)g(Marsland)f(and)g(M.)h(Campbell.)j
(Parallel)14 b(search)h(of)h(strongly)f(ordered)f(game)h(trees.)21
b Fb(Computing)14 b(Surveys)p Fn(,)j(14:533\226551,)209
1243 y(1982.)43 1390 y([35])40 b(D.)24 b(L.)g(Miller)e(and)h(J.)h(F)-8
b(.)24 b(Pekny)-6 b(.)38 b(The)23 b(role)f(of)i(performance)e(metrics)h
(for)h(parallel)d(mathematical)g(programming)h(algorithms.)209
1505 y Fb(ORSA)f(Journal)d(on)i(Computing)p Fn(,)e(5\(1\),)i(1993.)43
1652 y([36])40 b(M.)33 b(Padberg)e(and)g(G.)i(Rinaldi.)59
b(A)33 b(branch\255and\255cut)c(algorithm)h(for)j(the)f(resolution)e
(of)i(large\255scale)e(symmetric)k(traveling)209 1766
y(salesman)20 b(problems.)27 b Fb(SIAM)20 b(Rev)-6 b(.)p
Fn(,)21 b(33:60\226100,)16 b(1991.)43 1913 y([37])40
b(P)-10 b(.)20 b(Pardalos,)e(Y)-10 b(.)20 b(Li,)f(K.G.)g(Ramakrishna,)f
(and)g(M.G.C.)i(Resende.)25 b(Lower)18 b(bounds)g(for)i(the)e
(quadratic)f(assignment)h(problem.)209 2028 y Fb(Annals)c(of)h
(Operations)f(Research)p Fn(,)h(50:387\226411,)d(1994.)18
b(Special)c(V)l(olume)g(on)h(Applications)d(of)j(Combinatorial)d
(Optimization.)43 2175 y([38])40 b(Judea)23 b(Pearl.)38
b Fb(Heuristics\255Intelligent)19 b(Search)24 b(Strategies)e(for)i
(Computer)f(Problem)f(Solving)p Fn(.)38 b(Addison\255W)o(esley)-6
b(,)22 b(Reading,)209 2289 y(MA,)f(1984.)43 2437 y([39])40
b(Ira)35 b(Pramanick)f(and)h(Jon)f(G.)i(Kuhl.)66 b(An)35
b(inherently)e(parallel)f(method)i(for)g(heuristic)g
(problem\255solving:)55 b(Part)34 b(i\255general)209
2551 y(framework.)28 b Fb(IEEE)20 b(T)-6 b(ransactions)19
b(on)h(Parallel)d(and)j(Distributed)e(Systems)p Fn(,)j(6\(10\),)e
(October)g(1995.)43 2698 y([40])40 b(B.)18 b(Monien)e(R.)i(Feldmann,)e
(P)-10 b(.)18 b(Mysliwietz.)24 b(Studying)16 b(overheads)g(in)h
(massively)h(parallel)d(min/max\255tree)h(evaluation.)21
b(In)d Fb(Proc.)209 2812 y(of)i(the)g(6th)g(ACM)g(Symposium)g(on)g
(Parallel)e(Algorithms)h(and)g(Architectures)p Fn(,)g(pages)g
(94\226103,)f(1994.)43 2960 y([41])40 b(A.)26 b(G.)g(Ranade.)40
b(Optimal)24 b(speedup)f(for)j(backtrack)f(search)g(on)g(a)h
(butter\003y)e(network.)41 b(In)26 b Fb(Proceedings)d(of)i(the)g(Third)
f(ACM)209 3074 y(Symposium)c(on)g(Parallel)e(Algorithms)h(and)g
(Architectures)p Fn(,)g(1991.)43 3221 y([42])40 b(V)-7
b(.)30 b(Nageshwara)e(Rao)h(and)g(V)-7 b(.)30 b(Kumar)l(.)53
b(Concurrent)28 b(access)j(of)f(priority)e(queues.)52
b Fb(IEEE)30 b(T)-6 b(ransactions)28 b(on)i(Computers)p
Fn(,)209 3335 y(C\25537\(12\),)18 b(1988.)43 3483 y([43])40
b(V)-7 b(.)23 b(Nageshwara)d(Rao)i(and)g(V)o(ipin)f(Kumar)l(.)33
b(On)23 b(the)f(ef)o(\002cicency)g(of)h(parallel)c(backtracking.)33
b Fb(IEEE)23 b(T)-6 b(ransactions)21 b(on)h(Parallel)209
3597 y(and)f(Distributed)f(Systems)p Fn(,)j(4\(4\):427\226437,)17
b(April)k(1993.)31 b(Also)22 b(available)d(as)j(T)-8
b(echnical)20 b(Report)h(TR)h(90\25555,)e(Department)g(of)209
3711 y(Computer)f(Science,)g(University)h(of)g(Minnesota,)e
(Minneapolis,)g(MN.)43 3858 y([44])40 b(C.)26 b(Roucairol.)41
b(A)26 b(parallel)d(branch)h(and)h(bound)f(algorithm)f(for)j(the)f
(quadratic)e(assignment)i(problem.)41 b Fb(Discr)m(.)26
b(Appl.)e(Math.)p Fn(,)209 3972 y(18:211\226225,)16 b(1987.)43
4120 y([45])40 b(B.)29 b(Monien)e(S.)i(T)-8 b(schvke,)31
b(R.)e(L|ling.)50 b(Solving)27 b(the)h(traveling)f(salesman)h(problem)f
(with)h(a)h(distributed)d(branch\255and\255bound)209
4234 y(algorithm)21 b(on)j(a)f(1024)f(processor)h(network.)36
b(In)23 b Fb(Proc.)h(of)f(the)g(9th)g(International)c(Parallel)i
(Processing)i(Symposium)p Fn(,)g(pages)209 4348 y(182\226189,)18
b(Santa)h(Barbara,)f(CA,)i(April)f(1995.)43 4495 y([46])40
b(Benjamin)20 b(W)l(.)i(W)m(ah,)f(Gou\255Jie)g(Li,)h(and)f(C.)i(F)-8
b(.)21 b(Y)l(u.)33 b(Multiprocessing)19 b(of)j(combinatorial)d(search)j
(problems.)31 b Fb(IEEE)22 b(Computer)p Fn(,)209 4610
y(June)e(1985.)43 4757 y([47])40 b(Benjamin)20 b(W)l(.)i(W)m(ah)f(and)g
(Y)-10 b(.)22 b(W)l(.)g(Eva)g(Ma.)33 b(MANIP\227a)21
b(multicomputer)f(architecture)g(for)h(solving)g(combinatorial)e
(extremum\255)209 4871 y(search)h(problems.)27 b Fb(IEEE)20
b(T)-6 b(ransactions)19 b(on)h(Computers)p Fn(,)f(c\22633,)h(May)g
(1984.)1947 5610 y Fk(14)p eop
%%Trailer
end
userdict /end-hook known{end-hook}if
%%EOF