面向向量处理器的基于SIMD的FFT并行计算方法

摘要

本发明公开了一种面向向量处理器的基于SIMD的FFT并行计算方法，包括以下步骤：根据FFT变换的长度N和向量处理单元的数目M，确定迭代级数L和混洗级数K，并计算蝶形因子数目(N+M×(K-2))；其中N＝2L，M＝2K；在向量存储体中分配两块存储区，其中，第一块存储区的大小为N×W，第二块存储区的大小为(N+M×(K-2))×W；从ASRAM中将待运算数据加载到第一块存储区，蝶形因子加载到第二块存储区；取出待运算数据和相应的蝶形因子，前(L-K)级，进行蝶形运算后结果返回到原存储位置，后K级数据经混洗后进行一级蝶形运算，再混洗，结果返回原存储位置。本发明原理简单且操作方便，能提高计算速度。

说明书

技术领域

本发明涉及向量处理器以及数字信号处理领域，尤其涉及一种用于向量处理器的基于 SIMD的FFT并行计算方法。

背景技术

随着4G无线通信技术，高清视频图像处理技术的发展，向量处理器得到了广泛的应用。 图1为向量处理器的一般性结构示意图，其中向量处理器一般由M个向量处理单元(PE)组 成，每个PE包含数个功能单元，一般包括ALU(算术逻辑单元)、MAC(乘法单元)、BP (移位单元)等，这些功能部件可以读写一组局部寄存器：每个PE包含一组局部寄存器， 所有PE的同一编号的局部寄存器在逻辑上又组成一个向量寄存器。例如图1中PE_0～PE_M-1 的所有R₀寄存器在逻辑上组成了向量寄存器VR₀，每个PE所对应的R₀称为向量寄存器VR₀的一个元素。向量处理器采用SIMD(单指令流多数据流，Single Instruction stream Multiple Data  streams)的方式，在同一条向量指令的控制下，M个PE同时对各自同一编号的局部寄存器 进行相同的操作，用以开发应用程序的数据级并行性，其高效性在解决运算密集型的应用中 具有很大的优势。而VLIW(Very Long Instruction Word，超长指令字)是指一种非常长的指 令组合，它把许多条指令连在一起，增加了运算速度。

FFT(Fast Fourier Transform，快速傅里叶变换)算法大大减少了离散傅里叶变换(DFT) 的计算量。例如，N点DFT变换，其计算量为N²，基2的FFT的计算量为Nlog₂N，因此 被经常被用来实现数据从时域到频域的转换，是OFDM(Orthogonal Frequency Division  Multiplexing，正交频分复用)解调、图像信号处理、GPS卫星定位等许多系统中的核心算法， 得到了越来越广泛的应用。传统的FFT算法的实现方法多种多样，一般采用通用处理器或单 独的数字信号处理器来串行进行FFT运算。FFT对运算速度和数据的吞吐能力都有很高的要 求，如何高效实现FFT算法一直是业界研究的热点问题。

根据FFT算法的特点，在每一级的所有FFT蝶形单元中，前后两个待运算数据是等间隔 的，并进行同样结构的基本蝶形运算，如图2为按频率抽取基2FFT基本蝶形图，蝶形单元 的数据间隔为N/2，且两数之和存回第一个数据的原位置，两数之差与蝶形因子的积存回第 二个数据的原位置，这个特性非常适合进行数据的并行处理，因此提出一种在向量处理器上 基于SIMD实现FFT并行计算的方法。

发明内容

本发明所要解决的技术问题是：针对现有技术存在的问题，本发明提供一种原理简单、 操作方便、能充分利用向量处理器的多级并行性特点，提高计算速度的面向向量处理器的基 于SIMD的FFT并行计算方法。

为解决上述技术问题，本发明采用以下技术方案：

一种面向向量处理器的基于SIMD的FFT并行计算方法，其特征在于包括以下步骤：

(1)根据FFT变换的长度N和向量处理单元的数目M，确定迭代级数L和混洗级数K， 并计算蝶形因子数目J；其中N＝2^L，M＝2^K：

(2)在向量存储体中分配两块存储区，其中，第一块存储区的大小为N×W，第二块存 储区的大小为J×W，其中W为待运算数据宽度；从ASRAM中将待运算数据加载到第一块 存储区，蝶形因子加载到第二块存储区；

(3)从向量存储体中取出待运算数据和相应的蝶形因子，判断是否为前(L-K)级，若 是，则基于VLIW和SIMD对待运算数据进行一级蝶形运算，并将运算结果返回到向量存储 体中的原存储位置，转到步骤(5)，否则，转到步骤(4)；

(4)将待运算数据进行混洗操作，基于VLIW和SIMD对待运算数据进行一级蝶形运算， 对运算结果进行混洗操作，并将操作结果返回到向量存储体中的原存储位置；

(5)判断是否已运算了L级，若没有，则返回步骤(3)；若是，则完成并结束计算。

作为本发明的进一步改进：

所述向量存储体包括M个存储块，所述M个存储块与M个向量处理单元依次一一对应； M个存储块统一编址，按BANK交叉存放(指第一个字在第一个BANK存放，第二个字在 第二个BANK存放，...，直到第M个字在第M个BANK存放。然后第M+1个字又在第一 个BANK存放，...，依次类推)；每个存储块分成上存储区和下存储区并支持同时进行两个 向量访存操作。

所述步骤(2)中将待运算数据加载到第一块存储区，具体包括以下步骤：将待运算数据 平均分为第一部分数据和第二部分数据，所述第一部分数据的存储地址结束于所述上存储区 的最后端，所述第二部分数据的存储地址开始于所述下存储区的最前端，所述第一部分数据 和第二部分数据的存储地址连续。

所述基于VLIW和SIMD对待运算数据进行蝶形运算时，采用3重循环控制，第1重循 环控制迭代级数，第2重循环控制相同子序列个数，第3重控制单个子序列运算次数。

当第3重循环次数少于循环填充次数(循环体之外的填充次数)时，所述第2重循环和 第3重循环的顺序互换。

所述步骤(2)中将蝶形因子加载到第二块存储区时，前(L-K)级蝶形因子连续存储， 最后K级的蝶形因子存储时每级存储M个，蝶形因子数为M/2个的蝶形因子连续存储2次、 蝶形因子数为M/4个的蝶形因子连续存储4次……依此类推，最后一级的蝶形因子不存储； 则蝶形因子数目J＝N+M×(K-2)。

前(L-K)级的蝶形因子存储时，只存储奇数级的蝶形因子；计算时，偶数级的蝶形因 子与前一级的蝶形因子共用；最后K级的蝶形因子存储时每级存储M个，蝶形因子数为M/2 个的蝶形因子连续存储2次、蝶形因子数为M/4个的蝶形因子连续存储4次……依此类推， 最后一级的蝶形因子不存储；当(L-K)为偶数时，蝶形因子数目J＝2×(N-M)/3+M×(K-1)； 当(L-K)为奇数时，蝶形因子数目J＝2×(N-M/2)/3+M×(K-1)。

与现有技术相比，本发明的优点在于：

1、本发明的面向向量处理器的基于SIMD的FFT并行计算方法，每次前后连续取M个 数据，M个PE并行进行蝶形运算，这种基于SIMD的面向向量处理器的向量化实现方法是 提高FFT计算性能的有效方法。能够充分利用向量处理器的向量计算特点、挖掘向量处理器 的多级并行性，充分开发了FFT算法的数据并行性，能够大幅度提高FFT的运算速度。

2、本发明的面向向量处理器的基于SIMD的FFT并行计算方法，待运算数据的存储方 式，既保持了待运算数据前后部分的连续存储，便于数据共享和程序的循环控制，又最大程 度减少了访存冲突，避免了不必要的开销。蝶形因子的存储方式，利用蝶形因子的可重用性， 减少了蝶形因子的数量，节省了存储空间。待运算数据和蝶形因子在向量存储器中连续存储， 且与向量处理单元的PE_0～PE_M-1一一对应，为M个PE提供高带宽的数据访问提高支持。

附图说明

图1是现有的向量处理器的结构示意图。

图2是本发明的按频率抽取基2FFT基本蝶形图。

图3是本发明的总流程图。

图4是本发明的向量存储体的结构示意图。

图5是本发明具体实施例的数据存储示意图。

图6是本发明具体实施例中以N＝8点FFT为例的FFT运算的迭代示意图。

图7是本发明的混洗方式示意图。

图8是本发明具体实施例的混洗方式示意图。

具体实施方式

以下将结合说明书附图和具体实施例对本发明作进一步详细说明。

如图3所示，本发明的一种面向向量处理器的基于SIMD的FFT并行计算方法，以按频 率抽取2048点基2FFT为例，包括以下步骤：

1、根据FFT变换的长度N＝2048和向量处理单元的数目M＝16，确定迭代级数L＝11和 混洗级数K＝4，并计算蝶形因子数目J，根据蝶形因子的存储方式不同，J有2种结果。以下 以(N+M×(K-2))＝2080为例进行说明。

2、在向量存储体中分配两块存储区，其中，第一块存储区的大小为2048×W，第二块存 储区的大小为2080×W，其中W是待运算数据的宽度，包括实部和虚部。通过DMA从ASRAM (异步存储器)中将待运算数据加载到第一块存储区，蝶形因子加载到第二块存储区。

如图4所示，向量存储体由M＝16个块(BANK_0～BANK_15)组成，且与向量处理单 元的PE_0～PE_15一一对应，16个BANK统一编址，按BANK交叉存放，可以进行数据共 享，为16个PE提供高带宽的数据访问；每个BANK按两组多体交叉组织形式支持多端口访 问(多端口包括两个向量访存操作端口，还包括DMA端口和标量访存端口)，即分成上下两 个存储区，可同时支持两个向量访存操作。

本实施例中，如图5所示，加载待运算数据时，将2048点数据分为前后两部分，优先将 两部分数据在BANK上下存储区的分界处前后存储，即BANK上存储区放前1024点数据， 一直到BANK上存储区的最后端；BANK下存储区放后1024点数据，且从BANK下存储区 的最前端开始，并使得两部分数据的地址连续；在能将两部分数据在BANK上下存储区的分 界处前后存储的情况下，既可以进行数据共享，又有效避免了访存冲突的产生。本方法既保 持了待运算数据前后部分的连续存储，便于数据共享和程序的循环控制，又最大程度减少了 访存冲突，避免了不必要的开销。

本实施例中，存储待运算蝶形因子时，11级因子逐级存储，最后四级的不同蝶形因子个 数分别为8个，4个，2个，1个；由于最后四级每级因子少于16个，我们采取8个因子连 续存放两次；4个因子连续存放4次；2个因子连续存放8次，1个因子连续存放16次的方 式存储，由于最后一级因子为1，为了节省存储空间和减少乘法运算次数，所以省略掉了， 这样总的蝶形因子的个数为2080个(做为本发明的进一步改进，前7级还可以每两级存储一 级的方式连续存储，即只需存储一，三，五，七级的因子，二，四，六级可以共用前一级的 因子，即第一级存储1024个，接着存储第三级的256个，第五级的64个，第七级的16个； 这样总的蝶形因子的个数减少为1408个)。本方法利用蝶形因子的可重用性，减少了蝶形因 子的数量，节省了存储空间。

3、向量处理单元从向量存储体中取出待运算数据和相应的蝶形因子，判断是否为前7级， (当前级数用比较指令进行条件判断，即每运算1级L递减1，并与(L-K)进行比较，这里 L＝11，K＝4)，若是，则基于VLIW和SIMD对待运算数据进行一级蝶形运算，并直接将运算 结果返回存储到向量存储体中的原存储位置，进行同址迭代，转到步骤5，否则，转到步骤4。

如图6所示，是以N＝8点FFT为例的FFT运算的迭代示意图，每级进行原位运算，且 每级蝶形单元数据间隔依次为N/2，N/4，N/8，…，直到N/N；N＝2048时，每级蝶形单元数 据间隔依次为1024，512，256，…，1。

4、后四级FFT运算时，向量处理单元从向量存储体中取出待运算数据并进行混洗操作， 从向量存储体中取出蝶形因子，基于VLIW和SIMD对待运算数据进行一级蝶形运算，将运 算结果进行混洗操作，将操作结果返回存储到向量存储体中的原存储位置。

本发明的混洗级数为K，其中K＝log₂M，M为向量处理器中向量处理单元PE的数目 (本实施例中，M＝16)，一般为2的整数次幂。混洗操作通过混洗指令VEXC mode，VR_i， VR_j来实现，VR_i和VR_j用以指定要进行数据交换的两个向量寄存器，mode为模式编号， 用来指定这两个向量寄存器之间数据交换的模式，mode的取值为0、1、2、…、2×K-1，各 混洗模式下的交换方式由用户事先设定，并通过DMA提前加载到混洗模式存储器中。如图7 所示，本发明的混洗方式，通过混洗指令和数据混洗单元，VR_x和VR_y任意PE中的元素R_x和R_y的值可以来自VR_i和VR_j任意PE中的局部寄存器R_i或R_j的值，即通过混洗操作可以在 所有PE间进行数据交换。

图8是本实施例的混洗方式示意图，其中，Mode0-1为倒数第4级的混洗方式，Mode2-3 为倒数第3级的混洗方式，Mode4-5为倒数第2级的混洗方式，Mode6-7为倒数第1级的混 洗方式。通过混洗操作，在最后4级运算中分别一次性实现了2个16点、4个8点、8个4 点、16个2点的蝶形单元的运算，能使16个PE同时工作，提高了运算效率。

5、判断是否已运算了L级，若没有，则返回步骤3；若是，则完成并结束计算。

上述步骤中，蝶形运算时，前5级共用3重循环程序，随着级数的增加，子序列个数呈 指数增加到32个，单个子序列点数呈指数减少为64点，即第6级的内层为前后各32点的子 序列，16个VPE只需运算两次，少于循环填充次数3次，所以我们单独抽出第6级，并对调 第2重与第3重循环，这样，就变成了外层控制单个子序列运算次数，内层控制相同子序列 个数的2重循环程序。这样，程序便可顺利地进行软件流水。

以上所述仅是本发明的优选实施方式，本发明的保护范围并不仅局限于上述实施例，凡 属于本发明思路下的技术方案均属于本发明的保护范围。应当指出，对于本技术领域的普通 技术人员来说，在不脱离本发明原理前提下的若干改进和润饰，应视为本发明的保护范围。