Skip to main content

4.1 TALCO-XDrop Accelerator Design

第四节 TALCO-XDrop Accelerator Design 讲的是：怎么把 TALCO 算法（作用在 X-Drop 上）做成硬件加速器。
核心目标是：用固定的片上内存，加速任意长的序列比对，同时保证结果和不做 tiling 的 X-Drop 完全一致。

下面按“整体架构 → 计算流程 → Phase 1 → Phase 2 → 回溯 → 回退机制 → 一句话总结”来讲解。

1. 整体位置：协处理器 + Host CPU​

论文图 6 展示了整体结构：

  • Host CPU：负责发任务、收结果。
  • Controller：连接 Host 和多个 TALCO-Align 单元。
  • 多个 TALCO-Align 单元：并行执行比对。
  • Device Memory：存放序列和最终结果。

Host CPU 把一对对序列的地址发给 TALCO-Align 单元。
每个单元独立算一个比对。

如果某个比对因为 wavefront 长度超过硬件限制 而失败，硬件会返回一个 invalid flag，Host CPU 就用软件重新算这个比对。
这样虽然会慢一点，但保证了结果正确。

2. TALCO-XDrop 单元内部结构​

图 7a 是 TALCO-XDrop 阵列的硬件设计，关键部件有：

  • PE 阵列：一组处理单元，按 systolic 方式排列。
  • FIFO：暂存上一 stripe 最后一行的 H 和 D 值。
  • Traceback Pointer SRAM：每个 PE 专用，存 traceback 指针。
  • Start/Stop SRAM：存每个 stripe 的起止位置。
  • Reduction Tree：判断多个 PE 算出的 convergence pointer 是否收敛到同一个格子。
  • Convergence Pointer SRAM：存每个 wavefront 的收敛结果。
  • Traceback Logic：从收敛点或最大分点开始回溯。
  • 寄存器 H_max、H_max'：跟踪最大分数。

你可以把它理解成一条流水线：

PE 阵列负责算分数和指针 → SRAM 存下来 → Reduction Tree 检测收敛 → Traceback Logic 回溯 → 输出给软件。

3. 数据表示与参数​

  • 序列用 3 bits 一个碱基 存 SRAM，支持扩展 DNA 字母表： σ∈{A,C,G,T,N}\sigma \in \{A, C, G, T, N\} 其中 NN 表示模糊字符。
  • M：一个 tile 内从起点到 marker 的 wavefront 数，设计时固定。
  • B_max：一个 wavefront 最多能容纳多少个 cell，设计时固定。
  • 如果某个 wavefront 超过 Bmax⁡B_{\max}，硬件回退 CPU。
  • 打分参数可以运行时传入：
    • 替换矩阵 WW
    • gap open 罚分 oo
    • gap extend 罚分 ee

4. 计算流程总览​

TALCO-XDrop 的硬件计算和软件 TALCO 一一对应：

软件 TALCO硬件 TALCO-XDrop
Phase 1：算分数，存 traceback 指针PE 阵列算分，指针存 SRAM
到达 marker用寄存器标记
Phase 2：传播 convergence pointerPE 做 pointer redirection，Reduction Tree 检测收敛
收敛后确定 CtbC_{tb}Convergence Pointer SRAM 存结果
回溯当前 tileTraceback Logic 从 CtbC_{tb} 回溯
下一个 tile 用 marker 分数初始化FIFO / SRAM 保存 marker 分数

5. Phase 1：正常算分、存指针​

5.1 PE 阵列怎么算？​

X-Drop 是按 wavefront（反对角线） 推进的。
硬件把 wavefront 切成一条条 stripe，每个 stripe 有 NPEN_{PE} 行。
图 7 的例子中 NPE=4N_{PE} = 4。

每个 PE 负责计算一部分格子，公式就是 Needleman-Wunsch + affine gap：

Ii,j=max⁡{Hi,j−1−o,Ii,j−1−e}I_{i,j} = \max \{H_{i,j-1} - o, I_{i,j-1} - e\} Di,j=max⁡{Hi−1,j−o,Di−1,j−e}D_{i,j} = \max \{H_{i-1,j} - o, D_{i-1,j} - e\} Hi,j=max⁡{Ii,j,Di,j,Hi−1,j−1+W(Ri,Qj)}H_{i,j} = \max \{I_{i,j}, D_{i,j}, H_{i-1,j-1} + W(R_i, Q_j)\}

其中：

  • II：插入状态
  • DD：删除状态
  • HH：最终分数
  • WW：匹配/错配分数

每个格子还会生成一个 traceback 指针，共 4 bits：

  • 2 bits 表示 HH 是从 II、DD 还是对角线来的；
  • 1 bit 表示 II 的方向；
  • 1 bit 表示 DD 的方向。

这样回溯时才能知道每一步怎么走。

5.2 X-Drop 剪枝怎么实现？​

硬件维护一个运行中的最大分数 Hmax⁡H_{\max}。
当某一列所有格子的分数都低于：

Hmax⁡−XH_{\max} - X

就停止这个 stripe，后面的格子不再计算。
这就是 X-Drop 的剪枝，图 7 中白色的“未计算区域”就是被剪掉的。

5.3 跨 stripe 怎么衔接？​

一个 stripe 算完后，最后一行的 HH 和 DD 值存入 FIFO。
下一个 stripe 需要这些值来继续算。
如果上一 stripe 的某些值没算，就初始化为 −∞-\infty。

5.4 指针存哪里？​

Phase 1 的 traceback 指针存到每个 PE 专用的 SRAM bank。
另外，每个 stripe 的起始和结束位置也存到额外 SRAM，因为 X-Drop 的边界随 XX 变化，回溯时要用。

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

到达 marker 后，进入 Phase 2。
这时 不再存 traceback 指针，而是计算 convergence pointer。

6.1 pointer redirection​

每个 PE 根据当前格子的 traceback 指针，找到它在上一 frontier 对应的格子，然后继承那个格子的 convergence pointer。
这样，convergence pointer 就沿着回溯路径一层一层往 marker 方向传播。

6.2 Reduction Tree 检测收敛​

一个 wavefront 被多个 PE 分成若干子集。
每个 PE 算出一个 convergence pointer，表示“我这个格子的回溯路径最终会落到 marker 上的哪个格子”。

Reduction Tree 会检查：

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

  • 如果是，就在 Convergence Pointer SRAM 里存下那个格子的索引，按当前 wavefront 索引寻址。
  • 如果不是，就存 −1-1，表示还没收敛。

当所有子集的指针都相同，就判定 收敛。

6.3 收敛后还要做什么？​

收敛后，硬件继续算分，直到：

Hmax⁡′>Hmax⁡H_{\max}^{\prime} > H_{\max}

这里 Hmax⁡′H_{\max}^{\prime} 是 Phase 2 中看到的最大分数。

  • 如果收敛点对应的分数最终成为最大，就从 收敛点 开始回溯。
  • 否则，从 Hmax⁡H_{\max} 对应的格子 开始回溯。

这处理了局部比对中最大分可能出现在收敛点之后的情况。

一旦在某个 frontier 上检测到收敛，硬件并不会立刻停止，而是继续计算分数，同时维护一个 Phase 2 的最大分 Hmax⁡′H_{\max}^{\prime}。这个继续计算的过程会一直进行，直到满足以下两个终止条件之一：

  1. Hmax⁡′>Hmax⁡H_{\max}^{\prime} > H_{\max}
    出现了比 Phase 1 最大分更高的分数。

  2. 到达序列末尾（或 wavefront 超过硬件限制，回退 CPU）
    如果一直算到末尾都没有出现更大的分数，就说明 Phase 1 的 Hmax⁡H_{\max} 就是全局最大分。

为什么不能无限算下去？

因为有两个硬性停止条件：

  • 到达序列末尾：不可能再有新的格子了，所以停止；
  • wavefront 超过硬件限制 Bmax⁡B_{\max}：硬件无法处理，返回 invalid flag，Host CPU 用软件重新算。

所以，即使 Hmax⁡′>Hmax⁡H_{\max}^{\prime} > H_{\max} 一直不满足，计算也不会无限进行，而是会在序列末尾自然停止

7. 回溯：Traceback Logic​

一旦确定回溯起点，Traceback Logic 就开始工作：

  • 从起点出发，根据 SRAM 里的 traceback 指针一步步走；
  • 使用 Start/Stop SRAM 里的 stripe 起止信息；
  • 走出当前 tile 的 partial alignment；
  • 把路径发给软件，由软件拼接成完整比对。

然后进入下一个 tile：

  • 用 marker 的分数初始化下一个 tile；
  • 重复 Phase 1 和 Phase 2。

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

硬件设计时固定了 Bmax⁡B_{\max}。
如果某个 wavefront 的 cell 数超过 Bmax⁡B_{\max}，硬件无法处理，就：

  • 返回一个 invalid flag；
  • Host CPU 用软件重新算这个比对。

这样虽然牺牲了一点吞吐，但保证了结果永远正确。
这是 TALCO 相比 GACT-X 的一个重要优势：GACT-X 会贪心选错，而 TALCO-XDrop 宁可回退也不出错。

9. 和 GACT-X 的关系​

TALCO-XDrop 和 GACT-X 很像，都是 systolic PE 阵列 + X-Drop banding。
区别是：

  • GACT-X 只有 Phase 1 的贪心 tiling；
  • TALCO-XDrop 多了图 7a 灰色框里的 Phase 2 逻辑：
    • pointer redirection；
    • Reduction Tree；
    • Convergence Pointer SRAM；
    • 收敛后回溯。

所以 TALCO-XDrop 可以保证与完整 X-Drop 等价，而 GACT-X 不能。

10. 一句话总结​

TALCO-XDrop 加速器用 systolic PE 阵列计算 X-Drop 的分数和 traceback 指针，Phase 1 把指针存进 SRAM；到达 marker 后，Phase 2 用 pointer redirection 和 Reduction Tree 检测所有回溯路径是否汇聚到 marker 上同一个格子；一旦收敛，就从那个格子开始回溯，输出当前 tile 的 partial alignment；然后用 marker 分数初始化下一个 tile。如果 wavefront 超过硬件限制，就回退 CPU。这样就在固定片上内存下，实现了任意长序列的加速，并保证结果与软件 X-Drop 一致。

。