OutlineDesignFormalizationModels of Computation: And There are More...Model Of ComputationUsefulness of a Model of ComputationCommon Models of ComputationNotion of TimeControl versus Data FlowSlide 10Telecom/MM applicationsReactive Real-time SystemsModels Of Computation for reactive systemsSlide 14Finite State MachinesFSM ExampleSlide 17FSM DefinitionNon-deterministic FSMsNDFSM: incomplete specificationNDFSM: unknown behaviorNDFSM: time rangeNDFSMs and FSMsSlide 24Modeling ConcurrencyFSM CompositionSlide 27Slide 28Slide 29Slide 30Slide 31Slide 32Moore vs. MealySlide 34Hierarchical FSM modelsSlide 36StateChartsState DecompositionStateChart OR-decompositionStateChart AND-decompositionStateCharts SyntaxStateCharts Actions and EventsGraphical Hierarchical FSM LanguagesSynchronous vs. Asynchronous FSMsSlide 45SynchronizationHandoverFrame SynchronizationBit SynchronizationAsynchronous communicationAsynchronous communicationCommunication MechanismsCommunication models1OutlineOutlinePart 3: Models of ComputationPart 3: Models of ComputationFSMsFSMsDiscrete Event Systems Discrete Event Systems CFSMsCFSMsData Flow ModelsData Flow ModelsPetri Nets Petri Nets The Tagged Signal ModelThe Tagged Signal Model2DesignDesignFrom an idea…From an idea…… … build something that performs a certain functionbuild something that performs a certain functionNever done directly:Never done directly:some aspects are not considered at the beginning of the some aspects are not considered at the beginning of the developmentdevelopmentthe designer wants to explore different possible implementations the designer wants to explore different possible implementations in order to maximize (or minimize) a cost functionin order to maximize (or minimize) a cost functionModels can be used to reason about the properties of an Models can be used to reason about the properties of an objectobject3FormalizationFormalizationModel of a design with precise unambiguous semantics:Model of a design with precise unambiguous semantics:Implicit or explicit relations: inputs, outputs and (possibly) Implicit or explicit relations: inputs, outputs and (possibly) state variablesstate variablesProperties Properties ““Cost” functions Cost” functions ConstraintsConstraintsFormalization of Design + Environment =closed system of equations and inequalities over some algebra.4Models of Computation: And There are More...Models of Computation: And There are More...Continuous time (ODEs)Continuous time (ODEs)Spatial/temporal (PDEs)Spatial/temporal (PDEs)Discrete timeDiscrete timeRendezvousRendezvousSynchronous/ReactiveSynchronous/ReactiveDataflowDataflow......Tower of Babel, Bruegel, 1563Each of these provides a formal framework for reasoning about certain aspects of embedded systems.5Model Of ComputationModel Of ComputationA MoC is a framework in which to express what sequence of actions must be A MoC is a framework in which to express what sequence of actions must be taken to complete a computationtaken to complete a computationExamples: Finite State Machine, Turing Machine, differential equationExamples: Finite State Machine, Turing Machine, differential equationWhy different models?Why different models?Different models = different propertiesDifferent models = different propertiesTuring-complete models are Turing-complete models are tootoo powerful! powerful!Some problems may be Some problems may be undecidableundecidableMOC needs toMOC needs tobe powerful enough for application domainbe powerful enough for application domainhave appropriate synthesis and validation algorithmshave appropriate synthesis and validation algorithms6Usefulness of a Model of ComputationUsefulness of a Model of ComputationExpressivenessExpressivenessGeneralityGeneralitySimplicitySimplicityCompilability/ SynthesizabilityCompilability/ SynthesizabilityVerifiabilityVerifiabilityThe ConclusionThe ConclusionOne way to get all of these is to mix diverse, simple models of computation, while One way to get all of these is to mix diverse, simple models of computation, while keeping compilation, synthesis, and verification separate for each MoC. To do that, we keeping compilation, synthesis, and verification separate for each MoC. To do that, we need to understand these MoCs need to understand these MoCs relative to one anotherrelative to one another, and understand , and understand their their interaction when combined in a single system design.interaction when combined in a single system design.7Common Models of ComputationCommon Models of ComputationFinite State MachinesFinite State Machinesfinite statefinite stateno concurrency nor time no concurrency nor time Data-FlowData-FlowPartial OrderPartial OrderConcurrent and DeterminateConcurrent and DeterminateStream of computationStream of computationDiscrete-EventDiscrete-EventGlobal Order (embedded in time)Global Order (embedded in time)Continuous TimeContinuous TimeThe behavior of a design in general is described by a The behavior of a design in general is described by a compositioncomposition8Notion of TimeNotion of Time9Control versus Data FlowControl versus Data FlowFuzzy distinction, yet Fuzzy distinction, yet usefuluseful for: for:specification (language, model, ...)specification (language, model, ...)synthesis (scheduling, optimization, ...)synthesis (scheduling, optimization, ...)validation (simulation, formal verification, ...)validation (simulation, formal verification, ...)Rough Rough classificationclassification::control:control:don’t know when data arrive (quick reaction)don’t know when data arrive (quick reaction)time of arrival often matters more than valuetime of arrival often matters more than valuedata:data:data arrive in regular streams (samples)data arrive in regular streams (samples)value matters mostvalue matters most10Control versus Data FlowControl versus Data FlowSpecification, synthesis and validation methods Specification, synthesis and validation methods emphasizeemphasize::for control:for control:event/reaction relationevent/reaction relationresponse time response time (Real Time scheduling for deadline satisfaction)(Real Time scheduling for deadline satisfaction)prioritypriority among events and processes among events and processesfor data:for data:functional dependency between
View Full Document
Unlocking...