In this section we will show that an *N*-node hypercube can emulate
the routing algorithm performed by an *N*-node -dilated
butterfly with constant slowdown. Our strategy is to break the
butterfly into two halves and to embed each half in the hypercube with
constant load, congestion, and dilation. The halves are wired
together by a set of paths with constant congestion and dilation
. Although a
packet may be delayed for -bit steps while traveling from one
half to the next, the total time remains .

Our embedding will rely crucially on the notion of a star partition.
This in turn will rely on perfect *1*-error correcting codes which
were first constructed by Hamming [13] for words of
bits. More specifically, for every word *w* of length
there exists a codeword, , of length such that
every word of length is either a codeword or has Hamming
distance 1 from exactly one codeword.

A hypercube is a network where the number of nodes, *N*, is a power of
two, say . The exponent *s* is called the dimension of the
cube. Each node has an *s*-bit address and an undirected edge to each
of the *s* nodes whose address differs in one bit.

Suppose that we have a hypercube (or subcube) with
dimensions. A node, *v*, is a *star center* if *v* is a
codeword: . Define a *
star* to be a star center and all of its neighbors. The node
differs from in the *i*th bit and is called the *i*th
*arm* of the star. Since *c* is a perfect *1*-error
correcting code, every node in the hypercube is either a star center
or the neighbor of a star center (i.e., the arm of a star). That is,
the stars partition the nodes of the hypercube. An edge of a
hypercube is either between a star center and an arm or between arms
on different stars.

Let . For simplicity suppose that the butterfly is *2n-k+1*
by and that every dilated edge is actually composed of *n*
edges. We will embed this into a hypercube of dimension *2n*. Observe
that the hypercube has approximately twice as many nodes. As a first
step we will embed levels 0 to *n* of the butterfly. To do so we will
first give an embedding of the butterfly nodes in these levels and
then we will give a mapping of the butterfly edges.

A node in the first *n+1* levels of the
butterfly can be described by the pair
where consists of the most significant bits of the row in
which the node resides, consists of the least significant bits,
and is the level in which the node resides. Since any
path in the butterfly passes through nodes with the same value of
*m* in the first *n+1* levels, all nodes with the same value of
*m* will be considered as the sub-butterfly . Our
mapping of nodes in the sub-butterflies to nodes in the hypercube
is defined as follows:

for . Map (as well as from above) to .

Note that since *m* is composed of *n-k* bits, is composed of
*n* bits and hence the hypercube has dimension *2n*. Let be the
sub-cube where the least significant bits of all the nodes agree with
*l*. Note that all the nodes in row *l* of each sub-butterfly are mapped
to a star in . In fact, is partitioned by the stars formed
from the *l*th row of every sub-butterfly. Consider two rows of
that differ by one bit, say *l* and . One gets mapped to the
star in and the other to the star in
such that the corresponding arms of each star differ in the *i*th bit.
The map suggests that we can use the *i*th dimension of the hypercube
to route the *i*th dimension (level) of the butterfly.

Now we must show how to map butterfly edges to hypercube edges.
Consider the dilated edge between and in the
sub-butterfly for (we will handle separately). The first node of this edge is the *i-1*st arm
of the star in and the endpoint is the *i*th arm of the
star in . We need to distribute the *n* edges of the
dilated edge in to the *n* edges between the arms of the
stars in the two sub-cubes. Let denote the *j*th edge of the dilated edge between
and in the butterfly. This edge is
mapped to the following path in the hypercube. Starting at
in we first go to via .
Then we take the edge which takes us to in .
Finally, we go to via in . More
succinctly,

For the edge we make the obvious modification:

A straight edge in the butterfly, , , is mapped in a similar way except that
we don't need to change the *i*th bit of *l*:

for . Again we make the obvious modification
for *i=1*:

**Proof:**
From the construction, we know that butterfly edges are routed
only through edges that link arms of different stars. There are then
two cases to consider, depending on whether or not the stars are in
different subcubes.

*Case 1:* hypercube edges of the form

Such an edge must be the third hypercube edge used for a crossing butterfly edge. Moreover, the butterfly edge must be of the form where , or , and . Hence, this hypercube edge is used by at most two edges from the dilated butterfly.

*Case 2:* hypercube edges of the form

Such an edge can be the first, second, fourth, or fifth edge in a path
for , or any of the four
edges in a path for .
In each case, there are two possible choices for the values of *m*,
*l*, *i*, and *j*, depending on the direction in which the edge is
used. Hence, each such edge is used at most 16 times.

to .667emto .667em

The remaining levels of the dilated butterfly can be mapped to the
hypercube in an analogous fashion. In particular, we can map the last
*n+1* levels of the butterfly to the hypercube by using the same
algorithm as before, except that butterfly node is
mapped to hypercube node , where , , and .
(Note that we simply swapped the roles of the most and least
significant bits.) Butterfly edges are mapped in an analogous
fashion.

Unfortunately, the embedding process just described maps each node in
the middle *k+1* levels of the butterfly to two different places. We
will resolve this problem by using only the location prescribed by the
first embedding for nodes on levels *n-k* through *n*.

We are left with the problem of embedding the edges from level *n* to
level *n+1*, since the nodes on level *n* are located by the embedding
of the first *n+1* levels of the butterfly, and the nodes on level
*n+1* are located by the embedding of the last *n+1* levels of the
butterfly. We do not know how to embed these edges with constant
dilation, but we can embed them with constant congestion and dilation as follows. Recall that the nodes on level *n* of the
butterfly are mapped one-to-one to the *n*th arms of stars, while the
nodes of level *n+1* are mapped one-to-one to the *k+1*st arms of stars.
The path for the *j*th edge between level *n* and *n+1*
begins (ends) with a trip to (from) the *j*th arm of a
star. This can be done with congestion and dilation *2* for
both the level *n* and level *n+1* nodes using the paths

or

Since each of these star arms are distinct, the paths can be completed with congestion and dilation using Benes routing [6].

The hypercube can now easily emulate the butterfly routing algorithms
from Section 2. Each hypercube node emulates at most
*2* butterfly nodes. Also, since the first *n* levels of butterfly
edges are embedded with constant congestion and dilation, the
hypercube can emulate transmission along these edges with constant
slowdown. The same is true of the last *n-k-1* levels of butterfly
edges. Only the edges from level *n* to *n+1* cause problems. Since
these edges are embedded with dilation , it takes bit steps to emulate transmission along them. Fortunately, the
routing algorithms use the butterfly edges in order of increasing
dimension from *0* to *2n-k-1*, so the -step delay
experienced along the edges from level *n* to *n+1* is additive.

Mon Jul 22 17:37:10 EDT 1996