Polyhedral Process Networks - Signal Processing Systems - page 1331

W := { R[i,j] -> a[i,j] } * D;
R := { S[i,j] -> a[i-1,j-1] } * D;
S := { R[i,j] -> [1,i,2,j,3]; S[i,j] -> [4,i,5,j,6] };
last W before R under S;
produces

([K, N] -> { R[i, j] -> S[1 + i, 1 + j] : i >= 0 and
i<=-3+Kandj>=0andj<=-3+N},
[K,N]->{ })
The output contains both the union of the M i and U . Here, U is the empty set because
all of the read accesses read a value that was previously written.
If there is more than one write access relation in the input of Operation 7 , then the
computation is a little bit more complicated. After computing the lexicographically
maximal element of a write that shares i iterator values with the read, we still need
to check that there is no other write in between. That is, we need to check if there is
a write from a different write access that also shares i iterator values with the read,
also occurs before the read, but occurs after the already found write. Again we have
to consider all possible cases of shared iterator values between the two writes, now
from i to 2 d

1, as a write that occurs after a given iteration and that has fewer
iterator values in common with the given iteration will be executed after an iteration
that has more iterator values in common.
The above sketch of an algorithm can still be significantly improved by checking
the write access relations in the appropriate order and by taking into account the fact
that the dimensions that correspond to the statement locations have fixed values. For
a more detailed description, we refer to [ 8 ] , where a variant of the above algorithm
is applied directly on “quasts”, the output structure of piplib which we will not
explain here.

+

5.2 Reuse

A process network constructed using the standard dataflow analysis of the previous
section will always send data from the process that corresponds to the statement
that wrote a given value in the sequential program to the process that corresponds
to the statement that read the given value, even if the same value is read multiple
times from the same process. Now, in practically any form of implementation of
process networks, sending data from a process to itself (or simply keeping it) is
much cheaper than sending data to another process. It is therefore better to only
transmit data from one process to another the first time it is needed.
Obtaining a network that only transmits data to a given process once is actually
fairly simple. When applying Operation 7 from the previous section, instead of
only supplying a list of write accesses to the array read by the read access R ,we
extend the list with all read accesses to the given array (including R itself) from