Skip to main content

4.4 TALCO-WFAA Accelerator Design

第四节里的 TALCO-WFAA Accelerator Design 讲的是：怎么把 TALCO 算法作用在 WFA-Adapt 上，做成硬件加速器。
它的目标和 TALCO-XDrop 一样：用固定的片上内存，加速任意长的序列比对，同时保证结果与软件 WFA-Adapt 一致。

但 WFA-Adapt 的计算模式和 X-Drop 很不一样，所以硬件结构也不同。下面按“整体思路 → 三大模块 → Phase 1 → Phase 2 → 回溯 → 与 WFA-FPGA 的区别 → 回退机制 → 总结”来讲解。

1. 整体思路：迭代执行 extend、reduce、compute​

WFA-Adapt 的三角矩阵按 分数 ss 逐行推进。
每一行对应一个 alignment score，列对应对角线 kk。
硬件要做的事情就是：

对每一行，先 extend（沿对角线匹配延伸），再 reduce（剪掉落后太多的对角线），最后 compute（计算下一行的最远到达位置和指针）。

TALCO-WFAA 把这个过程做成流水线：

  • NextN_{ext} 个 extend 模块：并行做匹配延伸。
  • NcompN_{comp} 个 compute 模块：并行计算下一行的 cell offset 和指针。
  • reduce 模块：做 WFA-Adapt 的剪枝。

图 8 展示了这个阵列。
每个 extend 和 compute 模块都配有一对 SRAM，用来存查询序列和参考序列，因为 WFA-Adapt 的访问模式不规则。

2. 数据表示与固定参数​

  • 序列还是用 3 bits 一个碱基 存 SRAM，字母表： σ∈{A,C,G,T,N}\sigma \in \{A, C, G, T, N\}
  • M：一个 tile 内从起点到 marker 的 wavefront 数，设计时固定。
  • BmaxB_{max}：一个 wavefront 最多能容纳多少 cell，设计时固定。
  • 如果某一行超过 BmaxB_{max}，硬件回退 CPU。
  • WFA-Adapt 的打分参数在设计时固定。论文里设为：
    • mismatch x=1x = 1
    • gap open o=2o = 2
    • gap extend e=1e = 1

因为 gap open 和 gap extend 不同，分数依赖会跨两行。
所以 TALCO 里 WFA-Adapt 的 frontier 由两行组成，这和 Levenshtein 距离下一行就够不同。

3. Phase 1：正常计算并存储 traceback 指针​

Phase 1 从 tile 起点算到 marker，任务和软件 TALCO 的 Phase 1 一样：

算分数、算指针、存指针。

3.1 extend 模块：沿对角线匹配延伸​

每个 extend 模块收到一个 cell offset 和三角矩阵中的 K 位置。
它从参考序列和查询序列的对应位置开始，逐个比较碱基，直到遇到不匹配。

为了加速，硬件会同时比较多个连续碱基，然后用一个 reduction tree 找出最早不匹配的位置。
这样就能快速算出这条对角线能免费延伸多远。

extend 返回一个新的 offset，表示匹配延伸后的位置。

3.2 reduce 模块：WFA-Adapt 剪枝​

所有 cell 的新 offset 算完后，reduce 模块启动。
它做的是 WFA-Adapt 的启发式剪枝：

把那些“落后太多”的外侧对角线丢掉。

具体来说，它根据新 offset 判断哪些 cell 离最远到达位置太远，然后剪掉。
另一个 reduction tree 用来确定新的边界：

kmax⁡′,kmin⁡′k_{\max}^{\prime}, \quad k_{\min}^{\prime}

这两个值存到专用 SRAM，供后续使用。

3.3 compute 模块：计算下一行​

compute 模块根据当前 frontier 和 WFA 的递推公式，计算下一行每个 cell 的最远到达 offset。
论文里用到的公式是 WFA 的 (4) 到 (7)，这里不需要完全展开，只要知道它做的是：

  • 从 Hi−1H_{i-1}、Ii−1I_{i-1}、Di−1D_{i-1}、Hi−2H_{i-2} 这些状态，算出新的 HsH_s、IsI_s、DsD_s；
  • 同时计算 traceback 指针；
  • 把指针存到 SRAM。

为了保存这些状态，硬件用了四组寄存器数组，分别对应：

Hi−1,Ii−1,Di−1,Hi−2H_{i-1}, \quad I_{i-1}, \quad D_{i-1}, \quad H_{i-2}

它们存的是每个 cell 的 offset。

这样，Phase 1 就正常地一行一行往前算，直到 marker。

4. Phase 2：传播 convergence pointer，检测收敛​

到达 marker 后，进入 Phase 2。
这时：

  • extend 和 reduce 模块照常工作；
  • compute 模块不再存 traceback 指针，而是计算 convergence pointer；
  • convergence pointer 存到寄存器 Hs−1H_{s-1}、Is−1I_{s-1}、Ds−1D_{s-1}、Hs−2H_{s-2} 中；
  • 不再使用 traceback pointer SRAM，节省内存。

convergence pointer 的作用和 TALCO-XDrop 一样：

表示当前 cell 的回溯路径，最终会落到 marker 上的哪个格子。

4.1 收敛检测​

一个 frontier 是两行。
硬件用一个 reduction tree 检查：

当前 frontier 上所有 cell 的 convergence pointer 是否都指向 marker 上的同一个格子？

  • 如果是，就判定 收敛。
  • 如果否，就继续算下一行。

和 TALCO-XDrop 一样，未收敛不会报错，只是继续往后算，直到收敛或到达序列末尾。

4.2 收敛后回溯​

一旦收敛，traceback logic 开始工作：

  • 用收敛点作为回溯起点；
  • 利用 SRAM 里存的 traceback 指针、kmax⁡k_{\max}、kmin⁡k_{\min} 等信息；
  • 逐步生成 compact CIGAR（紧凑的比对描述）。

如果一直不收敛，但已经到达序列末尾，那么就从 (m,n)(m,n) 开始回溯，其中 mm 和 nn 分别是参考序列和查询序列的长度。

生成的 compact CIGAR 会被送到 CPU 线程，再解包成完整的 CIGAR 输出。

5. 与 WFA-FPGA 设计的两点区别​

论文提到，TALCO-WFAA 参考了 WFA-FPGA [43]，但有两处不同：

  1. 状态存储方式
    WFA-FPGA 用 SRAM 来算下一 wavefront 的 offset；
    TALCO-WFAA 用专用寄存器来减少内存访问。
    这更适合 ASIC，因为寄存器访问更快、更省电；而 WFA-FPGA 的设计更偏向 FPGA。

  2. 并行度
    WFA-FPGA 有多个并行 extend 单元，但只有一个 compute 单元；
    TALCO-WFAA 同时并行使用 多个 extend 和多个 compute 单元，充分利用 WFA-Adapt 的并行性。

6. 回退机制：保证正确性​

和 TALCO-XDrop 一样：

  • 如果某个 wavefront 的长度超过硬件预设的 Bmax⁡B_{\max}，硬件无法处理；
  • 硬件返回 invalid flag；
  • Host CPU 用软件重新算这个比对。

这样虽然牺牲一点吞吐，但保证结果永远正确。

7. 一句话总结​

TALCO-WFAA 加速器把 WFA-Adapt 的计算拆成 extend、reduce、compute 三个步骤，用多个 extend 和 compute 模块并行执行。Phase 1 正常计算分数和 traceback 指针，存到 SRAM；到达 marker 后，Phase 2 让 compute 模块改为计算 convergence pointer，并用 reduction tree 检测所有回溯路径是否汇聚到 marker 上同一个格子。一旦收敛，就从该点回溯生成 compact CIGAR；若到末尾仍未收敛，就从 (m,n)(m,n) 回溯。如果 wavefront 超过 Bmax⁡B_{\max}，则回退 CPU。这样就在固定片上内存下，实现了任意长序列的 WFA-Adapt 加速，并保证与软件结果一致。