前言傅里叶变换是信号处理和科学计算的基石——时域到频域的转换、卷积定理把卷积变成乘法、图像压缩里的频域编码这些操作背后都是FFT。在CPU上FFTW和numpy.fft已经做得很好了但一旦数据量大到需要NPU加速比如64通道2048点的雷达信号、4K图像的2D-FFT通用CPU方案就力不从心了。昇腾CANN生态里的ops-fft仓库提供了在昇腾NPU上执行FFT/FFT2/IFFT等频域变换算子的实现专门针对达芬奇架构的Vector计算单元做了优化。CANN社区在atomgit.com/cann上开源了这个仓库是昇腾NPU上频域计算的标准算子库。FFT的数学原理和计算复杂度FFT快速傅里叶变换不是一种新的变换而是DFT离散傅里叶变换的快速算法。DFT的定义是X[k] sum(x[n] * exp(-j2pikn/N)), n0…N-1直接计算DFT需要N2次复数乘法FFT利用exp函数的周期性和对称性把N2降到N*log2(N)。比如N2048时DFT需要4,194,304次复数乘法FFT只需要22,528次加速186倍。FFT的核心操作是蝶形运算Butterfly Operation。一个2点FFT就是一次蝶形运算X[0] x[0] W * x[1] X[1] x[0] - W * x[1]其中W是旋转因子Twiddle FactorW exp(-j2pi*k/N)。N点FFT可以分解成log2(N)级蝶形运算每级有N/2个蝶形运算。蝶形运算的特点是每个蝶形只依赖两个输入计算结果直接写入输出位置不需要额外的临时存储。这个特点对NPU加速非常友好——可以把蝶形运算映射到Vector单元的SIMD通道上并行执行。ops-fft在昇腾NPU上的实现原理ops-fft的实现分三个层次分解策略、数据排布、Vector单元映射。分解策略。ops-fft支持Radix-2和Radix-4两种分解。Radix-2把N点FFT分解成两个N/2点FFT每级做N/2个2点蝶形运算。Radix-4把N点FFT分解成四个N/4点FFT每级做N/4个4点蝶形运算。Radix-4的计算步骤更少log4(N)级 vs log2(N)级但每个蝶形运算更复杂4输入4输出 vs 2输入2输出。ops-fft的默认策略是混合基分解对于2的幂次大小的FFT优先使用Radix-4分解剩余部分用Radix-2补充。比如2048 4^5 * 2就是5级Radix-4加1级Radix-2。混合基比纯Radix-2少了约33%的计算步骤Vector单元的利用率更高。数据排布。FFT运算需要频繁访问旋转因子和中间结果数据访问模式是逐级变化的——每级的蝶形运算的输入间距不同。这种不规则的访问模式对NPU的内存系统是挑战。ops-fft的做法是在每一级蝶形运算之前重排数据使得当前的蝶形运算变成连续内存访问。具体来说# ops-fft内部的数据重排逻辑简化说明# 以8点FFT为例3级蝶形运算# 原始输入顺序: x[0], x[1], x[2], x[3], x[4], x[5], x[6], x[7]# 第1级蝶形运算相邻元素配对 (0,1), (2,3), (4,5), (6,7)# 第2级蝶形运算间距2的元素配对 (0,2), (1,3), (4,6), (5,7)# 第3级蝶形运算间距4的元素配对 (0,4), (1,5), (2,6), (3,7)# ops-fft在第1级之前做Bit-Reversal重排# 使得所有级的蝶形运算都变成相邻元素操作# 重排后: x[0], x[4], x[2], x[6], x[1], x[5], x[3], x[7]# 这样每一级的蝶形运算都是相邻配对对Vector单元的SIMD更友好Bit-Reversal重排的代价是一次额外的数据搬运但换来了所有后续蝶形运算都是连续内存访问总体上更高效。Vector单元映射。昇腾NPU的Vector单元支持128个FP32通道或256个FP16通道的SIMD并行。ops-fft把每级蝶形运算的N/2个操作分批映射到Vector通道上。以2048点FFT为例每级有1024个蝶形运算。FP16模式下Vector有256个通道1024/2564批每批处理256个蝶形运算4批串行完成一级。log2(2048)11级总共44批Vector计算。ops-fft支持的算子类型ops-fft提供了完整的FFT算子族1D FFT。支持C2C复数到复数和R2C实数到复数两种模式。R2C模式利用实数信号的频域对称性只计算N/21个频点计算量减半。2D FFT。支持图像等2D数据的频域变换内部实现是先对行做1D FFT再对列做1D FFT。行列FFT之间需要做转置Transposeops-fft在转置步骤做了内存排布优化避免Cache冲突。IFFT。逆FFT和FFT的区别在于旋转因子的符号相反j变成-j以及结果需要除以N。ops-fft的IFFT复用FFT的计算路径只修改旋转因子的符号。FFT Shift。把零频分量移到频谱中心常用于图像频域可视化。FFT Shift本身不做FFT计算只是做数组的前后半交换。# ops-fft的调用示例通过AscendCL Python接口importacl# 创建1D FFT计划# plan描述了FFT的参数长度、数据类型、方向# 为什么用plan因为FFT的分解策略和旋转因子可以预计算# 多次执行同一个FFT时只需要计算一次planplanacl.fft.create_plan_1d(n2048,# FFT长度input_typeacl.FFT_C2C,# 复数输入复数输出directionacl.FFT_FORWARD# 正向FFT)# 执行FFT# input和output都在Device Memory上避免Host-Device搬运outputacl.fft.execute(plan,input,stream)# 销毁plan# 为什么需要显式销毁plan内部持有旋转因子表的Device Memory# 不销毁会导致显存泄漏acl.fft.destroy_plan(plan)实模式R2C的优化细节实数信号的FFT有一个重要的优化空间实数信号的频域结果是共轭对称的X[k] conj(X[N-k])。这意味着只需要计算前N/21个频点后N/2-1个频点可以通过共轭得到。ops-fft的R2C模式利用了这个性质把N点实数数据打包成N/2个复数数据做N/2点C2C-FFT然后从结果中恢复出N/21个频点。这样计算量从Nlog2(N)降到N/2log2(N/2)约减少50%。# R2C模式的使用示例plan_r2cacl.fft.create_plan_1d(n2048,input_typeacl.FFT_R2C,# 实数输入复数输出directionacl.FFT_FORWARD)# 输入是2048个float实数输出是1025个complexN/21个频点# 比C2C模式的2048个complex输出节省了约50%的内存和计算量real_signalacl.rt.malloc(2048*4)# 2048个float32freq_outputacl.fft.execute(plan_r2c,real_signal,stream)R2C模式在图像处理和音频信号处理中很常用因为原始信号通常是实数的。对于雷达信号这类本来就是复数的数据还是需要用C2C模式。使用前后效率对比以4K图像3840x2160的2D-FFT为例对比CPU和ops-fft的性能对比维度numpy.fft (CPU, 16核)scipy.fft (CPU, 16核)ops-fft (Ascend 910)2D-FFT延迟85ms42ms3.8ms吞吐量帧/秒1224263内存占用64MB64MB128MB含Device Memory功耗约120WCPU约120WCPU约70WNPU能效比帧/焦耳0.100.203.76ops-fft比numpy.fft快22倍比scipy.fft快11倍。能效比的差距更大——NPU的70W功耗远低于16核CPU的120W每焦耳能处理的帧数是CPU的18-37倍。再看不同FFT尺寸下的对比FFT尺寸numpy.fft延迟ops-fft延迟加速比2560.02ms0.008ms2.5x10240.12ms0.025ms4.8x40962.1ms0.12ms17.5x1638438ms0.65ms58.5xFFT尺寸越大ops-fft的加速比越高。小尺寸FFT256点的加速比只有2.5x因为数据搬运开销占比大NPU的计算优势体现不出来。大尺寸FFT16384点的加速比达到58.5x计算密集度上来了Vector单元的并行能力才能充分发挥。ops-fft和sip的关系ops-fft提供基础FFT算子sip提供信号处理领域的融合FFT算子。两者的区别在于ops-fft的FFT是独立的频域变换操作每次调用产生一次Global Memory的出入sip的FFT是融合流水线的一部分中间结果不写回Global Memory。如果你的应用只需要做FFT变换比如图像频域滤波、音频频谱分析ops-fft就够用了。如果你需要做FFT 加窗 IFFT 取模这样的固定流水线sip的融合算子性能更好。结尾ops-fft是昇腾NPU上频域计算的标准算子库它通过混合基分解、Bit-Reversal重排和Vector单元SIMD映射在昇腾NPU上实现了比CPU FFT库10-50倍的性能提升。理解FFT的蝶形运算原理和ops-fft的数据排布优化有助于选择合适的FFT尺寸和数据模式R2C vs C2C来获得最佳性能。对于需要更高性能的信号处理流水线可以考虑sip融合算子。仓库地址https://atomgit.com/cann/ops-fft
昇腾CANN频域算子库ops-fft：FFT算子从蝶形运算到NPU加速的实现原理
前言傅里叶变换是信号处理和科学计算的基石——时域到频域的转换、卷积定理把卷积变成乘法、图像压缩里的频域编码这些操作背后都是FFT。在CPU上FFTW和numpy.fft已经做得很好了但一旦数据量大到需要NPU加速比如64通道2048点的雷达信号、4K图像的2D-FFT通用CPU方案就力不从心了。昇腾CANN生态里的ops-fft仓库提供了在昇腾NPU上执行FFT/FFT2/IFFT等频域变换算子的实现专门针对达芬奇架构的Vector计算单元做了优化。CANN社区在atomgit.com/cann上开源了这个仓库是昇腾NPU上频域计算的标准算子库。FFT的数学原理和计算复杂度FFT快速傅里叶变换不是一种新的变换而是DFT离散傅里叶变换的快速算法。DFT的定义是X[k] sum(x[n] * exp(-j2pikn/N)), n0…N-1直接计算DFT需要N2次复数乘法FFT利用exp函数的周期性和对称性把N2降到N*log2(N)。比如N2048时DFT需要4,194,304次复数乘法FFT只需要22,528次加速186倍。FFT的核心操作是蝶形运算Butterfly Operation。一个2点FFT就是一次蝶形运算X[0] x[0] W * x[1] X[1] x[0] - W * x[1]其中W是旋转因子Twiddle FactorW exp(-j2pi*k/N)。N点FFT可以分解成log2(N)级蝶形运算每级有N/2个蝶形运算。蝶形运算的特点是每个蝶形只依赖两个输入计算结果直接写入输出位置不需要额外的临时存储。这个特点对NPU加速非常友好——可以把蝶形运算映射到Vector单元的SIMD通道上并行执行。ops-fft在昇腾NPU上的实现原理ops-fft的实现分三个层次分解策略、数据排布、Vector单元映射。分解策略。ops-fft支持Radix-2和Radix-4两种分解。Radix-2把N点FFT分解成两个N/2点FFT每级做N/2个2点蝶形运算。Radix-4把N点FFT分解成四个N/4点FFT每级做N/4个4点蝶形运算。Radix-4的计算步骤更少log4(N)级 vs log2(N)级但每个蝶形运算更复杂4输入4输出 vs 2输入2输出。ops-fft的默认策略是混合基分解对于2的幂次大小的FFT优先使用Radix-4分解剩余部分用Radix-2补充。比如2048 4^5 * 2就是5级Radix-4加1级Radix-2。混合基比纯Radix-2少了约33%的计算步骤Vector单元的利用率更高。数据排布。FFT运算需要频繁访问旋转因子和中间结果数据访问模式是逐级变化的——每级的蝶形运算的输入间距不同。这种不规则的访问模式对NPU的内存系统是挑战。ops-fft的做法是在每一级蝶形运算之前重排数据使得当前的蝶形运算变成连续内存访问。具体来说# ops-fft内部的数据重排逻辑简化说明# 以8点FFT为例3级蝶形运算# 原始输入顺序: x[0], x[1], x[2], x[3], x[4], x[5], x[6], x[7]# 第1级蝶形运算相邻元素配对 (0,1), (2,3), (4,5), (6,7)# 第2级蝶形运算间距2的元素配对 (0,2), (1,3), (4,6), (5,7)# 第3级蝶形运算间距4的元素配对 (0,4), (1,5), (2,6), (3,7)# ops-fft在第1级之前做Bit-Reversal重排# 使得所有级的蝶形运算都变成相邻元素操作# 重排后: x[0], x[4], x[2], x[6], x[1], x[5], x[3], x[7]# 这样每一级的蝶形运算都是相邻配对对Vector单元的SIMD更友好Bit-Reversal重排的代价是一次额外的数据搬运但换来了所有后续蝶形运算都是连续内存访问总体上更高效。Vector单元映射。昇腾NPU的Vector单元支持128个FP32通道或256个FP16通道的SIMD并行。ops-fft把每级蝶形运算的N/2个操作分批映射到Vector通道上。以2048点FFT为例每级有1024个蝶形运算。FP16模式下Vector有256个通道1024/2564批每批处理256个蝶形运算4批串行完成一级。log2(2048)11级总共44批Vector计算。ops-fft支持的算子类型ops-fft提供了完整的FFT算子族1D FFT。支持C2C复数到复数和R2C实数到复数两种模式。R2C模式利用实数信号的频域对称性只计算N/21个频点计算量减半。2D FFT。支持图像等2D数据的频域变换内部实现是先对行做1D FFT再对列做1D FFT。行列FFT之间需要做转置Transposeops-fft在转置步骤做了内存排布优化避免Cache冲突。IFFT。逆FFT和FFT的区别在于旋转因子的符号相反j变成-j以及结果需要除以N。ops-fft的IFFT复用FFT的计算路径只修改旋转因子的符号。FFT Shift。把零频分量移到频谱中心常用于图像频域可视化。FFT Shift本身不做FFT计算只是做数组的前后半交换。# ops-fft的调用示例通过AscendCL Python接口importacl# 创建1D FFT计划# plan描述了FFT的参数长度、数据类型、方向# 为什么用plan因为FFT的分解策略和旋转因子可以预计算# 多次执行同一个FFT时只需要计算一次planplanacl.fft.create_plan_1d(n2048,# FFT长度input_typeacl.FFT_C2C,# 复数输入复数输出directionacl.FFT_FORWARD# 正向FFT)# 执行FFT# input和output都在Device Memory上避免Host-Device搬运outputacl.fft.execute(plan,input,stream)# 销毁plan# 为什么需要显式销毁plan内部持有旋转因子表的Device Memory# 不销毁会导致显存泄漏acl.fft.destroy_plan(plan)实模式R2C的优化细节实数信号的FFT有一个重要的优化空间实数信号的频域结果是共轭对称的X[k] conj(X[N-k])。这意味着只需要计算前N/21个频点后N/2-1个频点可以通过共轭得到。ops-fft的R2C模式利用了这个性质把N点实数数据打包成N/2个复数数据做N/2点C2C-FFT然后从结果中恢复出N/21个频点。这样计算量从Nlog2(N)降到N/2log2(N/2)约减少50%。# R2C模式的使用示例plan_r2cacl.fft.create_plan_1d(n2048,input_typeacl.FFT_R2C,# 实数输入复数输出directionacl.FFT_FORWARD)# 输入是2048个float实数输出是1025个complexN/21个频点# 比C2C模式的2048个complex输出节省了约50%的内存和计算量real_signalacl.rt.malloc(2048*4)# 2048个float32freq_outputacl.fft.execute(plan_r2c,real_signal,stream)R2C模式在图像处理和音频信号处理中很常用因为原始信号通常是实数的。对于雷达信号这类本来就是复数的数据还是需要用C2C模式。使用前后效率对比以4K图像3840x2160的2D-FFT为例对比CPU和ops-fft的性能对比维度numpy.fft (CPU, 16核)scipy.fft (CPU, 16核)ops-fft (Ascend 910)2D-FFT延迟85ms42ms3.8ms吞吐量帧/秒1224263内存占用64MB64MB128MB含Device Memory功耗约120WCPU约120WCPU约70WNPU能效比帧/焦耳0.100.203.76ops-fft比numpy.fft快22倍比scipy.fft快11倍。能效比的差距更大——NPU的70W功耗远低于16核CPU的120W每焦耳能处理的帧数是CPU的18-37倍。再看不同FFT尺寸下的对比FFT尺寸numpy.fft延迟ops-fft延迟加速比2560.02ms0.008ms2.5x10240.12ms0.025ms4.8x40962.1ms0.12ms17.5x1638438ms0.65ms58.5xFFT尺寸越大ops-fft的加速比越高。小尺寸FFT256点的加速比只有2.5x因为数据搬运开销占比大NPU的计算优势体现不出来。大尺寸FFT16384点的加速比达到58.5x计算密集度上来了Vector单元的并行能力才能充分发挥。ops-fft和sip的关系ops-fft提供基础FFT算子sip提供信号处理领域的融合FFT算子。两者的区别在于ops-fft的FFT是独立的频域变换操作每次调用产生一次Global Memory的出入sip的FFT是融合流水线的一部分中间结果不写回Global Memory。如果你的应用只需要做FFT变换比如图像频域滤波、音频频谱分析ops-fft就够用了。如果你需要做FFT 加窗 IFFT 取模这样的固定流水线sip的融合算子性能更好。结尾ops-fft是昇腾NPU上频域计算的标准算子库它通过混合基分解、Bit-Reversal重排和Vector单元SIMD映射在昇腾NPU上实现了比CPU FFT库10-50倍的性能提升。理解FFT的蝶形运算原理和ops-fft的数据排布优化有助于选择合适的FFT尺寸和数据模式R2C vs C2C来获得最佳性能。对于需要更高性能的信号处理流水线可以考虑sip融合算子。仓库地址https://atomgit.com/cann/ops-fft
