Information Technology Reference
In-Depth Information
1
2
3
4
5
2
1
4
3
5
2
4
1
5
3
4
2
5
1
3
4
5
2
3
1
5
4
3
2
1
Figure 7.9
A systolic implementation of bubble sort on a sequence of five items. Underlined
pairs of items are compared and swapped if out of order. The bottom row shows the first set of
comparisons.
If
r
is even, on the first phase of the algorithm this 1 does not move. However, on all
subsequent phases it moves right until it arrives at its final position. If
r
is odd, it moves
right on all phases until it arrives in its final position. Thus by the second step the rightmost
1 moves right on every step until it arrives at its final position. The second rightmost 1 is
free to move to the right without being blocked by the first 1 after the second phase. This
second 1 will move to the right by the third phase and continue to do so until it arrives at
its final position. In general, the
k
th rightmost 1 starts moving to the right by the
(
k
+
1
)
st
phase and continues until it arrives at its final position. It follows that at most
n
phases are
needed to sort the 0-1 sequence. By the zero-one principle, the same applies to all sequences.
To derive the lower bound, assume that the sorted elements are increasing from left to
right in the linear array. Let the elements initially be placed in decreasing order from left
to right. Thus, the process of sorting moves the largest element from the leftmost location
in the array to the rightmost. This requires at least
n
−
1steps. Thesamelowerbound
holds if some other permutation of the
n
elements is desired. For example, if the
k
th largest
element resides in the rightmost cell at the end of the computation, it can reside initially in
the leftmost cell, requiring at least
n
−
1operationstomovetoitsfinalposition.
7.5.3 Matrix Multiplication on a 2D Mesh
2D systolic arrays are natural structures on which to compute the product
C
=
A
×
B
of
matrices
A
and
B
. (Matrix multiplication is discussed in Section
6.3
.) Since
C
=
A
B
can
be realized as
n
matrix-vector multiplications,
C
can be computed with
n
linear arrays. (See
Fig.
7.7
.) If the columns of
B
are stored in successive arrays and the entries of
A
pass from
one array to the next in one unit of time, the
n
th array receives the last entry of
B
after 4
n
×
−
2
time steps. Thus, this 2D systolic array computes
C
=
A
1steps.Somewhat
more efficient 2D systolic arrays can be designed. We describe one of them below.
×
B
in 4
n
−
Search WWH ::
Custom Search