Information Technology Reference
In-Depth Information
3rd lsb
2nd lsb
1st lsb
100 011 001
Figure 7.15
The FFT butterfly graph with column numberings. The predecessors of vertices
at the
k
th level differ in their
k
th least significant bits.
111
110
101
010
000
THEOREM
7.7.1
There exists a normal sorting algorithm on the
p
-vertex hypercube,
p
=
2
d
,that
sorts
p
items in time
O
(log
2
p
)
.
Normal algorithms can also be used to perform a
sum on the hypercube
and
broadcast
on the hypercube
, as we show. We give an ascending algorithm for the first problem and a
descending algorithm for the second.
7.7.1 Summing on the Hypercube
Let the hypercube be
d
-dimensional and let
a
=(
a
d−
1
,
a
d−
2
,
...
,
a
0
)
denote an address of a
vertex. Associate with
a
the integer
=
a
d−
1
2
d−
1
+
a
d−
2
2
d−
2
+
|
a
|
···
+
a
0
.Thus,when
d
=
3, the addresses
{
0, 1, 2,
...
,7
}
{
(
0, 0, 0
)
,
(
0, 0, 1
)
,
are associated with the eight 3-tuples
(
0, 1, 0
)
,
...
,
(
1, 1, 1
)
}
, respectively.
1
)
tuple
(
a
d−
1
,
...
,
a
1
)
, send to vertex
(
a
d−
1
,
...
,
a
1
,0
)
the value stored at vertex
(
a
d−
1
,
...
,
a
1
,1
)
.
In the summing problem we store at vertex
(
a
d−
1
,
...
,
a
1
,0
)
the sum of the original values
stored at vertices
(
a
d−
1
,
...
,
a
1
,0
)
and
(
a
d−
1
,
...
,
a
1
,1
)
. Below we show the transmission
(e.g.
V
(
0
)
Let
V
(
|
a
|
)
denote the value stored at the vertex with address
a
.Foreach
(
d
−
←
V
(
1
)
) and addition (e.g.
V
(
0
)
←
V
(
0
)+
V
(
1
)
) that result for
d
=
3:
V
(
0
)
←
V
(
1
)
,
V
(
0
)
←
V
(
0
)+
V
(
1
)
V
(
2
)
←
V
(
3
)
,
V
(
2
)
←
V
(
2
)+
V
(
3
)
V
(
4
)
←
V
(
5
)
,
V
(
4
)
←
V
(
4
)+
V
(
5
)
V
(
6
)
←
V
(
7
)
,
V
(
6
)
←
V
(
6
)+
V
(
7
)
For each
(
d
2
)
tuple
(
a
d−
1
,
...
,
a
2
)
we then send to vertex
(
a
d−
1
,
...
,
a
2
,0,0
)
the value
stored at vertex
(
a
d−
1
,
...
,
a
2
,1,0
)
.Againfor
d
=
3, we have the following data transfers and
additions:
−
Search WWH ::
Custom Search