Skip to main content

1. DRAM Traffic Modeling

这一节 A. DRAM Traffic Modeling 的核心目的，是为 传统逐阶段执行（baseline stage-by-stage） 与 Locus 的跨阶段融合执行（fused execution） 建立统一的 DRAM 流量模型，用公式量化中间数据搬运的开销，并证明 fusion 为什么能大幅降低 DRAM traffic。它同时给出片上缓冲区容量约束，指导后续的 tile 大小、片上存储分配和 partitioning 设计。

下面按论文逻辑详细展开。

1. 建模对象：三阶段 S2G pipeline​

模型只考虑 S2G mapping 中最核心、最耗内存的三个阶段：

  • LC：Linear Chaining，线性链接
  • GC：Graph Chaining，图链接
  • AL：Alignment，比对

Seeding 阶段因为运行时间占比很小，且主要产生 anchors，被归入初始输入。模型关注的是每个 query 产生的中间数据量，以及这些数据在阶段之间如何往返 DRAM。

论文先定义了一组符号，即 Table I。

2. 符号定义（Table I）​

工作负载相关：

  • NaN_a：anchor 数量（论文 Table I 写作 NαN_\alpha，公式中用 NaN_a）
  • NcN_c：chain 数量
  • NpN_p：path 数量
  • NgN_g：gap 数量
  • Sa,Sc,SpS_a, S_c, S_p：anchor、chain、path 记录大小，分别为 16B,48B,80B16\mathrm{B}, 48\mathrm{B}, 80\mathrm{B}
  • SwS_w：WFA scratchpad 大小
  • SoS_o：CIGAR 输出大小
  • ρc=Nc/Na\rho_c = N_c/N_a：chain 压缩比
  • ρp=Np/Na\rho_p = N_p/N_a：path 压缩比

图与批处理相关：

  • α\alpha：跨 bubble 的 path 比例，约 0.400.40
  • β\beta：一个 sorted batch 中每个 bin 的 reads 数
  • SτS_\tau：每个 graph node 的 topology 字节数
  • ∣Bi∣|B_i|：bin ii 中的 node 数

设计参数：

  • McapM_{cap}：片上 buffer 总容量
  • Mfuse,MtopoM_{fuse}, M_{topo}：fusion working set 与 topology 的预算
  • TT：每个 tile 的 anchor 数
  • NwN_w：并发 WFA scratchpad 槽数

这些符号贯穿公式 (4)、(5)、(6)。

3. Baseline：逐阶段执行的 DRAM traffic​

传统 stage-by-stage 执行中，每个阶段从 DRAM 读输入，计算后把输出写回 DRAM。下一阶段再重新读入。因此中间结果会被反复搬运。

给定一个 query 产生 NaN_a 个 anchors，论文给出每阶段 DRAM traffic：

DLC=NaSa+NcScDGC=NcSc+αNpSτ+NpSpDAL=NpSp+NgSw+NgSo(4)\begin{array}{rl} D_{\mathrm{LC}} &= N_aS_a + N_cS_c \\ D_{\mathrm{GC}} &= N_cS_c + \alpha N_pS_\tau +N_pS_p \\ D_{\mathrm{AL}} &= N_pS_p + N_gS_w + N_gS_o \end{array} \tag{4}

逐项解释：

LC 阶段​

DLC=NaSa+NcScD_{\mathrm{LC}} = N_aS_a + N_cS_c
  • NaSaN_aS_a：从 DRAM 读入全部 anchors。
  • NcScN_cS_c：把生成的 local chains 写回 DRAM。

GC 阶段​

DGC=NcSc+αNpSτ+NpSpD_{\mathrm{GC}} = N_cS_c + \alpha N_pS_\tau + N_pS_p
  • NcScN_cS_c：重新从 DRAM 读入 chains。
  • αNpSτ\alpha N_pS_\tau：对约 α≈0.40\alpha \approx 0.40 的跨 bubble 路径，需要从 DRAM 取子图 topology，包括 edge lists 和 node lengths。
  • NpSpN_pS_p：把 graph-chain paths 写回 DRAM。

AL 阶段​

DAL=NpSp+NgSw+NgSoD_{\mathrm{AL}} = N_pS_p + N_gS_w + N_gS_o
  • NpSpN_pS_p：重新读入 paths。
  • NgSwN_gS_w：为每个 gap 分配并丢弃 WFA scratchpad，这是最大的项。
  • NgSoN_gS_o：写出 CIGAR 结果。

总 baseline traffic​

Dbase=DLC+DGC+DALD_{\mathrm{base}} = D_{\mathrm{LC}} + D_{\mathrm{GC}} + D_{\mathrm{AL}}

关键问题是：有些数据被写了又读、读了又写：

  • NcScN_cS_c 在 LC 写出，又在 GC 读回；
  • NpSpN_pS_p 在 GC 写出，又在 AL 读回。

这些就是 stage-to-stage round trips，也是 fusion 要消除的主要目标。

论文指出：对于长读 L≥10KbpL \geq 10\mathrm{Kbp}，WFA scratchpad 项 NgSwN_gS_w 主导 DbaseD_{\mathrm{base}}，超过总流量的 86%86\%。这与 Section II-C 的观察一致：WFA buffer 随 gap 长度二次增长，而 bubble 节点平均约 108bp108\mathrm{bp}，进一步放大了 gap 和 buffer。

4. Fused Execution：融合执行的 DRAM traffic​

Locus 的核心思想是：把每个 read 的 anchors 分成大小为 TT 的 tiles，每个 tile 在片上 buffer MfuseM_{\mathrm{fuse}} 中依次完成：

LC→GC→AL\mathrm{LC} \to \mathrm{GC} \to \mathrm{AL}

chain descriptors、path headers、WFA scratchpad 都保留在片上，不再跨阶段写回 DRAM。

同时，host 按 mapped bin 对 reads 分组，一次提交一个 bin 给 Locus。这样一个 bin 的 subgraph 数据（vertex sequences 和 adjacency lists）只需从 DRAM 加载一次，就能被该 batch 中所有 β\beta 个 reads 复用。

于是每个 query 的 fused traffic 为：

Dfuse=NaSa⏟anchors+αNpSτβ⏟topology/β+NgSo⏟CIGAR(5)D_{\mathrm{fuse}} = \underbrace{N_aS_a}_{\mathrm{anchors}} + \underbrace{\frac{\alpha N_pS_\tau}{\beta}}_{\mathrm{topology}/\beta} + \underbrace{N_gS_o}_{\mathrm{CIGAR}} \tag{5}

三项含义：

  1. NaSaN_aS_a：初始 anchor 读入，这是不可消除的输入。
  2. αNpSτβ\frac{\alpha N_pS_\tau}{\beta}：分区子图 topology 数据，被 β\beta 个 reads 分摊，因此除以 β\beta。
  3. NgSoN_gS_o：最终 CIGAR 输出，不可消除。

注意：TT 没有出现在 DfuseD_{\mathrm{fuse}} 中。原因是只要一个 tile 能放进片上 buffer，TT 变大或变小既不改变 DRAM traffic，也不改变 subgraph partition。Tile size 只影响片上吞吐，因此它出现在下面的容量约束里，而不是流量公式里。

5. 片上缓冲区容量约束​

为了让 fusion 成立，当前 tile 的 anchors、中间结果、WFA scratchpad 以及当前 bin 的子图数据必须同时放在片上。论文给出容量约束：

TSa+ρcTSc+ρpTSp+NwSw+∣Bi∣⋅Sτ≤Mcap(6)TS_{a} + \rho_{c}TS_{c} + \rho_{p}TS_{p} + N_{w}S_{w} + |B_{i}| \cdot S_{\tau} \leq M_{cap} \tag{6}

逐项解释：

  • TSaTS_{a}：tile 的 anchor buffer。
  • ρcTSc\rho_c T S_c：chain buffer，按 compaction ratio ρc=Nc/Na\rho_c = N_c/N_a 与 TT 成比例。
  • ρpTSp\rho_p T S_p：path buffer，按 ρp=Np/Na\rho_p = N_p/N_a 与 TT 成比例。
  • NwSwN_w S_w：NwN_w 个并发 gap alignment 的 WFA scratchpad。
  • ∣Bi∣⋅Sτ|B_i| \cdot S_\tau：当前 bin ii 的子图 topology 大小。

所有项之和不能超过片上容量 McapM_{cap}。

这个约束说明：tile size TT 不能无限增大；WFA 并发槽 NwN_w 也受限于片上 scratchpad；而子图数据大小 ∣Bi∣Sτ|B_i|S_\tau 取决于 partitioning 的结果。因此，Section III-B 的 bubble-aware partitioning 直接影响这个约束能否被满足。

6. DRAM 流量降低比​

定义降低比：

R=DbaseDfuseR = \frac{D_{\mathrm{base}}}{D_{\mathrm{fuse}}}

对于长读：

  • 分子 DbaseD_{\mathrm{base}} 由 NgSwN_gS_w 主导；
  • 分母 DfuseD_{\mathrm{fuse}} 由 NaSaN_aS_a 主导。

所以 RR 受 anchor-load floor 限制。论文报告：

  • RR 从 100 bp 短读的 24×24\times 到 10 Kbp 长读的 27×27\times。
  • Graph partitioning 还能为 β≈10−50\beta \approx 10-50 的 batch 额外贡献约 10%10\% 的 reduction，这正是 30×30\times whole-genome coverage 的典型范围。

这些数字与后文 Section V-E 的 DRAM traffic 分析一致：fusion 消除了 WFA scratchpad 的重复分配、chain descriptor 和 path data 的往返，使最终 fused traffic 降到 baseline 的约 4%4\%。

7. 这一节的核心结论与作用​

总结起来，Section III-A 做了四件事：

  1. 量化 baseline 的冗余 DRAM 搬运：LC、GC、AL 之间存在大量 stage-to-stage round trips，WFA scratchpad 是最大来源。
  2. 建立 fused execution 的流量模型：通过片上保留中间结果，消除 chain/path/WFA 的 DRAM 往返；通过 bin 级批处理，把 topology 流量除以 β\beta。
  3. 给出片上容量约束：tile size、WFA 并发槽、子图大小必须满足 McapM_{cap} 限制。
  4. 推导降低比并指导设计：RR 受 anchor load 限制，graph partitioning 能进一步减少 topology 流量，从而引出 Section III-B 的 RBCP 分区算法。

因此，这一节不仅是性能分析，也是 Locus 架构与 partitioning 设计的理论基础。