Outline Part 3 Models of Computation FSMs Discrete Event Systems CFSMs Data Flow Models Petri Nets The Tagged Signal Model 1 Discrete Event Explicit notion of time global order Events can happen at any time asynchronously As soon as an input appears at a block it may be executed The execution may take non zero time the output is marked with a time that is the sum of the arrival time plus the execution time Time determines the order with which events are processed DE simulator maintains a global event queue Verilog and VHDL Drawbacks global event queue tight coordination between parts Simultaneous events non deterministic behavior Some simulators use delta delay to prevent non determinacy 2 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 0 delay causality loop 3 Outline Part 3 Models of Computation FSMs Discrete Event Systems CFSMs Data Flow Models Petri Nets The Tagged Signal Model 4 Co Design Finite State Machines Combining FSM and Discrete Event Synchrony and asynchrony CFSM definitions Signals networks Timing behavior Functional behavior CFSM process networks Example of CFSM behaviors Equivalent classes 5 Codesign Finite State Machine Underlying MOC of Polis and VCC Combine aspects from several other MOCs Preserve formality and efficiency in implementation Mix synchronicity zero and infinite time asynchronicity non zero finite and bounded time Embedded systems often contain both aspects 6 Synchrony Basic Operation Synchrony is often implemented with clocks At clock ticks Module reads inputs computes and produce output All synchronous events happen simultaneously Zero delay computations Between clock ticks Infinite amount of time passed 7 Synchrony Basic Operation 2 Practical implementation of synchrony Impossible to get zero or infinite delay Require computation time clock period Computation time 0 w r t reaction time of environment Feature of synchrony Functional behavior independent of timing Simplify verification Cyclic dependencies may cause problem Among simultaneous synchronous events 8 Synchrony Triggering and Ordering All modules are triggered at each clock tick Simultaneous signals No a priori ordering Ordering may be imposed by dependencies Implemented with delta steps delta steps computation ticks continuous time 9 Synchrony System Solution System solution Output reaction to a set of inputs Well designed system Is completely specified and functional Has an unique solution at each clock tick Is equivalent to a single FSM Allows efficient analysis and verification Well designed ness May need to be checked for each design Esterel Cyclic dependency among simultaneous events 10 Synchrony Implementation Cost Must verify synchronous assumption on final design May be expensive Examples Hardware Clock cycle maximum computation time Inefficient for average case Software Process must finish computation before New input arrival Another process needs to start computation 11 Pure Asynchrony Basic Operation Events are never simultaneous No two events have the same tag Computation starts at a change of the input Delays are arbitrary but bounded 12 Asynchrony Triggering and Ordering Each module is triggered to run at a change of input No a priori ordering among triggered modules May be imposed by scheduling at implementation 13 Asynchrony System Solution Solution strongly dependent on input timing At implementation Events may appear simultaneous Difficult expensive to maintain total ordering Ordering at implementation decides behavior Becomes DE with the same pitfalls 14 Asynchrony Implementation Cost Achieve low computation time average Different parts of the system compute at different rates Analysis is difficult Behavior depends on timing Maybe be easier for designs that are insensitive to Internal delay External timing 15 Asynchrony vs Synchrony in System Design They are different at least at Event buffering Timing of event read write Asynchrony Explicit buffering of events for each module Vary and unknown at start time Synchrony One global copy of event Same start time for all modules 16 Combining Synchrony and Asynchrony Wants to combine Flexibility of asynchrony Verifiability of synchrony Asynchrony Globally a timing independent style of thinking Synchrony Local portion of design are often tightly synchronized Globally asynchronous locally synchronous CFSM networks 17 CFSM Overview CFSM is FSM extended with Support for data handling Asynchronous communication CFSM has FSM part Inputs outputs states transition and output relation Data computation part External instantaneous functions 18 CFSM Overview 2 CFSM has Locally synchronous behavior CFSM executes based on snap shot input assignment Synchronous from its own perspective Globally asynchronous behavior CFSM executes in non zero finite amount of time Asynchronous from system perspective GALS model Globally Scheduling mechanism Locally CFSMs 19 Network of CFSMs Depth 1 Buffers Globally Asynchronous Locally Synchronous GALS model F B C C F G C G C G CFSM1 CFSM1 C A C CFSM2 CFSM2 C C B A B C B 12 09 1999 F G 1 A 0 B CFSM3 20 Introducing a CFSM A Finite State Machine Input events output events and state events Initial values for state events A transition function Transitions may involve complex memory less instantaneous arithmetic and or Boolean functions All the state of the system is under form of events Need rules that define the CFSM behavior 21 CFSM Rules phases Four phase cycle Idle Detect input events Execute one transition Emit output events Discrete time Sufficiently accurate for synchronous systems Feasible formal verification Model semantics Timed Traces i e sequences of events labeled by time of occurrence 22 CFSM Rules phases Implicit unbounded delay between phases Non zero reaction time avoid inconsistencies when interconnected Causal model based on partial order global asynchronicity potential verification speed up Phases may not overlap Transitions always clear input buffers local synchronicity 23 Communication Primitives Signals Carry information in the form of events and or values Event signals present absence Data signals arbitrary values Event data may be paired Communicate between two CFSMs 1 input buffer signal receiver Emitted by a sender CFSM Consumed by a receiver CFSM by setting buffer to 0 Present if emitted but not
View Full Document
Unlocking...