Parallel Computation - Models of Computation: Exploring the Power of Computing - page 297

Given a systolic array with inputs supplied externally over time (see Fig. 7.10 ), we enlarge
the array so that each component of each matrix is initially placed in a unique cell. The
enlarged array contains the original n

× n array.

Let C =[ c i , j ] .Because c i , j = u a i , u b u , j , it follows that for each value of i , j , t ,and
u there is a path from a i , u to the cell at which c i , j is computed as well as a path from b t , j to
this same cell. Thus, it follows that there is a path in the array between arbitrary entries a i , u
and b t , j of the matrices A =[ a i , u ] and B =[ b t , j ] .Let s be the maximum number of array
edges between an element of A or B and an element of C on which it depends. It follows
that at least s steps are needed to form C and that every element of A and B is within dis-
tance 2 s .Furthermore,eachofthe2 n 2 elements of A and B is located initially in a unique
cell of the expanded systolic array. Since there are at most σ ( 2 s ) vertices within a distance
of 2 s , it follows that σ ( 2 s )= 2 ( 2 s ) 2 + 2 ( 2 s )+ 1

≥

2 n 2 , from which we conclude that the

1

2 ( n 2

1

4 ) 1 / 2

1 n

number of steps to multiply n

× n matrices is at least s ≥ − −

4 ≥ 2 −

1.

7.5.4 Embedding of 1D Arrays in 2D Meshes
Given an algorithm for a linear array, we ask whether that algorithm can be efficiently realized
on a 2D mesh. This is easily determined: we need only specify a mapping of the cells of a linear
array to cells in the 2D mesh. Assuming that the two arrays have the same number of cells, a
natural mapping is obtained by giving the cells of an n

n mesh the snake-row ordering .(See
Fig. 7.11 .) In this ordering cells of the first row are ordered from left to right and numbered
from 0 to n

×

−

1; those in the second row are ordered from right to left and numbered from

n to 2 n −

1. This process repeats, alternating between ordering cells from left to right and
right to left and numbering the cells in succession. Ordering the cells of a linear array from
left to right and numbering them from 0 to n 2

−

1 allows us to map the linear array directly
to the 2D mesh. Any algorithm for the linear array runs in the same time on a 2D mesh if the
processors in the two cases are identical.
Now we ask if, given an algorithm for a 2D mesh, we can execute it on a linear array. The
answer is affirmative, although the execution time of the algorithmmay be much greater on the
1D array than on the 2D mesh. As a first step, we map vertices of the 2D mesh onto vertices
of the 1D array. The snake-row ordering of the cells of an n

× n array provides a convenient

0 1 2 3

7 6 5 4

8 9 10 11

15 14 13 12

Figure 7.11 Snake-row ordering of the vertices of a two-dimensional mesh.