Prime Factor FFT 分解图 (prime_factor_fft_decomposition_graphs)

一句话概述

本模块实现了素因子算法（Prime Factor Algorithm, PFA）FFT在 AMD Versal AI Engine 上的硬件加速设计。它将一个大尺寸 DFT（离散傅里叶变换）分解为多个互质小尺寸 DFT 的级联计算，利用 AI Engine 的向量矩阵乘法能力高效执行核心运算，同时通过可编程逻辑（PL）处理复杂的数据重排和转置操作——这就像把一道复杂的数学题拆解成几道简单的小题，再按特定顺序组装答案。

问题空间与设计动机

核心问题：大尺寸 FFT 的计算瓶颈

在数字信号处理中，FFT 是最基础也是计算最密集的运算之一。传统 Cooley-Tukey 算法虽然广泛使用，但存在两个关键限制：

1. 旋转因子（Twiddle Factor）开销：在各级蝶形运算之间需要进行大量的复数乘法来计算旋转因子，这消耗了显著的计算资源和功耗。
2. AI Engine 的适配性：Versal AI Engine 对小尺寸 DFT（\(N < 32\)）的向量矩阵乘法有极佳的支持，但对大尺寸 FFT 的直接实现效率不高。

为什么选择素因子算法？

PFA 提供了一种优雅的解决方案。当变换长度 \(N\) 可以分解为互质因子的乘积 \(N = N_1 \times N_2 \times ... \times N_k\) 时：

• 无旋转因子：由于因子间互质，PFA 完全消除了级间的旋转因子乘法，这是与 Cooley-Tukey 的本质区别。
• 维度分解：将一维 DFT 转换为多维 DFT，每个维度独立计算小尺寸变换。
• AI Engine 友好：小尺寸 DFT（如 7、9、16 点）恰好适合 AI Engine 的向量处理能力。

权衡与代价

PFA 的主要代价是复杂的 I/O 置换（Permutation）：输入数据需要按照特定的数学规则重新排序，输出同样需要逆序还原。这种重排不是简单的连续内存访问，而是基于模运算的分散-聚集模式。

设计决策：在 Versal 架构中，这个"缺点"被转化为优势——使用 PL（可编程逻辑）通过 HLS 实现专门的置换核，与 AI Engine 形成紧耦合的异构流水线。

心智模型：三维立方体中的数据流

想象一个 \(7 \times 9 \times 16\) 的三维数据立方体（这正是本设计中 1008 点 FFT 的分解）：

         N3=16
           ↑
          /|
         / |
        /  |      每个维度上的变换
       /   |      ━━━━━━━━━━━━━━━━
      +----+----→ N2=9           DFT-7: 沿 X 轴（长度 7）
      |    |/                    DFT-9: 沿 Y 轴（长度 9）
      |    +                     DFT-16: 沿 Z 轴（长度 16）
      |   /
      |  / N1=7
      | /
      +/

数据流动的五个阶段：

1. 输入置换：原始序列被打散，按特定模式填入立方体
2. 第一维变换（DFT-7）：沿 X 轴方向对每行做 7 点 DFT
3. 转置1：数据从"行优先"转为"列优先"，准备第二维变换
4. 第二维变换（DFT-9）：沿 Y 轴方向做 9 点 DFT
5. 转置2：再次重排，准备第三维变换
6. 第三维变换（DFT-16）：沿 Z 轴方向做 16 点 DFT
7. 输出置换：将结果从立方体映射回线性输出序列

这种思维方式帮助理解为什么需要 PL 进行数据重排——AI Engine 专注于高效的向量计算，而 PL 负责灵活的数据路由。

架构概览

组件职责说明

核心抽象：Graph 与 Kernel 的层次结构

本模块采用**分层图（Hierarchical Graph）**设计模式，这是 ADF（AI Engine Data Flow）框架的核心范式：

三层嵌套结构

pfa1008_graph (顶层集成图)
├── dft7_graph (7点DFT子图)
│   ├── k_tile0: dft7_compute (计算核)
│   ├── k_tile1: dft7_compute (计算核)
│   └── k_tile2: dft7_combine (合并核)
├── dft9_graph (9点DFT子图)
│   ├── k_tile0-k_tile2: dft9_compute
│   └── k_tile3: dft9_combine
└── dft16_graph (16点DFT子图)
    ├── k_tile0-k_tile3: dft16_compute
    └── k_tile4: dft16_combine

设计意图解读

为什么采用这种分层结构？

1. 模块化验证：每个 DFT 子图可以独立仿真测试（见 dft7_app.cpp、dft9_app.cpp、dft16_app.cpp）
2. 代码复用：相同的 dftX_compute 模板类被多个计算核实例化，仅系数不同
3. 物理映射清晰：子图内部的核 placement 与顶层系统集成时的 placement 分离，便于布局优化

Compute Kernel vs Combine Kernel 的分工：

• Compute Kernel：执行实际的向量矩阵乘法 DFT 计算，需要旋转因子系数
• Combine Kernel：将多个并行计算通道的结果汇总，完成最终的数据整理和输出格式化

这种分离反映了 SIMD 并行处理的典型模式——先并行计算，后归约合并。

数据流详解

端到端数据路径

以完整的 PFA-1008 处理为例，追踪一个样本块的生命周期：

阶段1: 输入置换 (PL)
├─ 输入: 1008个复数样本，多相序，双128-bit流
├─ 处理: 写入ping-pong缓冲(4x复制)，按LUT地址读取
└─ 输出: 7点变换分组，交替发送到两路流

阶段2: DFT-7计算 (AIE)
├─ 输入: 每流7个样本构成一个变换
├─ 处理: 
│   ├─ k_tile0/k_tile1并行计算(各处理一半)
│   └─ mac8()指令每周期完成2个[1x1]x[1x4]运算
└─ 输出: 4*NFFT样本到合并核，再输出到双路流

阶段3: 转置1 (PL)
├─ 输入: DFT-7结果，双路流
├─ 处理: 线性写入，stride-7读取(7点间隔)
└─ 输出: 9点变换分组，准备DFT-9

阶段4-7: 类似流程继续...

流式接口契约

所有 AI Engine kernel 遵循统一的流式数据契约：

• 输入宽度：双路 input_stream<TT_DATA>*，支持 64-bit PLIO
• 输出宽度：双路 output_stream<TT_DATA>*
• 数据类型：cint16（16位复数整数）
• 吞吐量目标：2 Gsps（SSR=2）

关键设计决策分析

决策1：互质因子选择 (7 × 9 × 16 = 1008)

为什么选择这三个数？

• 7 和 9：小素数/素数幂，AI Engine 的向量矩阵乘法对其有极高效率
• 16：2的幂次，可用优化的基-2/基-4结构，同时也是 AI Engine 向量宽度的倍数
• 互质性：确保 PFA 的无旋转因子特性成立

替代方案：使用 \(1008 = 16 \times 63\) 的二维分解会更简单，但会损失三维分解带来的并行度和灵活性。

决策2：计算核与合并核的分离

观察 dft7_graph 的结构：

k_tile0 = kernel::create_object<TT_COMPUTE>(...);  // 计算核0
k_tile1 = kernel::create_object<TT_COMPUTE>(...);  // 计算核1
k_tile2 = kernel::create_object<TT_COMBINE>();     // 合并核

为什么不用单个核完成全部工作？

• 资源平衡：DFT-7 的计算需要 2 个 tile 才能满足吞吐量，但输出需要合并为统一格式
• 专业化分工：计算核专注于 MAC 运算，合并核处理数据重组
• 效率差异：DFT-9 中 tile2 只有 25% 效率，分离后不影响其他 tile

决策3：显式物理位置约束

代码中大量使用 location<kernel>()、location<buffer>() 等约束：

// DFT7 Placement: 2x2方块，左下角为(LOC_X, LOC_Y)
location<kernel>(dft7.k_tile2) = tile(LOC_X+0, LOC_Y+0);
location<kernel>(dft7.k_tile0) = tile(LOC_X+1, LOC_Y+0);
location<kernel>(dft7.k_tile1) = tile(LOC_X+0, LOC_Y+1);

设计考量：

• 延迟优化：相邻 tile 之间的数据通路延迟最低
• 存储器 bank 分配：显式指定 stack、parameter、buffer 的位置避免冲突
• 外部堆栈：k_tile2 的 stack 故意放在 2x2 方块左侧，释放内部 bank 给缓冲区

决策4：模板参数化设计

template<class TT_DATA, class TT_TWIDDLE, class TT_ACC, unsigned NFFT>
class dft7_compute { ... };

收益：

• 类型安全：编译期确定数据精度（cint16）、累加器宽度（cacc48）
• 代码复用：同一模板用于 DFT-7/9/16，仅需实例化不同参数
• 编译优化：常量表达式（如 NSAMP_I = 7*NFFT/2）可在编译期计算

与新贡献者相关的注意事项

隐式契约与前置条件

1. NFFT 的约束：

   • DFT-7: NFFT = 9*16 = 144（来自 dft7_graph.h）
   • DFT-9: NFFT = 7*16 = 112
   • DFT-16: NFFT = 7*9 = 63

   修改这些值会破坏与其他阶段的样本数量匹配。

2. 缓冲区大小计算：

   static constexpr unsigned NSAMP_I = 7*NFFT/2;  // 输入样本数
   static constexpr unsigned NSAMP_O = 4*NFFT;    // 输出样本数
   

   这些公式基于特定的数据打包方式，更改会影响内存布局。

3. 系数数组对齐：

   alignas(16) TT_TWIDDLE (&coeff)[COEFF_DEPTH];
   

   旋转因子表必须 16 字节对齐，以满足 AI Engine 向量加载要求。

常见陷阱

调试建议

1. 分层验证：先在单个子图（如 dft7_app.cpp）上验证正确性，再集成到完整系统
2. 数据文件检查：data/ 目录下的 .txt 文件用于仿真验证，格式为每行一个十六进制复数值
3. Matlab 参考：matlab/ 目录提供黄金参考模型，可用于对比输出

跨模块依赖关系

上游依赖

• Vitis_Platform_Creation.Feature_Tutorials.03_Vitis_Export_To_Vivado.Makefile.graph：构建系统继承的 Makefile 基础设施

下游使用者

• prime_factor_fft_pipeline_graphs：父模块，包含本模块作为子组件
• prime_factor_fft_system_integration：系统集成层，将本设计与 DMA、PL 核连接

相关设计

• channelizer_ifft_and_tdm_fir_graphs：同样使用频域变换技术的设计
• fft_reference_and_host_orchestrated_transforms：FFT 参考实现对比

子模块文档

本模块包含三个核心 DFT 子图实现，每个都有独立的详细文档：

• dft7_subgraph：7点DFT图，2计算核+1合并核结构
• dft9_subgraph：9点DFT图，3计算核+1合并核结构
• dft16_subgraph：16点DFT图，4计算核+1合并核结构

以及顶层集成图：

• pfa1008_top_graph：完整的1008点PFA FFT集成图

总结

Prime Factor FFT Decomposition Graphs 模块展示了如何在 Versal 架构上将数学算法优雅地映射到异构硬件。其核心洞察在于：

1. 算法层面：利用 PFA 的无旋转因子特性，将大尺寸 FFT 分解为 AI Engine 友好的小尺寸 DFT
2. 架构层面：明确划分 AI Engine（密集计算）和 PL（灵活数据路由）的职责边界
3. 工程层面：通过分层图结构和显式物理约束，实现高性能且可维护的设计

对于新加入团队的开发者，建议从阅读 dft7_graph.h 开始，理解最基本的计算-合并模式，然后逐步扩展到完整的 pfa1008_graph。Matlab 参考模型 (matlab/fft_pfa_3d.m) 是理解算法行为的宝贵资源。