Skip to main content

2.5 Compute Unit Design Choice

论文第4.3节 Compute Unit Design Choice 讨论的是：在 GenDP 的 PE 内部，计算单元（CU）应该采用什么结构的 ALU 归约树（reduction tree）。作者对比了 1 级、2 级、3 级三种方案，最终选择 2 级 ALU reduction tree。下面从背景、三种结构、对比指标和选择理由几个方面详细解释。

1. 为什么需要 reduction tree？​

在基因组 DP kernel 中，很多目标函数都有相似的“归约”模式。比如：

  • BSW：计算 H(i,j)H(i,j) 时，要从多个候选值中取最大值：

    H(i,j)=max⁡{0, H(i−1,j−1)+S, E(i,j), F(i,j)}H(i,j) = \max\{0,\ H(i-1,j-1)+S,\ E(i,j),\ F(i,j)\}

    这是一个“多输入取最大”的归约操作。

  • PairHMM：计算 fM(i,j)f^M(i,j) 时，要先把多个转移概率乘积累加起来：

    fM(i,j)=ρ⋅(αmmfM+αimfI+αdmfD)f^M(i,j) = \rho \cdot (\alpha_{mm} f^M + \alpha_{im} f^I + \alpha_{dm} f^D)

    这是一个“多输入求和”的归约操作。

这些操作可以表示成 归约树：多个输入经过多级 ALU，逐步归约成一个输出。Figure 7(a)(b) 展示了 BSW 和 PairHMM 的归约数据流。

如果 CU 只有一个 ALU，那么每次只能算一个操作，中间结果要频繁写回寄存器文件（RF），再读出来做下一步。这会增加 RF 访问次数，降低性能。因此，设计多级 ALU 树，让中间结果在 ALU 之间直接传递，可以减少 RF 访问。

2. 三种 ALU reduction tree 方案​

Figure 7(c)(d)(e) 展示了三种选择：

2.1 1 级 ALU reduction tree（Figure 7c）​

  • 只有 1 个 ALU。
  • 所有操作串行执行，每一步结果都要写回 RF，下一步再从 RF 读取。
  • 优点：面积小，关键路径短，ALU 利用率高（100%）。
  • 缺点：RF 访问次数多。因为每个中间结果都要存回寄存器，再读出来。

2.2 2 级 ALU reduction tree（Figure 7d）​

  • 有 3 个 ALU：第一级两个 ALU，第二级一个 ALU。
  • 第一级 ALU 的输出直接作为第二级 ALU 的输入，不需要写回 RF。
  • 优点：比 1 级减少 RF 访问次数；面积和关键路径平衡较好。
  • 缺点：ALU 利用率下降（因为有些 ALU 可能空闲）。

2.3 3 级 ALU reduction tree（Figure 7e）​

  • 有 7 个 ALU：第一级 4 个，第二级 2 个，第三级 1 个。
  • 更多中间结果在 ALU 树内部传递，进一步减少 RF 访问。
  • 优点：RF 访问次数最少。
  • 缺点：ALU 数量多，面积大；关键路径长；很多 ALU 在单单元格计算中空闲，利用率大幅下降。

3. 对比指标：Table 2 数据解读​

Table 2 比较了三种方案在四个 kernel 上的表现：

Kernel级别RF AccessesCU Utilization
BSW120100%
21160.6%
31028.6%
PairHMM13296.9%
21664.6%
31140.3%
POA15685.7%
25628.5%
35412.7%
Chain12495.8%
22038.3%
32016.4%
  • RF Accesses：计算一个 DP 单元格时，访问寄存器文件的次数。次数越少越好，因为 RF 访问耗能且可能成为瓶颈。
  • CU Utilization：在单单元格计算期间，每个 ALU 被利用的周期百分比。越高越好，表示硬件不浪费。

从数据看：

  • 1 级：RF 访问多，但利用率极高（接近 100%）。
  • 2 级：RF 访问明显减少（例如 BSW 从 20 降到 11），利用率适中（60% 左右）。
  • 3 级：RF 访问进一步减少，但幅度很小（BSW 从 11 降到 10，PairHMM 从 16 降到 11），而利用率大幅下降（BSW 从 60.6% 降到 28.6%）。

这说明：3 级树用更多的 ALU 换来了很小的 RF 访问减少，但导致大量 ALU 空闲，面积和能耗不划算。

4. 为什么选择 2 级？​

综合来看，2 级 reduction tree 是最佳平衡点：

  1. RF 访问显著减少：相比 1 级，2 级把 RF 访问几乎减半（BSW 20→11，PairHMM 32→16）。这直接降低了寄存器文件带宽压力和能耗。
  2. CU 利用率仍然可接受：虽然比 1 级低，但 60% 左右对于 DP 这种不规则计算已经不错。3 级虽然 RF 访问略少，但利用率太低，很多 ALU 闲置。
  3. 面积和关键路径更优：2 级只有 3 个 ALU，面积远小于 3 级的 7 个 ALU。关键路径也更短，有利于提高时钟频率。
  4. 与 DP 目标函数匹配：大多数 DP 目标函数的归约深度不超过 2 级。例如 BSW 的 max 操作可以两个一组归约，PairHMM 的求和也可以先两两相加再汇总。2 级树正好覆盖常见模式。

因此，论文最终选择 2 级 ALU reduction tree 作为 CU 的设计。

5. 乘法模块为什么独立？​

论文提到：

The CU also contains a multiplication module for the weight calculation in the Chain kernel. Since multiplication increases the length of the CU critical path, we design it as a separate unit from the ALU reduction tree.

意思是：

  • Chain kernel 需要做乘法（权重计算）。
  • 乘法器的延迟通常比加法/取最大值长，如果把它串在 ALU 归约树中，会拉长整个 CU 的关键路径，降低时钟频率。
  • 所以把乘法器设计成 独立单元，与 ALU 树并行或分时工作。这样 ALU 树可以保持较短的关键路径，乘法也不会拖慢整体。

6. 形象比喻​

把 CU 想象成一个厨房：

  • 1 级 ALU：只有一个灶台，每做一步菜都要把半成品端回冰箱（RF），下次再拿出来。冰箱门开关频繁，效率低。
  • 2 级 ALU：有三个灶台，第一级两个同时备料，第二级一个汇总。半成品直接在灶台间传递，不用频繁跑冰箱。灶台数量不多，大家都有活干。
  • 3 级 ALU：有七个灶台，但菜谱只需要两步，很多灶台闲着。虽然少跑了几趟冰箱，但厨房面积大、成本高，不划算。

因此，2 级是“够用且高效”的选择。

7. 一句话总结​

第4.3节通过对比 1 级、2 级、3 级 ALU reduction tree，发现 2 级树在减少寄存器文件访问、保持计算单元利用率、控制面积和关键路径之间取得了最佳平衡。乘法模块因关键路径长而独立设计。最终 GenDP 的 CU 采用 2 级 ALU 归约树，以高效支持 BSW、PairHMM、POA、Chain 等 DP kernel 的目标函数。