HyperX / Flattened Butterfly
将多级 Butterfly 压平为单级直连的高 radix 拓扑族及其统一构造框架
核心要点：
- Flattened Butterfly (Kim 2007) 把多级 Butterfly 压平为单级直连
- HyperX (Ahn 2009) 进一步推广为多维异形结构，每维交换机数 $S_i$ 可不同
- 维度内全互联，对角度数 $\sum (S_i - 1)$
- 直径 = $L$ （维度数），通常 2-3 跳，所有间接网络中最低
- 与 Fat-tree 等割集时交换机数少 8-28%
- 统一框架：Hypercube ($S_i=2$) / Full-mesh ($L=1$) / Dragonfly 组内都是 HyperX 特例
- 商用生态薄弱，AI 集群无已知纯 HyperX 部署
Butterfly 网络是什么？
$k$-ary $n$-fly: $n$ 级交换单元，每级 $k^{n-1}$ 个 $k \times k$ 交叉开关，路由 $k^n$ 个输入到 $k^n$ 个输出。
命名约定：
- $k$-ary：交换机端口数 ($k \times k$ 交叉开关)
- $n$-fly：交换机级数 （fly = butterfly 蝶形）
这个命名与 Torus 的 $k$-ary $n$-cube 平行：
| 记法 | $k$ 含义 | $n$ 含义 | 总规模 | 网络类型 |
|---|---|---|---|---|
| $k$-ary $n$-cube (Torus) | 每维节点数 | 维度数 | $k^n$ | 直连 |
| $k$-ary $n$-fly (Butterfly) | 交换机端口数 | 级数 | $k^n$ | 间接 （多级交换） |
@tbl-topo-hx-naming Butterfly vs Torus 命名
Butterfly 关键特性：
- 单射路由：每对输入-输出恰好 1 条路径，无路径多样性，链路故障/拥塞无替代
- 直径 = $n$ （级数），延迟低
- 与 Fat-tree 的区别：Fat-tree 在每级提供 $k/2$ 条等价路径，Butterfly 只有 1 条。Fat-tree 本质是"加宽的 Butterfly" — 用更多中间级换路径多样性
- 输入端 = 输出端：实际双向通信中，输入端 $i$ 和输出端 $i$ 是同一个终端节点的发送和接收方向
Butterfly 在现代不作为独立拓扑使用，衍生出 Flattened Butterfly （压平） 和 Butterfly 通信模式 （集合通信算法）。
Flattened Butterfly 怎么压平？
把同一数据通路上的 $n$ 个交换单元合并为 1 台物理交换机，级间链路变交换机直连[1]，见 @fig-topo-hx-evolution。
以 2-ary 3-fly 为例：
| 压平前 (2-ary 3-fly) | 压平后 (2-ary 3-flat) | |
|---|---|---|
| 交换单元总数 | 12 （3 级 × 4 个/级） | 4 台交换机 |
| 每台端口数 | 2 （2×2 交叉开关） | 5 （2 终端 + 3 网络） |
| 数据经过交换单元数 | 3 （每级 1 个） | 1-3 （直连 1 跳可达） |
| 路径多样性 | 1 条/对 | 1 条/对 （不变） |
@tbl-topo-hx-flatten Flattened Butterfly 压平对比
本质：用交换机端口数 (radix) 换级数减少。12 个 2-port → 4 个 5-port。
为什么现代系统能压平：现代交换机有 64-128 端口，端口"富余"，压平代价 （端口数增加） 完全可承受。
一般公式 ($k$-ary $n$-flat)：每台交换机在 $n$ 个维度上与其他 $k-1$ 个交换机全互联。
- 交换机总数：$k^{n-1}$
- 终端端口：$T = k$
- 网络端口：$(k-1) \times n$
- 交换机 radix: $R = k + (k-1) \cdot n$
- 直径：$n$ 跳
- 终端总数：$k^n$ （与原 Butterfly 相同）
HyperX 是怎么推广的？
允许每个维度的交换机数 $S_i$ 各不相同，构成 $L$ 维混合拓扑[2]。
- $L$ 个维度，第 $i$ 维有 $S_i$ 个交换机，同维度内全互联
- 交换机总数：$N_{sw} = \prod_{i=1}^{L} S_i$
- 网络度数：$\sum (S_i - 1)$
- 直径：$L$ 跳
- 终端总数：$N = N_{sw} \cdot T$ ($T$ = 每交换机终端数)
HyperX 作为统一框架，覆盖哪些拓扑？
Hypercube / Full-mesh / Flattened Butterfly / Dragonfly 组内都是特例 (@tbl-topo-hx-unify):
| 拓扑 | HyperX 参数 | 维度内连接 |
|---|---|---|
| Hypercube | $S_i = 2$，所有维度 | 每维 2 节点直连 |
| Flattened Butterfly | $S_i$ 全部相等 | 每维 $k$ 节点全互联 |
| Full-mesh | $L = 1$，单维度 | 所有节点全互联 |
| Dragonfly （组内） | 单维度对应组内 | 组内路由器全互联 |
@tbl-topo-hx-unify HyperX 统一框架
从 Hypercube 角度看：Hypercube 每维仅 2 节点，HyperX 把每维扩展到 $S_i$ 节点并全互联，用更高 radix 换更低直径和更高割集。
关键参数
核心问题：HyperX 的交换机数、终端数、radix、直径、链路数、割集带宽的关键公式和物理含义是什么？
| 属性 | 值 |
|---|---|
| 交换机总数 | $N_{sw} = \prod S_i$ |
| 终端总数 | $N = N_{sw} \cdot T$ |
| 交换机 radix | $R = T + \sum(S_i - 1)$ |
| 网络直径 | $L$ |
| 链路总数 | $N_{sw} \cdot \sum \frac{S_i - 1}{2}$ |
| 割集带宽 | 沿维 $i$ 切割：$\frac{N_{sw}}{S_i} \cdot \lfloor S_i/2 \rfloor \cdot \lceil S_i/2 \rceil \cdot b$ |
| Vertex-Transitive | Yes |
@tbl-topo-hx-params HyperX 关键参数
与 Fat-tree 经济性：Ahn et al. 报告在等割集带宽条件下，HyperX 交换机数比 Fat-tree 少 8-28%；等成本下割集带宽提升[2]。
HyperX 的核心优势是什么？
极低直径 + 割集可配置。
- 直径：$L$ 跳 （通常 2-3），远低于 Fat-tree ($2\log_r N$) 和 3D Torus ($\frac{3k}{2}$)。延迟敏感通信 （小消息 AllReduce、PP P2P） 受益
- 割集可配：通过调 $S_i$ 灵活配置不同方向带宽，优于 Torus （各维等宽） 和 Fat-tree （割集由交换机端口固定）
- 路由：支持 DOR (Dimension-Ordered)，按维度顺序逐维跳转，每维内直达，最多 $L$ 跳，天然无死锁。非均匀流量需 Valiant 或 UGAL 自适应路由
维度内全互联的代价是什么？
$O(S_i^2)$ 条链路/维度，$S_i$ 大时布线复杂度远高于 Torus。
这是 HyperX 对 radix 的核心需求 — 交换机端口数限制了可支持的维度数和每维规模。
适用场景与局限
核心问题：HyperX 适合和不适合哪些并行策略和部署场景？
适用：
- 高 radix 交换机可用 （64+ 端口使单级全互联可行）
- 延迟敏感工作负载 ($L = 2-3$ 跳最低)
- 割集带宽需可调 ($S_i$ 灵活配置)
- 中等规模 （数百-数千节点）
局限：
- 布线复杂度 $O(S_i^2)$/维，远高于 Torus
- 规模扩展受限于 radix
- 缺乏商用生态 （主流厂商无 HyperX 预配置）
- 容错性弱 （交换机故障影响该维全部通信）
- 非均匀流量依赖自适应路由 （UGAL 增加路径长度）
实际部署
核心问题：HyperX 在 HPC 和 AI 集群中有哪些实际部署？AI 集群为何没有纯 HyperX 部署？
HPC 有过部署，AI 集群尚无纯 HyperX 部署：
| 系统 | 拓扑 | 说明 |
|---|---|---|
| IBM PERCS (Power 775, 2011) | 2 级直连 | 组内全互联思想与 HyperX 同源 |
| Cray Aries (XC30/XC40) | Dragonfly | 组内全互联思想与 HyperX 同源 |
@tbl-topo-hx-deploy HyperX 实际部署
AI 集群未采用原因：
- 商用交换机 ASIC 未针对 HyperX 全互联优化
- Fat-tree 有成熟 ECMP/Clos 生态，HyperX 的 UGAL 需要定制固件
- AI 运维团队熟悉 Spine-Leaf，HyperX 部署和调试门槛高
Takeaway
| 知识点 | 核心结论 |
|---|---|
| Flattened Butterfly | 多级 Butterfly 压平为单级，用 radix 换级数 |
| HyperX | 推广为 $L$ 维异形，$S_i$ 可不同 |
| 直径 | $L$ 跳 （通常 2-3），间接网络最低 |
| 经济性 | 等割集下交换机数比 Fat-tree 少 8-28% |
| 统一框架 | Hypercube / Full-mesh / FBF / Dragonfly 组内均为特例 |
| 路由 | DOR 天然无死锁，非均匀流量需 UGAL |
| 部署现状 | HPC 有部分，AI 集群无纯 HyperX 部署 |
| 商用障碍 | ASIC 不优化 + 路由需定制固件 + 运维门槛高 |
参考资料
- Kim J. et al., Flattened Butterfly: A Cost-Efficient Topology for High-Radix Networks, ISCA 2007. https://doi.org/10.1145/1250662.1250679
- Ahn J. et al., HyperX: Topology, Routing, and Packaging of Efficient Large-Scale Networks, SC 2009. https://doi.org/10.1145/1654059.1654101