With fixed lookahead information in a simulation model, the overhead of asynchronous conservative parallel simulation lies in the mechanism used for propagating time updates in order for logical processes to safely advance their local simulation clocks. St
Finally,section7givesourconclusions.
2.Model
Theparalleldiscreteeventsimulationmodeliscom-posedofasetoflogicalprocesses(i.e.LPs)connectedbyunidirectionalchannelsthroughwhichmessagesaresentfromsenderLPstoreceiverLPs.Weassumethatthetopol-ogyofthegraphdoesnotchangeduringsimulation.Suchamodelcanberepresentedasadirectedgraph,wherethenodesinthegraphrepresenttheLPsandtheedgesrepre-sentchannelsthatconnectthecorrespondingLPs.LettibethelocalsimulationclockofLPi.De neδi,j≥0tobethedelayassociatedwiththechannelfromLPitoLPj.Notethatδi,jisasimpleformoflookahead.TheeventsentfromLPitoLPjattimeτwillshowupattimeτ+δi,jinLPj’sevent-list.Toavoiddeadlock,weassumethatthesumofthedelaysofedgesalonganycycleinthegraphisstrictlylargerthanzero.ForLPi,letPRED(i)bethesetofprede-cessorLPsofLPiandletSUCC(i)bethesetofsuccessorLPsofLPi.
LetTi,jbethechanneltimefromLPitoLPj.Thechan-neltimemaybeconstantlyupdatedbythesourceLPofthechannel(i.e.LPi)wheneverthelocalsimulationclockofLPiisupdated:Ti,j=ti+δi,j.Itisunderstoodthatchanneltimesmaynotbeupdatedinstantaneously.There-fore,atanytimeduringsimulation,weareonlysurethatTi,j≤ti+δi,j.LetHibethesafetimeofLPi,de nedasthelatestsimulationtimeuptowhicheventsinLPicanbesafelyprocessedwithoutintroducingtheriskofcausal-ityerrors.ItisguaranteedthatnoeventswithtimestampsmallerthanHiwilllaterarriveatLPi.Theoretically,thesafetimeofLPicanbederivedatanytimefromaglobalsnapshotofthesimulation:Hi=minj∈PRED(i){tj+δj,i},wheretjisthecurrentsimulationtimeofLPjatthesnap-shot.Inouralgorithm,LPionlylooksatthetimesofits
incomingchannels.Wede neH′
i=minj∈PRED(i){Tj,i}
andsaythatLPiisreadyifandonlyifti<H′
andtooexpensivetoobtaini.Inprac-tice,itisunnecessaryasnap-shotinordertocomputethesafetime.Instead,thealgo-rithmonlyneedsalowerboundofthetruesafetime,whichwecalleventexecutionhorizonandisdenotedashi.ItisobtainedbytraversingtheincomingchannelsofLPiandstoringtheminimumofcurrentchanneltimeTj,iinhi.ItisunderstoodthatthepredecessorLPjmaynotupdateTj,ipromptly.However,thiswillonlycauseasmallerhitobecalculated,sincewearesurethatTj,iisnon-decreasing.AnLPschedulingalgorithmisdescribedinformallyasfollows.WhenareadyLPiisdispatchedforexecution,thehithatitcomputesissuretobegreaterthanitslocalsim-ulationclockti.AlleventswithinLPiwithtimestampssmallerthanhiarethenprocessedintimestamporder.Dur-ingtheprocess,neweventsmaybegenerated.Eventslocal
toLPiareinserteddirectlyintotheLP’sevent-list.ExternaleventsarequeuedupintheoutputchannelsandwillbelaterwithdrawnbythedestinationLPs.OnceallsafeeventsinLPihavebeenexecuted,LPimustbesuspendedfromexe-cution.ItisobviousthatthesafetimeofLPiisdeterminedbythepredecessorLPwiththesmallestchanneltime.ThesafetimeofLPiwillnotincreaseunlessthepredecessorLPwithsmallestchanneltimeadvancesitslocalsimulationclock.Borrowingtermsfromtheliterature,wecallthatLPwithsmallestchanneltimethecriticalparentofLPi.ThechannelbetweenLPianditscriticalparentiscalledcriticalchannel.Notethattherecouldbemorethanonecriticalpar-entofanLPatthesametime;theyallpossessthesmallestchanneltime.ToadvancethesafetimeofanLP,allitscrit-icalparentsmustadvancetheirsimulationclocks.WhenanLPissuspendedfromfurtherexecution,thedispatchershouldbeabletodispatchanotherreadyLPforexecution.Wecallsuchtransitionacontextswitch.TheexecutionofanLPbetweentwoconsecutivecontextswitchesiscalledanexecutionsessionorasessioninshort.ThesimulationendswhenthetimestampsofallLPsreachtheprede nedsimu-lationendtimeHT>0orsomeotherterminationconditionissatis ed.
3.RelatedWork
Itiswell-knownthatconservativeparallelsimulationcannotbeatthecriticalpath[4].Tomakethingsworse,itisconsideredasimpracticaltoidentifyandthereforescheduleeventsonthecriticalpathasitunfoldsdynamically.How-ever,manyconservativeschedulingalgorithmstakeadvan-tageofthenotionandstrivetoscheduleeventsthataremorelikelytobeonthecriticalpath.
Steppingupatahigherlevel,schedulingcriticaleventscanbeapproximatedasschedulingcriticalLPs1.WhenareadyLPisscheduledforexecution,thesessioncontinuesuntilthelocalsimulationclockreachesitssafetime.TheLPcannotcontinueuntilitscriticalparentsadvancethechanneltimes.TheproblemthentranslatesintoanLPschedulingpolicythatcanpreferentiallyscheduleLPsthatcontaincrit-icalevents.NaroskaandSchwiegelshohn’sschedulingal-gorithm[9]givesprioritiestologicalprocessesthatdirectlyin uencecomputationsonotherprocessors.Thecommuni-cationlatencyamongprocessorswithdistributedmemoryismorelikelytoputeventssentbetweenthemonthecriti-calpath.AnempiricalperformancestudyofalternativeLP
Lock-Free Reference Coun... 暂无评价 10页 免费 Lock-free scheduling of ... 暂无评价 10页 免费 An efficient parallel an... 暂无评价 15页 免费 An...
Lock-free scheduling of ... 暂无评价 10页 免费 Scheduling+Parallel+Proc.... Scheduling Dynamically Spawned Processes in MPI-2 M? rcia C. Cera1 , ...
No livelocks or theorical scheduling issues Usually cheaper and scale better ...? Solutions July 31, 2013 13 / 37 Shattering Illusions in Lock-Free ...
A framework for implementing objects and scheduling tasks in lock-free real...Formally, if several processes attempt to access a that are implemented in...
Network f. Parallel g. Distributed h. Clustered ...processes using the following scheduling algorithms:...physical addresses for the following logical ...
A framework for implementing objects and scheduling tasks in lock-free real...Formally, if several processes attempt to access a that are implemented in...
热门文档