Digital Signal Processing Reference
In-Depth Information
The notion of computational wavefronts offers a very simple way to design
wavefront computing, which consists of three steps:
(1) Decompose an algorithm into an orderly sequence of recursions;
(2) Map the recursions onto corresponding computational wavefronts in the array;
(3) Pipeline the wavefronts successively through the processor array.
4.4
Example: Wavefront Processing for Matrix Multiplication
The notion of computational wavefronts may be better illustrated by an example of
the matrix multiplication algorithm where
A
,
B
,and
C
,areassumedtobe
N
×
N
matrices:
C
=
A
×
B
.
(26)
The topology of the matrix multiplication algorithm can be mapped naturally
onto the square, orthogonal
N
puting network serves as a (data) wave-propagating medium. To be precise, let us
examine the computational wavefront for the first recursion in matrix multiplication.
Suppose that the registers of all the PEs are initially set to zero, that is,
C
ij
(0)
×
0.
The elements of
A
are stored in the memory modules to the left (in columns) and
those of
B
in the memory modules on the top (in rows). The process starts with PE
(1, 1), which computes:
=
C
11
(
1
)=
C
11
(
0
)+
a
11
b
11
.
The computational activity then propagates to the neighboring PEs (1, 2) and (2,
I), which execute:
C
12
(
1
)=
C
12
(
0
)+
a
11
b
12
and
C
21
(
1
)=
C
21
(
0
)+
a
21
b
11
.
The next front of activity will be at PEs (3,1), (2,2), and (1,3), thus creating
a computation wavefront traveling down the processor array. This computational
wavefront is similar to optical wavefronts (they both obey Huygens' principle), since
each processor acts as a secondary source and is responsible for the propagation of
the wavefront. It may be noted that wave propagation implies localized data flow.
Once the wavefront sweeps through all the cells, the first recursion is over. As the
first wave propagates, we can execute an identical second recursion in parallel by
pipelining a second wavefront immediately after the first one. For example, the (1,
1) processor executes
(
)=
(
)+
=
+
.
C
11
2
C
11
1
a
12
b
21
a
11
b
11
a
12
b
21
