Skip to main content

2.1 Graph SIMD Smith-Waterman (GSSW)

GSSW 全称 Graph SIMD Smith-Waterman，是 Vg Map 中用于把短读段片段（约 100100 个碱基对）比对到泛基因组图上的一个动态规划内核。要理解它，可以分三层：先看线性 Smith-Waterman，再看 SIMD 加速，最后看图参考带来的变化。

1. 基础：线性 Smith-Waterman 在做什么​

Smith-Waterman 是一种经典的序列比对算法。它要填一个 n×mn \times m 的动态规划矩阵：

  • mm：查询序列长度，比如一条读段。
  • nn：参考序列长度，比如参考基因组的一段子串。

矩阵中每个单元格 (i,j)(i,j) 的分数，取决于它左边 (i,j−1)(i,j-1)、左上 (i−1,j−1)(i-1,j-1)、上边 (i−1,j)(i-1,j) 三个单元格的最大值。也就是说：

score(i,j)=max⁡(score(i,j−1), score(i−1,j−1), score(i−1,j))+匹配/错配分数\text{score}(i,j) = \max\big(\text{score}(i,j-1),\ \text{score}(i-1,j-1),\ \text{score}(i-1,j)\big) + \text{匹配/错配分数}

因为 (i,j)(i,j) 依赖 (i,j−1)(i,j-1)，所以按行计算时，同一行内必须从左到右串行。这不利于并行。

2. Farrar 算法：用 SIMD 打破行内依赖​

Farrar 提出一种“条带化”方法：他先猜测 (i,j−1)(i,j-1) 不是三个依赖中的最大值，于是可以先把一行中多个单元格打包进 SIMD 寄存器，同时计算。算完后检查猜测是否正确；如果猜错，再修正。

论文里举了一个字长为 33 的例子：同一颜色的单元格被打包进一个 SIMD 字，一次算多个格子。这样就把原本串行的行内计算，变成了 SIMD 并行。

所以 SIMD Smith-Waterman 的核心思想是：

用“先猜后修正”的方式，把动态规划矩阵中同一行的多个单元格并行计算。

3. 图版本：GSSW 把参考从“线”换成“图”​

线性 Smith-Waterman 的纵轴是一条线性参考序列。GSSW 的纵轴不是一条线，而是参考图的一个无环子图，并且按照拓扑排序排列。

具体来说：

  • 泛基因组图由节点和有向边组成。
  • Vg Map 会从种子命中位置周围，提取一个较小的无环子图。
  • 这个子图里的节点按拓扑顺序排列，节点内部是一段连续的参考序列。
  • 节点之间通过有向边连接。

计算时：

  • 节点内部：仍然可以用 SIMD Smith-Waterman，像线性版本一样，同一行多个单元格并行计算。
  • 节点的第一行：不能只看上一个节点，而要看所有父节点。因为一个节点可能有多个入边，来自多个父节点。
  • 所以节点第一行需要单独初始化：先收集所有父节点对应位置的分数，取最大值，再作为当前节点第一行的初始值。

论文里用红色箭头表示这种“父节点到当前节点第一行”的依赖。于是 GSSW 的计算模式变成：

在节点内部是密集的 SIMD 计算；到了节点边界，又要做间接的图访问，去合并父节点信息。两者交替出现。

这就是 GSSW 与线性 SSW 最大的不同：图结构引入了不规则的节点初始化步骤。

4. GSSW 的取舍：不算少，但算得整齐​

很多比对算法会用复杂的剪枝启发式，只计算动态规划矩阵中必要的单元格。但剪枝会让代码难以并行，有时还降低准确性。

GSSW 的选择是：

  • 计算比必要更多的单元格。
  • 保持算法简单、规整、可向量化。
  • 牺牲一些速度，换取高准确性和硬件加速友好性。

论文指出，GSSW 是“更慢，但高度准确”，因此是一个很好的硬件加速目标。

5. 性能特征：核心受限 + 内存受限​

论文对 GSSW 的微架构分析发现：

  • 它是核心受限的，因为动态规划计算密集，数据依赖复杂。
  • 它同时也是内存受限的，原因有两个：
    1. 它使用仿射间隙评分，这会让内存占用大约变成三倍。
    2. 它会把 SIMD 缓冲区写回动态规划矩阵，这个写回过程需要解包条带数据，局部性差。

和线性 SSW 相比，GSSW 的微架构比例几乎一样，但内存停顿大约多 33 倍。论文把来源定位到三行源代码：它们把用于分数计算的 SIMD 缓冲区写回 DP 矩阵。

另一个关键区别是：

  • 线性 SSW 中，第 ii 行只依赖第 i−1i-1 行，所以只需要保存上一行。
  • GSSW 中，第 ii 行可能访问它依赖的任意节点，所以它保存了整个 DP 矩阵的所有行。

但论文也观察到一个优化机会：在一个节点内部，行与行之间其实是线性依赖的，这些行并不需要全部存储。如果利用这一点，就可以避免昂贵的 SIMD 缓冲区到 DP 矩阵的写回，从而提升性能。

6. 一句话总结​

GSSW 是 Smith-Waterman 的图版本 + SIMD 加速版。它把参考从线性序列换成泛基因组图的拓扑排序子图：节点内部用 SIMD 并行填动态规划矩阵，节点边界则要合并多个父节点的信息。它计算量大但准确、规整、可向量化，代价是内存占用高、写回开销大，是泛基因组比对中一个典型的计算密集型内核。