WFAA offset: Extend

这三个概念是 WFA-Adapt 硬件加速的核心。下面用最直观的方式讲清楚它们分别是什么、用来做什么。

---

1. 先回顾 WFA 的三角矩阵

WFA 的三角矩阵中：

• 行 = 分数 $s$（alignment score）
• 列 = 对角线 $k = i - j$

每个格子 $(s, k)$ 记录的是：

在分数 $s$ 下，对角线 $k$ 上能到达的最远位置。

这个“最远位置”就是 offset。

---

2. 什么是 offset？

offset 就是对角线上的位置坐标。

在 WFA 中，对角线 $k = i - j$ 固定后，只需要一个坐标就能确定位置。通常用 $i$（参考序列上的位置）作为 offset。

• offset = $i$ 表示：在对角线 $k$ 上，已经走到了 $R$ 的第 $i$ 个位置；
• 对应的 $j = i - k$，即 $Q$ 的第 $j$ 个位置。

offset 的作用：

告诉硬件“当前这条对角线上，匹配延伸到了哪里”。
后面的 extend 模块就从这里继续往后比较，看还能不能再匹配。

例子：

• 对角线 $k = 0$，offset = 4；
• 意思是：$R$ 和 $Q$ 已经匹配走到 $(4, 4)$；
• 下一个要比较的是 $R[5]$ 和 $Q[5]$。

---

3. 什么是 K 位置？

K 就是对应对角线的编号 $k = i - j$。

三角矩阵的每一列就是一个 $k$。
WFA 的波前只在 $k_{\min}$ 到 $k_{\max}$ 之间推进，因为外侧对角线被 WFA-Adapt 剪枝了。

K 的作用：

告诉 extend 模块“当前在哪条对角线上工作”。
有了 K 和 offset，就能唯一确定一个格子的位置 $(i, j)$：

$$i = \text{offset}, \quad j = \text{offset} - K$$

例子：

• $K = -1$，offset = 3；
• 则 $i = 3$，$j = 3 - (-1) = 4$；
• 对应格子 $(3, 4)$。

---

4. extend 模块是做什么的？

extend 模块负责 匹配免费延伸。

WFA 的核心规则是：

匹配不增加分数，可以沿对角线一直走，直到遇到不匹配为止。

extend 模块做的事就是：

1. 接收输入：一个 cell offset 和一个 K 位置；
2. 计算起点：根据 offset 和 K，算出 $R$ 和 $Q$ 上的起始位置： $$r_i = \text{offset}, \quad q_i = \text{offset} - K$$
3. 逐位比较：从 $r_i$ 和 $q_i$ 开始，比较 $R$ 和 $Q$ 的碱基；
4. 同时比较多个碱基：为了加速，硬件不是一次比一个，而是同时比较多个连续碱基；
5. 用 reduction tree 找最早不匹配位置：多个比较结果送入 reduction tree，快速确定第一个不匹配的位置；
6. 返回新 offset：新 offset = 最后一个匹配的位置，表示这条对角线延伸到的最远点。

一句话：

extend 模块就是“从给定位置出发，沿对角线一直匹配，直到遇到不匹配，然后返回新的最远位置”。

图示：

对角线 k = 0，offset = 1

R: A C G T A C
Q: A C G T A C
     ↑ 从 (1,1) 开始

extend 比较：
R[2]=C vs Q[2]=C → 匹配
R[3]=G vs Q[3]=G → 匹配
R[4]=T vs Q[4]=T → 匹配
R[5]=A vs Q[5]=C → 不匹配，停止

返回新 offset = 4

---

5. 这三个概念在流程中的位置

回顾论文原文的流程：

❶ extend 模块

• 接收：cell offset + K 位置；
• 做：匹配延伸，比较多个碱基，reduction tree 找最早不匹配；
• 返回：新 offset。

❷ reduce 模块

• 所有 cell 的新 offset 算完后，reduce 模块启动；
• 做：WFA-Adapt 剪枝，丢掉落后太多的外侧对角线；
• 用 reduction tree 确定新的 $k_{\max}'$ 和 $k_{\min}'$，存到 SRAM。

❸ 寄存器数组

• 四组寄存器：$H_{i-1}$、$I_{i-1}$、$D_{i-1}$、$H_{i-2}$；
• 存：每个 cell 的 offset；
• 作用：保存当前 frontier 的状态，供 compute 模块使用。

❹ compute 模块

• 根据之前算好的 frontier，用 WFA 递推公式 (4)–(7)；
• 找出每个 cell 的最远到达 offset；
• 同时计算 traceback pointer。

❺ 存指针，继续迭代

• traceback pointer 存到 SRAM；
• 进入下一轮 extend → reduce → compute。

---

6. 用一张图总结

        ┌─────────────────────────────────────────┐
        │  三角矩阵                                │
        │                                         │
        │  s=0   k=-2  k=-1  k=0  k=1  k=2       │
        │         ·     ·    4    ·    ·          │
        │  s=1   ·     3     5    4    ·          │
        │  s=2   2     4     6    5    7          │
        │                    ↑                    │
        │              格子 (s=2, k=0)            │
        │              offset = 6                 │
        │              K = 0                      │
        └─────────────────────────────────────────┘

extend 模块：
  输入：offset=6, K=0
  → r_i = 6, q_i = 6
  → 比较 R[7] 和 Q[7]（如果存在）
  → 返回新 offset

reduce 模块：
  根据所有 cell 的新 offset
  → 剪枝，更新 k_max, k_min

compute 模块：
  根据 H/I/D 寄存器
  → 算下一个 frontier 的 offset 和 traceback pointer

---

7. 一句话总结

概念	是什么	作用
offset	对角线上的位置坐标（通常用 $i$）	告诉硬件匹配延伸到了哪里
K 位置	对角线编号 $k = i - j$	确定在哪条对角线上工作
extend 模块	匹配延伸单元	从 offset 和 K 出发，比较碱基，返回新的最远 offset

extend 模块的核心任务是：给定对角线和起始位置，沿对角线做匹配延伸，返回新的最远位置。offset 和 K 就是它需要的两个输入参数。