2.3 FFT并行算法

更新于 2026年11月21日 版权声明
2.3 FFT并行算法

FFT算法本身所具有的内在并行性,使得它非常适合在并行机上实现。并行机中的流水线机和阵列机属于SIMD(单指令多数据流)型系统,需要使用同步并行算法。多核片上系统(MPSoC)符合共享存储的MIMD的异步并行计算模型APRAM特征,能够实现异步并行算法,按“任务功能块级”并行执行。在MIMD的异步并行计算模型APRAM上,实现FFT算法有两个关键指标影响并行加速比,一是处理机任务分配调度,应尽量做到负载平衡;二是尽量减少通信,减少并行处理机的同步等待时间。FFT经典并行算法的基本思路:每一级变换中有图示个蝶形运算,将这些运算平均分配到各处理器分别计算;再把运算结果上传到指定的综合处理器,对运算结果进行整合;按照上述步骤完成每一级变换运算,最后再对结果进行排序。这种算法运算效率非常高,其中Cooley-Tukey算法就是一种基于具有共享存储器的MIMD模型上的并行FFT算法:

算法2.1 Cooley-Tukey并行算法(https://www.daowen.com)

图示

在算法2.1 中,在同一级变换中,把蝶形运算分别送入各处理机并行计算,共需要做复数乘法运算图示次,复数加法运算Nlg N次。其中每次复数乘法运算包含四次实数乘法与两次实数加法运算,每次复数加法运算包含两次实数加法运算。因此,算法运算量为实乘法共计2Nlg N次,实加法共计2Nlg N次。假设有M个CPU,理论上每个CPU运算量为图示实乘法,图示实加法。但是在实际上机运行中,因为每一层需要同步运算的时间与一个蝶形运算消耗的时间几乎差不多,从而并行效率会下降。

✍AI写作