Unformatted text preview:

EE249 LectureTaken fromRoberto Passerone PhD ThesisHeterogeneous Models of Computation: An Abstract Algebra ApproachObjectives Provide the foundation to represent different semantic domains for the Metropolis metamodel Study the problem of heterogeneous interaction Formalize concepts such as abstraction and refinementAn Example of Interaction Combine a synchronous model with a dataflow model Synchronous model Total order of event Data flow model Partial order of events Discrete Time model Metric order of eventsAn Example of Heterogeneous Interaction The interaction is derived from a common refinementof the heterogeneous models The resulting interaction depends on the particular refinements employed Our objective is to derive the consequences of the interaction at the higher levels of abstractionData Flow Model Assume signals take values from a set V Each signal is a sequence from V (an element of V*) Let A be the set of signals One behavior is a function f : A  V* A data-flow agent is a set of those behaviorsa b c d ……………………………Data flowe f g h ……………………………i j k l ……………………………Synchronous Model Signals are again sequences from V (elements of V*)… But are synchronized One element of the sequence is g : A  V One behavior is a sequence of those functions <gi>  ( A  V )* A synchronous agent is a set of those sequences………g1………g2………g3………g4…SynchronousDiscrete Time Model Assume time is represented by the positive integers N Then define a behavior h: N  ( A  V ) A discrete time agent is a set of those functions………1………2………3………4…Discrete TimeDiscrete to Synchronous AbstractionSynchronousDiscreteba b c e egg j j l mon p p r s* * * *a b eg j ln p rDiscrete to Data Flow AbstractionData flowDiscreteba b c e egg j j l mon p p r sb a c eg j l mon p r sb a c eg j l mon p r sInteraction PropagationSynchronousData flowDiscreteT1T2V1V2VW1W2U1U21. Refinement2. Composition3. Projection4. AbstractionObjectives Provide a semantic foundations for integrating different models of computation Independent of the design language Not just specific to the Metropolis meta-model Maximize flexibility for using different levels of abstraction For different parts of the design At different stages of the design process For different kinds of analysis Support many forms of abstraction Model of computation (model of time, synchronization, etc.) Scoping Structure (hierarchy)OverviewP1P2MSP1.pZ.write()  P2.pX.read()pXpZ pX pZM’ M’Meta ModelPre-PostProcess NetworksData FlowDiscrete TimeNon-metric TimeContinuous TimeAgent AlgebrasConservative ApproximationsDomain of agents with operations: projection, renaming and compositionScope Concentrate on Natural semantic domains (sets of agents) Relations and functions over semantic domains Relationships between semantic domains and their relations and functions Defer worrying about specific abstract syntaxes and semantic functions Convenient for manual, formal reasoning De-emphasizing executable and finitely-representable models (for now)Agents and Behaviors For each model of computation we always distinguish between the domain of individual behaviors the domain of agents For different models of computation individual behaviors can be very different mathematical objects We always call these objects traces The nature of the elements of the carrier is irrelevant! An agent is primarily a set P of traces We call them trace structures Also includes the signature: T = ( , P )Trace structure algebraCompositionScopingInstantiationTrace algebraProjectionRenamingConcatenationTrace and Trace Structure AlgebrasModel of individual behaviorsModel of agents(semantic domain)A trace structurecontains a setof tracesSet of tracesCSet of tracestructuresAEssential Elements Must be able to name elements of the model Variables, actions, signals, states We do not distinguish among them and refer to them collectively as a set of signals W Each agent has an alphabet and a signature Alphabet: A  W Signature:  = A,  = ( I, O ), etc. The operations on traces and trace structures must satisfy certain axioms The axioms formalize the intuitive meaning of the operations They also provide hypothesis used in proving theorems Trade-off between generality and structureMetric Time Traces = ( VR , VN , MI , MO)x =( , d, f )f( v ) = [ 0, d ] -> Rf( n ) = [ 0, d ] -> Nf( a ) = [ 0, d ] -> { 0, 1 } Model time as a metric space Can talk about the difference in time between points in the behavior in quantitative terms Able to specify timing constraints in quantitative terms Able to represent continuous as well as discrete behavior Projection and renaming easily defined on the functionsMetric Time Model: Traces A trace x models one execution of a hybrid system: Signature  = ( VR: real valued var’s,VN: integer valued var’s,MI: input actions,MO: output actions) The alphabet A of x is the union of the components of  d is a non-negative real number Length (in time) of x Can be infinity f gives values as a function of time:f: VR--> [0, d] --> R,f: VN--> [0, d] --> N,f: MI--> [0, d] --> {0, 1},f: MO--> [0, d] --> {0, 1}.Metric Time Model: Operations on Traces Let x’ = proj(B)(x) represents scoping B is a subset of A ’ and f’ are restricted to variables and actions in B d’ = d Let x’ = rename(r)(x) represents instantiation r is a one-to-one function with domain A variables and actions in ’ and f’ are renamed by r d’ = d Let x’’ = x • x’ (concatenation) represents sequential composition ’ = , d is finite, and end of x matches beginning of x’ ’’ =  d’’ = d + d’ f’’(v, t) is equal tof(v, t) for t  df’(v, t - d) for t  dMetric Time Model: Trace Structures A trace structure T = (, P) models a process or an agent of a hybrid system P is a set of traces with signature Traits: T refines T’ if P  P’ Natural model for physical components (such as those described with differential equations, possibly with discrete control variables) Too detailed for many other aspects of embedded systems Not a finite


View Full Document

Berkeley ELENG C249A - Heterogeneous Models of Computation:

Documents in this Course
Load more
Download Heterogeneous Models of Computation:
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 Heterogeneous Models of Computation: 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 Heterogeneous Models of Computation: 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?