DOC PREVIEW
Berkeley ELENG C249A - Models of Computation

This preview shows page 1-2-23-24 out of 24 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 24 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 24 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 24 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 24 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 24 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Page 1Outline• Part 3: Models of Computation– FSMs– Discrete Event Systems – CFSMs– Data Flow ModelsEE249Fall071– Petri Nets – The Tagged Signal ModelData-flow networks•A bit of history•A bit of history• Syntax and semantics– actors, tokens and firings• Scheduling of Static Data-flow– static scheduling–code generationEE249Fall072g– buffer sizing• Other Data-flow models– Boolean Data-flow– Dynamic Data-flowPage 2Data-flow networks•Powerful formalism for data-dominated system specification•Powerful formalism for data-dominated system specification• Partially-ordered model (no over-specification)• Deterministic execution independent of scheduling• Used for– simulation–schedulingEE249Fall073g– memory allocation– code generationfor Digital Signal Processors (HW and SW)A bit of history• Karp computation graphs (‘66): seminal work •Kahn process networks (‘58): formal model•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)EE249Fall074–Ptolemy (UCB), Khoros (U. New Mexico), Grape (U. Leuven)– SPW (Cadence), COSSAP (Synopsys)– textual:– Silage (UCB, Mentor)– Lucid, HaskellPage 3Data-flow network •AData-flow network is a collection offunctional nodeswhichA Dataflow network is a collection of functional nodeswhich 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 tokensEE249Fall075Intuitive semantics• (Often stateless) actors perform computation• Unbounded FIFOs perform communication via sequences of tk i ltokens carrying values– integer, float, fixed point– matrix of integer, float, fixed point– image of pixels• State implemented as self-loop EE249Fall076• Determinacy: – unique output sequences given unique input sequences – Sufficient condition: blocking read– (process cannot test input queues for emptiness)Page 4Intuitive semantics•At each time one actor isfiredAt 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 queuesEE249Fall077Intuitive semantics• Example: FIR filter– single input sequence i(n)–single output sequence o(n)– o(n) = c1 i(n) + c2 i(n-1) i*c2EE249Fall078*c1+oi(-1)Page 5Intuitive semantics• Example: FIR filtersingle input sequence i(n)–single input sequence i(n)– single output sequence o(n)– o(n) = c1 i(n) + c2 i(n-1) i*c2EE249Fall079*c1+oi(-1)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*c2EE249Fall0710*c1+oi(-1)Page 6Intuitive semantics• Example: FIR filtersingle input sequence i(n)–single input sequence i(n)– single output sequence o(n)– o(n) = c1 i(n) + c2 i(n-1) i*c2EE249Fall0711*c1+oi(-1)Intuitive semantics• Example: FIR filtersingle input sequence i(n)–single input sequence i(n)– single output sequence o(n)– o(n) = c1 i(n) + c2 i(n-1) i*c2EE249Fall0712*c1+oi(-1)Page 7Intuitive semantics• Example: FIR filtersingle input sequence i(n)–single input sequence i(n)– single output sequence o(n)– o(n) = c1 i(n) + c2 i(n-1) i*c2EE249Fall0713*c1+oi(-1)Intuitive semantics• Example: FIR filtersingle input sequence i(n)–single input sequence i(n)– single output sequence o(n)– o(n) = c1 i(n) + c2 i(n-1) i*c2EE249Fall0714*c1+oPage 8Intuitive semantics• Example: FIR filtersingle input sequence i(n)–single input sequence i(n)– single output sequence o(n)– o(n) = c1 i(n) + c2 i(n-1) i*c2EE249Fall0715*c1+oIntuitive semantics• Example: FIR filter–single input sequence i(n)– single output sequence o(n)– o(n) = c1 i(n) + c2 i(n-1) i*c2EE249Fall0716*c1+oPage 9Intuitive semantics• Example: FIR filter–single input sequence i(n)– single output sequence o(n)– o(n) = c1 i(n) + c2 i(n-1) i*c2EE249Fall0717*c1+oQuestions•Does the order in which actors are fired affect the final result?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!!EE249Fall0718Page 10Formal semantics: sequences•Actors operate from asequenceof input tokens to asequenceofActors operate from a sequenceof input tokens to a sequenceof 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 ft kEE249Fall0719sequence of tokens• In general, we consider the actors mathematically as functions from sequences to sequences (not from tokens to tokens)Ordering of sequences•Let X1and X2be two sequences of tokensLet 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 orderEE249Fall0720• Example: [ x1, x2 ] <= [ x1, x2, x3]• Example: [ x1, x2 ] and [ x1, x3, x4] are incomparablePage 11Chains of sequences•Consider the set S of all finite and infinite sequences of tokensConsider 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 EE249Fall0721(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 (Least) Upper Bound•Given a subset Y of S anupperboundof Y is an element z ofGiven a subset Y of S, an upperboundof 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 YEE249Fall0722bound(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)Page 12Complete Partial Order•Every chain in S has a least upper boundEvery


View Full Document

Berkeley ELENG C249A - Models of Computation

Documents in this Course
Load more
Download Models of Computation
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Models of Computation and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Models of Computation 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?