Scalable global and local hashing strategies for d

SubmittedtoIEEETransactionsonParallelandDistributedSystems,1994.ScalableGlobalandLocalHashingStrategiesforDuplicatePruninginParallelA*GraphSearch1NiharR.MahapatraandShantanuDuttDepartmentofElectricalEngineering,UniversityofMinnesota,Minneapolis,MN55455PrincipalContact:ShantanuDuttPhone:612-625-0323;Fax:[phone]emailaddress:[e-mail]19,1995AbstractFormanyapplicationsoftheA*algorithm,thestatespaceisagraphratherthanatree.TheimplicationofthisforparallelA*algorithmsisthatdierentprocessorsmayperformsignicantduplicatedworkifinter-processorduplicatesarenotpruned.Inthispaper,weconsidertheproblemofduplicatepruninginparallelA*graph-searchalgorithmsimplementedondistributed-memorymachines.Acommonlyusedmethodforduplicatepruningusesahashfunctiontoassociatewitheachdistinctnodeofthesearchspaceaparticularprocessortowhichduplicatenodesarisingindierentprocessorsaretransmittedandtherebypruned.Thisapproachhastwomajordrawbacks.First,loadbalanceisdeterminedsolelybythehashfunction.Second,nodetransmissionsforduplicatepruningareglobal;thiscanleadtohotspotsandslowermessagedelivery.Toovercometheseproblems,weproposetwodierentduplicatepruningstrategies:(1)Toachievegoodloadbalance,wedecouplethetaskofduplicatepruningfromloadbalancing,byusingahashfunctionfortheformerandaloadbalancingschemeforthelatter.(2)Anovelsearch-spacepartitioningschemethatallocatesdisjointpartsofthesearchspacetodisjointsubcubesinahypercube(ordisjointprocessorgroupsinthetargetarchitecture),sothatduplicatepruningisachievedwithonlyintra-subcubeoradjacentinter-subcubecommunication.Thusmessagelatencyandhot-spotprobabilityaregreatlyreduced.TheaboveduplicatepruningschemeswereimplementedonannCUBE2hypercubemulticomputertosolvetheTravelingSalesmanProblem(TSP).Foruniformlydistributedinter-citycosts,ourstrategiesyieldaspeedupimprovementof13-35%on1024processorsoverpreviousmethodsthatdonotpruneanyduplicates,and13-25%overtheprevioushashing-onlyscheme.Fornormallydistributeddatathecorrespondingguresare135%and10-155%.Finally,weanalyzethescalabilityofourparallelA*algorithmsonk-aryn-cubenetworksintermsoftheisoeciencymetric,andshowthattheyhaveisoeciencylowerandupperboundsof(PlogP)and(Pkn2),respectively.Keywords:A*algorithm,branch-and-boundsearch,communicationdelay,duplicatepruning,graphsearch,isoeciencyfunction,k-aryn-cubes,parallelA*,scalability,travelingsalesmanproblem.1ThisresearchwasfundedinpartbyaGrant-in-AidfromtheUniversityofMinnesotaGraduateSchoolandinpartbytheNSFgrantMIP-9210049.SandiaNationalLabsprovidedaccesstotheir1024-processornCUBE2parallelcomputer.1IntroductionTheA*algorithm[24]isawell-known,generalizedbranch-and-boundsearchprocedure,widelyusedinthesolutionofmanycomputationallydemandingcombinatorialoptimizationproblems(COP’s)[27].Itsoperation,asdetailedlater,canbeviewedessentiallyasabest-rstsearchofastate-spacegraph.Parallelizationofbranch-and-boundmethodsprovidesaneectivemeanstomeetthecomputationalneedsofmanypracticalsearchproblems[7].Manyresearchershaveadoptedatreesearch-spaceformulationinproblemsliketheTravel-ingSalesmanProblem(TSP)[12,23],the15-puzzleproblem[12]andthevertexcoverproblem[12],wherethenaturalformulationisagraph.Thisimpliesthatnodesrepresentingidenticalsub-problemsarearticiallydenedtohavedierentstates.Thusidentical-subproblemnodesremainundetectedresultinginduplicationofsearch.Thisleadstoaninecient,althougheasilyparal-lelizable,sequentialA*/best-rstsearchalgorithm:eachprocessorexploresadierentpartofthesearchspacethatisdisjointfromthesearchspacesofotherprocessors.Thusa\misleadinggoodspeedupcanbeobtained.Agraphformulation,ontheotherhand,willenabledetectionofidenticalsubproblemsinA*andhenceavoidduplicatedsearch.However,itisnotaseasilyamenabletoparallelizationondistributed-memorymachinesasatreeformulation,sinceduplicatenodesmaybegeneratedindierentprocessors.Acommonlyusedmethodforpruninginter-processorduplicatesingraphsearch,utilizesasuitablehashfunctiontoassociatean\ownerprocessorwitheachdistinctnodeofthesearchspace.Thenduplicatenodesarisingindierentprocessorsaretransmittedtothesameownerwheretheyarepruned[8,21].Therearetwosignicantshortcomingsinthisapproach.First,loadbalanceisdeterminedsolelybythehashfunctionandhencemaynotbeveryeective.Second,nodetransmissionsforduplicatepruningareglobal;thiscanleadtohighermessagecontention(hotspots)andlatency.Theoverallgoalofourworkistodevelopscalablehigh-performanceparallelA*algorithmsfordistributed-memorymachinesthatcanbeappliedtomostCOP’s.InourpreviousworkonparallelA*,wedevelopedecientloadbalancingstrategies[5,6]thatareequallyusefulforbothtree-searchandgraph-searchproblems,anddemonstratedtheirsuperiorperformanceoverothercompetingmethods[1,11,13,17,25].Inthispaper,wedevelopecientinter-processorduplicatepruningmethods,andincorporatetheminparallelA*algorithmstoobtainhighspeedupoversequentialA*graphsearch.InSec.2,werstdescribeA*andthenpresentanimprovedversionusedinourimplementations.Next,inSec.3weoutlineourapplicationofA*toTSP,thetestproblemusedtodeterminetheecacyofourparallelizationtechniqu