集合通信理论下界
理论下界是任何算法都无法突破的性能极限，为评估算法优劣提供绝对标尺。本文从信息论和数据流量两个角度推导各集合通信原语的延迟下界和带宽下界。
通信延迟的数学建模方法（$\alpha$-$\beta$ 模型、LogP/LogGP、竞争修正等）详见 06-通信性能建模。符号约定见 00-总览。
延迟下界
延迟下界回答的问题是：不考虑消息大小（即使每步只传 1 bit），完成一次集合操作至少需要多少步？
信息传播约束
1-port 模型
考虑一个需要所有 $N$ 个节点参与的集合操作（如 AllReduce）。在 1-port 模型下（每步每个节点只能向一个邻居发送数据），信息传播速率如下：
- 第 0 步后：节点 0 的数据最多被 1 个节点知道（自己）
- 第 1 步后：最多被 2 个节点知道（节点 0 发给 1 个邻居）
- 第 2 步后：最多被 4 个节点知道（2 个已知节点各发给 1 个新邻居）
- 第 $t$ 步后：最多被 $2^t$ 个节点知道
要让所有 $N$ 个节点都获得节点 0 的信息，需要 $2^t \ge N$，即：
$$\begin{equation} t_{\min}^{\text{1-port}} = \lceil \log_2 N \rceil \label{eq:info-propagation-steps} \end{equation}$$这是信息论下界——即使每步传输量为 0 字节（只传递"是否存在"的信息），步数也不可能更少。因此：
$$\begin{equation} T_{\alpha}^{\min} = \lceil \log_2 N \rceil \cdot \alpha \label{eq:delay-lower-bound} \end{equation}$$k-port 模型
如果每个节点有 $k$ 个独立端口（独立 DMA 引擎），每步可以同时向 $k$ 个不同的邻居发送数据。此时信息传播更快：
- 第 $t$ 步后：最多 $(k+1)^t$ 个节点拥有数据（每个已知节点每步可以传给 $k$ 个新邻居，加上自己保持）
步数下界为：
$$\begin{equation} t_{\min}^{\text{k-port}} = \lceil \log_{k+1} N \rceil \label{eq:info-propagation-kport} \end{equation}$$延迟下界为：
$$\begin{equation} T_{\alpha}^{\min,\text{k-port}} = \lceil \log_{k+1} N \rceil \cdot \alpha \label{eq:delay-lower-bound-kport} \end{equation}$$具体数值对比（$k=1$ vs $k=2$）：
| $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% |
典型硬件的端口模型：SG2260 CDMA/VSDMA 双引擎 → $k=2$；NVLink A100 6 路独立链路 → $k=6$；InfiniBand 多 QP → 接近 all-port。
拓扑约束
1-port 模型
若网络拓扑的直径为 $D$（即最远两节点之间最短路径的跳数），那么从一个节点到另一个节点至少需要 $D$ 步传递信息。对于需要"所有节点都知道所有数据"的操作（如 AllReduce），最远的那对节点至少需要 $D$ 步通信：
$$\begin{equation} T_{\alpha}^{\min} \ge D \cdot \alpha \label{eq:topology-delay-bound} \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$ 的延迟——Ring 算法的 $(N-1)\alpha$ 延迟项虽然高于 $\lceil \log_2 N \rceil \cdot \alpha$，但实际上已被拓扑直径所限制。
k-port 模型下的拓扑约束
$k$-port 不改变拓扑的物理直径 $D$，但改变信息传播的有效覆盖速度。对于双向 Ring（$k=2$），信息从一个节点出发可以同时沿顺时针和逆时针传播，$t$ 步后覆盖的范围是两侧各 $t$ 跳，总覆盖 $2t+1$ 个节点。因此有效覆盖直径为：
$$\begin{equation} D_{\text{eff}}^{\text{2-port Ring}} = \lceil N/2 \rceil \cdot 1/2 = \lceil N/4 \rceil \label{eq:topology-delay-bound-2port} \end{equation}$$对比：
| $N$ | 1-port Ring 直径 $\lfloor N/2 \rfloor$ | 2-port Ring 有效直径 $\lceil N/4 \rceil$ |
|---|---|---|
| 4 | 2 | 1 |
| 8 | 4 | 2 |
| 16 | 8 | 4 |
| 32 | 16 | 8 |
带宽下界
术语说明："带宽下界"是"由带宽约束决定的时间下界"，不是"带宽本身的下界"。它回答的问题是：即使启动延迟 $\alpha = 0$（零开销启动），光是在有限带宽下搬完必需的数据，至少需要多长时间？与延迟下界一起构成总时间下界（见"综合下界"一节）。
推导框架
设 $N$ 个节点参与，消息大小为 $M$，每个节点有 $d$ 条带宽为 $\beta$ 的链路（全双工，同时收发）。
在 1-port 模型下，一个节点每步只能在 1 条链路上发送，有效出口带宽为 $\beta$。在 k-port 模型下，一个节点每步可以同时在 $k$ 条链路上发送，有效出口带宽为 $\min(k, d) \cdot \beta$。
若一个节点在整个操作过程中必须发送至少 $S$ 字节、接收至少 $R$ 字节，那么即使所有可用链路并行全速工作，完成时间也不低于：
$$\begin{equation} T_{\beta}^{\min} = \max\left(\frac{S}{p \cdot \beta}, \frac{R}{p \cdot \beta}\right), \quad p = \min(k, d) \label{eq:bw-lower-bound-general} \end{equation}$$其中 $p$ 是有效并行端口数。1-port 下 $p = 1$；all-port 下 $p = d$。后续各原语的推导以 1-port（$p = 1$, Ring 上 $d = 2$ 但每步只用 1 条链路）为基准，k-port 场景在各小节末尾单独分析。
关键在于推导每个原语中各节点必须发送和接收的最小数据量。
各原语的带宽下界详细推导见对应文档：03-一对多（Broadcast/Scatter）、04-多对一（Reduce/Gather）、05-reduce-scatter、06-all-gather、07-all-reduce、08-all-to-all。以下汇总各原语的下界结果。
各原语带宽下界汇总
1-port 模型（$p=1$）
| 原语 | 每节点发送 $S$ | 每节点接收 $R$ | 带宽下界 |
|---|---|---|---|
| Broadcast | $M$（root）/ 0 | $M$（非 root） | $M / \beta$ |
| Scatter | $M$（root）/ 0 | $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{(N-1)M}{N\beta}$（单阶段），总 $\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$（最大负载节点） |
2-port 模型（$p=2$，如双向 Ring）
| 原语 | 带宽下界（2-port） | 与 1-port 比 | Ring 实际步数 |
|---|---|---|---|
| ReduceScatter | $\frac{(N-1)M}{2N\beta}$ | $\times 0.5$ | $\lceil N/2 \rceil$ |
| AllGather | $\frac{(N-1)M}{2N\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}{2N\beta}$ | $\times 0.5$ | — |
综合下界
任何集合通信算法的时间同时受延迟下界和带宽下界约束：
$$\begin{equation} T \ge \max(T_{\alpha}^{\min}, T_{\beta}^{\min}) \label{eq:combined-lower-bound} \end{equation}$$以 AllReduce 为例：
$$\begin{equation} T \ge \max\left(\lceil \log_2 N \rceil \cdot \alpha, \quad \frac{(N-1)M}{N \cdot d\beta}\right) \label{eq:allreduce-combined-bound} \end{equation}$$这个 $\max$ 结构揭示了两种运行区间：
- 延迟主导区间（$M$ 很小）：$T_\alpha > T_\beta$，通信时间主要取决于步数。此时应选择延迟最优算法（步数少，如 Double Binary Tree 的 $O(\log N)$ 步）
- 带宽主导区间（$M$ 很大）：$T_\beta > T_\alpha$，通信时间主要取决于数据传输量。此时应选择带宽最优算法（链路利用率高，如 Ring 的 $\frac{2(N-1)}{N} \to 2$ 系数）
两个区间的交叉点为 $M^* = \frac{N \cdot d\beta \cdot \lceil \log_2 N \rceil \cdot \alpha}{(N-1)/1}$，消息大小在此值附近时两类算法性能接近。
最优算法的分类
- 延迟最优（Latency-Optimal）：算法的延迟项达到 $\lceil \log_2 N \rceil \cdot \alpha$
- 带宽最优（Bandwidth-Optimal）：算法的带宽项达到 $\frac{(N-1)M}{N \cdot d\beta}$
- 同时最优：少数算法能同时达到两个下界。Recursive Halving-Doubling 在 $N = 2^k$ 时同时具有 $O(\log N)$ 延迟和 $\frac{2(N-1)}{N}$ 带宽系数，是 AllReduce 的理论最优算法
各算法是否达到下界（以 AllReduce 为例）：
1-port 模型：
| 算法 | 延迟项 | 达到延迟下界？ | 带宽系数 | 达到带宽下界？ |
|---|---|---|---|---|
| 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}$ | 是 |
2-port 模型：
| 算法 | 延迟项 | 带宽项 | 备注 |
|---|---|---|---|
| Ring（双向） | $N \cdot \alpha$ | $\frac{M}{\beta}$ | 延迟减半，带宽仍最优 |
| Recursive Halving-Doubling | $2\log_2 N \cdot \alpha$ | $\frac{(N-1)M}{N\beta}$ | 2-port 下优势缩小，双向 Ring 已足够快 |
2-port 下双向 Ring 的延迟项从 $O(N)$ 降到 $O(N/2)$，与 Halving-Doubling 的 $O(\log N)$ 差距缩小。对于中等规模（$N \le 16$），双向 Ring 在延迟和带宽上都有竞争力，且实现更简单。
带宽最优的含义
"带宽最优"是相对于拓扑而言的——它衡量的是"算法是否充分利用了拓扑提供的带宽"，而非"算法的绝对性能"。Ring AllReduce 在 Ring 上带宽最优（每步每条链路都在传输数据，利用率 100%），Recursive Halving-Doubling 在超立方体上延迟+带宽同时最优。全连接拓扑（如 NVSwitch 域）的绝对性能更高，是因为硬件链路数多 $O(N)$ 倍（$N(N-1)/2$ 条 vs $N$ 条），不是算法优势。等链路预算下，Ring 的每条链路效率实际上更高。
Bisection 带宽下界
节点级带宽下界假设每个节点的链路可以独立使用。但在实际拓扑中，多个节点可能共享同一段物理链路，此时需要更紧的约束——bisection 带宽下界。
推导
将 $N$ 个节点等分为两组 $A$ 和 $B$，各 $N/2$ 个。横跨 $A$ 和 $B$ 之间的所有物理链路的总带宽称为 bisection bandwidth $B_{\text{bisection}}$。
对于 AllReduce：组 $A$ 中每个节点的最终结果需要包含组 $B$ 中所有节点的贡献（反之亦然）。从组 $B$ 传入组 $A$ 的数据量至少为多少？
组 $A$ 的 $N/2$ 个节点，每个节点最终持有 $M$ 字节的完整规约结果。结果中每个字节都包含了组 $B$ 的 $N/2$ 个节点的贡献。类似于单节点的推导，组 $A$ 至少需要从组 $B$ 接收 $\frac{N/2}{N} \cdot M = M/2$ 字节的有效信息（因为组 $A$ 自己贡献了 $N/2$ 份，组 $B$ 贡献了 $N/2$ 份，结果中组 $B$ 的贡献占比为 $1/2$）。
这 $M/2$ 字节必须通过 bisection 上的链路传输，因此：
$$\begin{equation} T_{\text{bisection}} \ge \frac{M/2}{B_{\text{bisection}}} \label{eq:bisection-lower-bound} \end{equation}$$对于 Ring 拓扑，bisection bandwidth 为 $B_{\text{bisection}} = 2\beta$（切割环的两条边），因此：
$$\begin{equation} T_{\text{bisection}} \ge \frac{M/2}{2\beta} = \frac{M}{4\beta} \label{eq:bisection-ring} \end{equation}$$对于 Fat-tree 拓扑，$B_{\text{bisection}} = \frac{N}{2} \cdot \beta$（全带宽），bisection 约束为 $\frac{M/2}{(N/2)\beta} = \frac{M}{N\beta}$，远小于节点级下界 $\frac{(N-1)M}{N\beta}$——此时节点级下界更紧，bisection 不是瓶颈。
结论：bisection 带宽下界在低 bisection bandwidth 的拓扑（Ring、Torus）中比节点级下界更紧，在高 bisection bandwidth 的拓扑（Fat-tree、全连接）中不起约束作用。
参考资料
- 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）- 各算法最优性分析