Digital Signal Processing Reference
In-Depth Information
3.5
Linear Schedule and Assignment
A
linear schedule
is an integer-valued scheduling vector
s
in the index space such
that
s
T
i
t
0
∈
Z
+
t
(
i
)=
+
(16)
where
t
0
is a constant integer. The data dependence constraint stipulates that
s
T
d
>
0 for any dependence vector
d
.
(17)
Clearly, all iterations that reside on a hyper-plane perpendicular to
s
, called
equi-temporal hyperplane
must be executed in parallel at different PEs. The equi-
temporal hyperplane is defined as
Q
s
T
i
. According to the
resource constraint, the maximum number of index points in
Q
determines the
minimum size (number of PEs) of the systolic array.
Assume that the PE index space is a
m
=
{
i
|
=
t(
i
)
−
t
0
,
i
∈
DG
}
1 dimensional subspace in the iteration
index space. Then the assignment of individual iterations
i
to a PE index p(
i
) can be
realized by projecting
i
onto the PE subspace along an integer-valued assignment
vector
a
.Definea
m
−
1) integer-valued
PE basis
matrix
P
such that
P
T
a
×
(
m
−
=
0
,
then a
linear PE assignment
can be obtained via an affine transformation
P
T
i
p
(
i
)=
+
p
0
.
(18)
P
T
i
t
(
)
i
=
.
(19)
p
(
i
)
The node mapping procedure can also be extended to a subset of nodes where
external data input and output take places. The same node mapping procedure will
indicate where and when these external data I/O will take place in the systolic array.
This special mapping procedure is also known as
I/O mapping
.
Different PEs in the systolic array are inter-connected by local buses. These buses
are implemented based on the need of passing data from an index point (iteration)
to another as specified by the dependence vectors. Hence, the orientation of these
buses as well as buffers on them can be determined also using
P
and
s
:
Arc mapping
:
s
T
P
T
D
e
=
(20)
where
is the number of first-in-first-out buffers required on each local bus, and
e
is the orientation of the local bus within the PE index space.
τ
