PARALLEL SIMULATION CSCI 8220
Popular in Course
Popular in ComputerScienence
This 11 page Class Notes was uploaded by Ulises Graham Jr. on Saturday September 12, 2015. The Class Notes belongs to CSCI 8220 at University of Georgia taught by Staff in Fall. Since its upload, it has received 17 views. For similar materials see /class/202314/csci-8220-university-of-georgia in ComputerScienence at University of Georgia.
Reviews for PARALLEL SIMULATION
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 09/12/15
CSCI 8220 Silnulation amp Modeling PDES Time Warp Mechanism State Saving and Simultaneous Events Nan Hipinelle uGA Copy State Save pmcessed event unpiocessed event D sn apshol oi LP stale Straggle Message inpuroueue Y ir queue resinre slate Variabieg forward execuliuri slarlirig Wilh R e lime stamp 18 even o Checkpoint all mo able state variables of the LP prior to processing each event 0 Rollback copy check pointed state to LP state variables Infrequent State Saving o Checkpoint LP periodically eg every Nth event Outline 0 State Saving Techniques Copy State Saving Infrequent State Saving Incremental State Saving Reverse Computation o Simultaneous Events Nan Hipinelle uGA Copy State Saving Drawbacks o FonNard execution slowed by checkpointing gtgt Must state save even if no rollbacks occ gtgt Inef cient if most of the state variables are not modi ed by each event 0 Consumes large amount of memory Copy state saving is only practical for LPs that do not have a large state vector Largely transparent to the simulation appli need locations of LP state variables ion only mnaHWinelle UBA Infrequent State Saving Example I Rollback to timeT May not have saved state at timeT n Execute forward coast forwardquot to time T F 39iiw mini aw in iiiiiiiuiiiii oiiback Roiibackto lastsaved state gt Coastfoivvard o Coastfonivar se pha gtgt Only needed to recreate state of LP at simulation time T gtgt Coast forward execution identical to the original execmion gtgt Must turn oftquot message sends during coast fonlvard or else 7 rollbacktoT could cause newmess es w htlmestamp lt1 and roll backs to times earliert an 7 could ieadm rollbacks eamerthan cvr 3 Pull back 0 Simualiun lime 72 Hesmre si re n In the prior 10 pmcessiiig iirne slamp 72 even send enliemessage wrin iirne sismn 24 input Queue eveni iiSl processed event ii up Wen unprocessed event Ci saved state Ulilptil o 9 antiemessa e aiitirii ies agesi I g 2 send sniirnesssge i sirsggier message causes rollback 4 Baas inrwsrd Pepmcess eveni wrin lime sisrnn 12 Hepmcess eveni wrin lime Siamp 21 dun i resend lime slamp 24 messa ge 0 Process sirsggier cnnnnue nnirnsi eveni nrncessing Infrequent State Saving Pros and Cons o Reduces time required for state saving o Reduces memory requirements 0 Increases time required to roll back LP more time to recreate state 0 Increases complexity of Time Warp executive o Largely transparent to the simulation application only need locations of LP state variables and frequency parameter Nun meme use Incremental State Save processed event Straggle Message I E 2 3 l sri apshol oi LP stale inpumueue 4 u Illwiiw x n y n z n LP Slate Variables xsg xl x4 2 Are slate Resume imam execulimi Starling wilh l lme Slamp 18 eueni 0 Before modifying a state variable save current version in state queue o Rollback Scan state queue from back restoring old values Specifying what to Checkpoint Incremental State Saving 0 Only state save variables modified by an event Generate change logquot with each event indicating previous value of state variable before it was modi ed 0 Rollback Scan change log in reverse order restoring old values of state variables Nun meme use Incremental State Saving 0 Must log addresses of modi ed variables in addition to state More ef cient than copy state save if most state variables are not modi ed by each event Can be used in addition to copy state save Implementation gtgt Manual insertion of state save pri itives gtgt Compiler Support corrpiler inserts checkpoint primitives gtgt Executable editing modify executable to insert chec point prirrl39tives gtgt Overload assignment operator mnaHWmelle use Approaches to Checkpointing Copy State Saving 0 Transparent to the application program for any frequency no explicit action need to be taken once the Time Warp executive now the location of the state Incremental State Saving 0 Manual insertion of state save primitives o Compiler Support compilerpreprocessor inserts checkpoint primitives cost 0 Executable edi modify executable to insert checkpoint p es not po able 0 Overload assignment operator um meme use Tech nique Advantage Disadvantage Manual Easy to implement Tedious an error prone executive Compilerpre Portable Cost to develop and processor maintain Execumme Editing independent source Not eas39ly pmed t code not needed new architectures Restricted to languages allowing Overloading EasY to Implement overioading assignment um meme use Reverse Computation 0 Rather than state save recompute prior state For each event computation need inverse com utation Instrument fonNard execution to enable reverse execution 0 Advantages Reduce overhead in fonNard computation path Reduce memory requirements 0 Disadvantages Tedious to do by hand requires automation Nun Mme um Outline RC Example ATM Multiplexer Original N m glen lt w 1 lm ddayslalul 3915 1 on cell arrival 0 Reverse 5ft glen gt42 a 1 b 1 515quot agnzsmlml e 11 I 11ng Issues 0 State Saving Techniques Copy State Saving Infrequent State Saving Incremental State Saving Reverse Computation o Slmultaneous Events Wqu m Zero Lookahead and Simultaneous Events Time Warp Do simultaneous event cause rollback o A possible rule If an LP processes an event at simulation time T and then receive a vent with time starrp T roll back the event that has already been process precessee event unpreeesseu event If an EVEN can ml back eyees may umur mm mm um 0 Zero Iookahead gtgt n P has zero lookahead if it can schedule an event with time tarrp al to the current simulation time of the o Simultaneous events gtgt Events containing the same time stamp in what order should they be processed o Repeatability gtgt An execution mechanism eg Time Warp is repeatable if repeated executions produce exactlythe same results n Often a requireme t gtgt Simpli es debugging Wqu m Approach 1 o Prevent UnEnding Rollback Cycles Straggler does not roll back already processed events with the same time stamp What are problems with this approach mm mm um Approach 2 Wide Virtual Time WV T Approach Prevent un39Enfi39ng ROHPaCK CyCIes39 D39sallow 0 Application uses time value eld to indicate time stragglers rolling back Its scheduling when the event occursquot dependent events or 39quotd39VeCtSChedUImg 0 Tie breaking eld used to order simultaneous events depended events events with same time value Time stamp tie breaking elds 0 Tie breaking eld can be viewed as low precision bits of time stamp 0 Question How or what should the bits represent Nun H melle MBA Nun H melle MBA An Approach Using WVT WVT Example Time stamp E Avoid rollback cycles despite zero lookahead events using age processed event 0 Avoid rollback cycles Age eld to order scheduling dependent lookahead Lp2 events unprocessed event Nonzero lookahead events Age Zero lookahead events Age Current Age 1 No Rollback LP1 gt Wqu m A mniHWmelle m An Approach Using WVT 0 Question Can there be two or more events Time stamp time value lp omy age LP ID 56 containing the same time stamp and age scheduled by the same LP Why or why not 0 Application specific ordering of events Application specific priority eld Constraint on zero lookahead events 0 Avoid rollback cycles Age eld to order dependent lookahead events Nonzero lookahead events Age 1 Zero lookahead events Age Current Age 1 0 Repeatable execution ID field identifying LP that scheduled the event Sequence number indicating of events scheduled um H melle MBA A W H melle MBA CSCI 8220 Parallel and Distributed Simulation PDES Distributed Virtual Environments Static Data Distribution mower ls Outline o Fundamental concepts Name space Description expressions Interest expressions 0 Static Data Distribution HLA Declaration Management Classbased ltering mm W Background Communication Primitives 0 Basic question When a simulator generates information eg state updates that may be of interest to other simulators who should receive the e 0 Example moving vehicles in a virtual environment e esenus upuau a on gtgt Each vehicle that can see the moving vehicle should receive a message Wu su mu u receive the message e um distribution ls essentially a message routing problem mower re o Unicast One sender message received by one destination 0 Broadcast One sender message received by all destinations o Multicast One sender message received by multiple but not necessarily all destinations Operations analagous to newsgroups 7 Join group 7 Leave group 7 Send message to group can be implemented by unicast or network multicast Best effort vs reliable multicast mm m Data Distribution in SIMNET and DIS Data Distribution 0 Question Who receives each message that is sent 0 Approach r deleting unneeded messages 0 Problem quotnering ON2 messages with N federates can use large amount of m unication bandwidth 0 Time spent receiving and ltering unwanted message becomes a bottleneck mm ls Goal route data produced by one simulator to those simulators that are interested in receiving it and ideally not to simulators that are not interested in receiving it This implies there is S me way for a simulator to specify what data it is interested in receiving interest expressions 0 Some way to describe the data that is produced description expressions 0 A common language vocabulary to specify description and interest expressions name space mm ls Page ltgt Example Analogy Internet Newsgroups interestexpressions 0 Description expression 39m me ested 39m 5 5an Name of newsgroup to which the message is posted the position of alrcxaft the position oftanks 0 Interest expression Set of newsgroups a user is subscribed to gtgt Subscribe to ugacscicasscsci8220quot and ugacscicasscsci8220quot er gtgt Class announcements postedto ugacscicasscsci8220quot 61 description 3 Morales i expression 7 r 7 I position update for a tank obieq 0 Name space Set of all newsgroup names Name Ipaoe in ii n iaiil iii mmit tax 7 en Mi e tax 5 Name Space Interest amp Description Expressions 39 V abulary used create 0 Interest expres n subset of name space Data description expressions y Interested in all aircraft y interest expressions 7 aircralt x v for any x and any v o A name space is a set of tuples v1 v2 vquot where v is a basic type or another tuple gtgt Interested in tanks that are close b quot Example class location 7 tank x v where 10 lt x lt 20 and 130 lt v 150 7 class enumerated type lttank aireratt ship 0 Description expression subset of the name space 7L at I 39IXr d39zl IYr d39zlwh ltXlt1 d quotinvinn apetin ever in e in ever in el ere an x tank 15 135 Values in name space tanklo2oo aircrart1o2o gtgt aircraft 36 99 Values ofthe tuple space may correspond to Data muting mm quot quotquotquot39 39quotquotquot E39 39imm quot39quothl m quotquot39 quot quot quot A simulator receives a message ifthe message s description S 1quot quotquot quotquot Wm quotquotquotquot quotH 2 quot U quot quotH expression overlaps with the simulator s interest expressions space reginns nemgrnup namel o May include static properties ofobjects eg class names attribute ames or dynamic properties attribute values IlxMyIVIIE WM 9 in gt1le7 e mu 3 Data Distribution Concepts Static vs Dynamic Data Distribution o static Data Distribution x ame space only includes static properties that do not change during the execution j I gt Example Declaration Management in the HLA g e i i s iiiseri i Name spaoe alipossioietupievaiues data dstriputiir dataty es e Gi e me updates Inlhe pnsilinn attribute iii all irpjeets iii class tankquot gti Cannot lter based on dynamically computed quantities e Cannnlszy Give me updates In tank irpjeets that are elnsetir mequot a Dynamic Data Distribution gti Name space includes dynamic quantities that may change during the execution vuumased data distribution 7 Give me updates In tank nhjects that are elnsetir mequot nterest expressions simulatori The message is routed to y Example Data Distribution Management in the HLA nterest expressions simulator2 Simulatorz but motto e Renting spaces 7 D f Simu alor e Suhscriheln pnsitinn attribute nltank nhjeets that are in my seetiir til l4 esoiption expression or a message M 2 Wish Page ltgt RTI Software Outline o RTI Interface to the application federate i Name space lnterest expressions F HEW Description nterest Expressions Expressions o RTI design issues gt i What should the federate interface look like gt i How is the interface mapped to the underlying co hanisms mmunicatlon mec may lax 1 o Fundamental concepts Name space Description expressions Interest expressions 0 Static Data Distribution HLA Declaration Management Classbased ltering uquot Mi e lax 4 ClassBased Data Distribution Class Hierarchy Example 0 Declaration Management services in the HLA o Federation Object Model FOM defines an object class hierarchy describing all data exchanged among federates n object classes ii Attributes 0 Description expressions and interest expressions specify points in the object class hierarchy quotmam 5 0 Each class inherits attributes from parent class 0 z n a o m o n n o A 2 n m 1quot at a 3 ltVehicleposition ltAircraltpositiongt ltAircraftaltitudegt ltTankpositiongt ltTankturretgt lt517positiongt ltE17altitudegt ltEl7bombsgt ltSpit repositiongt ltSpit realtitudegt Spit re bullets1 B Description Expressions Interest Expressions Ve e position Aircraft position altltu de B 17 Bomber position f39re altitude bullets altitude bornbs Update Attribute Values service sends a messa e Description expression an attribute of an object instance ii Singleltclass attribute point in the name s pace Examples Spll re poslnongt orltAircraft altitude quotmama lax i7 Vehicle position Aircraft position ii ii i ie 17 Bomber Spitfire o Subscribe object Class Attributes class attributes o lnterest expression Subtree rooted at subscription point i Subscribe Aircraft altitude receive updates to altitude attribute of Aircraft 511 Spit re objects ii SAllcra altitude 1517 aoiimar ltiludegt inlt re altlltldegt i In all cases message appears as an update to an aircraft object a an Mia B iax in Page ltgt CSCI 82 Parallel amp Distributed Simulation PDES Time Warp Mechanism Computing Global Virtual Time Global Virtual Time Outline 0 GVT Computations Introduction Synchronous vs Asynchronous GVT vs L TS 0 Computing Global Virtual Time Transient Message Problem Simultaneous Reporting Problem 0 Samadi Algorithm Message Acknowledgements Marked Acknowledgment Messages Nan name MBA Global Virtual Time m 5 ca or partially processed mes Need to Fossil Collect Time Warp algorithm consumes more throughout the execution via the creation of new events Need to reclaim memory used for an the at is no longer need d a mechanism for operations th e llO cannot be undone n only b sag and more memory at cannot be rolled TWLPs only roll back as a result of receiving a message e created by an unprocessed e antrmessage anwes 2 send aritiwessage GVT unprocessed antimessage new unpiucessed events m s t W E amrmessaues Events with time stamps equal to GVT is needed There are two processed events wtn TS in the first heTWLP processed is canceled by an antrrnessage Wlth t Nun name USA GVT minimum time stamp among all unprocessed or partially processed messages at wallclock time t o Comput39ng GVT trivial if aninstantaneous snapshot of the computation could be obtained compute minimum time stamp a Unprocessed events amp antimessages within each LP Transient messages messages sent before time tthat are received after ti Memory associated with events with a TS equal to GVT cannot be reclaimed because GVT co e TS o e equal to an antimessage that has no be processed Such an antimessage could require one to rollback events with time stamp exactly equal to GVT Global Virtual Time GVTt minimum time stamp among all unprocessed or partially processed messages at wallclock time t I Computing GVT tri an instantaneous39snapshot of the computation could be obtained compute minimum timestamp amon Unprocessed events amp antimessages within each LP Transient messages messages sent before time ttnat are received after time t Synchronous vs Asynchronous GVT computation gtgt Synchronous GVT algorithms LPs stop processing events once a GVT corrputation has been daected Asynchronous GVT algorithms LPs can continue processing events and schedule new events while the GVT computation proceeds in backgroun quot GVT vs LBTS GVT algorithms can be used to compute LBTS and vice versa assuming a fully connected topology and zero lookahead 0 Both determine the mi mum time stamp of messages or antimessage that may later arrive gtgt Historically developed separatel velo O a o ped using different assurmtions lookahead Latency to compute GVT typically less critical than the latency to compute LBTS need to corm t LBT gtgt Asynchronous execution of GVT computation preferred to allow optimistic event processing to continue Nun amen m The Transient Message Problem 0 Transient message A message that has been sent but has not yet been received at its destination 0 Erroneous values may be computed if the l orithm does not take into account transient messages GVY quot lls GVT nn100 2001 GVT equot I f 7 3 6 739 new process Sean messagehere Process 1 t 4 39ll Process 2 ZED wallclock tlme mmmm ma Simultaneous Reporting Problem rroneous values of GVT may be computed when processes receive GVT request at different point in time GVT 1Il7ll100 on mine v GVT en a g Process 1 I M UD tsan Process 2 Plucesses arl eventwltn rs znn allEl retelling ackrluwledumsrl I Process 1 doesn t account for time stamp 90 m I Process 2 assumes process 1 will account for the message I no message acknowledgements solve this problem No at least not by themselves gtgt Solmion Mark acks that are sent after local min has been reported rm amen m Asynchronous GVT I An incorrect GVT algorithm Controller process broadcast compute GVT requestquot upon receiving the GVT request each proce ss computes its local minimum and reports it back to the controller Controller computes global minimum broadcast to others I Difficulties transient message problem messages sent but not yet received must be considered in computing GVT L report their local minima at different points in wallclock times leading to an incorrect GVT value Nun amen m Transient Messages A Solution Approach Ensure every message is accounted for by at least one processor when GVT is being computed I Send an acknowledgement message for each message I aiuei 39 39 I Receiver takes respons ty as it receives message v 6V1 aqua l3VI lllllll1w Sol lEKElIEDH prurEsstS9U P 1 message here rocess Am Process 2 wallclock time mama WA SenderlslEmunslblelulurlackrlmvledued memes Sanladi s Algorithm Approach Send an ack for each event amp antimessage received mark acks after the processor has reported its local minimum 0 Controller broadcast start GVTquot message aur proce ul 39 39 39 me ane were received o subsequent acks sent by process are marked until new GVT is received 0 llu II I 39 39 value A GVT equot Process 1 MM lulu Process 2 wallclock time 1C CSCI 8220 Parallel and Distributed Simulation PDES Introduction The Time Warp Mechanism nitratian um The Synchronization Problem be processeuin time stam el lt Wlthlrteacthg processimust d39el39 mug Illqunerencetotneloc t ensu ret tnepa rallelsirn ula same resultsgas the corresponding rusallty constrainti n Will produceje ctl sequential Simulation i Ssuf clent Ye i Synchronization Algorithms rvative svnchronizatio ate 4 n avoid violating the local causality constraint Walt ul ltll lt S lst generation null messages ChandvMisraBrvant ii 2nd generation later in course time stamp otnekt event i3ptimistiosvnchro izauon allovv violations orlocal causalitv to occur but ect them at runtime and recover using a rollba ism ii Time Warp Jetterson mm Han llEA Time Warp Algorithms 0 Many have been proposed will cover fundamental concep rollback antimessages Global Wrtual Time GVT I ally assume nonzero lookahead 0 Time Warp Structure local control mechan In processor mostly indepe implemented within each ndent of other processors global control mechanism used to reclaim memory and used to commit operations such as IIO that cannot be rolled back requires a distributed computation involving all processors in the system Filtratian mm o Optimistic Synchronization 0 Time Warp Local Control Mechanism 7 o lback 7 Event cancellation Global Control Mechanism a Global Virtual Time 7 Fossil Collection Filtratian um Time Warp Algorithm Jefferson Assumptions gtgt logical processes LF39s exchanging time stamp gtgt ovnamic network topology ovn mic creation ot n message sent on each link need not be sent in time stamp order gtgt netvork provides reliable delivery butneeo not preserve or er asic idea eo events messages LF39s ck o u gtgt process events vvo Worrying about messagesthatWill arrive later gtgt detect out or order execution recover using rollbac JK in m mum yiitl4589in39 Time Warp Local Control Mechanism Eacn LP process events in lime starrp order like a sequential simulator except 7 do NOT discard processed events and 2 add a rollback mecnanisrn lnpui Queue event llstl I t X lanilrmessages r straggler message ariives in tne past causing rollback l araeesea gt nausea evens D an lessees Problem Need to accounttor messages received in the LP s past Approach Rollbackand then reacornpute Problem Sub Roll t it i back changesto state variables t iiii iiie ii i iiiiiui lBlli39ll pertormeo bv events a iiiiii I39ll Sub Problem Rollback previouslv sent inessages Scilulioii ar illrlllESSagES and message aniiiliilatioris ioutptit uueuei AntiMessages undo message sends by unsendmg a metmusty senr message 3 antimatter I Mechanism r To undo the effects or a preyrously sent posrtrye message the LP need only send the correspondrng antremessage n Message send rn addrtron to sendrng the message leave a copy or the correspondrng a Processing Incoming AntiMessages Casel Correspondrng message nas not yet been processed annrnrrate messageanuemessage parr Case ll Correspondrng message nas already been processed rollbacktotrme prror to processrng message secondary rollback anmhrlate messagaantremessage parr Case lll Correspondng message nas not yet been receryed queue antremessage anmhrlate messagaantremessage parrwnen message rs receryed 2 rolbackeventsM a as 4 2arestore state 55 A r anrrmessage srrrve Pmcessedeenls unpreceseueens unn sue C D arm message or send antremessage LP Sijnulat39ion Example 2 rollback events at rrmes as and 27 2a restore state ofLP to me pnorzo processrng trme stamp 2r event lnputOueue processed wants eventlrstl 1 7 r 7 3e unpmcessedwems 39l rurrlrr J r lJ 5 3r er rrnan lr antremessaues v x Uulput Queue my send amemessage antlemessauesr n 42 I BEFORE A H rnpumueue Hr Heinlein tr 39rht rene 5 resume execunon oyprocessrng event ar rrme rs output or reue antlemessagesr I AFTER e Rollback Receiving a Straggler Message Processing Incoming AntiMessages Casel Correspondrng message nas not yet been processed anmhrlate messageanuemessage parr Case ll Correspondrng message nas already been processed rollbacktotrme prror to processrng message secondary rollback anmhrlate messagaantremessage parr Case lll Correspondrng message nas not yet been receryed queue antremessage anmhrlate messagaantremessage parrwnen message rs receryed r anrrmessage srrrve Pmcessedeenls unpreceseueens D D arm message JrJll r slate Global Virtual Time and Fossil Collection Runwayf mee rusm Schedule Landed evenuldeelr Now m d e 7 Schedule Departure eventllncal o lnw or iii InTheMr gt o r Schedule landed eventllncal aw 1 else Runwayf ree True Departure Event in e Delay to beach mther airwrtl Gm OllTheGNlul 1 Schedule Arrival Event tmnnhe quotsmut another dirpart 11 o A mechanism is needed to ces e 9 old state and events perform irrevocable operations eg IO 0 Observation A Io bound on the time stamp of any rollback that can occur in the future is needed 0 Global Virtual Time GVT is de ned as the minimum time stamp of any unprocessed or partially processed message or anti message in the s stem GVT provides a lower bound on the time stamp of any future rollback storage for events and state vectors older than GVT except one state vector can be rec 39 ed IIO operations with time stamp less than GVT can be performed 0 ObservationzThe computation corresponding to GVT will not be rolled back guaranteeing Mm Hymnal usu
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'