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 *l*th 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].

Mon Jul 22 21:19:59 EDT 1996