Outline Part 3 Models of Computation FSMs Discrete Event Systems CFSMs Data Flow Models Petri Nets The Tagged Signal Model 1 EE249Fall07 Data flow networks A bit of history Syntax and semantics actors tokens and firings Scheduling of Static Data flow static scheduling code generation buffer sizing Other Data flow models Boolean Data flow Dynamic Data flow 2 EE249Fall07 Data flow networks Powerful formalism for data dominated system specification Partially ordered model no over specification Deterministic execution independent of scheduling Used for simulation scheduling memory allocation code generation for Digital Signal Processors HW and SW 3 EE249Fall07 A bit of history Karp computation graphs 66 seminal work Kahn process networks 58 formal model Dennis Data flow networks 75 programming language for MIT DF machine Several recent implementations graphical Ptolemy UCB Khoros U New Mexico Grape U Leuven SPW Cadence COSSAP Synopsys textual Silage UCB Mentor Lucid Haskell 4 EE249Fall07 Data flow network A Data flow network is a collection of functional nodes which are connected and communicate over unbounded FIFO queues Nodes are commonly called actors The bits of information that are communicated over the queues are commonly called tokens 5 EE249Fall07 Intuitive semantics Often stateless actors perform computation Unbounded FIFOs perform communication via sequences of tokens carrying values integer float fixed point matrix of integer float fixed point image of pixels State implemented as self loop Determinacy unique output sequences given unique input sequences Sufficient condition blocking read process cannot test input queues for emptiness 6 EE249Fall07 Intuitive semantics At each time one actor is fired When firing actors consume input tokens and produce output tokens Actors can be fired only if there are enough tokens in the input queues 7 EE249Fall07 Intuitive semantics Example FIR filter single input sequence i n single output sequence o n o n c1 i n c2 i n 1 i c2 c1 8 i 1 o EE249Fall07 Intuitive semantics Example FIR filter single input sequence i n single output sequence o n o n c1 i n c2 i n 1 i c2 c1 9 i 1 o EE249Fall07 Intuitive semantics Example FIR filter single input sequence i n single output sequence o n o n c1 i n c2 i n 1 i c2 c1 10 i 1 o EE249Fall07 Intuitive semantics Example FIR filter single input sequence i n single output sequence o n o n c1 i n c2 i n 1 i c2 c1 11 i 1 o EE249Fall07 Intuitive semantics Example FIR filter single input sequence i n single output sequence o n o n c1 i n c2 i n 1 i c2 c1 12 i 1 o EE249Fall07 Intuitive semantics Example FIR filter single input sequence i n single output sequence o n o n c1 i n c2 i n 1 i c2 c1 13 i 1 o EE249Fall07 Intuitive semantics Example FIR filter single input sequence i n single output sequence o n o n c1 i n c2 i n 1 i c2 c1 14 o EE249Fall07 Intuitive semantics Example FIR filter single input sequence i n single output sequence o n o n c1 i n c2 i n 1 i c2 c1 15 o EE249Fall07 Intuitive semantics Example FIR filter single input sequence i n single output sequence o n o n c1 i n c2 i n 1 i c2 c1 16 o EE249Fall07 Intuitive semantics Example FIR filter single input sequence i n single output sequence o n o n c1 i n c2 i n 1 i c2 c1 17 o EE249Fall07 Questions Does the order in which actors are fired affect the final result Does it affect the operation of the network in any way Go to Radio Shack and ask for an unbounded queue 18 EE249Fall07 Formal semantics sequences Actors operate from a sequence of input tokens to a sequence of output tokens Let tokens be noted by x1 x2 x3 etc A sequence of tokens is defined as X x1 x2 x3 Over the execution of the network each queue will grow a particular sequence of tokens In general we consider the actors mathematically as functions from sequences to sequences not from tokens to tokens 19 EE249Fall07 Ordering of sequences Let X1 and X2 be two sequences of tokens We say that X1 is less than X2 if and only if by definition X1 is an initial segment of X2 Homework prove that the relation so defined is a partial order reflexive antisymmetric and transitive This is also called the prefix order Example x1 x2 x1 x2 x3 Example x1 x2 and x1 x3 x4 are incomparable 20 EE249Fall07 Chains of sequences Consider the set S of all finite and infinite sequences of tokens This set is partially ordered by the prefix order A subset C of S is called a chain iff all pairs of elements of C are comparable If C is a chain then it must be a linear order inside S otherwise why call it chain Example x1 x1 x2 x1 x2 x3 is a chain Example x1 x1 x2 x1 x3 is not a chain 21 EE249Fall07 Least Upper Bound Given a subset Y of S an upper bound of Y is an element z of S such that z is larger than all elements of Y Consider now the set Z subset of S of all the upper bounds of Y If Z has a least element u then u is called the least upper bound lub of Y The least upper bound if it exists is unique Note u might not be in Y if it is then it is the largest value of Y 22 EE249Fall07 Complete Partial Order Every chain in S has a least upper bound Because of this property S is called a Complete Partial Order Notation if C is a chain we indicate the least upper bound of C by lub C Note the least upper bound may be thought of as the limit of the chain 23 EE249Fall07 Processes Process function from a p tuple of sequences to a q tuple of sequences F Sp Sq Tuples have the induced point wise order Y y1 yp Y y 1 y p in Sp Y Y iff yi y i for all 1 i p Given a chain C in Sp F C may or may not be a chain in Sq We are interested in conditions that make that true 24 EE249Fall07 Continuity and Monotonicity Continuity F is continuous iff by definition for all chains C lub F C exists and F lub C lub F C Similar to continuity in analysis using limits Monotonicity F is monotonic iff by definition for all pairs X X X X F X F X Continuity implies monotonicity intuitively outputs cannot be withdrawn once they have been produced timeless causality F transforms chains into chains 25 EE249Fall07 Least Fixed Point semantics Let X be the set of all sequences A network is a mapping F from the sequences to the sequences X F X I The behavior of the network is defined as the unique least fixed point of the equation If F is …
View Full Document
Unlocking...