A library hierarchy for implementing scalable para

ALibraryHierarhyforImplementingSalableParallelSearhAlgorithmsL.Ladanyi,T.K.Ralphsy,andM.SaltzmanzNovember14,2001AbstratThisreportdesribesthedesignoftheAbstratLibraryforParallelSearh(ALPS),aframeworkforimplementingsalable,parallelalgorithmsbasedontreesearh.ALPSisspeiallydesignedtosupportdataintensivealgorithms,inwhihlargeamountsofdataarerequiredtodesribeeahnodeinthesearhtree.ImplementingsuhalgorithmsinasalablemannerisdiÆultduetodatastoragerequirements.ThisreportalsodesribesthedesignoftwootherlibrariesbuiltontopofALPS,therstofwhihistheBranh,Constrain,andPrieSoftware(BiCePS)library,aframeworkthatsupportstheimplementationofparallelbranhandboundalgorithmsinwhihtheboundingisbasedonsometypeofrelaxation,usuallyLagrangean.Inthislayer,thenotionofglobaldataobjetsassoiatedwiththevariablesandonstraintsisintrodued.TheseglobalobjetsprovideaonnetionbetweenthevarioussubproblemsinthesearhtreeandpresentfurtherdiÆultiesindesigningsalablealgorithms.Finally,wewilldisusstheBiCePSLinearIntegerSolver(BLIS),aonretizationofBiCePS,inwhihlinearprogrammingisusedtoobtainboundsineahsearhtreenode.1IntrodutionThisreportdesribesresearhinwhihweareseekingtodevelophighlysalablealgorithmsforperforminglarge-saleparallelsearhindistributed-memoryomputingenvironments.Tosupportthedevelopmentofsuhalgorithms,wehavedesignedtheAbstratLibraryforParallelSearh(ALPS),aC++lasslibraryuponwhihauseranbuildawidevarietyofparallelalgorithmsbasedontreesearh.Initially,wewillbeinterestedinusingALPStoimplementalgorithmsforsolvinglarge-saledisreteoptimizationproblems(DOPs).DOPsariseinmanyimportantappliationsDepartmentofMathematialSienes,IBMT.J.WatsonResearhCenter,YorktownHeights,NY10598,ladanyius.ibm.omyDepartmentofIndustrialandSystemsEngineering,LehighUniversity,Bethlehem,PA18015,tkralphslehigh.edu,~tkr2,fundingfromNSFgrantACI-0102687andIBMFaultyPartnershipAwardzDepartmentofMathematialSienes,ClemsonUniversity,mjslemson.edusuhasplanning,sheduling,logistis,teleommuniations,bioengineering,robotis,designofintelligentagents,et.MostDOPsareintheomplexitylassNP-ompletesothereislittlehopeofndingprovablyeÆientalgorithms[12℄.Nevertheless,intelligentsearhalgorithms,suhasbranh,onstrain,andprie(BCP),havebeentremendouslysuessfulattaklingthesediÆultproblems.TosupporttheimplementationofparallelBCPalgorithms,wehavedesignedtwoaddi-tionalC++lasslibrariesthatarebuiltontopofALPS.Therst,alledtheBranh,Con-strain,andPrieSoftware(BiCePS)library,implementsageneriframeworkforrelaxation-basedbranhandbound.Inthislibrary,wemakeveryfewassumptionsaboutthenatureoftherelaxations,i.e.,theydonothavetobelinearprograms.Theseondlibrary,alledtheBiCePSLinearIntegerSolver(BLIS),implementsLP-basedbranhandboundalgorithms,inludingBCP.ThedesignoftheselibrarieswillallowustodevelopparallelalgorithmsthatnotonlyhavetheabilitytoutilizeaverylargenumbersofproessorseÆiently,butalsohavetheabilitytohandleverylargeprobleminstanesfromverydiÆultproblems.Themainfeatureofsuhalgorithmsisthattheyrequirethemaintenaneofavastamountofinformationabouteahnodeinthesearhtree.However,thisdatausuallydoesnotvarymuhfromparenttohild,soweusedatastruturesbasedonauniquediereningshemewhihismemoryeÆient.Thisshemeforstoringthetreeallowsustohandleproblemsmuhlargerthanweotherwiseould.Anumberoftehniquesfordevelopingsalableparallelbranhandboundalgorithmshavebeenproposedintheliterature[3,9,10,15,17,39℄.However,weknowofnoprevi-ousworkspeiallyaddressingthedevelopmentofsalablealgorithmsfordata-intensiveappliations.StandardtehniquesforparallelbranhandboundbreakdownwhenappliedtoBCP,primarilybeausetheyalldependontheabilitytoeasilyshuttlesearhtreenodesbetweenproessors.ThedatastruturesweneedinordertoreateeÆientstoragedonotallowthisuidmovement.OurdesignoveromesthisdiÆultybydividingthesearhtreeintosubtreesontainingalargenumberofrelatedsearhnodesthatanbestoredtogether.Thisrequiresthedesignofmoresophistiatedloadbalaningshemesthataommodatethisstorageonstraint.Thisprojetbuildsonpreviousworkinwhihwedevelopedtwoobjet-oriented,generiframeworksforimplementingparallelBCPalgorithms.SYMPHONY(Single-orMulti-ProessOptimizationoverNetworks)[34℄isaframeworkwritteninCandCOIN/BCP[36℄isaframeworkwritteninthesamespiritinC++.Beauseoftheirgeneri,objet-orienteddesigns,bothareextremelyexibleandanbeusedtosolveawidevarietyofdisreteoptimizationproblems.Soureodeandextensivedoumentationforbothframeworksareurrentlydistributedforfreetotheresearhommunityandeahisinuseatanumberuniversitiesandresearhentersworld-wide[33℄.Withrespettosequentialomputation,thesetwopakagesarematureandwellrened.Theyeahontainmostoftheadvanedfeaturesavailableintoday’soptimizationodesandoupytheuniquepositionofbeingtheonlygeneri,parallelimplementationsofBCPweareawareof.Eahanahievelinearspeedupforsmallnumbersofproessors,but2theyemployamaster-slaveparadigmthatausesthetreemanager(ortheutpoolintheaseofSYMPHONY)tobeomeabottlenekwhenthenumberofproessorsislarge.Ouronlusionisthatwearedoingmostthingsright.WearenowinapositiontomovetowardeÆientlarge-saleparallelism.2MotivationandBakground2.1Branhand