Skip to main content

2.5.3 All-reduce communication

All-reduce communication 是并行计算中的一种集合通信操作：所有参与节点各自提供一个值，经过归约（如求和、取最大值）后，每个节点都得到相同的归约结果。

简单说就是：
每个人都贡献一个数 → 大家一起算出总和/最大值 → 每个人都拿到这个最终结果。

它和普通“归约”的区别在于：

  • Reduce：所有节点把值汇总到一个节点，只有那个节点知道结果。
  • All-reduce：汇总后，结果广播给所有节点，人人都知道。

在 PanGaea 论文 4.2 节中，All-reduce 被用于 WFA 波前对齐模式（Mode 2A/2B） 的数据流，用来在 PE 阵列中同步波前状态，确保每个 PE 都能拿到全局一致的 DP 值，继续沿对角线推进。

1. 为什么 WFA 需要 All-reduce？​

WFA 沿 DP 矩阵的对角线推进。计算单元格 (s,d)(s,d) 时，需要之前波前 (s−δ,d±1)(s-\delta, d\pm 1) 的值。
这些值可能由多个 PE 分别计算出来，但每个 PE 都需要用到它们来更新自己的状态。

例如：

  • 某些 PE 负责计算 EE 矩阵，某些负责 FF 矩阵；
  • 相邻对角线共享大量数据；
  • 计算 Hs,dH_{s,d} 时需要从多个 penalty level 取最大值。

如果每个 PE 只知道自己局部的值，就无法正确计算下一层。
因此必须：

  1. 归约：把多个 PE 的局部结果合并（比如取最大值），得到全局正确的波前值；
  2. 广播：把这个全局值发给所有 PE，让它们同步更新。

这两步合起来就是 All-reduce。

2. 在 PanGaea 中如何实现？​

论文 4.2 节提到，WFA 模式采用 邻居交换 + All-reduce 的混合数据流：

  • 邻居交换：每个 PE 把 EE 矩阵发给右邻居，把 FF 矩阵发给左邻居。
    这是点对点通信，利用对角线依赖的局部性。

  • All-reduce 通信：除了邻居交换，还需要把某些结果归约并广播给所有相关 PE。
    例如图 6(c) 显示数据从 PE0PE_0 通过 All-reduce 发送到 PE5PE_5。

在 PE 网格中，All-reduce 通常分两步：

  1. 归约阶段：沿水平或垂直方向，各 PE 把自己的局部值传递并比较，最终汇聚到一个节点（例如 PE0PE_0）得到全局最大值。
  2. 广播阶段：PE0PE_0 把全局结果沿原路广播回去，所有 PE 都收到相同的值。

这样，每个 PE 都获得了全局一致的波前值，可以继续计算下一层对角线。

3. 一个直观比喻​

想象一个团队在做决策：

  • 每个成员（PE）手头有一个候选分数。
  • 他们需要知道全队的最高分，并且每个人都要知道这个最高分是多少，才能继续下一步。

All-reduce 的过程就是：

  1. 每个人把分数传给组长，组长比较后得到最高分（归约）；
  2. 组长把最高分告诉所有人（广播）。

最终，每个人都拿到了相同的最高分。
在 WFA 中，这个“最高分”就是某个波前层的正确 DP 值，所有 PE 必须同步使用它。

4. 与线性链的垂直-水平归约对比​

特性线性链归约（Mode 1）WFA All-reduce（Mode 2A/2B）
目的从 144 个分数中找全局最大，只需 PE0PE_0 知道归约波前值，并让所有 PE 都知道
通信方向垂直 → 水平，最终汇聚到 PE0PE_0归约 + 广播，所有 PE 都参与并接收
结果分布只在 PE0PE_0 存储所有 PE 都获得相同结果
硬件实现嵌入 PE 输出逻辑的 MAX 比较器邻居交换 + 网格上的归约/广播路径

5. 为什么不用简单的广播或归约？​

  • 只用归约：只有 PE0PE_0 得到全局值，其他 PE 不知道，无法继续计算。
  • 只用广播：没有归约，广播的值从哪来？必须先合并多个 PE 的局部结果。
  • All-reduce 正好结合两者：先归约出全局值，再广播给所有人。

在 WFA 中，每个 PE 都需要全局波前值来更新自己的 H,E,FH, E, F 矩阵，所以 All-reduce 是自然的选择。

6. 总结​

All-reduce 是一种“人人贡献、人人知晓”的集合通信操作：先归约（如取最大），再广播结果。
在 PanGaea 的 WFA 模式中，它用于同步波前 DP 值：多个 PE 计算出的局部结果先归约成全局正确值，然后广播给所有 PE，确保对角线推进时每个 PE 都使用一致的数据。它与邻居交换配合，构成了 WFA 高效的数据流。

一句话：All-reduce 就是“大家一起算出一个结果，然后每个人都拿到这个结果”，在 WFA 中保证所有 PE 步调一致地推进波前。