Minimizer Lookup Logic

1. Lookup logic

这部分查找逻辑完全由 MinSeed 硬件实现。它不是软件循环，而是硬件里的比较器 + 状态机 + 地址生成逻辑。下面把这段硬件逻辑拆开讲清楚。

一、先定位：这段查找发生在哪一步？

回顾第 6 节的 MinSeed 算法流程：

计算 query read 的 minimizer；
查每个 minimizer 的出现频率；
过滤高频 minimizer；
取剩余 minimizer 的 seed 位置；
计算候选子图；
交给 BitAlign。

第 2 步和第 4 步都要查哈希索引。
查哈希索引的过程就是：

哈希值 → bucket → 第二级找匹配 minimizer → 第三级取 seed 位置

第二级查找正是其中的关键一步，MinSeed 硬件直接实现。

二、MinSeed 加速器的组成回顾

第 8.1 节说，MinSeed 加速器由三部分组成：

三个计算模块：
- Minimizer Finder；
- Minimizer Filter by Frequency；
- Candidate Seed Region Calculator。
三个 scratchpad：
- read scratchpad；
- minimizer scratchpad；
- seed scratchpad。
内存接口：
- 负责从 HBM 查 minimizer 频率、seed 位置和子图。

第二级查找逻辑属于内存接口 + Minimizer Filter by Frequency 模块的协同工作，全部在硬件里完成。

三、第二级查找的硬件实现细节

1. 硬件模块分工

模块	职责
Minimizer Filter by Frequency	发起“查这个 minimizer 的频率”请求
内存接口	生成 HBM 地址，发读请求，接收数据
比较器 + 状态机	在第二级条目中逐条比较哈希值，直到匹配
地址生成器	计算第二级每条记录的地址
计数器	跟踪已比较的条目数，和第一级返回的数量比较

2. 具体流程

假设 MinSeed 要查 minimizer (m)，它的哈希值为 (h)。

步骤 1：读第一级 bucket

内存接口读第一级：

地址 = bucket_table_base + bucket_index × 4

start_addr：该桶的 minimizer 在第二级表中的起始地址；
count：该桶包含的 minimizer 数量。

步骤 2：初始化第二级查找状态

硬件状态机初始化：

current_addr = start_addr；
remaining = count；
found = false。

步骤 3：逐条读第二级并比较

每个周期（或每几个周期，取决于 HBM 延迟）：

发读请求：
```
地址 = current_addr
读取 12 B
```
接收 12 B 数据，拆成三个字段：
- hash_value（哈希值）；
- third_level_start（第三级起始地址）；
- num_locations（seed 位置数量）。

比较器比较：

if hash_value == h:
    found = true
    保存 third_level_start 和 num_locations
    停止查找
else:
    current_addr += 12
    remaining -= 1
    if remaining == 0:
        未找到（该 minimizer 不在索引中）
        停止查找

循环：回到步骤 1，直到 found 或 remaining == 0。

步骤 4：返回结果

如果找到匹配：

把 third_level_start 和 num_locations 传给下一步；
内存接口继续读第三级，取 seed 位置。

如果没找到：

说明这个 minimizer 在参考图中不存在；
直接丢弃，不产生 seed。

3. 为什么可以用顺序比较？

论文第 5 节说：

The minimizers are sorted based on their hash values.

翻译：
同一桶里的 minimizer 按哈希值排序。

因为排序了，硬件可以：

顺序比较：从起始地址逐条读，直到哈希值 ≥ 目标哈希值；
或二分查找：如果桶内条目多，可以用二分减少比较次数。

论文没有明确说用哪种，但从硬件简单性看，顺序比较更常见，因为：

每个桶的 minimizer 数量不多（(2^24) 个桶分散后，每桶平均条目数很少）；
顺序比较逻辑简单，不需要复杂的分支预测；
可以利用 HBM 的突发读，一次读多条。

4. 并行化

因为 MinSeed 可以同时处理多个 minimizer，硬件可以：

多个查找请求流水线化；
一个 minimizer 在等 HBM 返回时，另一个 minimizer 可以发起新的 bucket 读；
这就是双缓冲和流水线的作用（第 8.1、8.3 节）。

四、这段逻辑为什么放在硬件里？

1. 软件循环太慢

如果这段查找用 CPU 软件做：

每次比较都要取指、译码、执行、访存；
分支预测失败会冲刷流水线；
内存延迟无法隐藏。

而硬件可以：

用状态机直接控制地址生成和比较；
比较器一拍完成；
多个请求流水线并行；
延迟被其他计算掩盖。

2. 和内存接口紧耦合

第二级查找需要频繁访问 HBM。
如果放在软件里，CPU 要发内存请求、等数据、再比较，延迟很高。
MinSeed 硬件把内存接口和比较逻辑放在一起，可以：

发请求后不阻塞，继续处理其他 minimizer；
数据返回后立即比较；
比较结果直接驱动下一步（读第三级或丢弃）。

3. 和频率过滤无缝衔接

第二级查找的目的之一就是取 num_locations（seed 位置数量），用于频率过滤。
硬件里这个字段直接来自第二级记录，不需要额外计算。
过滤逻辑（比较阈值）也由硬件比较器完成，非常快。

五、总结：第二级查找的硬件实现

环节	硬件实现
发起查找	Minimizer Filter by Frequency 模块
读第一级 bucket	内存接口，地址 = base + index × 4
初始化	状态机设置 current_addr 和 remaining
读第二级条目	内存接口，地址 = current_addr，读 12 B
比较哈希值	硬件比较器，一拍完成
地址递增	地址生成器，current_addr += 12
计数	计数器，remaining -= 1
找到/未找到	状态机控制，找到则保存第三级地址和数量
读第三级	内存接口，地址 = third_level_start + j × 8
流水线	双缓冲 + 多请求并行，隐藏 HBM 延迟

一句话：
MinSeed 硬件里有一个状态机 + 比较器 + 地址生成器 + 计数器，专门负责在第二级表中逐条比较哈希值，找到匹配的 minimizer 后取出第三级地址和 seed 位置数量。这段逻辑完全由硬件实现，和内存接口紧耦合，通过流水线和双缓冲隐藏 HBM 延迟，是 MinSeed 能高效完成 seeding 的关键之一。

2. MinSeed 频率过滤

一、频率是泛基因组图中的频率，不是 query read 中的频率

论文第 6 节原文：

After finding the minimizers of each read, MinSeed queries the hash-table-based index (Section 5) stored in memory to fetch the occurrence frequency (i.e., #locations) of each minimizer.

翻译：
找到每条 read 的 minimizer 后，MinSeed 查询存在内存中的哈希索引，获取每个 minimizer 的出现频率（即位置数量）。

关键点：

频率 = 该 minimizer 在参考基因组（泛基因组图）中出现的次数；
不是 query read 中的频率；
具体来说，是哈希索引第三级中该 minimizer 对应的 seed 位置数量（num_locations）。

论文第 6 节接着说：

A minimizer is discarded if its occurrence frequency in the reference genome is above a user-defined threshold.

翻译：
如果某个 minimizer 在参考基因组中的出现频率超过用户定义的阈值，就丢弃它。

所以频率的来源是参考图，不是 read。

为什么用参考图的频率？

因为频率过滤的目的是：
去掉在参考图中到处都是的 minimizer，因为它们会产生大量候选位置，让 alignment 爆炸。

如果一个 minimizer 在参考图中出现 1 次 → 它很独特，产生 1 个候选，很有价值；
如果一个 minimizer 在参考图中出现 100 万次 → 它可能在重复区域，产生 100 万个候选，做 alignment 会非常慢，所以丢弃。

query read 中每个 minimizer 只出现一次（或少数几次），用它自己的频率没有意义。

二、query read 中的 minimizer 可能在参考图中不存在吗？

完全可能，而且很常见。 原因有三类：

1. 测序错误

测序仪会引入错误，错误率可能高达 5%–10%（长读）。
如果 read 中某个 k-mer 因为测序错误而改变，它对应的 minimizer 就可能不在参考图中。

例如：

参考图：  ... A C G T A C G T ...
read：    ... A C G T A C G A ...   ← 最后一个 T 被误读成 A

read 中出现的 C G A 这个 minimizer，参考图中可能根本不存在。

2. 真实变异

样本基因组可能含有参考图未收录的变异。
虽然泛基因组图已经包含了很多已知变异，但不可能包含所有个体的所有变异。

如果 read 携带一个参考图中没有的新变异，它产生的 minimizer 就可能查不到。

3. 参考图不完整或 read 来自非参考区域

参考图可能没有覆盖某些重复区域、着丝粒、端粒等；
read 可能来自线粒体、病毒、污染序列等参考图不包含的来源。

这些情况下，read 的 minimizer 在参考图中没有对应位置。

三、当 minimizer 在参考图中不存在时，MinSeed 怎么处理？

哈希索引第二级查找的逻辑是：

根据第一级 bucket 拿到第二级起始地址和数量；
在第二级中逐条比较哈希值；
如果找到匹配的 minimizer → 取它的 seed 位置数量，继续处理；
如果遍历完该桶的所有条目都没有匹配 → 说明这个 minimizer 在参考图中不存在。

此时硬件会：

直接丢弃这个 minimizer；
不产生任何 seed；
继续处理下一个 minimizer。

论文没有明确写“未找到”分支，但从算法逻辑和硬件设计可以推断：

状态机在 remaining == 0 且 found == false 时停止查找；
这个 minimizer 不进入频率过滤，也不进入 seed 位置获取；
它相当于被“自然过滤”掉了。

这会影响灵敏度吗？

不会显著影响。 原因：

一个 read 通常有很多 minimizer（比如 10 kbp read 可能有几百到几千个）；
少数 minimizer 因为测序错误或变异而查不到，不影响整体；
其他正确的 minimizer 仍然会产生候选，足以让 BitAlign 找到正确比对。

论文第 11.4 节说：

MinSeed does not decrease the sensitivity of the overall sequence-to-graph mapping compared to the baseline software tools since both MinSeed and the baseline software tools implement the same optimization of discarding the seeds that have higher frequency than the threshold.

翻译：
MinSeed 不会降低整体 S2G 映射的灵敏度，因为它和基线软件工具一样，只丢弃高频种子。

隐含的意思是：
查不到的 minimizer 本来就不是有效种子，丢弃它们不会漏掉正确比对。

四、总结

问题	答案
频率是 query read 中的还是参考图中的？	参考图（泛基因组图）中的频率，即该 minimizer 在图中出现的次数
频率从哪来？	哈希索引第三级中该 minimizer 的 seed 位置数量
query read 的 minimizer 可能在参考图中不存在吗？	完全可能，原因包括测序错误、真实变异、参考图不完整
不存在时怎么处理？	第二级遍历完没找到匹配 → 直接丢弃，不产生 seed
会影响灵敏度吗？	不会显著影响，因为 read 通常有很多 minimizer，少数查不到不影响整体

一句话：
频率过滤用的是 minimizer 在参考图中的出现次数，不是 query read 中的频率；query read 中的 minimizer 完全可能在参考图中不存在，此时 MinSeed 会直接丢弃它，不产生 seed，也不会显著影响映射灵敏度。

1. Lookup logic​

一、先定位：这段查找发生在哪一步？​

二、MinSeed 加速器的组成回顾​

三、第二级查找的硬件实现细节​

1. 硬件模块分工​

2. 具体流程​

步骤 1：读第一级 bucket​

步骤 2：初始化第二级查找状态​

步骤 3：逐条读第二级并比较​

步骤 4：返回结果​

3. 为什么可以用顺序比较？​

4. 并行化​

四、这段逻辑为什么放在硬件里？​

1. 软件循环太慢​

2. 和内存接口紧耦合​

3. 和频率过滤无缝衔接​

五、总结：第二级查找的硬件实现​

2. MinSeed 频率过滤​

一、频率是泛基因组图中的频率，不是 query read 中的频率​

为什么用参考图的频率？​

二、query read 中的 minimizer 可能在参考图中不存在吗？​

1. 测序错误​

2. 真实变异​

3. 参考图不完整或 read 来自非参考区域​

三、当 minimizer 在参考图中不存在时，MinSeed 怎么处理？​

这会影响灵敏度吗？​

四、总结​