Modeling Embedded SystemsReading List for This LectureHow to Design Embedded Systems? (Wescon 1975)Methodical Design of Embedded SystemsAbstractions and ModelsGood ModelsSeparate Behavior from ArchitectureElements of a Model of a Computation System: LanguageSimulation and SynthesisModels Useful In Validating DesignsHeterogeneous SystemsSlide 12Importance of Time in Embedded Systems: Reactive OperationReactive Operation (contd.)Real Time OperationShades of Real-timeExample: Characterizing Real-time Performance of an OSTiming ConstraintsMany Notions of TimeTiming Constraints in a DSP SystemsSlide 21Latency vs. Throughput Which is “Harder” Real-time?More General Timing ConstraintsMaximum Timing ConstraintsObservationMinimum Timing ConstraintsMore Complex Timing ConstraintsPopular Computation Models for Embedded SystemsHow do the models differ?Example: Modeling DSP SystemsDigression: Graphs as an Abstract Syntax for ModelsFinite State MachinesFSM ExamplesMore Complex FSMProtocol Controller FSMFSM ExampleNon-Deterministic FSMMealy-Moore FSMsRetrigerrable One-shot TimerProblems with Conventional FSMScalabilitySlide 42ConcurrencySlide 44Mealy-Moore SolutionConcurrent State Model SolutionOrthogonal ComponentsApproach 1: Enumerate AllApproach 2Harel’s StateCharts: Extension of Conventional FSMsFeatures of StateChartsBasic Harel SyntaxState DecompositionStateChart OR-decompositionStateChart AND-decompositionStateCharts SyntaxTransitionsStateCharts Actions and EventsOrder of Nested ActionsHistoryConditional TransitionsAnother Example of the Power of StateChart FormalismExample: Jolt Cola MachineThe Combined State Machine in StateChart FormalismExample: Coin Receptacle FSMSubstate: Issuing CanClass Button FSMConcurrent StatechartsSlide 69Slide 70Explicit SynchronizationExample Concurrent FSMCommunication in Concurrent FSMsPropagations and BroadcastsGraphical Hierarchical FSM LanguagesRaphsody, StateMate etc. by i-LogixCo-design Finite State Machines (CFSMs)Network of CFSMsCommunication PrimitivesMore on EventsGeneralization to SignalsExample CFSM SpecificationNetwork of CFSMs: Depth-1 BuffersDiscrete EventsSlide 85Reactive Synchronous ModelsEsterelEsterel ExampleData Flow Based ModelsData Flow NetworkFlow Graph ModelsSemanticsSynchronous Data FlowWhat Latency & Sample Period can a SDFG achieve?SDFG can be Transformed to Affect TL & TSDataflow Process NetworksSynchronous vs. AsynchronousAsynchronous CommunicationsCommunication ModelsModeling Approaches based on Software Design MethodsHow Models Influence an Application Design?Choice of ModelMani SrivastavaUCLA - EE DepartmentRoom: 7702-B Boelter HallEmail: [email protected]: 310-267-2098WWW: http://www.ee.ucla.edu/~mbsCopyright 2001  Mani SrivastavaModeling Embedded SystemsEE202A (Fall 2001): Lecture #22Copyright 2001  Mani SrivastavaReading List for This LectureMANDATORY READINGE.A. Lee, “Embedded Software,” UCB ERL Memorandum M01/26.http://ptolemy.eecs.berkeley.edu/publications/papers/01/embsystems/Harel, D.; Lachover, H.; Naamad, A.; Pnueli, A.; Politi, M.; Sherman, R.; Shtull-Trauring, A.; Trakhtenbrot, M. STATEMATE: a working environment for the development of complex reactive systems. IEEE Transactions on Software Engineering, vol.16, (no.4), April 1990. p.403-14.http://ielimg.ihs.com/iel1/32/1950/00054292.pdfOTHER READINGNone3Copyright 2001  Mani SrivastavaHow to Design Embedded Systems? (Wescon 1975)“...deliberately avoid data processing aides such as assemblers, high-level languages, simulated systems, and control panels. These computer-aided design tools generally get in the way of cost-effective design and are more a result of the cultural influence of data processing, rather than a practical need.”“It’ s my observation that the bulk of real-world control problems require less than 2,000 instructions to implement. For this size program computer aided design does little to improve the design approach and does a lot to separate the design engineer from intimate knowledge of his hardware.”4Copyright 2001  Mani SrivastavaMethodical Design of Embedded SystemsAd hoc approach to design does not work beyond a certain level of complexity, that is exceeded by vast majority of embedded systemsMethodical, engineering-oriented, tool-based approach is essentialspecification, synthesis, optimization, verification etc.prevalent for hardware, still rare for softwareOne key aspect is the creation of modelsconcrete representation of knowledge and ideas about a system being developed - specificationmodel deliberately modifies or omits details (abstraction) but concretely represents certain properties to be analyzed, understood and verifiedone of the few tools for dealing with complexity5Copyright 2001  Mani SrivastavaAbstractions and ModelsFoundations of science and engineeringActivities usually start with informal specificationHowever, soon a need for Models and Abstractions is establishede.g.: Chess and Poker - No Rules, No GamesConnections to Implementation (h/w, s/w) and ApplicationTwo types of modeling: system structure & system behaviorthe behavior and interaction of atomic componentscoordinate computation of & communication between componentsModels from classical CSFSM, RAM (von Neumann)CSP (Hoare), CCS (Milner)Turing machine, Post Machine, Universal Register Machine6Copyright 2001  Mani SrivastavaGood ModelsSimplePtolemy vs. GalileoAmenable for development of theory to reasonshould not be too generalHas High Expressive Powera game is interesting only if it has some level of difficulty!Provides Ability for Critical ReasoningScience vs. ReligionPractice is currently THE only serious test of model qualityExecutable (for Simulation)SynthesizableUnbiased towards any specific implementation (h/w or s/w)7Copyright 2001  Mani SrivastavaSeparate Behavior from Architecture8Copyright 2001  Mani SrivastavaElements of a Model of a Computation System: LanguageSet of symbols with superimposed syntax & semanticstextual (e.g. matlab), visual (e.g. labview) etc.Syntax: rules for combining symbolswell structured, intuitiveSemantics: rules for assigning meaning to symbols and combinations of symbolswithout rigorous semantics, precise model behavior over time is not well definedfull executability and automatic h/w or s/w synthesis is impossibleE.g. operational semantics (in