跳到主要内容

多对一通信：Reduce 与 Gather

多对一通信原语由多个节点将数据汇聚到单个 root 节点。Reduce 对数据执行规约运算（SUM/MAX/MIN），Gather 执行数据拼接（无规约）。两者分别是 Broadcast 和 Scatter 的对偶操作。

Reduce​

语义定义​

所有节点的数据执行规约运算，结果存储在 root 节点：

$$\begin{equation} B_{\text{root}} = \bigoplus_{i=0}^{N-1} A_i \label{eq:alltoone-reduce-semantics} \end{equation}$$

其中 $\oplus$ 为关联且交换的规约运算（SUM/MAX/MIN/MUL），每个节点 $i$ 持有数据 $A_i$（大小 $M$ 字节）。

与 Broadcast 的对偶性​

Reduce 是 Broadcast 的逆操作——反转数据流并在每个汇聚点加入规约计算：

维度BroadcastReduce
数据流方向root → 所有节点所有节点 → root
操作复制复制 + 规约
输入/节点$M$（仅 root）$M$（所有节点）
输出/节点$M$（所有节点）$M$（仅 root）

Broadcast 的每种算法都有对应的 Reduce 版本（反转数据流即得）。

理论下界​

延迟下界：与 Broadcast 对偶，$N$ 个节点的数据需要汇聚到 root，信息传播约束同样要求至少 $\lceil\log_2 N\rceil$ 步：

$$\begin{equation} T_{\alpha}^{\min} = \lceil \log_2 N \rceil \cdot \alpha \label{eq:reduce-delay-lb} \end{equation}$$

带宽下界：规约操作可在中间节点执行（部分结果逐步合并），root 不需要接收所有 $(N-1)M$ 字节原始数据。root 只需接收 $M$ 字节的最终规约结果，因此瓶颈在 root 端的入口带宽：

$$\begin{equation} T_{\beta}^{\min} = \frac{M}{d \cdot \beta} \label{eq:reduce-bw-lb} \end{equation}$$

计算下界（额外引入）：

$$\begin{equation} T_{\text{compute}}^{\min} = \frac{(N-1) \cdot M}{\gamma} \label{eq:alltoone-reduce-compute-lb} \end{equation}$$

其中 $\gamma$ 为规约运算的计算吞吐量。以 SG2260 为例，SUM 单元吞吐量 $\gamma = 512$ GB/s，远高于通信带宽 64 GB/s，因此计算通常不是瓶颈。

算法分析​

链式 Reduce​

Broadcast 链式传播的对偶。$N-1$ 步，每步一个节点将 $M$ 字节发给上游并执行规约。每步代价 $\alpha + M/\beta + M/\gamma$（通信 + 规约），当 $\gamma \gg \beta$ 时计算被覆盖：

$$\begin{equation} T_{\text{chain-reduce}} \approx (N-1)\alpha + \frac{(N-1)M}{\beta} \label{eq:chain-reduce} \end{equation}$$

二叉树 Reduce​

Broadcast 二叉树反转。8 节点（root=0）示例：

步骤操作
11→0, 3→2, 5→4, 7→6（每对相邻节点规约）
22→0, 6→4（两对结果再规约）
34→0（最终规约）

Broadcast 二叉树的对偶：$\lceil\log_2 N\rceil$ 步，每步子节点向父节点发送完整 $M$ 字节并规约。每步代价 $\alpha + M/\beta$：

$$\begin{equation} T_{\text{binomial-reduce}} \approx \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-reduce} \end{equation}$$

延迟项达到下界 $\eqref{eq:reduce-delay-lb}$，但带宽项 $\lceil\log_2 N\rceil \cdot M/\beta$ 非最优（每步传输完整 $M$）。

分块流水线 Reduce​

Broadcast 分块链式的对偶。将 $M$ 分成 $k$ 块，沿链逐块流水传播并规约。第 1 块需要 $N-1$ 步到达 root，之后每步到达一块，总步数 $N - 1 + k - 1$：

$$\begin{equation} T_{\text{pipe-reduce}} = (N - 1 + k - 1) \cdot \left(\alpha + \frac{M/k}{\beta} + \frac{M/k}{\gamma}\right) \label{eq:pipe-reduce} \end{equation}$$

最优 $k^*$ 处，大消息时趋近 $M/\beta + M/\gamma$（带宽最优）。

Reduce 的特殊性：规约计算与通信的交织​

与纯数据搬运（Broadcast/Scatter/Gather）不同，Reduce 的每个中间节点需要对收到的数据执行规约计算。

计算-通信重叠：若芯片支持计算和通信并行（如 SG2260 的 CDMA + SUM 单元独立运行），可在接收下一个 chunk 的同时对当前 chunk 执行规约：

$$\begin{equation} T_{\text{overlap}} = (N-1 + k - 1) \cdot \left(\alpha + \max\left(\frac{M/k}{\beta}, \frac{M/k}{\gamma}\right)\right) \label{eq:alltoone-reduce-overlap} \end{equation}$$

当 $\gamma \gg \beta$ 时，计算时间完全隐藏。

规约操作的结合律要求：流水线 Reduce 要求规约运算满足结合律（associativity）。浮点数 SUM 严格来说不满足，但实践中误差通常可接受。

Gather​

语义定义​

所有节点数据按 rank 顺序收集到 root：

$$\begin{equation} B_{\text{root}} = [A_0, A_1, ..., A_{N-1}] \label{eq:alltoone-gather-semantics} \end{equation}$$

每个节点 $i$ 持有 $A_i$（大小 $M/N$），root 最终持有总大小 $M$ 的完整数据。

与 Scatter 的对偶性​

Gather 是 Scatter 的逆操作（反转数据流）：

维度ScatterGather
数据流方向root → 所有节点所有节点 → root
操作分片分发按序收集
root 数据量变化$M$ → $M/N$$M/N$ → $M$

理论下界（与 Scatter 相同）​

$$\begin{equation} T_{\text{Gather}}^{\min} = \max\left(\lceil\log_2 N\rceil \cdot \alpha, \quad \frac{(N-1)M}{N \cdot d\beta}\right) \label{eq:gather-combined-lb} \end{equation}$$

二叉树 Gather（理论最优算法）​

Binomial Scatter 反转。每步中子节点向父节点发送数据，传输量逐步翻倍：

步骤操作传输数据量
11→0, 3→2, 5→4, 7→6每对传输 $M/8$
22→0, 6→4每对传输 $M/4$
34→0传输 $M/2$

共 $\lceil\log_2 N\rceil$ 步，第 $j$ 步每对子-父节点传输 $M \cdot 2^{j-1}/N$ 字节（数据量逐步翻倍）。带宽项求和：

$$\begin{equation} \frac{M}{N\beta}\sum_{j=1}^{\log_2 N} 2^{j-1} = \frac{M}{N\beta}(1 + 2 + \ldots + N/2) = \frac{M}{N\beta} \cdot (N-1) = \frac{(N-1)M}{N\beta} \label{eq:alltoone-gather-bw-sum} \end{equation}$$

因此：

$$\begin{equation} T_{\text{binomial-gather}} = \lceil\log_2 N\rceil \cdot \alpha + \frac{(N-1)M}{N\beta} \label{eq:binomial-gather} \end{equation}$$

同时达到延迟下界和带宽下界 $\eqref{eq:gather-combined-lb}$ ——理论最优。

Gather 与 Reduce 的区别​

维度ReduceGather
操作规约（SUM/MAX/...）拼接（concatenation）
root 最终数据大小$M$（与输入相同）$M$（所有节点数据拼接）
数据量变化不变增长（$M/N$ → $M$）
计算开销有无（纯数据搬运）

四个原语的统一视角​

对称关系​

Broadcast  <--反转数据流+加规约-->  Reduce
    |                                  |
  去规约+                            去规约+
  数据分片                           数据分片
    |                                  |
    v                                  v
Scatter    <--反转数据流-->          Gather

代价公式汇总​

原语最优算法延迟项带宽项同时最优？
Broadcast分块二叉树$\lceil\log_2 N\rceil \cdot \alpha$$M/\beta$（近似）近似
Scatter二叉树$\lceil\log_2 N\rceil \cdot \alpha$$\frac{(N-1)M}{N\beta}$是
Reduce分块二叉树$\lceil\log_2 N\rceil \cdot \alpha$$M/\beta$（近似）近似
Gather二叉树$\lceil\log_2 N\rceil \cdot \alpha$$\frac{(N-1)M}{N\beta}$是

Scatter 和 Gather 能同时达到两个下界，是四个原语中理论最优的。Broadcast 和 Reduce 需要在延迟主导（二叉树）和带宽主导（流水线）之间按消息大小做算法切换。

参考资料​