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
0.950.90.850.8
o
itaR0.75 hcti0.7wS tx0.65etno0.6C0.550.50.45D=00.4
D=10000
D=1001
2
4
8
16
32
64
Number of LPs Per Processor
Figure4.Theratioofthenumberofcontextswitcheswithincreasingnumberoflogicalprocessesperprocessor.
contextswitches.Theoverheadisproportionaltothenum-berofconnections.Also,notethatthecrossingpointshiftstowardsmoreLPsastheconnectivityincreases.Second,withincreasingworkload,thelock-freealgorithmoutper-formsitscounterpartingreaterscalewhenthenumberofLPsissmall.Thisisre ectedbysteepercurvesastheeventdensityislarger.
Figure4showstheratiosofcontextswitchesaswe xedtheconnectionradiusat6.Thecurvescoincidewiththeex-ecutiontimeratiosandshowlargersavingsforthelock-freealgorithmwhenthenumberofLPsislow.Also,itappearsthatthelargertheeventdensity,thesmallerthenumberofcontextswitchesforthelock-freealgorithmcomparedtoCCT.Asthesavingsincontextswitchesforthelock-freealgorithmdecreasesasweincreaseLPpopulation,theover-headfromthecomplexityofextrabookkeepingtoavoidun-necessarycontextswitchesinthelock-freealgorithmcan-notbefullycompensatedanymore.WithmoreLPsreadyforexecutionatanytimeonaprocessor,therewillbeapro-longedqueueingtimeforallLPsonaverage.Thismakesitmorelikelythattheremainingcriticalchannelswillbeupdatedandthereforetheunnecessarycontextswitchwillbeavoided.Thatis,eventhoughCCTdoesnottrytoavoidunnecessarycontextswitches,multiprogrammingcertainlyhelpsitavoidtheissuewithincreasingnumberofprocesses.Thisfurtherjusti estheclaimofCCT’sauthorstosupportsimulationoflow-granularitynetworkmodels,whichusu-allyconsistoflargenumberoflogicalprocesses.
7.Conclusion
Inthispaper,wedescribedanovellock-freealgorithmforschedulinglogicalprocessesinconservativeparalleldiscrete-eventsimulation.Weconsiderouralgorithmasrobustwhencomparedwiththealgorithmusinglocks.InmodelswiththenumberofLPscomparativetoavailableprocessors,thealgorithmshowsmuchbetterperformance
anddoesnotsufferfromthedefectofthosealgorithmsus-inglocks,whereslowprocessmayblockotherprocessesandformabottleneckthatdegradestheperformanceoftheentiresystem.Thebene t,though,comeswithacost.Theaddedcomplexityofthelock-freealgorithmintroducedsomeoverheadfrommanipulatingvariablesusedforbook-keeping.Theoverhead,though,hasonlymodesteffectontheoverallperformanceofthealgorithmespeciallywhentheworkloadbecomesnon-trivial.
References
[1]K.M.ChandyandJ.Misra.Distributedsimulation:acase
studyindesignandveri cationofdistributedprograms.IEEETransactionsonSoftwareEngineering,SE-5(5):440–52,1979.
[2]R.M.Fujimoto.Paralleldiscreteeventsimulation.Commu-nicationsoftheACM,33(10):30–53,1990.
[3]M.Herlihy.Wait-freesynchronization.ACMTransactions
onProgrammingLanguagesandSystems,13(1):124–149,1991.
[4]D.JeffersonandP.Reiher.Supercriticalspeedup(discrete
eventsimulation).Proceedingsofthe24thAnnualSimula-tionSymposium,pages159–68,1991.
[5]D.R.Jefferson.Virtualtime.ACMTransactionsonPro-grammingLanguagesandSystems,7(3):404–25,1985.[6]J.Liu,D.Nicol,B.Premore,andA.Poplawski.Perfor-mancepredictionofaparallelsimulator.Proceedingsofthe13thWorkshoponParallelandDistributedSimulation,pages156–64,1999.
[7]X.Liu,D.M.Nicol,andK.Tan.Lock-freeschedul-ingoflogicalprocessesinparallelsimulation.TechnicalReportTR2001-385,ComputerScienceDepartment,Dart-mouthCollege,2001.
[8]J.Mellor-CrummeyandM.Scott.Algorithmsforscalable
synchronizationonshared-memorymultiprocessors.ACMTransactionsonComputerSystems,9(1):21–65,1991.
[9]E.NaroskaandU.Schwiegelshohn.Anewscheduling
methodforparalleldiscrete-eventsimulation.ProceedingsofEuropeanConferenceonParallelProcessingEURO-PAR’96,pages582–93vol.2,1996.
[10]D.Nicol,J.Liu,andJ.Cowie.Safetimestampsandlarge-scalemodeling.Proceedings14thWorkshoponParallelandDistributedSimulation(PADS2000),pages71–8,2000.[11]D.M.Nicol.Principlesofconservativeparallelsimula-tion.Proceedingsof1996WinterSimulationConferenceProceedings,pages128–35,1996.
[12]H.Y.Song,R.A.Meyer,andR.Bagrodia.Anempirical
studyofconservativescheduling.Proceedings14thWork-shoponParallelandDistributedSimulation(PADS2000),pages165–72,2000.
[13]J.Valois.Lock-freedatastructures.Ph.DThesis,Rensselaer
PolytechnicInstitute,May1995.
[14]Z.Xiao,B.Unger,R.Simmonds,andJ.Cleary.Scheduling
criticalchannelsinconservativeparalleldiscreteeventsim-ulation.Proceedingsofthe13thWorkshoponParallelandDistributedSimulation,pages20–8,1999.
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...
热门文档