A Comparison of Task Pools for Dynamic Load Balanc

AComparisonofTaskPoolsforDynamicLoadBalancingofIrregularAlgorithms∗MatthiasKorchThomasRauberUniversitätBayreuthFakultätfürMathematik,PhysikundInformatikFachgruppeInformatik{matthias.korch,rauber}@uni-bayreuth.deAbstractSinceastaticworkdistributiondoesnotallowforsatisfac-toryspeed-upsofparallelirregularalgorithms,thereisaneedforadynamicdistributionofworkanddatathatcanbeadaptedtotheruntimebehaviorofthealgorithm.Taskpoolsaredatastructureswhichcandistributetasksdynamicallytodifferentprocessorswhereeachtaskspecifiescomputa-tionstobeperformedandprovidesthedataforthesecom-putations.Thispaperdiscussesthecharacteristicsoftask-basedalgorithmsanddescribestheimplementationofse-lectedtypesoftaskpoolsforshared-memorymultiproces-sors.SeveraltaskpoolshavebeenimplementedinCwithPOSIXthreadsandinJava.Thetaskpoolsdifferinthedatastructurestostorethetasks,themechanismtoachieveloadbalance,andthememorymanagerusedtostorethetasks.Runtimeexperimentshavebeenperformedonthreediffer-entshared-memorysystemsusingasyntheticalgorithm,thehierarchicalradiositymethod,andavolumerenderingalgo-rithm.1.IntroductionDesigningparallelalgorithmsforirregularproblemsischal-lengingworkbecauseitisusuallynotpossibletopredicttheamountofworkconnectedtoagivenpartoftheinputdata.Therefore,thereisnogoodstrategyavailabletodetermineastaticworkdistributionthatminimizesthecommunica-tionduringtheexecutionofthealgorithmandleadstoagoodloadbalanceatthesametime.Touseallprocessorsefficiently,irregularalgorithmsmustsupportadynamicas-signmentofcomputationstoprocessors.Onewaytodesignirregularalgorithmsforshared-memorymultiprocessorsistosplitthealgorithmintosev-eraltypesoftaskswhichareusedastheminimumunitofparallelism.Everytaskspecifiesasequenceofoperationstobeperformedandprovidesthedatafortheseoperations.Tasksarestoredinacommondatastructurewhichiscalled∗ThisisapreprintofanarticlepublishedinConcurrencyandCompu-tation:PracticeandExperience,16:1–47.Copyrightc2004JohnWileyandSons,Ltd.taskpool.Atthebeginningofthealgorithm,tasksfortheinputdataarecreatedandstoredinthetaskpool.Then,everyprocessorremovesandexecutestasksfromthepooluntilalltaskshavebeenexecuted.Duringtheexecutionofatask,newtaskscanbecreated.Taskpoolscanbeusedasauniversalapproachtoirregu-larproblems.Buttheuseoftaskpoolsoftenleadstolowerlocalitythanmethodswhichexploitspecialpropertiesoftheproblem.Forexample,methodsperformingiterativestepscanusecostestimatesextractedfromearlierstepstoreadaptthedatadistributionaftereachiteration[36].Parallelalgorithmsthatusetaskpoolscanbedescribedbyanabstractmodel.Usingthismodel,theruntimebehav-iorofsuchalgorithmscanbecharacterizedbytaskgraphs,anditispossibletousetaskgrammarsforthedescriptionofthealgorithmitself.Thus,executingatask-basedalgorithmleadstotheproblemofschedulingadirectedacyclicgraph(DAG)tomultipleprocessorsdynamically.EventhestaticschedulingproblemisNP-hard[4].Thedesignerofataskpoolcanattackthisschedulingproblembyintroducingheuristicmethodsthatreducethelatencyoftheschedulebelowaspecificbound.Anotherpossibilityistoignorethestructureofthetaskgraphanduseasimplegreedyalgorithm.Thismayincreasetheidletimebutallowsforefficientimplementationsofthetaskpoolsoperations.Thispaperfollowsthesecondapproachbymin-imizingthenumberofinstructionsofthetaskpoolopera-tionsandchoosingdatastructuresthatreducecontentiononshareddata.Implementationsoftaskpoolsusuallyusecentralordis-tributedqueuestostoretasks.Ifdistributedqueuesareused,amechanismtotransfertasksbetweenthequeuesshouldberealized,sothattheworkloadcanbebalanced.Ifpartsofthetaskpooldatastructuresaresharedbyseveralproces-sors,synchronizationmustbeusedtoavoidraceconditions.Thispaperdescribessomepossiblewaystoreducethenum-berofsynchronizationoperationsandalsothetimeproces-sorsspendwaitingtoacquirelocks.Sinceallocatingandfreeingobjectsinmainmemoryisexpensive,oneshouldalwaystrytoreducethenumberofsuchsystemcalls.Thiscanbeachievedbyre-usingmemoryblocksorbyallocat-1inglargeblockswhichcanholdseveralobjects.Becausetaskpoolsusedynamicobjectstorepresenttaskinstancesandtypicallylargenumbersoftaskinstanceswithshortex-ecutiontimesareusedtoachieveagooddistributionoftheworkload,savingsystemcallscanimprovetheperformancesignificantly.ThispaperdescribesseveraltypesoftaskpoolswhichhavebeenimplementedinCwithPOSIXthreadsandinJava.Theseimplementationshavebeenevaluatedonthreedifferentshared-memorysystems:aLinuxPC,aSunEn-terprise420RandaSunFire6800.Resultsareshownforasyntheticalgorithmandtworealisticapplications:thera-diosityandthevolrendapplicationfromtheSPLASH-2ap-plicationsuite[46].Thebestresultshavebeenobtainedusingtaskpoolswithdynamictaskstealing.Synchroniza-tionoverheadandwaitingtimesofsuchtaskpoolscanbereducedbyusingprivateandpublicqueues.Therestofthepaperisorganizedasfollows:Section2givesanoverviewoftask-basedalgorithmsanddescribesdifferenttypesoftaskpools.Then,Section3presentsrun-timeexperimentsperformedwithseveraltaskpoolvariants.Section4discussesrelatedwork,andSection5concludesthepaper.2.Task-basedalgorithms2.1.Structureanddescriptionoftask-basedalgorithmsTask-based