EE249Fall071Outline• Part 3: Models of Computation– FSMs– Discrete Event Systems – CFSMs– Data Flow Models– Petri Nets – The Tagged Signal ModelEE249Fall072Data-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-flowEE249Fall073Data-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 generationfor Digital Signal Processors (HW and SW)EE249Fall074A 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, HaskellEE249Fall075Data-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 tokensEE249Fall076Intuitive 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)EE249Fall077Intuitive 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 inputqueuesEE249Fall078Intuitive semantics• Example: FIR filter– single input sequence i(n)– single output sequence o(n)– o(n) = c1 i(n) + c2 i(n-1) *c1+ oi*c2i(-1)EE249Fall079Intuitive semantics• Example: FIR filter– single input sequence i(n)– single output sequence o(n)– o(n) = c1 i(n) + c2 i(n-1) *c1+ oi*c2i(-1)EE249Fall0710Intuitive semantics• Example: FIR filter– single input sequence i(n)– single output sequence o(n)– o(n) = c1 i(n) + c2 i(n-1) *c1+ oi*c2i(-1)EE249Fall0711Intuitive semantics• Example: FIR filter– single input sequence i(n)– single output sequence o(n)– o(n) = c1 i(n) + c2 i(n-1) *c1+ oi*c2i(-1)EE249Fall0712Intuitive semantics• Example: FIR filter– single input sequence i(n)– single output sequence o(n)– o(n) = c1 i(n) + c2 i(n-1) *c1+ oi*c2i(-1)EE249Fall0713Intuitive semantics• Example: FIR filter– single input sequence i(n)– single output sequence o(n)– o(n) = c1 i(n) + c2 i(n-1) *c1+ oi*c2i(-1)EE249Fall0714Intuitive semantics• Example: FIR filter– single input sequence i(n)– single output sequence o(n)– o(n) = c1 i(n) + c2 i(n-1) *c1+ oi*c2EE249Fall0715Intuitive semantics• Example: FIR filter– single input sequence i(n)– single output sequence o(n)– o(n) = c1 i(n) + c2 i(n-1) *c1+ oi*c2EE249Fall0716Intuitive semantics• Example: FIR filter– single input sequence i(n)– single output sequence o(n)– o(n) = c1 i(n) + c2 i(n-1) *c1+ oi*c2EE249Fall0717Intuitive semantics• Example: FIR filter– single input sequence i(n)– single output sequence o(n)– o(n) = c1 i(n) + c2 i(n-1) *c1+ oi*c2EE249Fall0718Questions• 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!!EE249Fall0719Formal 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)EE249Fall07Ordering of sequences• Let X1and X2be two sequences of tokens.• We say that X1is less than X2if and only if (by definition) X1is 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 incomparable20EE249Fall07Chains 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 21EE249Fall07(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 upperbound (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)22EE249Fall07Complete 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 chain23EE249Fall07Processes• Process: function from a p-tuple of sequences to a q-tuple of sequencesF : Sp-> Sq• Tuples have the induced point-wise order:Y = ( y1, … , yp), Y’ = ( y’1, … , y’p) in Sp:Y <= Y’ iff yi<= y’ifor 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 true24EE249Fall07Continuity and Monotonicity• Continuity: F is continuous iff (by definition) for all chains C, lub( F( C ) ) exists andF( lub( C ) = lub( F( C ) )• Similar to
View Full Document
Unlocking...