2.7 DPMap Algorithm

第5节 DPMap Algorithm 是 GenDP 框架中非常关键的一环：它负责把 DP 目标函数的数据流图（DFG） 映射到 PE 内部的 计算单元（CU） 上，最终生成计算指令。简单说，DPMap 就像一个小型“编译器后端”，把算法层面的操作图，调度到有限的硬件执行单元上。

1. 为什么需要 DPMap？

在 GenDP 中，每个 DP kernel（BSW、PairHMM、POA、Chain）都有一个 目标函数，比如：

BSW：取最大值、加法、比较；
PairHMM：乘法、加法、取对数；
POA：类似 BSW，但依赖图结构；
Chain：乘法、加法、取最大值、查找表。

这些目标函数可以表示成一个 数据流图（DFG）：

节点：代表一个操作，比如加法、乘法、取最大值、比较；
边：代表数据依赖，比如节点 B 的输入来自节点 A 的输出；
父节点：提供输入的操作；
子节点：接收输出的操作。

而 PE 内部的计算单元（CU）并不是无限灵活的。论文第4.3节指出，CU 采用 2级 ALU reduction tree，结构大致是：

第一级：4 输入 ALU（可以执行加法、减法、最大值、最小值等）；
第二级：2 输入 ALU（用于归约）；
还有一个独立的乘法模块；
每个 CU 最多支持一个 4 输入操作或一个乘法操作。

因此，不能把整个 DFG 直接塞进一个 CU。必须把 DFG 划分成多个子图，每个子图都能映射到一个 CU 的 ALU 树上。DPMap 就是做这个划分的。

2. DPMap 的整体思路

DPMap 把整个 DFG 分成若干子图，每个子图包含：

要么一个乘法节点；
要么三个 ALU 节点（对应 2 级归约树）。

子图内部的边表示 CU 内部的数据移动；子图之间的边表示需要通过 寄存器文件（RF） 传递数据。DPMap 的目标是尽量减少 RF 访问，同时满足 CU 的结构约束。

划分过程分三步：

Partitioning（划分）：提取要映射到 4 输入 ALU 和乘法器的节点，移除相关边，必要时复制节点。
Seeding（播种）：找出适合第二级 ALU 的节点（种子），把它们和父节点分组。
Refinement（精化）：把剩余节点每两个一组，映射到 2 级 ALU 树。

下面逐一解释。

3. 第一步：Partitioning（算法1）

目的：把那些必须单独占用 CU 资源的节点（乘法、4 输入操作）分离出来，并切断它们与外部过多的连接，减少后续分组复杂度。

算法1 遍历 DFG 的所有节点 $v_i$ ：

如果 $v_i$ 是乘法节点：
- 移除它的所有输入边和输出边。
- 原因：乘法器是独立单元，不能和其他操作共享同一个 CU 的 ALU 树。它的输入输出必须通过寄存器文件传递。
如果 $v_i$ 是比较（Comparison）或匹配得分（MatchScore）节点：
- 移除它的输入边。
- 原因：这类节点通常要映射到 4 输入 ALU，输入操作数需要从寄存器文件取。
- 如果 $v_i$ $v_{i}$ 有多个子节点：
  - 对每个子节点 $v_j$ $v_{j}$ ：
    - 如果 $v_j$ 是减法（Subtraction），则移除 $v_i$ 的输出边。
    - 否则，复制 $v_i$ 。
  - 为什么？减法不满足交换律a - b ≠ b - a。移除输出边的含义：当 $v_j$ $v_{j}$ 是减法时，移除 $v_i$ $v_{i}$ 的输出边：
    - 切断 $v_i$ 和 $v_j$ 之间的直接连接；
    - $v_i$ 的值必须写入寄存器文件；
    - 减法 $v_j$ 从寄存器文件读取 $v_i$ 的值。

Comparison >  : out = in[0] > in[1] ? in[2] : in[3] 
Comparison == : out = in[0] == in[1] ? in[2] : in[3]
MatchScore    : out = scoretable(in[0], in[1])
S(X(i), Y(j)) = (X(i) == Y(j)) ? matchScore : mismatchScore

形象理解：Partitioning 就像把 DFG 中“大块头”节点（乘法、比较）单独拎出来，切断它们与周围节点的直接连线，让它们的数据通过寄存器中转。对于有多个孩子的可交换节点，复制一份，让每个孩子都有自己的“父亲”，避免排队等数据。

移除输入边的含义：切断 $v_i$ 与它父节点之间的直接连接，让 $v_i$ 的输入不再来自 CU 内部的其他 ALU，而是从寄存器文件读取。

4 输入 ALU 的操作数太多，无法全部来自 CU 内部。这些节点必须在同一个周期产生结果；通过从寄存器文件读取，每个操作数可以在不同周期加载，调度灵活。
4 输入 ALU 是稀缺资源，需要独立调度。
比较操作的语义需要明确的输入顺序
- 比较操作 in[0] > in[1] 对顺序敏感：
- in[0] 和 in[1] 不能互换；
- 如果输入来自 CU 内部，很难保证正确的顺序；
- 从寄存器文件读取，地址明确，顺序可控。

4. 第二步：Seeding（算法2）

目的：找出适合作为 2 级 ALU reduction tree 第二级输入的节点，称为“种子”（seed）。种子通常是有两个父节点的节点，因为第二级 ALU 正好有两个输入。

算法2 遍历所有节点：

如果节点 $v_i$ 有两个父节点：
- 移除 $v_i$ 的输出边（因为输出要存寄存器）。
- 对 $v_i$ $v_{i}$ 的每个父节点 $v_j$ $v_{j}$ ：
  - 移除 $v_j$ 的输入边（因为父节点的输入操作数要从寄存器取）。
- 这样， $v_i$ 和它的两个父节点就可以一起映射到一个 CU：两个父节点分别计算第一级 ALU 的结果，然后送入第二级 ALU（即 $v_i$ ）进行归约。
如果节点 $v_i$ 有多个子节点：
- 移除 $v_i$ 的输出边。
- 原因：输出会被多个子节点使用，必须存到寄存器，不能留在 CU 内部。

形象理解：Seeding 就像在 DFG 中找“汇合点”：两个父节点汇到一个子节点。这个子节点正好对应第二级 ALU，两个父节点对应第一级 ALU。把它们打包成一个 CU 子图。同时切断与外部过多的连线，让数据通过寄存器进出。

目的：经过前两步，剩下的节点大多只有一个父节点或一个子节点。Refinement 把它们每两个一组，映射到 2 级 ALU 树。

算法3 反向遍历 DFG（从最后一个节点到第一个）：

对于每个节点 $v_i$ $v_{i}$ ：
- 对于它的每个父节点 $v_j$ $v_{j}$ ：
  - 如果 $v_j$ $v_{j}$ 还有父节点（即 $v_j$ $v_{j}$ 有祖父）：
    - 移除 $v_j$ 的输入边。
    - 这样就把 $v_j$ 和它的父节点分开，使得每两个节点可以组成一个子图。

形象理解：Refinement 就像把剩下的零散节点两两配对。反向遍历是为了从输出端往输入端整理，确保每个节点都能找到合适的搭档，最终所有子图都能塞进 CU 的 2 级 ALU 树。

6. 用 BSW 的例子走一遍（Figure 9）

BSW 的目标函数包含：取最大值、加法、比较、匹配得分等。Figure 9 展示了 DPMap 的三步：

(a) 原始 DFG：一堆节点和边，表示 BSW 的完整计算。
(b) Partitioning：
- 节点 comp（比较）的输入边被移除；
- 因为 comp 有两个孩子，且孩子包含可交换操作，所以 comp 被复制成两个 comp 节点。
- 这样每个孩子都有自己的 comp，避免共享。
(c) Seeding：
- 找到有两个父节点的节点（种子），把它们和父节点分组；
- 移除种子的输出边，以及父节点的输入边。
(d) Refinement：
- 剩下两个 comp 节点，每两个一组，最终形成两个子图。
- 所有子图都能映射到 CU 的 2 级 ALU 树。

最终，DPMap 输出的是一个个子图，每个子图对应一条计算指令，在 PE 的 CU 上执行。

7. 为什么这样设计有效？

匹配硬件：CU 是 2 级 ALU 树，DPMap 把 DFG 划分成符合这个结构的子图。
减少寄存器访问：通过复制节点、移除边，尽量让数据在 CU 内部流动，而不是频繁读写寄存器文件。
支持多种 DP kernel：不同 kernel 的目标函数不同，但都可以表示成 DFG，DPMap 用同一套规则处理，实现可编程性。
生成 VLIW 指令：每个子图对应一条 VLIW 计算指令，充分利用 2-way VLIW 的并行性。

8. 一句话总结

DPMap 是一个图划分算法，它把 DP 目标函数的数据流图，按照 PE 内 2 级 ALU 树的结构，分成多个子图。
它分三步：Partitioning 分离乘法和大输入节点，Seeding 找双亲节点打包，Refinement 把剩余节点两两分组。最终每个子图映射到一个计算单元，生成计算指令，实现高效可编程的 DP 加速。

1. 为什么需要 DPMap？​

2. DPMap 的整体思路​

3. 第一步：Partitioning（算法1）​

4. 第二步：Seeding（算法2）​

5. 第三步：Refinement（算法3）​

6. 用 BSW 的例子走一遍（Figure 9）​

7. 为什么这样设计有效？​

8. 一句话总结​