Skip to main content

4. Traceback Engine

D. Traceback Engine 详细介绍​

这一节介绍了 Locus 架构中的 Traceback Engine（回溯引擎）。它的职责是：在 PE 阵列完成每个 gap 的波前比对（Wavefront Alignment, WFA）之后，读取本地 scratchpad 中的分数矩阵和方向指针，沿最优比对路径反向回溯，并把结果压缩成 CIGAR 字符串，最终写入 GLB 的 IR Bank，作为该 read 的最终映射结果。论文对它的描述非常简短，但它在整个融合流水线中扮演着“收尾”和“输出”的关键角色。

下面从功能定位、输入来源、工作流程、输出形式、并发执行和整体意义几个方面详细展开。

1. 功能定位：比对阶段的后处理与结果生成​

WFA 算法本身计算的是波前上的分数和 furthest-reaching offsets，并产生用于回溯的方向指针（traceback pointers），但它并不直接输出人类或下游工具可读的比对字符串。Traceback Engine 就是负责把 WFA 的中间结果转化为最终比对描述的硬件模块。

具体来说，它完成三件事：

  1. 读取：从本地 scratchpad 中读取某个 gap 的分数矩阵和方向指针。
  2. 回溯：从最优比对路径的终点开始，沿着方向指针反向走到起点，重建最优比对路径。
  3. 压缩与输出：把回溯路径压缩成 CIGAR 字符串，写入 GLB 的 IR Bank。

因此，Traceback Engine 是 Alignment（AL）阶段的最后一环，也是整个 S2G mapping 流水线中产生最终映射结果的模块。

2. 输入来源：本地 Scratchpad 中的 WFA 结果​

论文在 B 节提到，PE 阵列在 Mode 2（affine gap WFA）和 Mode 3（edit distance WFA）中，会把波前 DP 矩阵和方向指针存储在本地 scratchpad 中。本地 scratchpad 的组织分为五个逻辑区域，分别对应 WFA 矩阵类型，访问延迟只有 1 个周期，远低于 GLB 的 3 个周期。

当 PE 阵列完成一个 gap 的波前比对后，该 gap 的分数矩阵和方向指针就已经在本地 scratchpad 中就绪。Traceback Engine 直接从 scratchpad 读取这些数据，而不需要访问 DRAM 或 GLB。这保证了回溯过程的高带宽和低延迟，也符合融合执行“中间数据留在片上”的设计原则。

3. 工作流程：读取 → 回溯 → 压缩 → 写回​

Traceback Engine 的工作流程可以概括为四个步骤：

  1. 读取分数矩阵和方向指针
    从本地 scratchpad 中获取当前 gap 的 WFA 结果。方向指针记录了每个波前单元在最优路径上来自哪个方向，例如对角线（match/mismatch）、水平（insertion）或垂直（deletion）。

  2. 沿最优比对路径反向回溯
    从最优比对路径的终点开始，依据方向指针一步步反向走到起点。这个过程重建了查询序列与参考路径之间逐位或逐段的比对关系。

  3. 压缩成 CIGAR 字符串
    回溯得到的路径被压缩为 CIGAR（Concise Idiosyncratic Gapped Alignment Report）字符串。CIGAR 使用操作符和长度来描述比对，例如：

    • M：match 或 mismatch
    • I：insertion
    • D：deletion
      例如 10M2I5M3D 表示 10 个匹配/错配、2 个插入、5 个匹配/错配、3 个缺失。

  4. 写入 IR Bank
    最终的 CIGAR 字符串被写入 GLB 的 Intermediate Result (IR) Bank，作为该 read 的最终映射结果。论文在 A 节说明，IR Bank 保存链接分数和回溯指针，并最终保存比对结果；Traceback Engine 的输出正是写入这里。

4. 输出形式：CIGAR 字符串与 IR Bank​

CIGAR 字符串是 S2G mapping 的最终输出之一，它编码了查询序列如何比对到图路径上。对于下游的变异检测、基因分型等分析，CIGAR 是必不可少的输入。

论文在 Stage 5 中提到：“The output is a CIGAR string encoding matches, mismatches, insertions, and deletions.” Traceback Engine 正是产生这个输出的硬件单元。由于最终结果写入 IR Bank，它不需要立即写回 DRAM，而是可以与其他 tile 的结果一起批量输出，从而减少 off-chip 写流量。

5. 并发执行：与下一个 tile 的加载重叠​

论文特别强调：

“The traceback engine operates concurrently with the next tile’s load phase, so its latency is hidden behind DRAM prefetch for the subsequent tile.”

这意味着 Traceback Engine 的回溯和压缩过程并不是串行地阻塞整个流水线，而是与下一个 tile 的 Load 阶段并发执行。下一个 tile 的加载由 Tile Prefetch Engine (TPE) 通过 DMA 预取完成，包括从 DRAM 加载下一个 bin 的顶点序列和邻接表。由于 DRAM 预取本身有延迟，Traceback Engine 的计算正好可以隐藏在这段延迟之后。

这种设计带来两个好处：

  1. 提高吞吐：Traceback 的延迟不占用关键路径，PE 阵列可以继续处理后续 tile。
  2. 保持流水线连续：融合流水线 LC → GC → AL 可以持续运转，不会因为回溯而停顿。

在 bubble 密集区域，GPF 可能成为瓶颈，控制器会节流 PE 吞吐；但 Traceback Engine 仍然可以与加载阶段重叠，尽可能减少对整体性能的影响。

6. 在融合流水线中的意义​

Traceback Engine 虽然描述简短，但它是 Locus 融合执行闭环的最后一环：

  • 完成 AL 阶段：PE 阵列负责波前分数计算，Traceback Engine 负责把分数转化为可读的比对结果。
  • 保持片上数据流：它从本地 scratchpad 读，往 IR Bank 写，中间不经过 DRAM，符合 fusion 的核心思想。
  • 只输出最终结果：融合执行让 chain descriptors、path headers、WFA scratchpad 都留在片上；只有 anchors、topology（被 batch 分摊）和 CIGAR 输出会访问 DRAM。Traceback Engine 产生的 CIGAR 正是公式 (5) 中的 NgSoN_gS_o 项。
  • 与 TPE 协同：TPE 预取下一个 tile 的数据，Traceback Engine 同时处理当前 tile 的回溯，两者重叠，形成细粒度流水。

7. 与 PE 阵列、Local Scratchpad、GLB 的关系​

可以用一个简单的数据流来总结：

PE Array (WFA)→Local Scratchpad (score matrix + pointers)→Traceback Engine→IR Bank (CIGAR)\text{PE Array (WFA)} \rightarrow \text{Local Scratchpad (score matrix + pointers)} \rightarrow \text{Traceback Engine} \rightarrow \text{IR Bank (CIGAR)}
  • PE 阵列：执行 Mode 2 / Mode 3 的波前比对，产生分数和方向指针。
  • Local Scratchpad：临时存储波前 DP 矩阵，访问延迟 1 周期。
  • Traceback Engine：读取 scratchpad，回溯并压缩成 CIGAR。
  • IR Bank：GLB 中的中间结果 bank，保存最终 mapping result。

Traceback Engine 不直接与 DRAM 交互，也不参与链接阶段的计算，它专注于比对结果的最终生成。

8. 小结​

Traceback Engine 是 Locus 架构中负责比对结果后处理的硬件模块。它的核心行为是：

  • 在 PE 阵列完成每个 gap 的 WFA 后，
  • 从本地 scratchpad 读取分数矩阵和方向指针，
  • 沿最优路径反向回溯，
  • 压缩成 CIGAR 字符串，
  • 写入 GLB 的 IR Bank，
  • 并与下一个 tile 的 Load 阶段并发，将自身延迟隐藏在 DRAM 预取之后。

虽然论文对这一节的描述很短，但它是融合流水线不可或缺的收尾环节：没有它，WFA 的中间分数无法转化为最终映射结果；没有它的并发设计，回溯延迟可能暴露在关键路径上，降低整体吞吐。因此，Traceback Engine 与 PE 阵列、GPF、TPE 一起，构成了 Locus 高效 S2G 加速器的完整闭环。