一种基于龙芯3号处理器的FFT高效并行实现优化方法

摘要

本发明公开了一种基于龙芯3号处理器的FFT高效并行实现优化方法，其特征在于，FFT高效并行实现优化方法是采用基-2蝶形计算并按如下步骤进行：1、设置初始化参数；2、获得所述FFT变换的级数；3、获得各旋转因子；4、划分子向量并判断是否进行分块处理；5、分块处理。本发明能解决现有并行FFT算法在龙芯3号处理器上低加速比的情况，达到在龙芯3号处理器上FFT的高效并行实现。

主权项

1.一种基于龙芯3号处理器的FFT高效并行实现优化方法，其特征在于，FFT高效并行实现优化方法是采用基-2蝶形计算并按如下步骤进行：步骤1、设置初始化参数，所述初始化参数为：源向量的长度N、龙芯3号处理器的核数p和分块长度NB；步骤2、利用式(1)获得所述FFT变换的级数S：S＝log₂N      (1)步骤3、利用式(2)获得各旋转因子$W_N^k=e^{-j\frac{2\pi }{N}k}---\left(2\right)$式(2)中，表示第k个旋转因子，k属于[1，N/2]；步骤4、将长度为N的源向量均分成p个长度为m的子向量；若m小于NB，则直接执行并行FFT变换，直到完成S级基-2蝶形计算；若m不小于NB，则执行步骤5；步骤5、将所述各子向量分块为各数据块，设定分块长度NB的取值范围为[a,b]，所述a为一级高速缓冲存储器L1-cache长度的一半；所述b为二级高速缓冲存储器L2-cache长度的一半；将各分块长度为NB的数据块分配到所述龙芯3号处理器的每个处理器核上执行并行FFT变换，直到完成第log₂(p^*NB)级基-2蝶形计算，获得中间向量；将所述中间向量按相同的旋转因子划分成p个中间子向量，所述中间子向量长度为m，将所述中间子向量分配到所述龙芯3号处理器的每个处理器核上执行，直到完成从第log₂(p^*NB)+1级到第S级基-2蝶形计算，从而完成FFT高效并行实现优化方法。