Digital Signal Processing Reference
In-Depth Information
Using
iscc
to perform these calculations, we have as input
A := [N] -> { S[i, j] -> a[i + j] : 0 <= i < N and
0<=j<i};
card (Aˆ-1);
ub (card (Aˆ-1));
and as output
[N] -> { a[i0] -> ((-1 + N) - [(i0)/2]) :
i0 <= -3 + 2N and i0 >= N;
a[i0] -> (i0 - [(i0)/2]) :
i0 <= -1 + N and i0 >= 1 }
([N] -> { max(1/2
*
N) : N >= 3;
max(1/2
*
N) : N = 2 }, False)
Note that the
ub
operation produces two results, one is the actual upper bound and
the other is a boolean that indicates whether the upper bound is definitely reached,
i.e., whether the upper bound is known to be equal to the maximum. In this example,
the upper bound may not be equal to the maximum.
4.5
Polyhedral Scanning
When writing out code for a process in a process network, we not only need to
make sure that an operation is performed for each element of its iteration domain,
but we also need to insert the appropriate reading and writing primitives in the
appropriate places. In particular, if
C
i
is a communication channel with the given
process as its source, then a write to the communication channel needs to be inserted
in each element of the domain of its mapping relation
M
i
. Similarly, if
C
j
is a
communication channel with the given process as its target, then a read from the
communication channel needs to be inserted in each element of the range of its
mapping relation
M
j
. Each of these domains and ranges is a polyhedral set and we
see that we need to generate code for visiting each element of these sets. That is, we
need the following operation.
Operation 6 (Code Generation).
Input:
A polyhedral relation R with
ran
R
d
Output:
Code for visiting each element in
dom
R in lexicographic order of their
image
⊆{}×
Z
The condition that the range of
R
needs to live in a single space, i.e., with a fixed
label and a fixed dimension, ensures that we can evaluate the lexicographic order.
