搜索
ParallelizationofParticleMethodsontheSphere OmerE gecio gluandAshokSrinivasanDepartmentofComputerScienceUniversityofCaliforniaSantaBarbara,CA93106fomer,ashokg@cs.ucsb.eduAbstractWeconsiderdatastructuresandalgorithmsfore cientparallelizationofparticlemethodswhenthedomainisthesurfaceofasphere.Suchapplicationstypicallyarisewhendealingwithdirectionaldata.Weproposeadomaindecompositionschemebasedongeometricpartitioning,thatprovidesdomainssuitablefore cientimplementationofrequisiteoperationsthatareper-formedonthedatainparallel.Thealgorithmhastheadvantageofbeingfastenoughtobeapplieddynamically,andatthesametimeprovidesgoodpartitions,comparableinqualitytothoseproducedbymultilevelgraphpartitioningschemes.1IntroductionParticlemethodsarewidelyusedinseveralapplications[1,5,4,3].Thesetypicallyinvolveasetofparticlesrepresentedaspointsinsomespace,andafunctionthatdescribestheinteractionbetweenpairsofparticles.Foreachparticle,oneindependentlysumstheinteractionbetweenitandallotherparticles,andanewstateforeachparticleisthencomputed.Thisnewstatetypicallyisanewpositionandvelocity,andthecalculationsarerepeatedseveraltimestoobservetheevolutionofthesystem.Thisleadstoanirregularcomputationalprobleminwhichthesetofparticleswhichinteractswithanygivenparticlechangeswithtimeinanunpredictablemanner.Furthermore,inapplicationsinvolvingdirectionaldatasuchascomplex uid owproblems[21,14],thenaturaldomainofrepresentationistheunitsphere.Inaparallelimplementation,particlesareassignedtoprocessorsby rstbreakingthedomainintosubdomains,andthenmappingthesesubdomainstodi erentprocessors.Eachprocessorproceedstocomputetheinteractionsofalltheparticlesinthesystemwiththeparticlesinitssubdomain.Theinteractionswithparticlesthatlieoutsideitssubdomainrequireaprocessortoobtainthestatesofthoseparticlesfromotherprocessors.Wecalltheparticlesinthesubdomainofaprocessorthepointsownedbytheprocessor.Thepointsownedbyagivenprocessorthatareneededbyotherprocessorsaresharedpoints.InmanyapplicationssuchasmoleculardynamicsandSmoothedParticleHydrodynamicsbasedmethods,theinteractingforcesbetweentheparticlesareshortrangeandthee ectofparticlesthatarefartherawaythanacertaincut-o distancecanbeignored[4,3].Inordertofurthermitigatehighcommunicationcosts,oneusuallytriestooverlapcomputationwithcommunication.Hence,processors rstsendtheirshareddatatotheprocessorsthatneedthem,andfollowingthisperformtheirlocalcomputations.Subsequently,theyreceivetheshareddatathey Thistechnicalreportdiscussesparallelizationofparticlemethodsonthesphere.Itconsistsoftwoparts(i)Domaindecomposition,and(ii)datastructurestofacilitatesuchcomputations.The rstpartappearsintheProceedingsoftheThirdInternationalWorkshoponParallelAlgorithmsforIrregularlyStructuredProblems(IRREGULAR’96),heldinSantaBarbara,California,August19-21,1996.Itisreproducedhereforcompleteness.11.DomainDecomposition.2.Mapdomainstoprocessors.3.Startloop(a)Determinesharedpoints.(b)Sendsharedpointstoprocessorsthatneedthem.(c)Computeusinginteriordata.(d)Receiveshareddataneededfromotherprocessors.(e)Computeusingreceiveddataandupdatestate.(f)Updatedomaindata.EndloopFigure1:Outlineofageneralparallelparticlemethodcalculation.themselvesneedandperformtheirremainingcomputations,andupdatethestatesofthepointsintheirsubdomain.Someupdatingofthedomainscanalsobedoneatthisstage.Usuallyafulldomaindecompositionisnotperformedattheendofeachiterationsincethecostofthedecompositioncanbeprohibitive.ThebasicschemeofsuchcalculationsisoutlinedinFigure1.E cientparallelizationrequiresthatwechoosesubdomainsforeachprocessorinsuchawaythatonlyfewparticlesoutsidethesubdomaininteractwithparticleswithinthesubdomain.Itisalsonecessarytoe cientlydeterminethesetofsharedparticlesateachprocessor.Animportantaspectofthecomputationsistoperforme ectivedynamicrangesearchingsothatonecomputesinteractionswithonlythoseparticlesthatarewithinthecut-o distanceoftheshortrangeinteractions.Theoutlineofthispaperisasfollows.Sect.2describesgraph-theoreticalandgeometricdo-maindecompositionstrategiesastheyapplytoparticlemethodsonthesphere.ThealgorithmwepresentinSect.3isessentiallyageometricpartitioningbasedonOrthogonalRecursiveBisection[2].However,wetakeadvantageofthegeometryofthespheretoproducepartitionswithqual-itycomparabletosophisticatedmethodssuchasspectralpartitioning.ExperimentalresultsandcomparisonswithotherpopularschemesavailableinChaco,version2.0[9]andMetis,version2.0.3[11]arepresentedinSect.4.Theseexperimentsshowthatouralgorithmisanorderofmagnitudefasterthaneventherelativelyfastinertialmethodforlargeproblemsizes,anddemonstratethehighqualityofthepartitionsobtained.InSection5,wedescribevarioussetsandtheoperationsthatareperformedonthem,whichabstracttheessentialfeaturesofthecomputationsinvolved,andalsodescribeourimplementationstrategy.Weshowhowourdomaindecompositionstrategyfacilitatese cientimplementationofotheroperationsonthedata.ConclusionsaregiveninSect.6.2DomainDecompositionDomaindecompositionhasbeenwidelystudied[9,10,11,12,13]andseveraltypesofmethodsforitssolutionhavebeenproposed:graph-theoreticalandg