2.1 Off-Chip Memory Access Formulation

3.1 节 Off-Chip Memory Access Formulation 的核心目的是：
用数学模型量化“逐阶段执行”和“融合执行”两种方式下，DRAM 访问量分别是多少，从而证明融合能大幅减少片外内存流量。

你可以把 DRAM 想成一个仓库，GLB（全局缓冲区）想成车间里的工作台。

• Baseline：每个阶段做完，都把半成品搬回仓库；下一个阶段再从仓库搬出来。
• Fusion：多个阶段在同一个车间里连续做，半成品直接放在工作台上传给下一道工序，不经过仓库。

下面逐层解释。

1. 先定义各种数据单元的大小

为了算 DRAM 流量，先假设每种数据占多少字节：

• $S_a = 16$ 字节：每个 anchor（种子锚点），存 query 坐标、graph 坐标、方向、跨度等。
• $S_{lc} = 48$ 字节：每条 linear chain（线性链），存边界位置、分数、anchor 偏移等。
• $S_{gc} \approx 1$ KB：每条 graph chain（图链），包含顶点序列、路径描述、比对分数等。
• $S_{wfa} = 40$ KB：每个 WFA buffer，用于 wavefront alignment 的对角线数组（match、insertion、deletion 状态）。

同时假设：

• $N_a$：一条 query 产生的 seed anchors 数量；
• $N_{lc}$：线性链数量，通常 $N_{lc} \approx N_a / 100$；
• $N_{gc}$：图链数量，通常 $N_{gc} \approx N_{lc} / 100$；
• $N_{gaps}$：对齐阶段需要处理的 inter-anchor gap 数量。

这些大小和比例来自实际 profiling，代表当前 S2G 框架的典型情况。

2. Baseline：逐阶段执行的 DRAM 访问

在传统逐阶段执行中，每个阶段独立处理完整数据集：
从 DRAM 读输入，处理完把输出写回 DRAM。

线性链阶段

$$\mathrm{DRAM_{LC}} = N_{a}S_{a} + N_{lc}S_{lc} \tag{1}$$

• 读：所有 anchors，$N_a S_a$；
• 写：所有 linear chains，$N_{lc} S_{lc}$。

图链阶段

$$\mathrm{DRAM_{GC}} = N_{lc}S_{lc} + N_{gc}S_{gc} \tag{2}$$

• 读：所有 linear chains，$N_{lc} S_{lc}$；
• 写：所有 graph chains，$N_{gc} S_{gc}$。

注意：linear chains 在公式 (1) 写了一次，在公式 (2) 又读了一次。
这就是中间数据反复进出 DRAM 的典型例子。

对齐阶段

$$\mathrm{DRAM_{AL}} = N_{gc}S_{gc} + N_{gaps}S_{wfa} \tag{3}$$

• 读：所有 graph chains，$N_{gc} S_{gc}$；
• 写/分配：每个 inter-anchor gap 独立分配一个 WFA buffer，共 $N_{gaps} S_{wfa}$。

这里的关键是：每个 gap 都单独分配和释放一个 40 KB 的 WFA buffer，造成大量分配抖动（allocation churn），这是 DRAM 流量的主要来源。

总 baseline 流量

$$\mathrm{DRAM_{baseline}} = \mathrm{DRAM_{LC}} + \mathrm{DRAM_{GC}} + \mathrm{DRAM_{AL}} \tag{4}$$

把三项加起来，你会发现很多数据被重复读写：

• linear chains：写一次、读一次；
• graph chains：写一次、读一次；
• WFA buffers：每个 gap 反复分配释放。

Profiling 显示：对于 10 Kbp 的 read，每条 query 平均产生 1205 MB 的累计内存占用，其中 96.4% 来自 alignment 阶段的 WFA buffer 循环分配。
这说明 baseline 的瓶颈不在计算，而在中间数据反复进出 DRAM。

3. Fusion：融合执行的 DRAM 访问

融合的思路是：把 anchors 分成 $T$ 个 tile（瓦片），每个 tile 处理 $T_a = \lceil N_a / T \rceil$ 个 anchors。
在一个 tile 内，依次跑完线性链、图链、对齐等所有阶段，中间数据一直留在 GLB 里，不写回 DRAM。只有 tile 全部处理完，才把最终 alignment 结果（CIGAR 字符串）写出去。

于是 DRAM 访问变成：

$$\mathrm{DRAM_{fused}}(T) = \underbrace{N_{a}\cdot S_{a}}_{\mathrm{anchor~input}} + \underbrace{T\cdot N_{gc}^{\mathrm{glue}}\cdot S_{cigar}}_{\mathrm{alignment~output}} \tag{5}$$

逐项解释：

• 第一项 $N_a S_a$：所有 anchors 仍然需要从 DRAM 读入一次。这是无法避免的输入。
• 第二项 $T \cdot N_{gc}^{\mathrm{glue}} \cdot S_{cigar}$：每个 tile 最终输出一些 alignment 结果。
  • $N_{gc}^{\mathrm{glue}} \approx N_{gc} / T$ 是每个 tile 平均包含的图链数；
  • $S_{cigar} \approx 25$ 字节，是每条 alignment 的 CIGAR 字符串大小；
  • 乘起来就是所有 tile 的 alignment 输出总量。

关键变化：
中间数据项消失了。
原来在 baseline 中反复读写的 $N_{lc} S_{lc}$、$N_{gc} S_{gc}$，以及 $N_{gaps} S_{wfa}$，现在都在 GLB 内部产生和消费，不再经过 DRAM。
而且 WFA buffer 不再每个 gap 单独分配，而是在一个 tile 内共享一个固定池，进一步消除分配抖动。

4. Tiling 优化

融合后，DRAM 流量表达式主要剩两项：anchor 输入和 CIGAR 输出。
但 tile 大小 $T_a$ 不能随便选，因为 GLB 容量有限。
所以优化问题写成：

$$\min_{T_{a}}\mathrm{DRAM_{fused}}(T_{a}) \tag{6}$$

同时要满足 GLB 容量约束 $C_{GLB}$。

直观理解：

• $T_a$ 太大：一个 tile 的中间数据太多，GLB 放不下；
• $T_a$ 太小：tile 数量 $T$ 太多，可能增加一些边界开销，但中间数据更容易放进 GLB。

所以要在 GLB 容量允许的前提下，选择合适的 tiling 因子，使 DRAM 总流量最小。

5. 总结

3.1 节的核心逻辑是：

1. Baseline 问题：逐阶段执行导致中间数据反复写入和读出 DRAM，尤其 WFA buffer 每个 gap 都分配释放，造成巨大 DRAM 流量。
2. Fusion 方案：把多个阶段融合到一个 tile 内执行，中间数据留在 GLB，只保留 anchor 输入和最终 CIGAR 输出。
3. 数学证明：通过公式 (1)-(5) 对比，baseline 的中间数据项在 fused 模型中消失，DRAM 流量大幅下降。
4. Tiling 优化：在 GLB 容量约束下选择 tile 大小，最小化剩余 DRAM 访问。

一句话：
这一节用数学公式说明，S2G 流水线的瓶颈是中间数据反复进出 DRAM；把流水线融合成 tile 后，中间数据留在片上，DRAM 只负责读入 anchors 和写出最终比对结果，从而显著降低片外内存访问。