8.1 MinSeed Accelerator
下面把论文 第 8.1 节 MinSeed Accelerator 拆开讲清楚。
这一节讲的是：MinSeed 算法在硬件上具体怎么实现。
它把第 6 节的算法映射成三个计算模块、三个暂存器和一套内存接口，并用双缓冲和流水线来隐藏延迟。
一、MinSeed 加速器的整体结构
论文原文：
As shown earlier in Figure 4, the MinSeed accelerator consists of: (1) three computation blocks responsible for finding the minimizers from a query read, filtering minimizers based on their frequencies, and finding the candidate reference regions (i.e., subgraphs surrounding the candidate seeds) by calculating each seed's leftmost and rightmost positions; (2) three scratchpad (on-chip SRAM memory) blocks; and (3) the memory interface, which handles the lookups of minimizer frequency, seed location, and subgraph from the attached main memory stack.
翻译并拆解：
MinSeed 加速器由三部分组成：
- 三个计算模块：
- 找 minimizer（从 query read 中提取）；
- 按频率过滤 minimizer；
- 计算候选参考区域（子图），即根据每个 seed 的左右边界确定候选子图。
- 三个 scratchpad（片上 SRAM 暂存器）：
- read scratchpad；
- minimizer scratchpad；
- seed scratchpad。
- 内存接口：
- 负责从主存（HBM 栈）中查找 minimizer 频率、seed 位置和子图节点。
Figure 10 展示了这个设计：
query read → [Read Scratchpad] → [Minimizer Finder] → [Minimizer Scratchpad]
↓ ↓
[Minimizer Filter by Frequency] ← 频率阈值
↓
[Seed Scratchpad] ← 主存（8字节 seed）
↓
[Candidate Seed Region Calculator] → 候选子图（输出）
↑
主存（2字节频率、图节点）
计算模块（紫色块）用简单逻辑实现，因为只需要基本操作：比较、简单算术、scratchpad 读写。
二、三个 scratchpad 详解
论文原文：
MinSeed accelerator consists of three scratchpads (gray-shaded blocks): (1) read scratchpad, which stores the query read; (2) minimizer scratchpad, which stores the minimizers fetched from the query read; and (3) seed scratchpad, which stores the seeds fetched from the memory for the minimizers. For all three scratchpads, we employ a double buffering technique to hide the latency of the MinSeed accelerator.
翻译：
MinSeed 有三个 scratchpad：
- read scratchpad：存 query read；
- minimizer scratchpad：存从 query read 中提取的 minimizer；
- seed scratchpad：存从主存中为 minimizer 取回的 seed。
三个 scratchpad 都采用双缓冲技术来隐藏 MinSeed 的延迟。
1. read scratchpad
论文原文：
Based on our empirical analysis, we find that (1) the read scratchpad requires 6 kB of storage such that it can store 2 query reads of 10 kbp length, where each character of the query reads is represented using 2 bits (A:00, C:01, G:10, T:11).
翻译：
根据实验分析，read scratchpad 需要 6 kB，可以存 2 条 10 kbp 长度的 query read。
每个字符用 2 位表示：A=00，C=01，G=10，T=11。
计算：
2 条 read × 10000 碱基 × 2 位 = 40000 位 = 5000 字节 ≈ 5 kB，留些余量就是 6 kB。
为什么是 2 条？
因为双缓冲：一条正在处理，另一条预取，隐藏传输延迟。
2. minimizer scratchpad
论文原文：
(2) the minimizer scratchpad requires 40 kB of storage such that it can store the minimizers of 2 different query reads, where the maximum number of minimizers that a query read in our datasets can have is 2050 and each minimizer is represented with 10B of data.
翻译：
minimizer scratchpad 需要 40 kB，可以存 2 条不同 query read 的 minimizer。
数据集中一条 read 最多有 2050 个 minimizer，每个 minimizer 用 10 字节表示。
计算：
2 × 2050 × 10 B = 41000 B ≈ 40 kB。
10 字节存什么？
通常包括 minimizer 的哈希值、位置、长度等信息，具体实现可灵活设计。
3. seed scratchpad
论文原文：
(3) the seed scratchpad requires 4 kB of storage such that it can store the seed locations of 2 different minimizers, where the maximum number of seed locations that a minimizer of a query read in our datasets can have is 242 and each seed location is represented with 8B of data.
翻译：
seed scratchpad 需要 4 kB，可以存 2 个不同 minimizer 的 seed 位置。
一个 minimizer 最多有 242 个 seed 位置，每个 seed 位置用 8 字节表示。
计算：
2 × 242 × 8 B = 3872 B ≈ 4 kB。
8 字节存什么？
通常包括节点 ID 和节点内偏移，如第 5 节索引第三级所述。
三、三个计算模块
1. Minimizer Finder（找 minimizer）
- 从 read scratchpad 读取 query read；
- 用第 6 节的单循环算法，在线性时间 O(m) 内找出所有 minimizer；
- 把 minimizer 写入 minimizer scratchpad。
硬件实现：
只需要比较器、计数器和简单的窗口滑动逻辑，非常轻量。
2. Minimizer Filter by Frequency（按频率过滤）
- 对 minimizer scratchpad 中的每个 minimizer，通过内存接口去主存查它的出现频率；
- 如果频率超过阈值（预计算，丢弃 top 0.02% 最频繁的），就丢弃；
- 否则保留，准备取 seed 位置。
硬件实现：
一个比较器 + 一个阈值寄存器，逻辑简单。
3. Candidate Seed Region Calculator（候选种子区域计算）
- 对保留下来的 minimizer，通过内存接口从主存取回所有 seed 位置，写入 seed scratchpad；
- 然后根据第 6 节 Figure 9 的公式，计算每个 seed 的左右边界：
- 左边界 (x = c - a \times (1+E))
- 右边界 (y = d + (m - b - 1) \times (1+E))
- 确定候选子图，再从主存取出该子图涉及的图节点；
- 把图节点写入 BitAlign 的 input scratchpad。
硬件实现：
需要乘法器（计算扩展长度）、加法器/减法器（计算左右边界），以及地址生成逻辑。
仍然属于简单算术，不需要复杂运算。
四、双缓冲与流水线
论文原文：
For all three scratchpads, we employ a double buffering technique to hide the latency of the MinSeed accelerator.
翻译：
三个 scratchpad 都用双缓冲来隐藏 MinSeed 的延迟。
双缓冲怎么工作？
- 当 MinSeed 正在处理当前 query read 的 minimizer 时，主机可以同时把下一条 query read 写入 read scratchpad 的另一个缓冲区；
- 当 MinSeed 正在查频率时，可以预取下一批 minimizer 的 seed 位置；
- 当 MinSeed 正在计算候选区域时，BitAlign 可能已经在处理上一批子图。
这样，内存访问的延迟被计算掩盖，MinSeed 不会成为整个 SeGraM 的瓶颈。
论文 8.3 节进一步说明：
We design each SeGraM accelerator (MinSeed + BitAlign) to operate in a pipelined fashion, such that we can hide the latency of the MinSeed accelerator. While BitAlign is running, MinSeed finds the next set of minimizers, fetches the frequencies and seeds from the main memory, and writes them to their associated scratchpads.
翻译：
每个 SeGraM 加速器（MinSeed + BitAlign）以流水线方式运行，隐藏 MinSeed 的延迟。
当 BitAlign 正在跑时，MinSeed 已经在找下一组 minimizer、取频率和 seed，并写入对应的 scratchpad。
效果：
MinSeed 不在关键路径上，整体吞吐量由更耗时的 BitAlign 决定。
五、内存接口与 HBM
论文原文：
(3) the memory interface, which handles the lookups of minimizer frequency, seed location, and subgraph from the attached main memory stack (5, and 7 from Figure 4).
翻译：
内存接口负责从主存栈中查找：
- minimizer 频率；
- seed 位置；
- 子图节点。
主存用的是 HBM（高带宽内存），因为：
- seeding 阶段有大量随机内存访问；
- HBM 提供低延迟和高带宽，能缓解 DRAM 延迟瓶颈（第 3.1 节 Observation 3）。
每个 SeGraM 加速器独占一个 HBM 通道，避免干扰。
六、总结：第 8.1 节的核心逻辑
- MinSeed 加速器由三部分组成：
- 三个计算模块：找 minimizer、频率过滤、候选区域计算；
- 三个 scratchpad：read、minimizer、seed；
- 内存接口：连接 HBM，查频率、seed、子图。
- scratchpad 尺寸经过精心设计：
- read：6 kB，存 2 条 10 kbp read；
- minimizer：40 kB，存 2 条 read 的 minimizer（每条最多 2050 个，每个 10 B）；
- seed：4 kB，存 2 个 minimizer 的 seed（每个最多 242 个，每个 8 B）。
- 双缓冲 + 流水线：隐藏内存延迟，让 MinSeed 不成为瓶颈。
- 简单逻辑：计算模块只用比较、算术、读写，硬件开销小。
- HBM 接口：利用高带宽低延迟，解决 seeding 的随机内存访问问题。
一句话：
MinSeed 加速器是一个轻量、高效的 seeding 硬件，它用三个 scratchpad 和简单计算模块实现 minimizer 提取、频率过滤和候选子图计算，并通过双缓冲、流水线和 HBM 接口隐藏延迟，为 BitAlign 准备好候选子图。