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

mapping of the cells of the 2D mesh onto the cells of the linear array with n 2 cells. We assume
that each of the cells of the linear array is identical to a cell in the 2D mesh.
We now address the question of communication between cells. When mapped to the 1D
array, cells can communicate only with their two immediate neighbors in the array. However,
cells on the n

n mesh can communicate with as many as four neighbors. Unfortunately, cells
in one row of the 2D mesh that are neighbors of cells in an adjacent row are mapped to cells
that are as far as 2 n

×

−

1 cells away in the linear array. We show that with a factor of 8 n

−

2
slowdown, the linear array can simulate the 2D mesh. A slowdown by at least a factor of n/ 2
is necessary for those problems and data for which a datum moves from the first to the last
entry in the array (in n 2

−

1 steps) to simulate a movement that takes 2 n

−

1 steps on the

array. ( ( n 2

−

1 ) / ( 2 n

−

1 )

≥ n/ 2for n ≥

2.)
Given an algorithm for a 2D mesh, slow it down as follows:

a) Subdivide each cycle into six subcycles.

b) In the first of these subcycles let each cell compute using its local data.

c) In the second subcycle let each cell communicate with neighbor(s) in adjacent columns.

d) In the third subcycle let cells in even-numbered rows send messages to cells in the next
higher numbered rows.

e) In the fourth subcycle let cells in even-numbered rows receive messages from cells in the
next higher numbered rows.

f ) In the fifth subcycle let cells in odd-numbered rows send messages to cells in next higher
numbered rows.

g) In the sixth subcycle let cells in odd-numbered rows receive messages from cells in next
higher numbered rows.

When the revised 2D algorithm is executed on the linear array, computation occurs in the
first subcycle in unit time. During the second subcycle communication occurs in unit time
because cells that are column neighbors in the2Dmeshareadjacentinthe1Darray. The
remaining four subcycles involve communication between pairs of groups of n cells each. This
canbedoneforallpairsin2 n 1 time steps: each cell shifts a datum in the direction of the

cell for which it is destined. After 2 n

−

− 1 steps it arrives and can be processed. We summarize

this result below.

THEOREM 7.5.4 Any T -step systolic algorithm on an n × n array can be simulated on a linear
systolic array with n 2 cells in at most ( 8 n

−

2 ) T steps.

In the next section we demonstrate that hypercubes can be embedded into meshes. From
this result we derive mesh-based algorithms for a variety of problems from hypercube-based
algorithms for these problems.

7.6 Hypercube-Based Machines
A d -dimensional hypercube has 2 d vertices. When they are indexed by binary d -tuples ( a d ,
a d− 1 , ... , a 0 ) , adjacent vertices are those whose tuples differ in one position. Thus, the 2D