Polyhedral Process Networks - Signal Processing Systems - page 1346

Taking the difference yields

⎧
⎨

2 ( N − 2 )+ 3 if ( i , j , 1 ) ∈ ran M ∧ i < K − 2 ∧ j < N − 2

( , , , )=

n K N i j ( − ) − + ( , , ) ∈ ∧ < − ∧ ≥ −

3 N 2 j 2 if i j 1 ran M i K 2 j N 2

⎩

( K − i )( N − 2 ) − j + 2 f ( i , j , 1 ) ∈ ran M ∧ i ≥ K − 2 .

The maximum over all reads in ran M occurs in the first domain and is equal to
2 1, which is the value shown on the first edge in Fig. 2 .

In iscc , the computation can be performed a follows.
M := [K, N] -> { R[i, j] -> S[1+i, 1+j] : i >= 0 and
i<=-3+Kandj>=0andj<=-3+N};
S := { R[i,j] -> [i,j,0]; S[i,j] -> [i+1,j+1,1] };
W:=(S>>S) * (ran M -> dom M);
R := (ran M) >> (ran M);
ub (((card W) - (card R)) * [K,N] -> { : K,N >= 10 });
The first two lines specify the input communication channel mapping from
Example 14 and the schedule from Example 18 . The next two lines construct the
relations W and R . When the >> operator is applied to a pair of relations, it returns
a relation between the domains of the input relations based on the lexicographic
order in the corresponding images. Note that we only need the schedule during the
construction of W since R is a relation between elements from the same iteration
domain. In the final line, we intersect the result of the counting problem with
constraints on the parameters. This intersection is only applied in order to produce
nicer output. Without the intersection, the output would contain several special cases
involving small values of the parameters. The final output is as follows.
([K, N] -> { max((-1 + 2 * N)) : N >= 10 and K >= 10 },
True)
Note that in this case the upper bound is determined to be equal to the maximum.

( N − 2 )+ 3 = 2 N −

8.2 Reordering Channels

For channels that have been identified as exhibiting reordering using the technique
of Sect. 6.1 , we need to choose where we want to perform the reordering of the
tokens. One option is to perform the reordering inside the channel itself. In this
case we can apply essentially the same technique as that of the previous section to
compute an upper bound on the minimal number of locations needed to store all
elements in the buffer at any given time. However, since the tokens now have to
be reordered, we need to be able to address them somehow. An efficient mapping
from read or write iterators to the internal buffer of the channel may require more
space than strictly necessary. We refer to [ 5 ] for an overview and a mathematical
framework for finding good memory mappings.