Three scratchpads of Minseed
1. read scratchpad
是的，MinSeed 会等一条 query read 完整写入 read scratchpad 的某个缓冲区后，才开始对这条 read 做 minimizer 查找。
但它不会等所有 reads，也不会让主机传输成为瓶颈——这靠的是双缓冲。
下面分三点讲清楚。
一、为什么必须等整条 read 写完？
因为 minimizer 计算需要遍历整条 read 的所有窗口。
论文第 6 节说：
The MinSeed algorithm starts by computing the minimizers of a given query read. ... The single-loop algorithm has a complexity of , where is the length of the query read.
翻译：
MinSeed 首先计算整条 query read 的 minimizer，单循环复杂度 ， 是整条 read 的长度。
minimizer 是在长度为 的窗口上滑动的。
如果 read 还没写完，最后一个窗口可能不完整，无法正确选出 minimizer。
所以 MinSeed 必须拿到完整的 read，才能保证所有窗口都合法。
二、双缓冲：等的是“某一条 read”，不是“所有 reads”
论文第 8.1 节说：
the read scratchpad requires 6 kB of storage such that it can store 2 query reads of 10 kbp length.
翻译：
read scratchpad 有 6 kB，可以存 2 条 10 kbp 的 read。
这正是双缓冲的设计：
缓冲区 A：MinSeed 正在处理（这条 read 已经完整写入）
缓冲区 B：主机正在写入（下一条 read）
工作方式：
- 主机先把第 1 条 read 完整写入缓冲区 A；
- MinSeed 开始处理缓冲区 A，同时主机往缓冲区 B 写第 2 条 read；
- MinSeed 处理完 A 后，切到 B 处理第 2 条；
- 同时主机往 A 写第 3 条 read；
- 如此循环。
所以 MinSeed 等的是当前缓冲区里那条 read 写完，而不是等所有 reads 都到齐。
当它在处理 A 时，B 已经在接收下一条，传输和处理是重叠的。
论文第 8.3 节印证了这一点：
Thus, this transfer is not on the critical path of SeGraM's execution, since the next query read to be processed has already been transferred and stored in the read scratchpad of the MinSeed accelerator when the current query read is being processed.
翻译：
这个传输不在 SeGraM 执行的关键路径上，因为当前 read 正在处理时，下一条 read 已经被传输并存入 read scratchpad 了。
三、能不能边写边算？
理论上可以：minimizer 是滑动窗口，只要窗口完整就能算。
但论文的设计是双缓冲批量处理，原因有三：
- 硬件简单：Minimizer Finder 只需从已写满的缓冲区顺序读取，不需要处理“半条 read”的边界情况；
- 窗口完整性：避免最后一个窗口不完整导致错误；
- 流水线效率：双缓冲已经能隐藏传输延迟，边写边算带来的额外复杂度不值得。
所以论文没有采用“边写边算”，而是“写完一条，处理一条；处理一条时，接收下一条”。
四、总结
| 问题 | 答案 |
|---|---|
| MinSeed 会等整条 read 写完吗？ | 会，等当前缓冲区的 read 完整写入 |
| 会等所有 reads 都到齐吗？ | 不会，双缓冲让它只等当前这一条 |
| 等的时候主机会闲着吗？ | 不会，主机在往另一个缓冲区写下一条 read |
| 传输在关键路径上吗？ | 不在，双缓冲隐藏了传输延迟 |
| 能边写边算吗？ | 理论上可以，但论文采用双缓冲批量处理，更简单高效 |
一句话：
MinSeed 会等一条 query read 完整写入 read scratchpad 的某个缓冲区后，才开始找 minimizer；但通过双缓冲，当它处理当前 read 时，主机已经在写吓一条 read，所以传输和处理重叠，传输不在关键路径上。
2. Minimizer scratchpad
在正常情况下，是的：MinSeed 会等一条 query read 的所有 minimizer 都写入 minimizer scratchpad 后，才进入下一步（频率过滤）。
但如果 minimizer 太多、scratchpad 装不下，就会采用分批（batching） 方式，不必等全部 minimizer 都算完。
下面分两种情况讲清楚。
一、正常情况：一条 read 的所有 minimizer 先写完，再过滤
论文第 8.1 节说：
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 B。
计算：
2 × 2050 × 10 B = 41000 B ≈ 40 kB。
这说明设计容量正好是按“一条 read 的所有 minimizer”为单位来规划的：
缓冲区 A：存第 1 条 read 的全部 minimizer（正在被 Filter 模块处理）
缓冲区 B：存第 2 条 read 的全部 minimizer（正在被 Finder 模块写入）
工作方式：
- Minimizer Finder 从 read scratchpad 读第 1 条 read，算出它全部 minimizer，写入缓冲区 A；
- 写完后，Filter 模块开始处理缓冲区 A 的 minimizer（查频率、过滤）；
- 同时，Minimizer Finder 开始算第 2 条 read 的 minimizer，写入缓冲区 B；
- 缓冲区 A 处理完，切到 B；同时 Finder 开始算第 3 条 read，写入 A。
所以，在正常情况下，确实是等一条 read 的所有 minimizer 都写入 scratchpad 后，才进入频率过滤。
二、特殊情况：minimizer 太多，装不下，就分批
论文第 8.3 节说：
If the minimizers do not fit in the minimizer scratchpad, we can perform a batching approach, where not all of the minimizers will be found and stored together. Instead, a batch (i.e., a subset) of minimizers is found, stored, and used, and then the next batch will be generated out of the read. A similar optimization can be applied to the seed scratchpad if capacity issues arise.
翻译：
如果 minimizer 太多，装不进 minimizer scratchpad，就采用分批处理：
一次只找一部分 minimizer，存下来用掉，再找下一批。
seed scratchpad 如果容量不够，也可以类似处理。
这种情况下：
- 不必等所有 minimizer 都算完；
- 一批 minimizer 写入后，Filter 模块就开始处理这一批；
- 同时 Finder 继续算下一批；
- 这样形成更细粒度的流水线。
但论文说这是容量不足时的备选方案，不是常规路径。
常规路径是前面说的“一条 read 的所有 minimizer 先写完，再过滤”。
三、为什么设计成“按 read 为单位”而不是“边算边过滤”？
论文采用“一条 read 的所有 minimizer 先写入，再过滤”的设计，原因有三：
-
minimizer scratchpad 容量正好匹配：
40 kB 可以存 2 条 read 的全部 minimizer（每条最多 2050 个），双缓冲刚好够用。 -
硬件简单：
Finder 只需顺序写入，Filter 只需顺序读取，不需要处理“半条 read”的边界情况。 -
过滤需要全局信息：
频率过滤是按 minimizer 逐个查频率，但同一条 read 的 minimizer 之间没有依赖，所以整批处理更高效。
四、和 read scratchpad 的双缓冲对比
| Scratchpad | 双缓冲单位 | 容量 | 对应 read 数 |
|---|---|---|---|
| read scratchpad | 一条 read | 6 kB | 2 条 10 kbp read |
| minimizer scratchpad | 一条 read 的所有 minimizer | 40 kB | 2 条 read 的 minimizer |
| seed scratchpad | 一个 minimizer 的所有 seed | 4 kB | 2 个 minimizer 的 seed |
可以看到：
- read scratchpad 和 minimizer scratchpad 都是按 read 为单位双缓冲；
- seed scratchpad 是按 minimizer 为单位双缓冲（因为一个 minimizer 可能有很多 seed）。
五、总结
| 问题 | 答案 |
|---|---|
| 正常情况要等一条 read 的所有 minimizer 都写入吗？ | 是的，写完后才进入频率过滤 |
| 如果 minimizer 太多装不下呢？ | 分批处理，一批写入后就开始过滤，同时算下一批 |
| 为什么按 read 为单位？ | scratchpad 容量正好匹配；硬件简单；过滤高效 |
| 双缓冲怎么配合？ | 一条 read 的 minimizer 在被过滤时，下一条 read 的 minimizer 正在写入另一个缓冲区 |
| 这和 read scratchpad 的双缓冲一致吗？ | 一致，都是按 read 为单位双缓冲 |
一句话：
正常情况下，MinSeed 会等一条 query read 的所有 minimizer 都写入 minimizer scratchpad 后，才开始频率过滤；如果 minimizer 太多装不下，就分批处理。双缓冲让“当前 read 的 minimizer 被过滤”和“下一条 read 的 minimizer 被写入”重叠进行。
3. Seed scratchpad
不需要。 MinSeed 的 seed scratchpad 是按 minimizer 为单位组织的，不是按整条 query read 为单位。
它会处理完一个 minimizer 的 seed 位置，就进入下一步（计算候选子图），同时预取下一个 minimizer 的 seed 位置。不需要等整条 read 所有 minimizer 的 seed 都取回来。
下面从论文第 8.1 节的设计来证明。
一、seed scratchpad 的容量说明它是按 minimizer 组织的
论文第 8.1 节：
(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 B。
计算：
2 × 242 × 8 B = 3872 B ≈ 4 kB。
注意关键词：2 different minimizers，不是“2 条 read 的所有 minimizer 的 seed”。
所以 scratchpad 的容量单位是 minimizer，不是整条 read。
二、对比三个 scratchpad 的组织单位
| Scratchpad | 容量 | 双缓冲单位 | 一条 read 对应多少 |
|---|---|---|---|
| read scratchpad | 6 kB | 一条 read | 2 条 10 kbp read |
| minimizer scratchpad | 40 kB | 一条 read 的所有 minimizer | 2 条 read 的 minimizer |
| seed scratchpad | 4 kB | 一个 minimizer 的所有 seed | 2 个 minimizer 的 seed |
可以看到：
- read scratchpad 和 minimizer scratchpad 是按 read 为单位；
- seed scratchpad 是按 minimizer 为单位。
为什么 seed scratchpad 不按 read 为单位？
因为一条 read 有很多 minimizer，每个 minimizer 又可能有很多 seed 位置。
如果按整条 read 存所有 seed，容量会爆炸（比如 2050 个 minimizer × 平均几十个 seed × 8 B，远超 4 kB）。
所以设计上只存当前正在处理的 minimizer的 seed，用双缓冲预取下一个 minimizer的 seed。
三、工作流程：逐个 minimizer 处理，流水线重叠
seed scratchpad 的双缓冲工作方式：
缓冲区 A：当前 minimizer 的 seed 位置，正在被 Candidate Seed Region Calculator 处理
缓冲区 B：下一个 minimizer 的 seed 位置，正在从 HBM 取回并写入
流程：
- 从 minimizer scratchpad 取第 1 个 minimizer；
- 内存接口从 HBM 取它的 seed 位置，写入 seed scratchpad 缓冲区 A；
- 写完后，Candidate Seed Region Calculator 开始处理缓冲区 A，计算候选子图；
- 同时，内存接口开始取第 2 个 minimizer 的 seed 位置，写入缓冲区 B；
- 缓冲区 A 处理完，切到 B；同时取第 3 个 minimizer 的 seed，写入 A；
- 如此循环，直到该 read 的所有 minimizer 处理完。
所以：
- 不需要等整条 read 所有 minimizer 的 seed 都取回来；
- 只需要等当前 minimizer 的 seed 写完，就可以进入下一步；
- 下一个 minimizer 的 seed 在后台预取，和当前处理重叠。
四、和 minimizer scratchpad 的区别
| 问题 | minimizer scratchpad | seed scratchpad |
|---|---|---|
| 存储单位 | 一条 read 的所有 minimizer | 一个 minimizer 的所有 seed |
| 是否等整条 read？ | 是，等一条 read 的所有 minimizer 写完 | 否，等一个 minimizer 的 seed 写完即可 |
| 双缓冲对象 | 当前 read 的 minimizer vs. 下一条 read 的 minimizer | 当前 minimizer 的 seed vs. 下一个 minimizer 的 seed |
| 原因 | 一条 read 的 minimizer 数量有限（最多 2050 个） | 一个 minimizer 的 seed 数量有限（最多 242 个），但 read 的 minimizer 很多，不能全存 |
所以两者的粒度不同：
- minimizer scratchpad：按 read 为单位；
- seed scratchpad：按 minimizer 为单位。
五、总结
| 问题 | 答案 |
|---|---|
| 要等整条 read 所有 minimizer 的 seed 都写入 seed scratchpad 吗？ | 不需要 |
| seed scratchpad 按什么单位组织？ | 一个 minimizer 的所有 seed 位置 |
| 双缓冲的对象是什么？ | 当前 minimizer 的 seed vs. 下一个 minimizer 的 seed |
| 什么时候进入下一步？ | 当前 minimizer 的 seed 写完后，就开始算候选子图 |
| 整条 read 的 minimizer 怎么处理？ | 逐个 minimizer 流水线处理，前一个在算候选子图，后一个在取 seed |
| 为什么这样设计？ | 一条 read 的 minimizer 太多，如果按 read 存所有 seed，容量会爆炸 |
一句话：
seed scratchpad 是按 minimizer 为单位双缓冲的，不需要等整条 read 所有 minimizer 的 seed 都写入。当前 minimizer 的 seed 写完后，就进入候选子图计算；同时下一个 minimizer 的 seed 在后台预取。这样既节省容量，又实现流水线重叠。
4. Seed scratchpad capacity
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.
论文第 8.2 节明确说明，BitAlign 的 input scratchpad 存储三类数据：
BitAlign uses two types of SRAM buffers: (1) input scratchpad, which stores the linearized reference graph, associated HopBits for each node, and the pattern bitmasks for the query read.
翻译：
BitAlign 用两种 SRAM 缓冲区，其中 input scratchpad 存储：
- 线性化参考图（linearized reference graph）；
- 每个节点相关的 HopBits；
- query read 的 pattern bitmasks。
下面逐项展开。
一、线性化参考图（Linearized Reference Graph）
- 来源：MinSeed 输出的候选子图。
- 内容：子图包含的图节点，按拓扑排序后线性排列。
- 每个节点包含：
- 节点 ID；
- 节点序列（A、C、G、T，2 位编码）；
- 出边信息（后继节点列表）。
- 为什么要线性化：BitAlign 需要按顺序遍历节点，拓扑排序保证当前节点依赖的后继节点已经处理过。
论文第 4 节步骤 7 说：
MinSeed ... fetches the graph nodes from memory for each candidate region in the reference and writes the nodes to the input scratchpad of BitAlign.
翻译：
MinSeed 从主存取出候选区域的图节点，写入 BitAlign 的 input scratchpad。
二、HopBits（每个节点相关的跳跃边信息）
- 来源：由子图的边表生成。
- 内容：一个邻接矩阵，描述节点之间是否存在 hop（非相邻边）。
- 作用：告诉 BitAlign 在计算匹配、删除、替换时，是否需要把远处节点的位向量纳入运算。
论文第 8.2 节说：
We implement the hop information between nodes of the graph as an adjacency matrix called HopBits.
翻译：
节点之间的 hop 信息用一个叫 HopBits 的邻接矩阵表示。
Figure 12 展示了 HopBits 矩阵：
- 如果从 NodeID_X 到 NodeID_Y 有出边（hop），则 HopBits 第 x 列第 y 行为 1；
- 否则为 0（图中用“-”表示）。
三、Pattern Bitmasks（query read 的模式位掩码）
- 来源：BitAlign 预处理阶段生成（Algorithm 1 第 3 行）。
- 内容：四个位向量，分别对应 A、C、G、T。
- 每个位向量的长度 = 窗口宽度 W（例如 128 位）。
- 某位为 1 表示 read 的对应位置是该字符。
论文第 7 节说：
As a pre-processing step, we generate four pattern bitmasks for the query read (one for each character in the alphabet: A, C, G, T).
翻译：
预处理阶段为 query read 生成四个模式位掩码，每个对应一个碱基。
生成后存入 input scratchpad，供 PE 根据当前节点字符快速取用。
四、容量
论文第 8.2 节说：
For a 64-PE configuration with 128 bits of processing per PE, BitAlign requires a total of in input scratchpad storage.
翻译：
在 64 个 PE、每个 PE 处理 128 位的配置下，input scratchpad 总共需要 24 kB。
这 24 kB 要装下：
- 线性化子图节点（序列 + 边信息）；
- HopBits 矩阵；
- 四个 pattern bitmasks。
五、总结
| 存储内容 | 来源 | 作用 |
|---|---|---|
| 线性化参考图 | MinSeed 输出的候选子图 | 提供节点序列和出边信息 |
| HopBits | 由子图边表生成 | 描述节点间 hop，供位运算使用 |
| Pattern bitmasks | BitAlign 预处理生成 | 四个位向量，对应 A/C/G/T，用于匹配计算 |
一句话：
BitAlign 的 input scratchpad 存储的是 MinSeed 传来的线性化候选子图（节点 + 边）、子图的 HopBits 邻接矩阵，以及 query read 的四个 pattern bitmasks；这些数据是 BitAlign 生成位向量、执行图对齐的全部输入。