🏠

FFT Output Permutation Kernel (pfa1008_permute_o)

一句话概括

这个模块是 Prime-Factor FFT 算法的输出端数据重排引擎。想象一下，FFT 计算完成后，数据就像是一副被打乱的扑克牌——虽然每张牌（样本）都在，但顺序完全错了。这个内核就是那个在硬件中以每周期 4 个样本的速率、不间断地将牌洗回正确顺序的"发牌员"。它通过巧妙的双缓冲乒乓架构和预计算的查找表，解决了素因子分解 FFT 中固有的复杂索引置换问题。

问题空间：为什么需要输出置换？

Prime-Factor FFT 的核心挑战

Prime-Factor Algorithm (PFA) FFT 是一种将大点数 FFT 分解为互素小点数 FFT 的算法。对于 N=1008=16×9×7 的情况：

1008点FFT = 16点DFT × 9点DFT × 7点DFT

这种分解带来了巨大的计算效率，但也引入了一个棘手的问题：数据在三维计算空间中流动后，输出顺序与自然顺序完全不同。

想象一个三维的数据立方体：

  • X轴：16点（DFT-16 维度）
  • Y轴：9点（DFT-9 维度）
  • Z轴：7点（DFT-7 维度）

数据在计算过程中按照 DFT-16 → DFT-9 → DFT-7 的顺序遍历这个立方体，但最终输出需要恢复到线性时间顺序。这就需要一个复杂的索引映射——即输出置换。

为什么不能用简单方案？

方案一：软件后处理

  • ❌ 需要将数据从 AI Engine 搬移到 DDR，CPU 重排后再搬回
  • ❌ 带宽瓶颈：1008点 × 8字节/样本 × 高采样率 = 巨大的内存流量
  • ❌ 延迟不可接受：实时信号处理场景无法容忍

方案二：AI Engine 内部重排

  • ❌ AI Engine 的计算资源宝贵，应用于核心 FFT 运算
  • ❌ 复杂的索引计算会消耗宝贵的指令周期
  • ❌ 数据局部性不佳，缓存效率低

方案三：当前 HLS 实现（最优解）

  • ✅ 在 PL (Programmable Logic) 中以硬件并行度完成重排
  • ✅ 每周期处理 4 个样本，与 AIE 吞吐量匹配
  • ✅ 使用 ping-pong 缓冲实现无停顿流水线
  • ✅ 预计算 LUT 避免运行时复杂索引运算

心智模型：理解这个模块的三种视角

视角一：邮局分拣系统 📮

想象一个高速运转的邮局分拣中心：

  • 输入：信件（样本）从不同的处理中心（DFT 阶段）到达，但顺序混乱
  • 缓冲区：两个巨大的分拣台（ping-pong buffer），一个接收新邮件时，另一个被读取
  • 查找表：每个地址对应一个"邮编到街道"的映射规则（PERM_O_ADDR LUT）
  • 输出：信件按照正确的街道门牌号（自然顺序）重新排列送出

视角二：四维数据魔方 🎲

核心数据结构 buff[2][4][4][NFFT/4] 可以看作：

维度 含义 取值范围
第1维 (2) Ping-Pong 切换 0=写入侧, 1=读取侧
第2维 (4) 多副本存储 支持任意偏移读取
第3维 (4) 样本位置 每周期4个样本的槽位
第4维 (252) 主存储深度 NFFT/4 = 1008/4 = 252

为什么要 4 个副本？因为输出置换可能要求从同一个 polyphase 的任意偏移位置读取连续样本。就像魔方的一个面，你需要能够从任何角度看到完整的颜色图案。

视角三：状态机流水线 ⏱️

┌─────────────┐    ┌─────────────┐    ┌─────────────┐
│   UNPACK    │───→│   PERMUTE   │───→│   WRITE     │
│  (解析输入)  │    │ (核心重排)   │    │ (流式输出)  │
└─────────────┘    └─────────────┘    └─────────────┘
      II=1              II=1               II=1

整个内核以 Initiation Interval = 1 运行，意味着每时钟周期都能开始处理一个新的 4 样本向量。

架构与数据流

flowchart LR subgraph Input["输入层"] A[AXI-Stream 128-bit] --> B[pfa1008_unpack] B --> C[permute_i数组] end subgraph Core["核心置换层"] C --> D[pfa1008_permute] D --> E[buff_ping写入侧] F[buff_pong读取侧] --> D G[PERM_O_ADDR_LUT] -.-> D D --> H[permute_o数组] end subgraph Output["输出层"] H --> I[pfa1008_write_streams] I --> J[AXI-Stream 128-bit] end style Core fill:#f9f,stroke:#333,stroke-width:2px

关键组件详解

1. pfa1008_unpack —— 数据解包器

void pfa1008_unpack( TT_STREAM& sig_i, TT_DATA (&permute_i)[4] )
{
  ( permute_i[3], permute_i[2], permute_i[1], permute_i[0] ) = sig_i.read();
}

设计意图：

  • 将 128-bit AXI-Stream 字拆分为 4 个 32-bit 样本
  • 注意索引顺序 [3,2,1,0] —— 这是为了匹配 AIE 的输出格式
  • 零开销操作：纯组合逻辑，不消耗时钟周期

类型定义（来自头文件）：

typedef ap_uint<32>            TT_DATA;    // 32-bit 样本（cint16）
typedef ap_uint<128>           TT_AXI4;    // 128-bit AXI 总线
typedef hls::stream<TT_AXI4>   TT_STREAM;  // HLS 流接口

2. pfa1008_permute —— 核心置换引擎

这是整个模块最复杂的部分，包含三个子阶段：

阶段 A：地址生成与 LUT 查找
READ_WRITE : for (int ss=0,offW=0; ss < 4; ss++,offW+=63) {
  TT_ADDR wr_addr_use = TT_ADDR(wr_addr + offW);
  TT_ADDR rd_addr_use = permute_lut[ss>>1][rd_addr+ss];
  wr_idx[ss].range(7,0) = wr_addr_use.range(9,2);  // 高位：索引
  rd_idx[ss].range(7,0) = rd_addr_use.range(9,2);
  wr_off[ss].range(1,0) = wr_addr_use.range(1,0);  // 低位：偏移
  rd_off[ss].range(1,0) = rd_addr_use.range(1,0);
}

关键洞察：

  1. 写地址步长 = 63：offW += 63 是因为数据按照 DFT-16 顺序写入（第三维度的 stride）

    • 1008 / 16 = 63，正好是 DFT-16 维度的大小

  2. LUT 双副本：permute_lut[2][NFFT] 配合 ss>>1 索引

    • 允许同时读取两个 LUT 条目（每周期需要 4 个读地址，分两组并行）

  3. 地址拆分：10-bit 地址拆分为 8-bit 索引 + 2-bit 偏移

    • 索引用于定位 buffer 行
    • 偏移用于选择 4 个 polyphase 副本之一
阶段 B：多路复用写入
// 根据偏移选择正确的索引和数据
mux_index( wr_idx, wr_off, 0, wr_idx0 );  // 找到 offset=0 对应的索引
mux_wrdata( permute_i, wr_off, 0, wr_data0 );  // 找到 offset=0 对应的数据

// 写入 4 个副本
WRITE : for (int ss=0; ss < 4; ss++) {
  buff[ping][0][ss][wr_idx0] = wr_data0;
  buff[ping][1][ss][wr_idx1] = wr_data1;
  ...
}

为什么需要 mux_index/mux_wrdata？

想象你有 4 个邮箱（polyphase），每个来信人（输入样本）有自己的偏好的投递口（offset）。但 buffer 是按索引组织的，你需要：

  1. 根据 offset 找到这封信应该存到哪个索引位置
  2. 确保同一周期的 4 封信不会冲突

这就像在一个有多个入口的停车场，需要根据车辆类型动态分配停车位。

阶段 C：乒乓读取与输出组装
// 从 pong 侧读取（与写入侧相反）
rd_data0[0] = buff[!ping][0][0][rd_idx[0]];
rd_data0[1] = buff[!ping][0][1][rd_idx[1]];
...

// 根据 LUT 给出的偏移选择最终输出
MUX_ALL : for (int ss=0; ss < 4; ss++) {
  switch ( rd_off[ss] ) {
    case 0 : permute_o[ss] = rd_data0[ss]; break;
    case 1 : permute_o[ss] = rd_data1[ss]; break;
    case 2 : permute_o[ss] = rd_data2[ss]; break;
    default: permute_o[ss] = rd_data3[ss]; break;
  }
}

乒乓机制的关键：

  • 当 ping=0 时：向 buff[0] 写入，从 buff[1] 读取
  • 当 ping=1 时：向 buff[1] 写入，从 buff[0] 读取
  • 切换发生在写完一整个 1008 点块之后
阶段 D：嵌套循环状态更新
// 三层嵌套计数器模拟 DFT-16/9/7 的遍历
if ( wr_cnt16 == 12 ) {      // DFT-16 内循环完成 (16/4-1=3? 实际是 12=3*4)
  if ( wr_cnt9 == 8 ) {      // DFT-9 中循环完成
    if ( wr_cnt7 == 6 ) {    // DFT-7 外循环完成 → 块结束
      ping = !ping;          // 切换乒乓
      wr_addr = 0;
      wr_cnt7 = wr_cnt9 = wr_cnt16 = 0;
    }
    else { /* 外层递增 */ }
  }
  else { /* 中层递增，addr = 7*wr_cnt9 + wr_cnt7 */ }
}
else { /* 内层递增，addr += 4*63 */ }

地址计算公式的数学含义：

  • wr_addr = 7*wr_cnt9 + wr_cnt7：在 DFT-9 维度上步进，每次跨越 7 个样本（DFT-7 大小）
  • wr_addr += 4*63：在 DFT-16 维度上步进，每次跨越 63 个样本（1008/16）

这正是 PFA 算法的核心索引映射：n = n₁·N₂ + n₂，其中 N₂=63。

3. pfa1008_write_streams —— 流式输出

void pfa1008_write_streams( TT_DATA (&permute_o)[4], TT_STREAM& sig_o )
{
  static bool running = 0;
  static ap_uint<10> startup = 0;
  
  TT_AXI4 ss0_data = ( permute_o[3], permute_o[2], permute_o[1], permute_o[0] );
  
  if ( running == 1 ) {
    sig_o.write( ss0_data );
  }
  if ( startup == NFFT/4-1 ) {
    running = 1;  // 启动延迟结束后开始输出
  }
}
}

启动延迟的处理：

  • 第一个块的数据需要先填满 buffer 才能开始有意义地读取
  • startup 计数器等待 NFFT/4 = 252 个周期
  • 这与 ping-pong 机制配合，确保输出有效数据

顶层封装：pfa1008_permute_o_wrapper

void pfa1008_permute_o_wrapper( TT_STREAM& sig_i, TT_STREAM& sig_o )
{
#pragma HLS interface mode=ap_ctrl_none port=return
#pragma HLS pipeline II=1

  static TT_DATA permute_i[4], permute_o[4];
#pragma HLS array_partition variable=permute_i dim=1
#pragma HLS array_partition variable=permute_o dim=1

  pfa1008_unpack( sig_i, permute_i );
  pfa1008_permute( permute_i, permute_o );
  pfa1008_write_streams( permute_o, sig_o );
}

HLS 编译指令解读：

指令 作用
ap_ctrl_none 无控制接口，内核自主运行（自由运行模式）
pipeline II=1 目标启动间隔为 1 时钟周期
array_partition dim=1 将数组 4 个元素完全展开，支持并行访问

依赖关系与系统上下文

上游调用者

该内核属于 prime_factor_fft_hls_kernels 模块，在完整系统中：

[AIE FFT Compute] → [Output Reordering Pipeline] → [DMA Sink]
                         ↑
                   [pfa1008_permute_o]

具体连接关系见 prime_factor_fft_system_integration 中的 output_side_reordering_pipeline。

下游消费者

输出直接连接到 DMA sink kernel (dma_sink_kernel)，将重排后的数据写回 DDR。

相关模块

模块 关系 说明
fft_input_permutation_kernel 对称模块 输入端的对应重排内核，结构类似但 LUT 不同
pfa1008_permute_i 参考实现 输入置换的简化版本，可作为对比学习

设计决策与权衡

决策一：四副本存储 vs. 单端口 RAM

选择：使用 buff[2][4][4][252]（4 个 polyphase 副本）

替代方案：使用单端口 RAM + 时分复用

  • ❌ 需要 4 倍时钟频率或 4 周期延迟
  • ❌ 无法满足 II=1 的吞吐要求

当前方案的代价：

  • BRAM 用量：2 × 4 × 4 × 252 × 32 bit ≈ 256 Kbit
  • 相当于约 16 个 18K BRAM（在 xcve2802 上可接受）

决策二：静态 LUT vs. 运行时计算

选择：预计算 PERM_O_ADDR 查找表

static TT_ADDR permute_lut[2][NFFT] = { PERM_O_ADDR, PERM_O_ADDR };

替代方案：运行时计算 Rader/Bluestein 索引映射

  • ❌ 需要模运算、乘法等复杂操作
  • ❌ 难以在 II=1 约束下完成

LUT 的生成：由 gen_permute_tables.m MATLAB 脚本离线计算，确保数学正确性。

决策三：True Dual-Port BRAM

#pragma HLS bind_storage variable=buff type=RAM_T2P impl=bram

T2P (True Two-Port) 允许同时读写不同地址，是实现 ping-pong 无缝切换的关键。

替代方案：TDP (Simple Dual-Port) 或单端口

  • ❌ 切换时需要停顿周期
  • ❌ 破坏 II=1 的连续性

决策四：Ping-Pong 粒度 = 整块 (1008 点)

选择：整块的乒乓切换

替代方案：行级或样本级乒乓

  • ❌ 控制逻辑复杂，容易产生边界条件错误
  • ❌ 对 PFA 的三维遍历模式不友好

当前方案的启动延迟为 NFFT/4 = 252 周期，在 312.5 MHz 下约为 0.8 μs，对大多数应用可接受。

性能特征

指标 数值 说明
目标时钟 312.5 MHz 来自 hls.cfg 的 3.2ns 约束
吞吐量 4 样本/周期 128-bit @ 312.5 MHz
等效采样率 1.25 GSamples/s 满足大多数宽带信号处理需求
启动延迟 252 周期 首次有效输出前的填充时间
II (启动间隔) 1 每周期可开始新事务

使用指南与扩展

基本使用流程

# 1. 进入内核目录
cd AI_Engine_Development/AIE-ML/Design_Tutorials/02-Prime-Factor-FFT/hls/pfa1008_permute_o

# 2. 运行 HLS 综合
make csynth

# 3. 运行 C 仿真验证
make csim

# 4. 导出 XO 文件供 Vitis 链接
make xo

修改 FFT 点数的注意事项

如需适配其他 PFA 分解（如 504=16×9×3.5 不适用，必须是整数分解）：

  1. 更新常量（pfa1008_permute_o.h）：

    static constexpr unsigned NFFT = 1008;  // 改为新点数

  2. 重新生成 LUT（gen_permute_tables.m）：

    N = 1008;  % 新点数
n1 = 16; n2 = 9; n3 = 7;  % 新的分解
% 重新计算 PERM_O_ADDR

  3. 调整地址位宽（如果需要）：

    typedef ap_uint<10> TT_ADDR;   // ceil(log2(NFFT))
typedef ap_uint<8>  TT_INDEX;  // ceil(log2(NFFT/4))

  4. 更新状态机计数器上限：

    • wr_cnt16 上限取决于 DFT-16 的遍历方式
    • wr_cnt9 上限 = 9-1 = 8
    • wr_cnt7 上限 = 7-1 = 6

常见陷阱

陷阱 1：LUT 索引越界

TT_ADDR rd_addr_use = permute_lut[ss>>1][rd_addr+ss];
// 如果 rd_addr+ss >= NFFT，行为未定义！

防护：确保 rd_addr 更新逻辑在 NFFT-4 处正确回绕：

if ( rd_addr == TT_ADDR(NFFT-4) ) {
  rd_addr = 0;
}

陷阱 2：乒乓同步丢失

如果读写速率不匹配（例如下游背压），可能导致 ping-pong 状态错乱。

检测：监控 sig_o 的 valid 信号和 running 标志的一致性。

陷阱 3：HLS 综合失败（II 不满足）

常见原因：

  • Buffer 端口不足 → 检查 ARRAY_PARTITION 是否生效
  • LUT 读取延迟过高 → 确保 bind_storage 设置为 BRAM
  • 数据依赖未标注 → 确认 dependence type=intra false 存在

测试与验证

测试平台结构（tb_wrapper.cpp）

// 1. 从文件加载测试向量
for (int xx=0; xx < NTRANSFORM*NFFT/4; xx++) {
  sig_i.write( read_from_files( ss0_i ) );
}

// 2. 添加零填充以覆盖启动延迟
for (int xx=0; xx < LATENCY; xx++) {
  sig_i.write( TT_AXI4(0) );
}

// 3. 运行 DUT
for (int ss=0; ss < NTRANSFORM*NFFT/4+LATENCY; ss++) {
  pfa1008_permute_o_wrapper( sig_i, sig_o );
}

// 4. 与黄金参考比较
for (int xx=0; xx < NTRANSFORM*NFFT/4; xx++) {
  TT_AXI4 gld0_o = read_from_files( ss0_o );
  TT_AXI4 act0_o = sig_o.read();
  flag |= ( act0_o != gld0_o );
}

测试数据生成

gen_vectors.m 和 gen_permute_tables.m 提供了完整的参考模型：

  • 输入数据：随机生成的复数序列
  • 预期输出：经过 MATLAB 参考 PFA FFT 和输出置换后的结果

总结

fft_output_permutation_kernel 是一个精心设计的硬件加速器内核，它解决了 Prime-Factor FFT 算法中固有的数据重排难题。其核心设计亮点包括：

  1. 乒乓双缓冲：实现无停顿流水线处理
  2. 四副本存储架构：支持任意偏移的并行读取
  3. 预计算 LUT：将复杂索引映射转化为 O(1) 查表
  4. 严格的 II=1 设计：每周期处理 4 个样本，匹配 AIE 吞吐量

对于新加入团队的开发者，理解这个模块的关键在于把握 "空间换时间" 的设计哲学：通过增加存储副本（4×）和预计算资源（LUT），换取了确定的低延迟和高吞吐。这种模式在 FPGA 信号处理中非常典型，值得在其他项目中借鉴。

On this page