Digital Signal Processing Reference
In-Depth Information
Fig. 17
WDF graph using
one- and multidimensional
token transport.
Bold
arrays
correspond to
multidimensional token
transport,
thin arrays
to
one-dimensional streams of
data.
Dashed circles
define
initial tokens respectively
arrays
A
B
D
E
C
7.2
Windowed Dataflow (WDF)
The multidimensional FIFO described in the previous section permits to introduce
a new class of multidimensional dataflow that allows for dynamic decisions, called
windowed dataflow (WDF)
. Such a dataflow graph consists of actors interconnected
by two types of edges. These edges either represent one-dimensional streaming
communication as employed for one-dimensional models of computation, or mul-
tidimensional communication represented by the multidimensional FIFO. In both
cases actors can request one or more input tokens, and write one or more output
tokens. The tokens might be one- or multidimensional. If only one of these tokens is
not available, the actor blocks, leading to deterministic applications. In this case, we
can also check whether enough input tokens are available on a given input edge. If
not, an alternative processing path can be taken. This leads to the most general class
This general approach destroys the strict relation between input windows and
output tokens, being fundamental for MDSDF and WSDF. Since an actor might
decide to consume one input window, and then produce ten output tokens without
reading any further input, it is not true anymore that adjacent input windows are
related to adjacent output tokens. In particular, it is not possible anymore to define a
processing order per actor. Instead each edge can have its own read and write order.
In other words, an actor having two input ports might read the array on the first input
edge in horizontal raster scan order, the array on the second input edge in vertical
raster scan order. While this increases the expressiveness, it complicates the data
dependency analysis and is hence not allowed in WSDF nor MDSDF.
Figure
17
illustrates a simple example graph demonstrating the interaction
between one- and multidimensional dataflow. The purpose consists in iteratively
filtering an input image until a certain exit condition is met. This corresponds to the
behavior of a
while-loop
.Actor
A
is supposed to generate the multidimensional input
array. Actor
B
has two multidimensional inputs. Depending on a one-dimensional
control token, actor
B
either filters the array generated by actor
A
and discards the
array on the second multidimensional input, or it filters its previous output and
does not read anything from actor
A
.Actor
C
filters the output of actor
B
using
a window of size
(
1
,
1
)
, in order to determine whether the exit condition is met.
