EE382V: Embedded System Design And Modeling

EE382V:Embedded System Design and ModelingLecture 2 – Models of Computation, LanguagesAndreas GerstlauerElectrical and Computer EngineeringUniversity of Texas at Austingerstl@ece.utexas.edu

Lecture 2: Outline Overview Modeling, computational models, languages Models of Computation (MoCs) Process models State machine models System-Level Design Languages (SLDLs) Goals, requirements Communication and computationEE382V: Embedded Sys Dsgn and Modeling, Lecture 2 2008 A. Gerstlauer2

Modeling Design models as an abstraction of a design instance Representation (model) of some aspect of reality– Virtual prototyping of what has been decided Specification for further implementation/synthesis– Describe desired functionality of what still to build Usually a combination of both Different parts of the model or different use cases for the same model Needed in every step of the design process Documentation and specification of outputs and inputs Capability to capture complex systems Precise, complete and unambiguous Observability and predictability to reason about properties Validation through simulation Analysis through formal methodsEE382V: Embedded Sys Dsgn and Modeling, Lecture 2 2008 A. Gerstlauer3

Models of Computation (MoCs) Define a class of models Formal, abstract description of a system– Decomposition into pieces and their relationship– Well-defined objects and composition rules Various degrees of– supported features– complexity– expressive power Examples Sequential, imperative program models– Sequence of statements that manipulate program state Process models: networks, dataflow, calculi– Concurrency, data dependencies/causality State machine models: evolution from FSM to PSM– Control flow and state enumerationEE382V: Embedded Sys Dsgn and Modeling, Lecture 2 2008 A. Gerstlauer4

Models vs. ineSequent.programDataflowEnglishSpanishJapaneseCC JavaRecipes vs. EnglishSequential programs vs. C Computation models describe system behavior Conceptual notion, e.g., recipe, sequential program Languages capture models Concrete form, e.g., English, C Variety of languages can capture one model E.g., sequential program model C,C , Java One language can capture variety of models E.g., C sequential program model, object-orientedmodel, state machine model Certain languages better at capturing certain modelsSource: T. Givargis, F. Vahid. “Embedded System Design”, Wiley 2002.EE382V: Embedded Sys Dsgn and Modeling, Lecture 2 2008 A. Gerstlauer5

Text vs. Graphics Models versus languages not to be confused with textversus graphics Text and graphics are just two types of languages– Text: letters, numbers– Graphics: circles, arrows (plus some letters, numbers)X 1 X 1;if (N)Y X 1;N? Y X 1Source: T. Givargis, F. Vahid. “Embedded System Design”, Wiley 2002.EE382V: Embedded Sys Dsgn and Modeling, Lecture 2 2008 A. Gerstlauer6

Lecture 2: Outline Overview Models of Computation (MoCs) Process models– Process networks– Dataflow– Process calculi State machine models: evolution from FSM to PSM–––––Finite State Machine (FSM)FSM with Data (FSMD)Super-state FSMD.Program State Machine (PSM) System-Level Design Languages (SLDLs)EE382V: Embedded Sys Dsgn and Modeling, Lecture 2 2008 A. Gerstlauer7

Process Models Set of processes Processes execute in parallelProcess1Process2– Concurrent composition Each process is internally sequential– Imperative program Inter-process communication? Shared variables– Synchronization: critical section/mutex, monitor, Producer Message passing– Synchronous, rendezvous (blocking send)– Asynchronous, queues (non-blocking send)Consumer Examples: MPI, Java Implementation: OS processes or threads Single or multiple processors/coresEE382V: Embedded Sys Dsgn and Modeling, Lecture 2 2008 A. Gerstlauer8

Deadlocks Circular chain of 2 or more processes which each hold ashared resource that the next one is waiting for Circular dependency through shared resourcesm1.lock();m2.lock(); m2.unlock();m1.unlock();m2.lock();m1.lock(); m1.unlock();m2.unlock(); Prevent chain by using the same precedence Use timeouts (and retry), but: livelock Dependency can be created when resources are shared Side effects, e.g. when blocking on filled queues/buffersEE382V: Embedded Sys Dsgn and Modeling, Lecture 2 2008 A. Gerstlauer9

Non-determinism Deterministic: same inputs always produce same outputs Random: probability of certain behavior Non-deterministic: undefined behavior (for some inputs) Undefined execution order– Statement evaluation in imperative languages: f(a , a )– Concurrent process race conditions:x a;y b;a 1;b 2;x ?, y ? Can be desired or undesired How to ensure correctness? Simulator must typically pick one behavior But: over-specification? Leave freedom of implementation choiceEE382V: Embedded Sys Dsgn and Modeling, Lecture 2 2008 A. Gerstlauer10

Kahn Process Network (KPN) [Kahn74] C-like process description (Algol) Unbounded (infinite), uni-directional, point-to-pointFIFO queues (channels) for communication Sender (send()) never blocks Receiver (wait()) blocks until data available Deterministic Process can’t peek into channels and can only wait on onechannel at a time Output data produced by a process does not depend onthe order of its inputs Terminates on global deadlock: all process blocked onwait() Formal mathematical representation Process continuous function mapping input to outputstreamsEE382V: Embedded Sys Dsgn and Modeling, Lecture 2 2008 A. Gerstlauer11

Kahn Process Networks (KPN) (2) Turing-complete, undecidable (in finite time) Terminates? Can run in bounded buffers (memory)? Scheduling [Parks95] Start with smallest bounded buffers Schedule with blocking send() until (artificial) deadlock Increase size of smallest blocked buffer and continue Behavior does not depend on scheduling strategy Focus on causality, not order (implementation issue) Difficult to schedule (Park’s algorithm) Dynamic memory allocation Memory usage depends on scheduling strategyEE382V: Embedded Sys Dsgn and Modeling, Lecture 2 2008 A. Gerstlauer12

Dataflow Networks Breaking processes down into network of actors Atomic blocks of computation, executed when firing Fire when required number of input tokens are available– Consume required number of tokens on input(s)– Produce number of tokens on output(s) Separate computation & communication/synchronization Actors (indivisible units of computation) may fire simultaneously, any order Tokens (units of communication) can carry arbitrary pieces of data Unbounded FIFOs on arcs between actorsf1()f2()f3()f4() Signal-processing applicationsEE382V: Embedded Sys Dsgn and Modeling, Lecture 2 2008 A. Gerstlauer13

Synchronous Dataflow (SDF) [Lee86] Fixed number of tokens per firing Consume fixed number of inputs Produce fixed number of outputs1a21b221c812dInitialization Delay Prevent deadlock2 Can be scheduled statically Solve system of linear equations for relative rates Periodically schedule actors in proportion to their rates Find a sequence of firings in each period Trade-off code size and buffer sizes– Single-appearance vs. memory-minimal scheduleEE382V: Embedded Sys Dsgn and Modeling, Lecture 2 2008 A. Gerstlauer14

Process Calculi Rendezvous-style, synchronous communication Communicating Sequential Processes (CSP) [Hoare78] Calculus of Communicating Systems (CCS) [Milner80] Formal, mathematical framework: process algebra Algebra objects, operations, axioms – Objects: processes (P, Q), events (a, b)– Composition operators: parallel (P Q), prefix/input (a P), choice (P Q)– Axioms: indemnity (Ø P P), reduction (a P a Q P Q) Manipulate processes by manipulating expressions Examples: LOTOS, Occam (Transputer),HandleC (Celoxica)EE382V: Embedded Sys Dsgn and Modeling, Lecture 2 2008 A. Gerstlauer15

Lecture 2: Outline Overview Models of Computation (MoCs) Process models Process networks Dataflow Process calculi State machine models: evolution from FSM to PSM–––––Finite State Machine (FSM)FSM with Data (FSMD)Super-state FSMD.Program State Machine (PSM) System-Level Design Languages (SLDLs)EE382V: Embedded Sys Dsgn and Modeling, Lecture 2 2008 A. Gerstlauer16

State Machine Models Finite State Machine (FSM) Basic model for describing control States and state transitions– FSM S, I, O, f, h Two types:– Mealy-type FSM (input-based)– Moore-type FSM (state-based)S1S2S3FSM modelSource: R. Doemer, UC IrvineEE382V: Embedded Sys Dsgn and Modeling, Lecture 2 2008 A. Gerstlauer17

State Machine Models Finite State Machine (FSM) Data Flow Graph (DFG) Basic model for describing computation (variant of SDF) Directed graph– Nodes: operations– Arcs: dependency of operationsOp1Op2Op3Op4Op5Op6DFG modelSource: R. Doemer, UC IrvineEE382V: Embedded Sys Dsgn and Modeling, Lecture 2 2008 A. Gerstlauer18

State Machine Models Finite State Machine (FSM) Data Flow Graph (DFG) Finite State Machine with Data (FSMD) Combined model for control and computation– FSMD FSM DFG Implementation: controller plus D modelEE382V: Embedded Sys Dsgn and Modeling, Lecture 2Source: R. Doemer, UC Irvine 2008 A. Gerstlauer19

State Machine Models Finite State Machine (FSM)Data Flow Graph (DFG)Finite State Machine with Data (FSMD)Super-State FSM with Data (SFSMD) FSMD with complex, multi-cycle states– States described by procedures in a programming languagea a b;c c d;PS1a 42;while (a 100){ b b a;if (b 50)c c d;a a c;}PS2PS3a 42;b a * 2;for(c 0; c 100; c ){ b c a;if (b 0)b -b;elseb b 1;a b * 10;}SFSMD modelEE382V: Embedded Sys Dsgn and Modeling, Lecture 2Source: R. Doemer, UC Irvine 2008 A. Gerstlauer20

State Machine Models Finite State Machine (FSM)Data Flow Graph (DFG)Finite State Machine with Data (FSMD)Super-State FSM with Data (SFSMD)Hierarchical Concurrent FSM (HCFSM) FSM extended with hierarchy and concurrency– Multiple FSMs composed hierarchically (OR) and in parallel (AND) Example: StateCharts (graphical), Esterel/Lustre (textual) Synchronous (lock-step) composition of concurrent FSMsS1S3S5HCFSM modelS2S4Source: R. Doemer, UC IrvineEE382V: Embedded Sys Dsgn and Modeling, Lecture 2 2008 A. Gerstlauer21

State Machine Models Finite State Machine (FSM)Data Flow Graph (DFG)Finite State Machine with Data (FSMD)Super-State FSM with Data (SFSMD)Hierarchical Concurrent FSM (HCFSM)Program State Machine (PSM) HCFSMD plus programming language– States described by proceduresin a programming language Example: SpecC!PS1PS3PS5PSM modelPS2PS4.a 42;while (a 100){ b b a;if (b 50)c c d;elsec c e;a c;}.Source: R. Doemer, UC IrvineEE382V: Embedded Sys Dsgn and Modeling, Lecture 2 2008 A. Gerstlauer22

Lecture 2: Outline Overview Models of Computation (MoCs) Process models State machine models System-Level Design Languages (SLDLs) Goals, requirements Communication and computationEE382V: Embedded Sys Dsgn and Modeling, Lecture 2 2008 A. Gerstlauer23

Design Languages Represent a model in machine-readable form Apply algorithms and tools Syntax provides the handle Grammar defines possible strings over an alphabetSemantics connects/maps strings to a model Operational semantics– Defined through execution of an abstract state machine Denotational semantics– Define through mapping into a mathematical domain (e.g. functions) General underlying model of computation Discrete-event semantics as common denominator– Event (value, tag) tuples– Signal sequence of events– Ordering of tags (time) defines order of events Able to represent different MoCs Defines interpretation of language into other MoCsEE382V: Embedded Sys Dsgn and Modeling, Lecture 2 2008 A. Gerstlauer24

Simulation vs. Synthesis Ambiguous semantics of languages3.4152.715--Finite state machinecase X iswhen X1 .when X2 --Look-up tableControllerMemory Simulatable but not synthesizable or verifiable Impossible to automatically discern implicit meaning Need explicit set of constructsSource: D. Gajski, UC IrvineEE382V: Embedded Sys Dsgn and Modeling, Lecture 2 2008 A. Gerstlauer25