3. PE and neighboring PE

在 GenASM-DC 中，一个处理块（PB）内的多个处理元件（PE）按顺序排列，每个 PE 负责查询模式的一个 $w$ 位字。相邻 PE 之间不是独立的，而是通过跨字进位传递和数据依赖通信紧密耦合，共同维护完整的多字位向量并完成并行计算。它们的联系主要体现在以下三个方面。

---

1. 跨字移位：MSB 与 LSB 的进位传递

当查询模式长度 $m$ 超过字长 $w$ 时，状态位向量 $R[d]$ 被拆分成多个 $w$ 位的字，每个 PE 持有其中一个字。左移操作（消耗一个模式字符）需要整个多字位向量同步滑动：

• 低位字的 MSB 溢出：当 PE 对其字进行左移时，最高有效位（MSB）会移出字外。
• 传递给高位字：这个溢出的位必须作为相邻更高位 PE 的最低有效位（LSB）输入，在移位时载入。
• 连接方式：PE $i$ 的 MSB 输出连接到 PE $i+1$ 的 LSB 输入。这样，整个位向量就像一个连续的位串一样滑动，保证跨字边界的匹配信息不丢失。

例如，若 PE0 处理模式的最低 $w$ 位，PE1 处理接下来的 $w$ 位，则 PE0 的 MSB 输出送入 PE1 的 LSB，依此类推。所有 PE 协同完成一次完整的左移。

---

2. 数据依赖：循环展开中的相邻 PE 通信

GenASM-DC 通过循环展开消除了原始 Bitap 的两级数据依赖，但计算某个状态 $R[d]$ 仍需要来自相邻 PE 和自身 PE 的历史数据。论文以目标单元 $T2\text{-}R2$（文本位置 2，编辑距离 2）为例说明：

• $T2\text{-}R2$ 由 $PE_x$ 在 $Cycle_y$ 生成，对应 $R[d]$。
• 它依赖于：
  • $T2\text{-}R1$（即 $R[d-1]$）：由 相邻的左边 PE（$PE_{x-1}$）在 前一个周期（$Cycle_{y-1}$）生成；
  • $T1\text{-}R1$（即 $oldR[d-1]$）：由 相邻的左边 PE（$PE_{x-1}$）在 前两个周期（$Cycle_{y-2}$）生成；
  • $T1\text{-}R2$（即 $oldR[d]$）：由 自身 PE（$PE_x$）在 前一个周期（$Cycle_{y-1}$）生成。

因此，PE 之间需要按照严格的时序传递数据：

• 左边 PE 在较早周期计算出的 $R[d-1]$ 和 $oldR[d-1]$ 必须及时送达右边 PE，用于计算更高编辑距离的 $R[d]$。
• 每个 PE 内部有两个触发器，用于暂存 oldR 值和跨字进位位，确保在正确的周期将数据传递给相邻 PE 或自身下一级。

这种依赖感知的映射使得无论实例化多少个 PE，单个 PB 对 DC-SRAM 的访问都能限制为每周期一次读和一次写，极大降低了内存带宽压力。

---

3. 脉动阵列中的数据流动

所有 PE 构成一个线性循环脉动阵列。数据（如模式位掩码、文本字符、中间位向量）从 DC-SRAM 加载后，在 PE 阵列中按节奏传播：

• 每个周期，PE 接收来自左边 PE 的数据（如 $R[d-1]$、进位位），结合自身存储的 oldR 和当前文本字符的模式位掩码，计算本字的中间位向量。
• 计算结果一方面写入自己的 TB-SRAM，另一方面将需要传递的位（MSB、$R[d]$ 等）发送给右边相邻 PE 或反馈回自身。
• 这种规则的数据流使得计算可以高度流水线化，性能随 PE 数量线性扩展。

---

总结

联系类型	说明
跨字进位	低位 PE 的 MSB 输出连接到高位 PE 的 LSB 输入，实现多字位向量整体左移。
数据依赖	计算 $R[d]$ 需要相邻左边 PE 在之前周期产生的 $R[d-1]$ 和 $oldR[d-1]$，以及自身 PE 产生的 $oldR[d]$。
时序协调	每个 PE 用两个触发器暂存历史数据和进位，确保在正确周期传递给相邻 PE。
脉动流动	数据在 PE 阵列中按周期传播，形成流水线，降低对 DC-SRAM 的带宽需求。

因此，相邻 PE 之间通过进位链和依赖数据传递紧密协作，共同完成一个查询模式的多字位向量计算。这种设计是 GenASM-DC 能够支持长读长、保持高并行度和低内存带宽的关键。