3. PE and edit distance d

你指出的矛盾是对的：在 SeGraM 的 BitAlign 中，PE 链并不是对应参考图的不同节点，而是对应不同的编辑距离 $d$。 图节点的迭代是在时间上顺序进行的，不是空间上分配给不同 PE。之前那种“不同 PE 对应不同节点”的说法是不准确的，应该纠正。

下面把 BitAlign 的算法和硬件映射理清楚。

1. BitAlign 算法中的两个循环

BitAlign 算法（论文 Algorithm 1）有两个嵌套循环：

• 外层循环：for i in (n-1):-1:0
  按拓扑排序逆序遍历线性化后的参考子图节点。每个节点 $i$ 有一个字符 curChar，对应一个模式位掩码 curPM。

• 内层循环：for d in 1:k
  对当前节点 $i$，计算不同编辑距离 $d$ 下的状态位向量 R[d]。

计算 R[d] 时需要用到：

• 当前节点 $i$ 在 $d-1$ 层的状态：用于 insertion；
• 后继节点 $j$ 在 $d-1$ 层的状态：用于 deletion 和 substitution；
• 后继节点 $j$ 在 $d$ 层的状态：用于 match。

2. 硬件映射：内层 $d$ 映射到 PE 链

SeGraM 的 BitAlign 硬件采用线性循环 systolic array。根据论文 Section 8.2 和图 11：

• 每个 PE 负责计算一个编辑距离层 $d$ 的 R[d] 位向量。
• PE 链上相邻的 PE 之间传递状态：
  • PE$_x$ 产生 R[d]，直接送给下一个 PE$_{x+1}$ 作为它的 R[d-1]（用于 insertion）。
  • PE$_x$ 的 R[d] 还会进入自己的 hop queue register，经过延迟后作为 oldR[d] 提供给同一个 PE（用于 match），并作为 oldR[d-1] 提供给下一个 PE（用于 deletion 和 substitution）。

因此，PE 链上的位置对应编辑距离 $d$：
PE$_0$ 负责 $d=0$，PE$_1$ 负责 $d=1$，……，PE$_k$ 负责 $d=k$。
相邻 PE 传递的是编辑距离层的状态向量，而不是图节点。

3. 图节点迭代是时间上的顺序循环

外层循环 for i 在硬件中是按时间顺序执行的。每个时钟周期（或每轮迭代），所有 PE 共同处理同一个图节点 $i$ 的不同编辑距离层。

• 当前节点 $i$ 的字符 curChar 被广播给所有 PE，每个 PE 使用相同的 curPM。
• 所有 PE 在同一周期分别计算该节点在 $d=0,1,\dots,k$ 层的 R[d]。

下一个周期，处理下一个节点 $i-1$。由于图是拓扑排序的，后继节点 $j$ 在之前的周期已经处理过，其 R[d] 值被保存在 hop queue register 或 bitvector scratchpad 中。当当前节点需要后继节点的状态时，就从 hop queue 中读取。

所以：

• PE 链 = 编辑距离 $d$ 的空间并行；
• 时间 = 图节点 $i$ 的顺序迭代。

4. 为什么会有“不同 PE 对应不同节点”的误解？

可能是因为 systolic array 中数据会流动，节点迭代在时间上展开，看起来像不同 PE 在处理不同节点。但实际上，在任何一个周期，所有 PE 处理的是同一个节点，只是编辑距离不同。图节点不是分配给不同 PE，而是按时间顺序逐个进入阵列。

5. 总结

在 SeGraM 的 BitAlign 中：

• 每个 PE 负责当前图节点的一个编辑距离层 $d$。
• 所有 PE 在同一周期共同处理同一个图节点，分别计算 $d=0,1,\dots,k$ 的位向量。
• 相邻 PE 之间传递的是编辑距离层的状态向量：PE$_x$ 的 R[d] 作为 PE$_{x+1}$ 的 R[d-1]。
• 图节点迭代是时间上的顺序循环，不是空间上分配给不同 PE。
• hop queue 用于存储之前已处理过的后继节点的 R[d] 值，以便当前节点通过 hop 访问非相邻节点的状态。

因此，之前“不同 PE 对应参考图的不同节点”的说法是错误的，正确的是：PE 链对应编辑距离 $d$，图节点在时间上顺序迭代。

---

在 SeGraM 的 BitAlign 中，每个参考字符并不是只存储一个大小为 $1 \times (k+1)$ 的标量矩阵。更准确地说：

• 对于每个参考字符（线性化后的单字符节点）$i$，BitAlign 会存储 $k+1$ 个状态位向量，分别对应编辑距离 $d = 0, 1, \dots, k$。
• 每个状态位向量 allR[i][d] 的长度等于 query read 窗口的位宽 $W$（在 SeGraM 硬件配置中 $W = 128$ 位）。
• 因此，对于每个参考字符 $i$，它对应的是一个 (k+1) 个位向量的集合，总共占用 $(k+1) \times W$ 位。

用论文 Algorithm 1 的记号：

allR[n][d]   // n 是线性化参考子图的字符数，d 是编辑距离 0..k

其中：

• n：参考子图的字符索引（每个字符对应一个线性化节点）
• d：编辑距离层，范围 $0 \le d \le k$
• allR[i][d]：一个长度为 $W$ 的位向量，表示在第 $i$ 个参考字符处、允许 $d$ 个错误时的部分匹配状态。

所以，对于每一个参考字符 $i$，存储了 allR[i][0], allR[i][1], …, allR[i][k]，共 $k+1$ 个位向量。每个位向量是 $W$ 位。

如果非要用“矩阵”来描述：

• 可以把它看作一个 (k+1) × W 的位矩阵：行对应编辑距离 $d$，列对应 query read 窗口中的位置。
• 而不是 $1 \times (k+1)$ 的标量矩阵。

此外，在硬件实现中，为了减少存储开销，BitAlign 只存储最终的 R[d] 位向量（即 allR[i][d]），而不存储计算过程中的中间位向量（match、insertion、deletion、substitution）。这些中间位向量在 traceback 阶段根据需要重新生成。这样每个参考字符的存储量就是 $(k+1) \times W$ 位，而不是 $3(k+1) \times W$ 或更多。

总结：

• 每个参考字符存储 $k+1$ 个状态位向量。
• 每个位向量长度为 $W$（如 128 位）。
• 总存储量 = 参考字符数 × (k+1) × W 位。
• 不是 $1 \times (k+1)$ 的标量矩阵，而是 $(k+1)$ 个 $W$ 位向量。