🏠

Prime Factor Algorithm (PFA) FFT 深度解析 —— Vitis-Tutorials 实现

1. 问题陈述

1.1 形式化定义

给定长度为 \(N\) 的复数序列 \(x[n]\)，其中 \(N\) 可分解为两两互素的整数乘积：

\[N = N_1 \cdot N_2 \cdot \dots \cdot N_k, \quad \gcd(N_i, N_j) = 1 \quad \forall i \neq j\]
计算其离散傅里叶变换 (DFT)：
\[X[k] = \sum_{n=0}^{N-1} x[n] \cdot W_N^{nk}, \quad W_N = e^{-j2\pi/N}\]

1.2 Vitis-Tutorials 具体问题

本研究聚焦于 1008点 PFA FFT 的实现，其中 \(N=1008=16 \times 9 \times 7\)，满足互素约束，系统架构结合了 AMD Versal 器件的 AI Engine (AIE/AIE-ML) 和可编程逻辑 (PL)。

2. 直觉

2.1 朴素方案的局限性

  • 直接 DFT：时间复杂度为 \(O(N^2)\)，对于 \(N=1008\) 需要超过 100 万次复数乘法，无法满足实时信号处理的低延迟高吞吐要求。
  • Cooley-Tukey FFT：需要 \(N\) 为高复合数且依赖 twiddle factor 乘法，在硬件实现中会引入额外的计算和存储开销。
  • 纯软件重排：需要将数据在 AIE 和 DDR 之间反复搬移，造成严重的带宽瓶颈和延迟。

2.2 关键洞察

Prime Factor Algorithm (PFA) 的核心在于利用 中国剩余定理 (CRT) 将一维 DFT 映射为多维 DFT，从而：

  1. 完全消除 twiddle factor（当因子互素时）
  2. 支持并行计算小尺寸 DFT
  3. 通过索引置换将多维结果还原为一维顺序

Vitis-Tutorials 的实现进一步将计算和重排分离：

  • AIE：专注于计算小尺寸 DFT（16/9/7点）
  • PL：通过 HLS 实现高速流水线式的索引置换

3. 形式化定义

3.1 索引映射

对于 \(N=N_1 \cdot N_2\) 且 \(\gcd(N_1,N_2)=1\)，定义双射索引映射：

\[n = \left\langle a \cdot N_2 \cdot n_1 + b \cdot N_1 \cdot n_2 \right\rangle_N, \quad 0 \leq n_1 < N_1, 0 \leq n_2 < N_2\]
\[k = \left\langle c \cdot N_2 \cdot k_1 + d \cdot N_1 \cdot k_2 \right\rangle_N, \quad 0 \leq k_1 < N_1, 0 \leq k_2 < N_2\]
其中 \(a,b,c,d\) 为满足 CRT 条件的整数。

3.2 多维 DFT 分解

将索引代入 DFT 公式可得：

\[X[k_1,k_2] = \sum_{n_2=0}^{N_2-1} \left( \sum_{n_1=0}^{N_1-1} x[n_1,n_2] \cdot W_{N_1}^{n_1k_1} \right) \cdot W_{N_2}^{n_2k_2}\]
对于 \(N=1008=16 \times 9 \times 7\)，该式可扩展为三维 DFT。

3.3 置换约束

输入/输出置换需满足：

  • 每周期处理 8 个样本（与 AIE 吞吐匹配）
  • 启动间隔 (Initiation Interval, II) 为 1
  • 使用双缓冲乒乓机制避免停顿

4. 算法

4.1 顶层执行流程

flowchart LR A[输入流] --> B[输入置换 pfa1008_permute_i] B --> C[DFT16 计算] C --> D[DFT9 计算] D --> E[DFT7 计算] E --> F[输出置换 pfa1008_permute_o] F --> G[输出流] subgraph PL B F end subgraph AIE C D E end

4.2 核心置换算法伪代码

# Prime Factor FFT 置换核心算法
# 适用于输入/输出置换，仅 LUT 内容不同
Algorithm: PFA_Permute(permute_i, permute_o, PERM_ADDR)
    Input: permute_i[8] — 输入数据块
           PERM_ADDR — 预计算置换查找表
    Output: permute_o[8] — 输出数据块
    Static: ping — 乒乓缓冲选择位
            wr_addr — 写地址计数器
            rd_addr — 读地址计数器
            buff[2][4][4][NFFT/4] — 四维乒乓缓冲
            permute_lut[4][NFFT] — LUT 副本

    # 步骤 1: 地址生成
    for ss from 0 to 7 do
        rd_addr_use = permute_lut[ss >> 1][rd_addr + ss]
        addr[ss] = rd_addr_use[9:2]  # 8位索引
        offset[ss] = rd_addr_use[1:0] # 2位偏移
    end for

    # 步骤 2: 线性写入 4 副本
    wr_addrA = wr_addr[9:2]
    wr_addrB = (wr_addr + 4)[9:2]
    for i from 0 to 3 do
        for j from 0 to 3 do
            buff[ping][i][j][wr_addrA] = permute_i[i]
            buff[ping][i][j][wr_addrB] = permute_i[i + 4]
        end for
    end for

    # 步骤 3: 并行读取所有可能性
    for ss from 0 to 7 do
        data0[ss] = buff[!ping][0][0][addr[ss]]
        data1[ss] = buff[!ping][1][0][addr[ss]]
        data2[ss] = buff[!ping][2][0][addr[ss]]
        data3[ss] = buff[!ping][3][0][addr[ss]]
        # 重复读取剩余 3 个槽位
    end for

    # 步骤 4: 多相复用选择
    for ss from 0 to 7 do
        switch offset[ss] do
            case 0: permute_o[ss] = data0[ss]
            case 1: permute_o[ss] = data1[ss]
            case 2: permute_o[ss] = data2[ss]
            default: permute_o[ss] = data3[ss]
        end switch
    end for

    # 步骤 5: 更新状态
    last_wr = (wr_addr == NFFT - 8)
    last_rd = (rd_addr == NFFT - 8)
    ping = last_wr ? !ping : ping
    wr_addr = last_wr ? 0 : wr_addr + 8
    rd_addr = last_rd ? 0 : rd_addr + 8

4.3 输出置换状态机

stateDiagram-v2 [*] --> IDLE IDLE --> WRITE_INNER: wr_cnt16 < 8 WRITE_INNER --> WRITE_INNER: wr_cnt16 < 8 WRITE_INNER --> WRITE_MIDDLE: wr_cnt16 == 8 WRITE_MIDDLE --> WRITE_INNER: wr_cnt9 < 8 WRITE_MIDDLE --> WRITE_OUTER: wr_cnt9 == 8 WRITE_OUTER --> WRITE_INNER: wr_cnt7 < 6 WRITE_OUTER --> SWAP_PING_PONG: wr_cnt7 == 6 SWAP_PING_PONG --> IDLE IDLE --> READ: always READ --> READ: rd_addr < NFFT - 8 READ --> RESET_RD_ADDR: rd_addr == NFFT - 8 RESET_RD_ADDR --> READ

5. 复杂度分析

5.1 计算复杂度

组件 操作类型 每块数量 每块复杂度
DFT16 复数乘加 1008/16 = 63 \(O(16^2)\)
DFT9 复数乘加 1008/9 = 112 \(O(9^2)\)
DFT7 复数乘加 1008/7 = 144 \(O(7^2)\)
置换 查找/存储 1008/8 = 126 \(O(1)\)

总体计算复杂度：

\[T(N) = 63 \cdot 16^2 + 112 \cdot 9^2 + 144 \cdot 7^2 = 16128 + 9072 + 7056 = 32256\]
对比直接 DFT 的 \(O(N^2)=1016064\)，加速比约为 31.5x。

5.2 存储复杂度

组件 大小 说明
四维乒乓缓冲 \(2 \times 4 \times 4 \times 252 \times 32\) bit ~256 Kbit
置换 LUT \(4 \times 1008 \times 10\) bit ~40 Kbit
小尺寸 DFT 系数 随 DFT 大小变化 可忽略

总体存储复杂度：\(O(N)\)，主要由缓冲和 LUT 贡献。

5.3 时间特性

指标 数值 说明
目标时钟 312.5 MHz PL 侧约束
吞吐量 8 样本/周期 匹配 AIE 接口
启动延迟 252 周期 缓冲填充时间
II 1 无停顿流水线

6. 实现说明

6.1 理论与代码的差异

  1. 四维缓冲架构：代码中的 buff[2][4][4][NFFT/4] 是理论双缓冲的超集，增加了 4 副本以支持任意偏移的并行读取。
  2. LUT 复制：permute_lut[4][NFFT] 复制了 4 份 LUT，避免了单端口 LUT 的访问冲突。
  3. 写地址步长：输出置换中使用 offW += 63，这是由于 \(1008/16=63\)，反映了 PFA 的三维索引映射。

6.2 工程权衡

决策 收益 代价
4 副本存储 支持 II=1 的任意偏移读取 BRAM 用量增加 4 倍
静态 LUT 避免复杂的运行时模运算 需要离线生成 LUT 并占用存储
True Dual-Port BRAM 无缝乒乓切换 资源利用率略高
整块乒乓切换 控制逻辑简单 启动延迟较高

6.3 HLS 优化指令

  • #pragma HLS array_partition variable=buff dim=1：完全展开乒乓缓冲维度，支持并行读写
  • #pragma HLS bind_storage variable=buff type=RAM_T2P impl=bram：指定真双端口 BRAM 实现
  • #pragma HLS pipeline II=1：强制启动间隔为 1，实现高吞吐
  • #pragma HLS dependence variable=buff type=intra false：消除虚假数据依赖，允许并行访问

7. 比较

7.1 与经典算法对比

特性 PFA FFT (Vitis) Cooley-Tukey FFT 直接 DFT
计算复杂度 \(O(\sum N_i^2)\) \(O(N \log N)\) \(O(N^2)\)
Twiddle Factor 无 有 有
索引置换 复杂 简单 (位反转) 无
硬件并行度 高 (独立小 DFT) 中 低
适用 N 互素因子乘积 高复合数 任意

7.2 与其他 PFA 实现对比

特性 Vitis AIE+PL 纯 AIE 纯 PL
计算资源 AIE 用于 DFT AIE 用于所有 PL 用于所有
重排性能 PL 高速流水线 AIE 指令周期受限 PL 可实现但 DFT 效率低
带宽需求 最低 (AIE-PL 紧耦合) 中等 高 (PL-DDR 交互)
可扩展性 好 (模块化 DFT) 中 差 (重写 HLS 代码)

8. 总结

Vitis-Tutorials 中的 Prime Factor Algorithm (PFA) FFT 实现是一个精心设计的异构系统，充分发挥了 AMD Versal 器件中 AIE 和 PL 的优势：

  • AIE 高效计算小尺寸互素 DFT
  • PL 以高吞吐流水线方式处理复杂的索引置换
  • 四维乒乓缓冲和预计算 LUT 确保了 II=1 的无停顿操作

该实现的核心哲学是 "空间换时间"，通过增加存储副本和预计算资源，换取了确定的低延迟和高吞吐，非常适合实时信号处理应用。

On this page