WIXLIB

Introduction toEmbedded SystemsSanjit A. SeshiaUC BerkeleyEECS 149/249AFall 2015 2008-2015: E. A. Lee, A. L. Sangiovanni-Vincentelli, S. A. Seshia. All rightsreserved.Chapter 6 - Models of Computation:Synchronous/Reactive and DataflowConcurrent Composition:Alternatives to ThreadsThreads yield incomprehensible behaviors.Composition of State Machines: Side-by-side composition Cascade composition Feedback compositionWe will begin with synchronous composition, an abstractionthat has been very effectively used in hardware design andis gaining popularity in software design.Lee & Seshia, UC Berkeley: 2 1

Recall: Actor Model for State MachinesExpose inputs and outputs, enabling composition:Lee & Seshia, UC Berkeley: 3Recall: Actor Model of Continuous-Time SystemsA system is a function thataccepts an input signal andyields an output signal.The domain and range ofthe system function aresets of signals, whichthemselves are functions.Parameters may affect thedefinition of the function S.Lee & Seshia, UC Berkeley: 4 2

Recall: Composition of ActorsAngular velocityappears on bothsides. The semantics(meaning) of themodel is the solutionto this equation.We will now generalize this notion of composition.Lee & Seshia, UC Berkeley: 5Side-by-Side CompositionSynchronous composition: the machines reactsimultaneously and instantaneously.Lee & Seshia, UC Berkeley: 6 3

Cascade CompositionSynchronous composition: the machines reactsimultaneously and instantaneously, despite the apparentcausal relationship!Lee & Seshia, UC Berkeley: 7Synchronous Composition:Reactions are Simultaneous and InstantaneousConsider a cascade composition as follows:Lee & Seshia, UC Berkeley: 8 4

Synchronous Composition:Reactions are Simultaneous and InstantaneousIn this model, you must not think of machine A as reacting before machineB. If it did, the unreachable states would not be unreachable.unreachableLee & Seshia, UC Berkeley: 9Feedback CompositionTurns out everything can be viewed as feedback composition Lee & Seshia, UC Berkeley: 10 5

Observation: Any Composition is aFeedback Compositions SNThe behavior of the systemis a “fixed point.”Lee & Seshia, UC Berkeley: 11Fixed Point SemanticsConsider aninterconnection of actorsReorganizeWe seek an s S Nthat satisfies F(s) s.Such an s is called afixed point.Abstract actorsAbstract signalss SNWe would like thefixed point to existand be unique. Andwe would like aconstructiveprocedure to find it.It is the behavior ofthe system.Lee & Seshia, UC Berkeley: 12 6

Data TypessxyLee & Seshia, UC Berkeley: 13Firing FunctionssxyLee & Seshia, UC Berkeley: 14 7

Well-Formed FeedbacksxyLee & Seshia, UC Berkeley: 15Well-Formed ExampleLee & Seshia, UC Berkeley: 16 8

Composite MachineLee & Seshia, UC Berkeley: 17Ill-Formed Example 1 (Existence)Lee & Seshia, UC Berkeley: 18 9

Ill-Formed Example 2 (Uniqueness)Lee & Seshia, UC Berkeley: 19Constructive Semantics: Single SignalLee & Seshia, UC Berkeley: 20 10

Non-Constructive Well-Formed State MachineLee & Seshia, UC Berkeley: 21Must / May AnalysisLee & Seshia, UC Berkeley: 22 11

Constructive Semantics: Multiple SignalsLee & Seshia, UC Berkeley: 23Constructive Semantics: Multiple ActorsProcedure is the same.Lee & Seshia, UC Berkeley: 24 12

Constructive Semantics: Arbitrary StructureProcedure is the same.A state machine language with constructive semanticswill reject all compositions that in any iteration fail tomake all signals known.Such a language rejects some well-formed compositions.Lee & Seshia, UC Berkeley: 25Synchronous Reactive Models: ConclusionsThe emphasis of synchronous composition, in contrastwith threads, is on determinate and analyzableconcurrency.Although there are subtleties with synchronousprograms, all constructive synchronous programs have aunique and well-defined meaning.Automated tools can systematically explore all possiblebehaviors. This is not possible in general with threads.Lee & Seshia, UC Berkeley: 26 13

Introduction toEmbedded SystemsChapter 6: Dataflow ModelsSimple Example: Spectrum AnalysisNot timecritical pathTime critical pathHow do we keep thenon-time critical pathfrom interfering withthe time-critical path?Dataflow Models, UC Berkeley: 28 14

A Solution with ThreadsThread AThread BTime critical pathCreate two threads: A has low priority B has high priorityWhy? RMS does not apply because thereare dependencies.EDF with precedences applies andis optimal w.r.t. feasibility, except forhow to assign deadlines.How to implement thecommunication between threads?Dataflow Models, UC Berkeley: 29Abstracted Version of the Spectrum Example:EDF scheduling81Precedence graph1Suppose that C requires 8data values from A to execute. Suppose further that Ctakes much longer to execute than A or B. EDF schedule:scheduleDataflow Models, UC Berkeley: 30 15

Dataflow ModelsActor AFIFO bufferActor BBuffered communication between concurrent components (actors).Static scheduling: Assign to each thread a sequence of actorinvocations (firings) and repeat forever.Dynamic scheduling: Each time dispatch() is called, determinewhich actor can fire (or is firing) and choose one.May need to implement interlocks in the buffers.Dataflow Models, UC Berkeley: 31Streams: The basis for Dataflow modelsDataflow Models, UC Berkeley: 32 16

DataflowFiring rules:the number oftokensrequired to firean actor.Dataflow Models, UC Berkeley: 33Buffers for Dataflow Unbounded buffers require memory allocation and deallocationschemes.Bounded size buffers can be realized as circular buffers or ringbuffers, in a statically allocated array. A read pointer r is an index into the array referring to the first emptylocation. Increment this after each read.A fill count n is unsigned number telling us how many data items arein the buffer.The next location to write to is (r n ) modulo buffer length.The buffer is empty if n 0The buffer is full if n buffer lengthCan implement n as a semaphore, providing mutual exclusion forcode that changes n or r.Dataflow Models, UC Berkeley: 34 17

Synchronous Dataflow (SDF)If the number of tokens consumed and produced by thefiring of an actor is constant, then static analysis can tellus whether we can schedule the firings to get a usefulexecution, and if so, then a finite representation of aschedule for such an execution can be created.Dataflow Models, UC Berkeley: 35Balance EquationsLet qA, qB be the number of firings of actors A and B.Let pC, cC be the number of tokens produced andconsumed on a connection C.Then the system is in balance if for all connections CqA pC qB cCwhere A produces tokens on C and B consumes them.Dataflow Models, UC Berkeley: 36 18

ExampleConsider this example, where actors and arcs arenumbered:The balance equations imply that actor 3 must fire twiceas often as the other two actors.Dataflow Models, UC Berkeley: 37Compactly Representing the Balance Equationsproduction/consumption matrix 1 1 0 0 2 1 2 0 1 Actor 1balance equationsConnector 1 q1 q q2 q3 firing vector 0 q 0 0 0 Dataflow Models, UC Berkeley: 38 19

Question on initial example What is the production/consumption matrix in this case?811Dataflow Models, UC Berkeley: 39Question on initial example What is the production/consumption matrix in this case?811 1 0 1 1 8 0 Dataflow Models, UC Berkeley: 40 20

ExampleA solution to the balance equations: 1 q 1 2 1 1 0 0 2 1 2 0 1 q 0This tells us that actor 3 must fire twice as often as actors 1 and 2.Dataflow Models, UC Berkeley: 41ExampleBut there are many solutions to the balance equations: 0 2 1 1 q 1 q 0 q 2 q 1 q 4 2 2 0 2 q 0For “well-behaved” models, there is a unique leastpositive integer solution.Dataflow Models, UC Berkeley: 42 21

Least Positive Integer Solution to the BalanceEquationsNote that if pC, cC , the number of tokens produced andconsumed on a connection C, are non-negative integers,then the balance equation,qA pC qB cCimplies: qA is rational if and only if qB is rational. qA is positive if and only if qB is positive.Consequence: Within any connected component, if thereis any non-zero solution to the balance equations, thenthere is a unique least positive integer solution.Dataflow Models, UC Berkeley: 43Consistent ModelsAn SDF model is consistent if there exists a non-zerosolution to the balance equations.Dataflow Models, UC Berkeley: 44 22

Example of an Inconsistent Model:No Non-Trivial Solution to the Balance Equations 1 1 0 0 1 1 2 0 1 There are no nontrivial solutions to the balanceequations.Note that this model can execute forever, but it requiresunbounded memory.Dataflow Models, UC Berkeley: 45Structured DataflowLabVIEW uses homogeneous SDF augmented withsyntactically constrained forms of feedback and ratechanges: While loops Conditionals SequencesLabVIEW models are decidable.Dataflow Models, UC Berkeley: 46 23

Many other concurrent MoCs have been explored (Kahn) process networksCommunicating sequential processes (rendezvous)Time-driven modelsMore dataflow variants: cyclostatic Heterochronous Petri nets Dataflow Models, UC Berkeley: 47Introduction toEmbedded SystemsMaterial for Further Reading 24

Abstracted Version of the Spectrum Example:Non-preemptive schedulingIs this dataflowmodel dynamic?Is it homogeneous?Assume infinitely repeatedinvocations, triggered byavailability of data at A.811Suppose that C requires 8 data values from A to execute.Suppose further that C takes much longer to executethan A or B. Then a schedule might look like this: scheduleThis suffersfrom jitter.Note that each period is EDF.Dataflow Models, UC Berkeley: 49Uniformly Timed ScheduleA preferable schedule would space invocations ofA and B uniformly in time, as in: minimum latencyDataflow Models, UC Berkeley: 50 25

Non-Concurrent Uniformly Timed ScheduleNotice that in this schedule, the rate at which A and Bcan be invoked is limited by the execution time of C. No jitter, but utilization is poor.Dataflow Models, UC Berkeley: 51Concurrent Uniformly Timed Schedule:Preemptive scheduleWith preemption, the rate at which A and B can beinvoked is limited only by total computation:thread 1:thread 2:preemptions high priority low priorityDataflow Models, UC Berkeley: 52 26

Ignoring Initial Transients,Abstract to Periodic TaskssampleTime 8sampleTime 1sampleTime 1In steady-state, the execution follows a simple periodicpattern:thread 1: thread 2: This follows theprinciples of ratemonotonicscheduling (RMS).Dataflow Models, UC Berkeley: 53Requirement 1: Bounded Buffersinterlockthread 1: sampleTime: 8sampleTime: 1 sampleTime: 1thread 2: If the execution of C runs longer than expected, to keepthe buffer bounded, thread 1 must be delayedaccordingly. This can be accomplished with semaphoresynchronization. But there are alternatives: Throw an exception to indicate timing failure. “Anytime” computation: use incomplete results of CDataflow Models, UC Berkeley: 54 27

Requirement 2: Respect Data DependencesampleTime: 8 thread 1:sampleTime: 1 sampleTime: 1thread 2:interlock If the execution of C runs shorter than expected, datadeterminacy requires that thread 2 be delayedaccordingly. That is, it must not start the next executionof C before the data is available.Dataflow Models, UC Berkeley: 55In Dataflow, Interlocks and Built-in Buffering takecare of these dependenciesFor dataflow, a one-time interlock ensures sufficient dataat the input of C for the first invocation: thread 1:high priorityperiodic interlocksthread 2:first-time interlock low priorityDataflow Models, UC Berkeley: 62 28

Dataflow: many variantsDataflow Models, UC Berkeley: 67Necessary and sufficient conditionsConsistency is a necessary condition to have a(bounded-memory) infinite execution.Is it sufficient?Dataflow Models, UC Berkeley: 71 29

Deadlock 11111ABIs this diagram consistent?Dataflow Models, UC Berkeley: 72Deadlock 2Some dataflow models cannot execute forever. In theabove model, the feedback loop injects initial tokens, butnot enough for the model to execute.Dataflow Models, UC Berkeley: 73 30