3 Emulating the routing algorithm on the hypercube

 

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.

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 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.