Dataflow Process Networks (DPNs)

Dataflow process networks define a very general model of computation for distributed computations. A DPN consists of a finite set of process nodes that are connected by FIFO buffers. Each FIFO buffer has exactly one process writing values to it (its producer node), and one process reading values from it (its consumer node). Since the size of the FIFO buffers is assumed to be unbounded, there is no need for a global coordination of the processes, i.e., each process node CAN fire whenever it has suffienct input data. When a node fires, it consumes some of the data values in its input buffers and produces data values in its output buffers.

DPNs are popular also due the liberal style, i.e., they do not enforce the use of special programming languages. However, some restrictions have to be considered to make sure that the execution of a DPN does not depend on the execution order of its process nodes. In particular, once a node becomes enabled, it must not become disabled by the firings of the nodes that produce data on its input buffers. For this reason, Kahn imposed the requirement that the nodes must perform blocking reads, i.e. if a data value should be read from an empty input buffer, then the reading process must wait (is blocked) until the desired data values arrive in the buffer. If the behavior of process nodes is specified by firing rules that make use of pattern matching as used in functional languages like ML, Haskell or F#, this requirement is fulfilled by demanding that patterns must only match with finite prefixes of sequences.

Besides these requirements that assure the confluence of a DPN, Kahn also assumed that process nodes perform a sequential code. This became important by the observation of Plotkin and Milner when they tried to prove the equivalence of operational and denotational semantics of functional languages. It turned out that denotational semantics was stronger since there are functions that cannot be implemented by sequential programs with the blocking read restriction (like Berry's Gustave function). On the other hand, sequential functions are too strong, so that one was interested in the right set of functions that lead to the desired equivalence of operational and denotational semantics. This gave rise to the full abstraction problem that was only resolved much later by Ong and others [HyOn00].

A particular useful set of DPNs are static and cyclo-static DPNs. This subset of DPNs has only nodes that always read the same number of values from particular input buffers. However, they may read different numbers of values from different input buffers. Because of this static behavior, one can check by solving a linear equation system whether the DPN can run with finite size FIFO buffers, and one can effectively determine the size of these buffers as well as a static schedule to run the DPN on a sequential machine.

These techniques are not sufficient to map DPNs to parallel machines, since then one either needs a global coordination, e.g. by adding backpressure communication, or a global schedule. However, from Petri net theory it is known that the use of S and T invariants further restricts the set of systems so that this problem is solved as well. We are currently adapting these results to DPNs to allow a multithreaded implementation of DPNs.

References

			[Kahn74] G. Kahn The Semantics of a Simple Language for Parallel Programming Information Processing
			[HyOn00] J.M.E. Hyland and C.-H.L. Ong On Full Abstraction for PCF Information and Computation
			[PaPL95] T.M. Parks and J.L. Pino and E.A. Lee A comparison of synchronous and cyclo-static dataflow Asilomar Conference on Signals, Systems and Computers (ACSSC)
			[Dese92] J. Desel A Proof of the Rank Theorem for Extended Free Choice Nets Application and Theory of Petri Nets