next up previous
Next: 3 A proof that Up: On-line Algorithms for Path Previous: 1.5 Our approach

2 The multi-Benes and multibutterfly networks


Our nonblocking network is constructed from a Benes network in much the same way that a multibutterfly network [37] is constructed from a butterfly network. We start by describing the butterfly, Benes, and multibutterfly networks.

An N-input butterfly has tex2html_wrap_inline1317 levels, each with N-nodes. An example is shown in Figure 2.1. The Benes network is a tex2html_wrap_inline1321 -level network consisting of back-to-back butterflies. The network in Figure 2.2 is a Benes network. Although Benes networks are usually drawn with the long diagonal edges at the first and last levels rather than in the middle (see e.g., [16, Figure 3-27,]), the networks are isomorphic.

Figure 2.1: An 8-input butterfly network.

Figure 2.2: An 8-input Benes network.

A multibutterfly is formed by gluing together butterflies in a somewhat unusual way. In particular, given 2 N-input butterflies tex2html_wrap_inline1331 and tex2html_wrap_inline1333 and a collection of permutations tex2html_wrap_inline1335 where tex2html_wrap_inline1337 , a 2-butterfly is formed by merging the node in row tex2html_wrap_inline1341 of level l of tex2html_wrap_inline1345 with the node in row tex2html_wrap_inline1347 of level l of tex2html_wrap_inline1351 for all tex2html_wrap_inline1353 , all tex2html_wrap_inline1355 , and all tex2html_wrap_inline1357 . The result is an N-input tex2html_wrap_inline1361 -level graph in which each node has 4 inputs and 4 outputs. Of the 4 output edges at a node, two are up outputs and two are down outputs (with one up edge and one down edge coming from each butterfly). For example, see Figure 2.3. Multibutterflies (i.e., d-butterflies) are composed from d butterflies in a similar fashion using d-1 sets of permutations, tex2html_wrap_inline1375 , where tex2html_wrap_inline1377 , resulting in a tex2html_wrap_inline1379 -level network with tex2html_wrap_inline1381 nodes.

Figure 2.3: An 8-input 2-butterfly network.

In a butterfly or multibutterfly, for each output v there is a distinct logical (up-down) path from the inputs to v. In order to reach v from any input u, the path from u to v must take an up-edge from level l to level l+1 if the lth bit in the row number of v is 0, and a down-edge if the bit is 1. (The bits are counted starting with the most significant, which is in position 0). Figure 2.4 shows the logical path from any input to output 011. Let us use the term physical path to denote our usual notion of a path through the network, i.e., a physical path consists of a sequence of nodes tex2html_wrap_inline1411 such that node tex2html_wrap_inline1413 resides on level i of the network, and nodes tex2html_wrap_inline1417 and tex2html_wrap_inline1419 are connected by an edge, for tex2html_wrap_inline1421 . In a butterfly network, the logical path can be realized by only one physical path through the network. In a multibutterfly, however, each step of the logical path can be taken on any one of d edges. Hence, for any logical path there are many physical paths through the network.

Figure 2.4: The logical up-down path from an input to output 011.

The notion of up and down edges can be formalized in terms of splitters. More precisely, the edges from level l to level l+1 in rows tex2html_wrap_inline1429 to tex2html_wrap_inline1431 in a multibutterfly form a splitter for all tex2html_wrap_inline1433 and tex2html_wrap_inline1435 . Each of the tex2html_wrap_inline1437 splitters starting at level l has tex2html_wrap_inline1441 inputs tex2html_wrap_inline1443 and outputs. The outputs on level l+1 are naturally divided into tex2html_wrap_inline1447 up outputs and tex2html_wrap_inline1449 down outputs. By definition, all splitters on the same level l are isomorphic, and each input is connected to d up outputs and d down outputs according to the butterfly and the permutations tex2html_wrap_inline1457 and tex2html_wrap_inline1459 .

The most important characteristic of a multibutterfly is the set of permutations tex2html_wrap_inline1461 , tex2html_wrap_inline1463 , tex2html_wrap_inline1465 that prescribe the way in which the component butterflies are to be merged. For example, if all the permutations are the identity map, then the result is the dilated butterfly (i.e., a butterfly with d copies of each edge). We are most interested in multibutterflies that have expansion properties. In particular, we say that an M-input splitter has expansion property tex2html_wrap_inline1471 if every set of tex2html_wrap_inline1473 inputs is connected to at least tex2html_wrap_inline1475 up outputs and tex2html_wrap_inline1477 down outputs for tex2html_wrap_inline1479 . Similarly, we say that a multibutterfly has expansion property tex2html_wrap_inline1481 if each of its component splitters has expansion property tex2html_wrap_inline1483 . For example, see Figure 2.5.

Figure 2.5: A splitter with expansion property tex2html_wrap_inline1485 .

Although the constants tex2html_wrap_inline1487 , tex2html_wrap_inline1489 , and d do not appear in the expressions for the running times of our algorithms, e.g., tex2html_wrap_inline1493 , as a practical matter they are crucial. In general, the larger tex2html_wrap_inline1495 is, the fewer bit steps an algorithm will require. However, since tex2html_wrap_inline1497 , a network with large tex2html_wrap_inline1499 must also have large d, and in practice it may be difficult to build a node that can receive and transmit along all d of its edges simultaneously if d is large. Furthermore, most of the algorithms require tex2html_wrap_inline1507 , which (as far as we know) can only be achieved for small tex2html_wrap_inline1509 . As we shall see, the fraction of network nodes that are actually used by paths is at most tex2html_wrap_inline1511 , so if tex2html_wrap_inline1513 is small, the network is not fully utilized.

If the permutations tex2html_wrap_inline1515 are chosen randomly, then with non-zero probability, the resulting d-butterfly has expansion property tex2html_wrap_inline1519 for any tex2html_wrap_inline1521 , and tex2html_wrap_inline1523 for which tex2html_wrap_inline1525 and


This bound appears as Corollary 2.1 in [37]. A derivation can be found in [18]. Roughly speaking, the bound says that the expansion, tex2html_wrap_inline1527 , can be almost as large as d-1, provided that tex2html_wrap_inline1531 is small enough. Furthermore, for any tex2html_wrap_inline1533 , tex2html_wrap_inline1535 can be made arbitrarily close to tex2html_wrap_inline1537 , by making d large. It is not known if tex2html_wrap_inline1541 can be made close to both d-1 and tex2html_wrap_inline1545 simultaneously. Constructions for splitters and multibutterflies with good expansion properties are known although the expansion properties are generally not as good as those obtained from randomly-generated graphs.

Like a multibutterfly, a multi-Benes network is formed from Benes networks by merging them together. A 2-multi-Benes network is shown in Figure 2.6. An N-input multi-Benes network has tex2html_wrap_inline1551 levels labeled tex2html_wrap_inline1553 through tex2html_wrap_inline1555 . Levels 0 through tex2html_wrap_inline1559 form a multibutterfly, while levels tex2html_wrap_inline1561 through 0 form the mirror image of a multibutterfly.

Figure 2.6: An 8-input 2-multi-Benes network.

As in the multibutterfly, the edges in levels 0 through tex2html_wrap_inline1571 are partitioned into splitters. Between levels tex2html_wrap_inline1573 and 0, however, the edges are partitioned into mergers. More precisely, the edges from level l to level l+1 in rows tex2html_wrap_inline1581 to tex2html_wrap_inline1583 form a merger for all tex2html_wrap_inline1585 and tex2html_wrap_inline1587 . Each of the tex2html_wrap_inline1589 mergers starting at level l has tex2html_wrap_inline1593 inputs and outputs. The inputs on level l are naturally divided into tex2html_wrap_inline1597 up inputs and tex2html_wrap_inline1599 down inputs. All mergers on the same level l are isomorphic, and each input is connected to 2d outputs. There is a single, trivial, logical path from any input of a multi-Benes network through the mergers on levels tex2html_wrap_inline1605 through -1 to the single splitter on level 0. (Any physical path will do.) From level 0 there is a single logical up-down path through the splitters to any output on level tex2html_wrap_inline1613 . In both cases, the logical path can be realized by many physical paths.

We say that an M-output merger has expansion property tex2html_wrap_inline1617 if every set of tex2html_wrap_inline1619 inputs (up or down or any combination) is connected to at least tex2html_wrap_inline1621 outputs, tex2html_wrap_inline1623 . With nonzero probability, a random set of permutations yields a merger with expansion property tex2html_wrap_inline1625 for any tex2html_wrap_inline1627 , and tex2html_wrap_inline1629 for which tex2html_wrap_inline1631 and


This inequality can be derived by making a small number of substitutions in the derivation of Inequality 2.1 found in [18]. We say that a multi-Benes network has expansion property tex2html_wrap_inline1633 if each of its component mergers and splitters has expansion property tex2html_wrap_inline1635 . The multibutterflies and multi-Benes networks considered throughout this paper are assumed to have expansion property tex2html_wrap_inline1637 .

It is worth noting that all the results in this paper hold for a broader class of networks than multibutterflies and multi-Benes networks. In particular, each basic butterfly component used to make a multibutterfly or multi-Benes network can be replaced by any Delta network. A Delta network is a regular network formed by splitters like the butterfly, but for which the individual connections within each splitter can be arbitrary [14].

next up previous
Next: 3 A proof that Up: On-line Algorithms for Path Previous: 1.5 Our approach

Bruce Maggs
Mon Jul 22 21:19:59 EDT 1996