Information Technology Reference
In-Depth Information
The diameter of the CCC is at most 3
r/
2
+
d
, as we now show. Given two vertices
v
1
=(
p
,
a
d−
1
,
...
,
a
0
)
and
v
2
=(
q
,
b
d−
1
,
...
,
b
0
)
, let their hypercube addresses
a
=
(
a
d−
1
,
...
,
a
0
)
and
b
=(
b
d−
1
,
...
,
b
0
)
differ in
k
positions. To move from
v
1
to
v
2
,move
along the ring containing
v
1
by decreasing processor numbers until reaching the next lower
index at which
a
and
b
differ. (Wrap around to the highest index, if necessary.) Move from
this ring to the ring whose hypercube address differs in this index. Move around this ring until
arriving at the next lower indexed processor at which
a
and
b
differ. Continue in this fashion
until reaching the ring with hypercube address
b
. The number of edges traversed in this phase
of the movement is at most one for each vertex on the ring plus at most one for each of the
k
d
positions on which the addresses differ. Finally, move around the last ring toward the
vertex
v
2
along the shorter path. This requires at most
r/
2 edge traversals. Thus, the maximal
distance between two vertices, the diameter of the graph, is at most 3
r/
2
+
d
.
≤
7.7 Normal Algorithms
Normal algorithms
on hypercubes are systolic algorithms with the property that in each cycle
some bit position in an address is chosen and data is exchanged only between vertices whose
addresses differ in this position. An operation is then performed on this data in one or both
vertices. Thus, if the hypercube has three dimensions and the chosen dimension is the second,
the following pairs of vertices exchange data and perform operations on them:
(
0, 0, 0
)
and
(
0, 1, 0
)
,
(
0, 0, 1
)
and
(
0, 1, 1
)
,
(
1, 0, 0
)
and
(
1, 1, 0
)
,and
(
1, 0, 1
)
and
(
1, 1, 1
)
.A
fully nor-
mal algorithm
is a normal algorithm that visits each of the dimensions of the hypercube in
sequence. There are two kinds of fully normal algorithms,
ascending
and
descending algo-
rithms
; ascending algorithms visit the dimensions of the hypercube in ascending order, whereas
descending algorithms visit them in descending order. We show that many important algo-
rithms are fully normal algorithms or combinations of ascending and descending algorithms.
These algorithms can be efficiently translated into mesh-based algorithms, as we shall see.
The
fast Fourier transform
(FFT) (see Section
6.7.3
) is an ascending algorithm. As sug-
gested in the
butterfly graph
of Fig.
7.15
, if each vertex at each level in the FFT graph on
n
=
2
d
d
,then
at level
l
pairs of vertices are combined whose indices differ in their
l
th component. (See
Problem
7.14
.) It follows that the FFT graph can be computed in levels on the
d
-dimensional
hypercube by retaining the values corresponding to the column indexed by
a
in the hypercube
vertex whose index is
a
. It follows that the FFT graph has exactly the minimal connectiv-
ity required to execute an ascending fully normal algorithm. If the directions of all edges
are reversed, the graph is exactly that needed for a descending fully normal algorithm. (The
convolution function
f
(
n
,
m
)
inputs is indexed by a pair
(
l
,
a
)
,where
a
is a binary
d
-tuple and 0
≤
l
≤
:
R
n
+
m
R
n
+
m−
1
over a commutative ring
can also be
implemented as a normal algorithm in time
O
(log
n
)
on an
n
-vertex hypercube,
n
=
2
d
.See
Problem
7.15
.)
Similarly, because the graph of Batcher's bitonic merging algorithm (see Section
6.8.1
)is
the butterfly graph associated with the FFT, it too is a normal algorithm. Thus, two sorted lists
of length
n
=
2
d
can be merged in
d
=log
2
n
steps. As stated below, because the butterfly
graph on 2
d
inputs contains butterfly subgraphs on 2
k
inputs,
k<d
, a recursive normal
sorting algorithm
can be constructed that sorts on the hypercube in
O
(log
2
n
)
steps. The
reader is asked to prove the following theorem. (See Problem
6.29
.)
→
R
conv
Search WWH ::
Custom Search