OutlineDiscrete EventSimultaneous Events in DESlide 4Co-Design Finite State Machines: Combining FSM and Discrete EventCodesign Finite State MachineSynchrony: Basic OperationSynchrony: Basic Operation (2)Synchrony: Triggering and OrderingSynchrony: System SolutionSynchrony: Implementation CostPure Asynchrony: Basic OperationAsynchrony: Triggering and OrderingAsynchrony: System SolutionAsynchrony: Implementation CostAsynchrony vs. Synchrony in System DesignCombining Synchrony and AsynchronyCFSM OverviewCFSM Overview (2)Network of CFSMs: Depth-1 BuffersIntroducing a CFSMCFSM Rules: phasesSlide 23Communication PrimitivesCommunication Primitives (2)Signals and CFSMCFSM networksScheduling MechanismTiming BehaviorTiming Behavior: Mathematical ModelTiming Behavior: Transition PointEvent/Data SeparationAtomicityNon Atomic Data Value ReadingAtomicity of Event ReadingFunctional BehaviorFunctional Behavior (2)CFSM and Process NetworksCFSM NetworksBuffer OverwriteExample of CFSM BehaviorsEquivalent Classes of CFSM BehaviorEquivalent Classes of CFSM Behavior (2)Equivalent Classes of CFSM Behavior (3)Equivalent Classes of CFSM Behavior (4)Some Possibility of Equivalent ClassesConclusionSlide 48Data-flow networksSlide 50A bit of historyData-flow networkIntuitive semanticsSlide 54Slide 55Slide 56Slide 57Slide 58Slide 59Slide 60Slide 61Slide 62Slide 63Slide 64QuestionsFormal semantics: sequencesOrdering of sequencesChains of sequences(Least) Upper BoundComplete Partial OrderProcessesContinuity and MonotonicityLeast Fixed Point semanticsFrom Kahn networks to Data Flow networksExamples of Data Flow actorsStatic scheduling of DFStatic scheduling of SDFBalance equationsSlide 79Slide 80Slide 81Static SDF schedulingAdmissibility of schedulesSlide 84From repetition vector to scheduleFrom schedule to implementationCompilation optimizationCode size minimizationBuffer size minimizationDynamic scheduling of DFExample of Boolean DFExample of general DFSummary of DF networksSlide 941OutlineOutlinePart 3: Models of ComputationPart 3: Models of ComputationFSMsFSMsDiscrete Event SystemsDiscrete Event Systems CFSMsCFSMsData Flow ModelsData Flow ModelsPetri Nets Petri Nets The Tagged Signal ModelThe Tagged Signal Model2Discrete EventDiscrete EventExplicit notion of time (global order…)Explicit notion of time (global order…)Events can happen at any time asynchronouslyEvents can happen at any time asynchronouslyAs soon as an input appears at a block, it may be executedAs soon as an input appears at a block, it may be executedThe execution may take non zero time, the output is marked with a The execution may take non zero time, the output is marked with a time that is the sum of the arrival time plus the execution timetime that is the sum of the arrival time plus the execution timeTime determines the order with which events are processedTime determines the order with which events are processedDE simulator maintains a global event queue (Verilog and VHDL)DE simulator maintains a global event queue (Verilog and VHDL)DrawbacksDrawbacksglobal event queue => tight coordination between partsglobal event queue => tight coordination between partsSimultaneous events => non-deterministic behaviorSimultaneous events => non-deterministic behaviorSome simulators use delta delay to prevent non-determinacySome simulators use delta delay to prevent non-determinacy3Simultaneous Events in DE Simultaneous Events in DE AABBCCttttFire B or C?Fire B or C?AABBCCttAABBCCttttB has 0 delayB has 0 delayB has delta delayB has delta delayFire C once? or twice?Fire C once? or twice?t+t+Fire C twice.Fire C twice.Still have problem with 0-delay Still have problem with 0-delay (causality) loop(causality) loopCan be refinedCan be refinedE.g. introduce timing constraintsE.g. introduce timing constraints(minimum reaction time 0.1 s)(minimum reaction time 0.1 s)4OutlineOutlinePart 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 Model5Co-Design Finite State Machines:Co-Design Finite State Machines:Combining FSM and Discrete EventCombining FSM and Discrete EventSynchrony and asynchronySynchrony and asynchronyCFSM definitionsCFSM definitionsSignals & networksSignals & networksTiming behaviorTiming behaviorFunctional behaviorFunctional behaviorCFSM & process networksCFSM & process networksExample of CFSM behaviorsExample of CFSM behaviorsEquivalent classesEquivalent classes6Codesign Finite State MachineCodesign Finite State MachineUnderlying MOC of Polis and VCCUnderlying MOC of Polis and VCCCombine aspects from several other MOCsCombine aspects from several other MOCsPreserve formality and efficiency in implementationPreserve formality and efficiency in implementationMix Mix synchronicitysynchronicityzero and infinite timezero and infinite timeasynchronicityasynchronicitynon-zero, finite, and bounded timenon-zero, finite, and bounded timeEmbedded systems often contain both aspectsEmbedded systems often contain both aspects7Synchrony: Basic OperationSynchrony: Basic OperationSynchrony is often implemented with clocksSynchrony is often implemented with clocksAt clock ticksAt clock ticksModule reads inputs, computes, and produce outputModule reads inputs, computes, and produce outputAll synchronous events happen simultaneouslyAll synchronous events happen simultaneouslyZero-delay computationsZero-delay computationsBetween clock ticksBetween clock ticksInfinite amount of time passedInfinite amount of time passed8Synchrony: Basic Operation (2)Synchrony: Basic Operation (2)Practical implementation of synchronyPractical implementation of synchronyImpossible to get zero or infinite delayImpossible to get zero or infinite delayRequire: computation time <<< clock periodRequire: computation time <<< clock periodComputation time = 0, w.r.t. reaction time of environmentComputation time = 0, w.r.t. reaction time of environmentFeature of synchronyFeature of synchronyFunctional behavior independent of timingFunctional behavior independent of timingSimplify verificationSimplify verificationCyclic dependencies may cause problemCyclic dependencies may cause problemAmong (simultaneous) synchronous eventsAmong (simultaneous) synchronous
View Full Document
Unlocking...