Skip to main content

1. GenASM-DC architecture

7. GenASM Hardware Design —— GenASM-DC Hardware 解释​

GenASM-DC 是 GenASM 框架中负责距离计算（Distance Calculation）的硬件加速器。它的设计目标是高效执行第 5 节中修改后的 Bitap 算法，生成中间位向量并计算最小编辑距离。其硬件架构基于线性循环脉动阵列（linear cyclic systolic array），并针对内存带宽和面积进行了优化。

下面从总体结构、处理元件、存储设计和数据依赖协调四个方面进行解释。

1. 总体架构：线性循环脉动阵列​

GenASM-DC 被实现为一个线性循环脉动阵列。脉动阵列的特点是：多个处理单元以规则的方式连接，数据在阵列中有节奏地流动，每个周期都有新的数据输入和结果输出。
“循环”指的是通过反馈逻辑，将部分输出重新送回输入端，从而在不增加额外内存端口的情况下，支持算法中反复迭代的需求。这种设计有助于：

  • 固定所需的内存端口数量；
  • 减少内存占用；
  • 提高数据复用率，降低对 DC-SRAM 的访问压力。

一个 GenASM-DC 加速器由处理块（Processing Block, PB）和控制与内存管理逻辑组成。PB 内部包含多个处理元件（Processing Elements, PEs）。

2. 处理元件（PE）与处理核心（PC）​

每个 PE 包含：

  • 一个处理核心（Processing Core, PC）；
  • 基于触发器的存储逻辑（用于暂存中间数据）。

PC 是主要计算单元，它实现了算法 1 中第 15–19 行的位运算，即对 ww 位查询模式执行近似字符串匹配。具体来说，PC 内部包含移位器、与门、或门等逻辑，用于计算每个编辑距离 dd 下的删除（D）、替换（S）、插入（I）和匹配（M）中间位向量，并最终按位与得到状态位向量 R[d]R[d]。

PE 的数量是可配置的，根据计算需求、面积、内存带宽和功耗进行权衡。例如，论文中常采用 64 个 PE，每个 PE 处理 64 位。

3. 存储设计：DC-SRAM 与 TB-SRAM​

GenASM-DC 使用两种 SRAM 缓冲区：

（1）DC-SRAM​

  • 作用：存储参考文本、查询模式的模式位掩码（Pattern Bitmask），以及 PE 产生的中间数据（如 oldR 值和跨字移位所需的 MSB）。
  • 容量示例：对于 64-PE 配置，每个 PE 处理 64 位，处理一个 10Kbp 的长读长（错误率 15%），对应文本区域约 11.5Kbp，DC-SRAM 总共需要 8KB。
  • 访问特点：通过依赖感知的映射，单个 PB 对 DC-SRAM 的访问被限制为每周期一次读和一次写，极大降低了带宽需求。

（2）TB-SRAM​

  • 作用：存储 GenASM-DC 生成的中间位向量（匹配、插入、删除），供后续的 GenASM-TB（回溯）模块使用。
  • 容量示例：每个 PE 拥有一个专用的 TB-SRAM，容量为 1.5KB，单读写端口。64 个 PE 共需 96KB TB-SRAM。
  • 写入带宽：每个周期，每个 PE 向自己的 TB-SRAM 写入 192 位（24 字节） 的数据。

这种分离式存储设计既满足了 DC 阶段对中间数据的快速暂存，又为 TB 阶段提供了必要的位向量记录。

4. 数据依赖协调与循环展开​

第 5 节提到，原始 Bitap 存在两级数据依赖，GenASM-DC 通过循环展开消除了这些依赖，使得多个位向量可以并行计算。硬件上，这种并行性通过将图 5 中的每个线程（列）映射到一个 PE 来实现。

每个 PE 中有两个触发器，用于协调跨 DC 迭代的数据依赖。以图 5 中的目标单元 T2-R2T2\text{-}R2 为例：

  • T2-R2T2\text{-}R2 由 PExPE_x 在 CycleyCycle_y 生成，对应 R[d]R[d]。
  • 为了生成它，需要：
    • T2-R1T2\text{-}R1（对应 R[d−1]R[d-1]）：由 PEx−1PE_{x-1} 在 Cycley−1Cycle_{y-1} 生成；
    • T1-R1T1\text{-}R1（对应 oldR[d−1]oldR[d-1]）：由 PEx−1PE_{x-1} 在 Cycley−2Cycle_{y-2} 生成；
    • T1-R2T1\text{-}R2（对应 oldR[d]oldR[d]）：由 PExPE_x 在 Cycley−1Cycle_{y-1} 生成。

其中 xx 是 PE 索引，yy 是周期索引。通过这种依赖感知的映射，GenASM-DC 能够：

  • 在正确的周期将所需数据从相邻 PE 或自身触发器传递过来；
  • 无论实例化多少个 PE，都能保证单个 PB 对 DC-SRAM 的访问仅为每周期一次读和一次写；
  • 实现高度并行且规则的数据流，非常适合脉动阵列架构。

5. 可扩展性与优势​

GenASM-DC 的硬件设计具有以下优势：

  • 高并行度：通过循环展开和文本级并行，多个 PE 可同时计算不同文本位置和编辑距离的位向量。
  • 低内存带宽：依赖感知映射和片上 SRAM 缓存，使得外部内存访问极少，主要带宽用于读取参考文本和查询序列。
  • 线性扩展：性能随 PE 数量线性增长，便于根据面积和功耗预算调整配置。
  • 与 GenASM-TB 协同：DC 阶段产生的中间位向量被写入 TB-SRAM，为后续回溯提供完整信息。

总结​

GenASM-DC 硬件是一个基于线性循环脉动阵列的加速器，由多个 PE 组成，每个 PE 内含一个 PC 和触发器存储。它通过专门的 DC-SRAM 和 TB-SRAM 分别存储输入/中间数据和回溯所需位向量，并利用依赖感知映射和循环展开，在硬件层面高效实现了修改后的 Bitap 算法。这种设计使得 GenASM-DC 能够以低内存带宽、高并行度和可扩展的方式，快速完成近似字符串匹配中的距离计算任务。