CS244 Introduction to Embedded Systems and Ubiquitous Computing Instructor Eli Bozorgzadeh Computer Science Department UC Irvine Winter 2010 CS244 Lecture 6 Model of Computation Winter 2010 CS 244 2 Taxonomy of Computations Some Characteristics Regular vs Event Driven Real Time How much of each Parallelism Geographic distances Hard vs Soft deadlines Periodic vs Aperiodic Control Data Communication Regular examples streaming applications processors Event driven reactive triggered by changes in environment Highly concurrent vs sequential distributed systems Deterministic vs Non deterministic Degree of predictability Models 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 language Model M1 Model M2 Language L1 Behavior Tool Behavior Language L2 Models of Computation Sequential model of computation Concurrent model of computation A single thread of execution 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 class Models of Computation FSM DFG A set of places transitions edges and tokens Kahn Process Network KPN A set of computation nodes and flow paths Petri net A set of states and transitions Mealy and Moore A set of concurrent processes sharing data using unbounded buffers Petri net P1 Communicating Sequential Processes CSP P4 P2 P3 KPN Models of computation Examples Discrete Discreteevent event model model Discrete Events DE Events occur at discrete points on a time continuum Events trigger computations Computations trigger more events queue a b c ICS212 FQ05 Dutt Models Languages Tools 5 10 13 15 19 a 5 b 7 c 8 a 6 a 9 time action Models of computation Examples Continuous ContinuousTime Time CT CT Differential Differentialequations equations 2 x b 2 t Differential equations model continuous i o response as a function of continuous time Asynchronous Asynchronousmessage messagepassing passing Synchronous Synchronousmessage messagepassing passing Models of Computation Synchronous Reactive SR Publish Subscribe P S Break time into an ordered sequence of instances Each instance is initiated by an event from the environment 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 models Languages Common Evolving SystemC SystemVerilog SpecC Others Assembly closest language to Turing machine model of computation ANSI C C ANSI C C POSIX ADA VHDL JAVA Magic for layout VHDL subset for RTL Ptolemy API extensions CORBA Client server TCP IP Etc Models vs languages Poetry Recipe Story State machine Sequent program Dataflow English Spanish Japanese C C Java Model s Languag es 11 E g sequential program model C C Java One language can capture variety of models Concrete form e g English C Variety of languages can capture one model Conceptual notion e g recipe sequential program Languages capture models Sequential programs vs C Computation models describe system behavior Recipes vs English E g C sequential program model object oriented model state machine model Certain languages better at capturing certain computation models Finite state machine FSM model UnitControl process using a state machine req floor u d o t 1 0 0 0 GoingUp req floor timer 10 req floor timer 10 u d o t 0 0 1 0 Idle DoorOpen u d o t req req floor 0 0 1 1 floor req floor u d o t 0 1 0 0 GoingDn req floor 12 u is up d is down o is open t is timer start Formal definition An FSM is a 6 tuple F S I O F H s0 Moore type Associates outputs with transitions H maps S x I O Shorthand notations to simplify descriptions 13 Associates outputs with states as given above H maps S O Mealy type 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 Implicitly assign 0 to all unassigned outputs in a state Implicitly AND every transition condition with clock edge FSM is synchronous Finite state machine with datapath model FSMD FSMD extends FSM complex data types and variables for storing data 14 u d o t 1 0 0 0 GoingUp req floor u d o t 0 0 1 0 Idle req n floor 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 u d o t 0 1 0 0 req floor timer 10 timer 10 DoorOpen req floor GoingDn req floor u d o t 0 0 1 1 req floor u is up d is down o is open t is timer start I O V may represent complex data types i e integers floating point etc F H may include arithmetic operations H is an action function not just an output function req floor V is a set of variables v0 v1 v 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 We described UnitControl as an FSMD FSMD 7 tuple S I O V F H s0 FSMs use only Boolean data types and operations no variables Describes variable updates as well as outputs Complete system state now consists of current state s i and values of all variables Describing a system as a state machine 1 List all possible states 2 Declare all variables none in this example 3 For each state list possible transitions with conditions to other states req floor 4 For each state and or transition list associated u d o t 1 0 0 0 req floor GoingUp actions 5 For each state ensure timer 10 req floor u d o t 0 0 1 0 exclusive and complete timer 10 Idle DoorOpen exiting transition conditions u d o t 0 0 1 1 req floor No two exiting conditions can be true at same time One condition must be true at any given time 15 Otherwise nondeterministic state machine Reducing explicit transitions should be avoided when first learning req floor u d o t 0 1 0 0 req floor GoingDn u is up d is down o is open req floor t is timer start State machine vs sequential program model Different thought process used with each model State machine Sequential program model Encourages designer to think of all possible states and transitions among states based on all possible input conditions