Berkeley ELENG C249A - Models of Computation for Embedded System Design

Unformatted text preview:

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 BoniventoOutlineGoalsMOCsDiscrete EventsDataflow Process NetworksPetri NetsSynchronous/ReactiveCommunicating Synchronous FSMLabeled Transition SystemsSDL Process NetworksHybrid SystemsCFSMConclusionsGoalsFirst step in embedded system design: specification processFormal representation helpsMOCs: efficiency, formal verification, design refinement, optimization and implementationTSM: framework to compare MOCsMOCsA 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   TTTMIfMfIM01001000001011101000101010011000100010010000100100001010000011111000001310,, ttt0IfMM 1Synchronous/ReactiveAll signals have events with identical tags (synchronous)All signals have events at every clock tickCycle based models (clocked-synchronous circuit)EsterelSynchronous & MultirateWCDMA cell simulatorsUser 1User 2User NDSPBase StationCommunicating Synchronous FSMFSM 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 statesSynchronousSequential behavior vs. state explosion–Hierarchy, concurrency, non-determinismOther modelsLabeled Transition Systems (LTS)–CSP, CCS–Communication is based on rendevouz–Single LTS is an interleaved asynchronous modelSDL Process Networks–Specification, simulation and design of TLC protocolsHybrid 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.CFSMGlobally 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.CFSMTiming 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 2ConclusionsNo 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

Berkeley ELENG C249A - Models of Computation for Embedded System Design

Documents in this Course
Load more
Download Models of Computation for Embedded System Design
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Models of Computation for Embedded System Design and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Models of Computation for Embedded System Design 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?