《IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems》：ESFA: An Efficient Scalable FFT Design Framework on Versal AI Engine
编辑推荐：
为解决在Versal自适应计算加速平台（ACAP）上实现高效、可扩展的快速傅里叶变换（FFT）的挑战，研究人员提出了ESFA框架。该框架通过多级分区算法、布局优化模型和自动代码生成器，在多个AI Engine上实现了FFT的并行加速。实验表明，该框架在1K点FFT上实现了9226/2059 MS/s的仿真/系统吞吐量，较现有方案最高提升23.2倍，显著提升了计算效率和可扩展性。
在数字信号处理（DSP）、通信、图像处理等诸多领域，快速傅里叶变换（FFT）扮演着将时域信号转换为频域表示的关键角色。尽管其计算复杂度已通过Cooley-Tukey等算法从O(N2)降低至O(N log N)，但随着数据规模和实时性要求的不断提升，如何进一步加速FFT运算始终是业界关注的核心问题。传统的加速方案曾在中央处理器（CPU）、图形处理器（GPU）、现场可编程门阵列（FPGA）、专用集成电路（ASIC）等多种硬件平台上进行探索，但它们往往在性能、灵活性、能效或成本方面存在局限。
近年来，AMD（原赛灵思）推出的Versal自适应计算加速平台（ACAP）为高性能计算带来了新的可能性。该平台集成了可编程逻辑（PL）、标量处理器、智能引擎以及一个关键组件——人工智能引擎（AIE）阵列。AIE是一种由数百个7路超长指令字（VLIW）处理器组成的二维阵列，运行频率高达1 GHz，能够提供巨大的并行计算能力。这似乎为FFT等计算密集型任务提供了理想的温床。然而，现实却充满挑战。此前的研究和商业IP（如AMD/Xilinx的DSP库）大多局限于单AIE的实现方式，这不仅限制了可处理的FFT规模（例如最大仅支持2K点），更忽视了利用多个AIE协同工作以进一步提升性能的巨大潜力。将FFT高效、自动地映射到由多个AIE构成的复杂异构系统上，面临着内核向量化、工作负载分区、数据流协同优化、布局规划、自动化代码生成等一系列难题。
为了解决上述挑战，一项名为“ESFA: An Efficient Scalable FFT Design Framework on Versal AI Engine”的研究在《IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems》期刊上发表。该研究提出了一个端到端的ESFA框架，旨在自动化地实现Versal ACAP平台上高效、可扩展的FFT设计。该研究的核心目标是打破单AIE的性能瓶颈，通过系统性的方法挖掘多AIE并行计算的潜力，从而显著提升FFT的计算吞吐量和资源效率，并支持更大规模的FFT运算。
为了达成这一目标，研究人员主要运用了四项关键技术。首先，算法分析与多级分区：研究基于Cooley-Tukey算法，提出并扩展了单级分区算法，进而发展出多级分区算法，将大规模的N点FFT分解为多个小规模的基FFT（如64、128、256、512、1024点）和中间级FFT的组合，从而将计算任务分配到多个AIE上形成流水线。其次，内核优化与向量化编码：针对单个AIE，研究设计了手工向量化的基FFT内核代码，充分利用AIE的7路VLIW架构，通过乒乓缓冲和数据重排消除依赖，实现了接近理论极限的单核计算效率。第三，基于整数线性规划（ILP）的布局方案：针对内存受限的FFT任务，研究将AIE和数据在二维阵列上的布局问题建模为一个ILP问题，以最小化资源占用量为目标，在满足数据局部性和访问延迟约束的前提下，自动生成面积利用率高、形状规则的优化布局，显著提升了布局成功率和系统集成便利性。第四，吞吐量-资源权衡分析模型与自动代码生成器：研究建立了一个分析模型，能够快速评估不同分区模式（分区级数L、各级分区因子Fi、基大小B）下的预期质量结果（QoR），包括所需AIE数量M和系统吞吐量P，从而在广阔的设计空间中为用户描绘出最优的吞吐量-资源权衡前沿。基于用户选定的配置，框架的自动代码生成器能够产生面向AIE、PL和主机CPU的完整源代码，实现敏捷的端到端系统部署。
研究结果
- •
单内核效率：研究首先评估了单AIE上不同基尺寸FFT的性能。结果显示，64点FFT由于计算负载低，获得了最高的单核吞吐量。随着FFT尺寸增大，吞吐量逐渐下降，表明在单个AIE上扩大FFT规模会降低计算效率。这凸显了将大尺寸FFT分解到多个AIE的必要性。
- •
单级分区性能：以1K点FFT为例，研究比较了分区因子为2、4、8的单级分区设计（即1K = 2×512, 4×256, 8×128）。实验发现，随着分区因子增大，系统吞吐量显著提升，最高达到4241.92 MS/s，相比单内核设计实现了4.9倍的加速。然而，当分区因子为8时，第二级（最后一级）的计算时间远长于第一级，导致流水线不平衡。为此，研究引入了“层级分区因子”，将第二级的工作负载进一步分配到多个AIE（最高4个），成功消除了瓶颈，使8×128设计的性能提升了3.6倍，并提高了资源效率（吞吐量/核心）。
- •
多级分区性能与设计空间探索：ESFA框架能够自动探索并实施多级分区设计。研究展示了五种不同的分区模式，例如1K = 2×2×2×2×64（四级分区，基为64）。分析表明，在分区级数相同时，更大的分区因子通常能带来更高的系统吞吐量。同时，将较大的分区因子置于更靠近基FFT的级别，有助于均衡旋转因子的计算负载，缩短关键路径。更深的多级分区（使用更多AIE）能带来比单纯增大某一级分区因子更显著的性能提升。最终，在1K点FFT上，ESFA发现的最优分区模式实现了高达9226.04 MS/s的仿真吞吐量，相比单内核设计加速达10.7倍。框架还能报告每种模式所需的AIE资源，帮助用户进行权衡决策。
- •
与现有方案的对比：研究将ESFA生成的最佳设计（1K = 2×2×2×2×64）与基于FPGA、ASIC、CGRA以及AMD/Xilinx官方IP的先进方案进行了全面对比。在仿真中，该设计取得了9226.04 MS/s的吞吐量，相对于现有的FPGA方案实现了3.4倍至23.2倍的性能提升（考虑到本设计数据宽度为32位，是多数对比方案16位的两倍，归一化后的优势可能更大）。在VCK190开发板上的实际系统测试中，由于DDR-PL和PL-AIE之间的数据传输延迟，吞吐量降至2059.53 MS/s，但仍显著优于对比的FPGA方案，实现了2.2倍至5.2倍的加速，并且展现了优于CGRA和ASIC方案的灵活性与可扩展性，支持从64点到32K点的多种FFT规模。
- •
布局优化效果：研究对比了由AMD/Xilinx AIE编译器生成的默认布局与ESFA的ILP布局方案生成的优化布局。对于单级分区（1K = 4×256）和多级分区（1K = 2×2×2×128）案例，优化布局在满足所有内存约束的前提下，使用的AIE核心和存储体数量更少，布局形状更加紧凑、规则。这不仅提高了面积和能效，也使得生成的设计更容易被AIE编译器成功放置和路由，并为与其他模块集成或设计复制提供了便利。
研究结论与意义
本研究成功设计并实现了ESFA框架，系统性地解决了在Versal ACAP平台上高效、自动实施可扩展FFT所面临的一系列关键挑战。该框架的核心贡献在于：1）提出了多级FFT分区算法，能够灵活地将大规模FFT计算映射到多个AIE上，形成高效流水线；2）开发了基于ILP的布局优化模型，为内存受限任务快速生成高质量布局，提升了编译成功率和硬件利用率；3）构建了准确的分析模型，能够前瞻性地评估不同设计选择的性能-资源权衡，指导设计空间探索；4）实现了自动化代码生成，极大降低了在复杂异构平台上的编程门槛。
实验结果表明，ESFA框架能够充分发挥Versal ACAP中AIE阵列的巨大计算潜力。在1K点FFT上，所实现的设计在仿真和实际系统中均取得了超越现有方案的卓越性能，最高可达23.2倍的加速比。更重要的是，ESFA提供了一种系统化的设计方法论，其价值不仅限于FFT加速。该框架中解决的内核优化、任务分区、数据流安排、布局规划与自动化代码生成等通用性问题，对于将其他具有规则计算模式的数字信号处理（DSP）算法（如滤波器、卷积等）高效映射到Versal乃至类似的可编程异构计算平台，具有重要的借鉴意义和推广价值。它为实现高性能、高能效、高可编程性的下一代信号处理系统提供了强有力的工具支撑。
