Skip to main content

2.5 Proposed Mapping and Dataflow

4.2 节 Proposed Mapping and Dataflow 的核心是：
在把 S2G 流水线映射到 PanGaea 的 PE 阵列上时，针对不同阶段的计算模式，设计两套高效的数据流——一套用于稀疏的线性链，一套用于密集的波前对齐。
这两套数据流都充分利用 PE 网格的通信能力，把归约、广播、邻居交换等操作嵌入阵列内部，避免专用硬件，提高灵活性和效率。

下面分模式解释。

1. Mode 1：Linear Chaining 的数据流​

计算模式​

线性链要计算：固定锚点 ii，遍历所有可能的 j<ij < i，求：

fi=max⁡j<i{fj+score(i,j)−penalty(Δx,Δy)}f_i = \max_{j< i}\{f_j + \mathrm{score}(i,j) - \mathrm{penalty}(\Delta x,\Delta y)\}

每个 PE 可以独立评估一个 (i,j)(i,j) 对。
所以最自然的映射是：每个 PE 负责一个 (i,j)(i,j) 对，144 个 PE 并行计算。

数据流：广播-单播-归约​

因为所有 PE 都要用到锚点 ii 的信息，而每个 PE 还需要不同的 jj，所以采用如下步骤：

  1. 广播：锚点数据 {ai:ai+15}\{a_i : a_{i+15}\} 通过共享总线（H-tree 分布）广播到所有 PE。
    实际上，数据从 PE0PE_0 发出，通过点对点连接到达每个 PE。
    这样所有 PE 都能拿到相同的 ii 信息。

  2. 并行计算：每个 PE 根据自己负责的 jj，计算 (i,j)(i,j) 对的分数。
    此时 144 个 PE 同时工作，得到 144 个候选分数。

  3. 归约：需要从 144 个分数中找出最大值和对应的最佳 j∗j^*。
    归约分两步：

    • 垂直通信：每一列 PE 先在本列内比较，把该列的最大分数送到第一行。
    • 水平通信：第一行各列的最大值再水平比较，最终 PE0PE_0 收到全局最大分数和最佳 jj。

  4. 存储：PE0PE_0 把结果写入 SRAM，供后续阶段使用。

为什么这样设计？​

  • 不需要单独的归约树硬件。归约用的 MAX 比较器直接嵌入 PE 的输出混合逻辑中。
  • 相比独立归约树，节省约 15% 面积，减少 3 个周期的延迟。
  • 通信利用 PE 网格的垂直-水平拓扑，自然且高效。

2. Mode 2A/2B：WFA 波前对齐的数据流​

计算模式​

波前对齐沿 DP 矩阵的对角线推进。
计算单元格 (s,d)(s,d) 时，需要之前波前的值，例如：

  • Hs−x,dH_{s-x,d}、Hs−(o1+e1),d−1H_{s-(o_1+e_1),d-1}、Hs−e1,d−1H_{s-e_1,d-1} 等；
  • EE 矩阵来自左侧，FF 矩阵来自右侧。

依赖关系是：计算 (s,d)(s,d) 需要 (s−δ,d±1)(s-\delta, d\pm 1) 的值，其中 δ\delta 是惩罚偏移。
相邻对角线之间共享大量数据，例如 (s,d)(s,d) 和 (s,d+1)(s,d+1) 都需要 (s−x,d)(s-x,d)。

数据流：邻居交换 + All-reduce​

因为依赖沿对角线方向，且相邻对角线有重叠，所以把 PE 组织成 2D 网格，让邻居之间直接交换数据：

  1. 水平交换：

    • 每个 PE 把计算出的 EE 矩阵发给右邻居；
    • 把 FF 矩阵发给左邻居。
    • 这样，每个 PE 都能从邻居那里得到自己需要的 EE 或 FF 值。

  2. All-reduce 通信：

    • 除了邻居交换，还需要把某些结果归约并广播到所有相关 PE。
    • 例如，图 6(c) 显示数据从 PE0PE_0 通过 All-reduce 发送到 PE5PE_5。
    • All-reduce 的含义是：先在所有 PE 间做归约（如取最大值），再把结果广播给所有 PE。
    • 这样每个 PE 都能获得全局一致的波前值，继续下一层计算。

  3. 多端口 scratchpad：

    • WFA 每周期每个 PE 需要多次读取 DP 矩阵（Mode 2A 需 9 次，Mode 2B 需 3 次）。
    • 所以局部 scratchpad 必须多端口，才能支撑这种密集访问。

为什么这样设计？​

  • 波前对齐是密集 DP，数据依赖规则且局部性强。
  • 用 2D 网格和邻居交换，可以把通信限制在相邻 PE 之间，减少长距离传输。
  • All-reduce 保证所有 PE 同步获得最新波前值，支持对角线推进。
  • Mode 2A 和 2B 共享算术单元，数据流也类似，只是读取的矩阵数量和来源层次不同。

3. 两套数据流的对比​

特性Mode 1（线性链）Mode 2A/2B（波前对齐）
计算模式稀疏 DP，每个 PE 算一个 (i,j)(i,j) 对密集 DP，沿对角线推进
映射方式每个 PE 负责一个 jjPE 对应 DP 矩阵的对角线单元
主要通信广播 + 垂直/水平归约邻居交换 + All-reduce
归约方式嵌入 PE 输出逻辑的 MAX 比较器All-reduce 归约并广播
优点无需专用归约树，节省面积和延迟利用局部依赖，减少通信，支持密集计算

4. 总结​

4.2 节提出的映射和数据流，本质上是根据计算模式的特点，选择最合适的 PE 间通信方式：

  • 线性链：数据共享多、需要全局归约 → 广播 + 网格归约。
  • 波前对齐：依赖沿对角线、局部重叠多 → 邻居交换 + All-reduce。

这两种数据流都尽量把通信和归约操作嵌入 PE 阵列内部，避免专用硬件，从而在同一个灵活 PE 阵列上高效支持 S2G 流水线的不同阶段。
最终效果是：减少硬件面积、降低延迟、提高 PE 利用率，为跨阶段融合提供基础。