Skip to main content

4.2 TALCO-XDrop not Convergence

如果没有收敛，TALCO 不会停下来等待，也不会直接出错，而是继续往后计算更多的 frontier，直到满足下面两个终止条件之一：

  1. 到达比对末尾；
  2. wavefront 长度超过硬件限制 BmaxB_{max}，触发回退 CPU。

下面分算法层面和硬件层面说明。

1. 算法层面：未收敛就继续推进​

回顾 Algorithm 1 的 Phase 2：

else
    ConvPrcurr ← redirect(Prf, ConvPrprev)
    if Clast was updated in the current tile then
        ConvPrlatt ← ConvPrcurr[Clast]
    end if
    if all pointers in ConvPrcurr point to a marker cell then
        C_tb ← Cx
        break
    else if f has reached the end of the alignment then
        C_tb ← ConvPrlatt
        break
    end if
    ConvPrprev ← ConvPrcurr
end if

如果 Reduction Tree 检测到没有收敛，那么：

  • all pointers ... point to a marker cell 为假；
  • 算法不会 break；
  • 执行 ConvPrprev ← ConvPrcurr；
  • 然后 j ← j + 1，Sprev ← Scurr，进入下一个 frontier；
  • 在新的 frontier 上重新计算 convergence pointer，再次检查是否收敛。

也就是说，未收敛只是意味着 Phase 2 还要多算几层，而不是失败。

2. 什么时候才会停止 Phase 2？​

Phase 2 只在以下情况结束：

情况 A：收敛了​

当前 frontier 上所有格子的 convergence pointer 都指向 marker 上的同一个格子 CxC_x。
此时：

Ctb=CxC_{tb} = C_x

然后跳出内层循环，开始回溯当前 tile。

情况 B：到达比对末尾​

如果一直不收敛，但已经算到了序列末尾，那么算法会检查：

else if f has reached the end of the alignment then
    C_tb ← ConvPrlatt
    break

这里 ConvPrlatt 是之前保存的、局部最大分格子 Clast 对应的 convergence pointer。
如果 Clast 在当前 tile 内更新过，就用它作为回溯起点。
对于全局比对，Clast 就是终点 (m,n)(m,n)；对于局部比对，Clast 是当前最大分格子。

所以，即使完全不收敛，到达末尾后仍然能确定一个正确的回溯起点。

3. 硬件层面：Reduction Tree 未收敛怎么办？​

在 TALCO-XDrop 加速器中：

  • 每个 PE 计算自己负责的格子的 convergence pointer；
  • Reduction Tree 检查当前 wavefront 的所有子集是否都指向 marker 上的同一个格子；
  • 如果收敛，就把那个格子的索引写入 Convergence Pointer SRAM，并通知 Traceback Logic；
  • 如果没有收敛，Reduction Tree 不会产生有效的 C_tb，硬件继续计算下一个 wavefront。

具体行为：

  1. 继续推进 wavefront
    硬件会继续让 PE 阵列计算下一个 frontier 的分数和 convergence pointer，再次送入 Reduction Tree 检测。

  2. 末尾检测
    硬件中有逻辑判断是否已经到达参考序列和查询序列的末尾。
    如果到达末尾仍未收敛，就使用之前保存的 Clast 或 ConvPrlatt 作为回溯起点。

  3. 超过 Bmax⁡B_{\max} 则回退
    如果某个 wavefront 的 cell 数超过硬件预设的 Bmax⁡B_{\max}，硬件无法继续处理。
    此时会返回一个 invalid flag，Host CPU 用软件重新算这个比对。
    这保证了正确性，但会牺牲一点吞吐。

所以，未收敛本身不会导致回退；只有 wavefront 太长才会回退。

4. 未收敛会影响什么？​

  • 不影响正确性：TALCO 仍然保证与完整 banded 算法结果一致。
  • 只影响效率：Phase 2 需要多算一些 frontier，这些 frontier 属于冗余计算，会在下一个 tile 中重算。
  • 收敛越快，效率越高：论文实测，低错误率时效率 95–97%，最差也超过 85%。
    如果一直不收敛，效率会下降，但不会出错。

5. 一句话总结​

如果 Reduction Tree 没有检测到收敛，TALCO 不会停止或报错，而是继续计算下一个 frontier，直到所有回溯路径汇聚到 marker 上同一个格子，或者到达比对末尾。到达末尾仍未收敛时，就用之前保存的局部最大分格子对应的 convergence pointer 作为回溯起点。如果 wavefront 超过硬件限制，则回退 CPU。未收敛只增加冗余计算，不影响结果正确性。