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 ith bit and is called the ith
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 lth 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 ith bit.
The map suggests that we can use the ith dimension of the hypercube
to route the ith 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-1st arm
of the 
star in 
and the endpoint is the ith 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 jth 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 ith 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.
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 nth arms of stars, while the
nodes of level n+1 are mapped one-to-one to the k+1st arms of stars.
The path for the jth edge between level n and n+1
begins (ends) with a trip to (from) the jth 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.