Skip to main content

2.1.3 WFA Buffer

在 Alignment 阶段，WFA（Wavefront Alignment）要对 read 和候选图路径做碱基级精细比对。这个比对不是整条 read 一次性做完，而是按 anchor 之间的 gap 分段进行的。每个 gap 就是 read 上两个相邻 anchor 之间的区域，需要单独跑一次 WFA。

WFA 算法在计算过程中需要维护一个 DP 矩阵，按 penalty score 分层，每一层存储对角线上的 match、insertion、deletion 状态。这个矩阵不能完全放在寄存器里，必须有一块工作内存来存放，论文中估计每个 gap 需要约 40 KB 的 WFA buffer。

为什么传统方式每个 gap 都要单独分配和释放？​

在逐阶段执行的 baseline 中，Alignment 阶段是独立处理每个 gap 的：

  1. 取一个 gap；
  2. 为它申请一块 40 KB 的 WFA buffer；
  3. 在这块 buffer 上跑 WFA，算出这个 gap 的比对；
  4. 比对完成，这块 buffer 就没用了，释放掉；
  5. 处理下一个 gap，再申请一块新的 40 KB buffer。

因为一条 read 可能有很多 inter-anchor gap，NgapsN_{\mathrm{gaps}} 很大，所以这个“申请—使用—释放”的过程会重复成千上万次。每次申请和释放都是对同样大小的内存块操作，这就是 allocation churn（分配抖动）。

为什么 allocation churn 是个大问题？​

① 内存管理开销大​

频繁申请和释放 40 KB 的大块内存，会给内存分配器带来很大压力。分配器需要维护空闲列表、合并碎片、可能还要向操作系统申请新的物理页。这些操作本身就要消耗 CPU 时间，在加速器中则可能由内存控制器或 DMA 引擎承担，增加控制开销。

② 内存碎片化​

每次分配和释放同样大小的块，虽然理论上可以重用，但如果分配释放的时序交错，空闲块可能被切碎，导致后续分配需要更大的连续空间时找不到，只能向 DRAM 申请新页。这会进一步增加 DRAM 访问。

③ 数据必须往返 DRAM​

在 baseline 中，WFA buffer 是放在片外 DRAM 里的工作内存。每次为一个 gap 分配 buffer，意味着要：

  • 从 DRAM 读入初始数据；
  • WFA 计算过程中反复读写这块 buffer；
  • 算完后把结果写回，然后释放。

因为 buffer 不在片上，所有中间 DP 状态都要经过 DRAM。而 WFA 的计算模式需要频繁访问不同 penalty level 的矩阵值，所以对这块 buffer 的读写次数非常多。论文 profiling 显示，对于 10 Kbp 的 read，每条 query 平均产生 1205 MB 的累计内存占用，其中 96.4% 来自 alignment 阶段 WFA buffer 的循环分配。

④ 总流量巨大​

单看一个 gap 的 buffer 是 40 KB，好像不大。但一条 read 有大量 gap，每个 gap 都要独立走一遍“分配→读写→释放”，累积起来就是：

Ngaps×SwfaN_{\mathrm{gaps}} \times S_{wfa}

其中 Swfa=40S_{wfa} = 40 KB。NgapsN_{\mathrm{gaps}} 可能成百上千，所以总 DRAM 流量会达到数百 MB 甚至 GB 级别。这就是 baseline 中 DRAM 流量的主要来源。

融合设计如何解决？​

PanGaea 把整个流水线融合成 tile。在一个 tile 内，所有 gap 不再各自申请独立的 WFA buffer，而是共享一个固定的 WFA buffer 池。

  • 这个池子常驻在片上 GLB 或 local scratchpad 中；
  • 每个 gap 按顺序复用同一块 buffer；
  • 不需要反复向 DRAM 申请和释放；
  • 中间 DP 矩阵留在片上，不经过 DRAM。

这样，原来公式 (3) 中的 NgapsSwfaN_{\mathrm{gaps}} S_{wfa} 项就被消除了。DRAM 只需要读入 anchors，写出最终的 CIGAR 结果。Allocation churn 消失，DRAM 流量大幅下降。

一句话总结​

每个 gap 单独分配和释放 40 KB WFA buffer，是因为传统逐阶段执行把每个 gap 当作独立任务，需要临时工作内存；由于 gap 数量巨大，这种反复申请释放造成 allocation churn，并且所有中间 DP 状态都要经过 DRAM，成为 alignment 阶段 DRAM 流量的主要来源。融合设计让所有 gap 共享一块常驻片上的 WFA buffer，从而消除了这种抖动和多余的 DRAM 访问。