ACHIEVING SCALABLE PARALLEL MOLECULAR DYNAMICS USING DYNAMIC(5)

Theseoptimizationsandothersreduceworkinanon-uniformmanner,whichisnotad-equatelymodeledinsection3.Aswithanyparallelalgorithm,itisdesirabletoperformnomoretotalworkthananoptimizedsequentialversion,soaparallelismstrategymustbeimplementedthatconsiderstheoptimizationsusedinoursimulator.Wedescribesuchaneffortinthenextsection.

4.3.ADynamicDomainDecompositionStrategy.Oneinterestingresultfromourex-periencewiththeKSRwastheconsistencyoftheimbalanceintheloadoveralongpe-riod.Typically,oneprocessorhadaheavierloadthantheothers,anditwasthisprocessor’sarrivalatthesynchronizationpointthatdeterminedtheoverallparallelperformance.Thestate-vs.-timechartsofexecutionontheKSR-1convincedusthatanadaptivedecomposi-tionwasnecessary,andthatperformanceimprovementscouldbemadeifthecomputationalloadsamongtheprocessorsweremorebalanced.

Fortunately,high-performancecomputersoftenhavebuilt-insupporttogivedetailedperformancequantitiesaboutaprogram.Forinstance,theCrayVectorProcessorsyieldanexactcountofhowmanyinstructions( oating-point,integer,andmisc)wereexecutedonbehalfofaprogram.TheKSR-1hadasetofbuilt-inregistersthatindicatednotonlyclockcyclecounts,butmemoryoperationsaswell(cachehits,localmemoryhits,andcy-clestallswaitingforremoteshared-memoryaccess).Thedataintheseregistersprovideacost-freemeasureoftheworkperformedbyaprogramonaprocessor-by-processorbasis,andassuch,areusefulindetermininganequitableloadbalance.

ToobtainanevenlybalanceddecompositioninourMDsimulations,weusepastper-formanceasapredictionoffutureworkrequirements.Onereasonthisisviableisthatthe

ABSTRACT. To achieve scalable parallel performance in Molecular Dynamics Simulations, we have modeled and implemented several dynamic spatial domain decomposition algorithms. The modeling is based upon the Bulk Synchronous Parallel architecture model (BSP)

16NYLAND,PRINS,YUN,HERMANS,KUM,ANDWANG

systemofmolecules,whileundergoingsomemotion,isnotmovingallthatmuch.Thecom-binationofthisaspectofMDwiththeaccurateperformanceinformationavailableleadstodynamicspatialdecompositionsthatprovideimprovedperformanceandarequicktocom-pute.

Thefollowingde nitionsareneededtodescribeourwork-baseddecompositionstrategy.

Thedynamicswork,,performedbyeachprocessorsincethelastload-balancingoperation(doesnotincludeinstructionsusedforcommunicationandsynchroniza-tion)

Thetotalwork,,performedbyallprocessorssincethelastload-balancingoperation

Theideal(average)work,

workoneveryprocessor.Thisisadif cultproblemtosolveconsideringthethree-dimensionalnatureof

thesimulation

space.

average

work

per

atom

bo b1 b2 b3 b4

Previous

Future

bo b1 b2 b3 b4

FIGURE8.Unbalancedworkloadsonasetofprocessors.Ifthebound-

ariesaremovedasshown,thentheworkwillbemoreinbalance.

Instead,ifwechangethefocustotheboundariesinsteadofthevolumes,andplacetheboundariesonedimensionatatime(asisdoneintheORBdecomposition),thenastraight-forwardimplementationcanbedeveloped.Figure8showsasingledimensionsplit

boundaries,ofwhichonlyaremovable(andareintosubdivisions,with

naturallyatthebeginningandendofthespacebeingdivided).InSigma,we rstdividethe

balancedparts,theneachofthoseintoparts,andspacealongthe-dimensioninto

nally,eachofthe“shafts”intoparts,usingthefollowingdescription.

Considertherepartitioninginasingledimensionasshownin gure8.Alongthe-axis,theregionboundariesseparateatomsbasedontheirposition(atomsaresortedby-position).Theheightofapartitionrepresentstheaverageworkperatominapartition,whichasstatedearlier,isnotconstantduetodensitychangesinthedataandoptimizations

ABSTRACT. To achieve scalable parallel performance in Molecular Dynamics Simulations, we have modeled and implemented several dynamic spatial domain decomposition algorithms. The modeling is based upon the Bulk Synchronous Parallel architecture model (BSP)

ACHIEVINGSCALABLEPARALLELMD17

FIGURE9.Thisgraphshowstwoviewsoftheadaptivedecomposition

workingover800timeberoftracesshowthecesssincetheatomgroupsis700thebasedontheworking).Ifaalargernumbershowsthe600

ingatomcountasadaptivethan5%,vs.theAdaptive Spatial Decompositionover TimeNumber of Atom Groupson Each Processor40%30%20%

500Percentage of timespent waitingthathavebeenintroduced.theareasis.Thegoalis400byarea)isascloseto10%

0%

0123456789

Rebalancing Step

ABSTRACT. To achieve scalable parallel performance in Molecular Dynamics Simulations, we have modeled and implemented several dynamic spatial domain decomposition algorithms. The modeling is based upon the Bulk Synchronous Parallel architecture model (BSP)

18NYLAND,PRINS,YUN,HERMANS,KUM,ANDWANG

4.5.Results.Thedevelopmentofthisdecompositionstrategytookplacein1994onaKSR-1computer.Thishardwarehadexcellentsupportformeasuringworkoneachprocessorinacost-freemanner,inthattherewasaregisteravailablethatcontainedanelapsedcyclecountforeachthread.ThecomputationthatcountedasworkwasallcomputationthatoccurredaspartofMD(wedidnotwanttoincludetheextra“work”createdbyspin-locksinthesynchronizationprimitives).

Subsequently,wehavemovedtothemorerecentparallelarchitecturesbuiltbySGI,includingthePowerChallengeandtheOrigin2000,bothrepresentingasingle-address,shared-memoryparallelcomputingparadigm.AcquiringperformancedataontheSGIisnotasexactasontheKSR,butisstillpossibleusingthegettimeofday()systemcall(indedicatedexecutionmode).

Parallel Performance of Sigma

100Simulation Steps per Second10lated(at12concerntothe4scientistsusing8the2010simulator.Weisindeed1themetricofmostrantestsusing

to,,,decompositionswherewesetProcessors,,,and.Thereareseveralconclusionstobedrawnfromtheperformancegraph,themostimpor-

tantofwhichisthesteadylinearimprovementinperformancewithincreasingprocessors.Thesimilarslopesoftheperformancetrajectoriesforthedifferentdatasetsshowsthattheperformancescalessimilarlyforeachdataset.Theaverage …… 此处隐藏：6162字，全部文档内容请下载后查看。喜欢就下载吧 ……