Multidimensional Dataflow Graphs - Signal Processing Systems - page 1150

Depending on the result, it generates a one-dimensional control token at the end of
each array. This corresponds to a CSDF-like behavior of actor C .Actor D obtains
the same control token in order to decide whether the result can be forwarded to the
destination actor E , or whether the array represents an intermediate result and needs
to be discarded. The graph contains hence a mixture of one- and multidimensional
communication with dynamic decisions.

7.3 Combination of Multidimensional Dataflow

with Finite State Machines

The model discussed in the previous section did not detail the inner structure
of an actor. In fact they can be modeled by any sort of language or description
technique. In particular, it is possible to define the dynamic behavior using
finite state machines. This allows a general description technique for all sorts of
actors, followed by a classification process whether an actor is static or dynamic.
Depending on this classification, appropriate analysis techniques can be applied.
The polyhedral analysis, for instance requires strictly static models of computation
in order to permit the embedding into a common grid. Since the multidimensional
FIFO uses the same interface than its one-dimensional counterpart, combination
with finite state machines is very similar to the concepts described in [ 4 ] .

8 Matrix-Based Multidimensional Dataflow

The WSDF model of computation as well as its subset MDSDF discussed in Sects. 4
and 2 produce and consume tokens along the Cartesian coordinate axes. While it is
possible to define in which order these tokens are read and written (see Sect. 5 ) , the
ensemble of sliding windows and produced tokens still follow a rectangular grid
for each edge. Furthermore non-rectangular windows need a decomposition into
subwindows [ 12 ] . Finally, for both WSDF and MDSDF horizontally adjacent input
windows are related to horizontally adjacent output tokens. The same holds for the
other dimensions.
Section 3 discussed a generalization of the sampling patterns by introduction
of corresponding sampling matrices. However overlapping sliding windows are not
considered. Section 7 , on the other hand, relaxed the strict relation between input
and output tokens. However, this has to be paid by reduced analysis capabilities.
Furthermore on each edge, the ensemble of all produced and consumed tokens still
follow a rectangular grid.
For applications that need non-rectangular sampling patterns, use of a matrix
based notation can be a corresponding remedy. Array-OL [ 5 ] follows such a