CS244-Introduction to Embedded Systems and Ubiquitous ComputingCS244 – Lecture 6Taxonomy of ComputationsModels, Languages, & ToolsModels of ComputationModels of Computation …Models of computation: ExamplesSlide 8Slide 9LanguagesModels vs. languagesFinite-state machine (FSM) modelFormal definitionFinite-state machine with datapath model (FSMD)Describing a system as a state machineState machine vs. sequential program modelTry Capturing Other Behaviors with an FSMCapturing state machines in sequential programming languageLanguage subset approachGeneral templateHCFSM and the Statecharts languageProgram-state machine model (PSM): HCFSM plus sequential program modelPetri NetsApplications of Petri NetPowerPoint PresentationSlide 26Slide 27Slide 28Slide 29Slide 30Example: In a Restaurant (A Petri Net)Example: In a Restaurant (Two Scenarios)Example: In a Restaurant (Scenario 1)Example: In a Restaurant (Scenario 2)Petri Net with TimeReferencesConcurrent process modelProcess NetworkAsynchronous message passingDataflow modelSynchronous dataflowCS244-Introduction to Embedded Systems and Ubiquitous ComputingInstructor: Eli BozorgzadehComputer Science DepartmentUC IrvineWinter 2010Winter 2010- CS 2442CS244 – Lecture 6Model of ComputationTaxonomy of Computations “Regular” vs “Event-Driven”Regular examples: streaming applications, processors,…Event-driven: “reactive” (triggered by changes in environment)Real-Time Hard vs. Soft deadlines Periodic vs. AperiodicControl, Data, Communication How much of each?Parallelism, Geographic distances Highly concurrent vs. sequential; distributed systemsDeterministic vs. Non-deterministicDegree of predictabilitySome CharacteristicsModels, Languages, & ToolsA model of computation is a conceptual notions used to capture a system behavior, e.g.:A set of objectsComposition rulesExecution semanticsA languages defines the syntax to capture a models of computationA tool is a “compiler” transforming a model captured in one language to a model captured in another languageModel M1Model M2Language L1Language L2ToolBehaviorBehaviorModels of ComputationSequential model of computationA single thread of executionConcurrent model of computationMultiple threads of executionSynchronization pointsCommunication mechanismsObject Oriented (OO) Model of computationView the computation as a set of objectsBased, inherited, or composedPolymorphism: a derived class can modify the behavior of its base classModels of Computation …FSMA set of states and transitionsMealy and MooreDFGA set of computation nodes and flow pathsPetri netA set of places, transitions, edges, and tokensKahn Process Network (KPN)A set of concurrent processes sharing data using unbounded buffersCommunicating Sequential Processes (CSP)P1P2P4P3Petri netKPNICS212 FQ05 (Dutt) Models, Languages, ToolsModels of computation: ExamplesDiscrete event modelDiscrete event modelabctimeactiona:=5 b:=7 c:=8 a:=6 a:=9 queue5 10 13 15 19Discrete Events (DE)Events occur at discrete points on a time continuumEvents trigger computationsComputations trigger more eventsModels of computation: ExamplesContinuous Time (CT): Differential equationsContinuous Time (CT): Differential equationsSynchronous message passingSynchronous message passingbtx22Asynchronous message passingAsynchronous message passingDifferential equations model continuous i/o response as a function of continuous timeModels of Computation …Synchronous Reactive (SR)Break time into an ordered sequence of instancesEach instance is initiated by an event from the environmentPublish & Subscribe (P&S)Sending applications (publishers) publish messages without explicitly specifying recipientsReceiving applications (subscribers) receive only those messages that the subscriber has registered an interest inLoosely coupled networked systems (middleware handles the linking)Hybrid and hierarchical modelsLanguagesCommon:Assembly (closest language to Turing-machine model of computation)ANSI C, C++ANSI C/C++ & POSIXADA, VHDLJAVAEvolving:SystemCSystemVerilogSpecC, …Others:Magic for layoutVHDL subset for RTLPtolemyAPI extensionsCORBAClient-serverTCP/IPEtc.11Models vs. languagesComputation models describe system behaviorConceptual notion, e.g., recipe, sequential programLanguages capture modelsConcrete form, e.g., English, CVariety of languages can capture one modelE.g., sequential program model  C,C++, Java One language can capture variety of modelsE.g., C++ → sequential program model, object-oriented model, state machine modelCertain languages better at capturing certain computation modelsModelsLanguagesRecipeSpanishEnglish JapanesePoetry Story Sequent.programC++C JavaStatemachineData-flowRecipes vs. EnglishSequential programs vs. C12Finite-state machine (FSM) modelIdleGoingUpreq > floorreq < floor!(req > floor) !(timer < 10)req < floorDoorOpenGoingDnreq > flooru,d,o, t = 1,0,0,0u,d,o,t = 0,0,1,0u,d,o,t = 0,1,0,0u,d,o,t = 0,0,1,1u is up, d is down, o is openreq == floor!(req<floor)timer < 10t is timer_startUnitControl process using a state machine13Formal definitionAn FSM is a 6-tuple F<S, I, O, F, H, s0>S is a set of all states {s0, s1, …, sl}I is a set of inputs {i0, i1, …, im}O is a set of outputs {o0, o1, …, on}F is a next-state function (S x I → S)H is an output function (S → O)s0 is an initial stateMoore-typeAssociates outputs with states (as given above, H maps S → O)Mealy-typeAssociates outputs with transitions (H maps S x I → O)Shorthand notations to simplify descriptionsImplicitly assign 0 to all unassigned outputs in a stateImplicitly AND every transition condition with clock edge (FSM is synchronous)14Finite-state machine with datapath model (FSMD)FSMD extends FSM: complex data types and variables for storing dataFSMs use only Boolean data types and operations, no variablesFSMD: 7-tuple <S, I , O, V, F, H, s0>S is a set of states {s0, s1, …, sl}I is a set of inputs {i0, i1, …, im}O is a set of outputs {o0, o1, …, on}V is a set of variables {v0, v1, …, vn}F is a next-state function (S x I x V → S)H is an action function (S → O + V)s0 is an initial stateI,O,V may