Skip to main content

**Convergence Pointer

show how

Convergence pointer 的寻找过程，本质上是让“标记上每个格子的身份”沿着回溯路径一层层往前传播，直到所有路径都携带同一个身份。 下面以 TALCO-XDrop 为例，把整个过程拆开讲清楚。

1. 先理解 convergence pointer 是什么​

在 TALCO 中，marker 是一个特殊的 frontier，记作 fMf_M。
Marker 上最多有 Bmax⁡B_{\max} 个格子。

Convergence pointer 是每个格子的一个“身份标签”，它回答：

从这个格子沿 traceback 往回走，最终会落到 marker 上的哪个格子？

比如：

  • 某个格子的 convergence pointer = 5；
  • 意思是：它回溯到 marker 时，会经过 marker 上编号为 5 的那个格子。

所以 convergence pointer 不是指针方向，而是一个指向 marker 格子的索引，用 log⁡2(Bmax⁡)\log_2(B_{\max}) 位表示。

2. 初始化：marker 上的每个格子先指向自己​

当算法到达 marker 时：

if j - i = M - 1 then
    ConvPrprev ← 为 Scurr 中每个 cell 分配唯一 id
    Smarker ← Scurr
end if

此时 Scurr 就是 marker frontier 的分数。
对 marker 上的每个格子，给它一个唯一 id：

  • 格子 0 → id = 0
  • 格子 1 → id = 1
  • 格子 2 → id = 2
  • …

然后 ConvPrprev 就是：

ConvPrprev[0] = 0
ConvPrprev[1] = 1
ConvPrprev[2] = 2
...

意思是：marker 上的每个格子，目前只知道自己指向自己。
这是传播的起点。

3. 传播：redirect 函数​

进入 Phase 2 后，每推进一个 frontier，就做一次：

ConvPrcurr ← redirect(Prf, ConvPrprev)

redirect 做的事情是：

对当前 frontier 的每个格子，看它的 traceback pointer 指向上一 frontier 的哪个格子，然后继承那个格子的 convergence pointer。

用公式表示：

ConvPrcurr[i]=ConvPrprev[Prf[i]]\text{ConvPrcurr}[i] = \text{ConvPrprev}[\text{Prf}[i]]

其中：

  • Prf[i]：当前 frontier 第 ii 个格子的 traceback pointer；
  • 它指向上一 frontier 的某个格子；
  • ConvPrprev[那个格子]：那个格子已经携带的 marker 身份；
  • 把这个身份赋给当前格子。

这样，marker 的身份就沿着回溯路径，一层一层往前传播。

4. 一个具体例子​

假设 marker 上有 3 个格子，编号 0、1、2。

初始化​

ConvPrprev = [0, 1, 2]

第一个 frontier 之后​

假设当前 frontier 有 3 个格子 A、B、C：

  • A 的 traceback pointer 指向 marker 的格子 1；
  • B 的 traceback pointer 指向 marker 的格子 1；
  • C 的 traceback pointer 指向 marker 的格子 2。

那么：

ConvPrcurr[A] = ConvPrprev[1] = 1
ConvPrcurr[B] = ConvPrprev[1] = 1
ConvPrcurr[C] = ConvPrprev[2] = 2

结果：

ConvPrcurr = [1, 1, 2]

还没收敛，因为不是所有值都相同。

第二个 frontier 之后​

假设新的 frontier 有 D、E、F：

  • D 的指针指向 A；
  • E 的指针指向 B；
  • F 的指针指向 C。

那么：

ConvPrcurr[D] = ConvPrcurr[A] = 1
ConvPrcurr[E] = ConvPrcurr[B] = 1
ConvPrcurr[F] = ConvPrcurr[C] = 2

结果还是：

ConvPrcurr = [1, 1, 2]

第三个 frontier 之后​

假设 G、H、I：

  • G 的指针指向 D → 1
  • H 的指针指向 E → 1
  • I 的指针指向 E（而不是 F）→ 1

那么：

ConvPrcurr = [1, 1, 1]

所有值都等于 1，收敛了。
此时 Cx=1C_x = 1，也就是 marker 上编号为 1 的那个格子。
TALCO 就令：

Ctb=Cx=1C_{tb} = C_x = 1

然后从这个格子开始回溯当前 tile。

5. 怎么判断收敛？​

判断条件很简单：

当前 frontier 上所有格子的 convergence pointer 是否都等于同一个值？

  • 如果是，就收敛，取这个值为 CxC_x；
  • 如果不是，就继续推进。

在硬件中，这个判断由 Reduction Tree 完成。
它把当前 frontier 上所有格子的 convergence pointer 收集起来，检查是否全部相同。

6. 为什么这样传播是正确的？​

关键在于 traceback pointer 的依赖关系。

在 X-Drop 中，frontier fjf_j 包含两条相邻 wavefront WjW_j 和 Wj+1W_{j+1}。
任何从 fj+1f_{j+1} 出发的 traceback 路径，必然经过 fjf_j 上的某个格子。
所以：

  • 如果 fjf_j 上所有格子的 convergence pointer 都指向 marker 上的 CxC_x；
  • 那么从 fj+1f_{j+1} 往后任何格子出发的回溯路径，都会经过 fjf_j 上某个格子；
  • 那个格子的 convergence pointer 是 CxC_x；
  • 所以整条回溯路径必然经过 CxC_x。

这就是为什么一旦收敛，CxC_x 就是所有后续路径的必经点。

7. 特殊情况​

情况 A：一直不收敛​

如果 Phase 2 一直不收敛，但已经到达序列末尾：

C_tb ← ConvPrlatt

ConvPrlatt 是之前保存的、局部最大分格子 Clast 对应的 convergence pointer。
对于全局比对，Clast 是终点 (m,n)(m,n)；对于局部比对，Clast 是当前最大分格子。
所以即使没有收敛，也能用这个值作为回溯起点。

情况 B：局部最大分在收敛前更新​

if Clast was updated in the current tile then
    ConvPrlatt ← ConvPrcurr[Clast]
end if

这保证局部比对的最大分格子对应的 convergence pointer 被保存下来，以备后用。

8. WFA-Adapt 中的区别​

在 TALCO-WFAA 中：

  • frontier 是两行，不是两条 wavefront；
  • 但 convergence pointer 的传播逻辑一样：
    • marker 上的格子先指向自己；
    • 每推进一行，用 traceback pointer 继承上一行的 convergence pointer；
    • 检查所有 convergence pointer 是否相同；
    • 相同则收敛。

区别只在于 frontier 的定义和 traceback pointer 的编码方式，传播机制是相同的。

9. 一句话总结​

Convergence pointer 的寻找过程是：marker 上的每个格子先获得唯一 id；然后每推进一个 frontier，每个格子根据它的 traceback pointer 继承上一 frontier 对应格子的 id；这样 marker 的身份就沿着回溯路径一层层传播；当当前 frontier 上所有格子的 id 都相同时，就找到了收敛点 CxC_x，它就是当前 tile 的安全回溯起点 CtbC_{tb}。