On Critical Path Analysis of Parallel Discrete Eve

OnCriticalPathAnalysisofParallelDiscreteEventSimulationsSudhirSrinivasan,PaulF.Reynolds,Jr.TechnicalReportNo.CS-93-29May25,1993OnCriticalPathAnalysisofParallelDiscreteEventSimulationsSudhirSrinivasanPaulF.Reynolds,Jr.ComputerScienceReportNo.TR-93-29May25,1993OnCriticalPathAnalysisofParallelDiscreteEventSimulationsABSTRACTSeveralprotocolshavebeenproposedtosynchronizethelogicalprocesses(LP’s)ofaparalleldiscreteeventsimulation(PDES).Whilemostprotocolshavebeenknowntoperformwellundercertainconditions,thegeneralobservationhasbeenthattheperformanceofprotocolsissensitivetotheapplicationbeingsimulated,sometimeseventoaparticularinstanceofit.Inthistechnicalnote,weaddresstheissueofdeterminingalowerboundonthecompletiontimeofaparticularsimulationrunusingcriticalpathanalysis.Twostudieshavebeenconductedpreviouslyonthissubject.Whilethesestudieshaveprovidedsomeusefulinsightsintotheperformanceofprotocols,certainissueshaveremainedunexplored.Weexaminetheseissuesandpresentfourenhancementstotheearlierresultsoneofwhichistoindicateaflawinoneofthepreviousstudies.Thetwomaincontributionsofthisworkaretopresent:(i)atriviallowerboundforallPDES’swhichcontradictsaresultfromoneofthepreviousstudiesand,(ii)areasonablelowerboundonthecompletiontimeforallPDES’s.CategoriesandSubjectDescriptors:D.1.3[ProgrammingTechniques]:ConcurrentProgramming-parallelprogramming;D.4.1[OperatingSystems]:ProcessManagement-synchronization;D.4.4[OperatingSystems]:CommunicationsManagement-messagesending;D.4.7[OperatingSystems]OrganizationandDesign-distributedsystems;D.4.8[OperatingSystems]Performance-Operationalanalysis;I.6.8[SimulationandModeling]TypesofSimulation-parallelanddiscreteeventGeneralTerms:PerformanceAdditionalKeyWordsandPhrases:Criticalpath,Aggressiveprotocols,Super-criticalspeed.OnCriticalPathAnalysisofParallelDiscreteEventSimulations11IntroductionForoverfifteenyears,researchershaveattemptedtospeeduptheexecutionofdiscreteeventsimulationsusingmultiprocessors.Therehavebeensomeencouragingadvancesbutnocompletesolutionstotheproblemasyet.Thecommunityseekssimulationmechanismswhichcanbeprovedtoworkefficientlywithawiderangeofapplicationsandarchitectures.Tothisend,twopreviouspapers[BeJe85(1)andJeRe91(7)]havestudiedtheproblemofboundingthecompletiontimeofsimulationsfrombelowinordertoobtainanideaaboutthebestpossiblecompletiontime.Inthisnote,wecarrythisworkfurtherandinfact,completeitbyderivingareasonablelowerboundforallPDES’s.Inthisprocess,weenhancetheresultsof[BeJe85(1)andJeRe91(7)]andpointoutaflawin[JeRe91(7)].Weassumefamiliaritywiththecommonapproachtoperformingparalleldiscreteeventsimulation,namelythepartitioningofadiscreteeventsimulationintocomponentsgenerallycalledlogicalprocesses(LP’s).EachoftheLP’sisadiscreteeventsimulationbyitselfexceptthatitmustensurethatitexecutesevents,whetherinternallygeneratedorreceivedfromotherLP’s,soasnottoviolatecausalityconstraints.EnsuringtheobservanceofcausalityconstraintsistypicallylefttoaPDESprotocol.Protocoldesign(andrecentlyanalysis)hasbeenthefocusofmostoftheresearchinPDES.Themainreasonforthisisthatnoneoftheprotocolsdevisedthusfarhavebeenshowntoperformefficientlyundermanydifferentconditions.Agoodsurveyofprotocolsisfoundin[Fuji90(4)].Mostoftheseprotocolsfallintotwoclasses:conservativeandoptimistic.Underaconservativeprotocol,anLPdoesnotproceedwiththeexecutionofitsnexteventuntilitcanascertainthatitwillneverreceiveamessagewithalowertimestamplateron.Thusthesimulationwillbeaccurate.Optimisticprotocols,ontheotherhand,relyonspeculativeoraggressivecomputation;i.e.underthese,LP’sexecuteeventsregardlessofthepossibilityofreceivingmessagesintheirlogicalpast(calledstragglers).SinceanLPmayreceivestragglers,theseprotocolsincludethecapabilityofcheckpointing(orstatesaving)androllingback.Bothconservativeandoptimisticprotocolshavebeenshowntoperformwellundercertainconditionsandbadlyunderothers.In[Reyn88(11)],itwaspointedoutthatthesetwoclassesrepresentpointsonaspectrumofpossibilitiesforprotocols.Inthispaper,wewillusetheterminologydefinedtherein.Accordingtothisterminology,conservativeprotocolsarenon-aggressive,accurateandwithoutriskwhileoptimisticprotocolsareaggressive,accurateandwithrisk.Weuse“conservative”and“non-aggressive”interchangeably.Itisimportanttonotethatoptimisticprotocolsformasubclassofaggressiveprotocols(thosewhichallowLP’stoexecuteeventswithouttheguaranteeoffreedomfromcausalityerrors).Wedifferentiatebetween“aggressive”and“optimistic”sincesomeoftheargumentsapplytothelarger,moregeneralclassofaggressiveprotocols.2Optimality:CriticalPathanalysisWiththelackofaconsistentlyefficientPDESprotocol,anaturalquestiontoaskis“Whatisthebestwecando?”Thatis,givenaparticularsimulationrun,whatisthesmallestamountofrealtimerequiredtoexecutethatparticularsimulationrun?Ofcourse,wemustalsoask“Doessuchaboundexist?”Knowingtheanswerstothesequestions,wemaystrivetodevelopprotocolswhichcanbeshowntoachieveoratleastapproachtheabovelowerbound(ifitexists).BerryandJeffersonfirststudiedthesequestionsin[BeJe85(1)].Theyrecognizedthatadiscreteeventsimulationcanbedescribedbyanacyclicd