Skip to main content

3. Graph Path Finder Engine

C. Graph Path Finder Engine 详细介绍​

这一节介绍了 Graph Path Finder (GPF) 引擎，它是 Locus 加速器中专门负责 图链接（Graph Chaining, GC）阶段最短路径搜索的硬件模块。GPF 的核心任务是：当线性链接产生的链（chain）需要跨 segment 边界扩展时，判断源 segment 能否到达目标 segment，并计算它们之间的图路径距离。这个距离信息用于给跨 segment 转换打分，同时也用于识别需要插入的中间顶点，从而完成 bridging，为后续比对阶段生成完整的 vertex-by-vertex 路径。

下面从功能背景、搜索算法、硬件组成、并发执行和设计意义几个方面详细展开。

1. 功能背景：为什么需要 GPF​

在 S2G mapping 的图链接阶段，线性链接只能在同一 segment 内连接 anchors，无法跨越 segment 边界。而在泛基因组图中，遗传变异被编码为 bubble：从入口顶点分叉成多条替代路径，再在出口顶点汇合。因此，一条链可能需要从某个 segment 上的链连接到另一个 segment 上的链。

GPF 需要解决两个问题：

  1. 是否存在有效路径：源 segment sis_i 能否到达目标 segment sjs_j？
  2. 路径距离是多少：如果存在，最短路径的图距离是多少？

这个距离用于计算图链接的转换分数。论文在 Stage 3 中描述：GC 对每对候选 local chains 调用 shortest-kk path query，转换分数会惩罚实际图路径距离与查询坐标隐含的期望距离之间的差距。此外，GPF 还要识别中间图顶点，用于在 Filtering and bridging 阶段插入到连续链之间，生成完整路径。

在 bubble 区域，源和目标之间可能存在多条替代路径，最短-kk 算法必须从 DRAM 加载所有相关子图数据。因此，GPF 的效率直接影响图链接阶段的性能和 DRAM 流量。

2. 搜索算法：基于优先队列的最短路径搜索​

GPF 实现的是基于优先队列的最短路径搜索[53]，本质上是一种 Dijkstra 风格的搜索，但支持提取 kk 条最短路径。

具体流程：

  • 对每个查询，引擎从源顶点到目标顶点探索路径。
  • 维护一个候选集合，按累积距离排序。
  • 搜索终止条件有两个：
    1. 已经提取出 kk 条最短的源到目标路径。默认 k=4k = 4，与论文 Section II-B 中描述的 shortest-kk 查询一致。
    2. 当前距离超过一个阈值。这个阈值通常是基于坐标估计的 2 倍（typically 2×2\times the coordinate-based estimate）。

这种设计在精度和开销之间取得平衡：只探索有希望的路径，避免在 bubble 密集区域进行组合爆炸式的全路径枚举。

3. 硬件组成：四个关键组件​

GPF 引擎由四个硬件组件构成，分别负责优先队列管理、距离记录、邻接表缓存和路径重建。

3.1 二叉堆优先队列​

  • 功能：维护待探索的顶点，按累积距离排序，支持插入和提取最小值。
  • 硬件管理：
    • 插入（insert）：2 个周期
    • 提取最小值（extract-min）：3 个周期
  • 容量：支持 256 个条目。
  • 这是搜索的核心数据结构，决定了 GPF 的吞吐能力。

3.2 距离表（Distance Table）​

  • 功能：记录已访问顶点及其最优成本。
  • 作用：防止冗余探索。当搜索再次到达某个顶点时，如果新路径的距离不优于已记录的最优成本，就可以跳过，从而减少不必要的图遍历和 DRAM 访问。

3.3 弧缓存（Arc Cache）​

  • 功能：缓冲最近访问的邻接表（adjacency lists）。
  • 作用：图搜索过程中会频繁读取邻接表。弧缓存把这些数据保留在片上，减少对 DRAM 的重复访问，尤其在 bubble 区域多条替代路径共享部分子图时，缓存能显著降低 topology 流量。

3.4 路径重建单元（Path Reconstruction Unit）​

  • 功能：当找到目标路径后，通过距离表回溯，重建从源到目标的顶点序列。
  • 输出：发出 vertex sequence，供后续 bridging 和比对使用。
  • 这一步把搜索得到的距离信息转化为实际的图路径，用于在连续链之间插入中间顶点。

4. 并发执行：与 PE 阵列重叠​

GPF 引擎的一个重要设计特点是与 PE 阵列并发执行。论文指出：

  • 当 PE 阵列正在为 anchor batch b+1b + 1 计算线性链接时，GPF 可以同时处理来自 batch bb 的图查询。
  • 这种重叠隐藏了 GPF 的延迟，对于图链接不在关键路径上的 tile 尤其有效。
  • 但是，在 bubble 密集区域，GPF 可能成为瓶颈。此时，控制器会节流 PE 吞吐，以维持正确的执行顺序和阶段间的依赖关系。

这种并发设计让 GPF 的搜索延迟不会直接暴露在关键路径上，同时通过节流机制保证在 GPF 压力大时不会出现数据依赖错误。

5. 与其他组件的关系​

  • 与 RMQ 引擎的区别：
    • RMQ 引擎用于线性链接阶段，通过线段树在 O(log⁡n)O(\log n) 时间内筛选候选前驱 anchor，减少 PE 阵列的计算量。
    • GPF 引擎用于图链接阶段，执行图上的最短路径搜索，处理跨 segment 和 bubble 的路径查询。
  • 与 PE 阵列的协作：
    • PE 阵列的 Mode 1（Chaining）会复用 GPF 提供的图路径距离来计算跨 segment 转换分数。
    • PE 阵列的 Mode 3（WFA edit distance）用于验证通过 bubble 的候选路径，而 GPF 先找到候选路径。
  • 与 Traceback Engine 和 GLB 的关系：
    • GPF 的搜索结果（距离和顶点序列）会写入 GLB 的 IR Bank，供后续阶段使用。
    • Traceback Engine 最终生成 CIGAR 字符串，而 GPF 提供的是路径级别的信息。

6. 设计意义总结​

GPF 引擎是 Locus 实现完整 S2G 融合流水线的关键组件之一，其设计意义在于：

  1. 支持跨 segment 图链接：解决线性链接无法跨越 segment 边界的问题。
  2. 处理 bubble 多路径：通过 shortest-kk 搜索和距离阈值，在 bubble 区域探索替代路径，同时控制搜索开销。
  3. 降低 DRAM 访问：通过弧缓存和距离表减少重复的邻接表读取和冗余探索。
  4. 隐藏搜索延迟：与 PE 阵列并发执行，在非关键路径上隐藏 GPF 延迟；在瓶颈时通过节流维持正确顺序。
  5. 为 bridging 和比对提供基础：路径重建单元输出的顶点序列用于插入中间顶点，生成完整路径，供后续 WFA 比对使用。

总之，GPF 引擎在 Locus 架构中承担了图链接阶段最复杂、最不规则的计算任务，它的高效实现直接决定了 Locus 在 bubble 密集区域的性能和 DRAM 流量表现。