Multidimensional Dataflow Graphs - Signal Processing Systems - page 1145

Fig. 13 Firing grid for
processing orders not
following the horizontal raster
scan order. ( a ) Produced
output tokens, ( b ) Firing grid,
( c ) Data dependency analysis

a b

c

6.2 Different Processing Orders

The careful reader might have observed that the above reasoning is only valid as long
as all actors follow horizontal raster scan order. As however discussed in Sect. 5 , this
is not necessarily the case. Solving this problem is possible by performing a grid
point remapping. This means that the schedule is still constructed by traversing the
common grid in raster scan order. However, when computing the data dependencies,
it is taken into account that the actors themselves show a different processing order.
To illustrate the principles, assume that actor B of Fig. 8 now generates the output
tokens in vertical raster order as shown in Fig. 13 a . Every data element is produced
in a single firing. Hence, an overall number 2 × 3 firings is necessary to generate

the output array. Figure 13 b depicts the corresponding firing grid of actor B ,

consisting of 2

( 2 , 3 )

3 crosses. It is defined that the firing grid is still traversed in raster
scan order. Consequently, in order to take the correct processing order of actor B
into account, a mapping between the firing grid points and the actually produced
output token has to be established. The result is depicted by numbers in Fig. 13 a , b.
For instance, the second firing produces the first data element in the second row of
the output array.
As discussed in Sect. 5 , the processing order has no impact on the relation
between input windows and output tokens. Hence the output token number 2
still depends on the lower left sliding window as illustrated in Fig. 8 a . Since the
processing order of actor A is assumed to be the same than in Sect. 6.1 , this leads
to the dependency analysis shown in Fig. 13 c . It can be derived from the fact that
the second firing of actor B reads the lower left sliding input window whose data
elements are produced by the source firings being origins of the arrows in Fig. 13 c .
With this new dependency analysis, a valid schedule can be derived in the same
manner as explained in Sect. 6.1 .
Reference [ 12 ] shows how this can be mathematically expressed in form of
integer programs solvable by cplex [ 8 ] , or the PIP Library [ 1 ] . Furthermore it
discusses the impact of non-overlapping grids. Since all these aspects exceed the
scope of this topic, the interested reader is refereed to [ 12 ] .

×