Skip to main content

8.2 BitAlign Accelerator

下面把论文 第 8.2 节 BitAlign Accelerator 拆开讲清楚。
这一节讲的是：BitAlign 算法在硬件上具体怎么实现。
核心是一个基于 脉动阵列（systolic array） 的位向量生成引擎，外加 hop queue 寄存器 来处理图中的跳跃边（hop），并用两个 scratchpad 存储输入和中间结果。

一、BitAlign 加速器的整体组成​

论文原文：

As shown earlier in Figure 4, the BitAlign accelerator consists of: (1) two computation blocks responsible for generating bitvectors to perform approximate string matching and edit distance calculation and traversing bitvectors to perform traceback; (2) two scratchpad blocks for storing the input data and intermediate bitvectors, and (3) hop queue registers for handling the hops.

翻译并拆解：

BitAlign 加速器由三部分组成：

  1. 两个计算模块：
    • 位向量生成模块：做近似字符串匹配和编辑距离计算；
    • 回溯模块：遍历位向量，执行 traceback，找到最优比对。
  2. 两个 scratchpad：
    • input scratchpad：存线性化参考图、HopBits、模式位掩码；
    • bitvector scratchpad：存中间位向量，供 traceback 使用。
  3. hop queue 寄存器：处理图中的 hop，把非相邻节点的位向量喂给当前处理单元。

二、核心：线性循环脉动阵列​

论文原文：

We implement the bitvector generation hardware of BitAlign as a linear cyclic systolic array based accelerator. While this design is based on the GenASM-DC hardware, our new design incorporates hop queue registers in order to feed the bitvectors of non-neighboring characters/nodes.

翻译：

BitAlign 的位向量生成硬件采用线性循环脉动阵列。
它基于 GenASM-DC 硬件，但新增了 hop queue 寄存器，用来喂入非相邻字符/节点的位向量。

什么是脉动阵列？
一种硬件结构，多个处理单元（PE）排成一行，数据像心跳一样在 PE 之间流动。
每个 PE 每个周期处理一部分数据，然后传给下一个 PE。
这样能实现高吞吐、低内存带宽的并行计算。

为什么用脉动阵列？
因为 alignment 需要大量位运算，且不同位置的计算有规律。
脉动阵列可以让数据在 PE 之间循环，减少对内存的访问。

三、PE（Processing Element）设计​

论文 Figure 11 展示了一个 PE 的结构。我们拆解它的工作方式。

1. 每个 PE 做什么？​

每个 PE 负责计算一个节点在某个编辑距离 d 下的状态位向量 R[d]R[d]。
它需要：

  • 当前节点的字符对应的模式位掩码（PatternBitmask）；
  • 来自前一个 PE 的 R[d−1]R[d-1]（用于插入）；
  • 来自 hop queue 的 oldR[d] 和 oldR[d-1]（用于匹配、删除、替换）；
  • HopBits 信息。

2. 数据流​

论文原文：

The R[d]R[d] bitvector generated by each processing element (PE) (i.e., hop bitvector) is fed to the tail of the hop queue register of the current PE. Each hop queue register then provides its stored bitvectors as the old R[d]R[d] bitvectors to the same PE (required for the match bitvector calculation), and as the old R[d−1]R[d - 1] bitvectors to the next PE (required for deletion and substitution bitvector calculation) in the next cycle. The R[d−1]R[d - 1] bitvector (required for insertion bitvector calculation) is directly provided by the previous PE (i.e., not through the hop queue registers).

翻译并解释：

  • 每个 PE 生成的 R[d]R[d] 位向量（也叫 hop bitvector）被送到当前 PE 的 hop queue 寄存器的尾部。
  • 下一个周期，hop queue 寄存器把存储的位向量提供出去：
    • 作为 old R[d]R[d] 给同一个 PE（用于计算匹配 M）；
    • 作为 old R[d−1]R[d-1] 给下一个 PE（用于计算删除 D 和替换 S）。
  • 而用于计算插入 I 的 R[d−1]R[d-1] 由前一个 PE 直接提供，不经过 hop queue。

通俗理解：
hop queue 就像一个延迟队列，把当前节点生成的位向量暂存起来，等需要时再喂给当前节点或下一个节点。
这样，当图中有 hop（非相邻边）时，当前节点可以直接从 hop queue 里拿到那些“远处”节点的位向量，而不需要重新计算或从内存读取。

3. HopBits 矩阵​

论文原文：

We implement the hop information between nodes of the graph as an adjacency matrix called HopBits. Based on the HopBits entry of the current text character, either the actual hop bitvector (if the HopBits entry is 1), or a bitvector containing all ones such that it will not have any effect on the bitwise operations (if the HopBits entry is 0), is used when calculating the match, deletion, and substitution bitvectors of the current PE.

翻译：

节点之间的 hop 信息用一个邻接矩阵 HopBits 表示。
对于当前字符，如果 HopBits 对应项为 1，就使用实际的 hop 位向量；
如果为 0，就使用一个全 1 的位向量，这样不会影响位运算结果。

Figure 12 展示了线性化子图和 HopBits 矩阵：

  • 如果从 NodeID_X 到 NodeID_Y 有出边（hop），则 HopBits 矩阵第 x 列第 y 行为 1；
  • 否则为 0（图中用“-”表示）。

这样，PE 在计算匹配、删除、替换时，会参考 HopBits，决定是否把 hop 节点的位向量纳入运算。

四、Hop Limit：为什么可以限制 hop 距离？​

论文原文：

In order to decrease the size of each hop queue register and the HopBits matrix, we perform an empirical analysis in Figure 13, where we measure the fraction of total number of hops in the graph-based reference genome that we can cover when we limit the distance between the farthest node to take into account and the current node (i.e., hop limit).

翻译：

为了减小 hop queue 寄存器和 HopBits 矩阵的大小，我们做了实验分析（Figure 13）：
限制“当前节点到最远 hop 节点的距离”（即 hop limit），看能覆盖多少比例的 hop。

Figure 13 结果：

  • 横轴：hop limit（节点数）；
  • 纵轴：覆盖的 hop 比例。

当 hop limit = 12 时，覆盖超过 99% 的 hop。

为什么？
论文解释：

This is a reasonable limit because a significant percentage of genetic variations in a human genome are either single nucleotide substitutions (SNPs) or small indels, which would result in short hops that connect near-vicinity vertices in the graph. On the other hand, even though large structural variations (SVs) would result in long hops connecting farther vertices, such SVs occur at a very low frequency.

翻译：
因为人类基因组中大部分遗传变异是 SNP 或小 indel，它们只产生短 hop，连接邻近节点。
大结构变异（SV）会产生长 hop，但出现频率很低。
所以在拓扑排序的图中，大多数节点的邻居都在附近。

结论：
选择 hop limit = 12，可以覆盖 >99% 的 hop，同时大幅减小硬件开销。

五、Scratchpad 大小​

论文原文：

BitAlign uses two types of SRAM buffers: (1) input scratchpad, which stores the linearized reference graph, associated HopBits for each node, and the pattern bitmasks for the query read; and (2) bitvector scratchpad, which stores the intermediate bitvectors generated during the edit distance calculation step and used during the traceback step.

翻译：

BitAlign 使用两种 SRAM 缓冲区：

  1. input scratchpad：
    • 存线性化参考图；
    • 每个节点的 HopBits；
    • query read 的模式位掩码。
  2. bitvector scratchpad：
    • 存编辑距离计算过程中生成的中间位向量；
    • 供 traceback 阶段使用。

具体大小（论文原文）：

For a 64-PE configuration with 128 bits of processing per PE (i.e., the width of bitvectors), BitAlign requires a total of 24kB24\mathrm{kB} in input scratchpad storage. Each PE also requires a total of 2kB2\mathrm{kB} bitvector scratchpad storage (128kB128\mathrm{kB} in total) and 192 B hop queue register storage (12kB12\mathrm{kB} in total). In each cycle, 128 bits of data (16 B) is written to each bitvector scratchpad and to each hop queue register by each PE.

翻译：

  • 配置：64 个 PE，每个 PE 处理 128 位（位向量宽度）；
  • input scratchpad：总共 24 kB；
  • 每个 PE 的 bitvector scratchpad：2 kB，64 个共 128 kB；
  • 每个 PE 的 hop queue 寄存器：192 B，64 个共 12 kB；
  • 每周期每个 PE 向 bitvector scratchpad 和 hop queue 写入 128 位（16 B）。

六、存储优化：只存 R[d]，减少 3 倍内存​

论文原文：

As we explain in Section 7, in order to decrease the memory footprint of the stored bitvectors required for traceback execution, we store only the ANDed version of the intermediate bitvectors (R[d])(R[d]) and re-generate the intermediate bitvectors (i.e., match, substitution, deletion, and insertion) during traceback. Thus, each element of the hop queue register has a length equal to the window size (W)(W) instead of 3∗W3*W. Similarly, with this design choice, the size of each bitvector scratchpad of each PE decreases by 3×3\times.

翻译：

如第 7 节所述，为了减少 traceback 所需位向量的内存占用，我们只存 AND 后的中间位向量 R[d]R[d]。
在 traceback 时，再按需重新生成匹配、替换、删除、插入这四种中间位向量。
因此，hop queue 寄存器的每个元素长度等于窗口大小 WW，而不是 3W3W。
同样，每个 PE 的 bitvector scratchpad 大小也减少了 3 倍。

为什么重要？
因为 alignment 硬件的主要面积和功耗来自内存。
减少 3 倍内存，可以显著降低面积和功耗，同时允许每个 PE 处理更多位（从 GenASM 的 64 位提升到 128 位），进一步提高并行度。

七、总结：第 8.2 节的核心逻辑​

  1. BitAlign 加速器 = 脉动阵列 + hop queue + 两个 scratchpad。
  2. 脉动阵列：多个 PE 并行计算位向量，数据在 PE 间循环流动。
  3. hop queue：解决图中非相邻节点的依赖，把远处节点的位向量暂存并喂给当前 PE。
  4. HopBits 矩阵：记录节点间是否有 hop，决定是否使用实际 hop 位向量。
  5. hop limit = 12：覆盖 >99% 的 hop，同时减小硬件开销。
  6. scratchpad 大小：
    • input：24 kB；
    • bitvector：每个 PE 2 kB，共 128 kB；
    • hop queue：每个 PE 192 B，共 12 kB。
  7. 存储优化：只存 R[d]R[d]，traceback 时重新生成中间向量，内存减少 3 倍，允许更宽的位处理（128 位）。

一句话：
BitAlign 加速器用脉动阵列并行生成位向量，用 hop queue 处理图中的跳跃边，用 HopBits 矩阵和 hop limit 控制硬件复杂度，并通过只存 R[d]R[d] 大幅减少内存，从而在硬件上高效完成 S2G 的 alignment。