Skip to main content

2.2 Tiling Strategy of S2G Mapping

3.2 节 Tiling Strategy of S2G Mapping 的核心是：
为了在片上 GLB 中完成图链阶段的融合计算，必须把庞大的 pangenome graph 切成能放进 GLB 的小块，同时尽量让每一块内部连接紧密、跨块边少。
但 pangenome graph 有自己特殊的结构，不能直接用传统图划分算法，所以作者提出了 BFS + 装箱 的划分策略。

下面分几层解释。

1. 为什么需要图划分？​

3.1 节已经说明：融合执行要把 anchors 分成 tile，每个 tile 内跑完线性链、图链、对齐，中间数据留在 GLB。
但图链阶段需要访问 pangenome graph 的拓扑和顶点序列。
整个图有 31 亿碱基对，不可能全放片上。
所以必须把图也切成小块，每个块能装进 GLB，并且处理某个 tile 的 anchors 时，主要访问对应的图块。

这就是 3.2 节要解决的问题：
如何把 pangenome graph 划分成适合片上处理的分区（bin），同时满足 GLB 容量约束。

2. 图划分面临哪些挑战？​

论文指出三个难点：

  1. 图极度稀疏，主要是线性拓扑
    pangenome graph 大部分区域就是一条线，只有少数变异泡产生分支。
    传统图划分算法可能过度复杂，或者把线性区域切碎。

  2. 顶点包含变长 DNA 序列
    每个顶点不是一个碱基，而是一段长度不等的 DNA 片段。
    划分时不能只数顶点个数，必须考虑每个顶点的序列长度。

  3. 存在长距离依赖
    有些边连接相距很远的顶点，如果划分不当，会导致跨分区通信频繁，破坏片上局部性。

传统算法如 METIS 目标是最小化跨分区边，但：

  • 在大 pangenome 图上扩展性差；
  • 不考虑节点序列长度异质性；
  • 可能产生很多长距离跨区边。

所以作者放弃了 METIS，改用更轻量、更贴合图结构的方法。

3. 提出的方法：BFS + 装箱​

形式化描述​

把 pangenome graph 表示为：

G=(V,E,σ(V))G = (V, E, \sigma(V))

其中：

  • VV：顶点集合；
  • EE：边集合；
  • σ(v)\sigma(v)：顶点 vv 对应的 DNA 序列长度。

每个分区（bin）有碱基容量上限 LL，要求：

∑vi∈ρσ(vi)≤L\sum_{v_i \in \rho} \sigma(v_i) \leq L

也就是一个 bin 内所有顶点的序列长度之和不能超过 LL。
LL 由 GLB 容量决定。

第一步：BFS 分组​

从某个种子顶点开始，做广度优先搜索，把空间上相邻的顶点聚在一起。
因为 pangenome graph 主要是线性的，BFS 会沿着线性路径扩展，宽度有限，不会一下子扩散到很远的地方。
这样得到的分区天然具有空间局部性：分区内的顶点在图上彼此靠近，跨分区的边少，长距离依赖也被限制在分区边界。

而且 BFS 可以从多个种子顶点并行开始，同时构建多个独立分区。
这提高了划分的并行性，适合硬件加速。

第二步：修改的装箱​

BFS 遍历过程中，维护一个当前 bin。
每遇到一个顶点，检查把它加入当前 bin 后，总碱基数是否超过 LL：

  • 如果没超过，就贪心地放进去；
  • 如果超过了，就结束当前 bin，开一个新 bin，继续装。

这里的关键是：按序列长度而不是顶点个数来装箱。
因为不同顶点长度差异很大，如果按顶点数划分，可能一个 bin 里全是短顶点，另一个 bin 里一个长顶点就撑爆 GLB。
按碱基总数约束，才能保证每个 bin 真正能放进片上缓冲。

4. 这样划分的好处​

  1. 减少跨分区通信
    BFS 让相邻顶点在同一分区，图链阶段访问的顶点大多落在同一个 bin 内，减少跨分区边，降低 DRAM 访问。

  2. 尊重 GLB 容量
    每个 bin 的碱基总数不超过 LL，保证一个分区的图序列能完整加载到 GLB，不会溢出。

  3. 适应顶点长度异质性
    按序列长度装箱，避免长顶点导致分区过大。

  4. 并行构建
    多个 BFS 种子可以同时开始，并发生成独立分区，适合硬件并行。

  5. 与 tiling 配合
    图分区之后，处理一个 anchor tile 时，只需要把对应的图分区加载到 GLB。
    由于分区空间局部性好，图链阶段的大部分访问都在片上进行，从而支持 3.1 节的融合 tiling，最大化 tile 大小，最小化 DRAM 流量。

5. 和 3.1 节的关系​

3.1 节给出了优化问题：

min⁡TaDRAMfused(Ta)s.t.WS(T)≤CGLB\min_{T_a} \mathrm{DRAM}_{\mathrm{fused}}(T_a) \quad s.t. \quad WS(T) \leq C_{\mathrm{GLB}}

其中 WS(T)WS(T) 是 tile 的工作集大小，必须不超过 GLB 容量。
3.2 节的图划分就是让 WS(T)WS(T) 可控的关键手段：
把图切成小 bin，每个 bin 能装进 GLB，这样处理一个 tile 时，只需要加载少量图分区，工作集就不会超标。
因此，3.2 节是 3.1 节优化模型在 pangenome graph 上的具体落地策略。

一句话总结​

3.2 节提出用 BFS 按图拓扑邻近性分组，再用按碱基长度的贪心装箱把顶点装入容量受限的 bin，从而把庞大的 pangenome graph 划分成适合片上 GLB 的小分区。这样既保证了图链阶段的局部性，减少了跨分区通信，又满足了 GLB 容量约束，使 3.1 节的融合 tiling 成为可能。