next up previous
Next: 4 Lower bounds on Up: Fast Algorithms for Bit-Serial Previous: 2.2 Routing in the

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 tex2html_wrap_inline1321 -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 tex2html_wrap_inline1323 .gif Although a packet may be delayed for tex2html_wrap_inline1325 -bit steps while traveling from one half to the next, the total time remains tex2html_wrap_inline1327 .

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 tex2html_wrap_inline1331 bits. More specifically, for every word w of length tex2html_wrap_inline1335 there exists a codeword, tex2html_wrap_inline1337 , of length tex2html_wrap_inline1339 such that every word of length tex2html_wrap_inline1341 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 tex2html_wrap_inline1345 . 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 tex2html_wrap_inline1353 dimensions. A node, v, is a star center if v is a codeword: tex2html_wrap_inline1359 . Define a star to be a star center and all of its neighbors. The node tex2html_wrap_inline1361 differs from tex2html_wrap_inline1363 in the ith bit and is called the ith arm of the tex2html_wrap_inline1369 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 tex2html_wrap_inline1375 . For simplicity suppose that the butterfly is 2n-k+1 by tex2html_wrap_inline1379 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 tex2html_wrap_inline1389 where tex2html_wrap_inline1391 consists of the most significant bits of the row in which the node resides, tex2html_wrap_inline1393 consists of the least significant bits, and tex2html_wrap_inline1395 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 tex2html_wrap_inline1403 . Our mapping of nodes in the sub-butterflies to nodes in the hypercube is defined as follows:


for tex2html_wrap_inline1407 . Map tex2html_wrap_inline1409 (as well as tex2html_wrap_inline1411 from above) to tex2html_wrap_inline1413 .

Note that since m is composed of n-k bits, tex2html_wrap_inline1419 is composed of n bits and hence the hypercube has dimension 2n. Let tex2html_wrap_inline1425 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 tex2html_wrap_inline1431 . In fact, tex2html_wrap_inline1433 is partitioned by the stars formed from the lth row of every sub-butterfly. Consider two rows of tex2html_wrap_inline1437 that differ by one bit, say l and tex2html_wrap_inline1441 . One gets mapped to the tex2html_wrap_inline1443 star in tex2html_wrap_inline1445 and the other to the tex2html_wrap_inline1447 star in tex2html_wrap_inline1449 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 tex2html_wrap_inline1457 and tex2html_wrap_inline1459 in the tex2html_wrap_inline1461 sub-butterfly for tex2html_wrap_inline1463 (we will handle tex2html_wrap_inline1465 separately). The first node of this edge is the i-1st arm of the tex2html_wrap_inline1469 star in tex2html_wrap_inline1471 and the endpoint is the ith arm of the tex2html_wrap_inline1475 star in tex2html_wrap_inline1477 . We need to distribute the n edges of the dilated edge in tex2html_wrap_inline1481 to the n edges between the arms of the tex2html_wrap_inline1485 stars in the two sub-cubes. Let tex2html_wrap_inline1487 denote the jth edge of the dilated edge between tex2html_wrap_inline1491 and tex2html_wrap_inline1493 in the butterfly. This edge is mapped to the following path in the hypercube. Starting at tex2html_wrap_inline1495 in tex2html_wrap_inline1497 we first go to tex2html_wrap_inline1499 via tex2html_wrap_inline1501 . Then we take the edge which takes us to tex2html_wrap_inline1503 in tex2html_wrap_inline1505 . Finally, we go to tex2html_wrap_inline1507 via tex2html_wrap_inline1509 in tex2html_wrap_inline1511 . More succinctly,


For the edge tex2html_wrap_inline1515 we make the obvious modification:


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


for tex2html_wrap_inline1529 . 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 tex2html_wrap_inline1537 where tex2html_wrap_inline1539 , tex2html_wrap_inline1541 or tex2html_wrap_inline1543 , tex2html_wrap_inline1545 and tex2html_wrap_inline1547 . 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 tex2html_wrap_inline1551 , or any of the four edges in a path for tex2html_wrap_inline1553 . 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 tex2html_wrap_inline1565 is mapped to hypercube node tex2html_wrap_inline1567 , where tex2html_wrap_inline1569 , tex2html_wrap_inline1571 , and tex2html_wrap_inline1573 . (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 tex2html_wrap_inline1593 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 tex2html_wrap_inline1611 congestion and dilation 2 for both the level n and level n+1 nodes using the paths




Since each of these star arms are distinct, the paths can be completed with tex2html_wrap_inline1623 congestion and tex2html_wrap_inline1625 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 tex2html_wrap_inline1637 , it takes tex2html_wrap_inline1639 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 tex2html_wrap_inline1645 -step delay experienced along the edges from level n to n+1 is additive.

next up previous
Next: 4 Lower bounds on Up: Fast Algorithms for Bit-Serial Previous: 2.2 Routing in the

Bruce Maggs
Mon Jul 22 17:37:10 EDT 1996