Multidimensional Dataflow Graphs - Signal Processing Systems - page 1140

border processing. The first solution is closely related to the initial tokens known
for MDSDF. In the second case, the idea is to make the extended border big enough
such that it can cover complete sliding windows. Then an actor can fire without
needing any input tokens. The result of these firings can then be fed back to its own
inputs. Further details on this aspect can be found in [ 11 , 12 ] . The same holds for
the modeling of windows that do not have a rectangular form.

5 Processing Order

One-dimensional dataflow models of computation describe streams of tokens that
flow through a graph of actors. Their translation into a concrete implementation
is thus relatively straightforward by mapping the edges of the graph to FIFOs.
These FIFOs receive, store and forward the tokens without changing their order. The
next step for translating a one-dimensional dataflow graph into an implementation
consists in generation of an actor schedule. It defines the temporal order by which
the dataflow actors are executed [ 7 ] .
Compared to this approach, multidimensional dataflow graphs offer an additional
degree of freedom that needs to be refined during system implementation as
discussed in the following subsections.

5.1 Refinement of Multidimensional Dataflow Graphs

Multidimensional models of computation as discussed in Sects. 2 and 4 represent
the transport of arrays, while these arrays are not atomic, but are produced and read
in smaller parts. Compared to 1D models, this introduces a new degree of freedom,
namely the processing order . The dataflow graph depicted in Fig. 8 a , for instance,
clearly defines which token produced by actor B depends on which input tokens
generated by actor A . However, the order, by which the window samples the input
array and hence the order by which the output tokens are generated, is still open.
Figure 10 shows some possible orders by which actor B of Fig. 8 a might generate
the output array. There are very well applications which assume a horizontal raster
scan order that first moves in horizontal, and then in vertical direction (Fig. 10 a ).
But the opposite is of course also viable (Fig. 10 b ). There are even applications

a b c

Fig. 10 Processing order of actor B belonging to Fig. 8 a . ( a ) Horizontal raster scan. ( b ) Vertical
raster scan. ( c ) Block-based