Digital Signal Processing Reference
In-Depth Information
be constructed in many different ways. Here, we will describe just one of those.
Let
d
i
be the dimension of the iteration domain
D
i
and let
d
be the maximal such
dimension, i.e.,
d
max
i
d
i
. We define a relation between on one side each of the
iteration domains and on the other side a (2
d
=
+
1)-dimensional space. The odd
dimensions 2
k
1) in this space are equated to iterators
k
.Theeven
dimensions 2
k
(0 to 2
d
) represent the “position” of the
k
th loop surrounding the
given statement (for
k
+
1(1to2
d
−
d
). The position could
be a line number or a sequence number. For iteration domains with
d
i
<
<
d
), or the statement itself (for
k
=
d
, only
dimensions up 2
d
i
are defined as above. The remaining dimensions can be assigned
an arbitrary value, say zero.
To see that the lexicographic order on the target space corresponds to the
execution order of the input program, note that if the first dimension in which two
schedule iteration vectors differ is 2
n
, then the two corresponding statements share
n
loops, the iterators of these
n
loops have the same value in both vectors and the
statements have a different location inside the
n
th loop. If the first dimension in
which two schedule iteration vectors differ is 2
n
+
1, then the two corresponding
statements share at least
n
1 loops, the iterators of first
n
loops have the same
value in both vectors, but the iterator of the next loop has a different value in the
two vectors.
+
Example 6.
If we take line numbers as positions, then the schedule corresponding
{
R
(
i
,
j
)
→
(
1
,
i
,
2
,
j
,
3
)
}∪{
S
(
i
,
j
)
→
(
4
,
i
,
5
,
j
,
6
)
}∪{
W
(
i
,
j
)
→
(
4
,
i
,
5
,
j
,
9
)
}.
(7)
Combining all this information, we have the following definition.
Definition 4 (Polyhedral Model).
The
polyhedral model
of a sequential program
consists of a list of statements, where each statement is in turn represented by
An identifier
i
,
A dimension
d
i
,
d
i
,
An iteration domain (a polyhedral set)
D
i
⊆{
i
}×
Z
A list of accesses and
A schedule.
Finally, each array access is represented by an identifier, an access relation
(a polyhedral relation) and a type (read or write).
The use of a polyhedral model imposes the following restrictions on the input
program:
Static control flow,
Pure functions and
Loop bounds, conditions and index expressions are quasi-affine expressions in
the parameters and the iterators of enclosing loops.
