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