Skip to main content

2. PE and neighboring PE

在 SeGraM 的 BitAlign 中，一个 PE 会在计算涉及编辑距离 d−1d-1 层的位向量时，用到相邻 PE 的匹配状态向量。具体来说，BitAlign 把内层循环 for d in 1:k 映射到 PE 链上：当前 PE 负责编辑距离 dd，前一个相邻 PE 负责 d−1d-1。因此：

  1. 计算 insertion 位向量时
    当前 PE 计算
    [ I = (allR[i][d-1] \ll 1) ] 需要当前图节点 ii 在 d−1d-1 层的状态向量 allR[i][d-1]。这个向量由前一个相邻 PE直接提供，不经过 hop queue。

  2. 计算 deletion 和 substitution 位向量时
    对于当前节点 ii 的每个后继节点 jj，需要： [ D = allR[j][d-1] ] [ S = allR[j][d-1] \ll 1 ] 即后继节点 jj 在 d−1d-1 层的状态向量。前一个相邻 PE 会通过 hop queue 把存储的 oldR[d-1] 传递给当前 PE，用于计算 deletion 和 substitution。

  3. 计算 match 位向量时不用相邻 PE
    match 需要的是后继节点 jj 在相同编辑距离 dd 层的状态： [ M = (allR[j][d] \ll 1) \mid curPM ] 这个 oldR[d] 由当前 PE 自己的 hop queue 提供，而不是相邻 PE。

所以，总结成一句话：
当当前 PE 要计算编辑距离 d>0d>0 的 insertion、deletion、substitution 位向量，即需要 d−1d-1 层匹配状态时，它会用到相邻 PE 的匹配状态向量。其中 insertion 直接用前一个 PE 的 R[d-1]，deletion/substitution 用前一个 PE 经 hop queue 传来的 oldR[d-1]；而 match 用的是同一 PE 的 oldR[d]，不涉及相邻 PE。