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