DATAFLOW PROCESS NETWORKS

Edward A. Lee

Electronics Research Laboratory Memorandum number UCB/ERL M94/53
July, 1994

[PDF]

ABSTRACT

This paper reviews a model of computation used in industrial practice in signal processing soft-ware environments and experimentally in other contexts. It gives this model the name "dataflow process networks," and studies its formal properties as well as its utility as a basis for program-ming language design. Variants of this model are used in commercial visual programming sys-tems such as SPW from the Alta Group of Cadence (formerly Comdisco Systems), COSSAP from Synopsys (formerly Cadis), the DSP Station from Mentor Graphics, and Hypersignal from Hyperception. They are also used in research software such as Khoros from the University of New Mexico and Ptolemy from the University of California at Berkeley.

Dataflow process networks are shown to be a special case of Kahn process networks, a model of computation where a number of concurrent processes communicate through unidirectional FIFO channels, where writes to the channel are non-blocking, and reads are blocking. In dataflow pro-cess networks, each process consists of repeated "firings" of a dataflow "actor". An actor defines a (usually functional) quantum of computation. By dividing processes into actor firings, the con-siderable overhead of context switching incurred in most implementations of Kahn process net-works is avoided.

This paper relates the dataflow process networks to other dataflow models, including those used in dataflow machines, such as static dataflow and the tagged-token model. It also relates dataflow process networks to functional languages such as Haskell, and shows that modern language con-cepts such as higher-order functions and polymorphism can be used very effectively in dataflow process networks. A number of programming examples using a visual syntax are given.

This research in sponsored in part by ARPA, under the RASSP program, in cooperation with the United States Air Force, and by the National Science Foundation (MIP9201605).