Skip to main content

2.9 BSW DPMap DFG subgraphs

论文中，CU（Compute Unit）采用 2 级 ALU reduction tree，而 DPMap 负责把 BSW 的数据流图（DFG）划分成能映射到这棵 2 级树上的子图。下面我分三步帮你理解：先看 2 级 ALU 树长什么样、有什么限制；再看 BSW 单元格的 DFG 大概是什么；最后看 DPMap 如何一步步把 DFG 切成符合 CU 结构的子图。

1. 2 级 ALU reduction tree 的结构与限制​

论文 Figure 7(d) 展示了 2 级 ALU 树的结构：

第一级：   ALU1        ALU2
            \          /
第二级：        ALU3
                 |
               output
  • 第一级有 2 个 ALU：每个 ALU 可以接收多个输入（通常是 4 输入），执行加法、减法、取最大值、最小值、比较等操作。
  • 第二级有 1 个 ALU：它接收第一级两个 ALU 的输出，再做一次归约（比如取最大值或相加）。
  • 乘法器独立：因为乘法延迟长，不放在 ALU 树里，单独作为一个单元。

所以，一个 CU 在一个周期内最多能完成：

  • 两个第一级操作；
  • 一个第二级归约操作；
  • 或者一个独立的乘法。

DPMap 的目标就是：把 BSW 的目标函数 DFG 切成若干个子图，每个子图恰好能塞进这样一棵 2 级 ALU 树。

2. BSW 单元格的目标函数 DFG​

BSW 在计算一个单元格 ( (i,j) ) 时，通常要算三个值：( H(i,j) )、( E(i,j) )、( F(i,j) )。它们互相依赖，但可以表示成一个 DFG。

简化一下，只看 ( H(i,j) ) 的计算：

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

其中 ( S(X(i),Y(j)) ) 是匹配得分。这个操作可以画成 DFG：

H_diag ──┐
          ├── Add ──┐
S ────────┘         │
0 ──────────────────┼── Max ── H(i,j)
E ──────────────────┤
F ──────────────────┘
  • S 节点：计算匹配得分（可能通过查表或比较，论文里称为 comp 节点）。
  • Add 节点：把 ( H_diag ) 和 S 相加。
  • Max 节点：从 0、Add 结果、E、F 中取最大值。

类似地，E 和 F 也有自己的小 DFG，比如：

E(i,j)=max⁡{H(i−1,j)−go, E(i−1,j)−ge, 0}E(i,j) = \max\{H(i-1,j) - g_o,\ E(i-1,j) - g_e,\ 0\}

也会产生减法、取最大值等节点。

整个 BSW 单元格的 DFG 包含多个操作节点，有些节点有多个父节点（比如 Max），有些节点有多个子节点（比如 S 可能同时给多个加法用）。

3. DPMap 如何把 DFG 划分成 2 级 ALU 子图​

DPMap 分三步：Partitioning（划分）、Seeding（播种）、Refinement（精化）。我们结合 BSW 的 DFG 来看。

3.1 Partitioning：分离“大块头”节点​

算法 1 遍历 DFG：

  • 遇到乘法节点：移除它的所有输入输出边。因为乘法器独立，不能和 ALU 树混用。
  • 遇到比较/匹配得分节点（comp）：移除它的输入边。
    • 如果 comp 有多个子节点，并且子节点包含可交换操作（加法、取最大值等），就复制 comp 节点。
    • 为什么？因为 comp 的结果要被多个子节点使用。如果只有一个 comp，多个子节点会争抢同一个父节点，导致数据必须通过寄存器文件传递。复制 comp 后，每个子节点都有自己的 comp 父节点，数据可以在 CU 内部直接流动，减少寄存器访问。

在 BSW 例子里，S（匹配得分）就是一个 comp 节点。它可能同时给多个加法用（比如 H 的计算和 E/F 的计算）。Partitioning 会把 S 复制成多个，每个加法配一个独立的 S 节点。

3.2 Seeding：找“汇合点”打包​

算法 2 找两类节点：

  • 有两个父节点的节点：这种节点很适合作为 2 级 ALU 树的第二级。因为第二级 ALU 正好有两个输入。
    • 例如，一个 Max 节点有两个父节点：Add 和 E。那么 Max 可以放在第二级，Add 和 E 分别放在第一级。
    • 算法会移除这个种子节点的输出边（因为输出要存寄存器），并移除它父节点的输入边（因为父节点的输入要从寄存器取）。这样，种子和它的两个父节点就打包成一个子图，正好映射到一个 2 级 ALU 树。
  • 有多个子节点的节点：移除它的输出边，因为输出要被多个子节点使用，必须存寄存器。

在 BSW 中，Max 节点通常有多个父节点（0、Add、E、F）。但 2 级树第二级只能处理两个输入，所以不能直接把 4 输入的 Max 放进去。DPMap 会先通过 Partitioning 和 Seeding 把 Max 拆解或分组，让每个子图的第二级最多两个输入。比如，可以先两两取最大值，再合并。

3.3 Refinement：剩余节点两两配对​

算法 3 反向遍历 DFG：

  • 如果某个节点还有父节点（即有祖父），就移除它父节点的输入边。
  • 这样做的目的是把剩下的节点每两个一组，映射到 2 级 ALU 树的第一级和第二级。

经过前两步，大部分复杂节点已经被分组，剩下的通常是比较简单的单父单子节点。Refinement 把它们两两配对，每个配对占用一个 CU 的第一级和第二级 ALU。

在 BSW 例子中，最后可能剩下两个 comp 节点（比如计算匹配得分的部分），它们被分别分到两个子图中，每个子图正好对应一个 2 级 ALU 树。

4. 用 Figure 9 的 BSW 例子走一遍​

论文 Figure 9 展示了 BSW 的 DPMap 过程：

  • (a) 原始 DFG：一堆节点和边，表示 BSW 单元格的完整计算。其中 comp 节点代表匹配得分计算，它连接到多个子节点。
  • (b) Partitioning：
    • 移除 comp 节点的输入边。
    • 因为 comp 有两个子节点，且子节点包含可交换操作，所以把 comp 复制成两个 comp 节点。
    • 这样每个子节点都有自己的 comp 父节点，数据流更独立。
  • (c) Seeding：
    • 找到有两个父节点的节点（种子），把它们和父节点分组。
    • 移除种子的输出边和父节点的输入边。
    • 这些分组对应 2 级 ALU 树：父节点在第一级，种子在第二级。
  • (d) Refinement：
    • 剩下两个 comp 节点，每两个一组，最终形成两个子图。
    • 每个子图都能映射到一个 CU 的 2 级 ALU 树。

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

5. 一句话总结​

CU 的 2 级 ALU 树限制了每个子图最多两个第一级操作和一个第二级归约。DPMap 通过 Partitioning 分离乘法和大输入节点、复制 comp 节点；通过 Seeding 把双亲节点和父节点打包成 2 级结构；通过 Refinement 把剩余节点两两配对。最终，BSW 的 DFG 被切成多个子图，每个子图正好塞进一个 2 级 ALU 树，实现高效可编程的 DP 计算。