Skip to main content

4 SeGram: High-level Overview

下面把论文 第 4 节 SeGraM: High-Level Overview 拆开讲清楚。
这一节是全文的“总设计图”，告诉你 SeGraM 由哪两部分组成、每部分干什么、数据怎么流动、为什么这样设计能解决前面 3.2 节指出的 S2G 瓶颈。

一、这一节在全文中的位置​

前面：

  • 2.1 讲了传统 S2S 映射；
  • 2.2 讲了基因组图和 S2G 映射，以及 S2G alignment 因为 hop 变得复杂；
  • 3.2 分析了为什么现有 S2S 加速器和图加速器都不能直接加速 S2G；
  • 3.3 提出目标：设计一个通用加速器，同时支持 S2G 和 S2S。

第 4 节就是回答“怎么设计”： SeGraM = MinSeed（负责 seeding）+ BitAlign（负责 alignment）
两者都是软硬件协同设计，专门为图结构优化，同时也能处理线性序列。

二、SeGraM 的两个核心组件​

论文原文：

SeGraM consists of two main components: (1) MinSeed, the first minimizer-based seeding accelerator, which finds the candidate locations in a given genome graph; and (2) BitAlign, the first bitvector-based sequence-to-graph alignment accelerator, which performs alignment between a given read and the subgraph identified by MinSeed.

翻译并解释：

1. MinSeed（MS）​

  • 任务：为每条 query read 找候选映射位置。
  • 方法：基于 minimizer 的 seeding。
  • 具体做什么：
    1. 从 read 中找出 minimizer；
    2. 用 minimizer 去索引里查出现频率；
    3. 过滤掉频率过高的 minimizer；
    4. 获取剩余 minimizer 的 seed 位置；
    5. 根据 seed 位置，找出参考图中对应的候选子图（subgraph）。
  • 地位：论文称它是第一个基于 minimizer 的 seeding 硬件加速器。

什么是 minimizer？
在一条序列上滑动一个长度为 w 的窗口，每个窗口里有多个长度为 k 的 k-mer。
根据某种排序规则（比如字典序），选出最小的那个 k-mer，就叫 minimizer。
用 minimizer 代替所有 k-mer 建索引，可以大幅减少索引大小和查询次数。

2. BitAlign（BA）​

  • 任务：把 query read 和 MinSeed 找到的子图做精细比对。
  • 方法：基于 bitvector 的序列到图对齐算法。
  • 具体做什么：
    1. 读取子图和 query read；
    2. 生成 bitvector，做近似字符串匹配和编辑距离计算；
    3. 用 hop queue 处理图中的跳跃边（hop）；
    4. 保存中间 bitvector，供回溯（traceback）；
    5. 执行 traceback，找到最优 alignment；
    6. 把最优 alignment 信息返回给主机。
  • 地位：论文称它是第一个序列到图 alignment 硬件加速器。

什么是 bitvector？
用一串二进制位表示某个状态。
比如，某一位为 1 表示“这个位置匹配”，为 0 表示“不匹配”。
位运算在硬件里非常快，可以并行处理很多位，所以适合加速 alignment。

什么是 hop？
图中非相邻节点之间的边。
比如节点 A 直接连到节点 D，中间跳过 B、C，这条边就叫 hop。
S2G alignment 必须处理 hop，而 S2S 不需要。

三、执行前的预处理​

论文原文：

Before SeGraM execution starts, pre-processing steps (1) generate each chromosome's graph structure, (2) index each graph's nodes, and (3) pre-load both the resulting graph and hash table index into the main memory. Both the graph and its index are static data structures that can be generated only once and reused for multiple mapping executions.

解释：

SeGraM 开始跑之前，先做三件事：

  1. 生成每条染色体的图结构：用线性参考基因组 + 已知变异（VCF）构建基因组图。
  2. 索引图节点：为图中的节点建立哈希表索引，方便 seeding 快速查找。
  3. 预加载到主存：把图和索引都放进主存。

关键点：

  • 图和索引是静态的，只需要构建一次；
  • 可以重复用于很多次 mapping；
  • 所以预处理开销可以分摊到大量 reads 上，不是瓶颈。

四、SeGraM 的执行流程（12 步）​

论文 Figure 4 展示了整个流程。
我们按顺序讲，并分成两大阶段：MinSeed 阶段和 BitAlign 阶段。

阶段一：MinSeed 处理（步骤 1–7）​

步骤 1：读取 query read

  • 主机把 query read 流式传输给 SeGraM；
  • MinSeed 把它写入 read scratchpad（片上暂存 SRAM）。

步骤 2：找 minimizer

  • 用 read 的所有 k-mer，根据评分机制选出最小代表集，即 minimizer；
  • 写入 minimizer scratchpad。

步骤 3：查频率

  • 对每个 minimizer，从主存的哈希表里查它的出现频率（occurrence frequency）。

步骤 4：过滤高频 minimizer

  • 如果某个 minimizer 出现频率太高（比如在基因组里到处都是），就把它丢掉；
  • 目的是减少后面需要 alignment 的 seed 数量，因为高频 minimizer 会产生大量候选位置。

步骤 5：获取 seed 位置

  • 对保留下来的 minimizer，从主存索引里取出它们的 seed 位置；
  • 写入 seed scratchpad。

步骤 6：计算候选子图

  • 对每个 seed，根据它在 read 中的位置和参考中的位置，计算左右边界；
  • 确定参考图中对应的候选区域，也就是 subgraph。

步骤 7：取图节点

  • 从主存中取出这些候选子图涉及的图节点；
  • 写入 BitAlign 的 input scratchpad。

至此，MinSeed 完成，把“read + 候选子图”交给 BitAlign。

阶段二：BitAlign 处理（步骤 8–12）​

步骤 8：生成 bitvector

  • BitAlign 从 input scratchpad 读取子图和 query read；
  • 生成做近似字符串匹配和编辑距离计算所需的 bitvector。

步骤 9：写入 hop queue

  • 生成 bitvector 时，把处理 hop 所需的位向量写入 hop queue；
  • hop queue 用来处理图中非相邻节点之间的跳跃边。

步骤 10：写入 bitvector scratchpad

  • 同时把中间 bitvector 写入 bitvector scratchpad；
  • 这些位向量后面 traceback 时还要用。

步骤 11：执行 traceback

  • 所有 bitvector 生成完后，从 bitvector scratchpad 读回；
  • 执行 traceback，找到 read 和子图之间的最优 alignment。

步骤 12：返回结果

  • 把最优 alignment 信息流回主机。

五、为什么这样设计能解决问题？​

回顾 3.2 节指出的 S2G 瓶颈：

瓶颈SeGraM 的应对
Alignment 是主要瓶颈，且图中 hop 使其更贵BitAlign 专门用 bitvector + hop queue 加速图 alignment
内存访问不规则，cache miss 高MinSeed 用 minimizer 减少索引大小；BitAlign 用 systolic array 循环内部数据，减少内存带宽
Seeding 受 DRAM 延迟限制MinSeed 配 HBM，利用高带宽和低延迟
S2S 启发式不适用图MinSeed 和 BitAlign 都直接支持图结构，不依赖线性假设
搜索空间大用 minimizer 过滤高频种子，减少候选子图数量
现有 S2S 加速器无法处理 hopBitAlign 用 hop queue 显式处理 hop

论文还强调：

In MinSeed, the minimizer-based seeding approach decreases the memory footprint of the index and provides speedup during seed queries.

MinSeed 用 minimizer 减小索引内存占用，并加速 seed 查询。

In BitAlign, we design a new bitvector-based alignment approach, which is amenable to efficient hardware acceleration. BitAlign employs a systolic-array-based design to circulate the internal data (i.e., bitvectors) generated by different processing elements, which provides scalability and reduces both memory bandwidth and memory footprint.

BitAlign 用 systolic array（脉动阵列）让不同处理单元之间循环传递内部数据，提高可扩展性，减少内存带宽和占用。

六、一张简图概括 SeGraM 高层流程​

主机
  │
  ▼
[MinSeed]
  1. 读 query read → read scratchpad
  2. 找 minimizer → minimizer scratchpad
  3. 查频率 → 主存哈希表
  4. 过滤高频 minimizer
  5. 取 seed 位置 → seed scratchpad
  6. 计算候选子图
  7. 取图节点 → BitAlign input scratchpad
  │
  ▼
[BitAlign]
  8. 生成 bitvector
  9. 写 hop queue
 10. 写 bitvector scratchpad
 11. traceback
 12. 返回最优 alignment
  │
  ▼
主机

七、总结：第 4 节的核心思想​

  1. SeGraM 是通用加速器：同时支持 S2G 和 S2S，长短读都行。
  2. 两个组件分工明确：
    • MinSeed：负责 seeding，用 minimizer 快速找候选子图；
    • BitAlign：负责 alignment，用 bitvector 和 hop queue 处理图对齐。
  3. 预处理一次，反复使用：图和索引是静态的，加载到主存后可以服务大量 reads。
  4. 流水线设计：MinSeed 和 BitAlign 可以流水执行，隐藏 MinSeed 延迟。
  5. 针对瓶颈优化：用 HBM 解决内存延迟，用 scratchpad 和 systolic array 解决内存带宽，用 hop queue 解决 hop 依赖。

一句话：

第 4 节给出了 SeGraM 的整体蓝图：MinSeed 用 minimizer 快速缩小候选范围，BitAlign 用 bitvector 和 hop queue 精细比对图结构，两者软硬件协同，专门解决 S2G 中 alignment 这个最大瓶颈。