Hubbry Logo
Butterfly networkButterfly networkMain
Open search
Butterfly network
Community hub
Butterfly network
logo
7 pages, 0 posts
0 subscribers
Be the first to start a discussion here.
Be the first to start a discussion here.
Butterfly network
Butterfly network
Butterfly network
View on Wikipedia
from Wikipedia

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.

Technical requirements

[edit]

The interconnect network for a shared memory multiprocessor system must have low latency and high bandwidth unlike other network systems, like local area networks (LANs) or internet[citation needed] for three reasons:

  • Messages are relatively short as most messages are coherence protocol requests and responses without data.
  • Messages are generated frequently because each read-miss or write-miss generates messages to every node in the system to ensure coherence. Read/write misses occur when the requested data is not in the processor's cache and must be fetched either from memory or from another processor's cache.
  • Messages are generated frequently, therefore rendering it difficult for the processors to hide the communication delay.

Components

[edit]

The major components of an interconnect network are:[citation needed]

Figure 1: Butterfly Network for 8 processors
  • Processor nodes, which consist of one or more processors along with their caches, memories and communication assist.
  • Switching nodes (Router), which connect communication assist of different processor nodes in a system. In multistage topologies, higher level switching nodes connect to lower level switching nodes as shown in figure 1, where switching nodes in rank 0 connect to processor nodes directly while switching nodes in rank 1 connect to switching nodes in rank 0.
  • Links, which are physical wires between two switching nodes. They can be uni-directional or bi-directional.

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

The network derives its name from connections between nodes in two adjacent ranks (as shown in figure 1), which resembles a butterfly. Merging top and bottom ranks into a single rank, creates a Wrapped Butterfly Network.[1] 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.[2] Later in 1990, Cray Research's machine Cray C90, used a butterfly network to communicate between its 16 processors and 1024 memory banks.[3]

Butterfly network building

[edit]

For a butterfly network with p processor nodes, there need to be p(log2 p + 1) switching nodes. Figure 1 shows a network with 8 processor nodes, which implies 32 switching nodes. It represents each node as N(rank, column number). For example, the node at column 6 in rank 1 is represented as (1,6) and node at column 2 in rank 0 is represented as (0,2).[1]

For any 'i' greater than zero, a switching node N(i,j) gets connected to N(i-1, j) and N(i-1, m), where, m is inverted bit on ith location of j. For example, consider the node N(1,6): i equals 1 and j equals 6, therefore m is obtained by inverting the ith bit of 6.

Variable Binary representation Decimal Representation
j 110 6
m 010 2

As a result, the nodes connected to N(1,6) are :

N(i,j) N(i-1,j) N(i-1,m)
(1,6) (0,6) (0,2)

Thus, N(0,6), N(1,6), N(0,2), N(1,2) form a butterfly pattern. Several butterfly patterns exist in the figure and therefore, this network is called a Butterfly Network.

Butterfly network routing

[edit]
Figure 2: Butterfly Network Routing

In a wrapped butterfly network (which means rank 0 gets merged with rank 3), a message is sent from processor 5 to processor 2.[1] In figure 2, this is shown by replicating the processor nodes below rank 3. The packet transmitted over the link follows the form:

Header Payload Trailer

The header contains the destination of the message, which is processor 2 (010 in binary). The payload is the message, M and trailer contains checksum. Therefore, the actual message transmitted from processor 5 is:

010 M checksum

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.

  • The above packet reaches N(0,5). From the header of the packet it removes the leftmost bit to decide the direction. Since it is a zero, left link of N(0,5) (which connects to N(1,1)) gets selected. The new header is '10'.
  • The new packet reaches N(1,1). From the header of the packet it removes the leftmost bit to decide the direction. Since it is a one, right link of N(1,1) (which connects to N(2,3)) gets selected. The new header is '0'.
  • The new packet reaches N(2,3). From the header of the packet it removes the leftmost bit to decide the direction. Since it is a zero, left link of N(2,3) (which connects to N(3,2)) gets selected. The header field is empty.
  • Processor 2 receives the packet, which now contains only the payload 'M' and the checksum.

Butterfly network parameters

[edit]

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.[citation needed]

  • Bisection Bandwidth: The maximum bandwidth required to sustain communication between all nodes in the network. This can be interpreted as the minimum number of links that need to be severed to split the system into two equal portions. For example, the 8 node butterfly network can be split into two by cutting 4 links that crisscross across the middle. Thus bisection bandwidth of this particular system is 4. It is a representative measure of the bandwidth bottleneck which restricts overall communication.
  • Diameter: The worst case latency (between two nodes) possible in the system. It can be calculated in terms of network hops, which is the number of links a message must travel in order to reach the destination node. In the 8 node butterfly network, it appears that N(0,0) and N(3,7) are farthest away, but upon inspection, it is apparent that due to the symmetric nature of the network, traversing from any rank 0 node to any rank 3 node requires only 3 hops. Therefore, the diameter of this system is 3.
  • Links: Total number of links required to construct the entire network structure. This is an indicator of overall cost and complexity of implementation. The example network shown in figure 1 requires a total of 48 links (16 links each between rank 0 and 1, rank 1 and 2, rank 2 and 3).
  • Degree: The complexity of each router in the network. This is equal to the number of in/out links connected to each switching node. The butterfly network switching nodes have 2 input links and 2 output links, hence it is a 4-degree network.

Comparison with other network topologies

[edit]

This section compares the butterfly network with linear array, ring, 2-D mesh and hypercube networks.[4] Linear array can be considered as a 1-D mesh topology. Relevant parameters are compiled in the table[citation needed] (‘p’ represents the number of processor nodes).

Network parameters
Topology Diameter Bisection Bandwidth Links Degree
Linear array ⁠⁠ 1 ⁠⁠ 2
Ring ⁠⁠ 2 p 2
2-D mesh 2(√p - 1) √p 2√p(√p - 1) 4
Hypercube log2(p) ⁠⁠ log2(p) × (p/2) log2(p)
Butterfly log2(p) ⁠⁠ , h = number of nodes in a single layer log2(p) × 2p 4

Advantages

[edit]
  • Butterfly networks have lower diameter than other topologies like a linear array, ring and 2-D mesh. This implies that in butterfly network, a message sent from one processor would reach its destination in a lower number of network hops.
  • Butterfly networks have higher bisection bandwidth than other topologies. This implies that in butterfly network, a higher number of links need to be broken in order to prevent global communication.
  • It has a bigger computer range.

Disadvantages

[edit]
  • Butterfly networks are more complex and costlier than other topologies due to the higher number of links required to sustain the network.

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 (represented by degree) 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.

See also

[edit]

References

[edit]
Revisions and contributorsEdit on WikipediaRead on Wikipedia

Butterfly network

View on Grokipedia
from Grokipedia
A butterfly network is a multistage interconnection commonly used in to connect multiple processors or processing elements efficiently, characterized by its resemblance to butterfly wings when diagrammed and featuring a logarithmic number of stages for between nodes. In a typical k-ary n-fly butterfly network, there are n stages of radix-k switches, connecting N = k^n terminals, with each switch having 2k ports (k inputs and k outputs) and wiring that permutes address digits between stages to enable . Key properties of the butterfly network include a of n (O(log_k N) between any pair of nodes), providing low-latency communication, and a single unique minimal path between each pair of terminals, which supports deterministic but limits path diversity. Under uniform traffic patterns, it achieves balanced channel loads, making it suitable for applications like fast Fourier transforms (FFT) and bit-reversal permutations, though it can suffer congestion and reduced throughput with non-uniform or adversarial traffic due to potential link saturation. Advantages include high (scaling with N) and simplicity in , while disadvantages encompass high wiring complexity and vulnerability to hotspots without adaptive enhancements. Originating in the as a technique for efficient data routing in computing systems, the gained prominence through implementations like the BBN Butterfly parallel processor in the 1980s, which used the topology for massively parallel processing with processors and access. Modern variants, such as the flattened butterfly introduced by researchers including William Dally at Stanford, address limitations by reducing stages and increasing for better scalability in supercomputers and on-chip networks, offering up to 50% higher throughput and lower power consumption compared to topologies. These networks continue to influence designs, including those in data centers and multicore processors, due to their cost-efficiency and performance under balanced loads.

Fundamentals

Definition and Purpose

The butterfly network is a multistage network (MIN) used in to connect N inputs to N outputs through log₂ N stages of switching elements. Each stage consists of N/2 basic switches, arranged such that the overall connectivity pattern visually resembles the wings of a butterfly due to the symmetric fanning of links between levels. This topology provides a unique path of length log₂ N between any input-output pair, enabling deterministic with low depth. The primary purpose of the butterfly network is to facilitate efficient communication in multiprocessor systems, particularly for all-to-all data exchange patterns required in parallel algorithms. It excels in supporting permutation routing, where any arbitrary mapping of inputs to outputs can be realized simultaneously without internal conflicts, making it suitable for applications like fast Fourier transforms (FFT) and sorting operations that rely on structured data dependencies and collective communications. At its core, the butterfly network employs a regular, fixed interconnection scheme across stages, often visualized as a two-dimensional grid where horizontal lines represent stages and diagonal links denote switch connections—straight for one output and crossed for the other. This design ensures scalability and predictability, with each switch in stage i connecting to specific nodes in stages i-1 and i+1 based on bit positions in the input address. A representative example is an 8-input butterfly network (N=8, log₂ 8=3 stages), featuring 4 switches per stage. Inputs enter at stage 0 (e.g., labeled 000 to 111 in binary), connect via straight and cross links to stage 1 switches, which then route to stage 2, and finally to outputs at stage 3; for instance, input 000 might follow a straight path through all stages to output 000, while input 001 crosses in stage 1 to reach output 100, demonstrating the ports and interconnections that support full permutations.

Historical Development

The butterfly network topology originated in the late 1960s and 1970s amid growing interest in multistage networks (MINs) for efficient parallel processing and switching. Foundational concepts drew from permutation networks, including the perfect shuffle permutation proposed by Harold Stone in 1971, which enabled data redistribution across processors in a single stage and laid groundwork for more complex topologies. Earlier, V. E. Beneš introduced rearrangeable non-blocking networks in 1964, providing a theoretical basis for scalable switching fabrics that minimized crosspoint requirements while supporting arbitrary permutations. Complementing these, D. H. Lawrie described the omega network in 1975 as a self-routing MIN derived from Beneš structures, emphasizing fixed permutations for cost-effective in array processors. The butterfly network's distinctive structure also reflected influences from signal processing and sorting algorithms. The "butterfly" nomenclature and diagram echoed the computational graphs in the Cooley-Tukey (FFT) algorithm, published in 1965, where pairwise operations formed butterfly-like motifs for efficient polynomial evaluation. Similarly, Batcher's 1968 odd-even mergesort network utilized comparator stages resembling butterfly connections to achieve parallel sorting with logarithmic depth, inspiring interconnection designs for permutation-heavy tasks in parallel computers. A pivotal practical advancement occurred in the late 1970s when Bolt, Beranek and Newman (BBN) adapted butterfly switching—rooted in perfect shuffles and omega networks—for multiprocessor systems, initially building on their 1972 Pluribus switches. BBN's design efforts began in 1978, culminating in the first Butterfly parallel processor delivery in 1981, featuring up to 256 processors interconnected via a multistage butterfly fabric for shared-memory emulation. This system marked a key milestone in deploying MINs commercially, with the Butterfly series evolving through the ; the enhanced Butterfly 1000 series was announced in 1987, incorporating improved processors and software for broader adoption in scientific computing. From these theoretical MIN foundations, the butterfly topology transitioned to diverse implementations, including emulations on field-programmable gate arrays (FPGAs) for prototyping and acceleration in the and beyond. For instance, multi-FPGA setups have realized scalable 64-node butterfly networks compliant with standards like OCP-IP, enabling on-chip testing of parallel algorithms.

Architecture

Core Components

The core components of a butterfly network consist primarily of switching elements, nodes arranged in stages, and interconnecting links that facilitate routing in systems. The fundamental switching elements are 2x2 crossbar switches, which operate at each stage to control permutations by selectively connecting to outputs in either a straight (upper to upper, lower to lower) or (upper to lower, lower to upper) configuration. These switches enable basic rerouting decisions, allowing the network to rearrange paths dynamically. Each switch handles two and two outputs, forming the building block for scalable interconnection. The node arrangement in a butterfly network supports N = 2^k inputs and outputs, organized across k stages, with each stage containing N/2 such 2x2 switches. Inputs connect to the first stage of switches, and outputs emanate from the final stage, creating a multi-level that resembles the when visualized. For example, in an network (k=3), there are 3 stages, each with 4 switches, totaling 12 switches that interconnect the 8 input nodes to 8 output nodes. This radix-2 structure ensures a balanced distribution of computational load across stages. Links between consecutive stages employ permutation-based connections, specifically a perfect shuffle pattern, where outputs from one stage are redistributed to inputs of the next by interleaving indices. The perfect shuffle permutes the N outputs of one stage to the N inputs of the next stage, for example, by connecting the output with index i to the input with index obtained by left-rotating the binary representation of i by one bit (modulo adjustment for power of 2), ensuring each output links to exactly one input. This shuffling promotes even traffic distribution and supports efficient path diversity. Variants of the butterfly network include the baseline configuration, which uses linear indexing for connections without wrapping, and the wrapped-around (or circular shift) version, where the shuffle incorporates modular arithmetic to connect the ends, potentially reducing path lengths in cyclic applications. The logical layout of a butterfly network illustrates its radix-2 structure through a series of horizontal stages, with vertical and diagonal links forming non-blocking paths from any input to any output via a unique route, akin to edges in a projection. This design allows the components to collectively enable permutation routing, as explored in subsequent operational analyses.

Network Construction

The butterfly network is constructed as a multistage interconnection network using a series of switching stages connected via specific permutation patterns. It begins with an input stage consisting of N processor nodes, where N is a power of 2, typically N = 2^k for some integer k. Each subsequent stage is formed by applying a perfect shuffle permutation to the outputs of the previous stage, linking them to 2x2 crossbar switches that enable either straight-through or crossover connections. This process repeats for log₂ N stages, culminating in an output stage mirroring the input, resulting in a total of log₂ N + 1 levels or ranks. For larger networks, the construction follows a recursive approach. A butterfly network of order k (with 2^k nodes per rank) is built by combining two networks of order k-1: one for the lower half and one for the upper half, shifted by 2^{k-1}. The input rank of the full network connects to the first stage of both subnetworks via straight and shuffled links, while the outputs merge similarly. This recursive method allows scalable assembly, where each level adds a new dimension of connectivity without redesigning the base topology. Wiring patterns are designed to minimize crossovers, often employing multilayer VLSI layouts with L routing layers (L ≥ 2) to separate horizontal and vertical tracks, achieving area complexity O(N log N) and bounded wire lengths. For instance, odd layers handle vertical connections, and even layers manage horizontal ones, reducing interference in dense chip integrations. A concrete example is the construction of a 16-node butterfly network (k=4, 5 ranks with 16 nodes each). The input nodes are labeled in binary from 0000 to 1111 and connect pairwise to the 8 switches in stage 1 (e.g., inputs 0000 and 0001 to switch 0, 0010 and 0011 to switch 1). Outputs from stage 1 are then permuted via perfect shuffle to inputs of stage 2 switches, such as by left-rotating the binary labels by one bit. Subsequent shuffles propagate similarly through the stages, yielding full connectivity through four switching stages. Nodes are addressed using binary labels of the form [i, j], where i denotes the rank (0 to k) and j is the k-bit binary position within the rank (0 to 2^k - 1). Connections between [i, j] and [i+1, m] follow the rule: straight link to m = j, and shuffle link to m = (j + 2^{k-i-1}) mod 2^k, ensuring systematic wiring.

Operation

Routing Algorithms

The butterfly network possesses a self-routing property, in which the destination bits directly guide path selection at each switch without requiring centralized control or tables. This property enables packets to navigate autonomously through the network stages, leveraging the binary labeling of nodes and links. The core routing algorithm operates as follows: for a destination address d=dk−1…d0d = d_{k-1} \dots d_0 (where k=log⁡2Nk = \log_2 N and NN is the network size), at stage ii (with stages numbered from 0 to k−1k-1), the switch examines bit did_i to select the output port—typically 0 for the straight (upper) path and 1 for the cross (lower) path—before stripping that bit and forwarding the remaining address to the next stage. This deterministic process ensures a unique shortest path of length kk from source to destination. In the presence of contention, where multiple packets compete for the same output port, conflict resolution strategies include randomized (e.g., routing packets via a randomly chosen intermediate destination to balance load) or priority-based (using fixed priorities or nonpredictive selection to resolve bids without inspecting full destinations). These methods, combined with bounded queuing at switches, prevent indefinite blocking while maintaining . The self-routing mechanism supports any of inputs to outputs in O(log⁡N)O(\log N) depth, as each packet follows an independent path determined by its destination tag; this includes the bit-reversal essential for efficient (FFT) implementations, where data reordering aligns with the network's butterfly computation structure. For basic unicast routing, the algorithm can be expressed in pseudocode as follows:

function route_packet(source, destination): current_address = destination # Binary representation: d_{k-1} ... d_0 current_node = source for i from 0 to k-1: bit = extract_bit(current_address, i) # d_i if bit == 0: next_node = upper_neighbor(current_node, stage=i) else: next_node = lower_neighbor(current_node, stage=i) forward_packet_to(next_node, remaining_address) # Strip d_i current_node = next_node deliver_to(destination)

function route_packet(source, destination): current_address = destination # Binary representation: d_{k-1} ... d_0 current_node = source for i from 0 to k-1: bit = extract_bit(current_address, i) # d_i if bit == 0: next_node = upper_neighbor(current_node, stage=i) else: next_node = lower_neighbor(current_node, stage=i) forward_packet_to(next_node, remaining_address) # Strip d_i current_node = next_node deliver_to(destination)

This assumes a source-oblivious , where path choices depend solely on the destination and current .

Key Parameters

The , as a multistage connecting N=2kN = 2^k inputs to NN outputs, exhibits several key parameters that determine its structural efficiency and performance bounds. The represents the longest shortest path between any pair of nodes, measured in hops, and is equal to log⁡2N\log_2 N, corresponding to the number of stages traversed in the worst case. This low enables low-latency communication for distant nodes, with the maximum path length strictly k=log⁡2Nk = \log_2 N stages. The degree of each switch in the network is 4, consisting of two input ports and two output ports in the standard 2x2 configuration. This fixed degree balances connectivity and hardware simplicity, as intermediate switches connect bidirectionally across stages. The , defined as the minimum number of links crossing a balanced partition of the network into two equal-sized sets of N/2N/2 nodes each, is N/2N/2. This arises from the balanced cuts between consecutive stages, where exactly N/2N/2 channels span the midpoint, providing linear scalability in aggregate capacity. In terms of , the network requires O(Nlog⁡N)O(N \log N) switches and overall, with log⁡2N\log_2 N stages each containing N/2N/2 switches and NN per stage. This quadratic-logarithmic scaling reflects the total hardware investment for full connectivity. The path length between source and destination is precisely the number of stages k=log⁡2Nk = \log_2 N, as routing follows a unique deterministic path through the topology. Regarding scalability limits, the butterfly network demonstrates sensitivity to faults in individual stages, where a single switch or link can partition the network and disrupt connectivity for N node pairs due to the unique-path . This necessitates additional , such as extra stages, for enhanced in practical deployments.

Analysis and Applications

Performance Metrics

The butterfly network exhibits an average latency of O(log⁡N)O(\log N) under uniform traffic loads, leveraging its logarithmic diameter for efficient in permutations and balanced workloads. However, hotspots arising from uneven traffic distribution can lead to worst-case contention, escalating latency to O(N)O(N) in adversarial scenarios where multiple packets converge on the same link or switch. Historical throughput benchmarks for the BBN Butterfly multiprocessor, a seminal implementation from the , demonstrated scaling to higher aggregate rates in multi-node configurations. Modern emulations of butterfly topologies on GPUs have extended these capabilities, achieving significantly higher throughput in parallel graph algorithms; for instance, multi-GPU implementations of butterfly-based (BFS) traversals report over 10x speedup compared to CPU baselines for large-scale network analysis. In applications, the butterfly network's structure aligns naturally with the Cooley-Tukey FFT algorithm, enabling efficient mapping of butterfly operations for O(Nlog⁡N)O(N \log N) computation of discrete Fourier transforms in parallel environments. Similarly, for parallel sorting, the network supports implementations of the and parallel prefix computations, facilitating deterministic O(log⁡N)O(\log N) depth sorting with constant . Fault tolerance in butterfly networks stems from redundancy in variants like multibutterfly or extra-stage designs, which provide multiple disjoint paths between nodes, enhancing reliability in multistage interconnection setups. Simulation studies highlight the network's efficiency for random permutations under light to moderate loads, but dropping in adversarial traffic patterns that induce congestion. Post-2000 research has revitalized butterfly topologies in optical networks and network-on-chip (NoC) designs, where flattened or Clos-based variants demonstrate reduced power consumption and latency in photonic interconnects for chip-scale .

Comparisons with Other Topologies

The butterfly network shares a diameter of log⁡2N\log_2 N with the network, facilitating efficient short-path in both. Unlike the , which requires a node degree of log⁡2N\log_2 N that grows with system size, the butterfly maintains a constant degree of 4, reducing wiring and improving for large-scale implementations. The 's direct interconnection among processors enables symmetric, reconfigurable , whereas the butterfly's indirect multistage relies on fixed switch stages for connectivity. Both the and networks are multistage interconnection networks (MINs) with a of log⁡2N\log_2 N and bisection width of N/2N/2. The network is inherently blocking, supporting only N!/2N!/2 without path conflicts due to its self-routing shuffle-exchange pattern. In contrast, the is rearrangeably non-blocking, allowing any to be realized by reconfiguring switch settings, thus providing superior support for arbitrary communication patterns. Relative to 2D mesh and torus topologies, the butterfly offers substantially lower latency with its log⁡2N\log_2 N diameter compared to the O(N)O(\sqrt{N})
Add your contribution
Related Hubs
User Avatar
No comments yet.