EE 144/244: Fundamental Algorithms For System Modeling .
EE 144/244: Fundamental Algorithms for SystemModeling, Analysis, and OptimizationFall 2016Discrete Event SimulationStavros TripakisUniversity of California, BerkeleyStavros Tripakis (UC Berkeley)EE 144/244, Fall 2016Discrete Event Simulation1 / 53
Timed SystemsIn circuits, as well as in embedded / cyber-physical systems, timing is key:proper timing an issue of correctnessthe right values, at the right time (not too late, not too early)c.f. real-time control.Contrast this to personal computers: “best-effort” systems – timing anissue of performance.Stavros Tripakis (UC Berkeley)EE 144/244, Fall 2016Discrete Event Simulation2 / 53
(Timed) Discrete-Event (DE) Systemsvs. Continuous Control SystemsContinuous control systems:Coming from continuous system theory.Typically implemented by periodic sampling controllers (butsometimes also event-driven controllers): these are discrete, but try toapproximate the continuous ones.Discrete-event systems:More “sparse” events (typically).Discrete control: e.g., mode switches.Typically higher level: e.g., supervisory control (DE) vs. cruise control(continuous).Other application domains:IIQueueing theory.Circuits (VHDL, Verilog, SystemC).Stavros Tripakis (UC Berkeley)EE 144/244, Fall 2016Discrete Event Simulation3 / 53
(Timed) Discrete EventsEvent:something occurring at some point in timemay also carry a valueevent (timestamp, value)discrete-event systems: consumers/producers of event streamse16e26e3 e46 6e6e56···-system6t2t3 t4Stavros Tripakis (UC Berkeley)t56e86···--t1e7-t6timeEE 144/244, Fall 2016t7t8Discrete Event Simulationtime4 / 53
Continuous vs. Discrete Event SystemsContinuous systems: functions on continuous signals.Continuous signal x continuous function of dense time (R )x : R Vx(t): value of x at time t; belongs to some set of values V (e.g., R)Timed Discrete Event Systems: deal with timed discrete-event signals.Timed discrete-event signal: sequence of timed events.···continuoussystem···timetimee1e2e3 e4e5t1t2t3 t4t5···Stavros Tripakis (UC Berkeley)discreteeventsystemtimeEE 144/244, Fall 2016e6e7e8t6t7t8···Discrete Event Simulationtime5 / 53
DIGRESSION:CONTINUOUS vs. DISCRETE SIGNALSStavros Tripakis (UC Berkeley)EE 144/244, Fall 2016Discrete Event Simulation6 / 53
Continuous vs. discrete signalsIntuition:Discrete: only finite number of events can happen in a finite amount oftime.Continuous: not discrete.Stavros Tripakis (UC Berkeley)EE 144/244, Fall 2016Discrete Event Simulation7 / 53
Continuous vs. discrete signalsIntuition:Discrete: only finite number of events can happen in a finite amount oftime.Continuous: not discrete.Let’s try to formalize this intuition.Stavros Tripakis (UC Berkeley)EE 144/244, Fall 2016Discrete Event Simulation7 / 53
Continuous vs. discrete signalsLet R be the set of non-negative reals, modeling time.Let V be a set of values.A signal can be defined as a set of events:s R V(this is the tagged signal model [Lee and Sangiovanni-Vincentelli(1998)]).Stavros Tripakis (UC Berkeley)EE 144/244, Fall 2016Discrete Event Simulation8 / 53
Continuous vs. discrete signalsLet R be the set of non-negative reals, modeling time.Let V be a set of values.A signal can be defined as a set of events:s R V(this is the tagged signal model [Lee and Sangiovanni-Vincentelli(1998)]).Let T (s) be the set of all timestamps in signal s:T (s) {t (t, v) s}Stavros Tripakis (UC Berkeley)EE 144/244, Fall 2016Discrete Event Simulation8 / 53
Continuous vs. discrete signalsLet R be the set of non-negative reals, modeling time.Let V be a set of values.A signal can be defined as a set of events:s R V(this is the tagged signal model [Lee and Sangiovanni-Vincentelli(1998)]).Let T (s) be the set of all timestamps in signal s:T (s) {t (t, v) s}Then we can define:s is discrete if T (s) is order-isomorphic to a subset of N, whereN {0, 1, 2, .} is the set of natural numbers.Otherwise, s is continuous.Stavros Tripakis (UC Berkeley)EE 144/244, Fall 2016Discrete Event Simulation8 / 53
Order-isomorphismsA order-isomorphic B means there is an order-preserving bijectionf : A B.In our case the order is the usual on R and N. So:f must be a bijection: (1) f (a) must be defined for all a A, (2) forall b B there must exist a A such that f (a) b, and (3)a 6 a0 f (a) 6 f (a0 ).f must be order-preserving: a a0 f (a) f (a0 ).Stavros Tripakis (UC Berkeley)EE 144/244, Fall 2016Discrete Event Simulation9 / 53
Order-isomorphismsA order-isomorphic B means there is an order-preserving bijectionf : A B.In our case the order is the usual on R and N. So:f must be a bijection: (1) f (a) must be defined for all a A, (2) forall b B there must exist a A such that f (a) b, and (3)a 6 a0 f (a) 6 f (a0 ).f must be order-preserving: a a0 f (a) f (a0 ).Is N N (with lexicographic order) order-isomorphic to N ?Stavros Tripakis (UC Berkeley)EE 144/244, Fall 2016Discrete Event Simulation9 / 53
Continous and discrete signalsAre the signals below discrete or continuous?s1 {(t, t) t R }?Stavros Tripakis (UC Berkeley)EE 144/244, Fall 2016Discrete Event Simulation10 / 53
Continous and discrete signalsAre the signals below discrete or continuous?s1 {(t, t) t R }?Stavros Tripakis (UC Berkeley)Continuous.EE 144/244, Fall 2016Discrete Event Simulation10 / 53
Continous and discrete signalsAre the signals below discrete or continuous?s1 {(t, t) t R }?Continuous.s2 {(n, v) n N, v V }?Stavros Tripakis (UC Berkeley)EE 144/244, Fall 2016Discrete Event Simulation10 / 53
Continous and discrete signalsAre the signals below discrete or continuous?s1 {(t, t) t R }?Continuous.s2 {(n, v) n N, v V }?Stavros Tripakis (UC Berkeley)Discrete.EE 144/244, Fall 2016Discrete Event Simulation10 / 53
Continous and discrete signalsAre the signals below discrete or continuous?s1 {(t, t) t R }?Continuous.s2 {(n, v) n N, v V }?Discrete.s3 {(0, 0), (1, 1, ), (2, 2)}?Stavros Tripakis (UC Berkeley)EE 144/244, Fall 2016Discrete Event Simulation10 / 53
Continous and discrete signalsAre the signals below discrete or continuous?s1 {(t, t) t R }?Continuous.s2 {(n, v) n N, v V }?s3 {(0, 0), (1, 1, ), (2, 2)}?Stavros Tripakis (UC Berkeley)Discrete.Discrete.EE 144/244, Fall 2016Discrete Event Simulation10 / 53
Continous and discrete signalsAre the signals below discrete or continuous?s1 {(t, t) t R }?Continuous.s2 {(n, v) n N, v V }?s3 {(0, 0), (1, 1, ), (2, 2)}?Discrete.Discrete.s4 {(0.3, 0), (1.27, 1, ), (2π, 2)}?Stavros Tripakis (UC Berkeley)EE 144/244, Fall 2016Discrete Event Simulation10 / 53
Continous and discrete signalsAre the signals below discrete or continuous?s1 {(t, t) t R }?Continuous.s2 {(n, v) n N, v V }?s3 {(0, 0), (1, 1, ), (2, 2)}?Discrete.Discrete.s4 {(0.3, 0), (1.27, 1, ), (2π, 2)}?Stavros Tripakis (UC Berkeley)Discrete.EE 144/244, Fall 2016Discrete Event Simulation10 / 53
Continous and discrete signalsAre the signals below discrete or continuous?s1 {(t, t) t R }?Continuous.s2 {(n, v) n N, v V }?s3 {(0, 0), (1, 1, ), (2, 2)}?Discrete.Discrete.s4 {(0.3, 0), (1.27, 1, ), (2π, 2)}?Discrete.s5 {}?Stavros Tripakis (UC Berkeley)EE 144/244, Fall 2016Discrete Event Simulation10 / 53
Continous and discrete signalsAre the signals below discrete or continuous?s1 {(t, t) t R }?Continuous.s2 {(n, v) n N, v V }?s3 {(0, 0), (1, 1, ), (2, 2)}?Discrete.Discrete.s4 {(0.3, 0), (1.27, 1, ), (2π, 2)}?s5 {}?Discrete.Discrete.Stavros Tripakis (UC Berkeley)EE 144/244, Fall 2016Discrete Event Simulation10 / 53
Continous and discrete signalsAre the signals below discrete or continuous?s1 {(t, t) t R }?Continuous.s2 {(n, v) n N, v V }?s3 {(0, 0), (1, 1, ), (2, 2)}?Discrete.Discrete.s4 {(0.3, 0), (1.27, 1, ), (2π, 2)}?s5 {}?Discrete.Discrete.s6 {(t, t) t [0, 1]}?Stavros Tripakis (UC Berkeley)EE 144/244, Fall 2016Discrete Event Simulation10 / 53
Continous and discrete signalsAre the signals below discrete or continuous?s1 {(t, t) t R }?Continuous.s2 {(n, v) n N, v V }?s3 {(0, 0), (1, 1, ), (2, 2)}?Discrete.Discrete.s4 {(0.3, 0), (1.27, 1, ), (2π, 2)}?s5 {}?Discrete.Discrete.s6 {(t, t) t [0, 1]}?Stavros Tripakis (UC Berkeley)Continuous.EE 144/244, Fall 2016Discrete Event Simulation10 / 53
Continous and discrete signalsAre the signals below discrete or continuous?s1 {(t, t) t R }?Continuous.s2 {(n, v) n N, v V }?s3 {(0, 0), (1, 1, ), (2, 2)}?Discrete.Discrete.s4 {(0.3, 0), (1.27, 1, ), (2π, 2)}?s5 {}?Discrete.Discrete.s6 {(t, t) t [0, 1]}?Continuous.s7 {(t, btc) t R }?Stavros Tripakis (UC Berkeley)EE 144/244, Fall 2016Discrete Event Simulation10 / 53
Continous and discrete signalsAre the signals below discrete or continuous?s1 {(t, t) t R }?Continuous.s2 {(n, v) n N, v V }?s3 {(0, 0), (1, 1, ), (2, 2)}?Discrete.Discrete.s4 {(0.3, 0), (1.27, 1, ), (2π, 2)}?s5 {}?Discrete.Discrete.s6 {(t, t) t [0, 1]}?Continuous.s7 {(t, btc) t R }? Continuous, according to our definition. But itis also piecewise constant, and could therefore be considered asessentially discrete. This is how discrete signals are modeled in Simulink.Stavros Tripakis (UC Berkeley)EE 144/244, Fall 2016Discrete Event Simulation10 / 53
Continuous vs. discrete signalsOur definition of discrete vs. continuous signals:s is discrete if T (s) is order-isomorphic to a subset of N, whereN {0, 1, 2, .} is the set of natural numbers.Otherwise, s is continuous.Recall our intuition:Discrete: only finite number of events can happen in a finite amountof time.Continuous: not discrete.Does the definition capture our original intuition?Stavros Tripakis (UC Berkeley)EE 144/244, Fall 2016Discrete Event Simulation11 / 53
Example: bouncing ballJie Liu and Edward A. LeeStavros Tripakis (UC Berkeley)EE 144/244, Fall 2016Discrete Event Simulation11 / 53
Example: bouncing ballZeno system: infinite # ofdiscrete events in a finiteamount of time time blocked.Jie Liu and Edward A. LeeStavros Tripakis (UC Berkeley)EE 144/244, Fall 2016Discrete Event Simulation11 / 53
ZenoZeno’s “Achilles and the tortoise” paradox:Achilles and the tortoise enter a race. Achilles runs of course muchfaster. He graciously allows the tortoise a head start of 1 meter. Whowill win?Stavros Tripakis (UC Berkeley)EE 144/244, Fall 2016Discrete Event Simulation14 / 53
ZenoZeno’s “Achilles and the tortoise” paradox:Achilles and the tortoise enter a race. Achilles runs of course muchfaster. He graciously allows the tortoise a head start of 1 meter. Whowill win?“In a race, the quickest runner can never overtake the slowest, sincethe pursuer must first reach the point whence the pursued started, sothat the slower must always hold a lead.”(from wikipedia)Stavros Tripakis (UC Berkeley)EE 144/244, Fall 2016Discrete Event Simulation14 / 53
Zeno DE systemsA DE system is zeno if it generates an infinite number of events in a finite amount oftime:Zeno SignalsEventually, executionstops advancing time.Why?Note that if the Ramp is set to produceinteger outputs, then eventually theoutput will overflow and becomenegative, which will cause an exception.Lee 12: 19Zeno systems are sometimes useful (c.f., bouncing ball) but often an error of modeling.We will see how to avoid it in DE simulation, to avoid blocking time globally.Stavros Tripakis (UC Berkeley)EE 144/244, Fall 2016Discrete Event Simulation15 / 53
END DIGRESSIONStavros Tripakis (UC Berkeley)EE 144/244, Fall 2016Discrete Event Simulation16 / 53
Example Discrete-Event System: Dense-Time Delaye16e26e36e46e1···-Delay: 1-e26e3e46662.93.55.1-11.92.54.1Stavros Tripakis (UC Berkeley)···-R 2EE 144/244, Fall 2016Discrete Event SimulationR 17 / 53
Delay vs. ServerStavros Tripakis (UC Berkeley)EE 144/244, Fall 2016Discrete Event Simulation18 / 53
DIGRESSION:EVENTS vs. STATESStavros Tripakis (UC Berkeley)EE 144/244, Fall 2016Discrete Event Simulation19 / 53
From States to EventsIf my formalism only has the notion of state, can I define events?Stavros Tripakis (UC Berkeley)EE 144/244, Fall 2016Discrete Event Simulation20 / 53
From States to EventsIf my formalism only has the notion of state, can I define events?Event change of stateStavros Tripakis (UC Berkeley)EE 144/244, Fall 2016Discrete Event Simulation20 / 53
From States to EventsIf my formalism only has the notion of state, can I define events?Event change of stateExample: Lustre programnode UpwardEdge (X : bool) returns (E : bool);letE false - X and not pre X ;telStavros Tripakis (UC Berkeley)EE 144/244, Fall 2016Discrete Event Simulation20 / 53
From Events to StatesIf my formalism only has events as primitives, can I define state?Stavros Tripakis (UC Berkeley)EE 144/244, Fall 2016Discrete Event Simulation21 / 53
From Events to StatesIf my formalism only has events as primitives, can I define state?State history of events observed so farStavros Tripakis (UC Berkeley)EE 144/244, Fall 2016Discrete Event Simulation21 / 53
From Events to StatesIf my formalism only has events as primitives, can I define state?State history of events observed so farFormally:Σ: set of eventsΣ : set of finite event sequences historiesEvery s Σ can be seen as a stateStavros Tripakis (UC Berkeley)EE 144/244, Fall 2016Discrete Event Simulation21 / 53
From Events to StatesIf my formalism only has events as primitives, can I define state?State history of events observed so farFormally:Σ: set of eventsΣ : set of finite event sequences historiesEvery s Σ can be seen as a stateC.f. a famous theorem:Theorem (Myhill-Nerode theorem)A language L Σ is regular iff the equivalence relation over wordss L s0 b s00 Σ : s · s00 L s0 · s00 Lhas a finite set of equivalence classes. The number of equivalence classes of L isthe number of states in the smallest DFA recognizing L.Stavros Tripakis (UC Berkeley)EE 144/244, Fall 2016Discrete Event Simulation21 / 53
END DIGRESSIONStavros Tripakis (UC Berkeley)EE 144/244, Fall 2016Discrete Event Simulation22 / 53
Discrete-Event Models (DE)Networks of actors such as Delay, Server, sources, sinks, .model 1 (drawing)Stavros Tripakis (UC Berkeley)model 2 (ptolemy)EE 144/244, Fall 2016Discrete Event Simulation23 / 53
Example: car washTaken from [Misra(1986)]:Source generates car arrivals at some arbitrary times.Attendant directs cars to car wash stations CW1 or CW2:IIIIif both CW1 and CW2 are free, then to CW1;if only one is free, then to this free one;otherwise car waits until a station becomes free.Cars are served by attendant in FIFO order.CW1 spends 8 mins to wash a car.CW2 spends 10 mins to wash a car.Stavros Tripakis (UC Berkeley)EE 144/244, Fall 2016Discrete Event Simulation24 / 53
Delay vs. ServerAre CW1, CW2 delays or servers?Stavros Tripakis (UC Berkeley)EE 144/244, Fall 2016Discrete Event Simulation25 / 53
Analysis of DE Modelsmodel 1 (drawing)model 2 (ptolemy)We will look at simulation of DE models.Exhaustive verification (model-checking) of DE models: not wellstudied (see [Stergiou et al. 2013])Stavros Tripakis (UC Berkeley)EE 144/244, Fall 2016Discrete Event Simulation26 / 53
Analysis of DE Modelsmodel 1 (drawing)model 2 (ptolemy)We will look at simulation of DE models.Exhaustive verification (model-checking) of DE models: not wellstudied (see [Stergiou et al. 2013])Well studied problem: exhaustive verification of another type of DEsystem: timed automata [Alur and Dill(1994)]Stavros Tripakis (UC Berkeley)EE 144/244, Fall 2016Discrete Event Simulation26 / 53
DISCRETE-EVENT SIMULATIONStavros Tripakis (UC Berkeley)EE 144/244, Fall 2016Discrete Event Simulation27 / 53
Discrete-Event Simulation: Basic IdeaStandard DE simulation scheme:1:2:3:4:5:6:7:t : 0;// initialize simulation time to 0initialize global event queue Q with a set of initial events;// events in Q ordered by timestampwhile Q is not empty doremove earliest event e (ve , te ) from Q;t : te ;// advance global time“execute” event e: update system state, generate possible futureevents, and add them to Q, ordered by timestamps;end whileStavros Tripakis (UC Berkeley)EE 144/244, Fall 2016Discrete Event Simulation28 / 53
Example: Clock and DelayClock period: 0.6ci : events generated by Clockdi : events generated by Delay1:2:3:4:5:6:7:t : 0;initialize global event queue Q with a set of initial events;while Q is not empty doremove earliest event e (ve , te ) from Q;t : te ;“execute” event e;end whileStavros Tripakis (UC Berkeley)EE 144/244, Fall 2016Discrete Event Simulation29 / 53
Example: Clock and DelayClock period: 0.6ci : events generated by Clockdi : events generated by Delaypoint in algoafter initialization (step 2)after step 4after step 5after step 6after step 4after step 5after step 6after step 4after step 5after step 6···Stavros Tripakis (UC Berkeley)t0Q[(c0 , 0), (c1 , 0.6), (c2 , 1.2), .][(c1 , 0.6), (c2 , 1.2), .][(c1 , 0.6), (d0 , 1.0), (c2 , 1.2), .]current event e[(d0 , 1.0), (c2 , 1.2), .][(d0 , 1.0), (c2 , 1.2), (d1 , 1.6), .](c1 , 0.6)[(c2 , 1.2), (d1 , 1.6), .]Q does not change, butsomething gets printed(d0 , 1.0)(c0 , 0)00.61.0EE 144/244, Fall 2016Discrete Event Simulation30 / 53
Discrete-Event Simulation: Issues1: t : 0;2: initialize global event queue Q with a set of initial events;3: while Q is not empty do4:remove earliest event e (ve , te ) from Q;5:t : te ;6:“execute” event e: update system state, generate possible future events,and add them to Q, ordered by timestamps;7: end whileAppears intuitive, but details are left unspecified: steps 2, 6.Not modular : step 6 appears to work on the entire system state, not onindividual actors.How to make such a scheme completely modular is an active topic ofresearch (we will come back to this).Stavros Tripakis (UC Berkeley)EE 144/244, Fall 2016Discrete Event Simulation31 / 53
Discrete-Event Simulation: Issues1: t : 0;2: initialize global event queue Q with a set of initial events;3: while Q is not empty do4:remove earliest event e (ve , te ) from Q;5:t : te ;6:“execute” event e: update system state, generate possible future events,and add them to Q, ordered by timestamps;7: end whileAppears intuitive, but details are left unspecified: steps 2, 6.Not modular : step 6 appears to work on the entire system state, not onindividual actors.How to make such a scheme completely modular is an active topic ofresearch (we will come back to this).Let’s try to flesh out the details of steps 2 and 6.Stavros Tripakis (UC Berkeley)EE 144/244, Fall 2016Discrete Event Simulation31 / 53
Modeling Source ActorsSource actor an actor with no inputs.Clock is a source:Stavros Tripakis (UC Berkeley)EE 144/244, Fall 2016Discrete Event Simulation32 / 53
Modeling Source ActorsSource actor an actor with no inputs.Clock is a source:Option 1 – sources generate all their events at initialization.IISimulation time is finite, so presumably only finite number of events.But it may be very large.Stavros Tripakis (UC Berkeley)EE 144/244, Fall 2016Discrete Event Simulation32 / 53
Modeling Source ActorsSource actor an actor with no inputs.Clock is a source:Option 1 – sources generate all their events at initialization.IISimulation time is finite, so presumably only finite number of events.But it may be very large.Option 2 – model sources using feedback loops with initial events:Stavros Tripakis (UC Berkeley)EE 144/244, Fall 2016Discrete Event Simulation32 / 53
Feedback loops are necessary in generalExample: car wash (taken from [Misra(1986)]):Source generates car arrivals at some arbitrary times (e.g., at times 3, 8, 9, 14, 16,22)Attendant directs cars to car wash stations CW1 or CW2:IIIIif both CW1 and CW2 are free, then to CW1if only one is free, then to this free oneotherwise car waits until a station becomes freecars are served by attendant in FIFO orderCW1 (a server actor) spends 8 mins to wash a carCW2 (a server actor) spends 10 mins to wash a carStavros Tripakis (UC Berkeley)EE 144/244, Fall 2016Discrete Event Simulation33 / 53
But feedback loops can also be dangerous .Zeno SignalsEventually, executionstops advancing time.Why?Note that if the Ramp is set to produceinteger outputs, then eventually theoutput will overflow and becomeStavros Tripakis (UC ve, which willDiscrete Event Simulation34 / 53
Avoiding Zeno SystemsSuppose we add a constant (or at least bounded from below) non-zerodelay in every feedback loop:Is it sufficient to avoid zenoness?Stavros Tripakis (UC Berkeley)EE 144/244, Fall 2016Discrete Event Simulation35 / 53
Avoiding Zeno SystemsSuppose we add a constant (or at least bounded from below) non-zerodelay in every feedback loop:Is it sufficient to avoid zenoness?Yes. Exercise: prove it.Stavros Tripakis (UC Berkeley)EE 144/244, Fall 2016Discrete Event Simulation35 / 53
Avoiding Zeno SystemsSuppose we add a constant (or at least bounded from below) non-zerodelay in every feedback loop:Is it sufficient to avoid zenoness?Yes. Exercise: prove it.From now on we assume a constant non-zero delay in every feedback loop.Stavros Tripakis (UC Berkeley)EE 144/244, Fall 2016Discrete Event Simulation35 / 53
Another Example: AlarmSourcecancelAlarmalarmSinkAlarm actor: produces event at given time t, unless it receives inputat time t0 t.Stavros Tripakis (UC Berkeley)EE 144/244, Fall 2016Discrete Event Simulation36 / 53
Another Example: AlarmSourcecancelAlarmalarmSinkAlarm actor: produces event at given time t, unless it receives inputat time t0 t.How does the DE simulation algorithm handle this example?Stavros Tripakis (UC Berkeley)EE 144/244, Fall 2016Discrete Event Simulation36 / 53
Another Example: AlarmSourcecancelAlarmalarmSinkAlarm actor: produces event at given time t, unless it receives inputat time t0 t.How does the DE simulation algorithm handle this example?It appears that Alarm should post an initial event with time t. but this event may then have to be canceled during simulation ifsomething arrives at the input before t.Canceling events removing them from the event queue.Stavros Tripakis (UC Berkeley)EE 144/244, Fall 2016Discrete Event Simulation36 / 53
Why insert events only to cancel them later?Whether an event will be generated before t may not always be easy todetermine:Some complex modelcancelAlarmalarmSinkDE algorithm must work independently of how Alarm is connected.That’s what modular means.Stavros Tripakis (UC Berkeley)EE 144/244, Fall 2016Discrete Event Simulation37 / 53
Discrete-Event Simulation – version 21:2:3:4:5:6:7:t : 0;initialize global event queue Q with a set of initial events;while Q is not empty doremove earliest event e (ve , te ) from Q;t : te ;execute event e: update system state, generate possible futureevents, and add them to Q, ordered by timestamps; possibly removeevents from Q;end whileStavros Tripakis (UC Berkeley)EE 144/244, Fall 2016Discrete Event Simulation38 / 53
Another Issue: Simultaneous EventsThe AddSubtract actor is supposed to behave as follows:If it receives two simultaneous events, it adds/subtracts their values andproduces a single event at its output with the resulting value.If it receives an event in just one of the two inputs, it simply forwards it.Suppose the two SingleEvent actors produce two simultaneous events with thesame value x.What should the output be?Stavros Tripakis (UC Berkeley)EE 144/244, Fall 2016Discrete Event Simulation39 / 53
Another Issue: Simultaneous EventsThe AddSubtract actor is supposed to behave as follows:If it receives two simultaneous events, it adds/subtracts their values andproduces a single event at its output with the resulting value.If it receives an event in just one of the two inputs, it simply forwards it.Suppose the two SingleEvent actors produce two simultaneous events with thesame value x.What should the output be? A single event with value x x 0.Stavros Tripakis (UC Berkeley)EE 144/244, Fall 2016Discrete Event Simulation39 / 53
Another Issue: Simultaneous EventsHow to achieve the desired behavior with the DE simulation algorithm?1: t : 0;2: initialize global event queue Q with a set of initial events;3: while Q is not empty do4:remove earliest event e (ve , te ) from Q;5:t : te ;6:execute event e: update system state, generate possible future events, and addthem to Q, ordered by timestamps; possibly remove events from Q;7: end whileStavros Tripakis (UC Berkeley)EE 144/244, Fall 2016Discrete Event Simulation40 / 53
Discrete-Event Simulation – version 3It appears that the DE simulation algorithm must execute sets ofsimultaneous events, instead of one event at a time:1: t : 0;2: initialize global event queue Q with a set of initial events;3: while Q is not empty do4:remove earliest event e (ve , te ) set E of all (?) simultaneous earliestevents from Q;t : te ;execute event e set of events E: update system state, generate possiblefuture events, and add them to Q, ordered by timestamps; possibly removeevents from Q;7: end while5:6:Stavros Tripakis (UC Berkeley)EE 144/244, Fall 2016Discrete Event Simulation41 / 53
Discrete-Event Simulation – version 3It appears that the DE simulation algorithm must execute sets ofsimultaneous events, instead of one event at a time:1: t : 0;2: initialize global event queue Q with a set of initial events;3: while Q is not empty do4:remove earliest event e (ve , te ) set E of all (?) simultaneous earliestevents from Q;t : te ;execute event e set of events E: update system state, generate possiblefuture events, and add them to Q, ordered by timestamps; possibly removeevents from Q;7: end while5:6:Not as simple .Stavros Tripakis (UC Berkeley)EE 144/244, Fall 2016Discrete Event Simulation41 / 53
Issues with Simultaneous EventsSuppose the two SingleEvent sources produce two simultaneous events.Should these be processed together by the algorithm?Stavros Tripakis (UC Berkeley)EE 144/244, Fall 2016Discrete Event Simulation42 / 53
Issues with Simultaneous EventsSuppose the two SingleEvent sources produce two simultaneous events.Should these be processed together by the algorithm?No: AddSubtract needs to wait for the output of Scale.Stavros Tripakis (UC Berkeley)EE 144/244, Fall 2016Discrete Event Simulation42 / 53
Issues with Simultaneous EventsSuppose the two SingleEvent sources produce two simultaneous events.Should these be processed together by the algorithm?No: AddSubtract needs to wait for the output of Scale.Processing a set of simultaneous events E may result in new simultaneousevents not in E .We need some systematic way to do this .Stavros Tripakis (UC Berkeley)EE 144/244, Fall 2016Discrete Event Simulation42 / 53
Back to the Alarm ExampleSourcecancelAlarmalarmSinkAlarm actor: produces event at given time t, unless it receives inputat time t0 tStavros Tripakis (UC Berkeley)EE 144/244, Fall 2016Discrete Event Simulation43 / 53
Back to the Alarm ExampleSourcecancelAlarmalarmSinkAlarm actor: produces event at given time t, unless it receives inputat time t0 tWhat if Source produces an event also at time t?Stavros Tripakis (UC Berkeley)EE 144/244, Fall 2016Discrete Event Simulation43 / 53
Back to the Alarm ExampleSourcecancelAlarmalarmSinkAlarm actor: produces event at given time t, unless it receives inputat time t0 tWhat if Source produces an event also at time t?According to the semantics of Alarm, it should not raise an alarmevent.Does the DE simulation algorithm guarantee this?Stavros Tripakis (UC Berkeley)EE 144/244, Fall 2016Discrete Event Simulation43 / 53
Back to the Alarm ExampleSourcecancelAlarmalarmSink1: t : 0;2: initialize global event queue Q with {(alarm, t), (cancel, t)};3: while Q is not empty do4:remove earliest event e (ve , te ) from Q;5:t : te ;6:execute event e: update system state, generate possible future events, andadd them to Q, ordered by timestamps; possibly remove events from Q;7: end whileNon-determinism!IDifferent results depending on which of the two instantaneous events(alarm, t) and (cancel, t) is first removed from Q.Stavros Tripakis (UC Berkeley)EE 144/244, Fall 2016Discrete Event Simulation44 / 53
Dealing with Simultaneous EventsSourcecancelAlarmalarmSinkChronological ordering ( ordering by timestamps) of events in thequeue is not enough.Must also respect dependencies between simultaneous eventsIAlarm’s output event at time t depends on Source’s output event attime tHow to define event dependencies?Stavros Tripakis (UC Berkeley)EE 144/244, Fall 2016Discrete Event Simulation45 / 53
Dealing with Simultaneous EventsSourcecancelAlarmalarmSinkChronological ordering ( ordering by timestamps) of events in thequeue is not enough.Must also respect dependencies between simultaneous eventsIAlarm’s output event at time t depends on Source’s output event attime tHow to define event dependencies?First let’s formalize actor dependencies.Stavros Tripakis (UC Berkeley)EE 144/244, Fall 2016Discrete Event Simulation45 / 53
Dependency Relation among ActorsLet A1 , A2 be two actors in the DE model.Define the dependency relation A1 A2 (A2 depends on A1 ) as follows:A1 A2 b A1 is zero-delay (i.e., its output may have the sametimestamp as the input that produced it) and there is a connection froman output of A1 to an input of A2 .Stavros Tripakis (UC Berkeley)EE 144/244, Fall 2016Discrete Event Simulation46 / 53
Dependency Relation among ActorsLet A1 , A2 be two actors in the DE model.Define the dependency relation A1 A2 (A2 depends on A1 ) as follows:A1 A2 b A1 is zero-delay (i.e., its output may have the sametimestamp a
Timed Discrete Event Systems: deal with timed discrete-event signals. Timed discrete-event signal: sequence of timed events. continuous system time e 6 e 7 e 8 t 6 t 7 t 8 e 1 e 2 e 3 e 4 e 5 t 1 t 2 t 3 t 4 t 5 time system event discrete time time Stavros Tripakis (UC Berkeley) EE 144/244, Fa
Alexandre Donz e: EECS 144/244 { Continuous Systems Introduction 5 / 30. Today's course 1 Signals and Systems 2 Systems of Di erential Equations Modeling with ODEs Solutions of ODEs Alexandre Donz e: EECS 144/244 { Continuous Systems Introduction 6 / 30. Signals De nition A signal is a function from a time domain T to some domain D.
The VHF Frequencies Two Meters (2M) – 144 MHz to 148 MHz The Weak Signal part of the band is 144.0 MHz to about 144.5 MHz CW ONLY from 144.0 MHz to 144.1 MHz SSB Calling Frequency is 144.200 MHz RANGE– Modest station 150 –
Amtex Systems, Inc. 144 0 Amzur Technologies, Inc 144 14 Analysts International Corporation dba AIC Analysts Corporation 144 0 Apex Systems, Inc 144 30 . KMQ Enterprises, Inc. 144 39 Knovitas LLC 129 0 Latavco Consulting Group, LLC 93 39 Loblolly Consulting, LLC 103 29 Logic House, Ltd 144 54
FREQUENTLY ASKED QUESTIONS ABOUT RULE 144 AND RULE 145 Understanding Rule 144 under the Securities Act of 1933 What is Rule 144? Rule 144 permits public resales of the following, without having to register the resale with the Securities and Exchange Commission (the SEC): unregistered securities acquired directly from
1.25 in/33 mm Cable (OD) 18.2 mm Initial installation two 144-F cables Total capacity 2 x 144 F 288 F Figure 7. Standard 288-fiber loose tube cable placed in a standard duct compared to two 144-fiber cables placed in a microduct system Figure 8. Upgrade path utilizing a 144-fiber cable in microducts Figure 6. Payout of a 144-fiber MiniXtend .
List of Tables and Appendices ii r.144.2 Abstract vi r.144.3 1 Introduction 1 r.144.4 2 Methodology 7 r.144.5 3 Productivity of Teak Plantations 16 r.144.6 . available, no other money yield tables for teak in Kerala have since been published. Perhaps with teak prices changing on a monthly basis, money yield
CCC 100 Concrete Chemical corp. INCHRP # 244 Essais en cours Hydrozo 30M Sternson X INCHRP # 244 Melange de resine et silane Hdrozo 16 Sternson X INCHRP # 244 Krystol Silane Crete Construction INCHRP # 244 Sil
stock tank API gravity, separator pressure (psig), temperature ( F), and gas specific gravity, volume of produced hydrocarbons (bbls/day), molecular weight of the stock tank gas, VOC fraction of the tank emissions and atmospheric pressure (psia). The VBE estimates the dissolved GOR of a hydrocarbon solution as a function of the separator temperature, pressure, gas specific gravity, and liquid .
