多对一
Reduce 与 Gather 的语义、与一对多的对偶关系及算法下界
核心要点：
- Reduce 在汇聚链路上做规约 ($\oplus$), Gather 仅拼接不规约
- Reduce 是 Broadcast 的对偶，Gather 是 Scatter 的对偶 （反转数据流即得）
- 延迟下界 $\lceil \log_2 N \rceil \cdot \alpha$ 与对偶版本相同
- Reduce 带宽下界 $M / (d \beta)$, root 入口是瓶颈
- Binomial Tree Gather 同时达延迟与带宽下界，是四个一对多 / 多对一原语中唯一同时最优的算法 （与 Scatter 对偶）
Reduce
语义
所有节点数据按可结合可交换 $\oplus$ 规约，结果存 root:
$$\begin{equation} B_{\text{root}} = \bigoplus_{i=0}^{N-1} A_i \label{eq:cc-reduce-semantic} \end{equation}$$$\oplus \in$ {SUM, MAX, MIN, MUL}，每节点初始持 $A_i$ 大小 $M$。
Broadcast ↔ Reduce 对偶
反转 Broadcast 数据流并在汇聚点加规约即得 Reduce：
| 维度 | Broadcast | Reduce |
|---|---|---|
| 数据流方向 | root → 所有 | 所有 → root |
| 操作 | 复制 | 复制 + 规约 |
| 输入 / 节点 | $M$ （仅 root） | $M$ （所有） |
| 输出 / 节点 | $M$ （所有） | $M$ （仅 root） |
@tbl-cc-reduce-bcast-duality Broadcast ↔ Reduce 对偶
Broadcast 每种算法都有对应 Reduce 版本，反转数据流即可。
理论下界
核心问题：Reduce 的延迟、带宽、计算下界分别多少？
延迟下界：与 Broadcast 对偶，信息汇聚需 $\lceil \log_2 N \rceil$ 步：
$$\begin{equation} T_{\alpha}^{\min} = \lceil \log_2 N \rceil \cdot \alpha \label{eq:cc-reduce-delay-lb} \end{equation}$$带宽下界：规约可在中间节点执行，root 只需接收 $M$ 字节最终结果，瓶颈在 root 入口：
$$\begin{equation} T_{\beta}^{\min} = \frac{M}{d \beta} \label{eq:cc-reduce-bw-lb} \end{equation}$$计算下界：共 $(N-1)$ 次 $\oplus$ 累加，每次处理 $M$ 字节：
$$\begin{equation} T_{\text{compute}}^{\min} = \frac{(N-1) M}{\gamma} \label{eq:cc-reduce-compute-lb} \end{equation}$$SG2260 SUM 吞吐 $\gamma = 512$ GB/s，远高于通信带宽 64 GB/s, 计算通常不是瓶颈。
算法 1：链式 Reduce
Broadcast 链式的对偶，$N - 1$ 步：
$$\begin{equation} T_{\text{chain}} \approx (N-1) \alpha + \frac{(N-1) M}{\beta} \label{eq:cc-reduce-chain} \end{equation}$$延迟项与带宽项均远超下界，不推荐。
算法 2：二叉树 Reduce
Broadcast 二叉树的对偶，每步成对规约。8 节点示例：
| 步骤 | 操作 |
|---|---|
| 1 | 1 → 0, 3 → 2, 5 → 4, 7 → 6 （成对规约） |
| 2 | 2 → 0, 6 → 4 |
| 3 | 4 → 0 （最终规约） |
@tbl-cc-reduce-binomial-trace 8 节点二叉树 Reduce 步骤
$$\begin{equation} T_{\text{binomial}} = \lceil \log_2 N \rceil \cdot \left( \alpha + \frac{M}{\beta} \right) \label{eq:cc-reduce-binomial} \end{equation}$$延迟项达下界，带宽项 $\lceil \log_2 N \rceil \cdot M / \beta$ 非最优。
算法 3：分块流水线 Reduce
Broadcast 分块链式的对偶，沿链逐块流水规约：
$$\begin{equation} T_{\text{pipe}} = (N + k - 2) \cdot \left( \alpha + \frac{M / k}{\beta} + \frac{M / k}{\gamma} \right) \label{eq:cc-reduce-pipe} \end{equation}$$最优 $k^*$ 下大消息趋近 $M / \beta + M / \gamma$。
Reduce 特殊性：计算 / 通信交织
Reduce 中间节点必须做规约计算，不只是搬运。两点设计要注意：
- 计算 / 通信重叠：芯片若支持 （如 SG2260 CDMA + SUM 独立），接收下块时同时规约本块：
$\gamma \gg \beta$ 时计算完全被通信掩盖。
- 结合律要求：流水线 Reduce 要求 $\oplus$ 结合律。浮点 SUM 严格上不满足，实践误差通常可接受。
Gather
语义
所有节点数据按 rank 顺序收集到 root：
$$\begin{equation} B_{\text{root}} = [A_0, A_1, \ldots, A_{N-1}] \label{eq:cc-gather-semantic} \end{equation}$$各节点持 $A_i$ 大小 $M / N$, root 终持 $M$。
Scatter ↔ Gather 对偶
| 维度 | Scatter | Gather |
|---|---|---|
| 数据流方向 | root → 所有 | 所有 → root |
| 操作 | 分片分发 | 按序收集 |
| root 数据量变化 | $M \to M / N$ | $M / N \to M$ |
@tbl-cc-gather-scatter-duality Scatter ↔ Gather 对偶
理论下界与最优算法
核心问题：Gather 是否能同时达延迟与带宽下界？
综合下界 （与 Scatter 同）：
$$\begin{equation} T^{\min} = \max\left( \lceil \log_2 N \rceil \cdot \alpha, \quad \frac{(N-1) M}{N \cdot d \beta} \right) \label{eq:cc-gather-combined-lb} \end{equation}$$Binomial Tree Gather （Scatter 反向），每步传输量翻倍：
| 步骤 | 操作 | 单次传输量 |
|---|---|---|
| 1 | 1 → 0, 3 → 2, 5 → 4, 7 → 6 | $M / N = M / 8$ |
| 2 | 2 → 0, 6 → 4 | $M / 4$ |
| 3 | 4 → 0 | $M / 2$ |
@tbl-cc-gather-binomial-trace 8 节点 Binomial Tree Gather 步骤
第 $j$ 步每对节点传 $2^{j-1} M / N$，总带宽项：
$$\begin{equation} \frac{M}{N \beta} \sum_{j=1}^{\log_2 N} 2^{j-1} = \frac{(N-1) M}{N \beta} \label{eq:cc-gather-binomial-bw} \end{equation}$$ $$\begin{equation} T_{\text{binomial-gather}} = \lceil \log_2 N \rceil \cdot \alpha + \frac{(N-1) M}{N \beta} \label{eq:cc-gather-binomial} \end{equation}$$同时达延迟下界与带宽下界 — 理论最优。
Gather vs Reduce 的关键区别
| 维度 | Reduce | Gather |
|---|---|---|
| 操作 | 规约 ($\oplus$) | 拼接 |
| root 最终数据大小 | $M$ （与单节点输入同） | $M$ （所有节点拼接） |
| 数据量变化 | 不变 | 增长 $M/N \to M$ |
| 计算开销 | 有 | 无 |
@tbl-cc-gather-vs-reduce Gather 与 Reduce 区别
四原语统一视角
核心问题：Reduce/Gather/Broadcast/Scatter 四个原语在数据流向和拓扑上如何统一？
对称关系
Broadcast <-- 反转数据流 + 加规约 --> Reduce
| |
去规约 + 分片 去规约 + 分片
| |
v v
Scatter <-- 反转数据流 --> Gather
代价公式汇总
| 原语 | 最优算法 | 延迟项 | 带宽项 | 同时最优？ |
|---|---|---|---|---|
| Broadcast | 分块二叉树 | $\lceil \log_2 N \rceil \alpha$ | $\to M / \beta$ | 近似 |
| Scatter | 二叉树 | $\lceil \log_2 N \rceil \alpha$ | $(N-1) M / (N \beta)$ | 是 |
| Reduce | 分块二叉树 | $\lceil \log_2 N \rceil \alpha$ | $\to M / \beta$ | 近似 |
| Gather | 二叉树 | $\lceil \log_2 N \rceil \alpha$ | $(N-1) M / (N \beta)$ | 是 |
@tbl-cc-onetomany-cost-summary 四原语代价公式汇总
Scatter / Gather 同时达两下界，是四原语中理论最优；Broadcast / Reduce 需按消息大小在二叉树 (小 $M$) 与分块流水线 (大 $M$) 间切换。
Takeaway
| 知识点 | 核心结论 |
|---|---|
| Reduce 对偶于 Broadcast | 反转数据流 + 加规约 |
| Gather 对偶于 Scatter | 反转数据流 |
| Reduce 延迟下界 | $\lceil \log_2 N \rceil \cdot \alpha$ |
| Reduce 带宽下界 | $M / (d \beta)$, root 入口瓶颈 |
| Reduce 计算下界 | $(N-1) M / \gamma$，通常不是瓶颈 |
| Binomial Tree Gather | 延迟 + 带宽同时最优 |
| Reduce 算法切换 | 小 $M$ 二叉树，大 $M$ 分块流水线 |
| 浮点 SUM 注意 | 严格不结合，实践误差通常可接受 |
@tbl-cc-manytoone-takeaway 多对一通信要点
参考资料
- Thakur et al., "Optimization of Collective Communication Operations in MPICH", IJHPCA 2005
- Chan et al., "Collective Communication: Theory, Practice, and Experience", CCPE 2007
- Rabenseifner, "Optimization of Collective Reduction Operations", ICCS 2004
- SCCL Documentation v1.0 (SOPHGO)