1Introduction toEmbedded SystemsEdward A. Lee & Sanjit A. SeshiaUC BerkeleyEECS 149Spring 2009Copyright © 2008-09, Edward A. Lee & Sanjit A. Seshia, All rights reservedLecture 11: Simulation of Discrete-Event SystemsMaterial drawn from book by Banks et al., notes by M. Harchol-BalterEECS 149, UC Berkeley: 2Discrete-Event SystemA dynamical system whose evolution is governed by the occurrence of events at discrete time points, at possibly irregularly-spaced intervals (Informal defn)Many cyber-physical systems are modeled as discrete-event systems:Communication networksMicroprocessorsManufacturing facilitiesCommunicating robots2EECS 149, UC Berkeley: 3Example: Communicating Robots/Sensor NodesNetwork can fwd, corrupt, droppacketssendrecvEECS 149, UC Berkeley: 4This LectureHow to build a simulator for a discrete-event system – the basicsExamples of such simulators:ns-2 (for simulating computer networks)ModelSim (for simulating digital circuit designs)3EECS 149, UC Berkeley: 5Simulating a Discrete-Event System (DES)Discrete-EventSystemInputProcess3.How tocheck Output?2.How to generaterandom input?i/p o/pEnvironment1.How to simulate the system on an input?EECS 149, UC Berkeley: 6Simulating the System with an Event QueueSimulation Timer, T = 0Repeat while there are events in the event queue:1. Dequeue event at head of queue (“imminent event”)2. Advance simulation timer to time of imminent event 3. Execute imminent event: update system state4. Generate future events and enqueue them . . .Event queuet1e1t2e2t3e3timestampevent record t1< t2< t3< …4EECS 149, UC Berkeley: 7Example of Simulation with Event QueueNetwork123e1= send(1, 2, 00)T = 0. . .Event queue1.5e1e2= send(3, 1, 10)3.8e2EECS 149, UC Berkeley: 8Example of Simulation with Event QueueNetwork123e3= fwd(2, 1, 00)T = 1.5. . .Event queue1.6e3e2= send(3, 1, 10)3.8e25EECS 149, UC Berkeley: 9Example of Simulation with Event QueueNetwork123e4= recv(2, 1, 00)T = 1.6. . .Event queue3.8e2e2= send(3, 1, 10)4.1e4EECS 149, UC Berkeley: 10Implementing the Event QueueEvent with smallest time-stamp must be dequeuedNew events must be inserted into sorted order according to their timestampsEfficient Data Structure: Priority QueueParticular version: Calendar Queue [R. Brown, Comm. of the ACM, 1988, vol. 31(10)]6EECS 149, UC Berkeley: 11Simulating a Discrete-Event System (DES)Discrete-EventSystemInputProcess3.How tocheck Output?2.How to generaterandom input?i/p o/pEnvironment1.How to simulate the system?EECS 149, UC Berkeley: 12Generating Random InputsSuppose we have an input signal taking values in a set of “events”: {e1, e2, e3, …, en}Suppose event eioccurs with probability pi∑ipi= 1How do we generate events randomly?7EECS 149, UC Berkeley: 13Inverse Transform MethodGenerate u in [0,1) – uniformly at random using your programming environment’s built-in pseudo-random number generator e.g. drand48() in CSet p0= 0. Add up pi’s until we get to ∑i=0jpi u < ∑i=0j+1piGenerate input event ej+1Is this an efficient procedure?EECS 149, UC Berkeley: 14Analysis of Inverse Transform MethodInefficient if n is largeWhy?Because we need to compute many partial sums ∑ipiin order to figure out where u lies worst case: n-1 such sumsThere’s one special case where sampling from the pi’s is easy: what is it?8EECS 149, UC Berkeley: 15Solution: The Accept/Reject MethodEasy to generate events uniformly at random efficientlyBut in general, we have an arbitrary probability mass function p1, p2, …, pn.How can we leverage the ease of generating uniformly at random to generate according to the pi’s? The accept/reject method gives us a way to do thisEECS 149, UC Berkeley: 16General SetupGiven:Efficient method for sampling from n events according to p.m.f. {q1, q2, … qn}  e.g. the pmf is uniform random, qi= 1/n for all iNeed:Efficient method for sampling from same n events but according to non-uniform p.m.f. {p1, p2, …, pn}Constraint: ∀ i, qi> 0 iff pi> 0Any ideas on how to do this?9EECS 149, UC Berkeley: 17Idea #1 for Accept/Reject MethodDo two steps:1.Select index i randomly according to easy distribution {q1, q2, …, qn}2.Then accept the index i with probability pi generate event ei otherwise go back to step 1How do we implement this?EECS 149, UC Berkeley: 18Idea #1 for Accept/Reject MethodDo two steps:1.Select index i randomly according to easy distribution {q1, q2, …, qn}2.Then accept the index i with probability pi generate event eiTwo questions:1.Is this correct?  Are we really generating eiaccording to p1, p2, …,pn?2.Is this efficient? What is the expected #trials before we generate ei?YES, if each qi= 1/nOn the order of n10EECS 149, UC Berkeley: 19Idea #2 for Accept/Reject MethodDo three steps:1.Initially: select c such that pi/qi c ∀ i s.t. pi> 02.Select index i randomly according to easy distribution {q1, q2, …, qn}3.Then accept the index i with probability pi/(c qi)  generate event eiEECS 149, UC Berkeley: 20Idea #2 for Accept/Reject MethodDo three steps:1.Initially: select c such that pi/qi c ∀ i s.t. pi> 02.Select index i randomly according to easy distribution {q1, q2, …, qn}3.Then accept the index i with probability pi/(c qi)  generate event eiClaim: This method isCorrect: Pr(ejis generated) = pjEfficient: Expected #trials = c11EECS 149, UC Berkeley: 21Accept/Reject works the same way for Continuous Random Variables, too!Given: How to generate Y with “easy” probability density function (pdf) fY(t)Need: To generate X with pdf fX(t)Constraint: ∀ t, fY(t) > 0 iff fX(t) > 0Algorithm:1.Pick constant c such that fX(t)  c fY(t) ∀ t s.t. fY(t) > 02.Sample t according to fY3.Accept X = t with probability fX(t) / [c fY(t)] Useful for generating inter-arrival times of events EECS 149, UC Berkeley: 22Simulating a Discrete-Event System (DES)Discrete-EventSystemInputProcess3.How tocheck Output?2.How to generaterandom input?i/p o/pEnvironment1.How to simulate the system?12EECS 149, UC Berkeley: 23How to check the outputNeed to compare the observed input-output sequence with the expected input-output sequenceCompare(i0, o0), (i1, o1), (i2, o2), …. against(i0, o0’), (i1, o1’), (i2, o2’), …. Note: can only compare finite-length sequences!sendrecvEECS 149, UC Berkeley: 24How to check the outputSynthesize an