A butterfly network in graph theory is a specific type of interconnection network that is widely used in parallel computing, algorithm design, and routing. It is a directed acyclic graph that exhibits a layered structure, often derived from or related to the hypercube graph.
What is a Butterfly Network (BF(n))?
A butterfly network of dimension n, denoted as BF(n), is a graph with a unique structure consisting of multiple levels and vertices per level. It is a popular choice for algorithms like the Fast Fourier Transform (FFT) and for building high-performance communication architectures due to its efficient routing properties.
Key Structural Characteristics of BF(n)
The structure of a butterfly network is defined by its dimension n:
- Vertices: A BF(n) network has a total of (n+1)2n vertices.
- Levels: The network is organized into n+1 distinct levels, indexed from 0 to n.
- Vertices per Level: Each of these levels contains exactly 2n vertices.
- Vertex Addressing: Each vertex in the network can be uniquely identified by a pair
(level, position), wherelevelis an integer from 0 to n, andpositionis an n-bit binary string representing its position within that level. For example, a vertex at(k, p)means it's on levelkwith binary addressp. - Edges: Edges connect vertices between adjacent levels. From a vertex
(k, p)on levelk(where0 <= k < n), there are two types of outgoing edges:- Straight Edge: To the vertex
(k+1, p)on levelk+1. - Cross Edge: To the vertex
(k+1, p')wherep'is obtained by flipping the k-th bit ofp.
- Straight Edge: To the vertex
Vertex Degrees and Eulerian Property
The degree of vertices in a butterfly network follows a specific pattern:
- Degree 2: Vertices on level 0 and level n each have a degree of 2. For level 0, these are outgoing edges. For level n, these are incoming edges.
- Degree 4: Every other vertex (i.e., those on levels
1throughn-1) has a degree of 4. This means they have two incoming edges and two outgoing edges.
An important property of the butterfly network BF(n) is that it is an Eulerian graph. This is because it is a connected graph where every vertex has an even degree (either 2 or 4, as described above). An Eulerian graph allows for an Eulerian circuit, which is a trail in the graph that visits every edge exactly once and starts and ends at the same vertex.
Summary Table: BF(n) Characteristics
| Characteristic | Description | Value for BF(n) |
|---|---|---|
| Total Vertices | Number of nodes in the network | (n+1) * 2^n |
| Total Levels | Number of layers of vertices | n+1 |
| Vertices/Level | Number of nodes at each level | 2^n |
| Vertex Degree | Nodes at level 0 and n have degree 2. Others have degree 4. | 2 (levels 0, n), 4 (levels 1 to n-1) |
| Connectivity | How nodes are linked | Highly connected, bipartite |
| Graph Type | Is it Eulerian? | Yes |
Applications of Butterfly Networks
Butterfly networks are fundamental in various areas:
- Parallel Computing: They serve as efficient interconnection networks for parallel processors, allowing fast and contention-free routing of data. Their ability to route messages between any input and output without collision makes them suitable for high-performance computing architectures.
- Algorithm Design: The structure of the butterfly network closely mirrors the data flow in many divide-and-conquer algorithms, particularly the Fast Fourier Transform (FFT).
- Switching Networks: They are used in designing communication switches and routers, providing scalable and robust solutions for data transfer.
- VLSI Design: Their regular and simple structure makes them amenable to efficient implementation in Very Large Scale Integration (VLSI) circuits.
For more information, you can explore resources like Wikipedia's page on Butterfly Networks.
