Models of Computation for Embedded System DesignOutlineGoalsMOCsDiscrete Event (DE)Dataflow Process NetworksPetri NetsPetri Nets: exampleSynchronous/ReactiveSynchronous & MultirateCommunicating Synchronous FSMOther modelsSynchrony vs. AsynchronyCFSMSlide 15CFSM: exampleConclusionsModels of Computation for Embedded System Design Alvise BoniventoOutlineGoalsMOCsDiscrete EventsDataflow Process NetworksPetri NetsSynchronous/ReactiveCommunicating Synchronous FSMLabeled Transition SystemsSDL Process NetworksHybrid SystemsCFSMConclusionsGoalsFirst step in embedded system design: specification processFormal representation helpsMOCs: efficiency, formal verification, design refinement, optimization and implementationTSM: framework to compare MOCsMOCsA mathematical description that has a syntax and rules for computation of the behavior described by the syntax (semantics). Used to specify the semantics of computation and concurrency.Characteristics: compact description, fidelity to design style, synthesize and optimize behavior to an implementation.Language & MOCs: MOC affects expressiveness, trade off.Discrete Event (DE)•Totally ordered events•Digital Hardware simulators: Verilog, VHDL.•Efficient for large systems, but challenged by simultaneous eventsA B C A B CA B C A B Ctttttt+Δ t+Δ•VHDL: delta step solutionDataflow Process Networks•Directed graph: actors, streams and tokens•Process sequence of firings•Firings organized into a list and scheduled•One cycle through the schedule back to original state •DSP problemsA C DB A B C DPetri Nets•Process control, asynchronous communication and scheduling: avoids state explosiontokenplacetransition•The state of a PN is the marking•Transition fire when all the predecessors are marked•When firing occurs, the predecessors decrement their marking and the successors increase it.p0p1p2p3 p4p5p6t0t1 t2t3t4t5t6Petri Nets: examplep0p1p2p3 p4p5p6t0t1 t2t3t4t5t6 TTTMIfMfIM01001000001011101000101010011000100010010000100100001010000011111000001310,, ttt0IfMM 1Synchronous/ReactiveAll signals have events with identical tags (synchronous)All signals have events at every clock tickCycle based models (clocked-synchronous circuit)EsterelSynchronous & MultirateWCDMA cell simulatorsUser 1User 2User NDSPBase StationCommunicating Synchronous FSMFSM consists of:–Set of input symbols–Set of output symbols–Finite set of states with an initial state–Input symbols & states output symbols–Input symbols & states next statesSynchronousSequential behavior vs. state explosion–Hierarchy, concurrency, non-determinismOther modelsLabeled Transition Systems (LTS)–CSP, CCS–Communication is based on rendevouz–Single LTS is an interleaved asynchronous modelSDL Process Networks–Specification, simulation and design of TLC protocolsHybrid Systems–FA where each state is associated with a set of differential equations–When inequalities are satisfied transition may fire–Non-linear dynamic systemsSynchrony vs. Asynchrony Basic operation: at each clock tick, each module reads inputs, computes and produces outputs simultaneously.Triggering & Ordering: all modules are triggered to compute at every clock tick.System solution: unique solution at each clock tick, , makes verification makes verification easiereasier.Implementation cost: may be expensiveexpensive, clock rate not optimized. Basic operation: events with a non-zero amount of time between them, each process may take an arbitrary time.Triggering & Ordering: triggered to run only when inputs change.System solution: difficult to difficult to analyzeanalyze.Implementation cost: cheapercheaper and more flexiblemore flexible.CFSMGlobally asynchronous, locally synchronous (GALS).POLIS.CFSM has:–A finite state machine part: inputs, outputs, states, transition and output relation.–A data computation part: reference in the transition relation to external, combinational functions.–Locally synchronous behavior: each CFSM executes a transition by producing a single output reaction in zero time.–Globally asynchronous behavior: each CFSM reads inputs, executes a transition and produces outputs in an unbounded but finite amount of time. Asynchronous interaction from a system perspective.CFSMTiming behavior:–a global scheduler controls the interaction of the CFSMs.–During an execution a CFSM reads its inputs, performs a computation, possibly changes states and writes its outputs.–Each input signal is read at most once,each input event is cleared at every execution.–Input events are read atomically.Functional behavior:–Determined by the specified transition relation (TR)CFSM: exampleABCioi1i2err•Inputs arrive at a regular rate of Ni time units.•Each CFSM process at a regular rate of Nr if no errors or 2Nr in case of errors.•No missed event constraint.NrNi 2ConclusionsNo single agreed upon standard MOC.CFSM with initially unbounded FIFO buffers:–GALS–Unbounded buffers allows static and quasi static scheduling whenever possible.–Keep buffers lossy in the formal model and give the designer tools to verify a priori if any loss occurs.–Enforce no loss for some buffers in the implementation.–Capture most of the features of the different MOCs.Multiple languages with semantics in terms of CFSMs:–Multiple scheduling, allocation, partitioning, HW & SW synthesis algorithm can be applied. Formal verification throughout the design
View Full Document