Multidimensional Dataflow Graphs - Signal Processing Systems - page 1137

leads to the upper left output token. The window right to the upper left input window
also leads to the output token right to the upper left output token. In other words,
there is a strict and static relation which input window contributes to which output
token.
Because of the chosen window size, the windows do not overlap in horizontal
direction, since the window moves by two data elements in the y -direction. In
vertical direction, on the other hand, the windows overlap by one row, since the
window moves by two data elements while having a size of three rows. In other
words, while traditional schemes such as MDSDF assume that a data element will
be read only once, this is not true any more for WSDF. In particular, data elements
cannot always be discarded after the first reading operation.
The extended border handles the cases when the window exceeds the proper
input array. Note that the size of the extended border has to be chosen in such a
way, that sampling starts in the “upper left” corner of the extended array, and that
all data elements of the extended arrays will be included in the sampling process.
Note, furthermore that the streaming dimension is directed in x -direction, and that
the model can handle more than two-dimensional arrays.
Figure 8 b depicts a graphical notation and all necessary parameters in order to
describe the above mentioned array transport. Obviously, it is necessary to define
for each edge i the window size by means of the vector c i . Each of its components
specifies the size in the corresponding coordinate direction. Vector c i describes by

how many data elements the window moves in the different directions, where the
first coordinate corresponds to the x -dimension, the second to the y -dimension, and
so on.
Vector p i defines the produced output token size. Note that the produced token
size does not need to correspond to the overall array size. Consider for instance
actor B of Fig. 8 a . For each firing, it only produces a p 2 =(

Δ

token, while
the overall array consists of two rows and three columns. In other words, WSDF
explicitly models that a huge array can be generated successively by smaller
operations. By these means, it both reveals inherent data parallelism, and allows
for memory efficient implementations, where the buffers associated to the edges
can be smaller than one complete array.

1 , 1 )

4.2.2 Border Extension

As discussed in Sect. 4.1 , border processing is a fundamental aspect of local
algorithms. To this end, the vectors b i and b i in Fig. 8 define the size of the extended
border. In case of two dimensional applications, both vectors b i =

b i , 1 ,

b i , 2

b i , 1 ,

b i , 2 have two dimensions and b i , 1 and b i = defines the lower border, b i , 2