数据重排与转置阶段 (Data Reordering and Transpose Stages)

一句话概括

这个模块是素因子FFT-1008算法的数据交通指挥中心——它负责在三个DFT计算阶段之间重新组织数据的"行驶路线"，使得原本需要复杂硬件电路实现的矩阵转置操作，能够通过AIE-ML Memory Tile的智能缓冲描述符（Buffer Descriptor）来高效完成。想象它是一个三维数据魔方的旋转器：输入数据按照一个维度排列，输出时却按照另一个维度读取，而这一切都在Memory Tile的硬件支持下零开销完成。

问题空间与设计动机

素因子FFT的核心挑战

素因子算法（Prime Factor Algorithm, PFA）是一种将大点数的DFT分解为互素小点数DFT乘积的FFT技术。对于 N = 1008 = 7 × 9 × 16 的变换，PFA将其视为一个三维DFT计算：

这种分解的优势在于无需蝶形运算中的旋转因子（twiddle factors）乘法，但代价是需要在每一维DFT之间进行复杂的**数据重索引（re-indexing）**操作。

为什么需要这个模块？

在传统的Cooley-Tukey FFT中，数据流动相对规则；但在PFA中，每一维DFT完成后，数据必须按照特定的数学映射关系重新排列，才能进入下一维的计算。具体来说：

1. DFT-7阶段：输入数据按照 (n₁, n₂, n₃) 的自然顺序处理
2. 转置0阶段：需要将数据从 (7, 9, 16) 维度映射到 (9, 16, 7) 维度，以便DFT-9能够连续访问第二维的数据
3. 转置1阶段：进一步将数据从 (9, 16, 7) 映射到 (16, 9, 7) 维度，为DFT-16做准备

如果没有专门的转置机制，这种多维度的数据重排将成为整个流水线的瓶颈。

AIE-ML架构带来的机遇

早期的AIE架构（如VC1902）将这些转置操作实现在可编程逻辑（PL）中，需要额外的DMA和缓冲区资源。而AIE-ML架构引入了Memory Tile——一种位于AI Engine阵列内部的共享存储单元，支持通过**缓冲描述符（Buffer Descriptor, BD）**配置复杂的地址生成模式。

这一特性使得矩阵转置可以完全在AIE阵列内部完成，无需退出到PL，从而：

• 减少数据搬移延迟
• 降低PL资源消耗
• 简化整体数据流设计

核心抽象与心智模型

三维数据立方体

理解这个模块的最佳方式是想象一个三维数据魔方：

       D=16 (深度/Tile)
         │
         ▼
    ┌─────────┐
   ╱│        ╱│
  ╱ │       ╱ │  C=9 (列)
 ┌──┼──────┐  │  ↑
 │  └──────┼──┘  │
 │ ╱       │ ╱   │
 └─────────┘     └──→ R=7 (行)

• 维度0（R）：对应DFT-7的点数，大小为7
• 维度1（C）：对应DFT-9的点数，大小为9
• 维度2（D）：对应DFT-16的点数，大小为16

每个"小方块"包含8个复数样本（cint16类型），这是AIE-ML向量运算的基本粒度。

Buffer Descriptor作为"数据路由器"

Memory Tile的Buffer Descriptor（BD）可以被理解为一个智能数据路由器，它决定了：

1. 写入时（Write BD）：数据如何被"打包"进Memory Tile的缓冲区
2. 读出时（Read BD）：数据以何种"视角"被提取出来

关键在于：写和读的遍历顺序可以完全不同。这正是实现零开销转置的秘诀——数据在物理上保持不动，但通过改变读取时的地址生成顺序，实现了逻辑上的维度交换。

乒乓缓冲（Ping-Pong Buffering）

为了实现全流水线操作，每个Memory Tile配置了两组缓冲区（num_buffers = 2）：

• 当一组正在被写入上一阶段的输出时
• 另一组正在被读出供下一阶段使用

这种经典的双缓冲技术确保了数据流的连续性，避免了流水线气泡。

架构设计与数据流

模块组成

本模块包含三个独立的子模块，分别负责不同阶段的数据重排：

注意：图示展示了数据重排模块在整个PFA流水线中的位置。实际上，permute_i位于DFT-7之前（处理输入数据），transpose0位于DFT-7和DFT-9之间，transpose1位于DFT-9和DFT-16之间。

详细数据流

permute_i：输入端的特殊处理

permute_i是一个特殊的子模块，它处理的是输入置换而非简单的维度转置。根据README的描述，输入置换涉及模1008运算：

P = mod(C × D × R + R × D × C + R × C × D, 1008)

这种复杂的索引模式无法通过Memory Tile的标准BD直接生成（因为不支持模运算），因此早期设计中需要在PL中实现。但在本模块中，permute_i展示了一种简化的输入数据组织方式，为后续的纯Memory Tile转置做准备。

其核心代码如下：

// permute_i_graph.h
shared_buffer<TT_DATA> MT_buff;
MT_buff = shared_buffer<TT_DATA>::create({8,16,16},1,1);
write_access(MT_buff.in[0]) = tiling(write_bd);  // 线性写入
read_access(MT_buff.out[0]) = tiling(read_bd);   // 按特定模式读出

transpose0：第一维到第二维的桥梁

transpose0是第一个真正的维度转置，它将DFT-7的输出（按维度0组织）转换为DFT-9所需的输入（按维度1组织）。

写入模式（来自DFT-7的输出）：

tiling_parameters write_bd = {
  .buffer_dimension = {8,16,16},
  .tiling_dimension = {1,1,1},
  .offset = {0,0,0},
  .tile_traversal = {{.dimension=0, .stride=1, .wrap=7},  // 先遍历维度0
                     {.dimension=1, .stride=1, .wrap=9},  // 再维度1
                     {.dimension=2, .stride=1, .wrap=16}} // 最后维度2
};

读出模式（供给DFT-9的输入）：

tiling_parameters read_bd = {
  .buffer_dimension = {8,16,16},
  .tiling_dimension = {1,1,1},
  .offset = {0,0,0},
  .tile_traversal = {{.dimension=1, .stride=1, .wrap=9},  // 先遍历维度1
                     {.dimension=2, .stride=1, .wrap=16}, // 再维度2
                     {.dimension=0, .stride=1, .wrap=7}}  // 最后维度0
};

注意tile_traversal中维度的顺序变化——这就是转置的本质。

transpose1：第二维到第三维的过渡

transpose1执行类似的转置操作，将数据从(9, 16, 7)映射到(16, 9, 7)：

写入模式（匹配transpose0的读出）：

.tile_traversal = {{.dimension=1, .stride=1, .wrap=9},
                   {.dimension=2, .stride=1, .wrap=16},
                   {.dimension=0, .stride=1, .wrap=7}}

读出模式（供给DFT-16）：

.tile_traversal = {{.dimension=2, .stride=1, .wrap=16}, // 先遍历维度2
                   {.dimension=1, .stride=1, .wrap=9},  // 再维度1
                   {.dimension=0, .stride=1, .wrap=7}}  // 最后维度0

关键设计决策与权衡

1. Memory Tile vs PL实现的抉择

选择的方案：尽可能使用Memory Tile实现转置，仅在输入/输出端使用PL。

权衡分析：

决策理由：

• 中间阶段的转置是纯维度的循环置换，完全在Memory Tile能力范围内
• 输入/输出的复杂置换涉及模运算，必须由PL处理
• AIE-ML的Memory Tile提供了足够的缓冲容量（{8,16,16}配置）

2. 缓冲区维度选择：为什么是{8,16,16}？

实际的三维数据尺寸是 {7, 9, 16}，但代码中使用的是 {8, 16, 16}。

原因：Memory Tile要求缓冲区对齐到32位边界。将7扩展到8、9扩展到16，既满足了对齐要求，又利用了AIE-ML的向量处理能力（每次处理8个样本）。

代价：略微浪费了存储空间（约12.5%），但换取了硬件兼容性和处理效率。

3. Repetition Count = 8 的设计

repetition_count(MT_buff) = 8;

这个参数表示每个BD需要重复执行8次。这与DFT内核的设计密切相关——每个DFT内核在一次调用中处理8个连续的变换。因此，Memory Tile的BD也必须相应地重复8次，以保持数据流的同步。

4. 双缓冲（num_buffers = 2）的必要性

num_buffers(MT_buff) = 2;

单缓冲方案在写入和读取之间会产生冲突。双缓冲确保：

• 写入操作永远不会覆盖正在读取的数据
• 读取操作永远不会访问未准备好的数据
• 流水线可以全速运行，无停顿

新贡献者注意事项

隐式契约与约束

1. 数据类型一致性

   • 所有组件使用 cint16（16位复数）作为数据类型
   • 修改此类型会波及整个PFA流水线，需谨慎

2. 维度顺序的严格约定

   • 代码中硬编码了维度编号：0=7点，1=9点，2=16点
   • 更改这些编号会导致错误的地址生成

3. Buffer Descriptor的生命周期

   • BD在图构造时配置，运行时不可修改
   • 任何BD参数的变更都需要重新编译整个设计

常见陷阱

1. 忽略对齐要求

   // 错误：直接使用 {7,9,16}
   MT_buff = shared_buffer<TT_DATA>::create({7,9,16},1,1); // 可能导致运行时错误
   
   // 正确：使用对齐后的尺寸
   MT_buff = shared_buffer<TT_DATA>::create({8,16,16},1,1);
   

2. tile_traversal维度混淆

   • .dimension字段指的是buffer_dimension中的索引，不是逻辑维度
   • 例如，逻辑维度"9"在buffer_dimension中可能是索引1（因为前面有填充）

3. Repetition Count不匹配

   • 如果DFT内核改为处理16个变换，但Memory Tile仍配置为8，会导致数据失步

调试建议

1. 使用AIE仿真验证数据流

   • 每个子模块都有独立的测试应用（*_app.cpp）
   • 可以在隔离环境中验证单个转置阶段的正确性

2. 检查Matlab参考模型

   • matlab/目录包含地址计算和置换算法的参考实现
   • 当怀疑BD配置有误时，可与Matlab结果对比

3. 观察波形中的握手信号

   • Memory Tile的读写端口有就绪/有效握手信号
   • 死锁通常表现为某个端口持续等待

扩展指南

如需添加新的转置阶段：

1. 复制transpose0或transpose1目录结构
2. 修改tile_traversal中的维度顺序
3. 更新pfa1008_graph.h中的连接关系
4. 在Matlab中验证新的索引映射公式
5. 运行独立测试验证后再集成到完整流水线

与其他模块的关系

上游依赖

• co_prime_small_dft_stages：提供DFT-7、DFT-9、DFT-16的计算内核
  • transpose0接收来自DFT-7的输出
  • transpose1接收来自DFT-9的输出

下游消费

• 完整的PFA-1008图（pfa1008_graph.h）：将本模块的子图组合成完整流水线

相关文档

• radix16_dft_stage：与本模块同属prime_factor_fft_pipeline_graphs，处理Radix-16 DFT的特殊情况
• prime_factor_fft_hls_kernels：PL端的输入/输出置换内核，与本模块形成互补

总结

data_reordering_and_transpose_stages模块是AIE-ML架构下PFA-1008设计的核心创新之一。它充分利用了Memory Tile的Buffer Descriptor功能，将原本需要复杂硬件支持的矩阵转置操作转化为简单的配置参数调整。这种设计不仅提高了性能，还大幅简化了系统架构——数据无需离开AIE阵列即可完成重排，体现了软硬件协同设计的精髓。

对于新加入团队的工程师，理解本模块的关键在于把握三维数据立方体的心智模型和Buffer Descriptor作为数据路由器的抽象。一旦掌握了这些概念，阅读和维护代码将变得直观明了。