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 levels, each with N-nodes. An example is shown in Figure 2.1. The Benes network is a -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 and and a collection of permutations where , a 2-butterfly is formed by merging the node in row of level l of with the node in row of level l of for all , all , and all . The result is an N-input -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, , where , resulting in a -level network with 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 such that node resides on level i of the network, and nodes and are connected by an edge, for . 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 to in a multibutterfly form a splitter for all and . Each of the splitters starting at level l has inputs and outputs. The outputs on level l+1 are naturally divided into up outputs and 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 and .

The most important characteristic of a multibutterfly is the set of permutations , , 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 if every set of inputs is connected to at least up outputs and down outputs for . Similarly, we say that a multibutterfly has expansion property if each of its component splitters has expansion property . For example, see Figure 2.5.

Figure 2.5: A splitter with expansion property .

Although the constants , , and d do not appear in the expressions for the running times of our algorithms, e.g., , as a practical matter they are crucial. In general, the larger is, the fewer bit steps an algorithm will require. However, since , a network with large 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 , which (as far as we know) can only be achieved for small . As we shall see, the fraction of network nodes that are actually used by paths is at most , so if is small, the network is not fully utilized.

If the permutations are chosen randomly, then with non-zero probability, the resulting d-butterfly has expansion property for any , and for which 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, , can be almost as large as d-1, provided that is small enough. Furthermore, for any , can be made arbitrarily close to , by making d large. It is not known if can be made close to both d-1 and 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 levels labeled through . Levels 0 through form a multibutterfly, while levels 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 are partitioned into splitters. Between levels and 0, however, the edges are partitioned into mergers. More precisely, the edges from level l to level l+1 in rows to form a merger for all and . Each of the mergers starting at level l has inputs and outputs. The inputs on level l are naturally divided into up inputs and 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 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 . In both cases, the logical path can be realized by many physical paths.

We say that an M-output merger has expansion property if every set of inputs (up or down or any combination) is connected to at least outputs, . With nonzero probability, a random set of permutations yields a merger with expansion property for any , and for which 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 if each of its component mergers and splitters has expansion property . The multibutterflies and multi-Benes networks considered throughout this paper are assumed to have expansion property .

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