fft_input_permutation_kernel 技术深度解析

概述：这个模块是做什么的？

想象你有一个巨大的图书馆，书籍按照特定的数学规律排列——不是简单的从左到右、从上到下，而是遵循一种复杂的"质因数分解"索引方式。现在你需要把这些书重新排列，让阅读者能够按顺序高效地取阅。fft_input_permutation_kernel 就是这个"图书管理员"，它负责在 Prime Factor FFT（质因数快速傅里叶变换）流水线中，将输入数据从线性存储顺序重新排列为符合 \(7 \times 9 \times 16 = 1008\) 点 FFT 计算所需的特定访问模式。

具体来说，这是一个用 Vitis HLS 实现的硬件加速核，运行在 PL（Programmable Logic）端，工作频率 312.5 MHz。它接收来自 DMA 的 128-bit AXI4-Stream 数据流（每周期包含 4 个 32-bit 复数样本），通过双缓冲（ping-pong buffer）机制和查找表（LUT）驱动的地址生成，输出重排后的数据流，供下游的 AIE（AI Engine）进行 DFT-7 运算。

核心问题：为什么需要这个模块？

Prime Factor FFT 的数据访问困境

Prime Factor Algorithm (PFA) FFT 是一种将大点数 FFT 分解为互质小点数 FFT 的算法。对于 \(N = N_1 \times N_2 \times N_3 = 7 \times 9 \times 16 = 1008\) 的情况：

1. 三维数据立方体：1008 个样本被组织成一个 \(7 \times 9 \times 16\) 的三维数组
2. 非线性访问模式：每个计算阶段需要沿不同维度读取数据（先沿维度 1，再沿维度 2，最后沿维度 3）
3. 并行度要求：为了匹配 AIE 的计算吞吐，每周期需要同时提供 4 个样本

如果没有这个重排模块，AIE 将不得不以极不规则的模式访问内存，导致严重的 bank conflict 和性能瓶颈。就像让一个人同时从图书馆的不同楼层、不同书架取书——效率极低。

设计洞察：用空间换时间

解决方案的核心洞察是：在 PL 端预先完成所有重排，让 AIE 看到连续、规则的访问模式。这通过在 PL 中实现一个专用的"数据路由器"来完成——这就是 pfa1008_permute_i 的使命。

心智模型：理解这个模块的四个关键抽象

1. 双缓冲乒乓机制（Ping-Pong Buffer）

想象两个工作台：

• Ping 缓冲区：正在写入新的输入数据块
• Pong 缓冲区：正在被读取、输出重排后的上一块数据

当一块数据处理完成后，两个工作台的角色互换。这种机制保证数据流的连续性——写操作永远不会阻塞读操作，反之亦然。

static TT_DATA buff[2][4][4][NFFT/4];  // [ping/pong][polyphase][copy][sample]

2. 多副本存储（Data Replication）

这是最关键的设计决策之一。注意到缓冲区声明中的 [4][4] 维度：

• 第一个 [4] 代表 4 个"多相分支"（polyphase），对应每周期输出的 4 个样本
• 第二个 [4] 代表 4 份数据副本

为什么要存 4 份相同的数据？

因为输出重排可能需要从任意位置读取 4 个样本，而 BRAM 每个周期只能从一个地址读取。通过将同一份数据复制到 4 个独立的 BRAM bank，我们可以实现单周期并行读取 4 个任意位置的数据。

这就像把同一本书复印 4 份放在不同的书架上，这样 4 个人可以同时取阅同一本书的不同章节。

3. LUT 驱动的地址生成

重排模式完全由预计算的查找表决定：

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

PERM_I_ADDR 是一个包含 1008 个条目的常量数组，定义了输出序列中每个位置应该取自输入序列的哪个地址。这种硬编码 LUT 的方式相比实时计算地址：

• 优势：零计算延迟，确定性时序，II=1 可实现
• 代价：消耗 BRAM 存储 LUT（约 2KB）

4. 多路选择器网络（Polyphase Mux）

读取阶段，从 4 个 BRAM bank 各读出 4 个候选值，然后通过一个 4-to-1 的多路选择器网络，根据 LUT 提供的偏移量选择最终输出的 4 个样本：

switch ( offset[ss] ) {
  case 0 : permute_o[ss] = data0[ss]; break;
  case 1 : permute_o[ss] = data1[ss]; break;
  case 2 : permute_o[ss] = data2[ss]; break;
  default: permute_o[ss] = data3[ss]; break;
}

架构与数据流

详细数据流分析

阶段 1：解包（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();
}

• 输入：hls::stream<ap_uint<128>>，AXI4-Stream 接口
• 输出：ap_uint<32>[4]，4 个独立的 32-bit 样本
• 操作：将 128-bit 总线拆分为 4 个 32-bit 样本，使用 HLS 的元组解包语法

阶段 2：核心重排（Permute）

这是最复杂的阶段，每周期执行以下原子操作：

2a. 地址生成

// 从 LUT 读取 4 个输出位置的源地址
for (int ss=0; ss < 4; ss++) {
  TT_ADDR rd_addr_use = permute_lut[ss>>1][rd_addr+ss];
  addr[ss].range(7,0)   = rd_addr_use.range(9,2);    // 高 8 bit: 行地址
  offset[ss].range(1,0) = rd_addr_use.range(1,0);    // 低 2 bit: 列偏移
}

2b. 写入 Ping 缓冲区

// 将输入的 4 个样本分别写入 4 个 polyphase 的所有 4 个副本
buff[ping][0][0..3][wr_addrA] = permute_i[0];  // 样本 0 写入 bank 0 的所有副本
buff[ping][1][0..3][wr_addrA] = permute_i[1];  // 样本 1 写入 bank 1 的所有副本
// ... 以此类推

注意这里的数据广播模式：每个输入样本被同时写入同一 polyphase 的 4 个副本位置。这是为了实现后续的单周期任意读取。

2c. 从 Pong 缓冲区读取

// 从 4 个 polyphase 的 4 个副本中并行读取
data0[0..3] = buff[!ping][0][0..3][addr[0..3]];  // 副本 0
data1[0..3] = buff[!ping][1][0..3][addr[0..3]];  // 副本 1
// ... 以此类推

2d. 多路选择

// 根据 LUT 提供的偏移量，从 4 个副本中选择正确的值
for (int ss=0; ss < 4; ss++) {
  switch ( offset[ss] ) {
    case 0 : permute_o[ss] = data0[ss]; break;
    // ...
  }
}

2e. 状态更新

// 检测块边界，切换 ping/pong
bool last_wr = ( wr_addr == TT_ADDR(NFFT-4) );
bool last_rd = ( rd_addr == TT_ADDR(NFFT-4) );
ping    = ( last_wr == 1 ) ? !ping      : ping;
wr_addr = ( last_wr == 1 ) ? TT_ADDR(0) : TT_ADDR(wr_addr+4);
rd_addr = ( last_rd == 1 ) ? TT_ADDR(0) : TT_ADDR(rd_addr+4);

阶段 3：输出格式化（Write Streams）

void pfa1008_write_streams( TT_DATA (&permI)[4], TT_STREAM& sig_o )
{
  // 启动延迟处理：前 NFFT/4 个周期不输出（缓冲区填充期）
  if ( running == 1 ) {
    sig_o.write( ss0_data );
  }
  // 启动计数器管理
}

• 启动延迟（Startup Latency）：模块需要 NFFT/4 = 252 个周期来填充第一个 ping 缓冲区，在此期间不产生有效输出
• 这与 dma_source_kernel 的设计相呼应——DMA source 会在数据流末尾额外发送 NFFT/2 个零值来覆盖整个流水线的延迟

组件深度剖析

pfa1008_permute_i_wrapper —— 顶层封装

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

为什么选择 ap_ctrl_none？

这个模块被设计为始终运行的数据流处理单元，不需要 start/stop 控制信号。它的启动和停止由上游 DMA 的数据流控制（TLAST 信号）。这简化了系统集成，使得多个此类模块可以级联形成深层流水线。

pfa1008_permute —— 核心状态机

这是模块的心脏，包含：

• 静态状态变量：ping, wr_addr, rd_addr
• 双缓冲存储：buff[2][4][4][252]
• 查找表：permute_lut[2][1008]

HLS 优化指令解析

#pragma HLS array_partition variable=buff dim=1
#pragma HLS bind_storage variable=buff type=RAM_T2P impl=bram
#pragma HLS dependence variable=buff type=intra false

pfa1008_permute_i_luts.h —— 预计算查找表

#define PERM_I_ADDR { 0, 144, 288, 432, 576, 720, 864, 112, ... }

这个 1008 元素的数组定义了输入重排映射。第 \(i\) 个输出样本应该取自输入缓冲区的 PERM_I_ADDR[i] 位置。

这些数字从何而来？

查看 gen_permute_tables.m：

N1 = 7; N2 = 9; N3 = 16;
[P_i,P_o,N] = compute_perm_3d(N1,N2,N3);

这些地址是通过数学算法生成的，实现了 Good-Thomas 素因子 FFT 所需的中国剩余定理（CRT）重排。具体算法实现在 ../../matlab/compute_perm_3d.m 中（未在本次分析范围内）。

依赖关系与系统上下文

上游依赖：谁调用这个模块？

pfa1008_dma_src (DMA Source Kernel)
    ↓ AXI4-Stream (128-bit)
pfa1008_permute_i (本模块 - 输入重排)
    ↓ AXI4-Stream (128-bit)
[AIE Graph: DFT-7 Stages]

根据模块树，fft_input_permutation_kernel 属于 prime_factor_fft_hls_kernels 子系统，与 dma_source_kernel 和 fft_output_permutation_kernel 并列。

下游消费：数据流向何处？

重排后的数据流通过 AXI4-Stream 接口输出，连接到 AIE 图的输入端口。根据模块树中的 prime_factor_fft_pipeline_graphs，下游应该是：

• co_prime_small_dft_stages/dft7 —— 执行 7 点 DFT 的 AIE 核

与输出重排模块的关系

fft_output_permutation_kernel (pfa1008_permute_o) 是本模块的"镜像"：

• 本模块：线性输入 → 重排输出（用于 DFT-7 输入）
• 输出模块：重排输入 → 线性输出（用于 DFT-16 输出后重组）

两者共享相同的双缓冲 + LUT 架构，但重排模式不同（PERM_I_ADDR vs PERM_O_ADDR）。

设计权衡与决策分析

权衡 1：LUT vs 实时计算

决策理由：

• 1008 点 FFT 的尺寸是固定的（\(7 \times 9 \times 16\)），不需要运行时配置
• II=1 的要求排除了多周期计算方案
• 2KB BRAM 在 Versal 器件上成本极低

权衡 2：4x 数据复制 vs 多周期读取

决策理由：

• 需要维持 4 samples/cycle 的吞吐以匹配 AIE
• Versal 的 BRAM 资源丰富，4× 复制是可接受的
• 多周期读取会导致复杂的流水线气泡管理

权衡 3：ap_ctrl_none vs 显式控制

决策理由：

• 作为流水线中间节点，不需要频繁启停
• 简化了与 DMA 和 AIE 的集成
• 调试可通过 testbench 中的 cycle-accurate 仿真完成

新贡献者注意事项

关键不变量（Invariants）

修改代码前，确保以下不变量不被破坏：

1. II=1 约束：pfa1008_permute_i_wrapper 必须保持 pipeline II=1，任何增加逻辑深度的修改都可能导致时序失败
2. 双缓冲同步：ping 标志的切换必须与 wr_addr 和 rd_addr 的复位严格同步，否则会发生数据竞争
3. LUT 尺寸：PERM_I_ADDR 必须恰好包含 NFFT = 1008 个元素

常见陷阱

陷阱 1：BRAM 端口冲突

// 危险：以下代码可能导致端口冲突
buff[ping][0][0][addr1] = data1;  // 写端口 0
buff[ping][0][1][addr2] = data2;  // 写端口 0（冲突！）

当前实现通过 array_partition dim=2（将 4 个 polyphase 展开到不同 BRAM）避免此问题。如果添加更多 polyphase，需要相应调整 partition 策略。

陷阱 2：启动延迟不匹配

Testbench 中的启动延迟必须与 RTL 实现严格一致：

// tb_wrapper.cpp
static constexpr int LATENCY = NFFT/4;  // 252 cycles

如果修改了缓冲策略（如增加流水线级数），必须同步更新 testbench 的延迟注入。

陷阱 3：LUT 生成脚本依赖

pfa1008_permute_i_luts.h 是由 MATLAB 脚本 gen_permute_tables.m 生成的。手动编辑头文件会被下次脚本运行覆盖。如果需要修改重排模式：

1. 修改 gen_permute_tables.m 或底层的 compute_perm_3d.m
2. 重新运行 MATLAB 脚本
3. 验证生成的 LUT 与硬件实现兼容

扩展指南

场景：支持不同的 FFT 尺寸

假设需要支持 \(N = 5 \times 7 \times 16 = 560\) 点 FFT：

1. 修改参数：

   static constexpr unsigned NFFT = 560;  // 原为 1008
   

2. 重新生成 LUT：

   N1 = 5; N2 = 7; N3 = 16;
   [P_i,P_o,N] = compute_perm_3d(N1,N2,N3);
   

3. 调整缓冲区深度：

   static TT_DATA buff[2][4][4][NFFT/4];  // 现为 [2][4][4][140]
   

4. 验证地址位宽：

   typedef ap_uint<10> TT_ADDR;  // ceil(log2(560)) = 10，仍适用
   typedef ap_uint<8>  TT_INDEX; // ceil(log2(140)) = 8，仍适用
   

场景：增加并行度到 8 samples/cycle

这需要更激进的架构改动：

1. 将 permute_i[4] 改为 permute_i[8]
2. 缓冲区扩展到 [2][8][8][NFFT/8]（8 个 polyphase，8 个副本）
3. 修改 AXI4-Stream 宽度到 256-bit（8×32）
4. 重新评估 BRAM 用量和 II 可行性

性能特征

参考链接

• 上游模块：dma_source_kernel —— DMA 数据源
• 下游模块：co_prime_small_dft_stages/dft7 —— 7 点 DFT AIE 核
• 姊妹模块：fft_output_permutation_kernel —— 输出侧重排
• 系统集成：prime_factor_fft_system_integration/input_side_reordering_pipeline