HBM & Hash Table
下面从硬件视角讲清楚 SeGraM 的哈希表是怎么从主存（HBM）中取出来的。核心链路是：
MinSeed 计算 minimizer → 用哈希值定位 bucket → 读第一级 → 读第二级 → 读第三级 → 得到 seed 位置 → 再取子图节点。
整个过程通过 MinSeed 的内存接口完成，底层是 HBM2E。
一、哈希表放在哪里？
论文第 5 节说：
We store the hash-table-based index in main memory. ... Across all 24 chromosomes of the human genome, the total storage required for the hash-table-based index is 9.8 GB.
翻译：
哈希索引存在主存里。人类 24 条染色体的索引总共约 9.8 GB。
在 SeGraM 的硬件平台里，主存是 HBM2E。
论文第 8.3 节说：
Each SeGraM accelerator has exclusive access to one HBM2E channel to ensure low-latency and high-bandwidth memory access, without any interference from other SeGraM accelerators in each module.
翻译：
每个 SeGraM 加速器独占一个 HBM2E 通道，保证低延迟、高带宽，不受其他加速器干扰。
所以哈希表物理上存在 HBM2E 栈里，逻辑上被分成 24 条染色体的索引，分布在 8 个通道上。
二、哈希表的三级结构回顾
第 5 节定义了三级：
| 级别 | 存什么 | 每条大小 |
|---|---|---|
| 第一级：Bucket | 第二级起始地址 + 该桶 minimizer 数量 | 4 B |
| 第二级：Minimizer | 哈希值 + 第三级起始地址 + seed 位置数量 | 12 B |
| 第三级：Seed Location | 节点 ID + 节点内偏移 | 8 B |
这三张表在内存里是连续的数组，不是链表。
地址计算靠“起始地址 + 索引 × 条目大小”。
三、硬件查询流程（从内存取出的详细步骤）
假设 MinSeed 已经算出了一个 minimizer，要查它的频率和 seed 位置。
步骤 1：算 bucket 索引
硬件先计算 minimizer 的哈希值。
然后取哈希值的某些位，映射到 (2^24) 个桶中的一个。
论文第 5 节：
We empirically find that a bucket count of (2^24) strikes a reasonable balance.
所以桶数量是 (2^24)，第一级表有 (2^24) 个条目，每个 4 B，总大小约 64 MB。
步骤 2：读第一级（Bucket）
内存接口向 HBM 发出读请求：
地址 = bucket_table_base + bucket_index × 4
读取 4 字节
返回的两个字段：
- 该桶的 minimizer 在第二级表中的起始地址；
- 该桶包含的 minimizer 数量。
论文第 5 节：
Each entry in this first level corresponds to a single bucket, and contains the starting address of the bucket's minimizers in the second-level table, along with the number of minimizers in the second-level table that belong to the bucket.
翻译：
第一级每个桶条目包含第二级起始地址和 minimizer 数量。
步骤 3：读第二级（Minimizer）
根据第一级返回的起始地址和数量，去第二级表里找匹配的 minimizer。
第二级每条 12 B，包含：
- minimizer 的哈希值；
- 它的 seed 位置在第三级表中的起始地址；
- 它有多少个 seed 位置。
因为同一个桶里的 minimizer 是按哈希值排序的，硬件可以顺序比较，或做二分查找。
论文第 5 节：
The minimizers are sorted based on their hash values.
翻译：
minimizer 按哈希值排序。
所以硬件从起始地址开始，逐条读 12 B，比较哈希值，直到找到匹配的 minimizer。
步骤 4：读第三级（Seed Location）
找到匹配的 minimizer 后，从它的第二级记录里拿到：
- 第三级起始地址；
- seed 位置数量。
然后去第三级表读 seed 位置，每条 8 B，包含：
- 节点 ID；
- 节点内相对偏移。
论文第 5 节：
In the third level, each entry corresponds to one seed location. An entry contains the node ID of the corresponding seed location, and the relative offset of the corresponding seed location within the node.
翻译：
第三级每个条目是一个 seed 位置，包含节点 ID 和节点内偏移。
步骤 5：用 seed 位置取子图节点
MinSeed 拿到 seed 位置后，还要根据第 6 节的公式计算候选子图的左右边界，然后从主存里取该子图涉及的图节点。
论文第 8.1 节：
(3) the memory interface, which handles the lookups of minimizer frequency, seed location, and subgraph from the attached main memory stack.
翻译：
内存接口负责从主存栈中查找 minimizer 频率、seed 位置和子图。
四、内存接口怎么发请求？
MinSeed 加速器里有一个内存接口模块，它负责：
- 接收计算模块发出的查询请求；
- 生成 HBM 地址；
- 向 HBM 通道发读请求；
- 等待数据返回；
- 把返回的数据写入对应的 scratchpad。
论文第 8.1 节：
MinSeed accelerator consists of ... (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).
翻译：
MinSeed 加速器包含内存接口，负责从主存栈查找频率、seed 位置和子图。
具体请求粒度：
- 第一级桶条目 4 B；
- 第二级 minimizer 12 B；
- 第三级 seed 位置 8 B。
实际 HBM 访问可能一次读一个 cache line（如 64 B），但硬件会从返回的数据里提取需要的字段。
五、如何隐藏内存延迟？
哈希表查询是随机访问，延迟高。
SeGraM 用了三种手段隐藏延迟：
1. 双缓冲
论文第 8.1 节：
For all three scratchpads, we employ a double buffering technique to hide the latency of the MinSeed accelerator.
翻译：
三个 scratchpad 都用双缓冲隐藏 MinSeed 延迟。
当 MinSeed 正在等 HBM 返回当前 minimizer 的频率时，它可以继续处理下一个 minimizer 的请求。
read scratchpad、minimizer scratchpad、seed scratchpad 都有两个缓冲区，一个在用，一个在预取。
2. 流水线
论文第 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 加速器以流水线方式运行。
当 BitAlign 正在跑 alignment 时，MinSeed 已经在查下一组 minimizer 的频率和 seed。
所以 HBM 访问延迟被 BitAlign 的计算掩盖。
3. 独占 HBM 通道
论文第 8.3 节：
Each SeGraM accelerator has exclusive access to one HBM2E channel to ensure low-latency and high-bandwidth memory access.
翻译：
每个加速器独占一个 HBM2E 通道。
这样 32 个加速器同时查哈希表时，不会互相抢带宽，延迟稳定。
六、总结：哈希表从内存取出的完整流程
MinSeed 算出一个 minimizer
│
▼
计算哈希值 → 取某些位 → bucket 索引
│
▼
内存接口发读请求：bucket_table_base + index × 4
│
▼
HBM 返回 4 B：第二级起始地址 + minimizer 数量
│
▼
内存接口读第二级：起始地址 + i × 12，逐条比较哈希值
│
▼
找到匹配 minimizer：得到第三级起始地址 + seed 位置数量
│
▼
内存接口读第三级：起始地址 + j × 8
│
▼
HBM 返回 8 B：节点 ID + 节点内偏移
│
▼
MinSeed 用这些 seed 位置计算候选子图
│
▼
再取子图节点 → 写入 BitAlign 的 input scratchpad
一句话：
SeGraM 的哈希表存在 HBM2E 里，分成三级数组；MinSeed 通过内存接口，先读第一级桶拿到第二级起始地址，再读第二级找到匹配的 minimizer，再读第三级拿到 seed 位置；双缓冲和流水线隐藏 HBM 随机访问延迟，独占通道保证带宽和低延迟。