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

0 8 4 12 2 10 6 14 1 9 5 13 3 11 7 15

0 4 2 6 1 5 3 7 8 12 10 14 9 13 11 15

0 2 1 3 4 6 5 7 8 10 9 11 12 14 13 15

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

Figure 7.19 A normal ascending algorithm realized by shuffle operations on 2 k elements,
k = 2, 3, 4, ... , places into exchange locations elements whose indices differ by increasing powers
of two. Exchange locations are paired together.

positions places into exchange locations elements whose original indices differed by four, eight,
etc. The proof of correctness of this result is left to the reader. ( See Problem 7.17 .)
Since a shuffle on n = 2 d

elements can be done in 2 d− 1

−

1 steps on a linear array
with n cells (see Theorem 7.5.2 ), it follows that this fully normal ascending algorithm uses
T ( n )= φ ( d ) steps, where T ( 2 )= φ ( 1 )= 0and

1 )+ 2 d− 1 1 = 2 d

φ ( d )= φ ( d − − − d − 1

Do a fully normal descending algorithm by a shuffle followed by its steps in reverse order.

THEOREM 7.7.4 A fully normal ascending (descending) algorithm that runs in d =log 2 n steps
on a d -dimensional hypercube containing 2 d vertices can be realized on a linear array of n = 2 d
elements with T ( n )= n

− log 2 n − 1 (2T(n)) additional parallel steps.

From the discussion of Section 7.7 it follows that broadcasting, associative combining,
and the FFT algorithm can be executed on a linear array in O ( n ) steps because each can be
implemented as a normal algorithm on the n -vertex hypercube. Also, a list of n items can
be sorted on a linear array in O ( n ) steps by translating Batcher's sorting algorithm based on
bitonic merging, a normal sorting algorithm, to the linear array. (See Problem 7.20 .)

7.7.5 Fully Normal Algorithms on Two-Dimensional Arrays
We now consider the execution of a normal algorithm on a rectangular array. We assume
that the n = 2 2 d vertices of a 2 d -dimensional hypercube are mapped onto an m

m mesh,
m = 2 d , in row-major order. Since each cell is indexed by a pair consisting of row and column
indices, ( r , c ) , and each of these satisfies 0

×

1, they can each be
represented by a d -bit binary number. Let r and c be these binary numbers. Thus cell ( r , c )
is indexed by the 2 d -bit binary number rc .
Cells in positions ( r , c ) and ( r , c + 1 ) have associated binary numbers that agree in their
d most significant positions. Cells in positions ( r , c ) and ( r + 1, c ) have associated binary

≤ r ≤ m − 1and0 ≤ c ≤ m −