A general matrix iterative model for dynamic load

76011645
1 ℃
2020-01-27

整理文档很辛苦，赏杯茶钱您下走！

还剩 ... 页未读，继续阅读 >>

免费阅读已结束，点击下载阅读编辑剩下 ... 页

阅读已结束，您可以下载文档离线阅读编辑

资源描述

AGeneralMatrixIterativeModelforDynamicLoadBalancingyMarkA.FranklinVasudhaGovindanjbf@random.wustl.eduvasu@wuccrc.wustl.eduComputerandCommunicationsResearchCenterCampusBox1115,OneBrookingsDriveWashingtonUniversity,St.Louis,Missouri63130AbstractEectiveloadbalancingalgorithmsarecrucialinfullyrealizingtheperformancepotentialofparallelcomputersystems.Thispaperproposesageneralmatrixiterativemodeltorepresentarangeofdynamicloadbalancingalgorithms.Themodelandassociatedperfor-mancemeasuresareusedtoevaluateandcomparevariousloadbalancingalgorithmsandderiveoptimalalgorithmsandassociatedparametersforagivenapplicationandmultipro-cessorsystem.Themodelisparameterizedtorepresentthreeloadbalancingalgorithms-therandomstrategy,diusionandcompleteredistributionalgorithms.Themodelisvalidatedbycomparingtheresultswithmeasuredperformanceonarealisticworkload.TheparallelN-bodysimulationapplicationusedforthispurposehasanumberofinter-estingpropertiesandisrepresentativeofawideclassofrealisticscienticapplications.Theperformanceofthethreealgorithmsarecomparedandoptimalalgorithmparametersderivedfortheapplication.Therandomstrategyoutperformsboththediusion(12%better)andtheredistribution(30%better)algorithmsanditsperformanceiswithin25%oftheidealloadbalancecase.Generalperformancemodelssuchastheonepresentedinthispapercanbeusedtoguidethealgorithmdesignerinchoosingthebestalgorithmandassociatedparametersforagivenenvironment.Keywords:Dynamicloadbalancing,Performancemodel,Matrixiterativemodel,Par-allelN-bodysimulationySubmittedtoIEEETransactionsonParallelandDistributedSystems.ThisresearchhasbeensponsoredinpartbyfundingfromtheNSFunderGrantCCR-9021041andARPAundercontractDABT-93-C0057.11IntroductionEectiveprocessorandcommunicationresourceutilizationisessentialinfullyrealizingtheperformancepotentialofparallelcomputersystems,andcentraltothisisthedevel-opmentofappropriateloadbalancing(orloadsharing[7])algorithms.Thevariousloadbalancingalgorithmspresentedintheliterature[4,7,13,14]generallyfocusondistribut-ingtheworkloadinsomeequalfashionamongtheavailableprocessors.Inthispaper,wefocusonloadbalancingofcooperatingtasksbelongingtoasingleapplicationrunningonmultipleprocessors[2,8,11,19].Wedevelopasimplebuteectivematrixiterativemodeltorepresentawiderangeofloadbalancingalgorithms.Themodelandassociatedper-formancemeasuresareusedtoquantitativelycomparevariousloadbalancingalgorithms.Foragivenapplicationandmultiprocessorsystem,themodelisusedtochooseasuitablealgorithmandtotailorthealgorithmfor\bestperformance.ThemodelisvalidatedusingaparallelN-bodysimulationimplementationonanetworkofworkstations.Theloadbalancingmodelpresentedinthispaperservesasaneectiveperformanceevaluationtoolinthedesignofecientalgorithmsforparallelcomputingsystems.Fol-lowingarethehighlightsofthemodelandperformanceschemepresentedinthispaper:Thematrixiterativeformulationiscompactandintuitiveandcanbeparameterizedtorepresentarangeofloadbalancingalgorithms.Unlikeothermodelsinliteratureforanalyzingloadbalancingalgorithms,ourmodeliseasilyapplicabletoahetero-geneousprocessorsystems.Weapplythemodeltoaparallelapplicationrunningonaheterogeneousworkstationnetwork.Theperformanceevaluationschemeincorporatesallaspectsofloadbalancing.Theloadbalancingalgorithmisevaluatedtakingintoaccounttheperformancebenetsaswellastheoverhead(intermsofcomputationandcommunicationcosts)ofloadbalancing.Thecharacteristicsoftheparallelapplicationandthecomputingplat-formarealsoincorporatedintotheperformancemodel.Theperformancemeasurederivedthereforereectstheoverallperformanceofthesystem.Themodelisvalidatedbycomparingtheresultswithmeasuredperformanceonarealisticworkload.TheparallelN-bodysimulationapplicationusedforthispurposehasanumberofinterestingpropertiesandisrepresentativeofawideclassofrealisticscienticapplications.Loadbalancingalgorithmscanbebroadlyclassiedintostaticanddynamicstrategies[4,12].Instaticschemes,assignmentoftaskstoprocessorsismadebeforeexecutionanditisxedthroughouttheexecutiontime.Dynamic(orAdaptive)loadbalancingschemesperiodicallyreassigntasksasneededduringexecutiontoachievebalance.Dynamicloadbalancingstrategiescanalsobeclassiedascentralizedordistributedbasedonwhereloadcontrolisexercised.Centralizedloadbalancingalgorithmshavea\masternodewhichallocatestaskstootherprocessorsthusmaintainingabalancedworkload.Indis-tributedalgorithms,eachprocessormakesanindependentloadbalancingdecisionbased2onacombinationofitsownloadandsomesystem-wideloadinformation.Anotherclassi-cationofdynamicschemesrelatestowheretasktransferbetweenprocessorsisinitiated.Insenderinitiatedschemesheavilyloadednodesinitiatetransferoftaskstoothernodes.Inreceiverinitiatedschemes,lightlyloadednodesrequestothernodestosendtasks.Theprincipalfocusofthispaperistheanalysisofdynamic,distributed,sender-initiatedloadbalancingschemes.Themodelpresentedhere,however,canbeextendedtorepresentotherloadbalancingschemes.Therehavebeenseveralstudiesontheperformanceanalysisandmodelingofloadbal-ancingalgorithms[1,5,6,7,13,17].Eageret.al[7]useanalyticqueueingmodelstoco