WFAA convergence pointer

在 TALCO-WFAA 的 Phase 2 中，compute 模块不再存储 traceback pointer，而是计算并存储 convergence pointer。这些 convergence pointer 被存放在四组寄存器中：

$$H_{s-1},\quad I_{s-1},\quad D_{s-1},\quad H_{s-2}$$

为什么需要这四组？原因在于 WFA-Adapt 的仿射 gap 递推依赖关系。下面详细解释。

---

1. WFA-Adapt 的状态与依赖

WFA-Adapt 使用仿射 gap 罚分：

• gap open 罚分 $o$
• gap extend 罚分 $e$

每个格子 $(s,K)$ 需要维护多个状态：

• $M_{s,K}$（或 $H_{s,K}$）：匹配/错配状态的最远 offset
• $I_{s,K}$：插入状态
• $D_{s,K}$：删除状态

递推公式（论文 (4)–(7)）表明：

$$I_{s,K} = \max\{M_{s-o,K-1}+1,\ I_{s-e,K-1}+1\}$$ $$D_{s,K} = \max\{M_{s-o,K+1},\ D_{s-e,K+1}\}$$ $$X_{s,K} = \max\{I_{s,K},\ D_{s,K},\ M_{s-1,K}+1\}$$ $$H_{s,K} = X_{s,K} + \text{LCP}$$

从公式可以看出，计算第 $s$ 行的状态，需要用到：

• 第 $s-1$ 行的 $I$、$D$、$M$（即 $H$）
• 第 $s-2$ 行的 $M$（即 $H$），因为 gap open 罚分 $o$ 通常大于 1（论文中 $o=2$）

所以，第 $s$ 行依赖于 s-1 行的 H、I、D，以及 s-2 行的 H。

---

2. Phase 2 中 convergence pointer 的传播

在 Phase 1 中，每个格子计算 traceback pointer，并存储到 SRAM。
在 Phase 2 中，不再存储 traceback pointer，而是计算 convergence pointer：

当前格子的 convergence pointer = 它回溯到的前驱格子的 convergence pointer

这个“前驱格子”取决于当前格子的 traceback 来源：

• 如果来自 $I$ 状态，则前驱是 $I_{s-1}$（或 $I_{s-e}$，但 $e=1$ 时就是 $s-1$）
• 如果来自 $D$ 状态，则前驱是 $D_{s-1}$
• 如果来自 $M$ 状态，则前驱是 $H_{s-1}$ 或 $H_{s-2}$（取决于 gap open 罚分 $o$）

因此，为了传播 convergence pointer，必须为每个状态保存前一行的 convergence pointer。
这就是四组寄存器的由来：

寄存器	保存的 convergence pointer
$H_{s-1}$	第 $s-1$ 行匹配/错配状态的 convergence pointer
$I_{s-1}$	第 $s-1$ 行插入状态的 convergence pointer
$D_{s-1}$	第 $s-1$ 行删除状态的 convergence pointer
$H_{s-2}$	第 $s-2$ 行匹配/错配状态的 convergence pointer

当计算第 $s$ 行的某个格子的 convergence pointer 时，硬件根据它的 traceback 来源，从对应的寄存器中取出前驱的 convergence pointer，赋给当前格子。

---

3. 为什么不是 traceback pointer？

Phase 2 的目标是找到所有回溯路径的汇聚点 $C_x$，而不是重建完整比对。
因此不需要存储每步的方向，只需要知道“沿回溯路径最终会落到 marker 的哪个格子”。
这个信息就是 convergence pointer，它本身就是一个指向 marker 格子的索引。
为了传播这个索引，只需要保存前一行的 convergence pointer，而不是 traceback pointer。

---

4. 为什么是四组而不是三组？

如果 gap open 罚分 $o=1$，那么第 $s$ 行只依赖第 $s-1$ 行，三组寄存器（$H_{s-1}$、$I_{s-1}$、$D_{s-1}$）就够了。
但论文中设置 $o=2$，所以 $M_{s-o,K}$ 就是 $M_{s-2,K}$，需要额外一组 $H_{s-2}$ 来保存第 $s-2$ 行的匹配状态 convergence pointer。

因此，四组寄存器是由仿射 gap 参数决定的，具体是 $o=2, e=1$ 时的依赖关系。

---

5. 一句话总结

在 TALCO-WFAA 的 Phase 2 中，convergence pointer 需要沿着回溯路径传播。由于 WFA-Adapt 的仿射 gap 递推依赖第 $s-1$ 行的 $H$、$I$、$D$ 以及第 $s-2$ 行的 $H$，所以必须用四组寄存器分别保存这些前驱状态的 convergence pointer，以便当前行根据 traceback 来源继承正确的值。