Strategies for dynamic load balancing on highly pa

IEEETRANSACTIONSONPARALLELANDDISTRIBUTEDSYSTEMS,VOL.4,NO.9,SEPTEMBER1993979StrategiesforDynamicLoadBalancingonHighlyParallelComputersMarcH.Willebeek-LeMair,Member,IEEE,andAnthonyP.Reeves,SeniorMember,IEEEAbstract-Dynamicloadbalancingstrategiesforminimizingtheexecutiontimeofsingleapplicationsrunninginparallelonmulticomputersystemsarediscussed.Dynamicloadbalancing@LB)isessentialfortheefficientuseofhighlyparallelsystemswhensolvingnon-uniformproblemswithunpredictableloadestimates.Withtheevolutionofmorehighlyparallelsystems,centralizedDLBapproacheswhichmakeuseofahighdegreeofknowledgebecomelessfeasibleduetotheloadbalancingcommunicationoverhead.FiveDLBstrategiesarepresentedwhichillustratethetradeoffbetween1)knowledge-theaccuracyofeachbalancingdecision,and2)overhead-theamountofaddedprocessingandcommunicationincurredbythebalancingprocess.TheSender(Receiver)InitiatedDiffusion(SIDIRID)strate-giesareasynchronousschemeswhichonlyusenear-neighborinformation.TheHierarchicalBalancingMethod(HBM)organizesthesystemintoahierarchyofsubsystemswithinwhichbalancingisperformedindependently.TheGradientModel(GM)employsagradientmapoftheproximitiesofunderloadedprocessorsinthesystemtoguidethemigrationoftasksbetweenoverloadedandunderloadedprocessors.Finally,theDimensionExchangeMethod(DEM)requiresasynchronizationphasepriortoloadbalancingandthenbalancesiteratively.AllfivestrategieshavebeenimplementedonanInteliPSC/2hypercube.OurresultsindicatethattheRIDapproachperformswell,andcanmosteasilybescaledtosupporthighlyparallelsystems.IndexTerms-Distributedcontrol,dynamicloadbalancing,highlyparallelsystems,hypercubemulticomputer,multicom-putersynchronization,nonuniformproblems.I.INTRODUCTIONULTIPROCESSORsystemshavebeenshowntobeMveryefficientatsolvingproblemsthatcanbeparti-tionedintotaskswithuniformcomputationandcommunica-tionpatterns.However,thereexistsalargeclassofnonuniformproblemswithunevenandunpredictablecomputationandcommunicationrequirements.Dynamicloadbalancing(DLB)schemesareneededtoefficientlysolvenon-uniformproblemsonmultiprocessorsystems[11.Manyloadbalancingtech-niquesdesignedtosupportdistributedsystems(e.g.,LocalAreaNetworks)havebeenproposedandreviewedintheliterature[2]-[7].However,onlyafewstrategieshavebeendesigned,orarescalable,tosupporthighlyparallelmulti-computersystems(e.g.,tightlycoupledmessage-passingandsharedmemorysystems)[8]-[lo],[l],[12],[13].WeareManuscriptreceivedJanuary15,1990;revisedJanuary16,1993.ThisworkM.H.Willebeek-LeMairiswithIBMT.J.WatsonReserchCenter,A.P.ReevesiswihtheSchoolofElectricalEngineering,CornellUniver-IEEELogNumber9212275.wassupportedinpartbyanAT&TBellLaboratoriesPh.D.Scholarship.YorktwonHeights,NY10598.sity,Ithaca,NY14853.interestedindynamicloadbalancingschemeswhichseektominimizetotalexecutiontimeofasingleapplicationrunninginparallelonamulticomputersystem.Todoso,anoptimaltradeoffbetweentheprocessingandcommunicationoverheadandthedegreeofknowledgeusedinthebalancingprocessmustbesought.Wehavedevelopedageneralmodelfordynamicloadbal-ancing[14].Thismodelisorganizedasafourphaseprocess:1)processorloadevaluation,2)loadbalancingprofitabilitydetermination,3)taskmigrationstrategy,and4)taskselectionstrategy.Thefirstandfourthphasesofthemodelareproblemdependentandpurelydistributed;thatis,bothofthesephasescanbeexecutedindependentlyoneachindividualprocessor.Thesecondandthirdphasesoftheloadbalancingprocesscanbeperformedineitheradistributedorcentralizedfashion.Centralizedapproachestendtobemoreaccurateyetmoretimeconsumingandlessfeasibleasthenumberofprocessorsinthesystembecomeslarge.Weareprimarilyinterestedindistributedapproacheswhichcanbescaledtosupporthighlyparallelmulticomputersystems.Thetradeoffbetweenknowledgeandoverheadisillustrated,byexample,withfivedifferentDLBschemes.Theschemespresentedvaryintheamountofprocessingandcommunicationoverheadandinthedegreeofknowledgeusedinmakingbalancingdecisions.Theloadbalancingoverheadincludesthecommunicationcostsofacquiringloadinformationandofinformingprocessorsofloadmigrationdecisions,andtheprocessingcostsofevaluatingloadinformationtodeterminetasktransfers.SenderInitiatedDiffusion(SID)'isahighlydistributedlocalapproachwhichmakesuseofnear-neighborloadinformationtoapportionsurplusloadfromheavilyloadedprocessorstounderloadedneighborsinthesystem.Globalbalancingisachievedastasksfromheavilyloadedneighborhoodsdiffuseintolightlyloadedareasinthesystem.ReceiverInitiatedDifision(RID)istheconverseoftheSIDstrategy,whereunderloadedprocessorsrequisitionloadfromheavilyloadedneighbors.HierarchicalBalancingMethod(HBM)isanasynchronous,global,approachwhichorganizesthesystemintoahierarchyofsubsystems.Loadbalancingisinitiatedatthelowestlevelsinthehierarchywithsmallsubsetsofprocessorsandascendstothehighestlevelwhichencompassestheentiresystem.Thisschemecentralizesthebalancingprocessatdifferentlevelsofthetreewithincreasingdegreesofknowledgeathigherlevels.'Diffusionschemesarewellknownandarediscussedin[15],[16]1045-9219/93$03.0001993IEEE980IEEFTRANSACTIONSONPARA11ELANDDISTRIBUTEDSYSTEMSVOL4.NO9,SEPTEMBER1993Gradien