1. Proposed Graph Partitioning

B. Proposed Pangenome Graph Partitioning 详细介绍

这一节提出了 Reflexive Bubble-Centric Partitioning (RBCP)，一个专门面向泛基因组图的划分算法。其核心目标是：在把图划分成适合片上执行的 tile 时，保持 bubble（变异气泡）的完整性，同时平衡各 tile 的容量，并最大化片上数据局部性，减少跨 tile 通信和 DRAM 访问。

下面从动机、图拓扑特征、算法三阶段、容量约束、复杂度以及图4走查几个方面详细展开。

---

1. 动机：为什么传统图划分不适用

论文指出，现有加速工作（如 TALCO、GenDP、SeGraM）主要关注算法优化或指令级并行，没有充分利用泛基因组图在数据划分层面的数据并行性。更关键的是，传统图划分算法通常以最小化边割或顶点割为目标，但这一目标对泛基因组图并不充分：

• 泛基因组图中，遗传变异被编码为 bubble：从单一入口顶点分叉成多条替代路径，再在单一出口顶点汇合。
• 如果盲目最小化割，可能会把一个 bubble 的不同替代路径切到不同分区，导致：
  • 跨分区通信增加；
  • bubble 内部强依赖被破坏；
  • 片上数据复用减少；
  • off-chip DRAM 流量上升。

因此，泛基因组图需要一种 bubble-aware 的划分算法，而不是传统的最小割划分。

---

2. 泛基因组图的拓扑特征与分区挑战

论文对比了传统图（如社交网络、推荐网络）和泛基因组图：

• 传统图：通常服从幂律度分布，存在少量高度连接的 hub 节点。
• 泛基因组图：继承染色体 DNA 的近线性拓扑，绝大多数节点形成长而不分支的序列链；只在遗传变异位点出现局部分支，形成 bubble 结构，然后重新汇合到主路径。

这种拓扑带来两个相互冲突的需求：

1. 线性区域：

   • 适合简单、连续的内存分配；
   • 空间局部性高；
   • 任意切分带来的通信开销可忽略。

2. Bubble 区域：

   • 入口和出口节点之间存在长程依赖；
   • 任何穿过 bubble 的分区边界都会导致替代路径之间的跨 tile 通信；
   • 降低片上复用，增加 off-chip DRAM 流量。

此外，bubble 的大小差异极大：从仅几个碱基对的单核苷酸多态性（SNP），到跨越数千碱基的结构变异。这使得统一的分区策略无效。

这些特征共同要求一个满足以下条件的分区方案：

1. 将 bubble 视为不可分割的单元；
2. 在 tile 决策中考虑 bubble 大小；
3. 动态平衡 tile 利用率，而不是固定分配。

---

3. RBCP 算法总体思路

RBCP 基于 DRAM access model，利用泛基因组图的独特拓扑，区分线性序列区域和变异诱导的 bubble 区域。其目标是：

• 最大化片上数据局部性；
• 最小化长程依赖引起的通信。

RBCP 分为三个阶段：

1. 检测所有 bubble 结构；
2. 选择 tile 中心：围绕大的代表性 bubble 锚定每个分区；
3. 分配剩余节点：用距离驱动的所有权机制，把每个剩余节点分配到恰好一个 tile。

下面分别详细说明。

---

4. 阶段一：检测 Bubble 并收缩为超级节点

RBCP 采用 superbubble detection 算法 [31] 来识别所有 bubble。Superbubble 定义为一个子图，从单一入口顶点分叉成多条替代路径，再在单一出口顶点汇合。

识别后，每个 bubble 被收缩成一个单一的超级节点（supernode）。收缩后的超级节点长度等于该 bubble 内所有节点的序列长度之和。

这一步骤确保：

• 没有任何变异区域会被切分到不同 tile；
• bubble 内部的长程依赖被保留在同一个单元内。

图4 Panel 1 展示了检测结果：三个 bubble $B_0=24\mathrm{bp}$，$B_1=9\mathrm{bp}$，$B_2=4\mathrm{bp}$，并分别求和其序列长度。

---

5. 阶段二：选择分区中心

收缩 bubble 后，RBCP 选择多个中心 bubble 作为分区中心，以支持并行划分。

选择规则：

• 优先选择较大的 bubble 作为中心，因为大 bubble 对局部性和负载影响更大。
• 中心之间必须至少间隔 $M_{cap}/2$，其中 $M_{cap}$ 是片上 buffer 容量。这样相邻 tile 不会竞争同一区域。
• 图4 Panel 2 中，$B_0$ 和 $B_1$ 被选为中心，它们之间的拓扑距离 $d_{topo}=19\mathrm{bp}$，满足 $M_{cap}/2 = 17.5\mathrm{bp}$ 的间距规则。$B_2$ 因为 tile 预算已满足而未被选为中心。

---

6. 阶段三：容量受限的多源扩展

从所有中心 bubble 超级节点同时出发，RBCP 执行容量受限的多源 Dijkstra 扩展 [52]，沿着图的边向两个方向扩展。

具体规则：

• 每个未认领的单元被最近且有剩余容量的中心认领。
• 距离定义为从中心沿路径累积的序列长度。
• 如果一个中心加入某个单元会导致其 tile 超过 $M_{cap}$，则该中心拒绝该单元，并停止在该方向上的扩展。
• 被拒绝的单元仍然有资格被它的第二近的中心认领。
• 因此，RBCP 需要按中心分别跟踪扩展距离，而不是全局统一跟踪。
• 如果一个单元没有任何现有 tile 能接受它，它就成为一个新 tile 的种子，开启新一轮扩展。
• 每一轮为每个连通分量播下一个新 tile，未认领集合严格缩小，循环必然终止。

这一机制保证：

• 每个 tile 都在容量 $M_{cap}$ 以内；
• 每个 tile 保持连通；
• 所有 bubble 保持完整；
• 每个节点恰好属于一个 tile。

---

7. 算法复杂度与假设

• 复杂度：RBCP 是一次性离线步骤，代价为 $O(K(|V|+|E|)\log|V|)$。在近线性的泛基因组拓扑上，任何节点附近落在 $M_{cap}$ 范围内的中心数量是常数，因此实际开销接近单次多源扩展。
• 假设：没有单个收缩后的 bubble 超过 $M_{cap}$。阶段一的合并规则不会产生这样的 bubble；但如果存在一个原始 superbubble 大于 $M_{cap}$，则需要将其分解为替代路径。这是唯一会破坏 bubble 完整性的情况。

---

8. 图4走查：八单元示例

图4用 $M_{cap}=35\mathrm{bp}$ 的例子完整展示了 RBCP 的三个阶段。

Panel 1：检测 bubble 并求和长度

• 识别出三个 bubble：$B_0=24\mathrm{bp}$，$B_1=9\mathrm{bp}$，$B_2=4\mathrm{bp}$。

Panel 2：收缩 bubble 并选择分区中心

• 每个 bubble 收缩为一个不可分割单元，长度为其节点序列长度之和。
• 得到链：$5 \rightarrow 6 \rightarrow B_0(24) \rightarrow u(9) \rightarrow 10 \rightarrow B_1(9) \rightarrow 3 \rightarrow B_2(4)$，总长 $70\mathrm{bp}$。
• 选最大的两个 bubble $B_0$ 和 $B_1$ 作为 Partition 0 和 Partition 1 的中心。
• 它们之间 $d_{topo}=19\mathrm{bp}$，满足 $M_{cap}/2=17.5\mathrm{bp}$ 的间距规则。
• $B_2$ 未被选为中心，因为 tile 预算已满足。

Panel 3：容量受限多源扩展

• 每个分区认领最近的未认领单元，距离为从中心沿路径累积的序列长度。
• 争议单元 $u$ 距 Partition 0 为 $9\mathrm{bp}$，距 Partition 1 为 $19\mathrm{bp}$。
• Partition 0 已经持有 $B_0$ 和相邻的 $6\mathrm{bp}$ 单元，总计 $30\mathrm{bp}$。若加入 $u$，则 $30+9=39\mathrm{bp}$，超过 $M_{cap}=35\mathrm{bp}$。
• 因此 Partition 0 拒绝 $u$，转而认领其远端的 $5\mathrm{bp}$ 单元，最终关闭在 $35\mathrm{bp}$。
• Partition 1 在自己的扩展到达 $u$ 时认领它。
• Panel 4 给出结果：两个 tile 恰好都是 $35\mathrm{bp}$，且所有三个 bubble 保持完整。
• 如果只用距离扩展，Partition 0 会接受 $u$，关闭在 $44\mathrm{bp}$，导致 tile 溢出。

Panel 4：分配每个节点到唯一 tile

• 最终每个节点恰好属于一个 tile；
• 每个 bubble 完整；
• 每个 tile 不超过 $M_{cap}$。

---

9. 该分区算法的作用

RBCP 为后续 Locus 架构的融合执行提供了基础：

• 保持 bubble 完整性：避免跨 tile 通信，减少 DRAM 访问；
• 容量约束：确保每个 tile 能放入片上 buffer $M_{cap}$；
• 多中心并行扩展：支持负载均衡和并行划分；
• 动态种子机制：自动覆盖全图，不需要预先固定分区数；
• 与数据流配合：RBCP 识别的 bubble 信息可用于后续的 BPT（bubble-topology prefetching table），把 bubble 内部路径映射到专用 PE 行，进一步提升 PE 利用率。

总之，B 节提出的 RBCP 是 Locus 实现高吞吐、低 DRAM 流量的关键算法组件之一。