WFAA parallelism

这句话是在说 TALCO-WFAA 加速器内部同时使用多个 extend 模块和多个 compute 模块来并行计算。下面详细解释并行性从哪来、每个模块做什么、为什么需要两种不同的模块。

---

1. 先回顾 WFA-Adapt 的计算顺序

WFA-Adapt 的三角矩阵按分数 $s$ 逐行推进。每一行有多个对角线 $k$，范围在：

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

每个格子 $(s, k)$ 需要：

1. 计算 offset：根据上一行的 $H$、$I$、$D$ 状态，算出这个格子在匹配延伸前的初始位置；
2. 匹配延伸：从初始位置出发，沿对角线比较 $R$ 和 $Q$ 的碱基，直到不匹配，得到最终 offset；
3. 计算 traceback pointer：记录这个 offset 是从哪个状态来的。

这三步中，第 1 步和第 3 步由 compute 模块做，第 2 步由 extend 模块做。

---

2. 并行性从哪来？

关键观察：

同一行（同一个分数 $s$）中，不同对角线 $k$ 上的格子是互相独立的。

格子 $(s, k)$ 只依赖于上一行的 $(s-1, \cdot)$ 和 $(s-2, \cdot)$，不依赖于同一行的其他格子。
所以，同一行内所有对角线可以同时计算。

假设当前行的 $k$ 范围是：

$$k_{\min} = -5, \quad k_{\max} = 5$$

一共有 11 条对角线。

• 如果只有 1 个 extend 模块，就要串行做 11 次匹配延伸；
• 如果有 $N_{ext} = 11$ 个 extend 模块，就能一次并行做完 11 条对角线。

同理，compute 模块也是。

所以：

$N_{ext}$ 和 $N_{comp}$ 就是硬件为同一行内不同对角线提供的并行通道数。

---

3. extend 模块：并行做匹配延伸

每个 extend 模块负责一条对角线。

输入：

• 一个 cell offset（匹配延伸的起始位置）；
• 一个 K 位置（对角线编号）。

工作：

1. 根据 offset 和 K，算出 $R$ 和 $Q$ 的起始位置： $$r_i = \text{offset}, \quad q_i = \text{offset} - K$$
2. 从 $r_i$ 和 $q_i$ 开始，逐个比较碱基；
3. 为了加速，同时比较多个连续碱基；
4. 用 reduction tree 找出最早不匹配的位置；
5. 返回新的 offset（最后一个匹配的位置）。

并行方式：

• $N_{ext}$ 个 extend 模块各自负责一条对角线；
• 它们同时开始、同时结束；
• 每条对角线独立比较自己的碱基，互不干扰。

例子：

假设 $N_{ext} = 4$，当前行有 4 条对角线 $k = -2, -1, 0, 1$：

extend[0] 处理 k = -2
extend[1] 处理 k = -1
extend[2] 处理 k = 0
extend[3] 处理 k = 1

它们同时工作，一次就能算完 4 条对角线。

---

4. compute 模块：并行算 offset 和指针

每个 compute 模块负责一条对角线。

输入：

• 上一行的 $H_{i-1}$、$I_{i-1}$、$D_{i-1}$、$H_{i-2}$ 状态；
• 当前对角线 $k$。

工作：

1. 用 WFA 递推公式 (4)–(7) 计算： $$I_{s,K} = \max(M_{s-o,K-1} + 1, I_{s-e,K-1} + 1)$$ $$D_{s,K} = \max(M_{s-o,K+1}, D_{s-e,K+1})$$ $$X_{s,K} = \max(I_{s,K}, D_{s,K}, M_{s-s,K} + 1)$$ $$H_{s,K} = X_{s,K} + \text{LCP}(Q[X_{s,K} - K, n-1], R[X_{s,K}, m-1])$$
2. 算出最远到达 offset；
3. 计算 traceback pointer；
4. 把指针存到 SRAM。

并行方式：

• $N_{comp}$ 个 compute 模块各自负责一条对角线；
• 它们同时计算各自的 offset 和指针。

---

5. extend 和 compute 的分工

为什么需要两种模块，而不是一个模块全包？

因为 extend 和 compute 做的事情性质不同：

	extend 模块	compute 模块
任务	匹配延伸，比较碱基	递推计算，求 max，算指针
操作	字符串比较 + reduction tree	算术运算 + 状态选择
输入	offset + K	上一行的 H/I/D 状态
输出	新 offset	下一行的 offset + 指针
特点	数据依赖不规则，适合并行比较	计算密集，适合流水线

分开做的好处：

• 各自可以针对自己的任务优化；
• 可以流水线化：当一些 extend 模块在比较碱基时，一些 compute 模块可以同时算下一行的 offset；
• 硬件资源利用率更高。

---

6. 实际配置

论文里给出的 FPGA 和 ASIC 配置：

FPGA：

• 16 个 TALCO-WFAA 阵列；
• 每个阵列有 16 个 extend 模块和 16 个 compute 模块；
• 总共 256 个 extend + 256 个 compute 模块。

ASIC：

• 16 个 TALCO-WFAA 阵列；
• 每个阵列有 16 个 extend 模块和 16 个 compute 模块；
• 工作频率 556 MHz。

---

7. 一个直观比喻

把 WFA-Adapt 的一行想象成一条流水线：

• 有 11 个零件要加工；
• extend 模块是“匹配工人”，负责把每个零件沿对角线往前推，直到推不动；
• compute 模块是“计算工人”，负责根据上一轮结果，算出每个零件下一轮从哪里开始；
• 如果只有 1 个工人，就要一个一个来；
• 有 $N_{ext}$ 和 $N_{comp}$ 个工人，就能同时处理多条对角线。

---

8. 为什么不能无限增加 $N_{ext}$ 和 $N_{comp}$？

因为一行内的对角线数量是有限的：

$$k_{\max} - k_{\min}$$

• 如果 $N_{ext}$ 超过这个数量，多余的模块就闲置了；
• 而且对角线数量由 WFA-Adapt 的剪枝决定，通常不会太大；
• 论文里设置 $B_{\max} = 128$，但实际 $k_{\max} - k_{\min} < 90$；
• 所以 16 个 extend 和 16 个 compute 模块是比较合理的配置。

---

9. 一句话总结

$N_{ext}$ 和 $N_{comp}$ 是 TALCO-WFAA 为同一行内不同对角线提供的并行通道数。extend 模块负责匹配延伸，compute 模块负责递推计算和指针生成。因为同一行内不同对角线互相独立，所以可以同时用多个 extend 和 compute 模块并行处理，从而大幅加速 WFA-Adapt 的每一行计算。