Multidimensional Dataflow Graphs - Signal Processing Systems - page 1141

Fig. 11 Hierarchical
block-based processing order.
Each rectangle corresponds
to a firing producing one or
several data elements

which divide the output image into smaller blocks, and scan these blocks in raster
scan order (Fig. 10 c ), because this reduces the amount of required internal chip
buffer [ 17 ] .
Both WSDF and MDSDF do not impose any order. Hence, in addition to the
actor schedule, also the processing order has to be specified. For both models of
computation, specifying the processing order of one input or output array automat-
ically defines the order for all other arrays related to the considered actor, because
there is a strict relation between produced output tokens and read input windows . 3
Nevertheless, each actor can have its own processing order. Only feedback loops
within a dataflow graph might limit the admissible processing orders . 4

5.2 Specification of the Processing Order

While scheduling multidimensional dataflow graphs will be subject to Sect. 6 , this
section is dedicated to the processing order. Obviously, it is possible to define arbi-
trarily complex processing orders for each actor. However, this complicates further
analysis and implementation. Fortunately, many applications can be described by
relatively simple processing orders. They can be defined by clustering the actor
firings hierarchically into blocks.
Figure 11 depicts a corresponding example. In contrast to previous figures,
here each rectangle corresponds to one actor firing. Each of them generates a
multidimensional token on each output edge and reads a sliding window on each
input edge. Horizontally adjacent firings in Fig. 11 generate horizontally adjacent
output tokens and read horizontally adjacent input windows. The same holds for the
vertical dimension.
The processing order is now defined by clustering the actor firings into a
hierarchy of blocks as depicted in Fig. 11 . The small rectangles with the thinnest
borders correspond to the individual firings (hierarchy level 0). The rectangles with
two rows and three columns having a medium sized border define the first level of

3 Note that this relation will be broken in Sect. 7
4 Section 3 introduced a processing order to enumerate sample points that are not part of a
rectangular grid. This section differs in that it considers rectangular instead of arbitrary sampling
patterns. The defined processing orders are hence purely to describe the application behavior, and
are not a prerequisite for the balance equation.