基于Matrix的大点数FFT向量化设计与实现

摘要

本文依托Matrix多核并行的体系结构，结合大点数FFT的算法特性运用MFA算法完成了按频率抽取的基2一维以及二维的单核与多核大点数FFT向量化设计。总结起来本文所做的工作主要包括以下几点：
　　（1）实现了 MFA算法所需要的行列运算以及系数运算的子程序。列运算中运用令每个VPE对1列数据进行FFT运算16个VPE同时工作的方法优化了数据的访存形式，使核内外的数据交互更加易行；依据 Matr ix的结构提出一种运用计算压缩系数存储的方法，减少了核内外数据的搬移量。
　　（2）实现了大点数按频率抽取的基2FFT子程序（MF A算法）。在实现过程中优化了数据的存储布局，运用DMA索引取数的方法对列运算数据进行了重新排布，使列运算能够连续取数；使用双 Buffer的方法对数据进行传输使得数据传输和数据运算并行执行，大大提高了程序执行效率；同时通过内外循环互换、循环展开等方式对程序进行了流水排布，且通过消除AM_B usy等方法优化了程序，使程序具有了更高的性能。实验结果与标准基2FFT相比256K点双精度单核效率为30.95％，单精度512K点为29.35%。
　　（3）结合基2一维大点数FFT算法的特性，运用数据分组运算对数据进行分块然后调用MFA算法程序运算每块数据完成其单核实现，并结合多核间的数据同步对其进行了多核扩展。运用栅栏同步功能对多核之间的计算以及数据传输进行了同步；另外在循环过程中通过阻塞中断与信号灯的配合使用对数据的传输进行检测，简化了数据传输中断检测步骤；在系数准备过程中运用计算的方式对Buffer1中的系数数据进行生成，减少了数据的搬移次数，从而减少了程序开销。测试的结果显示双精度一维基2的1M点FFT单核、双核、四核、八核、十二核与标准FFT算法相比效率分别为：12.68%、6.21%、4.15%、2.39%、1.72%；单精度1M点的效率分别为：19.6%、13.15%、8.29%、4.65%、3.2%。
　　（4）分析介绍了二维FFT，同时借助MF A算法中的行和列FF T运算子程序实现了按频率抽取的基2二维大点数FFT。实现采用分块运算，充分发挥了GC的缓存功能，使DD R与AM的数据交互性能有了大幅提升；将相同的旋转因子存储在AM的不同半区，对数据进行交叉运算,减少了访存冲突对程序的影响。测试结果与标准二维基2FFT相比双精度1M点的单核、双核、四核、八核、十二核效率分别为：34.38%、29.58%、24.63%、16.82%、12.07%；单精度1M点的效率分别为：31.04%、27.49%、22.9%、14.96%、11.08%。

目录

声明

第一章 绪论

1.1 论文的研究背景和意义

1.2 本文所做的工作

1.3 论文的组织结构

第二章 大点数FFT算法分析

2.1 Matrix总架构

2.2 算法效率的制约因素

2.3 MFA算法分析

2.4 本章小结

第三章 MFA算法的设计与实现

3.1 单精度列计算

3.2 单精度行计算

3.3 双精度列计算

3.4 双精度行计算

3.5 本章小结

第四章 一维大点数FFT算法的设计与实现

4.1 大点数算法基础解析

4.2 单核程序的设计与实现

4.3 多核程序的设计与实现

4.4 性能分析

4.5 本章小结

第五章 二维大点数FFT算法的设计与实现

5.1 二维F F T算法原理

5.2 单核程序的设计与实现

5.3 多核程序的设计与实现

5.4 性能分析

5.5 本章小结

第六章 总结及工作展望

6.1 论文总结

6.2 展望及后续工作

致谢

参考文献

作者在学期间取得的学术成果