Skip to main content

5. Proposed Mapping and Dataflow

E. Proposed Mapping and Dataflow 详细介绍​

这一节提出了 Locus 的映射与数据流策略，目的是解决泛基因组图中两个关键问题：

  1. 长距离图依赖：bubble 的入口和出口之间存在跨越多条替代路径的长程依赖，如果映射不当，会导致 PE 之间频繁通信或空闲。
  2. 资源利用不足：bubble 内部不同替代路径的长度差异很大，若把每条路径固定映射到独立计算资源，短路径完成后其资源会闲置，而长路径仍在运行，造成 PE 利用率下降。

核心思想是：在宏观层面用 RBCP 保持 bubble 完整性，在微观层面用 BPT 把 bubble 路径共定位到专用 PE 行，并用顺序节点填充空闲周期，从而实现负载均衡和更高的 PE 利用率。

下面从宏观与微观两个层面、BPT 的构建、图 6(a) 示例、数据流重配置几个方面详细展开。

1. 宏观与微观两个层面的协同​

论文将映射与数据流设计分为两个层次：

  • 宏观层面（tile 形成）：由 RBCP（Reflexive Bubble-Centric Partitioning）完成。RBCP 在划分图时，把每个 bubble 收缩成一个不可分割的超级节点，确保 bubble 不会被切分到不同 tile。这样，bubble 内部的长程依赖被保留在同一个 tile 内，避免了跨 tile 通信。
  • 微观层面（PE 行映射）：由 BPT（bubble-topology prefetching table）完成。BPT 是一个紧凑的静态映射表，在离线预处理阶段构建，把每个 bubble 的不同替代路径分配到连续的 PE 行块上。

这种两层协同的设计，使得：

  • RBCP 保证 bubble 完整性，减少跨 tile 通信和 DRAM 访问；
  • BPT 保证 bubble 内部路径在 PE 阵列上高效执行，减少 PE 空闲。

2. BPT：气泡拓扑预取表的构建与作用​

BPT 的构建利用了 RBCP 阶段一已经识别出的 bubble 信息。在 RBCP 检测 superbubble 时，每个 bubble (si,ti)(s_i, t_i) 及其内部节点都已被标记。Locus 在离线预处理中，根据这些信息生成 BPT。

BPT 的具体映射规则：

  • 每个 bubble 分配给一个连续的 PE 行块。例如，一个 bubble 使用 PE 行 0 到行 2。
  • bubble 内的每条替代路径映射到一条专用 PE 行。例如，路径 S1 映射到行 0，S2 映射到行 1，S3 映射到行 2。
  • 入口节点和汇节点被多播和收集：
    • 入口节点（如 S0）同时广播到所有相关 PE 行，避免每行重复计算入口。
    • 汇节点在路径收敛时只分配一次，避免冗余。
  • 行内中间 DP 分数通过寄存器文件在相邻 PE 之间直接转发，减少对 scratchpad 或 GLB 的访问。

这样，bubble 内部的替代路径可以并行执行，且每条路径的计算被限制在专用 PE 行内，减少了 PE 间的复杂通信。

3. 负载均衡：用顺序节点填充空闲 PE 行​

BPT 将不同替代路径映射到不同 PE 行后，会遇到一个实际问题：替代路径的长度差异很大。有些路径节点少、序列短，会较早完成；而较长的路径仍在运行。这会导致短路径对应的 PE 行空闲，降低整体利用率。

论文提出的解决方案是：用顺序节点（sequential nodes）填充这些空闲行。

顺序节点的特点：

  • 它们位于线性区域，通常比 bubble 内部节点短。
  • 它们不依赖于正在执行的 bubble，因此可以独立调度。
  • 它们可以来自同一 tile 上批处理的其他 reads，或者来自线性区域中与当前 bubble 无依赖关系的节点。

具体做法：

  • 当短路径完成后，其对应的 PE 行变为空闲。
  • 调度器将顺序节点单播到这些空闲行，使其与仍在运行的长 bubble 路径并行执行。
  • 由于顺序节点较短，它们可以很好地填补空闲周期，直到 bubble 完全解析。

这种动态填充机制在微观层面平衡了 PE 负载，避免了因 bubble 路径长度不均而导致的资源浪费。

4. 图 6(a) 示例详解​

图 6(a) 展示了一个具体例子：一个 bubble 有三条替代路径 {S1,S2,S3}\{S1, S2, S3\}，内部节点为 {V1,...,V8}\{V1, ..., V8\}。

映射过程：

  • 入口节点 S0S0 被多播到所有 PE 行。
  • 路径 S1S1 分配给 PE 行 0（PE0-PE3）。
  • 路径 S2S2 分配给 PE 行 1（PE4-PE7）。
  • 路径 S3S3 分配给 PE 行 2（PE8-PE11）。
  • 每条路径按顺序处理其内部节点，并通过寄存器级转发传递中间 DP 分数。
  • 汇节点在路径收敛时只分配一次。

执行过程：

  • 路径 S1S1 和 S2S2 比 S3S3 短，因此 PE 行 0 和行 1 提前完成。
  • 此时，后续的顺序节点（例如线性区域中的 S1→S2S1 \rightarrow S2）被单播到这些空闲行。
  • 这样，所有 PE 保持活跃，直到 bubble 完全解析。

这个例子清晰地说明了 BPT 如何将 bubble 路径映射到 PE 行，以及如何用顺序节点填充空闲周期，实现负载均衡。

5. 数据流重配置：匹配算法依赖​

支持上述映射需要 PE 之间能够根据不同的计算模式重新配置连接。论文设计了两种主要的数据流模式：

5.1 链接模式（Chaining）​

  • 需求：链接递推需要从分布式本地分数中收集全局最大值，即找到最佳前驱 anchor。
  • 实现：
    • RMQ 引擎先用线段树在 O(log⁡n)O(\log n) 时间内进行粗候选选择，将候选集从所有 anchor 对缩小到过滤后的子集。
    • PE 阵列只评估被选中的 (i,j)(i, j) 对。
    • anchor ii 被广播到所有 PE。
    • 由于 RMQ 已经处理了选择，不需要 inter-PE reduction。
  • 数据流：每个 PE 独立计算一个候选的分数，无需 PE 间交换。

5.2 波前比对模式（WFA）​

  • 需求：WFA 需要在相邻对角线之间交换边界值。
  • 实现：
    • 每个 PE 处理一条对角线。
    • E 矩阵向右流动（水平方向）。
    • F 矩阵向左流动（水平方向）。
    • 匹配分数沿对角线流动。
    • 这种跨对角线依赖由模式寄存器设置，并在与数据通路多路复用器相同的周期内重新配置。
  • 数据流：PE 之间通过水平邻居交换边界值，形成波前计算所需的依赖链。

这两种模式的数据流重配置，使得同一套 PE 阵列能够高效支持链接和比对两个阶段，而无需为每个阶段设计专用互连。

6. 与 RBCP、GPF、PE 阵列的关系​

  • RBCP：在宏观层面提供 bubble 完整性，为 BPT 提供 bubble 和内部节点的信息。
  • BPT：在微观层面将 bubble 路径映射到 PE 行，并指导顺序节点填充。
  • GPF 引擎：在图链接阶段提供图路径距离，PE 阵列的链接模式利用这些距离计算跨 segment 分数。
  • PE 阵列：通过模式重配置，在链接模式和 WFA 模式之间切换，执行不同的数据流。
  • RMQ 引擎：在链接模式中预筛选候选，减少 PE 计算量。

7. 小结​

E 节提出的映射与数据流策略是 Locus 实现高效 S2G 映射的关键之一。它的核心贡献可以总结为：

  1. 两层映射：

    • 宏观：RBCP 保持 bubble 完整，形成 tile。
    • 微观：BPT 将 bubble 路径映射到专用 PE 行。

  2. 负载均衡：

    • 用顺序节点填充短路径完成后的空闲 PE 行，提高 PE 利用率。

  3. 数据流重配置：

    • 链接模式：RMQ 粗选 + 广播 + 无 inter-PE reduction。
    • WFA 模式：对角线并行 + E/F 矩阵水平交换。

  4. 整体效果：

    • 减少长距离依赖引起的通信；
    • 提高 PE 阵列在 bubble 密集区域的利用率；
    • 支持融合流水线在统一硬件上高效运行。

通过这种映射与数据流设计，Locus 能够在保持 bubble 完整性的同时，充分利用 PE 资源，从而在泛基因组图上实现高吞吐、低 DRAM 流量的序列到图映射。