Comparing Models of ComputationEdward A. Lee Alberto Sangiovanni- V...UC Berkeley Dept. of EECSMajor Collaborators:G. Berry W. T. Chang S. Edwards A. Girault L. Lava...Design Methodology Design is a human creative process. CAD system designers are toolsmiths, but ... They are not as much constrained by the laws of ... Can use instead the laws of logic (or anything e...A design environment is an artificial universe. It...An Artificial UniverseNot so long ago, electronic systems were literal e...Today, layers of abstraction hide the electromecha...Our metaphors are still too close to the physics.AbstractionAbstraction in system-level design is the act of p...... getting closer to the problem domain.... avoiding overspecification.Less Abstract, Closer to the PhysicalStill Less AbstractValidating Designs By construction property is inherent. By verification property is provable syntactically. By simulation check behavior for all inputs. By intuition property is true. I just know it is. By assertion property is true. Wanna make something of it?It is generally better to be higher in this listSome Models of ComputationSemantics — What does it Mean?This well-established field addresses many of the ...Issues Concurrency Synchronization A model of time Turing completeness Determinacy Finite state RedundancyUsefulness of a Model of Computation Expressiveness Generality Simplicity Compilability/Synthesizability VerifiabilityThe ConclusionOne way to get all of these is to mix diverse, sim...What is Time?Totally-Ordered Discrete-Event ModelsExamples of the sorts of problems that arise from ...The Tagged Signal ModelA mathematical framework within which the essentia...A denotational framework.Events and SignalsAbstractions of time give us tools to deal with th... set of values set of tags an event a signal is a set of events a functional signal is a (partial) function : the set of all signals (the powerset) -tuples of signalsPossible Interpretations of Tags Universal time () Discrete time ( is a totally ordered discrete se... Precedences ( is a partially ordered discrete se...Why not always use the “most physical” model:universal time? In specifying systems, avoid over-specifying. In modeling systems, recognize the inherent diff...Empty Signals and Events The empty signal: The tuple of empty signals: Note: and . For any signal , . For any tuple , (pointwise union).In some models of computation, the set of values i...Processes and ConnectionsProcesses a process for some a behavior (s satisfies the process) a process is a set of possible behaviorsConnections (a type of process) a connection :SystemsGiven a tuple P of processes, a system is another ...Given a process , the projection is defined byif there existssuch thatAn Example,Determinacy An input to a process is an externally imposed c... The set of all possible inputs is a further char... For example, means that the first signal is spec... A process is determinate if for all inputs , or ...Input/Output Partitions is a partition of if . A process with inputs, outputs is a subset of A process with inputs and output is a relation b... A functional process is a single-valued mapping ... A process that is functional with respect to som...ExampleSuppose:is functional with respect to the partitionis functional w.r.t.Key question: is functional w.r.t. ?Answer: It depends.Partial Ordering of Tags and Events Partially ordered: there exists an reflexive, an... Version of this relation: “<”. Ordering of the tags fi ordering of events. Given...Timed Systems Timed system: is totally ordered. Metric time: is a metric space.Continuous TimeLet denote the set of tags in a signal in a timed ... A continuous-time system is a metric timed syste...A connected set is one where there do not exist tw...Discrete Event SystemsGiven a system , and a tuple of signals that satis... A two-sided discrete-event system is a timed sys...IntuitivelyAny pair of events in a signal have a finite numbe...One-Sided Discrete-Event Systems A one-sided discrete-event system is a timed sys...IntuitivelyEvery signal has a first event.Synchrony Two events are synchronous if they have the same... Two signals are synchronous if all events in one... A system is synchronous if every signal in the s... A discrete-time system is a synchronous discrete...By this definition, synchronous dataflow (SDF) is ...Causality in DE Systems (Intuitively) A causal process has a non-negative (but possibl... A strictly causal process has a positive time de... A delta causal process has a time delay from inp...A Metric Space for DE SignalsIn a one-sided DE system, where WOLG , define the ...where is the smallest time where the two signals d...With this metric, behaviors of a discrete-event sy...Causality in the Cantor Metric SpaceCausality: .Strict causality: .Delta causality: there exists a such thatis a contraction mapping.Note: .Composing Functional Processes (1)Parallel composition:The composition is functional and (strictly, delta...Determinacy is preserved.Composing Functional Processes (2)Cascade composition:The composition is functional and (strictly, delta...Determinacy is preserved.Technicality: SourcesSource composition:The composition is functional and (strictly, delta...Composing Functional Processes (3)Feedback composition:Device: Capture Inputs with Source ProcessesIf and are determinate, and is causal, strictly ca...The Semantics of FeedbackFor , define the semantics to be a fixed point ofi.e. such that .Fixed Point Theorems Applied to Discrete-Event Sys... If is strictly causal, then it has at most one f... (Banach fixed point theorem) If the metric space..., , , ... If the metric space is compact (it is if is a fi...Lessons If subsystems are delta causal, then the Banach ... Specification languages often only insist on str... The set of VHDL signals is not compact. The lack of a constructive solution manifests it...Ordered Signal Process NetworksLet denote the tags in the signal and the union of... In a two-sided ordered signal process network, i... In a one-sided ordered signal process network, i...For any two distinct signals and , it could be tha... Events are often called tokens, and a signal is ...Example of an OSP Because tokens in each signal are ordered,for . Suppose each token consumed on the input results...for all .Dataflow A dataflow process or actor is an OSP with a
View Full Document
Unlocking...