Polyhedral Process Networks - Signal Processing Systems - page 1343

linear transformation A j . Not only would this allow us to compute potentially tighter
bounds on the buffer sizes, but it may even change the types of the communication
channels.

Example 21. Consider once more the program in Fig. 8 . InExample 16 we have
shown that the only channel in the corresponding network has reordering. If we
reverse the second loop, however, i.e., if we apply the transformation j

→− j + N ,

then the mapping on the channel becomes

M = { w → r | 0 ≤ w ≤ N ∧ r = w }

and we have

T = { w 1 → w 2 | 0 ≤ w 1 , w 2 ≤ N ∧ w 1 > w 2 ∧ w 1 < w 2 }.

This set is clearly empty and so the communication channel has become a FIFO.

The example shows that if we were to apply general linear transformations, then
we would need to do this before the detection of channel types of Sect. 6 . Infact,if
we want to detect reuse, as we did in Sect. 5.2 , then we would need to do this reuse
detection after any linear transformation. The reason is that a linear transformation
may change the internal order inside an iteration domain, meaning that what used
to be a previous iteration, from which we could reuse data, may have become a
later iteration. On the other hand, the dataflow in the sequential program imposes
some restrictions on which linear transformations are valid, so we need to perform
dataflow analysis (Sect. 5 ) before any linear transformation. The solution is to first
apply standard dataflow analysis (Sect. 5.1 ) , then to perform linear transformations
and finally to detect reuse inside the communication channels that were constructed
in the first step. A full discussion of general linear transformations is beyond the
scope of this chapter.
There is however one case where we are forced to apply a linear transformation,
and that is the case where not all iteration domains have the same dimension. Before
we can merge two iteration domains, they have to reside in the same space. In
particular, they need to have the same dimension. Let d be the maximal dimension of
any iteration domain, then we could could expand a d i -dimensional iteration domain
with d i ≤

d using the transformation I d , d i . This transformation effectively pads the
iteration vectors with zeros at the end. This may, however, not be the best place
to insert the zeros. A simple heuristic to arrive at better positions for the zeros is
to look at the communication channels between a lower-dimensional domain and a
full-dimensional domain and to insert the zeros such that iterators that are related
to each other through the communication channels are aligned. Note that inserting
zeros does not change the internal order inside the iteration domain. The same holds
for any scaling that we may want to apply based on essentially the same heuristic.

Example 22. Consider the communication channel between processes b and c in
the network of Fig. 11 (see Example 17 ) . The first process has a one-dimensional