Information Technology Reference
In-Depth Information
Figure
7.10
shows a 2D mesh for matrix multiplication. Each cell of this mesh adds to
its stored value the product of the value arriving from above and to its left. These two values
pass through the cells to those below and to their right, respectively. When the entries of
A
are
supplied on the left and those of
B
are supplied from above in the order shown, the cell
C
i
,
j
computes
c
i
,
j
,the
(
i
,
j
)
entry of the product matrix
C
. For example, cell
C
2,3
accumulates the
value
c
2,3
=
a
2,1
∗
b
3,3
. After the entries of
C
have been computed,
they are produced as outputs by shifting the entries of the mesh to one side of the array. When
generalized to
n
b
1,3
+
a
2,2
∗
b
2,3
+
a
2,3
∗
×
n
matrices, this systolic array requires 2
n
−
1 steps for the last of the matrix
components to enter the array, and another
n
1 steps to compute the last entry
c
n
,
n
.An
additional
n
steps are needed to shift the components of the product matrix out of the array.
Thus, this systolic array performs matrix multiplication in 4
n
−
−
2steps.
We put the following requirements on every systolic array (of any dimension) that com-
putes the matrix multiplication function: a) each component of each matrix enters the array
at one location, and b) each component of the product matrix is computed at a unique cell.
We now show that the systolic matrix multiplication algorithm is optimal to within a constant
multiplicative factor.
THEOREM
7.5.3
Two
n×n
matrices can be multiplied by an
n×n
systolic array in
4
n−
2
steps
and every two-dimensional systolic array for this problem requires at least
(
n/
2
)
−
1
steps.
Proof
The proof that two
n
2stepsbyatwo-
dimensional systolic array was given above. We now show that
Ω(
n
)
steps are required to
multiply two
n
×
n
matrices can be multiplied in 4
n
−
B
.Observethat
the number of cells in a two-dimensional array that are within
d
moves from any particular
cell is at most
σ
(
d
)
,where
σ
(
d
)=
2
d
2
+
2
d
+
1. The maximum occurs at the center of the
array. (See Problem
7.11
.)
×
n
matrices,
A
and
B
,toproducethematrix
C
=
A
×
b
1,3
b
1,2
b
2,2
b
3,2
b
2,3
b
3,3
b
1,1
b
2,1
0
b
3,1
0
0
a
1,1
a
1,2
a
1,3
c
1,1
c
1,2
c
1,3
a
2,1
a
2,2
a
2,3
c
2,1
c
2,2
c
2,3
0
a
3,1
a
3,2
a
3,3
c
3,1
c
3,2
c
3,3
0
0
Figure 7.10
A two-dimensional mesh for the multiplication of two matrices. The entries in
these matrices are supplied in successive time intervals to processors on the boundary of the mesh.
Search WWH ::
Custom Search