%!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 DI<00000030000000000000780000000000 007800000000000078000000000000780000000000007800000000000078000000000000 780000000000007800000000000078000000000000780000000000007800000000000078 000000000000780000000000007800000000000078000000000000780000000000007800 000000000078000000000000780000000000007800000000000078000000000000780000 0000000078000000000000780000007FFFFFFFFFFFF8FFFFFFFFFFFFFCFFFFFFFFFFFFFC 7FFFFFFFFFFFF80000007800000000000078000000000000780000000000007800000000 000078000000000000780000000000007800000000000078000000000000780000000000 007800000000000078000000000000780000000000007800000000000078000000000000 780000000000007800000000000078000000000000780000000000007800000000000078 000000000000780000000000007800000000000078000000000000780000000000003000 000036367BAF41>43 D91 D93 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(ayg@cs.purdue.edu)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(kumar@cs.umn.edu)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