Information Technology Reference
In-Depth Information
k
k
n/
2
n/
2
k
k
−
n/
2
k
k
−
n/
2
Figure 7.16
The two cases of a normal algorithm for cyclic shifting on a hypercube.
dimension of the hypercube. When
k>n/
2, cyclically shift each
(
n/
2
)
-tuple by
k
−
n/
2
positions and then swap the high-order
n
k
positions from each tuple across the highest
dimension of the hypercube. We have the following result.
−
THEOREM
7.7.3
Cyclic shifting of an
n
-tuple,
n
=
2
d
, by any amount can be done recursively by
a normal algorithm in
log
2
n
communication steps.
7.7.4 Shuffle and Unshuffle Permutations on Linear Arrays
Because many important algorithms are normal and hypercubes are expensive to realize, it
is preferable to realize normal algorithms on arrays. In this section we introduce the shuffle
and unshuffle permutations, show that they can be used to realize normal algorithms, and then
show that they can be realized on linear arrays. We use the unshuffle algorithms to map normal
hypercube algorithms onto one- and two-dimensional meshes.
Let
(
n
)=
and
n
=
2
d
.The
shuffle permutation
π
(
n
)
shue
{
0, 1, 2,
...
,
n
−
}
:
1
(
n
)
moves the item in position
a
to position
π
(
n
)
shue
(
a
)
,where
π
(
n
)
shue
(
a
)
is the
integer represented by the left cyclic shift of the
d
-bit binary number representing
a
.Forexam-
ple, when
n
=
8 the integer 3 is represented by the binary number 011 and its left cyclic shift
is 110. Thus,
π
(
8
)
(
n
)
→
shue
(
3
)=
6.Theshufflepermutationofthesequence
{
}
0, 1, 2, 3, 4, 5, 6, 7
{
}
is the sequence
. A shuffle operation is analogous to interleaving of the
two halves of a sorted deck of cards. Figure
7.17
shows this mapping for
n
=
8.
The
unshuffle permutation
π
(
n
)
0, 4, 1, 5, 2, 6, 3, 7
(
n
)
reverses the shuffle operation: it
moves the item in position
b
to position
a
where
b
=
π
(
n
)
unshue
:
(
n
)
→
shue
(
a
)
;thatis,
a
=
π
(
n
)
unshue
(
b
)=
π
unshue
(
π
shue
(
a
))
.Figure
7.18
showsthismappingfor
n
=
8.Theshufflepermutation
is obtained by reversing the directions of edges in this graph.
An unshuffle operation can be performed on an
n
-cell linear array,
n
=
2
d
, by assuming
that the cells contain the integers
from left to right represented as
d
-
bit binary integers and then sorting them by their least significant bit using a stable sorting
algorithm. (A
stable sorting algorithm
is one that does not change the original order of keys
{
0, 1, 2,
...
,
n
−
1
}
Search WWH ::
Custom Search