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 j 3 2 Subsets R1 and R2 3 R1 and R2 4 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 continuous sequential X Y F X F Y X0 X1 s t X0 X1 F F 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
View Full Document
Unlocking...