Information Technology Reference
In-Depth Information
V
(
0
)
←
V
(
2
)
,
V
(
0
)
←
V
(
0
)+
V
(
2
)
,
V
(
4
)
←
V
(
6
)
,
V
(
4
)
←
V
(
4
)+
V
(
6
)
,
We continue in this fashion until reaching the lowest dimension of the
d
-tuples at which point
we have the following actions when
d
=
3:
V
(
0
)
←
V
(
4
)
,
V
(
0
)
←
V
(
0
)+
V
(
4
)
At the end of this computation,
V
(
0
)
is the sum of the values stored in all vertices. This
algorithm for computing
V
(
0
)
can be extended to any associative binary operator.
7.7.2 Broadcasting on the Hypercube
The broadcast operation is obtained by reversing the directions of each of the transmissions
described above. Thus, in the example,
V
(
0
)
is sent to
V
(
4
)
in the first stage, in the second
stage
V
(
0
)
and
V
(
4
)
are sent to
V
(
2
)
and
V
(
6
)
, respectively, and in the last stage,
V
(
0
)
,
V
(
2
)
,
V
(
4
)
,and
V
(
6
)
are sent to
V
(
1
)
,
V
(
3
)
,
V
(
5
)
,and
V
(
7
)
, respectively.
The algorithm given above to broadcast from one vertex to all others in a hypercube can be
modified to broadcast to just the vertices in a subhypercube that is defined by those addresses
a
=(
a
d−
1
,
a
d−
2
,
...
,
a
0
)
in which all bits are fixed except for those in some
k
positions.
For example,
are the vertices of a subhypercube of the
three-dimensional hypercube (the rightmost bit is fixed). To broadcast to each of these vertices
from
(
0, 1, 0
)
, say, on the first step send the message to its pair along the second dimension,
namely,
(
0, 0, 0
)
. On the second step, let these pairs send messages to their pairs along the
third dimension, namely,
(
0, 1, 0
)
{
(
0, 0, 0
)
,
(
0, 1, 0
)
,
(
1, 0, 0
)
,
(
1, 1, 0
)
}
→
→
(
1, 0, 0
)
. This algorithm can be
generalized to broadcast from any vertex in a hypercube to all other vertices in a subhypercube.
Values at all vertices of a subhypercube can be associatively combined in a similar fashion.
The performance of these normal algorithms is summarized below.
(
1, 1, 0
)
and
(
0, 0, 0
)
THEOREM
7.7.2
Broadcasting from one vertex in a
d
-dimensional hypercube to all other vertices
can be done with a normal algorithm in
O
(
d
)
steps. Similarly, the associative combination of the
values stored at the vertices of a
d
-dimensional hypercube can be done with a normal algorithm
in
O
(
d
)
steps. Broadcasting and associative combining can also be done on the vertices of
k
-
dimensional subcube of the
d
-dimensional hypercube in
O
(
k
)
steps with a normal algorithm.
7.7.3 Shifting on the Hypercube
Cyclic shifting can also be done on a hypercube as a normal algorithm. For
n
=
2
d
,consider
shifting the
n
-tuple
x
=(
x
n−
1
,
...
,
x
0
)
cyclically left by
k
places on a
d
-dimensional hyper-
cube. If
k
n/
2(seeFig.
7.16
(a)), the largest element in the right half of
x
,namely
x
n/
2
−
1
,
moves to the left half of
x
. On the other hand, if
k>n/
2(seeFig.
7.16
(b)),
x
n/
2
−
1
moves
to the right half of
x
.
Thus, to shift
x
left cyclically by
k
places,
k
≤
n/
2, divide
x
into two
(
n/
2
)
-tuples,
shift each of these tuples cyclically by
k
places, and then swap the rightmost
k
components
of the two halves, as suggested in Fig.
7.16
(a). The swap is done via edges across the highest
≤
Search WWH ::
Custom Search