Discrete Event uExplicit notion of time global order uDE simulator maintains a global event queue Verilog Verilog and VHDL uDrawbacks s global event queue tight coordination between parts s Simultaneous events nonnon deterministic behavior uSome simulators use delta delay to prevent nonnon determinacy 1 Simultaneous Events in DE t A t B C B has 0 delay Fire B or C B has delta delay t A B t t C Fire C once or twice Can be refined E g introduce timing constraints minimum reaction time 0 1 s A B t C Fire C twice Still have problem with 00 delay causality loop 2 Outline uSynchrony and asynchrony uCFSM definitions s Signals networks s Timing behavior s Functional behavior uCFSM process networks uExample of CFSM behaviors s Equivalent classes 3 Codesign Finite State Machine uUnderlying MOC of Polis uCombine aspects from several other MOCs uPreserve formality and efficiency in implementation uMix s synchronicity t s zero and infinite time asynchronicity t non zero finite and bounded time non uEmbedded systems often contain both aspects 4 Synchrony Basic Operation u Synchrony is often implemented with clocks u At clock ticks u s Module reads inputs computes and produce output s All synchronous events happen simultaneously s Zero delay computations Zero Between clock ticks s Infinite amount of time passed 5 Synchrony Basic Operation 2 u u Practical implementation of synchrony s Impossible to get zero or infinite delay s Require computation time clock period s Computation time 0 w r t reaction time of environment Feature of synchrony s Functional behavior independent of timing t s Simplify verification Cyclic dependencies may cause problem t Among simultaneous synchronous events 6 Synchrony Triggering and Ordering u All modules are triggered at each clock tick u Simultaneous signals s No a priori ordering s Ordering may be imposed by dependencies t Implemented with delta steps delta steps computation ticks continuous time 7 Synchrony System Solution uSystem solution s Output reaction to a set of inputs uWell Well designed system s Is completely specified and functional s Has an unique solution at each clock tick s Is equivalent to a single FSM s Allows efficient analysis and verification uWell Well design design ness s May need to be checked for each design Esterel t Cyclic dependency among simultaneous events 8 Synchrony Implementation Cost uMust verify synchronous assumption on final design s May be expensive uExamples s Hardware t Clock cycle maximum computation time u s Inefficient for average case Software t Process must finish computation before u u New input arrival Another process needs to start computation 9 Asynchrony Basic Operation uEvents are never simultaneous s No two events have the same tag uComputation starts at a change of the input uDelays are arbitrary but bounded 10 Asynchrony Triggering and Ordering uEach module is triggered to run at a change of input uNo a priori ordering among triggered modules s May be imposed by scheduling at implementation 11 Asynchrony System Solution uSolution strongly dependent on input timing uAt implementation s Events may appear simultaneous s Difficult expensive to maintain total ordering t t Ordering at implementation decides behavior Becomes DE with the same pitfalls 12 Asynchrony Implementation Cost uAchieve low computation time average s Different parts of the system compute at different rates uAnalysis is difficult s Behavior depends on timing s Maybe be easier for designs that are insensitive to t t Internal delay External timing 13 Asynchrony vs Synchrony in System Design uThey are different at least at s Event buffering s Timing of event read write uAsynchrony s Explicit buffering of events for each module t Vary and unknown at startstart time uSynchrony s One global copy of event t Same start time for all modules 14 Combining Synchrony and Asynchrony uWants to combine s Flexibility of asynchrony s Verifiability of synchrony uAsynchrony s Globally a timing independent style of thinking uSynchrony s Local portion of design are often tightly synchronized uGlobally asynchronous locally synchronous s CFSM networks 15 CFSM Overview uCFSM is FSM extended with s Support for data handling s Asynchronous communication uCFSM has s FSM part t s Inputs outputs states transition and output relation Data computation part t External instantaneous functions 16 CFSM Overview 2 uCFSM has s Locally synchronous behavior t t s CFSM executes based on snapsnap shot input assignment Synchronous from its own perspective Globally asynchronous behavior t t CFSM executes in nonnon zero finite amount of time Asynchronous from system perspective uGALS model s Globally Scheduling mechanism s Locally CFSMs 17 Network of CFSMs CFSMs DepthDepth 1 Buffers uGlobally Asynchronous Locally Synchronous GALS model F B C C F G C G C G CFSM1 CFSM1 C A F G 1 C CFSM2 CFSM2 C C B A C B B A 0 B CFSM3 12 09 1999 18 Introducing a CFSM uA Finite State Machine uInput events output events and state events uInitial values for state events uA transition function Transitions may involve complex memorymemory less instantaneous arithmetic and or Boolean functions All the state of the system is under form of events uNeed rules that define the CFSM behavior 19 CFSM Rules phases uFour Four phase cycle Idle Detect input events Execute one transition Emit output events uDiscrete time s Sufficiently accurate for synchronous systems s Feasible formal verification uModel semantics Timed Traces i e sequences of events labeled by time of occurrence 20 CFSM Rules phases uImplicit unbounded delay between phases uNon Non zero reaction time avoid inconsistencies when interconnected uCausal model based on partial order global asynchronicity asynchronicity s potential verification speedspeed up uPhases may not overlap uTransitions always clear input buffers local synchronicity 21 Communication Primitives uSignals s Carry information in the form of events and or values t t Event signals present absence Data signals arbitrary values u s Event data may be paired Communicate between two CFSMs t 1 input buffer signal receiver s Emitted by a sender CFSM s Consumed by a receiver CFSM by setting buffer to 0 s Present if emitted but not consumed 22 Communication Primitives 2 uInput assignment s A set of values for the input signals of a CFSM uCaptured input assignment s A set of input values read by a CFSM at a particular time uInput stimulus s Input assignment with at least one event present 23 Signals and
View Full Document
Unlocking...