Skip to main content

WFAA trackback pointer

在 TALCO-WFAA 中，traceback pointer 的形式和 TALCO-XDrop 类似，都是每个格子存一个很小的离散标签/位域，用来记录这个格子的最远 offset 是通过哪种状态和操作得到的。

但因为底层算法是 WFA-Adapt，它的递推状态和 X-Drop 不同，所以指针编码的内容也不同。

1. WFA-Adapt 的状态​

WFA-Adapt 支持 affine gap，每个格子 (s,K)(s, K) 需要维护多个状态：

状态含义
MM 或 HH匹配/错配状态
II插入状态（QQ 中有 gap）
DD删除状态（RR 中有 gap）

递推公式（论文中的 (4)–(7)）大致是：

Is,K=max⁡(Ms−o,K−1+1, Is−e,K−1+1)I_{s,K} = \max(M_{s-o,K-1}+1,\ I_{s-e,K-1}+1) Ds,K=max⁡(Ms−o,K+1, Ds−e,K+1)D_{s,K} = \max(M_{s-o,K+1},\ D_{s-e,K+1}) Xs,K=max⁡(Is,K, Ds,K, Ms−s,K+1)X_{s,K} = \max(I_{s,K},\ D_{s,K},\ M_{s-s,K}+1) Hs,K=Xs,K+LCP(Q[Xs,K−K, n−1], R[Xs,K, m−1])H_{s,K} = X_{s,K} + \text{LCP}(Q[X_{s,K}-K,\ n-1],\ R[X_{s,K},\ m-1])

最终每个格子存的是 Hs,KH_{s,K}，也就是匹配延伸后的最远 offset。

2. traceback pointer 需要记录什么？​

回溯时，从某个格子 (s,K)(s,K) 出发，需要知道：

  1. Xs,KX_{s,K} 是从 II、DD 还是 MM 来的？
  2. 如果是从 II 来的，II 是从 MM 打开 gap，还是从 II 延长 gap？
  3. 如果是从 DD 来的，DD 是从 MM 打开 gap，还是从 DD 延长 gap？

这些信息决定了回溯时：

  • 如果来自 MM，则这一步是匹配或错配；
  • 如果来自 II 且是打开，则这一步是插入，并且前一步在 MM；
  • 如果来自 II 且是延长，则这一步是插入，并且前一步还在 II；
  • DD 同理。

因此，每个格子的 traceback pointer 需要编码：

  • X 的来源状态：II、DD、MM 三选一，约 2 bits；
  • 如果来自 I：打开还是延长，1 bit；
  • 如果来自 D：打开还是延长，1 bit。

所以，和 TALCO-XDrop 类似，TALCO-WFAA 的 traceback pointer 也是 几个 bit 的位域，概念上是 3–4 bits 左右。具体位宽论文没有明确给出，但结构和 TALCO-XDrop 的 4-bit 指针非常相似，只是状态名称和转移规则换成了 WFA 的 affine gap 递推。

3. 存储形式​

在 TALCO-WFAA 硬件中：

  • Phase 1 的 compute 模块计算每个格子的 offset 和 traceback pointer；
  • 指针存到 SRAM；
  • 每个格子对应一个指针，按对角线和分数索引；
  • Phase 2 中不再存 traceback pointer，而是用 convergence pointer 替代，convergence pointer 是一个整数，指向 marker 上的格子，需要 log⁡2(Bmax⁡)\log_2(B_{\max}) 位。

所以，TALCO-WFAA 的 traceback pointer 就是：

每个三角矩阵格子一个紧凑的位域标签，编码该格子的最远 offset 是通过错配、插入、删除中的哪一种，以及 gap 是打开还是延长得到的。

它和 TALCO-XDrop 的 4-bit 指针在本质上相同：都是用来在回溯时决定下一步往哪个状态走。