2.4 Chain

论文 2.3 节中的 Chain 是长读测序（long-read sequencing）分析中的核心动态规划算法，主要用于 将种子匹配（seed pairs / anchors）连接成共线的重叠区域。它出现在长读比对、长读组装以及宏基因组分类等流程中，论文指出它在对应流程阶段中花费约 75% 的时间。

下面从背景、问题定义、原始算法、并行化挑战、重排序 Chain、计算特征以及 GenDP 加速几个方面详细解释。

---

1. Chain 要解决什么问题？

在长读测序中，reads 长度可达 10,000 bp 以上。直接用 Smith-Waterman 这类算法做全序列比对太慢。因此，实际流程通常分两步：

1. 种子匹配（seeding）：先在两条序列之间找到许多短的精确匹配片段，称为 seed pairs 或 anchors。每个 anchor 表示 read A 的某个位置和 read B 的某个位置匹配。
2. 链化（chaining）：这些 anchors 在两条序列上的位置可能杂乱无章，需要把它们按顺序连接起来，形成一条或多条 共线（collinear） 的链，表示两个 reads 之间的重叠区域。

Chain 算法就是做第 2 步：给定一组锚点，找出得分最高的共线锚点链。这条链就代表两个 reads 之间的一个重叠区域。

论文 2.3 节说：

Given a set of seed pairs (anchors) shared between a pair of reads, Chain aims to group a set of collinear seed pairs into a single overlap region.

也就是说，把一组共线的种子对分组到一个重叠区域中。

---

2. 锚点与共线性

每个锚点可以表示为：

$$(i, j, w)$$

其中：

• $i$：在 read A 上的位置；
• $j$：在 read B 上的位置；
• $w$：该锚点的权重（通常与匹配长度或质量有关）。

共线性意味着：如果锚点 A 在锚点 B 之前，那么它们在两条序列上的位置也应该保持相同顺序。即：

$$i_1 < i_2 \quad \text{且} \quad j_1 < j_2$$

Chain 的目标就是找一组满足共线性的锚点，使总得分最大。 得分通常包括锚点权重减去它们之间的 gap 惩罚。

---

3. 原始 Chain：1D 动态规划

Chain 使用一个 一维 DP 表。每个锚点按其在 read A 上的位置排序，然后依次计算每个锚点的最佳得分。

论文 2.3 节描述：

In the 1-Dimension DP table (Figure 2d(ii)), each anchor is compared with N previous anchors (default setting $N = 25$) to determine the best parent.

具体来说：

• 对于第 $j$ 个锚点，考虑它之前的 $N$ 个锚点（默认 $N=25$）；
• 对每个前驱锚点 $i$，计算从 $i$ 连接到 $j$ 的得分： $$score(i) + weight(i,j)$$
• 取最大值作为 $j$ 的得分，并记录最佳前驱（parent）。

递推式大致为：

$$score(j) = \max_{i < j,\ j-i \le N} \left( score(i) + weight(i,j) \right)$$

其中 $weight(i,j)$ 表示从锚点 $i$ 到锚点 $j$ 的转移得分，通常与两个锚点之间的 gap 有关。

这样，最终得分最高的锚点链就是最佳重叠区域。

Figure 2d(i) 展示了锚点链化的示意：多个锚点被连接成一条共线链。

---

4. 并行化挑战

原始 Chain 的依赖模式是：

• 锚点 $j$ 依赖它之前的 $N$ 个锚点；
• 计算必须按锚点顺序进行，因为后面的锚点需要前面锚点的得分。

这种 前向依赖 导致很难并行化。每个锚点必须等待它前面的锚点计算完成，才能开始计算。对于长读测序，锚点数量可能达到数万，串行计算成为瓶颈。

论文说：

However, the dependency between neighboring anchors poses difficulties for parallelism.

---

5. 重排序 Chain（Reordered Chain）

为了并行化，论文提到 reordered Chain algorithm [28]。它的核心思想是 反转比较方向：

• 原始：每个锚点 $j$ 与它前面的 $N$ 个锚点比较，确定最佳前驱；
• 重排序：每个锚点 $i$ 与它后面的 $N$ 个锚点比较，并更新这些后续锚点的得分。

也就是说，对于每个锚点 $i$，主动去更新它后面的 $N$ 个锚点 $j$：

$$score(j) = \max(score(j),\ score(i) + weight(i,j))$$

这样，所有锚点都可以作为“源”并行地更新后续锚点。虽然最终仍需同步，但并行度大大提高。

论文 Figure 2d(iii) 展示了重排序后的锚点依赖：每个锚点与后续 $N$ 个锚点比较。

不过，重排序会带来额外计算。论文评估部分提到：

The GPU baseline and GenDP both apply the reordered Chain (Section 2.3) with $N = 64$ in order to best utilize the parallelism and avoid large overhead of branches, thus computing $3.72\times$ more cells than the CPU baseline.

也就是说，为了充分利用并行性并避免分支开销，GPU 和 GenDP 使用 $N=64$，而 CPU 基线默认 $N=25$。因此计算了大约 $64/25 \approx 2.56$ 倍的单元格，再加上其他因素，最终报告为 $3.72\times$ 更多的单元格。为了公平比较，论文将 GPU 和 GenDP 的吞吐率除以 $3.72$ 进行归一化。

论文还验证了重排序 Chain 的精度与原始 Minimap2 相当（Table 6）：

指标	Minimap2	Reordered Chain (N=64)
Map failure or error	0.2476%	0.2479%
Phred quality score of low quality map Q < 10	54.36	54.14

可见精度损失很小。

---

6. Chain 的计算特征

论文 Table 1 给出 Chain 的特征：

特征	值
维度	1D DP 表
大小	约 20,000
依赖	最后 $N$（约 25）个锚点
精度	32-bit 整数 / 浮点

解释：

• 1D DP 表：因为锚点已经按顺序排列，只需要一维数组存储每个锚点的得分；
• 大小约 20,000：长读测序中锚点数量很多；
• 依赖最后 $N$ 个锚点：每个锚点只与前面（或后面）$N$ 个锚点比较，默认 $N=25$；
• 32-bit 整数或浮点：得分可能较大，权重和 gap 惩罚可能需要浮点。

---

7. GenDP 如何加速 Chain？

GenDP 的 DPAx 架构通过以下方式支持 Chain：

7.1 1D DP 表映射到大型 PE 阵列

论文 3.1 节描述了 1D DP 表的映射：

• 多个小 PE 阵列可以连接成一个大 PE 阵列，包含 64 个 PE；
• 每个时间步，单元格（锚点）被映射到 PE 上；
• 数据在 PE 之间向前流动，类似 systolic 流水线；
• FIFO 用于传递依赖数据。

具体例子：

• 第一个时间步，单元格 #1–8 映射到 PE；
• 它们都依赖单元格 #0，所以 #0 的值从 FIFO 加载到每个 PE；
• 下一个时间步，单元格 #2–8 向前移动，单元格 #9 进入第一个 PE，#1 移出最后一个 PE；
• 同时，#1 被加载到 FIFO，因为 #2–9 都依赖 #1。

这种设计使得 Chain 的 1D 依赖可以高效地在 PE 阵列中流水化。

7.2 重排序 Chain 的并行性

GenDP 采用重排序 Chain，$N=64$，以充分利用 PE 阵列的并行性。每个锚点可以并行地更新后续锚点，PE 阵列同时处理多个锚点。

7.3 控制与计算解耦

DPAx 将控制指令和计算指令分开。对于 Chain，控制线程管理数据在 PE 之间的移动和 FIFO 的读写，计算线程执行得分更新和最大值操作。

7.4 精度支持

Chain 需要 32-bit 整数或浮点。DPAx 有整数 PE 阵列和浮点 PE 阵列，可以支持 Chain 的精度需求。论文提到 Chain 还使用了一个特殊的 Lookup Table (LUT) 指令，而 RISC-V 和 x86-64 分别需要 14 和 7 条指令才能实现同样的 LUT。

---

8. 性能表现

论文 Table 11 显示 Chain 的 VLIW 利用率约为 38.3%，在四个 kernel 中处于中等水平。

论文 Table 15 显示，Chain 上 GenDP 相对 CPU 加速 63.7×，相对 GPU 加速 281.4×。这是四个 kernel 中相对 GPU 加速最高的，部分原因是 GPU 基线也应用了重排序 Chain 并计算了更多单元格，而 GenDP 的 PE 阵列和 FIFO 设计非常适合 1D 流水线。

论文 7.2 节指出：

In the Chain kernel, both performances of GPU and GenDP are penalized by $3.72\times$ for the extra cell computation.

也就是说，Chain 的加速比已经考虑了重排序带来的额外计算，进行了公平归一化。

---

9. Chain 与其他 kernel 的对比

Kernel	维度	依赖	精度	在流程中的作用
BSW	2D	最后 2 波前	8/16-bit 整数	read alignment
PairHMM	2D	最后 2 波前	浮点	variant calling
POA	2D	图结构、长距离	32-bit 整数	组装抛光
Chain	1D	最后 $N$ 个锚点	32-bit 整数/浮点	长读重叠、组装、宏基因组分类

Chain 的独特之处：

• 唯一的一维 DP 表；
• 依赖固定数量的前驱/后继锚点；
• 原始算法串行，重排序后可并行；
• 需要处理大量锚点（约 20,000）；
• 是长读测序中耗时最多的步骤之一。

---

10. 一句话理解 Chain

Chain 是一种一维动态规划算法，用于把两个长读之间共享的种子锚点连接成共线的重叠区域。
原始算法按顺序依赖前 $N$ 个锚点，难以并行；重排序 Chain 让每个锚点主动更新后续 $N$ 个锚点，从而实现并行。GenDP 利用大型 PE 阵列和 FIFO 流水线，高效地支持 Chain 的 1D DP 计算，在考虑额外计算量的归一化后，仍取得显著的加速。