Decidable Dataflow Models for Signal Processing: Synchronous Dataflow and Its Extensions - Signal Processing Systems - page 1064

Fig. 1 Dataflow graph of a
simple DSP algorithm

Read Filter Play

Store

or fired , when enough input data are available. An arc is a FIFO channel that delivers
data samples, also called tokens , from an output port of the source node to an input
port of the destination node. If a node has no input port, the node becomes a source
node that is always executable. In DSP algorithms, a source node may represent
an interface block that receives triggering data from an outside source. The “Read”
block in Fig. 1 is a source block that reads audio data samples from an outside
source. A dataflow graph is usually assumed to be executed iteratively as long as the
source blocks produce samples on the output ports.
The dataflow model of computation was first introduced as a parallel program-
ming model for the associated computer architecture called dataflow machines [ 6 ] .
While the granularity of a node is assumed as fine as a machine instruction in
dataflow machine research, the node granularity can be as large as a well-defined
function block such as a filter or an FFT unit in a DSP algorithm representation. The
main advantage of the dataflow model as a programming model is that it specifies
only the true dependency between nodes, revealing the function-level parallelism
explicitly. There are many ways of executing a dataflow graph as long as data
dependencies between the nodes are preserved. For example, blocks “Filter” and
“Store” in Fig. 1 can be executed in any order after they receive data samples
from the “Read” block. They can be executed concurrently in a parallel processing
system.
To execute a dataflow graph on a target architecture, we have to determine where
and when to execute the nodes, which is called scheduling . Scheduling decision
can be made only at run-time for general dataflow graphs. A dynamic scheduler
monitors the input arcs of each node to check if it is executable, and schedules the
executable nodes on the appropriate processing elements. Thus dynamic scheduling
incurs run-time overhead of managing the ready nodes to schedule in terms of
both space and time. Another concern in executing a dataflow graph is resource
management. While a dataflow graph assumes an infinite FIFO queue on each arc, a
target architecture has a limited size of memory. Dynamic scheduling of nodes may
incur buffer overflow or a deadlock situation if buffers are not carefully managed. A
dataflow graph itself may have errors to induce deadlock or buffer overflow errors. It
is not decidable for a general dataflow program whether it can be executed without
buffer overflow or a deadlock problem.
On the other hand, some dataflow models have restricted semantics so that the
scheduling decision can be made at compile-time. If the execution order of nodes is
determined statically at compile-time, we can decide before running the program if
the program has the possibility of buffer overflow or deadlock. Such dataflow graphs
are called decidable dataflow graphs . More precisely, a dataflow is decidable if and
only if a schedule of which length is finite can be constructed statically. Hence,