Parallel Iterative A* Search: An Admissible Distributed Heuristic Search Algorithm

1 Introduction

Best.-first. heuristic search algorithms, such as the A · al­ gorithm, art" one of t.lw most. import.aut techniques usPJ t.o solve many problems in art ilicia.l intelligence and op­ erations research. A common ft·at.ure of heuristic search is it.s high computational cornplexit.y, which has signifi­ cant.ly limit.ed its application in practical domains such as flexible manufacturing, strategic planning, and man­ agenwnt. .

r n t.he past. decade, many parallel architectures have bet'n proposed and some of them are now commer­ ciallv available. Advances in pamllel computer technol­ ogy ·have offered the potential to greatly speedup t.he computations in genera.!. Due to the combinatorial as­ pect.s of heuristic search, a very large scale of parallelism can be potentially explored. However, the etllciency of lwurist.ic search algorithms mainly comes from the intel­ ligent. guidame of heuristics. \\'hen implementing par­ allel heuristic search algorithms on connnercial mult.i­ computers, researchers oft.f~ll face a tradeoff between the faithfulness to global hemistics and t.lw high communi­ cation cost. which serializes and slows down t.he COillJliJ­ t.ation. llnt.il recently, there was no easy solution to this dilemma..

In this pap('r, we present a dist.rihut.ed lwst-first hemist.ic search algorithm, Pa.mllel Iterative A · (PI A · ). We show that. the algorit.Inu is admissible, and we give an informal analysis of its load balancing, scalability and speedup. To empirically test the PI A* a.lgorit.lnn, a flow­ shop scheduling problem has been implemented on t.he BRN Butterfly 1\Jult.icomput.er [UBN, 1985) using up t.o 80 processors . From our experiments, this algorithm is Larry S. Davis Computer Vision Laboratory Center for Automation Research University of Maryland, College Park College Park, MD 207 42

capable of achieving almost. linear speedup on a large number of processors with relatively small problem size.

We will assume the reader is familiar with the A* al­ gorithm [Hart et a./. , 1968).

1.1 Related Work

Research in paralld heuristic search has been very active recent.ly. A* can he paralldized by storing the OPEN list. in global storage that. is accessible t.o all processors [l\lohan, 1982). l:l uang and Davis [ HJ87) use queueiug theory to show t.hat. this approach can achieve almost. linear speedup to a certain number of processors. How­ ever, beyond that. point.. the SJW<>dup lev<>ls oft' suddenly, no matter how many processor are used. Ra.o and Ku­ rnar [ 1988) proposed a concmren t heap dat.a structure for oi·ganizing the global OPEN list .. The tww data st.ruc­ hue allows processors to interleave operations on 0 PEN and improves the speedup to some extent; however, con­ gestion near t.he root. of the concurrent heap is still a problem.

Ktllmlr et a/. [1988) propos!:' another approach whirh su bstitut.es a. shared l3 LACKBOARD for t.he global OPEN list. and J.,t. each processor maintain its own lo­ cal OPEN list. Unfortunately, the BLACKBOARD may eventually become a bot.t.leneck as the number of proces­ sors increases.

A distributed approach has also be<>n tried by some researchers. Early work is represented by Wah and Eva Ma's MANIP [191:H). Anderson and Chen [1987) pre­ sented an algorithm to perform distributed best-first. search on hypercube multicomputers. To balance t.he workload , t.hey proposed t.o exchange a. summary of t.he cost. distribution in t.he local OPEN lists of nt>ighhor­ ing processors. Quinn [ 1987) presented four ot.her imple­ mentations of the best-first. S(~a.rrh on hypercubes. These four simple algorithms tried t.o ('it.Jwr improve t.lw useful computation at each processor, or t.o in1prove t.he com­ munication cost. , but. failed t.o effectively improve bot.h at. t.he same time.

2 The PIA* Algorithm

P JA · proceeds by repet.it.ive synrhroniz(~d it.<>rat.ions . At. each iteration , processors are synchronized twice t.o carry out. t.wo difl'erent. procedures: t.he node e:rpan.sion pmce­ dur·e and the node lmn.sfer procf'dure. Operations are largely local to the processor in the node expansion procedure and are complet.ely local in the node trans­ ft>r pl·ocf'dme. Dat.a. st.mct.mes in PI A · are dist.rihut.t·d to avoid bottleJwcks. Node selection, node expansion, node ordf'ring and successor distribution opNa.t.ious are fully paralldized by processors. Processors performing S('cll'ches which art' not. following t.he cmrent hest. hem·is­ t.ics are synchronized t.o st.op as soon as possible t.o reduce search ovnhea.d (the increase in t.he uumher of nodes that. must. be t>xpandt·d owing to the int.rodmt.ion of JHHall«>lism) . Dming processor synchronization, specu­ lat.iw eompnt.ations are cout.ingent.ly performed at. each processor, trying t.o keep processors always produd.iH·Iy busv. t.o reduce synchronization overheat!. Unnecessary con;mnnicat.ions are a.voi(led as long as processors atf' performing worthwhile st>arch work t.o reduct> comnmni­ cat.ion overht>ad. A symmetric successor node dist.rihu­ t.ion mdhod is us('d to direct. load balancing. Finally, the coned t.enninat.ion of PI A · is facilitated by it.s iterative st.rud.ure.

A general scalable parallel a.rchit.ect.ure model is used hy us t.o describe P1 A·. The architecture consists of a. sd of processor-lllf'lliOry pairs whieh conmJnnica.t.e through an unspecifif·d communication channel. The communicat.ion chamwl can be realized using a shared nwmo1·y or by message passing. 1\Jemory rcft>rencing through local HWilJory is compkt.('d in ronst.ant. unit. t.inw. A remote reference through the communirat.ion channel. howev('r, requires O(log P) time undt>r normal balanced t.raffic, where P is the uumber of processors. It. is our belief that this arch it.ect.ure model is general enough t.o snbsu111e most. scalable mnlt.icomput.ers which arf' ('lli'I'Pnf.lv available commercially, such as t.he BBN Bnt.t.erliy [Him, HJ85), t.he lnt.«>l Hy\wrcnbe [Int.d, 1981i] and t.he ConJwct.ion Machine [Hillis, 1985] .

HPcaHse some forward n-~ fen'nces are reqn ired for us t.o describe P 1.rl*, the reackr may need to re-read t.his sed.iou t.o understand this algorithm.

2.1 Data Structures

ln each processor j, two lists are maintained in it.s I o­ ral memory: t.he work list. (IV Lj) and the reception list. (RLj ), as shown in Figure 1. H-' Lj is a priority queue and RLj is a simple list. . At. t.he hPginning of each it.PJ'a­ t.ion. I·FLj cont.aiHs the sorted nodes awaiting expansion by processor j, and RLj = 0. Dnring the node expansion procedure, successor nodes generated are distributed t.o R Lj, j = 0 ... P- I, using a. successor dist.ribut.ion algo­ rithm t.o lw descrilwd in Section 2.5.

Henceforth, we will use W L/ t.o denote t.he set. of nodPs in t.lw work list. of processor j at. the beginning of it.era.t.ion i. If the subsnipt. is omit.t.ed , it. means t.he union of all P JH'OCt'ssors' work lists. That. is,

IJ t.he sHpnscript. is o111it.t.ed, it. means for all iterations. Similar uot.a.t.ion will he usf'd throughout. t.his paper.

Initially, H'£ 0 = {s} and R£ 0 = 0. As PIA· pro­ O't>ds, II' J} is similar to a. snapshot. of the OPEN list in A·, but. dist.ribut.ed.

2.2 Iteratiou Thr·~shohl. Mandatory Nodes ami Speculative Nodes

A threshold ti is associated wit.h each it.erat.ion i, with t 0 = h(s). How ti+l is a.ct.ua.lly computed will be de­ scribed iu the next section .

A node 11 E H' Li is ddined t.o be a mandatory node if f(n) ~ t i . Let Mi, which is a.snbset. of H'Li, be t.he set. of all mandatory nodes. As we shall see later, allmanda.­ t.orv nodes will event.ttallv be selected for expansion by eit.I;Pr _A· or PJA· in t.h; worst. case. A node n E IF Li is defined t.o be a .SJifCulafir·e node if f(n) > ti. Lt>t. Si be t.h(:' set. of all speculative nodes. Tlwn, ll'L; =ill; u s·i.

Init.ially, !tJ 0 = { ~} and S 0 = 1/J .

2.3 The Node Expansiou Procedure

The node expansion procedme at. each it.f'ra.t.ion i OJWr­ at.es as follows. A processor j first expands all the nodes from M/ and, by an algorithm to he describNI in Sect.ion 2.5 , put.s all t.he successor nodPs gt>w·rat.t·d into t.he rf'­ O'pt.ion lists ( RL ). Tlwn, as long as any ot.lwr p1·oct>ssor is expanding a nH:t.ttdat.ory nodt>, t.his processor cont.in­ tws t.o expand the best speculat.ivt' node from .'3/. \Vhen all t.he nodes fmm l\.[i haw he«>n PXpamlt>d, all JH'OCPS­ sors synchronize for tlw node transfer procedure which is dPscribed in Section 2.G.

ln PI .~1·, successors genPrat.ed by a. node expansion are not. consi(kred for expansion unt.il t.lw next. it.Pra­ t.ion; t.lwy are added t.o RL inunediat.ely aJt.er t.hey are generated.

Tlw node expansiou procedllJ'(' also computes ti+l and broadcasts it. to all processors. Jt. is set. t.o t.he maximum of (a)ti, and (h)t.lw minimum cost. of (i)all successors genf'ra.t.f'd from nodes in !tf', and (ii)t.he nodes inS'. LPt. Stt.c(.) be an opera.t.or which llla.ps a. set. of nodes t.o t.lwir successor nod('S. Tlwn. ti+l can be expressed as:

Thne is an etTicit>nt. pa.ra.IIPl nwt.hod for COHIJHII ing ti+l. For each processor j, a local constant. Cj. which is the minimum cost. of ( a)a.ll successors generated from nodes in Mj;, and ( b )the lwst. nod1' in s·j i, ran hP com­ puted dming t.he node expansion procPdurt>. Then, the mininmm of Cj, j = 0 · · · P- J, can be comput.t>d in par­ allel in time O(log P) [Paige and l\ruscal, I!J85] while processors are synduonizt'd; ti+J is then t.he maximum of ti and t.he computed minimum.

2.4 Synchronization

Let. us digr t'SS lwre t.o discuss how processor synchroniza­ tion in t.he node expansion procedme can be eHi cient.l y and correct.Jy implC'Ilwnt.ed. Essentially, what. we IH'ed is a barrier S.IJnchro ni.:ation bct.w«:>en processors. All of t.he processors a1·e rt'quired t.o meet. at. t.he barrier before any are a llowed t.o proceed . The harril'l' i11 our case is a sl. at.e iu which ea.rh processor j has fi11ishetl expanding llfj. Unt.. instead of unproduct.ive wait.ing at. I. he barri t> r, a processor j continues t.o expand the best speculative node from Sj while waiting.

If a sha rt>d nwmory is available, t.he ha rrier synchro­ nization ca11 be implnnent.ed by haviug a globa l variable whi ch rouut.s tht> n11mber of processors tha.t are wa.it.ing a.t. the ha rri t'r. When all of t.he processors have arrived a t. t.he barriPr , t.he barriN can be removed . This approach rt>q11ires at.omir o1wrat.ions on a global variable and may neat.e a hot. spot..

A lw t.t.Pr approa.d1 , called the butte1:fi.1J barrier sug­ gt>st.ed by Brooks Ill [l98G] , is t.o let. each processor syn­ chronizt' wit.h another processor pairwise at. each of log P stages in order to synchronize P processors. This ap­ proach rPmoves t.lw critical rPgions and hot. spots wit.h desired scalability, and is suitable for message-passing a rrhit.ectures, such as hypercubes, as well.

2.5 The Successor Distrihntion Algorithm

S11ccessor nodPs generated by a. processor are put. int.o R Lj. j = 0 · · · P - l , in a mu.Uiplcl: r·ound-mbin fashion. More prt>c i:=wly, snpposP that. the most. recent. SIICCPssor node gt·Jwnlted by processor j is adJt>d to RL;. Then t.he nPxt. successor node generated by processor j will be added t.o RL~,, wlwre k = (i + 1 mod P). At. each itPra t.ion , processor j sends its first. generated successor t.o RLi .

Tlw adva.nt.a.ge of t.his appmach is tha t. it. is simple t.o impleJJwnt and it.s symmetric st.ruct.ure lwlps PI A · at.­ t.a in t.h t> desired load balancing (see Section 5.1). Since t.he st1ccessors gener;:~t.ed are not. ronsidered for expan­ sion until t.he next. iteration,· son1e optimization can he made for message-passing architectures. 1\'fl>ssa.ges for suc ressor dist.rib11tion can he asynchronous so that coln­ pHt.a.t.ion and communication can be overlap pet! . For a rchitf:'ctures which requirP large comnJunicat.ion sf:'t.up t ime, successor nodes genera.t.ed can be distribut.,,d and cached in local memory and not. sent. until a.n effirient. messa.gt' size lor the underlying archit.ect.ure is reached .

2.6 The Node Transfer Procedure

After t.lw J!odf' expansion procedure, each processor j empt.it's t.lw nodf:'s fwm RLj and insPrt.s t.hem into II' Lj t.o fom1 a JJeW priority queue for t.he next. it.erat.ion . Note that. t . ht~ nodt> t.ransfer procedme is complt>t.dy local; no conJmun icat.ions he tween processors are req1.1ired .

Tht> relationship be tween IV £i+l and TV Li call be ex­ pressed as:

( Eq2) wlwre I;i E S; is t.he set. of speculative nodes whir.h were sd ec t.ed for eXJHHJsion by processors in t.he node expan­ sion procedure at. iteration i t.o use t.he otherwise idle t.ime for processor synchmuizat.iou.

2. 7 Termination

When a manda.t.ory node is fo11nd to he a. goal node by a. processor , a. message can be broadcast to inform a.Jl processors to termina.t.e . If a spenlla.t.ivP node is found t.o be a goal node, this node is simply added t.o RL because it 111a.y not. be an opt.ima l goal node.

PIA* can terminate, failing t.o reach a goal node, when H' Li = 0. IV Li = 0 if and only if 1r L/ = 0, for all j = 0 · · · P -1. This st.at.e can h(· rt'cognized ami broadcas t. to a ll processors at. t.he end of t he node transfer procedme.

2.8 Summary

The PI A · algorithm c.an be Sll!lllllar ized below:

loop until a goal node i.s ,·cached or IF£ i.s empty { Start. uocle expansion procedme }

for rach processor· j

eJ·pand all mandator:IJ node.s fmm I·V Lj , and add succcs.sor·s to RL u..sing the multiplcl: r·ound-robin .succFssm· distril11ttion algorithm:

while then-: is a processor Cl:panding a mandal.or·:IJ node

o·pand the bc.st speculati1·e node fmm W Lj and a.dd su.cce.ssoT'S to R L using the multiplo: round-r·obin .successor distribution algorithm;

{ Start. node transfer procedure }

for each pmcc.ssor· j

insert all nodes from R L i to II ' Lj;

Mandat.ory nodes and speculative nodes are discrimi­ na k J by comparing t.lwir cost. t.o a threshold f . A node n is a maiHJat.ory node if f(n) ::::; t; otherwise, it. is a speculal.ive node. Init.ia.lly, t = h( s ). Successive I values a re comput.t>d dming t.he node expansion procedure by ( l::q I) presented in Sect.ion 2.3.

3 Admissibility

It. is well known t.hat. if tlw heuris tic fuuct.ion h ::::; h* (the shortest. distance to a goal nodt·), t.lwn .A · is ad lllissible . PI A · is also a.thuissible IInder t.lw same conditions .

PI .A* has a similar property found in A* [Nilsson , HJ80]; i.e.:

Lemma 1 'Vi before termination. 3n' E W Li su.ch thai n' is on an optimal path from .s to a goa./ node and f(n') :S f*(.s).

Proof: (By induct.ion on t.lw numlwr of it.t'rat.ions) Ini­ t.ially, 11: L 0 = {s} and f( s ) = h( s ) ::::; h* (s) = J*(s) . Hence, s is t.he nod(·' 11 1 · Assnnw t.he IP illiWI is true for all H' Li I i < ~' . and ~~~· is a nodt>, in I r £~·. whi('h is on an optin~l path and J(n~' ) ::::; f*(.s). If node n~' was not. expandPd at. it.t'J'at.ion ~: . t.lwn nodP nk is in W J}'+l and t.he lemma is provNI. If n~' \\'as PX­ pa.nded a t. iteration k ( 11k was not. a goal node; oth­ erwise PI A · would have tPrminat.ed. ). then , sinre n~' is on an optimal path , one of it.s successors n' is on an optimal pat.h . From ( Eq2), node n' is in IV Lk+l , ant!

From (Eql) , we know ti+l ~ ti , for ewry i . !'l'loreowr , ti+ 1 = t i if and only if there is a nodt' 11 E Sv.c(JIJ ; ) wit.h f( 11) ~ ti (Note that. this node n will lw expanded at. it.erat.iou i + 1). Because we normally assumE' t.he arc cost. in the st.at.e-space graph is positive, this situation cannot. happen forever . Thus:

To show PI A · is admissible, Wt' need to prove another important. property of PI A* .

Lemma 3 Vi l>cforc termination, ti ~ f*(s).

Proof: (By induct.ion on t.he number of iterations) lni­ t.ially, t 0 = .f(s) ~ J*(s). Assume t i ~ f*~s), for all i < k:. Wt> know t!:+ 1 > t!: . If t"+ 1 = t ', t.lwn tk+ 1 ;; .f*(s) by the incluction hypothesis and the lemma is proved. lft!:+ 1 > t" , then, from (Eql) , tk+ 1 = 111in{.f(n) I 11 E Sur( A!") US'"}. By Lemma I . t.he set. i\J!: U .s·!: = IV If hr~s a node n with .f(n) ~ r(s) . It. is straight.forward t.o St'e that. this is also t.rnP for t.h t> sd. I;= S'uc( M~' )US' ~' (see t.he proof of L!,lllllJa. 1 ); i.e., there is at. least one nodt' n E I; such that .f(n) ~ f*(s). Therefore , t!:+ 1 ~ J*(s).

(Q.E.D.)

By lPnm1a 2, t.he threshold will eventually approal'h .f*(s) , if r(s) is finit.e. By L(~mma 3, t.he threshold will newr excet>d f* ( s ) before t. t>rminat.ion . Therefore, PI A* will !.!'rmiuat.(' by finding an optimal pa.t.h if there is one. That. is , we have proved :

Theorem 1 Algorif.hm PIA* is admissible.

4 Comparison of PI A.* to A*

Sonw iut.f:'rt'st.ing relationships exist. bet. ween PI A* and A · . H is well known that. any node 11 wit.h J( 11) < f* (.~) will eveut.ually be st-!Pd.ed for expansion by A*. A node 11 with j'(11) = f*(s) may or may not. he expanded hy A* depeuding on when the first. goal node is reached . llowt'ver. in the worst. case A* will expand all nodes 11 with f(n) ~ J*(s). We haw shown t.hat. ti ~ f*(s). Because a mandat.ory node n in PIA* has f(n) ~ ti, f(n) ~ r(s). for all n E Af; . That is:

Observation 1 All mandato1·y nodt's in PIA* will bt' npandcd by A* and PIA* in the wo1'sl case .

In pradin', PI 1t* may expand more nodes or fewer nodes t.han rl*. This phcnolllt'non is similar t.o the par­ allrl .su1rch anomalies discovert>d previously [Lai and Salmi . l9R4][Quinn and Deo, 198li). 'Ihese anomalies nw beconw noticeable when t.here are many nodes with cost. equal to f*(s) .

lnt.Preslingly, at. the last. if.t'rat.ion of PI A ·, some mandatory nodt'S 11, f(n) < f*(s) , whi ch would be al­ ways expand Pel by A ·, may not he expandPd by P 1 A* when PIA* t.erminat.es with an opt.imal solution path . This /1cnign anomaly of PI A.* is analogous to t.he find­ ing by ~l ero [Meor, HJR4) t.hat. the costs of anct>st.ors can he used t.o const.mct a more informed cost. function t.hat. will always dominate A · 's cost. function.

vVhen only one processor is used t.o run PI A · , no spt>culat.ive nodes would be PXpandt>d at each iteration, and obviously processor synchronization is not. required . PIA* then proceeds very similarly t.o A* exct>pt. t.hat. the order of the node !'Xpansion may lw diH.PrPn(. because a successor generated hy P 1 A* is not. iuuuediat.dy consid­ ert'd for expansion . However, fron1 Ohservat.ion 1. WP know:

Ohscrvatiou 2 PI A* nsiu,q a .sin,qlc pmccs.so1' JIC1fo1'm.s the samr tl ·umbe1' of nodt t'l'pausions as A* in the wo1·.st case.

That. is , PI A* using one processor can perform as well as .tl*.

5 Analysis and Experimental Results

In this section , we will giw an informal analysis of t.he load balancing, sca.labilit.y, and speedup of P 1 Jl*. Expt>r­ imental results will be also shown t.o support. t.he analy­ SIS .

To Pmpirically test. !.he P 1 A* algorithm, a three­ machine flow-shop sdwduling probh"'lll was implt>ment.ed on a BBN Butt.erfly Mult.icomput.er. The three-machine fl ow-shop sdwduling problem is t.o schedule a given sPt. of jobs on three machines such t.hat. t.he spa.n of t.i111e to finish all of the johs is minimized . Tlw towN bound function described by lgnall and Schrage [IU!3G) was ust>d as the cost. fun ct. ion f. vVe ran a 12-job prohlem using G, 10. :w, 30, 40, GO, 60, 10 and 80 procPssors on a Bnt.t.erfly a.nd compared their results. \Ve could not. run t.his prob­ lem on a. single processor because of insulliciPnt. nwmory available on one But.(.erfly processor. 'l'he expninwnt.al results are summarized in Table I. The dP!.a.iled exJwri­ mental results can be found in [Huang and Davis, 198!1].

5.1 Load Balaueiug

Load balancing is one of t.he main fa.ct.ors det.!"nnining t.he efficiency of a parallel algorit.hm. Processors not. only have t.o be kPp(. busy but. also havP t.o be busy on pro­ ductive work a. high percentage of the time in order to at.t.ain good load balancing a.nd to obtain almost linear speedup .

One of the main feat.ures that. contribute to the load balancing of the P 1 A · algorithm is its sym.m.etr·ic strttc­ fu, ·e. Each processor in PIA* maint.ains thP- same type of da.t.a structures, executes the same t.ype of operations, and interacts wit.h other processors in the samt> envi­ ronment . By symmetry principle, probabilistically, the nodes tend to Jist.ribute evenly hot.h in number and in cost among processors . In Figure 2, we plot, from our ex­ JWrinwnt.s , the t.ot al number of nodes expanded at each processor , and the number of nodes It'll in the work list at. each processor when 70 processors were used . The distribut.ion is very even among JH'ocessors .

At each iteration of PIA*, tht·re are two synchronized procedures: the node expansion procedure and the node t.ransft'r procedure . We will study the load bal ancing of these two procedures respect.ively.

5.1.1 Load Balancing in the Node Expansion Procedure

Processors ar1' kept almost const antly busy in the node t>Xpansion Jll'OC!'durt> becausf' t.Jw spt>culaf.ive colllput.a­ t.ion is JH'rfonned additiona lly at each processor to use t. lw waiting t.illlt' for JHOC!'ssor synchroniza tion. This ar­ rangPment. has been Vf'I.'Y effed.ive in our experinwnt.s . As we can set' from Figure 2. the total number of uodes expanded was nearly constant at each of the 70 proces­ sors.

Ant. , how product.ive is the specula tive comput.ation a t. pach iteration? If /IIi is evenly distribu ted a111ong all procf'ssors , t.hf'n very few speculative nodes will be selected for expansion . We have argtwd above tha t. this is gt>twrally so probabilistically, owing t.o t.he symmetri c st.rurt.ure of the P l A · algorithm. A SJH'cul at.ive node sd!'cl.ed for expausion by a procf'ssor is t.he best node a\·a.ilable t.o this processor's work list at that. t.inw. At each it.era t.ion, any speculati ve node n wit.h f(n) < f*( .~ ) can lwcomf' a mandat ory node a t. one of t.lt f' subsequent. it.t>rations , and will evf'nt.ually be expanded by A* as wdl. ll ~· ncf'. t.he speculat.iw roruput.a tion which expands this t.ypt> of srwcul a t.ivf' nodes is also pmduct. ive.

In om PXJl Priments (sf'e Table I) , the tot al numb1'r of specula tive nodes expanded tended to inn ease wlwn mort' processors \vere used ; hut the t.ot.alnumber of nodes (mandatory nodes ami specul ative nodes ) expandt·d did not. t. t>ud to increase (The zigzaggi ng is at.t.ribut.t·d t.o t he parallel Sf'ardt auotrmliPs ). Fur thermore, the t.ot.al lllllllber of itt>rations tendl:'d to df'crease as more processors were used (see Table J ). These results empirically show that most of the speculative computation performed was productive in our experiments .

5.1.2 Load balancing in the Node Transfer Procedure

If each lV Lj , j = 0 · · · P- I, is maintained as a h. ea11 [Horowitz and Salmi , 1978], then the time takf'n for a processor j to finish the node transft>r proc!'dme is pro­ portional t.o RLjlog(H' Li + RLj) . where RLj is the nu1nber of nodes in RLj and W Lj is the number ofnod1,s in H' Li before the node transfer JHOC!'dnre is executt'd.

Therefore, the load balancing of the node trausfer pro­ cPdure depends on how uniform the RLi 'sand t.lte H' Li 's are.

Proof: By the multiplex round-robin algorithm, the numbers of successors 'I'I'Ct>ivf'd by RL; and R Lj from a processor can differ at. most. by J . There are P processors; lwnce, IRL;- RLi I ~ P, if= j .

The nmlt.iplex round-robin algorithm for the successor distribution has a deterministic worst. case which is in­ dqJeudent of the problem sizl' but. can grow linearly wit.h t.he number of processors. T lw probability of t.lw worst> rase occurring is very low as t.Jw lllllllber of processors increases . In fact , when t.he a priori characl.l'l'ist.ics of a problem inst.anC<' are ttnavailahle, lwcause of t.lw sym­ nwt.ry, the expec ted maximutll difff'rence of RLi 's should be dose to zero.

Let. us consider Figmf' 2 again . Because t.he t.ot.al num­ ber of nocl!'s expanded and t.lw fiual size of the work list. at each processor are very uniform, we expt>d. that. the size of RLj 's before the node t.rausfer procedure should lw approxitnal.t'ly uniform at. each it.era tiou. Note that. eac h processor at. each ik rat.ion only expanded k ss than 10 nod!'s on the average (about. 200 nodi's eXJHt.nded 111 over 20 itera tions ) to obtain this load balancing.

5.2 Scalability

Comput ational reqnin·rnent.s for most. intt>rest.ing combi­ natorial search probl<'lliS grow very qni<'kly wit.h prob­ lem size. Jt. is not diffi cult. t.o find problt'tiiS which can use millions of processors for t. lu~ P L·h algorit.lun . Can the PI A* algorithm scale accordingly provided that. t.he underlying umlticompnl.t~r is scalable'? Except. for the successor dist.ribut.iolt and t.he processor synchmnization, OJWrat.ions in PI A · are ro1nph·h·ly local. Uy using the butt erfly barrier suggested by Brook III (J 08ti] , pror<'s­ sor synchronization can scale very wd l with increast'd numbers of processors.

Suceessor distribution is accomplislwd by the lwlp of a rPcept.ion list a t. each processor . Sine!' recept.ion lists are acct>ssed by all processors , a IPgit.imat.f' concem would he whet.lwr contention for them would lead t.o significant. degradation or a bott.leneck. An Pqualnumlwr of rf'cep­ tiou lists and processors exists. and each processor has e! JUal probabili ty of pl acing a node on any reception list.. Because it is a silllple list st.rud .nre, a reception list. can lw prot.ect.ed with a very short. critical region . We ex­ pect t.hat. cont.ent.ion for the reception list.s hy processors will not. be a problt-m iu pract.ice and its seriousness does not. increase with the number of processors. In [Huang and Davis, 1.989), we nse elt>ment.ary queueing theory t.o suppot'l. t.his expectation.

5.3 Speedup

Sinct> PI A* procet>ds it.erat.iwly, we will analyze the speedup in a single it.era.t.iou t.o project t.he overall sprrdup. Sperdup for P processors is normally dpfinrd as t.lw ra.t.io of rxrcut.ion time using one processor and that. using P processors; i.r.,

Lt>t. ns d·'fint> IV, = T1 and ll'p = P · Tp as t.hr tot.al a.mouut. of work requirrd wlwn using one processor ami P procrssors respt-ct.ively. Assume t.ha.t. t.he same set. of uodes arr rxpanded in H', and IV 7 ,. Then, t.o compare IF_, and H 'p. Wt> uot.r that. a fract.ion of Hl,,, f · H',, 0 < f < l, is t.lw work to add succt>ssors t.o R L. When P > I pro­ crssors are usrd, the same amount. of work is converkd t.o nonlocal successor dist.ribut.ion op«"ra.t.ions. Provided t.hat. au assumed scala.blt> mnlt.icomput.er is used t.o run PIA*, f ·IV. is converted to f ·Hr .· · c1logP in H'p , wlwrr c1 is a const.aut. which depends on the eftiriency of t.he communication nc>hvork in t.he underlying mult.i­ comput.er. In addition, 1-Fp also contains t.he comput.a­ t.ion cost. for processor synchronization. Assuming the buttn:fi.IJ ban'ier is used, each processor needs to run log P st.ages and in rach stage communicat.t>s wit.h an­ ot.lwr proressor. The t.ot.al cost. can t.hen be expressed as r2 P log 2 P, wlwre c2 is auot.her constant .. Therefore, we ran expn'ss IVp as:

and the speedup is:

The ahove equation shows how the comnmnication overhead introduced by successor distribution OJWra­ t.ions, and the processor synchronization overllf'ad would affert. the speedup of PI A ·. Since only simple opera­ tions are required for successor dist.ribut.ion, the frac­ tion .f should be very small for most. heuristic search problems. The significance of processor synchronization overhead is inversely proportional to .!jf; i.e., the syn­ ch ron izatio11 overhead is less sign ifir ant if each proressor expands more nodes at each iteration. For exponential searrh problems, we argue t.hat t.here are normally many mandatory nodes at. each iteration. Co11sider t.he 20-city Traveling Salesman Problem as an example. The size of t.he search st.a.t.e space is 20! . Assuming a 32-bit. in­ t.eger is nsed t.o represt'nt. t.he cost. of a sta.t.r , tlwre are at. most. :? 32 different. cost. values. Then, on the average , tht're are over 10 8 states assigned t.he same cost. value! Thr speedup, based on the execution time t.akrn when 5 processors were nsed, is shown in Tahle 1. On the avt'r­ age. fewer than 10 nodes wert> expanded at each iteration when more than !30 proressors WPre used (see [Huang and Davis, U:lR9]) . Overall, only about. 14000 Hodes were ex­ panded in total in every experiment .. The problem size was dwsen so that. the benchmarking time was reason­ ahlt> to nwasme, a.nd it. was just. harf'ly enough t.o Pfff'c­ t.ivdy ut.ilize 80 processors. From our analysis, PI A* , silllilar to most. other paralld algorithms , will perform better for problems with larger problem sizes.

As a comparison, we implenlf'nl.t>d the same problem using the central queue approadt on the same machine. The timing and speedup results are summarized in Table 2. The maximum speedup was less than 3 and the execu­ tion time had no sign of improvt>ment. when we increased the nu1nher of J)fOCPSSOI'S to 50.

Because of nwmory limitations, we were unable t.o obtain the speedup of PIA* based on A* running on a single proressor of Butterfly in Table 1; however, a small problem was tested to compare act.ual running times of PIA* and A*. The result. is shown in Table 3. The speedup of PIA* in Table 3 is based on A* . In our implemeut.a.tions, t.lw run time JWrfonnanre of PI A* using one processor is very dose to A* if both algorit.luns expand t.he same number of nodes . The to­ t.a.l number of nodes rxpanded depends on when a goal node is rear heel, and it can· vary wieldy if there are many nodes with cost. equa.l to the optimal solution cost . Also from Tahle 3, t.he parallelization overhead of PI A* is not significant. for this small problf'm size. (NotP that. when more than one processor a.re used, remote memory rt>fcrcnce has been ff'))Qrt.t-d t.o he about. 5 times more expensive than local memory reference on Butterfly.)

PIA*

"Compared t.o A*

6 Concluding Remarks and Future Research

Wr have presc>nted a dist.ribut.t'd best.-first. lwmist.ic search algorithm, PI A*. We proved the algorithm is admissible and gave an informal analysis of its load halan<'ing. sndahilit.y and speedup. A fl ow-shop sciH'dul­ ing prohknr was chosen t.o itnplf·JrJertt. t.lw P 1.,1· algo­ rit.htn orr t.he BBN But.t.erfly 1\lultiroruput.er using up to 80 (H"Ocessors. 'l'he experiment.al results were encour­ np;ing. H SPPlllS t.hat. this algorithm 1an adricv(' allllost. linear srwedup on a large nunrhcr of pro<'<'ssors wit.lr a r<>lat.ivdy small prohleru size. WP expec t t.his algorit.hm 1an lw efTkiPnt.ly implf'lnent.ed on a large class of s1alahle nrrdt.icornput.Prs ami can solve a variet.y of combinatorial opt.imiza.tion prohkms. How<>wr, lwca.use PI A· has not. lwen ext.Pnsively t.es t.ed on rnany t.ypes of problems and rnult.iconrput.ers, it.s adual limitations and advantages have yet. t.o he more carefully eva.luakd iu future tests.

The PI A · algorithm uses roughly the sanre amount. of nremory as A· .. A· often fails t.o solve a11 exporwnt.ial St'arch problt>tll because it. runs out. of space very qnickly. A lt.hough PIA · can efff'd.ively use the comhiued nwm­ ory of a loosely-coupled multiconrpnt.er, it. is also vnl­ rwrable t.o the memory shortage problem when trying t.o solw large exponential sear1h problems. vVe are ciPwl­ oping a liuear space varia.ut. of PI A · and investigating an implenwnt.ation on the Connection !\'lachine. Fmther results will be published in a sequel to this parwr.

7 Acknowledgements

The aut.hors would like to df:'eply thank Ri1hard Korf who rPvif~Wt·d and critiqued early dra.ft.s of this papn. Vi pin [( urmrr 's comnwnt.s on om early versions of PI A · have hePn very valuahl(, to liS . Special thanks t.o Perry Tlrorrrdyke aud N. S. Sridhar au who encouraged aud suppor·t.ed t.his research .