基于轻核阵列机的FFT算法并行化研究与实现

摘要

目前普遍采用基于流水的单路径延时反馈结构,或基于存储结构实现快速傅里叶变换(Fast Fourier Transform,FFT).前一种结构效率高但缺乏灵活性,而后一种结构通用性较好但性能较差.首先提出了一种FFT并行实现的算法,然后在并行图形阵列机(Parallel Array Architecture for Graphics,PAAG)平台上实现了基2时间抽取的FFT(Decimation-In-Timer FFT,DIT-FFT)算法;最后将长度为512的DIT-FFT算法分别映射到1个PE、4个PE、8个PE和16个PE上实现.分析实验结果显示:随着PE个数的增加,加速比呈曲线上升的趋势;但随着PE个数的不断增加,算法执行速度增长开始变得缓慢,当映射到8个PE上时,最大加速比可以达到5.98.