WFAA pruning : Reduce

在 TALCO-WFAA 中，$k_{\max}$、$k_{\min}$、$k_{\max}'$、$k_{\min}'$ 是 WFA-Adapt 剪枝机制的核心参数，用来控制每一行三角矩阵中实际需要计算的对角线范围。

---

$k_{\max}$ 和 $k_{\min}$

1. 先回顾 WFA-Adapt 的三角矩阵

• 行 = 分数 $s$
• 列 = 对角线 $k = i - j$
• 每个格子 $(s, k)$ 存最远 offset $H_{s,k}$

如果没有剪枝，每一行的 $k$ 范围会随着 $s$ 增大而不断变宽（$k$ 从 $-s$ 到 $+s$）。
但很多外侧对角线上的格子“落后太多”，对最终最优比对没有贡献。
WFA-Adapt 的启发式就是：丢掉这些外侧对角线，只保留中间一段。

---

2. $k_{\max}$ 和 $k_{\min}$：当前行的有效范围

在计算第 $s$ 行之前，硬件已经确定了这一行需要计算的对角线范围：

$$k_{\min} \le k \le k_{\max}$$

这个范围来自上一行的剪枝结果。
硬件只为这个范围内的每条对角线分配 extend 和 compute 模块。

• 范围内的对角线：正常计算 $I$、$D$、$X$、$H$ 和 traceback pointer。
• 范围外的对角线：视为不存在，不计算，也不存指针。

所以 $k_{\max}$ 和 $k_{\min}$ 决定了这一行的计算宽度，也就是并行度。

---

3. $k_{\max}'$ 和 $k_{\min}'$：剪枝后的新范围

当前行所有对角线算完后，reduce 模块执行 WFA-Adapt 剪枝：

检查每条对角线上最远到达的 offset。
如果某条外侧对角线的 offset 落后最远对角线太多，就丢掉它。

剪枝后得到新的范围：

$$k_{\min}' \le k \le k_{\max}'$$

这两个值存入专用 SRAM，供下一行使用。
下一行计算时，就用 $k_{\max}'$ 和 $k_{\min}'$ 作为它的 $k_{\max}$ 和 $k_{\min}$。

所以：

参数	含义	用途
$k_{\max}$、$k_{\min}$	当前行的对角线范围	决定这一行要算哪些对角线
$k_{\max}'$、$k_{\min}'$	剪枝后的新范围	作为下一行的 $k_{\max}$、$k_{\min}$

---

4. 在硬件流程中的位置

回顾论文原文：

❶ extend 模块对 $k_{\min}$ 到 $k_{\max}$ 范围内的所有 cell 计算新 offset。
❷ reduce 模块做剪枝，用 reduction tree 确定新的 $k_{\max}'$ 和 $k_{\min}'$，存入 SRAM。
❸ 四组寄存器存当前 frontier 的 offset。
❹ compute 模块计算下一行的 offset 和指针。
❺ 指针存 SRAM，进入下一轮迭代。

所以流程是：

上一行的 k_max', k_min'
        ↓
当前行的 k_max, k_min  ← 从 SRAM 读取
        ↓
extend 模块并行计算范围内的 cell
        ↓
reduce 模块剪枝 → 产生新的 k_max', k_min'
        ↓
存入 SRAM，供下一行使用

---

5. 为什么要剪枝？

因为 WFA-Adapt 的三角矩阵如果没有剪枝，第 $s$ 行有 $2s+1$ 条对角线。
当 $s$ 很大时（长序列、高错误率），计算量和内存都会爆炸。

剪枝后，每一行只保留最有希望的对角线，通常数量远小于 $2s+1$。
论文实测：

所有 wavefront 都有 $k_{\max} - k_{\min} < 90$。

所以硬件只需要支持最多约 90 条对角线的并行计算，就能处理所有读段类型。

---

6. 举例

假设当前行 $s=5$：

• 剪枝前范围：$k_{\min} = -5$，$k_{\max} = 5$；
• 算完后，reduce 模块发现 $k=-5$ 和 $k=5$ 的对角线 offset 落后太多；
• 剪枝后：$k_{\min}' = -3$，$k_{\max}' = 3$；
• 存入 SRAM。

下一行 $s=6$ 计算时：

• 从 SRAM 读取 $k_{\min} = -3$，$k_{\max} = 3$；
• 只计算这 7 条对角线，而不是全部 13 条。

这样每一行的计算宽度被动态控制在合理范围内。

---

7. 一句话总结

$k_{\max}$ 和 $k_{\min}$ 是当前行需要计算的对角线范围，决定并行度；$k_{\max}'$ 和 $k_{\min}'$ 是剪枝后得到的新范围，存入 SRAM 供下一行使用。它们共同实现了 WFA-Adapt 的自适应 banding，让 TALCO-WFAA 在固定硬件资源下高效处理长序列比对。

---

如何判断落后程度

在 WFA-Adapt 中，“某条外侧对角线的 offset 落后最远对角线太多”这个判断，是基于一个用户定义的参数 $W_{diff}$ 来做的。下面详细说明。

---

1. 先看每一行里 offset 的含义

在三角矩阵的第 $s$ 行：

• 每条对角线 $k$ 都有一个最远到达的 offset，记作 $H_{s,k}$；
• offset 越大，说明这条对角线在参考序列上走得越远，越“有希望”。

比如第 $s$ 行有 5 条对角线：

$k$	$H_{s,k}$
$-2$	3
$-1$	5
$0$	8
$1$	7
$2$	4

最远对角线是 $k=0$，offset = 8。

---

2. 落后多少才算“太多”？

WFA-Adapt 用一个阈值 $W_{diff}$ 来判断：

如果某条对角线的 offset 小于（最大 offset − $W_{diff}$），就认为它落后太多，剪掉。

形式化：

$$H_{s,k} < \max_{k'} H_{s,k'} - W_{diff} \quad \Longrightarrow \quad \text{剪掉对角线 } k$$

以上面的例子，如果 $W_{diff} = 3$：

• 最大 offset = 8；
• 阈值 = $8 - 3 = 5$；
• $k=-2$ 的 offset = 3 < 5 → 剪掉；
• $k=2$ 的 offset = 4 < 5 → 剪掉；
• $k=-1, 0, 1$ 保留。

剪枝后，新的范围是：

$$k_{\min}' = -1, \quad k_{\max}' = 1$$

这两个值存入 SRAM，供下一行使用。

---

3. $W_{diff}$ 的作用

$W_{diff}$ 是 WFA-Adapt 的启发式参数：

• $W_{diff}$ 越大：保留的对角线越多，越安全，但计算量越大；
• $W_{diff}$ 越小：剪枝越激进，速度越快，但可能丢最优路径。

论文里设置 $W_{diff} = 50$，因为它在实验中给出了最优比对分数。

---

4. 硬件里怎么实现？

在 TALCO-WFAA 中，reduce 模块负责这个判断：

1. 收集当前行所有对角线的 offset；
2. 用一个 reduction tree 找出最大 offset；
3. 对每条对角线，比较它的 offset 是否小于（最大 offset − $W_{diff}$）；
4. 把满足条件的对角线标记为剪枝；
5. 另一个 reduction tree 确定剪枝后剩下的最左和最右对角线，即 $k_{\min}'$ 和 $k_{\max}'$；
6. 存入专用 SRAM。

所以硬件只需要两个 reduction tree 就能完成剪枝判断。

---

5. 为什么用 offset 而不是分数？

因为 WFA 是按分数推进的，同一行内所有格子的分数相同（都是 $s$）。
区分“有希望”和“没希望”的唯一标准就是 offset：

offset 越大，说明这条对角线在同样的分数下走得越远，越可能到达终点。

所以剪枝依据是 offset 的相对落后程度，而不是分数。

---

6. 一句话总结

在 WFA-Adapt 中，每一行计算完后，找到所有对角线中最大的 offset，然后把 offset 小于（最大 offset − $W_{diff}$）的外侧对角线剪掉。剩下的范围就是 $k_{\min}'$ 到 $k_{\max}'$，存入 SRAM 供下一行使用。$W_{diff}$ 是控制剪枝激进程度的参数，论文中设为 50。