Skip to main content

6. HopBits

不是。SeGraM 的 BitAlign 中，HopBits 并不是固定 128×128128 \times 128 的完整邻接矩阵。它的实际大小由窗口大小 WW和hop limit共同决定。

1. 窗口大小 W=128W = 128​

BitAlign 采用分治策略，把线性化后的参考子图和 query read 划分成重叠窗口。在 SeGraM 的硬件配置中：

  • 每个 PE 的位向量宽度是 128 bit。
  • 窗口长度 WW 等于 PE 位宽，即 W=128W = 128。
  • 因此，在一个窗口内，线性化参考子图最多包含 128 个字符节点。

如果存储完整的邻接矩阵，那么 HopBits 确实是 128×128128 \times 128 位。

2. 但 SeGraM 限制了 hop limit = 12​

论文 Section 8.2 明确指出：

“In order to decrease the size of each hop queue register and the HopBits matrix, we perform an empirical analysis … when we limit the distance between the farthest node to take into account and the current node (i.e., hop limit).”

Figure 13 显示：当 hop limit = 12 时，可以覆盖超过 99% 的 hop。因此 SeGraM 选择 hop limit = 12。

这意味着：对于每个参考字符节点，HopBits 只记录它与后面最多 12 个节点之间的 hop 关系，而不是记录它与窗口内所有 128 个节点的关系。

所以 HopBits 实际是一个带状矩阵：

  • 行：窗口内的参考字符节点，最多 128 行。
  • 列：相对于当前节点的偏移，范围 0∼110 \sim 11，共 12 列。
  • 每个条目 1 bit。

因此 HopBits 的大小约为：

128×12 bit=1536 bit=192 Byte128 \times 12 \text{ bit} = 1536 \text{ bit} = 192 \text{ Byte}

而不是：

128×128 bit=16384 bit=2 KB128 \times 128 \text{ bit} = 16384 \text{ bit} = 2 \text{ KB}

3. HopBits 如何工作​

处理当前节点 ii 时，PE 会检查 HopBits 中对应行、偏移量为 j−ij-i 的位：

  • 如果为 1，表示从节点 ii 到节点 jj 存在一条 hop 边。
  • 然后从 hop queue register 中读取节点 jj 之前产生的 R[d] 位向量，参与当前节点的 match、deletion、substitution 计算。
  • 如果为 0，则使用全 1 位向量，不影响位运算结果。

hop limit = 12 意味着只考虑距离不超过 12 的 hop，超过这个距离的 hop 被忽略（因为占比不到 1%）。

4. 总结​

  • 完整邻接矩阵才会是 128×128128 \times 128。
  • SeGraM 实际使用的 HopBits 是受 hop limit 限制的带状矩阵，大小约为 128×12128 \times 12 位。
  • 这样做是为了减少硬件面积、功耗和 hop queue register 的深度。
  • 因此，HopBits 不是 128×128128 \times 128，而是 128×12128 \times 12 的位矩阵（或类似带状结构）。