*2.5.1 ALU
Multi-level ALU array（多级 ALU 阵列） 是 GenDP 论文中计算单元（CU）的核心结构。它不是简单的“多个 ALU 并排”，而是把多个 ALU 按层级组织成一棵 归约树（reduction tree），让中间结果在 ALU 之间直接传递，而不必频繁写回寄存器文件。
论文第 3.2 节说：
In order to support DP objective functions efficiently in the PE, we design a multi-level ALU array in the compute unit.
第 4.3 节进一步对比了 1 级、2 级、3 级三种方案，最终选择 2 级 ALU reduction tree。
下面从结构、工作原理、对比、应用场景几个方面详细解释。
1. 什么是 ALU 阵列？
ALU（Arithmetic Logic Unit，算术逻辑单元） 是执行基本运算的硬件单元，比如：
- 加法、减法
- 取最大值、最小值
- 比较（大于、等于）
- 移位、按位与/或
ALU 阵列 = 多个 ALU 组合在一起，可以同时执行多个操作。
最简单的形式是 1 级 ALU 阵列：只有一个 ALU，所有操作串行执行，每步结果写回寄存器，下一步再读出来。
2. 什么是“多级”ALU 阵列？
多级 指的是把多个 ALU 组织成 层级结构，每一级的输出作为下一级的输入，形成一棵 归约树。
论文 Figure 7 展示了三种方案：
2.1 1 级 ALU 树（Figure 7c）
┌─────────┐
输入 ──►│ ALU │──► 输出
└─────────┘
- 只有 1 个 ALU；
- 每次操作后结果必须写回寄存器文件（RF）；
- 下一步再从 RF 读出来。
问题：RF 访问次数多，功耗高，可能成为瓶颈。
2.2 2 级 ALU 树（Figure 7d）
┌─────────┐
输入 ──►│ ALU 1 │──┐
└─────────┘ │ ┌─────────┐
├──►│ ALU 3 │──► 输出
┌─────────┐ │ └─────────┘
输入 ──►│ ALU 2 │──┘
└─────────┘
- 第一级 2 个 ALU，第二级 1 个 ALU；
- 第一级的输出直接作为第二级的输入，不需要写回 RF；
- 总共 3 个 ALU。
优势：减少 RF 访问，面积和关键路径平衡好。
2.3 3 级 ALU 树（Figure 7e）
┌────┐ ┌────┐ ┌────┐ ┌────┐
输入 ──►│ALU │ │ALU │ │ALU │ │ALU │──┐
└────┘ └────┘ └────┘ └────┘ │
│ │ │ │
▼ ▼ ▼ │
┌────┐ ┌────┐ │
│ALU │ │ALU │────────────┤
└────┘ └────┘ │
│ │
▼ │
┌────┐ │
│ALU │───────────────┘
└────┘
- 第一级 4 个，第二级 2 个，第三级 1 个；
- 总共 7 个 ALU；
- RF 访问最少，但 ALU 数量多，很多 ALU 在单单元格计算中空闲。
3. 为什么需要多级？
核心原因是 减少寄存器文件（RF）访问。
在 DP 计算中，一个单元格需要多个操作，比如 BSW 的：
H(i,j) = max(0, H(i-1,j-1) + S, E(i,j), F(i,j))
这个公式包含：
- 1 次加法；
- 1 次取最大值（可能有多个输入）。
如果只有 1 个 ALU：
1. 读 H_diag, S → 加 → 写回 RF
2. 读 RF, 0, E, F → 取最大值 → 写回 RF
两次读写 RF。每一步都要访问寄存器，功耗和延迟都高。
如果有 2 级 ALU 树：
1. 读 H_diag, S → ALU1 加
读 E, F → ALU2 取最大值
2. ALU1 和 ALU2 的输出 → ALU3 取最大值 → 写回 RF
只需一次 RF 访问，中间结果在 ALU 树内部传递。
4. 论文的对比数据（Table 2）
论文比较了三种方案在四个 kernel 上的表现：
| Kernel | 级别 | RF 访问次数 | CU 利用率 |
|---|---|---|---|
| BSW | 1 | 20 | 100% |
| 2 | 11 | 60.6% | |
| 3 | 10 | 28.6% | |
| PairHMM | 1 | 32 | 96.9% |
| 2 | 16 | 64.6% | |
| 3 | 11 | 40.3% | |
| POA | 1 | 56 | 85.7% |
| 2 | 56 | 28.5% | |
| 3 | 54 | 12.7% | |
| Chain | 1 | 24 | 95.8% |
| 2 | 20 | 38.3% | |
| 3 | 20 | 16.4% |
结论：
- 3 级虽然 RF 访问略少，但 ALU 利用率大幅下降（大量 ALU 空闲）；
- 2 级在 RF 访问减少和 ALU 利用率之间取得最佳平衡；
- 因此论文选择 2 级 ALU reduction tree。
5. 乘法模块为什么独立？
论文说：
Since multiplication increases the length of the CU critical path, we design it as a separate unit from the ALU reduction tree.
意思是：
- 乘法器延迟比加法/取最大值长；
- 如果放在 ALU 树中，会拉长整个 CU 的关键路径，降低时钟频率；
- 所以把乘法器独立出来，与 ALU 树并行或分时工作。
6. 应用场景
多级 ALU 阵列不仅用于 GenDP，在很多领域都有应用：
6.1 动态规划加速器
- GenDP：BSW、PairHMM、POA、Chain 的目标函数；
- 其他 DP 加速器：如 DTW、Bellman-Ford 的硬件实现。
6.2 机器学习加速器
- TPU：矩阵乘法用脉动阵列 + 归约树；
- NPU：卷积、池化等操作需要多级归约；
- GPU：warp 内归约（reduction）用多级 ALU 树。
6.3 信号处理
- FFT：蝶形运算天然是多级结构；
- FIR/IIR 滤波器：乘积累加需要归约树；
- 音频/图像处理：卷积、池化等。
6.4 编译器与硬件综合
- HLS（High-Level Synthesis）：把 DFG 映射到多级 ALU 树；
- 指令调度：把无依赖的操作并行映射到多级 ALU。
6.5 通用处理器
- SIMD 单元：多个 ALU 并行；
- 超标量处理器：多个执行单元并行；
- VLIW 处理器：一条指令包含多个 ALU 操作。
7. 形象比喻
把多级 ALU 阵列想象成一个厨房：
- 1 级：只有一个灶台，每做一步菜都要把半成品端回冰箱（RF），下次再拿出来；
- 2 级：有三个灶台，第一级两个同时备料，第二级一个汇总。半成品直接在灶台间传递，不用频繁跑冰箱；
- 3 级：有七个灶台，但菜谱只需要两步，很多灶台闲着。
因此，2 级是“够用且高效”的选择。
8. 一句话总结
Multi-level ALU array 是把多个 ALU 组织成层级归约树的计算单元结构。
它的核心目的是减少寄存器文件访问，让中间结果在 ALU 之间直接传递。GenDP 选择 2 级 ALU 树（3 个 ALU），在 RF 访问、面积和利用率之间取得最佳平衡。这种结构广泛应用于 DP 加速器、机器学习加速器、信号处理、HLS 和通用处理器中。