Transcript DATAFLOW PROCESS NETWORKS

DATAFLOW PROCESS
NETWORKS
Edward A. Lee
Thomas M. Parks
Abstract
• This paper presents a model of computation
called “dataflow process networks”.
• Special case of Kahn process networks
• Relations with other dataflow models
Motivation
•
Programming methodology: “graphical dataflow
programming”
–
–
–
•
•
Visual syntax
Hierarchy
Examples: Khoros, Ptolemy, SPW, COSSAP, and the
DSP Station.
Most environments do not define a language in
any strict sense
Can be either interpreted or compiled
Process Networks
• A process is a mapping from one or more input
sequences to one or more output sequences
• A process network: concurrent processes
communicate only through one-way FIFO
channels with unbounded capacity.
process
One-way FIFO
process
Kahn Process
• The process is constrained to be continuous
– Prefix ordering of sequences: X  Y
– Set of sequence can be ordered as well:
X  Y, if Xi  Yi for each i
– Increasing chain of sequences:  = {X0, X1, …}, where X0  X1 
….
– Least upper bound of  : 
– Functional process F: SpSq
• Continuity
F() = F()
• Monotonicity
X  X’  F(X)  F(X’)
Network of Processes
• A network: a set of relations between sequences.
X = F(X,I)
• Any X that forms a solution is called a fixed point.
Continuity of F implies that there will be exactly
one “minimal” fixed point.
• Execute the network by first setting I =  and
finding the minimal fixed point, then by iterative
computation to find other solutions.
Nondeterminism
• A useful property is an ability to express nondeterminism.
• Nondeterminism leads to failure of continuity
• It can be added to Kahn networks by any of the five
methods:
–
–
–
–
–
Allowing processes to test inputs for emptiness
Allowing processes to be internally nondeterminate
Allowing more than one processes to write to a channel
Allowing more than one processes to consume data from a channel
Allowing processes to share variables
• Example
Example of Nondeterminism
B
A
D
E
C
• Merge node D
• May be nondeterminate, may also be determinate
• If D is a nondeterminate merge, then it is not a
Kahn process network
Streams
• One camp defines streams recursively, using cons-like list
constructors and usually treats them functionally using lazy
semantics. Another camp sees streams as channels. There
is no concept of simultaneity of tokens in the channel
model.
– A unique approach blends the benefits of a declarative style with
the simplicity of the channel model
– A more general approach is to associate with each stream a
“clock”, which defines the alignment of tokens in different
streams.
• A useful stream model must be as good at losing data as it
is at storing data.
Dataflow Process Networks
• Dataflow actor
– When it fires, it maps input tokens into output tokens
• Firing
– Consumes input tokens and produces output tokens
– A sequence of such firings is a particular type of Kahn
process that we call a dataflow process;
– a network of such processes is called a dataflow process
network.
• Firing rules
– Specify when an actor can fire
Firing Rules
– Select actor:
• R1 = {[*], , [T]}
• R2 = {, [*], [F]}
• R1 = {[*], }
• R2 = {, [*]}
• These rules are not sequential.
F
Control
DATA INPUT
DATA OUTPUT
merge
– Nondeterminate merge
T
select
• Definition:
R = {R1, R2, …, RN}
• Examples:
Sequential Firing Rules
•
Identifying sequential firing rules
–
For the example of select:
1.
2.
3.
4.
–
j = 3.
Subsets: {R1} and {R2}
R1 = {[*], , } and R2 = {, [*], }
Repeat till all modified firing rules become empty
For the nondeterminate example of the merge
node, the procedure fails at step 1.
Relationship to Higher-order
Function
• Define
F = map(f)
where F(R:X) = f(R):F(X)
• The definition is recursive
• Typically f requires only some finite
number of tokens on each input, while the
function returned by F can take infinite
stream argument.
Sequential Process
Sequential  continuous  monotonic
monotonic
X  Y  F(X)  F(Y)
continuous
 = {X0, X1, … } s.t. X0  X1  … ,
F() = F()
sequential
X = {X1, X2, …,Xp}, i, 1ip, s.t.
Y  X where Yi = Xi, F(Y) =F(X), when F is continuous.
• Theorem: if an actor function f has
sequential firing rules, then the process F =
map(f) is sequential
Relationship to Kahn Process
Networks
A
…|x3|x2|x1
B
• A special case of Kahn process networks
• Suppose A produces 1 token each process while B
consumes 3 each process
• Blocking read for B  scheduling of A and B
Execution Models
• A variety of execution models associated
with a dataflow process network.
–
–
–
–
–
Concurrent processes
Dynamic scheduling
Static scheduling
Compilation of dataflow graphs
Tagged token model
Experimenting With Language
Design
• The Ptolemy system
– Synchronous dataflow domain (SDF)
– Dynamic dataflow domain (DDF)
– Boolean dataflow domain (BDF)
• Visual hierarchy
– Firing subgraphs – the balance equations
– Side effects and state
• Function arguments
– Parameters and input streams
Experimenting With Language
Design
•
•
•
•
•
•
Firing rules and strictness
Recurrences and recursion
Higher order function
The tagged-token execution model
Data types and polymorphism
Parallelism