一对多
Broadcast 与 Scatter 的语义差异、算法与下界分析
核心要点：
- Broadcast 各节点收相同 $M$ 字节，Scatter 各节点收不同 $M / N$ 字节分片
- 两者延迟下界都是 $\lceil \log_2 N \rceil \cdot \alpha$
- Broadcast 的带宽下界 $M / (d \beta)$ 由 root 出口带宽决定，root 是瓶颈
- 二叉树达到延迟最优，分块二叉树流水线同时趋近带宽下界
- Binomial Tree Scatter 同时达延迟与带宽下界，是理论最优
Broadcast
语义
root 把 $M$ 字节消息 $A$ 复制到所有 $N$ 节点:
$$\begin{equation} \forall i \in [0, N): \quad B_i = A_{\text{root}} \label{eq:cc-bcast-semantic} \end{equation}$$理论下界
核心问题：Broadcast 最少需要几步 / 多少带宽？
延迟下界：信息需扩散到 $N$ 节点，倍增传播给出 $\lceil \log_2 N \rceil$ 步：
$$\begin{equation} T_{\alpha}^{\min} = \lceil \log_2 N \rceil \cdot \alpha \label{eq:cc-bcast-delay-lb} \end{equation}$$带宽下界：root 是唯一数据源，必须直接或间接送出 $M$ 字节。即使树形并发分发，root 出口至少要把 $M$ 字节推上 $d$ 条链路：
$$\begin{equation} T_{\beta}^{\min} = \frac{M}{d \beta} \label{eq:cc-bcast-bw-lb} \end{equation}$$综合下界：
$$\begin{equation} T_{\text{Bcast}}^{\min} = \max\left( \lceil \log_2 N \rceil \cdot \alpha, \quad \frac{M}{d \beta} \right) \label{eq:cc-bcast-combined-lb} \end{equation}$$带宽下界通用推导框架见 4.2 理论下界。
算法 1：链式传播 （不推荐）
root 依次沿链发，$N-1$ 步，每步发完整 $M$ 字节：
$$\begin{equation} T_{\text{chain}} = (N-1) \alpha + \frac{(N-1) M}{\beta} \label{eq:cc-bcast-chain} \end{equation}$$延迟项 $O(N)$ 与带宽项 $(N-1)M/\beta$ 都远超下界，实际不用。
算法 2：二叉树 (Binomial Tree)
每步所有已有数据的节点同时向一个新邻居发送，持有方倍增。
8 节点示例：
| 步骤 | 发送者 → 接收者 | 已有数据节点数 |
|---|---|---|
| 1 | 0 → 4 | 2 |
| 2 | 0 → 2, 4 → 6 | 4 |
| 3 | 0 → 1, 2 → 3, 4 → 5, 6 → 7 | 8 |
@tbl-cc-bcast-binomial-trace 8 节点 Binomial Tree Broadcast 步骤
$\lceil \log_2 N \rceil$ 步，每步完整 $M$:
$$\begin{equation} T_{\text{binomial}} = \lceil \log_2 N \rceil \cdot \left( \alpha + \frac{M}{\beta} \right) \label{eq:cc-bcast-binomial} \end{equation}$$延迟最优 ($= \lceil \log_2 N \rceil \alpha$，达 $\eqref{eq:cc-bcast-delay-lb}$)，带宽项 $\lceil \log_2 N \rceil \cdot M / \beta$ 未达下界，适合小消息。
算法 3：分块链式流水线
消息切 $k$ 块沿 $N-1$ 跳链流水。第 1 块要 $N-1$ 步到链尾，之后每步到一新块，总步数 $N + k - 2$:
$$\begin{equation} T_{\text{pipe-chain}} = (N + k - 2) \cdot \left( \alpha + \frac{M}{k \beta} \right) \label{eq:cc-bcast-pipe-chain} \end{equation}$$最优 $k^* = \sqrt{(N-1) M / (\alpha \beta)}$。$M \gg (N-1) \alpha \beta$ 时 $T^* \to M / \beta$, 趋近带宽下界。适合大消息。
算法 4：分块二叉树流水线 （通用最优）
树高从链的 $N-1$ 缩到 $\lceil \log_2 N \rceil$:
$$\begin{equation} T_{\text{pipe-tree}} = (\lceil \log_2 N \rceil + k - 1) \cdot \left( \alpha + \frac{M}{k \beta} \right) \label{eq:cc-bcast-pipe-tree} \end{equation}$$最优 $k^*$ 处同时趋近延迟与带宽下界，是通用场景的最优实现。
算法对比与切换
| 算法 | 延迟项 | 带宽项 | 延迟最优 | 带宽最优 | 适用 |
|---|---|---|---|---|---|
| 链式 | $(N-1) \alpha$ | $(N-1) M / \beta$ | 否 | 否 | 不推荐 |
| 二叉树 | $\lceil \log_2 N \rceil \alpha$ | $\lceil \log_2 N \rceil M / \beta$ | 是 | 否 | 小消息 |
| 分块链式 | $\approx (N-1) \alpha$ | $\to M / \beta$ | 否 | 是 | 大消息 |
| 分块二叉树 | $\approx \lceil \log_2 N \rceil \alpha$ | $\to M / \beta$ | 是 | 是 | 通用 |
@tbl-cc-bcast-algo-cmp Broadcast 算法对比
算法切换临界点：$M^* \approx 2 N \alpha \beta$, MPICH 实测约 12 KB。
SCCL 4 芯 Ring 实现
4 芯 2-port Ring 上 root 同时向两侧广播：第 1 步向 rank 1 与 rank 3 各发一份 $A$，第 2 步 rank 1 转发给 rank 2。共 2 步，与延迟下界 $\lceil \log_2 4 \rceil = 2$ 一致。
Scatter
语义
root 把 $[A_0, \ldots, A_{N-1}]$ 切片分发，节点 $i$ 收 $A_i$ (大小 $M / N$):
$$\begin{equation} \forall i \in [0, N): \quad B_i = A_i, \quad |A_i| = M / N \label{eq:cc-scatter-semantic} \end{equation}$$与 Broadcast 的区别：Broadcast 每节点收完整 $M$，网络总流量至少 $(N-1) M$; Scatter 每节点收 $M / N$ 不同分片，网络总流量约 $M$, 无数据放大。
理论下界
核心问题：Scatter 的延迟和带宽下界？
延迟下界：与 Broadcast 同，信息扩散需 $\lceil \log_2 N \rceil$ 步。
带宽下界：root 总共发出 $(N-1) M / N$ 字节：
$$\begin{equation} T_{\beta}^{\min} = \frac{(N-1) M}{N \cdot d \beta} \label{eq:cc-scatter-bw-lb} \end{equation}$$算法 1：逐个发送 (Naive)
root 依次发对应 chunk：
$$\begin{equation} T_{\text{naive}} = (N-1) \alpha + \frac{(N-1) M}{N \beta} \label{eq:cc-scatter-naive} \end{equation}$$带宽项达下界，延迟项 $O(N)$ 差。
算法 2: 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$ |
@tbl-cc-scatter-binomial-trace 8 节点 Binomial Tree Scatter 步骤
总 $\lceil \log_2 N \rceil$ 步，第 $j$ 步传 $M / 2^j$:
$$\begin{equation} \sum_{j=1}^{\log_2 N} \frac{M}{2^j \beta} = \frac{M}{\beta} \left( 1 - \frac{1}{N} \right) = \frac{(N-1) M}{N \beta} \label{eq:cc-scatter-binomial-bw} \end{equation}$$ $$\begin{equation} T_{\text{binomial-scatter}} = \lceil \log_2 N \rceil \cdot \alpha + \frac{(N-1) M}{N \beta} \label{eq:cc-scatter-binomial} \end{equation}$$延迟项与带宽项同时达下界，是 Scatter 的理论最优算法。
Scatter ↔ Gather 对偶
Scatter 数据流反转即得 Gather，代价公式相同：
$$\begin{equation} T_{\text{Gather}} = T_{\text{Scatter}} = \lceil \log_2 N \rceil \alpha + \frac{(N-1) M}{N \beta} \label{eq:cc-scatter-gather-duality} \end{equation}$$Broadcast = Scatter + AllGather
大消息场景，可改写 Broadcast 为 Scatter + AllGather：先分发，再环状收集。Scatter 与 AllGather 都可用带宽最优 Ring 实现，实测大 $M$ 下优于直接 Broadcast。
Takeaway
| 知识点 | 核心结论 |
|---|---|
| Broadcast vs Scatter | 同 root，前者复制 $M$，后者切 $M / N$ 分片 |
| 延迟下界 | 同为 $\lceil \log_2 N \rceil \cdot \alpha$ |
| Broadcast 带宽下界 | $M / (d \beta)$, root 是瓶颈 |
| Scatter 带宽下界 | $(N-1) M / (N d \beta)$ |
| Broadcast 算法选型 | 小 $M$ 二叉树，大 $M$ 分块二叉树流水线 |
| Binomial Tree Scatter | 延迟 + 带宽同时最优 |
| Gather 对偶 | Scatter 反向，公式同 |
| 大消息 Broadcast 改写 | Scatter + AllGather，带宽最优 |
@tbl-cc-onetomany-takeaway 一对多通信要点
参考资料
- Thakur et al., "Optimization of Collective Communication Operations in MPICH", IJHPCA 2005 — Broadcast 算法切换
- Chan et al., "Collective Communication: Theory, Practice, and Experience", CCPE 2007 — 理论下界
- SCCL Documentation v1.0 (SOPHGO) — 4 芯 Ring Broadcast / Scatter 实现
- NCCL Broadcast