Skip to main content

2.3 Graph Path Finder (GPF) Engine

4.1 节中的 Graph Path Finder (GPF) Engine 是 PanGaea 加速器里专门用来加速 Graph Chaining（图链） 阶段的硬件模块。它的核心任务是：在 pangenome graph 上，快速计算两条线性链端点之间的最短路径，判断它们能否通过变异泡连通，从而把局部链跨顶点连接成候选图路径。

下面从背景、挑战、算法、硬件实现和工作流程几个角度来解释。

1. 为什么需要 GPF 引擎？​

在 S2G 流水线中，Linear Chaining 只在同一个图顶点内部连接种子，输出局部链。
但 read 通常跨越多个顶点，所以需要 Graph Chaining 把不同顶点的局部链连起来。

图链阶段要解决的核心问题是：

给定一条局部链的终点（源顶点）和另一条局部链的起点（目标顶点），它们在图上是否可达？如果可达，最短路径是什么？路径上经过哪些顶点和变异泡？

这个问题本质上就是图上的最短路径搜索。
在 pangenome graph 中，图结构不规则，有分支、变异泡、长距离边。
在复杂区域，图遍历往往会主导整个图链阶段的运行时间。
如果只用通用 CPU 或 GPU 做，效率低、延迟高。
所以 PanGaea 设计了一个专用硬件引擎 GPF，来加速这个最短路径搜索过程。

2. GPF 引擎的核心功能​

论文中描述：

“The GPF engine accelerates the graph chaining stage by computing shortest paths between linear-chain endpoints across graph vertices. It implements Dijkstra's shortest-kk algorithm using a priority-queue-based approach.”

翻译成通俗的话：

  • 输入：图链阶段需要连接的两条局部链的端点，即源顶点和目标顶点。
  • 任务：在 pangenome graph 上找一条从源到目标的最短路径，或者找前 kk 条最短路径（shortest-kk）。
  • 方法：使用 Dijkstra 算法 的变体，配合优先队列来管理待探索的顶点。
  • 输出：候选路径，用于验证两条局部链能否跨顶点连接。

为什么是 shortest-kk？
因为图链阶段可能有多条候选路径都能连通，需要保留前几条最优的，供后续过滤和打分。
Dijkstra 本身是找单源最短路径，但这里只需要从源到目标的局部搜索，并且会剪枝，所以实际是限定范围的 Dijkstra。

3. 算法细节：Dijkstra + 优先队列 + 剪枝​

Dijkstra 算法回顾​

Dijkstra 用于在带权图中找单源最短路径。
基本步骤：

  1. 把源顶点加入优先队列，距离设为 0。
  2. 每次从优先队列取出当前距离最小的顶点。
  3. 遍历它的邻居，如果通过它到邻居的距离更短，就更新邻居距离，并把邻居加入优先队列。
  4. 重复直到队列为空或找到目标。

在 GPF 中，图的边权可能代表序列长度、变异代价或图距离。
目标是找到从源到目标的最小代价路径。

优先队列的作用​

优先队列（通常用最小堆实现）保证每次取出的都是当前已知距离最小的顶点。
这是 Dijkstra 正确性的关键。
在硬件中，优先队列可以用堆控制器 + 比较器实现，论文 Table 1 中 GPF Engine 的 “Priority Queue Logic” 面积约 0.1540 mm²。

剪枝：距离阈值​

论文提到：

“For each graph chain, the engine explores candidate paths from source to destination vertices, pruning branches that exceed predefined distance thresholds to constrain search complexity.”

意思是：
搜索时，如果某条分支的累计距离已经超过一个预设阈值，就把它剪掉，不再继续探索。
因为图链阶段并不需要全局最短路径，只需要找到足够好的、能验证可达性的路径。
剪枝可以大幅减少搜索空间，降低延迟和能耗。

4. 关键硬件组件​

距离表（Distance Table）​

论文：

“The distance table (a 16 KB SRAM) in the Path Reconstruct unit records visited vertices and their optimal costs, thereby avoiding redundant traversal of graph bubbles.”

距离表是一个 16 KB 的 SRAM，用来记录：

  • 哪些顶点已经被访问过；
  • 到达每个顶点的当前最优代价（距离）。

作用：

  • 避免重复访问：如果某个顶点已经以更优代价访问过，就不需要再探索；
  • 避免冗余遍历变异泡：变异泡可能有多条路径，距离表帮助快速判断哪条更优；
  • 支持路径重建：记录前驱顶点，最终可以回溯出完整路径。

路径重建单元（Path Reconstruct）​

除了距离表，还有逻辑用于根据距离表回溯路径。
当找到目标顶点后，从目标反向沿着前驱指针回到源，就得到一条候选路径。
这条路径就是图链阶段用来连接两条局部链的“桥”。

优先队列逻辑​

用堆控制器和比较器实现，管理待探索的顶点集合。
每次取出距离最小的顶点进行扩展。

弧缓存（Arc Cache）​

论文 Table 1 中还有 “Arc Cache 8 KB vertex cache”。
用于缓存顶点的邻接表（出边），减少访问 GLB 或 DRAM 的次数。
因为图遍历会频繁访问邻居，缓存能提高效率。

5. GPF 引擎的工作流程​

结合论文，GPF 处理一条图链的大致流程是：

  1. 接收源顶点和目标顶点：来自当前 tile 中需要连接的两条局部链的端点。
  2. 初始化：源顶点距离设为 0，加入优先队列；距离表清空或初始化。
  3. 循环搜索：
    • 从优先队列取出距离最小的顶点 uu；
    • 如果 uu 是目标顶点，停止搜索，进入路径重建；
    • 否则，遍历 uu 的邻居 vv；
    • 计算通过 uu 到 vv 的新距离；
    • 如果新距离小于距离表中 vv 的当前最优距离，且不超过剪枝阈值：
      • 更新距离表；
      • 记录前驱；
      • 把 vv 加入优先队列。
  4. 路径重建：从目标顶点沿前驱回溯到源，得到一条候选路径。
  5. 输出：把路径信息（经过的顶点、边、代价）交给后续阶段，用于构建图链。

由于一个 tile 内可能有很多对局部链需要连接，GPF 会重复执行上述过程。
但距离表可以在多次搜索间复用部分信息，或者每个图链独立搜索。

6. 与其他模块的协作​

  • GLB（Global Buffer）：GPF 需要访问图拓扑（顶点序列、邻接表），这些数据存在 Graph Topology Bank 中。GPF 通过 NoC 从 GLB 读取图数据。
  • PE 阵列：PE 阵列负责线性链和 WFA 对齐等密集计算；GPF 是独立引擎，专门处理图遍历这种不规则、分支密集的搜索。
  • 控制单元：主控制器调度 GPF 引擎，在合适的时机启动图链搜索。
  • Traceback Logic：GPF 输出路径后，后续对齐阶段可能用到这些路径信息，但 CIGAR 由 Traceback 生成。

7. 直观比喻​

把 pangenome graph 想象成一张城市地图，顶点是地点，边是道路，变异泡是环岛或岔路口。
图链阶段要判断：从 A 地到 B 地有没有路？哪条路最短？
GPF 引擎就像一个导航算法硬件加速器：

  • 优先队列 = 待探索路口的优先列表；
  • 距离表 = 记录到每个路口的最短距离，避免绕路；
  • 剪枝 = 如果某条路已经绕太远，就不走了；
  • 路径重建 = 找到目的地后，回溯出完整路线。

这样就能快速把两条局部链连接起来，形成完整的候选图路径。

8. 总结​

GPF 引擎是 PanGaea 中专用于图链阶段最短路径搜索的硬件模块。
它用 Dijkstra + 优先队列 + 剪枝，在 pangenome graph 上快速寻找局部链端点之间的候选路径。
距离表记录已访问顶点和最优代价，避免冗余遍历；路径重建单元回溯出完整路径。
这样就把图链阶段最耗时的图遍历操作加速了，使得整个融合流水线能够高效运行。

一句话：GPF 引擎就像图上的导航加速器，用硬件实现带剪枝的 Dijkstra 搜索，快速判断两条局部链能否跨顶点连通，并找出最优路径。