3.4 Memory requirements

这段 Memory requirement 是在算 TALCO 每个 tile 到底需要多少片上内存。核心结论是：

每个 tile 的内存只取决于 $M$ 和 $B_{\max}$，与输入序列的长度无关。
所以 TALCO 可以在固定大小的片上内存里，处理任意长的序列比对。

下面逐项拆开解释。

---

1. 先理解两个关键参数

• $B_{\max}$：一个 frontier 里最多有多少个 cell。
  你可以把它理解成“波前/带宽的最大宽度”。因为做了 banding（比如 X-Drop 或 WFA-Adapt），frontier 不会无限宽，最多 $B_{\max}$ 个格子。

• $M$：一个 tile 的 Phase 1 里包含多少个 frontier。
  也就是从 tile 起点算到 marker，一共推进 $M$ 个 frontier。

这两个参数都是设计时固定的，不随序列长度变化。

---

2. Phase 1 的内存

Phase 1 要做两件事：

1. 正常计算每个 frontier 的分数和 traceback 指针；
2. 把 traceback 指针存下来，供后面回溯用。

所以需要存：

• $M \times B_{\max}$ 个 traceback 指针
  因为 Phase 1 有 $M$ 个 frontier，每个 frontier 最多 $B_{\max}$ 个 cell，每个 cell 存一个指针。

• $B_{\max}$ 个分数
  计算当前 frontier 时，需要上一个 frontier 的分数 $S_{\text{prev}}$ 和当前 frontier 的分数 $S_{\text{curr}}$。
  每个 frontier 最多 $B_{\max}$ 个 cell，所以两份分数各 $B_{\max}$ 个。

因此 Phase 1 的内存量级是：

$$O(M \times B_{\max})$$

指针是主要部分，分数相对小一些，但量级相同。

---

3. Phase 2 的内存

Phase 2 不再存 traceback 指针，而是存 convergence pointer。

• convergence pointer 的作用是：
  告诉当前 cell，“你沿 traceback 往回走，最终会落到 marker 上的哪个格子”。

• marker 本身也是一个 frontier，最多有 $B_{\max}$ 个 cell。
  所以指向 marker 上某个格子的索引，需要：

$$\log_2(B_{\max}) \text{ 位}$$

• Phase 2 只需要维护当前 frontier 和上一个 frontier 的 convergence pointer，即：
  • ConvPrprev
  • ConvPrcurr

每个最多 $B_{\max}$ 个指针，每个指针 $\log_2(B_{\max})$ 位。
所以 Phase 2 的内存量级是：

$$O(B_{\max} \times \log_2(B_{\max}))$$

注意这里没有 $M$，因为 Phase 2 不存历史指针，只存当前和上一个。

实际：$2 \times B_{\max} \times \log_2(B_{\max})$

---

4. 合起来的总内存

一个 tile 的总内存：

$$O(M \times B_{\max} + \log_2(B_{\max}) \times B_{\max})$$

• 第一项来自 Phase 1 的 traceback 指针；
• 第二项来自 Phase 2 的 convergence pointer。

关键点：

• 没有出现 $m$ 或 $n$（输入序列长度）；
• 也没有出现 $d$（编辑距离）；
• 只和 $M$、$B_{\max}$ 有关。

所以无论序列多长，每个 tile 的内存都是固定的。

---

5. 局部比对还要多一点

如果底层算法是局部比对（比如 X-Drop 找局部最优），还需要记住当前见过的最大分数 cell。

• 需要额外存这个最大分 cell 的分数；
• 还需要存它的 convergence pointer，占 $\log_2(B_{\max})$ 位。

所以再加一点常数内存，但仍然只和 $B_{\max}$ 有关。

---

6. 为什么能回退 CPU？

因为硬件设计时固定了 $B_{\max}$。

• 如果实际某个 frontier 的 cell 数超过 $B_{\max}$，硬件片上内存放不下；
• 这时硬件返回一个 invalid flag；
• Host CPU 用软件重新算这个比对。

这样保证：

凡是硬件能处理的，结果一定和完整 banded 算法一致；
硬件处理不了的，就交给软件，结果也不会错。

这是 TALCO 相比 GACT 等旧 tiling 方法的一个重要优势：

• GACT 固定 tile 大小和重叠，可能丢路径，且没有回退机制；
• TALCO 有明确的内存上限，超了就回退，保证正确性。

---

7. 一个数值例子

假设：

• $M = 100$
• $B_{\max} = 1000$

Phase 1：

• traceback 指针：$100 \times 1000 = 100{,}000$ 个指针；
• 分数：约 $2 \times 1000 = 2000$ 个。

Phase 2：

• 每个 convergence pointer 需要 $\log_2(1000) \approx 10$ 位；
• 两个 frontier：$2 \times 1000 \times 10 = 20{,}000$ 位。

总内存量级约 $100{,}000$ 个指针 + 少量分数和位信息。
如果每个指针 4 位，大约 400 Kbit，完全可以放在片上 SRAM。

而不管序列是 10 Kbp 还是 100 Kbp，这个内存都不变。

---

8. 一句话总结

TALCO 每个 tile 的内存只由 $M$ 和 $B_{\max}$ 决定：Phase 1 存 $M \times B_{\max}$ 个 traceback 指针和两份 $B_{\max}$ 分数；Phase 2 存两份 $B_{\max}$ 个 convergence pointer，每个指针 $\log_2(B_{\max})$ 位。总内存 $O(M \times B_{\max} + \log_2(B_{\max}) \times B_{\max})$，与序列长度无关。如果实际 frontier 超过 $B_{\max}$，硬件就回退 CPU，保证结果与不 tiling 时一致。