Skip to main content

2.5.2 vertical-horizontal sequence

在 PanGaea 论文 4.2 节中，vertical-horizontal sequence 是线性链阶段做全局归约时采用的一种通信顺序：先在 PE 网格的每一列内部做垂直归约，再把各列的结果沿第一行做水平归约，最终汇聚到 PE0PE_0，得到最大分数和对应的最佳 j∗j^*。

它本质上是二维网格上一种高效的“多对一”归约数据流，与广播的“一对多”正好相反。

1. 应用场景：线性链的归约需求​

线性链阶段，每个 PE 独立计算一个 (i,j)(i,j) 对的分数：

fi(j)=fj+score(i,j)−penalty(Δx,Δy)f_i(j) = f_j + \mathrm{score}(i,j) - \mathrm{penalty}(\Delta x,\Delta y)

12×12=14412 \times 12 = 144 个 PE 同时算出 144 个候选分数。
但最终只需要：

  • 最大分数 max⁡jfi(j)\max_j f_i(j)；
  • 对应的最佳 j∗j^*。

所以必须把这 144 个分数归约成一个结果。

2. 为什么用“垂直 + 水平”两步？​

如果直接把 144 个 PE 连成一棵全局归约树，布线复杂、延迟大。
而 PE 本身排成 2D 网格，天然有行和列两个方向。
于是把归约拆成两步：

  1. 垂直归约：每一列内部先比较，选出该列的最大值。
  2. 水平归约：第一行各列的最大值再比较，选出全局最大值。

这样每一步只在相邻 PE 之间通信，通信距离短，并行度高。

3. 具体步骤​

假设 PE 阵列是 12×1212 \times 12，用 (r,c)(r, c) 表示第 rr 行、第 cc 列的 PE，r=0r=0 是第一行，c=0c=0 是第一列。

第一步：垂直通信（列内归约）​

  • 每一列 cc 中，从下往上（或从上往下）依次比较。
  • 每个 PE 把自己的分数与从下方传来的当前最大值比较，保留较大者及其对应的 jj。
  • 最终，每一列的最大值被送到第一行对应的 PE (0,c)(0, c)。

例如第 cc 列：

PE(11,c) 分数 → 与 PE(10,c) 比较 → 胜者 → 与 PE(9,c) 比较 → ... → PE(0,c)

这样，PE(0,c)PE(0,c) 就拿到了第 cc 列的最大分数和最佳 jj。

第二步：水平通信（行内归约）​

  • 第一行有 12 个 PE，每个都持有本列的最大值。
  • 从右往左（或从左往右）依次比较。
  • 每个 PE 把当前最大值与从右边传来的最大值比较，保留较大者及其 jj。
  • 最终，PE(0,0)PE(0,0) 即 PE0PE_0 得到全局最大分数和最佳 j∗j^*。

例如第一行：

PE(0,11) → 与 PE(0,10) 比较 → 胜者 → 与 PE(0,9) 比较 → ... → PE(0,0)

第三步：存储结果​

PE0PE_0 把全局最大分数和最佳 j∗j^* 写入 SRAM，供后续阶段使用。

4. 为什么这样设计高效？​

  • 通信局部化：垂直和水平都只在相邻 PE 之间传递，不需要长距离全局连线。
  • 并行性高：每一列的垂直归约可以同时进行；第一行的水平归约也可以流水进行。
  • 无需专用归约树：MAX 比较器直接嵌入 PE 的输出混合逻辑中，节省约 15% 面积，减少 3 周期延迟（论文 4.2 节）。
  • 与 PE 网格拓扑匹配：PE 阵列本来就是 2D 网格，垂直-水平顺序顺应了物理布局，布线自然。

5. 与广播的对比​

操作方向用途通信模式
H-tree 广播一对多把锚点数据从 PE0PE_0 发给所有 PE根 → 所有叶子
Vertical-horizontal 归约多对一把所有 PE 的分数汇聚到 PE0PE_0所有 PE → 列 → 行 → PE0PE_0

两者配合，构成线性链阶段完整的“广播-计算-归约”数据流：

  1. 广播：PE0PE_0 把 aia_i 发给所有 PE；
  2. 计算：每个 PE 算一个 (i,j)(i,j) 分数；
  3. 归约：垂直-水平序列把最大值汇聚回 PE0PE_0。

6. 一句话总结​

Vertical-horizontal sequence 是一种在 2D PE 网格中先按列、再按行做归约的通信顺序，用于把 144 个 PE 的计算结果高效汇聚到 PE0PE_0，得到全局最大值和最佳 j∗j^*。它利用网格的天然拓扑，避免专用归约树，减少布线和延迟，是 PanGaea 线性链阶段的关键数据流。