Skip to main content

1. PE and query read

在 SeGraM 的 BitAlign 中，PE 并不是把 query read 切成不同连续片段分给不同 PE。BitAlign 采用位并行（bit-parallel）和 systolic array：每个 PE 的位向量宽度是 128 bit，对应 query read 当前窗口中的 128 个连续碱基/位置。也就是说，PE 内 bitvector 的第 ii 位对应 query read 窗口中的第 ii 个字符。每个 PE 内部都对这 128 位并行做 Bitap/BitAlign 的位运算。

具体来说：

  • BitAlign 先把 query read 和线性化后的参考子图切成重叠窗口；在 SeGraM 的配置中，窗口长度等于每个 PE 的位宽，即 128。所以每个 PE 负责的是“当前 query read 窗口的 128 个位置”的匹配状态，而不是 query read 的某一段独立子串。
  • 不同 PE 主要对应参考图的不同节点/拓扑排序后的迭代。每个 PE 根据当前图节点字符 curChar 选择对应的 PatternBitmask，即 PM[curChar]。这个 bitmask 的每一位表示 query read 窗口中对应位置是否等于该参考字符。
  • 因此，所有 PE 使用的是同一个 query read 窗口的 pattern 信息，但每个 PE 用不同的参考图节点字符去与这个 query read 窗口做位并行匹配。

PE 之间的 query read 联系体现在 匹配状态位向量的传递，而不是 query read 片段的交换：

  • BitAlign 算法中，R[d]、oldR[d]、R[d-1] 等 bitvector 表示 query read 在不同编辑距离下的部分匹配状态。Bitap 里的左移 <<1 表示“消耗一个 query 字符”，也就是 query read 中的位置向前移动一位。
  • 在硬件中，PE 之间通过 systolic 链传递这些状态：
    • R[d-1] 由前一个 PE 直接提供给当前 PE；
    • hop queue register 把 oldR[d] 提供给同一个 PE，把 oldR[d-1] 提供给下一个 PE。
  • 这样，query read 的匹配状态可以沿 PE 链传播，相当于在 query read 的相邻字符位置之间传递匹配信息。
  • 对于基因组图中的 hop（非相邻节点），hop queue 会保存并延迟之前节点产生的 R[d] bitvector，使当前节点也能利用非相邻节点的 query read 匹配状态。

总结：
每个 PE 负责的是当前 query read 窗口的 128 位并行匹配状态；query read 的每个碱基对应 bitvector 中的一位。PE 之间不是划分 query read 的不同片段，而是通过 R[d-1]、oldR[d]、oldR[d-1] 等位向量传递同一个 query read 窗口在不同参考图节点/迭代下的匹配状态。