Skip to main content

2.1.1 Tiling Object Function

这个公式是 PanGaea 论文第 3.1 节中用于求解最优 Tiling 因子的优化问题模型。它的核心目的是：在片上内存（GLB）容量的限制下，寻找最佳的瓦片（Tile）大小，使得融合执行时的 DRAM 总访问量最小。

逐项拆解如下：

1. 目标函数：min⁡TaDRAMfused(Ta)\min_{T_a} \mathrm{DRAM}_{\mathrm{fused}}(T_a)​

  • TaT_a：决策变量，代表每个 Tile 中处理的 anchor 数量（即 Tiling 因子）。
  • DRAMfused(Ta)\mathrm{DRAM}_{\mathrm{fused}}(T_a)：融合执行模式下的总 DRAM 访问量。
  • 含义：我们希望找到一个最优的 TaT_a，使得融合流水线的 DRAM 流量降到最低。

回顾论文公式 (5)： DRAMfused(T)=Na⋅Sa+T⋅Ngcglue⋅Scigar\mathrm{DRAM_{fused}}(T) = N_{a}\cdot S_{a} + T\cdot N_{gc}^{\mathrm{glue}}\cdot S_{cigar} 其中 TT 是 Tile 的总数（T≈Na/TaT \approx N_a / T_a）。

  • 第一项 Na⋅SaN_a \cdot S_a 是固定的（读入所有 anchor 的流量）。
  • 第二项 T⋅Ngcglue⋅ScigarT \cdot N_{gc}^{\mathrm{glue}} \cdot S_{cigar} 是写回 CIGAR 结果的流量。
  • 因为 TT 与 TaT_a 成反比（T≈Na/TaT \approx N_a / T_a），所以 TaT_a 越大，Tile 总数 TT 越小，第二项 DRAM 输出流量就越小。
  • 因此，从 DRAM 流量最小化的角度来看，我们希望 TaT_a 越大越好。但 TaT_a 不能无限大，因为有下面的约束。

2. 约束条件：s.t.WS(T)≤CGLBs.t. \quad WS(T) \leq C_{\mathrm{GLB}}​

  • WS(T)WS(T)：Working Set，即执行当前 Tiling 方案时，片上需要驻留的工作集总大小（包括 anchors、中间产生的 linear chains、graph chains、以及 WFA buffer 等）。
  • CGLBC_{\mathrm{GLB}}：Global Buffer 的总容量。
  • 含义：一个 Tile 内的所有中间数据必须全部能装进片上的 GLB 中。如果 TaT_a 太大，Tile 内的 anchor 太多，产生的中间数据就会超出 GLB 容量，导致数据溢出到 DRAM，从而破坏融合的意义，DRAM 流量反而会急剧上升。
  • 因此，这是一个典型的带约束的优化问题：在 GLB 装得下的前提下，尽可能让 TaT_a 大。

3. 离散约束：Ta,Nwfa∈Z+T_a, N_{\mathrm{wfa}} \in \mathbb{Z}^+​

  • Z+\mathbb{Z}^+：正整数集合。
  • TaT_a：Tile 大小必须是正整数，不能处理半个 anchor。
  • NwfaN_{\mathrm{wfa}}：WFA buffer 的数量或大小因子，也必须是正整数。
  • 含义：硬件资源分配和数据分块必须是离散的整数，不能是小数。

直观理解​

这个公式在说：

找到一个最大的 TaT_a（正整数），使得一个 Tile 处理完这些 anchors 后，产生的所有中间数据（线性链、图链、WFA 矩阵等）能够完全塞进容量为 CGLBC_{\mathrm{GLB}} 的片上全局缓冲区里。在这个前提下，让 DRAM 访问量最小。

求解逻辑​

在实际优化中，WS(T)WS(T) 通常是 TaT_a 的单调递增函数（Tile 越大，中间数据越多）。

  1. 如果 TaT_a 太小：GLB 肯定装得下，但 Tile 数量 TT 变多，导致频繁的 Tile 切换和输出写回，DRAM 流量略增。
  2. 如果 TaT_a 太大：WS(T)>CGLBWS(T) > C_{\mathrm{GLB}}，数据溢出，DRAM 流量爆炸。
  3. 最优解：通常是在满足 WS(T)≤CGLBWS(T) \leq C_{\mathrm{GLB}} 的边界上，取最大的那个整数 TaT_a。这也解释了为什么论文后面会采用 BFS + 装箱策略来对图进行划分，目的就是为了在限制 LL（每个 bin 的最大碱基数）的前提下，尽量紧凑地填满 GLB。