Digital Signal Processing Reference
In-Depth Information
Fig. 7
Localized dependence
graph of convolution
algorithm
The dependence graph in Fig.
7
is
shift-invariant
in that the dependence vector
structure is identical of each (circled) lattice point of the iteration space. This
regularity and modularity is the key feature of a systolic computing algorithm that
lends itself for efficient systolic array implementation.
Due to the shift invariant nature, a DG of a localized RIA algorithm can be
conveniently represented by the set of indices
{
i
;
p
0
≤
Pi
≤
q
0
}
and the dependence
vectors
D
at each index point.
3.4
Mapping an Algorithm to a Systolic Array
)
∈
Z
+
is a mapping from each index point
i
in the index space
R to a positive integer t(
i
) which dictates
when
this iteration is to be executed. An
assignment
A:
i
A
schedule
S:
i
→
t
(
i
p(
i
) is a mapping from each index point
i
onto a PE index p(
i
)
where
the corresponding iteration will be executed. Given the dependence graph of
a given algorithm, the development of a systolic array implementation amounts to
find a mapping of each index point
i
in the DG onto (p(
i
), t(
i
)).
Toward this goal, two fundamental constraints will be discussed. First, it is
assumed that each PE can only execute one task (loop body) at a time. As such,
a
resource constraint
must be observed:
→
Resource Constraints
if t
(
i
)=
t
(
j
)
,
i
=
j
,
then p
(
i
)
=
p
(
j
)
;andif p
(
i
)=
p
(
j
)
,
i
=
j
,
then t
(
i
)
=
t
(
)
.
(11)
j
In addition, the data dependence also imposes a partial ordering of schedule. This
data dependence constraint
can be summarized as follows:
