拓扑对集合通信性能的影响
不同网络拓扑（Ring/Torus/Fat-Tree/Hypercube）和链路方向性（单向/双向/半双工）系统性地影响各集合通信原语的性能。本文从拓扑维度横向对比这些影响，核心结论：拓扑的 Bisection Bandwidth 是 AllReduce/AllToAll 的全局带宽下界；分层异构拓扑中采用"高带宽层内多做、低带宽层少传"的分层策略可获得 5x 以上加速。
拓扑关键指标
| 指标 | 对集合通信的意义 |
|---|---|
| 节点度 $d$ | 决定节点的聚合带宽上限 $d\beta$ |
| 直径 $D$ | Broadcast/Reduce 的延迟下界 $D \cdot \alpha$ |
| Bisection Bandwidth $B_{\text{bis}}$ | AllReduce/AllToAll 的全局带宽下界 |
| 对称性 | 影响负载均衡，非对称拓扑中某些节点成为瓶颈 |
常见拓扑指标对比
| 拓扑 | 度 $d$ | 直径 $D$ | $B_{\text{bis}}$ | 对称性 | 成本 |
|---|---|---|---|---|---|
| Linear | 1-2 | $N-1$ | $\beta$ | 否 | 最低 |
| Ring | 2 | $\lfloor N/2\rfloor$ | $2\beta$ | 是 | 低 |
| Binary Tree | 1-3 | $2\log_2 N$ | $\beta$ | 否 | 低 |
| Fat-Tree ($k$-ary) | $k$ | $2\log_k N$ | $\sim N\beta/2$ | 层级 | 高 |
| Hypercube | $\log_2 N$ | $\log_2 N$ | $N\beta/2$ | 是 | 中高 |
| 2D Torus | 4 | $\sqrt{N}$ | $2\sqrt{N}\beta$ | 是 | 中 |
| 3D Torus | 6 | $\frac{3}{2}N^{1/3}$ | $2N^{2/3}\beta$ | 是 | 中 |
| Fully-Connected | $N-1$ | 1 | $N^2\beta/4$ | 是 | 极高 |
各拓扑上的 AllReduce 性能
AllReduce 是对拓扑最敏感的原语。
Ring（$N$ 节点）
直接使用 Ring AllReduce（ReduceScatter + AllGather 各 $N-1$ 步，每步 $M/N$）：
$$\begin{equation} T_{\text{Ring}} = 2(N-1)\alpha + \frac{2(N-1)}{N} \cdot \frac{M}{\beta} \label{eq:topo-ring-ar} \end{equation}$$- 优势：带宽利用率接近 100%，实现简单，所有节点对称
- 劣势：延迟 $O(N)$，$N$ 较大时延迟爆炸
- 适用规模：$N \le 8 \sim 16$
Hypercube（$N = 2^k$ 节点）
使用 Halving-Doubling 算法（每阶段 $\log_2 N$ 步，每步与 Hypercube 上的直接邻居通信）：
$$\begin{equation} T_{\text{Hypercube}} = 2\log_2 N \cdot \alpha + \frac{2(N-1)}{N} \cdot \frac{M}{\beta} \label{eq:topo-hypercube-ar} \end{equation}$$延迟降至 $O(\log N)$，带宽项与 Ring 相同（同为最优）。但节点度 $O(\log N)$ 增长使布线复杂。
2D Torus（$r \times c$，$N = rc$）
分层策略：先行内 Ring AllReduce（$r$ 个节点），再列内 Ring AllReduce（$c$ 个节点）。以正方形 $r = c = \sqrt{N}$ 为例，每一维的 Ring AllReduce 代价为 $2(\sqrt{N}-1)\alpha + \frac{2(\sqrt{N}-1)}{\sqrt{N}} \cdot \frac{M}{\beta}$，两维串行：
$$\begin{equation} T_{\text{2D-Torus}} \approx 4(\sqrt{N}-1)\alpha + 4\frac{(\sqrt{N}-1)}{\sqrt{N}} \cdot \frac{M}{\beta} \label{eq:topo-2dtorus-ar} \end{equation}$$与 Ring $\eqref{eq:topo-ring-ar}$ 对比，延迟从 $2(N-1)\alpha$ 降至 $4(\sqrt{N}-1)\alpha$，减少约 $\sqrt{N}/2$ 倍。$N=16$ 时：Ring 30 步 vs 2D-Torus 12 步。
Fat-Tree
$k$-ary Fat-Tree 的直径为 $2\log_k N$（从叶到根再到叶），使用树形 AllReduce 可在 $2\log_k N$ 步内完成。Full Bisection Bandwidth 保证带宽项也达到最优：
$$\begin{equation} T_{\text{Fat-Tree}} = 2\log_k N \cdot \alpha + \frac{2(N-1)}{N} \cdot \frac{M}{\beta} \label{eq:topo-fattree-ar} \end{equation}$$延迟和带宽都接近最优，但网络成本高（交换机数量为 $O(N \log N / k)$）。
性能对比（$N=16$，$M=1$ MB，$\alpha=1\mu s$，$\beta=64$ GB/s）
| 拓扑 | 算法 | 延迟项（$\mu s$） | 带宽项（$\mu s$） | 总时间（$\mu s$） |
|---|---|---|---|---|
| Ring | Ring AllReduce | 30 | 29.3 | 59.3 |
| Hypercube | Halving-Doubling | 8 | 29.3 | 37.3 |
| 2D Torus (4x4) | 分层 Ring | 12 | ~47 | ~59 |
| Fully-Connected | Direct | 4 | ~1 | ~5 |
链路方向性的影响
单向链路（Unidirectional）
数据只能沿一个方向传输。Ring AllReduce 无法利用双向链路的优化版本，延迟项无法减半。
双向链路（Full-Duplex）
大多数现代互联（NVLink、PCIe、InfiniBand）均为全双工。双向 Ring AllReduce 将 $N$ 个 chunk 分两半分别传播，步数减半：
$$\begin{equation} T_{\text{bidir-Ring}} \approx (N-1)\alpha + \frac{(N-1)}{N} \cdot \frac{M}{\beta} \label{eq:topo-bidir-ring-ar} \end{equation}$$各原语对链路方向性的敏感度
| 原语 | 算法 | 单向链路步数 | 双向链路步数 | 加速比 |
|---|---|---|---|---|
| Broadcast | 链式 | $N-1$ | $\lceil(N-1)/2\rceil$ | $\approx 2\times$ |
| Broadcast | 二叉树 | $\log_2 N$ | $\log_2 N$ | $1\times$ |
| AllGather | Ring | $N-1$ | $\lceil(N-1)/2\rceil$ | $\approx 2\times$ |
| AllReduce | Ring | $2(N-1)$ | $\approx N-1$ | $\approx 2\times$ |
| AllReduce | Halving-Doubling | $2\log_2 N$ | $2\log_2 N$ | $1\times$ |
| AllToAll | Pairwise | $N-1$ | $N-1$ | $1\times$ |
关键规律：
- Ring 类算法从双向链路获益最大（步数减半）
- Tree/Hypercube 类算法对链路方向性不敏感
- AllToAll Pairwise 每步已经双向交换数据，天然利用全双工
半双工的影响
半双工链路必须串行化收和发，Ring AllReduce 的每步时间翻倍：
$$\begin{equation} T_{\text{half-duplex-Ring}} = 2(N-1) \cdot 2 \cdot \left(\alpha + \frac{M/N}{\beta}\right) \label{eq:topo-halfduplex-ring} \end{equation}$$实际带宽利用率降至全双工的一半。现代高性能互联极少使用半双工。
多层级异构拓扑
现实系统的层级结构
| 层级 | 拓扑类型 | 带宽 | 延迟 |
|---|---|---|---|
| L2: Chip 内（多 Die） | D2D Ring/Mesh | 100~900 GB/s | 0.1~0.5 $\mu s$ |
| L3: Board 内（多 Chip） | NVLink Ring/FC | 64~900 GB/s | 0.5~2 $\mu s$ |
| L4: Rack 内（多 Board） | PCIe/NVLink/IB | 25~400 GB/s | 2~5 $\mu s$ |
| L5: Rack 间 | InfiniBand/Ethernet | 12.5~100 GB/s | 5~50 $\mu s$ |
带宽跨度 L2 到 L5 可达 10100 倍，延迟跨度 10500 倍。
分层集合通信策略
核心原则：在高带宽层级内完成尽可能多的工作，最小化跨低带宽层级的通信量。
分层 AllReduce（2 层）：设 $G$ 组，每组 $L$ 节点（$N = GL$），组内带宽 $\beta_{\text{intra}} \gg$ 组间带宽 $\beta_{\text{inter}}$：
- Intra-group ReduceScatter：组内数据量 $M$ → 每节点 $M/L$ 的部分结果
- Inter-group AllReduce：跨组数据量 $M/L$（关键：将跨组通信量减少 $L$ 倍）
- Intra-group AllGather：每组内恢复完整结果
数值对比
$G=4$，$L=8$，$N=32$，$M=100$ MB，$\beta_{\text{intra}}=450$ GB/s，$\beta_{\text{inter}}=25$ GB/s：
- 直接 Ring（$\beta_{\text{inter}}$ 是瓶颈）：$T_{\text{flat}} \approx 310 + 7750 = 8060 \mu s$
- 分层策略：$T_{\text{hierarchical}} = 403 + 780 + 403 = 1586 \mu s$
- 加速比 $\approx 5.1\times$
分层策略将跨组数据量从 $M$ 缩减到 $M/L = 12.5$ MB，跨组带宽时间从 7750 $\mu s$ 降至 750 $\mu s$。
SCCL 的拓扑策略
SCCL（SOPHGO）针对不同芯片数量使用不同拓扑：
| 芯片数 | 拓扑 | 算法 |
|---|---|---|
| 2 | 直连 | 直接交换 |
| 4 | Ring | Ring AllReduce |
| 8 | Ring | Ring AllReduce |
| 16 | 2D Torus | 分层 Ring |
16 芯的 2D Torus 由两个 8 芯 Ring 纵向互联构成，是分层策略的典型实例。
拓扑-算法匹配指南
| 拓扑 | 最佳 AllReduce | 最佳 AllToAll | 最佳 Broadcast |
|---|---|---|---|
| Ring | Ring AllReduce | Ring AllToAll | 双向链式 |
| Hypercube | Halving-Doubling | Bruck | Binomial Tree |
| 2D Torus | 分层 Ring | 分维 AllToAll | 分维 Broadcast |
| Fat-Tree | Tree AllReduce | Pairwise | Binomial Tree |
| Fully-Connected | Direct | Pairwise | Binomial Tree |
参考资料
- Dally & Towles, "Principles and Practices of Interconnection Networks"（Morgan Kaufmann, 2003）
- Patarasuk & Yuan, "Bandwidth Optimal All-reduce Algorithms"（JPDC, 2009）
- Jia et al., "Optimizing Network Topologies for Large-Scale Distributed Training"（NSDI, 2023）
- SCCL Documentation v1.0（SOPHGO）- Ring/2D Torus 拓扑实现
- Google TPU v4 Architecture（Google Cloud）