Butterfly network


A butterfly network is a technique to link multiple computers into a high-speed network. This form of multistage interconnection network topology can be used to connect different nodes in a multiprocessor system. The interconnect network for a shared memory multiprocessor system must have low latency and high bandwidth unlike other network systems, like local area networks or internet for three reasons:
The major components of an interconnect network are:
These multistage networks have lower cost than a cross bar, but obtain lower contention than a bus. The ratio of switching nodes to processor nodes is greater than one in a butterfly network. Such topology, where the ratio of switching nodes to processor nodes is greater than one, is called an indirect topology.
The network derives its name from connections between nodes in two adjacent ranks, which resembles a butterfly. Merging top and bottom ranks into a single rank, creates a Wrapped Butterfly Network. In figure 1, if rank 3 nodes are connected back to respective rank 0 nodes, then it becomes a wrapped butterfly network.
BBN Butterfly, a massive parallel computer built by Bolt, Beranek and Newman in the 1980s, used a butterfly interconnect network. Later in 1990, Cray Research's machine Cray C90, used a butterfly network to communicate between its 16 processors and 1024 memory banks.

Butterfly network building

For a butterfly network with p processor nodes, there need to be p switching nodes. Figure 1 shows a network with 8 processor nodes, which implies 32 switching nodes. It represents each node as N. For example, the node at column 6 in rank 1 is represented as and node at column 2 in rank 0 is represented as.
For any 'i' greater than zero, a switching node N gets connected to N and N, where, m is inverted bit on ith location of j. For example, consider the node N: i equals 1 and j equals 6, therefore m is obtained by inverting the ith bit of 6.
VariableBinary representationDecimal Representation
j1106
m0102

As a result, the nodes connected to N are :
Thus, N, N, N, N form a butterfly pattern. Several butterfly patterns exist in the figure and therefore, this network is called a Butterfly Network.

Butterfly network routing

In a wrapped butterfly network, a message is sent from processor 5 to processor 2. In figure 2, this is shown by replicating the processor nodes below rank 3. The packet transmitted over the link follows the form:
The header contains the destination of the message, which is processor 2. The payload is the message, M and trailer contains checksum. Therefore, the actual message transmitted from processor 5 is:
Upon reaching a switching node, one of the two output links is selected based on the most significant bit of the destination address. If that bit is zero, the left link is selected. If that bit is one, the right link is selected. Subsequently, this bit is removed from the destination address in the packet transmitted through the selected link. This is shown in figure 2.
Several parameters help evaluate a network topology. The prominent ones relevant in designing large-scale multi-processor systems are summarized below and an explanation of how they are calculated for a butterfly network with 8 processor nodes as shown in figure 1 is provided.
This section compares the butterfly network with linear array, ring, 2-D mesh and hypercube networks. Note that linear array can be considered as a 1-D mesh topology. Relevant parameters are compiled in the table.
TopologyDiameterBisection BandwidthLinksDegree
Linear arrayp-11p-12
Ringp/22p2
2-D mesh224
Hypercubelog2p/2log2 × log2
Butterflylog2p/2log2 × 2p4

Advantages

The difference between hypercube and butterfly lies within their implementation. Butterfly network has a symmetric structure where all processor nodes between two ranks are equidistant to each other, whereas hypercube is more suitable for a multi-processor system which demands unequal distances between its nodes. By looking at the number of links required, it may appear that hypercube is cheaper and simpler compared to a butterfly network, but as the number of processor nodes go beyond 16, the router cost and complexity of butterfly network becomes lower than hypercube because its degree is independent of the number of nodes.
In conclusion, no single network topology is best for all scenarios. The decision is made based on factors like the number of processor nodes in the system, bandwidth-latency requirements, cost and scalability.