8m ago

18 Views

1 Downloads

287.18 KB

42 Pages

Transcription

EE382V:Embedded System Design and ModelingLecture 2 – Models of Computation, LanguagesAndreas GerstlauerElectrical and Computer EngineeringUniversity of Texas at [email protected]

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

System-Level Design Languages (SLDLs) Goals Executability– Validation through simulation Synthesizability– Implementation in HW and/or SW– Support for IP reuse Modularity– Hierarchical composition– Separation of concepts Completeness– Support for all concepts found in embedded systems Orthogonality– Orthogonal constructs for orthogonal concepts– Minimality SimplicitySource: R. Doemer, UC IrvineEE382V: Embedded Sys Dsgn and Modeling, Lecture 2 2008 A. Gerstlauer26

System-Level Design Languages (SLDLs) ilVeLDVHvaJa tionsCompositedata typesnot supportedpartially supportedsupportedSource: R. Doemer, UC IrvineEE382V: Embedded Sys Dsgn and Modeling, Lecture 2 2008 A. Gerstlauer27

System-Level Design Languages (SLDLs) Examples in use today C/C – ANSI standard programming languages, software design– traditionally used for system design because of practicality, availability SystemC– C API and library– initially developed at UCI, supported by Open SystemC Initiative SpecC– C extension– developed at UCI, supported by SpecC Technology Open Consortium SystemVerilog– Verilog with C extensions Matlab– specification and simulation in engineering, algorithm design UML– unified modeling language, software specification, graphical SDL– telecommunication area, standard by ITU, used in COSMOS SLDL– formal specification of requirements, not executable etc.Source: R. Doemer, UC IrvineEE382V: Embedded Sys Dsgn and Modeling, Lecture 2 2008 A. Gerstlauer28

Separation of Concerns Fundamental principle in modeling of systems Clear separation of concerns address separate issues independently System-Level Description Language (SLDL) orthogonal concepts orthogonal constructs System-level Modeling Computation– encapsulated in modules / behaviors Communication– encapsulated in channelsSource: R. Doemer, UC IrvineEE382V: Embedded Sys Dsgn and Modeling, Lecture 2 2008 A. Gerstlauer29

Computation vs. Communication Traditional modelP1P2s1s2s3 Processes and signals Mixture of computation and communication Automatic replacement impossibleSource: R. Doemer, UC IrvineEE382V: Embedded Sys Dsgn and Modeling, Lecture 2 2008 A. Gerstlauer30

Computation vs. Communication Traditional modelP1P2s1s2s3 Processes and signals Mixture of computation and communication Automatic replacement impossible SpecC modelC1B1v1B2v2v3 Behaviors and channels Separation of computation and communication Plug-and-playSource: R. Doemer, UC IrvineEE382V: Embedded Sys Dsgn and Modeling, Lecture 2 2008 A. Gerstlauer31

Computation vs. Communication Protocol Inlining Specification model Exploration modelC1B1B2v1v2v3– Computation in behaviors– Communication in channelsSource: R. Doemer, UC IrvineEE382V: Embedded Sys Dsgn and Modeling, Lecture 2 2008 A. Gerstlauer32

Computation vs. Communication Protocol Inlining Specification model Exploration modelC1B1B2v1v2v3– Computation in behaviors– Communication in channels Implementation modelB1B2v1v2v3– Channel disappears– Communication inlined into behaviors– Wires exposedSource: R. Doemer, UC IrvineEE382V: Embedded Sys Dsgn and Modeling, Lecture 2 2008 A. Gerstlauer33

Intellectual Property (IP) Computation IP: Wrapper modelBv1IPv2SynthesizablebehaviorIP in wrapperSource: R. Doemer, UC IrvineEE382V: Embedded Sys Dsgn and Modeling, Lecture 2 2008 A. Gerstlauer34

Intellectual Property (IP) Computation IP: Wrapper modelBTv1replacableat any timeSynthesizablebehaviorIPv2TransducerIP in wrapperSource: R. Doemer, UC IrvineEE382V: Embedded Sys Dsgn and Modeling, Lecture 2 2008 A. Gerstlauer35

Intellectual Property (IP) Computation IP: Wrapper modelBTv1replacableat any timeIPv2SynthesizablebehaviorIP in wrapperTransducer Protocol inlining with wrapperB1B1v1IPv2beforev1IPv2afterSource: R. Doemer, UC IrvineEE382V: Embedded Sys Dsgn and Modeling, Lecture 2 2008 A. Gerstlauer36

Intellectual Property (IP) Computation IP: Adapter modelBTv1replacableat any ource: R. Doemer, UC IrvineEE382V: Embedded Sys Dsgn and Modeling, Lecture 2 2008 A. Gerstlauer37

Intellectual Property (IP) Computation IP: Adapter modelBTIPAv1replacableat any timev2SynthesizablebehaviorTransducerAdapterIP Protocol inlining with adapterB1IPAB1IPv1v1v2v2beforeafterSource: R. Doemer, UC IrvineEE382V: Embedded Sys Dsgn and Modeling, Lecture 2 2008 A. Gerstlauer38

Intellectual Property (IP) Communication IP: Channel with wrapperC1C2v1v2replacableat any timeIPv3Virtual channelIP protocol channel in wrapperSource: R. Doemer, UC IrvineEE382V: Embedded Sys Dsgn and Modeling, Lecture 2 2008 A. Gerstlauer39

Intellectual Property (IP) Communication IP: Channel with wrapperC1C2v1replacableat any timev2IPv3IP protocol channel in wrapperVirtual channel Protocol inlining with hierarchical channelB1B2B1B2v1v1v2v2beforeafterSource: R. Doemer, UC IrvineEE382V: Embedded Sys Dsgn and Modeling, Lecture 2 2008 A. Gerstlauer40

Intellectual Property (IP) Incompatible busses: Transducer em busTransducerAdapterIP busIPSource: R. Doemer, UC IrvineEE382V: Embedded Sys Dsgn and Modeling, Lecture 2 2008 A. Gerstlauer41

Intellectual Property (IP) Incompatible busses: Transducer em busTransducerAdapterIP busIP Protocol inlining with transducerB1Tv1IPv4v2v5v3afterSource: R. Doemer, UC IrvineEE382V: Embedded Sys Dsgn and Modeling, Lecture 2 2008 A. Gerstlauer42

EE382V: Embedded Sys Dsgn and Modeling, Lecture 2 2008 A. Gerstlauer 6 Text vs. Graphics Models versus languages not to be confused with text versus graphics Text and graphics are just two types of languages – Text: letters, numbers – Graphics: circles, arrows (plus some letters, numbers) Source: T. Givargis, F. Vahid.