一对多通信：Broadcast 与 Scatter
一对多通信原语由单个 root 节点向多个节点分发数据。Broadcast 发送相同数据给所有节点，Scatter 将不同数据分片分发给各节点。
Broadcast
语义定义
root 节点将消息 $A$（大小 $M$ 字节）复制到通信域中所有 $N$ 个节点：
$$\begin{equation} \forall i \in [0, N): \quad B_i = A_{\text{root}} \label{eq:onetoall-bcast-semantic} \end{equation}$$理论下界
延迟下界：root 需要把信息传播到 $N-1$ 个节点。每步每个已有数据的节点可以发送给一个新节点，节点数以指数增长（$1, 2, 4, \ldots, 2^k$），因此至少 $\lceil \log_2 N \rceil$ 步：
$$\begin{equation} T_{\alpha}^{\min} = \lceil \log_2 N \rceil \cdot \alpha \label{eq:bcast-delay-lb} \end{equation}$$带宽下界：root 是唯一的数据源，它的 $M$ 字节数据最终要出现在其他 $N-1$ 个节点上，总传输量至少 $(N-1) \cdot M$ 字节。但关键瓶颈在 root 节点本身——root 是唯一的数据源，它必须直接或间接将 $M$ 字节送出。即使使用树形结构（root 发给 2 个子节点，子节点再转发），root 至少需要发送 $M$ 字节（发给第一层子节点）。因此 root 端的带宽下界为：
$$\begin{equation} T_{\beta}^{\min}(\text{Broadcast}) = \frac{M}{d \cdot \beta} \label{eq:broadcast-bw-lower-bound} \end{equation}$$带宽下界的通用推导框架见 01-理论下界。
综合下界：
$$\begin{equation} T_{\text{Broadcast}}^{\min} = \max\left(\lceil \log_2 N \rceil \cdot \alpha, \quad \frac{M}{d \cdot \beta}\right) \label{eq:bcast-combined-lb} \end{equation}$$算法分析
链式传播
root 依次沿链发送给每个节点。共 $N-1$ 步，每步发送完整 $M$ 字节给下一个节点，代价 $\alpha + M/\beta$：
$$\begin{equation} T_{\text{chain}} = (N-1) \cdot \left(\alpha + \frac{M}{\beta}\right) = (N-1)\alpha + \frac{(N-1)M}{\beta} \label{eq:chain-bcast} \end{equation}$$延迟项 $(N-1)\alpha$ 和带宽项 $(N-1)M/\beta$ 均远大于下界，实际中几乎不使用。
二叉树（Binomial Tree）
每步中所有已有数据的节点同时向一个新节点发送，节点数翻倍。8 节点示例：
| 步骤 | 发送者 → 接收者 | 已有数据节点数 |
|---|---|---|
| 1 | 0 → 4 | 2 |
| 2 | 0 → 2, 4 → 6 | 4 |
| 3 | 0 → 1, 2 → 3, 4 → 5, 6 → 7 | 8 |
共 $\lceil\log_2 N\rceil$ 步，每步所有已有数据的节点同时向一个新节点发送完整 $M$ 字节。每步代价 $\alpha + M/\beta$：
$$\begin{equation} T_{\text{binomial}} = \lceil \log_2 N \rceil \cdot \left(\alpha + \frac{M}{\beta}\right) = \lceil \log_2 N \rceil \cdot \alpha + \lceil \log_2 N \rceil \cdot \frac{M}{\beta} \label{eq:binomial-bcast} \end{equation}$$- 延迟项 $\lceil\log_2 N\rceil \cdot \alpha$ 达到延迟下界 $\eqref{eq:bcast-delay-lb}$
- 带宽项 $\lceil\log_2 N\rceil \cdot M/\beta$ 未达到带宽下界（每步传输完整 $M$，未利用分块流水线）
- 适合小消息（延迟主导区）
分块链式流水线
将消息切成 $k$ 块（每块 $M/k$），沿 $N-1$ 跳的链逐块流水传播。第 1 块需要 $N-1$ 步到达链尾，之后每步到达一个新块。总步数为 $(N-1) + (k-1) = N+k-2$，每步代价 $\alpha + \frac{M/k}{\beta}$：
$$\begin{equation} T_{\text{pipe-chain}} = (N + k - 2) \cdot \left(\alpha + \frac{M}{k\beta}\right) \label{eq:pipe-chain-bcast} \end{equation}$$对 $k$ 求导令 $dT/dk = 0$，可得最优分块数 $k^* = \sqrt{(N-1)M / (\alpha\beta)}$。当 $M \gg (N-1)\alpha\beta$ 时，$k^*$ 很大，$T^* \approx (N-1)\alpha + M/\beta \approx M/\beta$，趋近带宽下界 $\eqref{eq:broadcast-bw-lower-bound}$。适合大消息（带宽主导区）。
分块二叉树流水线
结合二叉树的低延迟和流水线的高带宽利用：
与分块链式类似，但基数从链（$N-1$ 步到达末端）缩短到树的高度（$\lceil\log_2 N\rceil$ 步）。第 1 块需要 $\lceil\log_2 N\rceil$ 步到达所有叶子，之后每步到达一个新块，总步数 $\lceil\log_2 N\rceil + k - 1$：
$$\begin{equation} T_{\text{pipe-tree}} = (\lceil \log_2 N \rceil + k - 1) \cdot \left(\alpha + \frac{M/k}{\beta}\right) \label{eq:pipe-tree-bcast} \end{equation}$$最优 $k^*$ 处同时接近延迟下界和带宽下界，是通用场景的最优实现。
SCCL 的 Broadcast 实现（4 芯 Ring）
4 芯双向 Ring 上，root 同时向两个方向广播：第 1 步向 rank 1 和 rank 3 各发一份 $A$，第 2 步 rank 1 转发给 rank 2。共 2 次迭代，与理论延迟下界 $\lceil\log_2 4\rceil = 2$ 步一致。
算法对比
| 算法 | 延迟项 | 带宽项 | 延迟最优？ | 带宽最优？ | 适用场景 |
|---|---|---|---|---|---|
| 链式 | $(N-1)\alpha$ | $(N-1)M/\beta$ | 否 | 否 | 不推荐 |
| 二叉树 | $\lceil\log_2 N\rceil\alpha$ | $\lceil\log_2 N\rceil M/\beta$ | 是 | 否 | 小消息 |
| 分块链式 | $(N-1)\alpha$（近似） | $\to M/\beta$ | 否 | 是 | 大消息 |
| 分块二叉树 | $\lceil\log_2 N\rceil\alpha$（近似） | $\to M/\beta$ | 是 | 是 | 通用 |
算法切换临界点：$M^* \approx 2N \cdot \alpha \cdot \beta$（MPICH 实测约 12 KB）。
Scatter
语义定义
root 将数据 $[A_0, A_1, ..., A_{N-1}]$（总大小 $M$）切片后分发，节点 $i$ 收到 $A_i$（大小 $M/N$）：
$$\begin{equation} \forall i \in [0, N): \quad B_i = A_i, \quad |A_i| = M/N \label{eq:onetoall-scatter-semantic} \end{equation}$$与 Broadcast 的区别：Broadcast 每节点收到相同完整数据（$M$ 字节），Scatter 每节点收到不同数据分片（$M/N$ 字节）。Scatter 无数据放大，总网络流量约为 $M$；Broadcast 总流量至少 $(N-1)M$。
理论下界
延迟下界：与 Broadcast 相同，需要至少 $\lceil \log_2 N \rceil$ 步：
$$\begin{equation} T_{\alpha}^{\min} = \lceil \log_2 N \rceil \cdot \alpha \label{eq:onetoall-scatter-delay-lb} \end{equation}$$带宽下界：root 发出 $M(N-1)/N$ 数据：
$$\begin{equation} T_{\beta}^{\min} = \frac{(N-1)M}{N \cdot d\beta} \label{eq:onetoall-scatter-bw-lb} \end{equation}$$算法分析
逐个发送（Naive）
root 依次向每个节点发送对应 chunk：
$$\begin{equation} T_{\text{naive}} = (N-1)\alpha + \frac{(N-1)M}{N\beta} \label{eq:onetoall-scatter-naive} \end{equation}$$延迟项差（$O(N)$），但带宽项达到下界。
二叉树 Scatter（Binomial Tree Scatter）
每步传输的数据量递减，8 节点（root=0）示例：
| 步骤 | 操作 | 传输数据量 |
|---|---|---|
| 1 | 0 → 4：发送 $[A_4..A_7]$ | $M/2$ |
| 2 | 0 → 2：发送 $[A_2,A_3]$；4 → 6：发送 $[A_6,A_7]$ | $M/4$ |
| 3 | 0→1, 2→3, 4→5, 6→7：各发 $M/8$ | $M/8$ |
共 $\lceil\log_2 N\rceil$ 步，每步启动延迟 $\alpha$。第 $j$ 步传输 $M/2^j$ 字节（数据量逐步减半）。带宽项求和：
$$\begin{equation} \frac{M}{\beta}\sum_{j=1}^{\log_2 N}\frac{1}{2^j} = \frac{M}{\beta}\left(1 - \frac{1}{N}\right) = \frac{(N-1)M}{N\beta} \label{eq:onetoall-scatter-binomial-bw-sum} \end{equation}$$因此：
$$\begin{equation} T_{\text{binomial-scatter}} = \lceil\log_2 N\rceil \cdot \alpha + \frac{(N-1)M}{N\beta} \label{eq:binomial-scatter} \end{equation}$$- 延迟项 $\lceil\log_2 N\rceil \cdot \alpha$ 达到延迟下界
- 带宽项 $\frac{(N-1)M}{N\beta}$ 达到带宽下界
- 同时最优，是理论最优的 Scatter 算法
对偶性：Scatter 与 Gather
Scatter 的对偶操作是 Gather（各节点数据收集到 root）。将 Scatter 算法的数据流反转即得 Gather 算法，代价公式完全相同：
$$\begin{equation} T_{\text{Gather}} = T_{\text{Scatter}} = \lceil\log_2 N\rceil \cdot \alpha + \frac{(N-1)M}{N\beta} \label{eq:onetoall-gather-scatter-duality} \end{equation}$$Broadcast 与 Scatter 的关系
Scatter + AllGather = Broadcast 的一种实现方式：先 Scatter 分发，再 AllGather 收集所有分片。大消息时可能优于直接 Broadcast，因为 Scatter 和 AllGather 都可以用带宽最优的 Ring 算法实现。
参考资料
- Thakur et al., "Optimization of Collective Communication Operations in MPICH"（IJHPCA, 2005）- Broadcast 算法切换策略
- Chan et al., "Collective Communication: Theory, Practice, and Experience"（CCPE, 2007）- Scatter/Broadcast 理论下界
- SCCL Documentation v1.0（SOPHGO）- 4 芯 Ring Broadcast/Scatter 实现
- NCCL Broadcast（NVIDIA）