理论下界
延迟、带宽与 Bisection 三层约束如何共同决定集合通信算法选型
核心要点：
- 延迟下界 = max（信息传播步数，拓扑直径） × $\alpha$
- 带宽下界 = 必传字节量 / 有效并行带宽
- 总时间下界 = max（延迟下界，带宽下界），决定算法选型分区
- $k$-port 同时收紧两类下界，但拓扑直径仍受 $D$ 钳制
- Bisection 下界仅在 Ring / Torus 等低割集带宽拓扑上紧
通信延迟代数建模 ($\alpha\beta$ / LogP / LogGP) 见 06-通信性能建模，符号 / $k$-port 等名词见 4.1 总览 Glossary。
信息传播给出的延迟下界
核心问题：不考虑消息大小，完成一次全节点参与的集合操作至少需要多少步？
1-port 模型：$\lceil \log_2 N \rceil$ 步
信息以倍增方式扩散。1-port 下每步每节点至多 1 send + 1 recv，一份数据每步覆盖的节点数最多翻倍：
- 第 0 步：1 个节点持有
- 第 $t$ 步：至多 $2^t$ 个节点持有
要覆盖全部 $N$ 节点需 $2^t \ge N$，步数下界：
$$\begin{equation} t_{\min}^{\text{1-port}} = \lceil \log_2 N \rceil \label{eq:cc-bound-info-1port} \end{equation}$$对应延迟项：
$$\begin{equation} T_{\alpha}^{\min} = \lceil \log_2 N \rceil \cdot \alpha \label{eq:cc-bound-delay-1port} \end{equation}$$这是信息论下界 — 即使每步只传 1 bit，步数也不可能更少。
$k$-port 模型：$\lceil \log_{k+1} N \rceil$ 步
每节点同时向 $k$ 个新邻居发送，扩散基数变为 $k+1$。第 $t$ 步后至多 $(k+1)^t$ 节点持有数据：
$$\begin{equation} t_{\min}^{\text{k-port}} = \lceil \log_{k+1} N \rceil \label{eq:cc-bound-info-kport} \end{equation}$$ $$\begin{equation} T_{\alpha}^{\min, k\text{-port}} = \lceil \log_{k+1} N \rceil \cdot \alpha \label{eq:cc-bound-delay-kport} \end{equation}$$| $N$ | 1-port $\lceil \log_2 N \rceil$ | 2-port $\lceil \log_3 N \rceil$ | 步数减少 |
|---|---|---|---|
| 4 | 2 | 2 | 0% |
| 8 | 3 | 2 | 33% |
| 16 | 4 | 3 | 25% |
| 32 | 5 | 4 | 20% |
| 64 | 6 | 4 | 33% |
@tbl-cc-bound-info-prop 1-port vs 2-port 信息传播步数
典型硬件 $k$ 值：SG2260 CDMA + VSDMA → $k=2$; A100 6 路 NVLink → $k=6$; InfiniBand 多 QP → 接近 all-port。
拓扑直径给出的延迟下界
核心问题：信息传播下界假设任意两节点可直连。物理拓扑直径如何进一步钳制？
拓扑直径 $D$ 给出硬下界
最远两节点间至少要 $D$ 步通信，所以延迟下界附加约束 $T_\alpha \ge D \cdot \alpha$:
$$\begin{equation} T_{\alpha}^{\min} \ge D \cdot \alpha \label{eq:cc-bound-topo} \end{equation}$$Ring 拓扑直径 $D = \lfloor N / 2 \rfloor$。当 $N > 4$ 时 $\lfloor N / 2 \rfloor > \lceil \log_2 N \rceil$，拓扑约束反而比信息论下界更紧 — Ring 上 AllReduce 不可能达到 $\lceil \log_2 N \rceil \cdot \alpha$。
$k$-port 不改变拓扑直径
$k$-port 改变扩散基数，不缩短物理直径。2-port Ring 上每节点同时向两侧推进，$t$ 步覆盖 $2t + 1$ 节点，要 $2t + 1 \ge N$ 即 $t \ge (N-1)/2$:
$$\begin{equation} D_{\text{eff}}^{\text{2-port Ring}} = \lceil (N-1) / 2 \rceil \label{eq:cc-bound-2port-ring-diam} \end{equation}$$与 Chan et al. (2007) 的 $\lceil (N-1)/k \rceil$ 结果一致 (取 $k=2$)。
| $N$ | 1-port Ring 直径 $\lfloor N/2 \rfloor$ | 2-port Ring 有效直径 $\lceil (N-1)/2 \rceil$ |
|---|---|---|
| 4 | 2 | 2 |
| 8 | 4 | 4 |
| 16 | 8 | 8 |
| 32 | 16 | 16 |
@tbl-cc-bound-ring-diam Ring 拓扑直径对端口数不敏感
结论：偶数 $N$ 两列相等。2-port Ring 的优势不在缩短直径，而在双倍出口带宽 （见下节）。
带宽下界推导框架
核心问题：给定每节点必传字节量 $S$ / 必收字节量 $R$，在带宽 $\beta$ 下完成所需最少时间？
通用公式
设节点度 $d$ （物理直连数），有效并行端口 $p = \min(k, d)$。整个操作中每节点至少发 $S$ / 收 $R$ 字节，即使所有链路并行全速工作：
$$\begin{equation} T_{\beta}^{\min} = \max\left( \frac{S}{p \cdot \beta}, \frac{R}{p \cdot \beta} \right) \label{eq:cc-bound-bw-general} \end{equation}$$1-port 取 $p=1$; all-port Ring 取 $p=d=2$。
关键是推导每个原语的 $S$ 和 $R$。各原语完整推导见对应文档，这里只列结果。
1-port 下各原语带宽下界
| 原语 | 每节点发送 $S$ | 每节点接收 $R$ | 带宽下界 |
|---|---|---|---|
| Broadcast | $M$ (root) / 0 | $M$ （非 root） | $M / \beta$ |
| Scatter | $M$ (root) | $M / N$ | $M / \beta$ （root 端） |
| Reduce | $M$ （非 root） | $M$ (root) | $M / \beta$ |
| Gather | $M / N$ | $M$ (root) | $M / \beta$ （root 端） |
| ReduceScatter | $\frac{N-1}{N} M$ | $M / N$ | $\frac{(N-1) M}{N \beta}$ |
| AllGather | $M / N$ | $\frac{N-1}{N} M$ | $\frac{(N-1) M}{N \beta}$ |
| AllReduce (RS + AG) | $\frac{N-1}{N} M$ | $\frac{N-1}{N} M$ | $\frac{2 (N-1) M}{N \beta}$ |
| AllToAll （均匀） | $\frac{N-1}{N} M$ | $\frac{N-1}{N} M$ | $\frac{(N-1) M}{N \beta}$ |
| Dispatch / Combine （非均匀） | 按路由 | 按路由 | $\max_j R_j / \beta$ |
@tbl-cc-bound-bw-1port 1-port 模型下各原语带宽下界
2-port 下各原语带宽下界
2-port 把每节点出口带宽翻倍，带宽下界整体减半：
| 原语 | 带宽下界 (2-port) | 与 1-port 比 | Ring 实际步数 |
|---|---|---|---|
| ReduceScatter | $\frac{(N-1) M}{2 N \beta}$ | $\times 0.5$ | $\lceil N / 2 \rceil$ |
| AllGather | $\frac{(N-1) M}{2 N \beta}$ | $\times 0.5$ | $\lceil N / 2 \rceil$ |
| AllReduce (RS + AG) | $\frac{(N-1) M}{N \beta}$ | $\times 0.5$ | $N$ |
| AllToAll | $\frac{(N-1) M}{2 N \beta}$ | $\times 0.5$ | — |
@tbl-cc-bound-bw-2port 2-port 模型下各原语带宽下界
综合下界与算法选型
核心问题：延迟和带宽下界同时存在，实际时间由哪个主导？应选什么算法？
综合下界
任何算法时间同时受两类下界约束：
$$\begin{equation} T \ge \max( T_{\alpha}^{\min}, T_{\beta}^{\min} ) \label{eq:cc-bound-combined} \end{equation}$$1-port 下 AllReduce 综合下界：
$$\begin{equation} T \ge \max\left( \lceil \log_2 N \rceil \cdot \alpha, \quad \frac{(N-1) M}{N \beta} \right) \label{eq:cc-bound-allreduce-1port} \end{equation}$$$k$-port 下两项同步收紧：
$$\begin{equation} T \ge \max\left( \lceil \log_{k+1} N \rceil \cdot \alpha, \quad \frac{(N-1) M}{N \cdot \min(k, d) \cdot \beta} \right) \label{eq:cc-bound-allreduce-kport} \end{equation}$$两个运行区间决定算法选型
延迟主导区间 ($M$ 小): $T_\alpha > T_\beta$，选延迟最优算法 (步数少，如 Double Binary Tree 的 $O(\log N)$ 步)。
带宽主导区间 ($M$ 大): $T_\beta > T_\alpha$，选带宽最优算法 (链路利用率高，如 Ring 的 $\frac{2 (N-1)}{N} \to 2$ 系数)。
交叉点 (1-port):
$$\begin{equation} M^* = \frac{N \beta \cdot \lceil \log_2 N \rceil \cdot \alpha}{N - 1} \label{eq:cc-bound-crossover} \end{equation}$$消息大小在 $M^*$ 附近时两类算法性能接近，实际系统通常用阈值切换 （NCCL 在 ~1 MB 切 Tree / Ring）。
最优算法判据
核心问题：哪些算法同时达到延迟下界和带宽下界？
三种最优性
- 延迟最优：延迟项达 $\lceil \log_2 N \rceil \cdot \alpha$
- 带宽最优：带宽项达 $\frac{(N-1) M}{N \cdot d \beta}$ （相对拓扑）
- 同时最优：两个下界都达到。Recursive Halving-Doubling 在 $N = 2^k$ 时同时具有 $O(\log N)$ 延迟和 $\frac{2 (N-1)}{N}$ 带宽系数，是 AllReduce 的理论最优算法
1-port AllReduce 算法对照
| 算法 | 延迟项 | 达到延迟下界？ | 带宽系数 | 达到带宽下界？ |
|---|---|---|---|---|
| Ring | $2 (N-1) \alpha$ | 否 ($O(N)$) | $\frac{2 (N-1)}{N}$ | 是 |
| Double Binary Tree | $2 \log_2 N \cdot \alpha$ | 是 ($O(\log N)$) | $\log_2 N$ | 否 |
| Recursive Halving-Doubling | $2 \log_2 N \cdot \alpha$ | 是 | $\frac{2 (N-1)}{N}$ | 是 |
@tbl-cc-bound-1port-algo-cmp 1-port AllReduce 算法是否达到下界
2-port 下 Ring 优势扩大
| 算法 | 延迟项 | 带宽项 | 备注 |
|---|---|---|---|
| Ring (2-port) | $N \cdot \alpha$ | $M / \beta$ | 延迟减半，带宽最优 |
| Recursive Halving-Doubling | $2 \log_2 N \cdot \alpha$ | $\frac{(N-1) M}{N \beta}$ | 优势缩小，Ring 在中小 $N$ 已足够 |
@tbl-cc-bound-2port-algo-cmp 2-port AllReduce 算法对照
带宽最优的真实含义："带宽最优"衡量算法是否充分利用拓扑提供的带宽，而非绝对性能。全连接拓扑 （NVSwitch 域） 绝对性能更高是因为链路数多 $O(N)$ 倍，不是算法优势。等链路预算下 Ring 每链路效率更高。
Bisection 下界
核心问题：节点级带宽下界假设每节点链路独立，实际拓扑中多节点共享物理链路，如何收紧？
推导
将 $N$ 节点对半分组 $A / B$ (各 $N/2$)，跨组链路总带宽称为 $B_{\text{bisection}}$。AllReduce 中组 $A$ 每节点最终持有的 $M$ 字节都包含 $B$ 的贡献，因此组 $A$ 至少需从 $B$ 接收 $M / 2$ 字节有效信息，全部经 bisection 链路：
$$\begin{equation} T_{\text{bisection}} \ge \frac{M / 2}{B_{\text{bisection}}} \label{eq:cc-bound-bisection} \end{equation}$$不同拓扑的紧度对比
| 拓扑 | $B_{\text{bisection}}$ | Bisection 下界 | 节点级下界 | 谁更紧 |
|---|---|---|---|---|
| Ring | $2 \beta$ | $\frac{M}{4 \beta}$ | $\frac{(N-1) M}{N \beta} \to \frac{M}{\beta}$ | 节点级 |
| Fat-tree （满带宽） | $\frac{N}{2} \beta$ | $\frac{M}{N \beta}$ | $\frac{(N-1) M}{N \beta} \to \frac{M}{\beta}$ | 节点级 |
| Torus 2D ($\sqrt{N}$ 边) | $2 \sqrt{N} \beta$ | $\frac{M}{4 \sqrt{N} \beta}$ | $\frac{(N-1) M}{N \beta}$ | $N$ 大时 bisection 紧 |
@tbl-cc-bound-bisection-cmp Bisection 下界与节点级下界紧度对比
结论：Bisection 下界仅在低 bisection 带宽拓扑 （Torus / 多级 oversubscription） 紧，Fat-tree / 全连接拓扑里节点级下界更紧，Bisection 不起约束作用。
Takeaway
| 知识点 | 核心结论 |
|---|---|
| 延迟下界由谁决定 | max(信息传播 $\lceil \log_{k+1} N \rceil$，拓扑直径 $D$) × $\alpha$ |
| 带宽下界由谁决定 | 每节点必传字节量 / 有效并行带宽 $p \beta$ |
| 综合下界结构 | $T \ge \max(T_\alpha, T_\beta)$，两区间用消息大小区分 |
| $k$-port 的作用 | 同时收紧两类下界，但拓扑直径不变 |
| 算法选型逻辑 | 小 $M$ 选延迟最优 (Tree)，大 $M$ 选带宽最优 (Ring)，交叉点 $M^*$ 切换 |
| Halving-Doubling 的地位 | $N = 2^k$ 时同时最优，是 AllReduce 的理论上界 |
| Bisection 何时紧 | 仅低割集带宽拓扑 (Torus / oversubscription Fat-tree) |
@tbl-cc-bound-takeaway 理论下界要点
参考资料
- Chan et al., "Collective Communication: Theory, Practice, and Experience", CCPE 2007 — 理论下界综合分析
- Patarasuk & Yuan, "Bandwidth Optimal All-reduce Algorithms for Clusters of Workstations", JPDC 2009 — AllReduce 带宽最优性证明
- Thakur et al., "Optimization of Collective Communication Operations in MPICH", IJHPCA 2005 — 各算法最优性分析