diff options
Diffstat (limited to 'parallel/dop7.ps')
| -rwxr-xr-x | parallel/dop7.ps | 1844 |
1 files changed, 1844 insertions, 0 deletions
diff --git a/parallel/dop7.ps b/parallel/dop7.ps new file mode 100755 index 0000000..eff0ac1 --- /dev/null +++ b/parallel/dop7.ps @@ -0,0 +1,1844 @@ +%!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 |