Networks derived from hypercubes form the architectural basis of most
parallel computers, including machines such as the BBN Butterfly, the
Connection Machine, the IBM RP3 and GF11, the Intel iPSC, and the NCUBE.
The butterfly, in particular, is quite popular, and has been
demonstrated to perform reasonably well in practice. An example of an
*8*-input butterfly is illustrated in Figure 1. The
nodes in this graph represent switches, and the edges represent wires.
Each node in the network has a distinct label , where *r* is
the row, and *l* is the level. In a butterfly with *N* inputs, the
row is a -bit binary number and the level is an integer between *0*
and . The nodes on level *0* and are called the *
inputs* and *outputs*, respectively. For , a node
labeled is connected to nodes and , where
denotes *r* with bit *l* complemented (bit *0* is the most
significant, bit the least).

The primary duty of the network in a parallel machine is to route
messages between its processors and/or memory modules. In a
butterfly, messages are typically sent from the switches on level *0*,
called the *inputs*, to those on level , called the *
outputs*. In a *one-to-one* routing problem, each input is the
origin of at most one message, and each output is the destination of a
most one message. One-to-one routing is also called *permutation
routing*. All of the algorithms discussed in this paper route
messages in a *store-and-forward* fashion. A store-and-forward
algorithm treats messages as indivisible objects. At each step, a
message can either remain at a switch or move in its entirety from one
switch to another across an edge, provided that no other messages use
the same edge at that step. Store-and-forward routing is also called
*packet switching*, and messages are often referred to as packets.
A related paper [2] extends the results of this paper for
a different method of routing called *circuit switching*.

One of the nice features of the butterfly is that there is a simple
algorithm for finding a path of length from any input to any
output. Upon reaching switch , , a packet with
destination compares *r* with *R*. If they are
equal, the packet takes the edge to . If not, it takes the
edge to . One problem with the butterfly is that this path
is unique. As a consequence, if some switch or edge along the unique
path from input *i* to output *j* (say) becomes congested or fails,
then communication between input *i* and output *j* will be disrupted.

**Figure 1:** An *8*-input butterfly network.

- 1.1 Dilated butterflies
- 1.2 Splitter networks
- 1.3 Randomly-wired splitter networks and multibutterflies
- 1.4 Our results
- 1.5 Related work
- 1.6 Outline

Mon Jul 22 18:45:42 EDT 1996