Skip to main content

2.8 BSW DFG

在 GenDP 中，把 BSW 的目标函数转换为 数据流图（DFG），是 DPMap 算法的第一步。只有先画出 DFG，才能后续把它划分成适合 2 级 ALU 树的子图。下面我一步步讲解 BSW 目标函数如何变成 DFG。

1. 先写出 BSW 的目标函数​

BSW 计算一个单元格 (i,j)(i,j) 时，需要计算三个矩阵：H(i,j)H(i,j)、E(i,j)E(i,j)、F(i,j)F(i,j)。

典型的仿射 gap Smith-Waterman 公式是：

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)\} 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\} F(i,j)=max⁡{H(i,j−1)−go, F(i,j−1)−ge, 0}F(i,j) = \max\{H(i,j-1) - g_o,\ F(i,j-1) - g_e,\ 0\}

其中：

  • S(X(i),Y(j))S(X(i),Y(j))：匹配得分，由当前两个碱基决定；
  • gog_o：gap opening penalty；
  • geg_e：gap extension penalty；
  • H(i−1,j−1)H(i-1,j-1)、H(i−1,j)H(i-1,j)、H(i,j−1)H(i,j-1)、E(i−1,j)E(i-1,j)、F(i,j−1)F(i,j-1)：来自前一个波前的已知值。

这些值都是输入，而 H(i,j)H(i,j)、E(i,j)E(i,j)、F(i,j)F(i,j) 是输出。

2. 把每个操作变成 DFG 节点​

DFG 中：

  • 节点 = 一个操作，比如加法、减法、取最大值、比较、查表；
  • 边 = 数据依赖，表示某个节点的输出是另一个节点的输入；
  • 父节点 = 提供输入的操作；
  • 子节点 = 接收输出的操作。

按照上面的公式，逐个操作建节点：

2.1 匹配得分节点：comp​

S=score(X(i),Y(j))S = score(X(i), Y(j))
  • 操作：根据两个碱基查表或比较，得到匹配得分；
  • 输入：X(i)X(i)、Y(j)Y(j)；
  • 输出：SS；
  • 节点类型：论文中称为 comp（Comparison / MatchScore）。

2.2 加法节点：计算对角线候选​

A1=H(i−1,j−1)+SA_1 = H(i-1,j-1) + S
  • 操作：加法；
  • 输入：H(i−1,j−1)H(i-1,j-1) 和 SS；
  • 输出：A1A_1；
  • 父节点：H(i−1,j−1)H(i-1,j-1) 和 comp。

2.3 减法节点：计算 E 的候选​

A2=H(i−1,j)−goA_2 = H(i-1,j) - g_o A3=E(i−1,j)−geA_3 = E(i-1,j) - g_e
  • 操作：减法；
  • 输入：H(i−1,j)H(i-1,j) 和 E(i−1,j)E(i-1,j)；
  • 输出：A2A_2、A3A_3。

2.4 最大值节点：计算 E​

E(i,j)=max⁡{A2,A3,0}E(i,j) = \max\{A_2, A_3, 0\}
  • 操作：取最大值；
  • 输入：A2A_2、A3A_3、常量 0；
  • 输出：E(i,j)E(i,j)。

2.5 减法节点：计算 F 的候选​

A4=H(i,j−1)−goA_4 = H(i,j-1) - g_o A5=F(i,j−1)−geA_5 = F(i,j-1) - g_e
  • 操作：减法；
  • 输入：H(i,j−1)H(i,j-1)、F(i,j−1)F(i,j-1)；
  • 输出：A4A_4、A5A_5。

2.6 最大值节点：计算 F​

F(i,j)=max⁡{A4,A5,0}F(i,j) = \max\{A_4, A_5, 0\}
  • 操作：取最大值；
  • 输入：A4A_4、A5A_5、0；
  • 输出：F(i,j)F(i,j)。

2.7 最大值节点：计算 H​

H(i,j)=max⁡{0, A1, E(i,j), F(i,j)}H(i,j) = \max\{0,\ A_1,\ E(i,j),\ F(i,j)\}
  • 操作：取最大值；
  • 输入：0、A1A_1、E(i,j)E(i,j)、F(i,j)F(i,j)；
  • 输出：H(i,j)H(i,j)。

3. 连边，形成 DFG​

把上面的节点按数据依赖连起来：

H(i-1,j-1)  ──┐
              ├── A1 (Add) ──┐
comp (S) ─────┘              │
                             │
H(i-1,j) ──── A2 (Sub) ──┐   │
                         ├─ E (Max) ──┐
E(i-1,j) ──── A3 (Sub) ──┘            │
                                      │
H(i,j-1) ──── A4 (Sub) ──┐            ├─ H (Max) ── H(i,j)
                         ├─ F (Max) ──|
F(i,j-1) ──── A5 (Sub) ──┘            |
                                      │
0 ────────────────────────────────────┘

这就是 BSW 一个单元格的 DFG。

节点清单：

节点类型说明
comp比较/查表计算匹配得分 SS
A1加法H(i−1,j−1)+SH(i-1,j-1) + S
A2减法H(i−1,j)−goH(i-1,j) - g_o
A3减法E(i−1,j)−geE(i-1,j) - g_e
E最大值max⁡(A2,A3,0)\max(A2, A3, 0)
A4减法H(i,j−1)−goH(i,j-1) - g_o
A5减法F(i,j−1)−geF(i,j-1) - g_e
F最大值max⁡(A4,A5,0)\max(A4, A5, 0)
H最大值max⁡(0,A1,E,F)\max(0, A1, E, F)

4. 为什么 comp 节点会被复制？​

论文 Figure 9(b) 说：

节点 comp 的输入边被移除，一个 comp 节点被复制成两个 comp 节点，因为它们的子节点都有另一个父节点且包含可交换操作。

在 BSW 的 DFG 中，comp 节点（匹配得分 SS）可能被多个子节点使用。比如：

  • 在标准公式中，SS 只用于 A1A_1（加法）；
  • 但在某些 BSW 实现中，SS 可能同时用于 H 和 E/F 的计算，或者 comp 节点代表比较操作，其结果被多个地方引用。

当 comp 有多个子节点，且每个子节点除了 comp 之外还有另一个父节点，并且子节点的操作是可交换的（如加法、取最大值），DPMap 就会复制 comp 节点，让每个子节点都有自己的 comp 父节点。

为什么复制？

  • 如果不复制，多个子节点共享同一个 comp 父节点，那么 comp 的输出必须写入寄存器文件，再由多个子节点读取，增加 RF 访问。
  • 复制后，每个子节点都有自己的 comp，数据可以在 CU 内部直接流动，减少 RF 访问。
  • 复制是可交换操作允许的，因为加法、取最大值等操作满足交换律，复制不会改变结果。

在 BSW 例子中，Figure 9(b) 显示 comp 被复制成两个 comp 节点，每个子节点各配一个。

5. DFG 到 2 级 ALU 树的映射约束​

CU 的 2 级 ALU 树结构是：

第一级：   ALU1        ALU2
            \          /
第二级：        ALU3
                 |
               output

约束：

  • 第一级最多 2 个 ALU，每个可接收多个输入；
  • 第二级 1 个 ALU，接收第一级两个输出；
  • 每个 CU 最多一个 4 输入操作或一个乘法；
  • 乘法器独立。

所以 DFG 不能直接整个塞进一个 CU。必须切成子图，每个子图满足：

  • 最多两个第一级操作；
  • 一个第二级归约；
  • 边在子图内部表示 CU 内部数据移动；
  • 边跨子图表示需要寄存器文件传递。

DPMap 的三步就是做这个切分。

6. 用 Figure 9 走一遍​

  • (a) 原始 DFG：就是上面画的那张图，包含 comp、A1–A5、E、F、H 等节点。
  • (b) Partitioning：
    • comp 的输入边被移除；
    • comp 被复制成两个，因为它的子节点有多个，且操作可交换；
    • 乘法节点（如果有）的输入输出边被移除；
    • 4 输入节点的父边被移除。
    • 结果：所有节点最多两个父节点。
  • (c) Seeding：
    • 找有两个父节点的节点（如 E、F、H 这些 Max 节点），把它们和父节点分组；
    • 这些分组正好对应 2 级 ALU 树：父节点在第一级，Max 在第二级。
  • (d) Refinement：
    • 剩下的 comp 节点每两个一组，映射到 2 级 ALU 树；
    • 最终形成若干子图，每个子图对应一条 VLIW 计算指令。

7. 一句话总结​

把 BSW 目标函数变成 DFG，就是把公式中的每个操作（比较、加法、减法、取最大值）变成节点，把数据依赖变成边。
comp 节点因被多个子节点共享且操作可交换而被复制，以减少寄存器访问。DPMap 随后把这个 DFG 划分成多个子图，每个子图正好能映射到 CU 的 2 级 ALU 树：两个第一级操作加一个第二级归约。这样，BSW 的目标函数就能在 GenDP 的 PE 阵列上高效执行。