Dataflow Networks

Dataflow Networks is a graphical MoC very closely related to Process Networks. In this model arcs also represent FIFO queues. But now the nodes of the graph, instead of representing processes, represent actors. Instead of responding to the simple the blocking-read semantics of Process Networks, actors use firing rules that specify how many tokens must be available on every input for the actor to fire (see figure 1.5). When an actor fires, it consumes a finite number of tokens and produces also a finite number of output tokens. A process can be formed by repeated firings of a dataflow actor.

An actor may have more than one firing rule. The evaluation of the firing rules is sequential in the sense that rules are sequentially evaluated until at least one of them is satisfied. Thus an actor can only fire if one or more than one of its firing rules are satisfied. In general, though, synchronous dataflow actors have a single firing rule of the same kind: a number of tokens that must be available at each of the inputs. For example, an adder with two inputs has a single firing rule saying that each input must at least have one token.

As pointed out by [Parks, 1995] breaking down processes into smaller units such as dataflow actors firings, makes efficient implementations possible. Restricting the type of dataflow actors to those that have a predictable consumption and production pattern makes it possible to perform static, off-line analysis to bound the memory.

In Dataflow Networks instead of suspending a process on blocking read or non-blocking write, processes are freely interleaved by a scheduler that determines the sequence of actor firings. The biggest advantage is that the cost of process suspension and resumption is avoided[Lee and Park, 1995].

In many signal processing applications the firing sequence can be determined statically at compile time. The class of dataflow process networks where this is possible are called ``synchronous dataflow networks'' and will be commented in next section.

Dataflow graphs have data-driven semantics. The availability of operands enables the operator and hence sequencing constraints follow only from data availability. This feature has its limitations. The principal strength of dataflow networks is that they do not over-specify an algorithm by imposing unnecessary sequencing constraints between operators [Buck and Lee, 1994].

Figure 1.5: Dataflow Process Network
\includegraphics[%
width=0.55\textwidth]{images/ch1-Foundations/ps/DPN.eps}

2004-10-18