🏠

Prime Factor FFT 流水线图模块 (prime_factor_fft_pipeline_graphs)

一句话概括

本模块在 AMD AIE-ML 硬件上实现了一个 1008 点素因子 FFT (Prime Factor FFT)，将一个大 FFT 分解为三个互素的小 DFT (7 点、9 点、16 点)，并通过多级重排和转置在 AI 引擎阵列上构建高效的流水线处理图。

问题空间：为什么要做素因子 FFT？

传统 FFT 的困境

标准 Cooley-Tukey FFT 要求变换长度为 2^N（基-2）或复合数。当你需要一个非 2 的幂次的 FFT（如 1008 点）时，你有几个选择：

  1. 补零到最近的 2 的幂（1024 点）：简单，但浪费计算和存储
  2. 混合基 FFT（如 1008 = 2^4 x 3^2 x 7）：灵活，但控制流复杂
  3. 素因子算法 (PFA)：将 N = N1 x N2 x N3 且 gcd(Ni, Nj) = 1，完全消除旋转因子 (twiddle factors)

PFA 的核心优势

PFA 消除了 FFT 蝶形运算中的复数旋转因子乘法，将 N 点 FFT 分解为：

  • 输入重排（索引映射）
  • 小 DFT 块（长度互素）
  • 输出重排

对于 1008 = 7 x 9 x 16：

  • 7 点、9 点、16 点 DFT 分别映射到 AIE 核心
  • 无需复数旋转因子硬件
  • 中间数据通过 AIE 流网络转置

架构全景：流水线图的心理模型

工厂流水线类比

想象一个三阶段的工厂流水线，处理 1008 个零件的批次：

  1. 预处理车间 (Permute I)：将零件按特殊顺序排列，确保后续车间能并行处理
  2. 第一加工车间 (7 点或 9 点 DFT)：7 条并行流水线，每条处理 144 个零件
  3. 中转仓库 0 (Transpose 0)：重新整理零件，准备下一阶段
  4. 核心加工车间 (16 点 DFT)：16 条高吞吐流水线
  5. 中转仓库 1 (Transpose 1)：再次整理零件
  6. 第二加工车间 (9 点或 7 点 DFT)：完成剩余加工
  7. 后处理车间 (Permute O)：按原始顺序重组零件

AIE 图的核心抽象

在代码层面，这个工厂是一个数据流图 (ADF Graph)：

  • 节点 (Kernel)：运行在 AIE 核心上的 C++ 函数（DFT 计算、转置、重排）
  • 边 (Stream)：AIE 流网络连接的 FIFO 通道，单生产者-单消费者
  • PLIO：可编程逻辑 I/O，连接 AIE 阵列到外部 PL (Programmable Logic) 或 DDR

子模块划分与职责

本模块按 PFA 算法的数学结构划分为三个子模块，每个子模块封装特定的计算阶段：

1. 互素小 DFT 阶段 (co_prime_small_dft_stages)

包含组件：dft7, dft9

职责：

  • 实现 7 点和 9 点离散傅里叶变换
  • 利用互素特性（gcd(7,9)=1）支持 PFA 算法
  • 通过多核并行处理大量小 DFT 组（144 组 7 点或 112 组 9 点）

设计要点：

  • DFT7 使用 3 个 AIE 核心横向排列在同一行
  • DFT9 使用 4 个 AIE 核心排列在相邻行
  • 小 DFT 使用直接矩阵乘法或 Winograd 算法而非蝶形运算

查看详细文档

2. 基-16 DFT 阶段 (radix16_dft_stage)

包含组件：dft16

职责：

  • 实现 16 点离散傅里叶变换，作为 PFA 的中间维度
  • 利用 16 是 2 的幂的特性，支持基-2 或基-4 快速算法
  • 作为计算密集型核心，平衡整个流水线的吞吐

设计要点：

  • 仅使用 2 个 AIE 核心（少于 DFT7/9），因为需要处理的 16 点组数最少（63 组）
  • 核心放置在与 DFT7 同一行但不同列，形成连续流水线
  • 16 点 DFT 可使用优化的基-4 或分裂基算法

查看详细文档

3. 数据重排与转置阶段 (data_reordering_and_transpose_stages)

包含组件：permute_i, transpose0, transpose1

职责：

  • permute_i：执行 Good-Thomas 算法的输入索引映射（重排）
  • transpose0：第一级小 DFT 后的矩阵转置，重排数据维度
  • transpose1：16 点 DFT 后的矩阵转置，准备第二级小 DFT

设计要点：

  • 重排和转置是 PFA 的关键步骤，实现无旋转因子的 FFT
  • 转置在 AIE 核心本地内存中完成，利用高带宽内存访问
  • 每个转置阶段都改变数据在内存中的布局，匹配下一阶段 DFT 的访问模式
  • 输出重排（permute_o，在 DFT9/7 第二级后）恢复自然顺序

查看详细文档

与系统其他部分的交互

上游依赖

本模块作为 AIE 图实现，依赖 AMD/Xilinx 提供的标准工具链：

下游消费者

本模块是完整 1008 点 PFA FFT 设计的一部分，通常与以下模块协同工作：

数据契约

  • 输入格式：PLIO 期望 64 位宽的复数样本（通常为 cint16 打包为 32 位实部+32 位虚部，或 16+16）
  • 输入源：默认从文本文件 data/sig_i.txt 读取，实际系统通常连接 DMA 数据源
  • 输出目标：输出到 data/sig_o.txt，实际系统通常连接 DMA 数据接收器
  • 批量处理：aie_dut.run(8) 表示一次运行处理 8 个 1008 点变换批次

新贡献者必读：陷阱与注意事项

1. Tile 位置冲突

问题：如果你添加新核或移动现有核，很容易将两个核放在同一个 tile，导致编译错误。

检查清单：

  • 确保每个 tile(X, Y) 组合在全局范围内唯一
  • 使用 AMD 的 x86sim 或 aiesim 仿真器验证布局无冲突
  • 注意 DFT7 (Y+0) 和 DFT9 (Y+1) 虽然行不同，但可能在阵列边界处冲突

2. 流深度（FIFO 深度）不足

问题：如果某阶段处理速度不匹配，流缓冲区可能溢出或下溢。

常见原因：

  • DFT16 只有 2 个核心，如果输入速率过高，可能成为瓶颈
  • 转置阶段需要足够缓冲区来重组数据

调试方法：

  • 使用 aiecompiler 的 --dump-graph 选项查看流连接
  • 在 connect<stream> 中显式指定 FIFO 深度（如果支持）
  • 使用仿真器检查 stall 周期

3. 核心启动顺序依赖

问题：虽然 AIE 图是数据驱动的，但某些核可能有隐式初始化顺序要求。

注意点：

  • init() 调用会启动所有核心，但核心实际开始执行取决于数据到达
  • 确保输入数据在 run() 前已准备好，或理解流控的反压行为

4. 数值溢出和定标

问题：定点 FFT 很容易在中间计算中溢出。

定标策略：

  • 了解每个 DFT 阶段的增益：7/9/16 点 DFT 有不同的峰值增益
  • 典型的 AIE FFT 实现使用块浮点（block floating point）或每个阶段除以 2
  • 检查输出文件的动态范围，确保没有削波

调试技巧：

  • 使用 x86sim 生成 Golden 参考输出
  • 对比 MATLAB/Python 的 FFT 结果
  • 逐步检查每个阶段的中间输出（如果可能）

5. 时钟和吞吐率匹配

问题：AIE 核心、PLIO 和外部存储器可能有不同的时钟域。

考虑因素：

  • AIE 核心通常运行在 1 GHz
  • PLIO 的吞吐率取决于 plio_64_bits 和时钟配置
  • 确保 DMA 能够足够快地供应/消费数据以保持流水线满载

优化建议：

  • 使用 plio_64_bits 最大化吞吐
  • 考虑使用 PL 侧的 HLS 核进行数据重排，减轻 AIE 的 Permute 负担
  • 仿真时监控 stall 周期和吞吐率

总结

prime_factor_fft_pipeline_graphs 模块是一个教学与实战并重的 AIE-ML 设计范例。它展示了如何在 AMD AI 引擎上实现高性能的信号处理流水线：

  • 算法层面：利用素因子算法消除旋转因子，用规整的小 DFT 替代复杂的大 FFT
  • 架构层面：通过显式的核心布局和流连接，将数学流水线映射到物理 AIE 阵列
  • 工程层面：平衡了吞吐、延迟、资源使用和可维护性

对于新加入的工程师，理解这个模块不仅是学习一个 FFT 实现，更是掌握如何在 AIE 架构上思考和设计并行流水线的范本。

On this page