面向FFT并行计算的无冲突存储访问方法

摘要

本发明公开一种面向FFT并行计算的无冲突存储访问方法，该方法步骤包括：1)判断当前处理器的结构，若为SIMD结构，执行步骤3)；否则执行步骤2)；2)配置一个存储组存储运算数据，存储组包括多个并行的单端口存储体；执行FFT计算时，将待运算数据的地址映射为所对应的目标存储体以及在目标存储体内地址的二维无冲突访存地址；3)配置多个并行的存储组存储运算数据，每组存储组包括多个并行的单端口存储体；执行FFT计算时，将待运算数据的地址映射为所对应的目标存储组、目标存储体以及在目标存储体内地址的三维无冲突访存地址。本发明能够实现FFT并行计算的无冲突访问，具有访存效率高且硬件开销小的优点。

说明书

技术领域

本发明涉及微处理器中FFT运算技术领域，尤其涉及一种面向FFT并行计算的无冲突存 储访问方法。

背景技术

FFT(Fast Fourier Transform，快速傅里叶变换)算法是1965年由J.W.库利和T.W.图基 提出的实现离散傅里叶变换(Discrete Fourier Transform，DFT)的一种快速算法，是无线通 信、图像处理等许多嵌入式应用中的核心算法，其运算性能的高低往往决定着整个数字处理 系统的实时处理能力。应用需求的不断发展对FFT的性能也提出了越来越高的要求，随着数 字信号处理器技术的发展，使得实现高效可编程的FFT并行算法成为可能。

目前常见的FFT算法的实现方法分为两种，第一种是专用的FFT硬件加速器，例如基于 FPGA方式或将其作为微处理器片内的FFT硬件协处理器，其仅用于FFT算法加速；第二种 是基于通用微处理器或数字信号处理器指令集体系结构的软件编程实现。第一种方法的适用 范围有限，不能满足需求的发展变化，且硬件实现代价高、缺乏灵活性；第二种方法由于是 基于指令集编程方法的实现，因而具有一定的灵活性、通用性，而且随着高性能微处理器技 术的发展，使得采用这种方法也获得与专用FFT硬件加速器相当的运算性能。

N点序列x(n)的DFT计算公式如下：

$X\left(k\right)=\underset{n=0}{\overset{N-1}{\Sigma }}x\left(n\right)W_N^{\mathrm{nk}}---\left(1\right)$

其中，0≤k<N,假设序列长度N为2的整数幂。

基2时域抽取的FFT算法是利用旋转因子的对称性、周期性和可约性，将N点序列 x(n)按序号前后对半分开，将N点DFT X(k),k＝0,1,…,N-1，按频域序号的奇偶分成两个N/2 点的DFT，即：

$X\left(k\right)=\underset{n=0}{\overset{N/2-1}{\Sigma }}x\left(2n\right)W_{N/2}^{\mathrm{nk}}+W_N^k\underset{n=0}{\overset{N/2-1}{\Sigma }}x(2n+1)W_{N/2}^{\mathrm{nk}}---\left(2\right)$

令k＝2r,k＝2r+1，其中r＝0,1,2,…,N/2-1，X(k)按奇偶序号分开，有：

$\left(\begin{array}{c}X\left(2r\right)=\underset{n=0}{\overset{N/2-1}{\Sigma }}[x\left(n\right)+x(n+N/2)]W_{N/2}^{\mathrm{rn}}\\ X(2r+1)=\underset{n=0}{\overset{N/2-1}{\Sigma }}[x\left(n\right)-x(n+N/2)]W_N^n{W}_{N/2}^{\mathrm{rn}}\end{array}\right)---\left(3\right)$

如N/2仍然是偶数，则继续按如上方式分解，直到两点DFT为止。

N＝16点的序列X的基2蝶形运算流程如图1所示，16点序列基2的FFT计算依次分解 为8点、4点、2点DFT。长度为N的序列基2的FFT算法需要进行log₂N级、每级又有N 次蝶形运算，在每级蝶形单元中，前后两个待运算数据是等间隔的，并进行同样结构的蝶形 运算，蝶形单元的数据间隔为N/2^j，其中j为蝶形运算的级数，j＝1,2……log₂N；再将两数之 和存回第一个数据的原位置，两数之差与蝶形因子的积则存回第二个数据的原位置，FFT计 算的该特性非常适合进行数据的并行处理和在SIMD扩展结构实现向量化运算。

随着集成电路技术和性能需求的发展，单指令流多数据流(Single Instruction Multiple  Data，SIMD)结构已成为高性能微处理器的重要扩展，单芯片也可集成越来越多的功能单元。 采用超标量或超长指令字(Very LongInstruction Word，VLIW)结构，可以使多个功能单元 以SIMD方式对数据进行运算，以开发更多的指令级、数据级并行，从而获得更高的运算性 能。为充分利用微处理器运算单元中的乘法器、加法器，提高计算效率，高性能微处理器通 常支持双访问带宽(或以上)的并行访存操作。FFT的一次蝶形运算除了系数常数，还需要 一拍能提供两个操作数，因此FFT运算需要利用微处理器的双访问带宽提供操作数。

由于容量相同的双端口存储体的面积和功耗一般是单端口存储体的2倍，而片上大容量 存储器面积和功耗具有严格限制，因此片上存储结构一般选择数量为2的整数次幂个单端口 存储体，按低位交叉并行方式组织，能够以较低面积和功耗代价提供了双访问带宽。但由于 FFT蝶形运算的待运算数据地址的不连续性和对称性，每次蝶形运算都存在并行访存冲突； 特别在SIMD扩展结构中，访存冲突导致向量存储带宽使用效率降低，FFT的实际计算效率 将大幅低于理论峰值。

发明内容

本发明要解决的技术问题就在于：针对现有技术存在的技术问题，本发明提供一种实现 方法简单、能够消除FFT并行计算中访存冲突、访存效率高且硬件消耗小的面向FFT并行计 算的无冲突存储访问方法。

为解决上述技术问题，本发明提出的技术方案为：

一种面向FFT并行计算的无冲突存储访问方法，步骤包括：

1)判断当前处理器的结构，若为SIMD结构，转入执行步骤3)；否则转入执行步骤2)；

2)配置一个存储组存储运算数据，所述存储组包括多个并行的单端口存储体；执行FFT 计算时，将待运算数据的线性地址映射为二维无冲突访存地址，所述二维无冲突访存地址对 应为待运算数据所在的目标存储体以及在目标存储体内地址，根据所述二维无冲突访存地址 对数据进行访存；

3)配置多个存储组存储运算数据，每个存储组包括多个并行的单端口存储体；执行FFT 计算时，将待运算数据的线性地址映射为三维无冲突访存地址，所述三维访存地址对应为待 运算数据所在的目标存储组、目标存储体以及在目标存储体内地址，根据所述三维无冲突访 存地址对数据进行访存。

作为本发明的进一步改进：所述步骤2)中多个并行的单端口存储体的其中P个存储体 按照低位交叉方式进行编址，且P为大于3的奇数；步骤3)中每个存储组其中P个存储体 按照低位交叉方式进行编址，且P为大于3的奇数。

作为本发明的进一步改进：所述步骤2)中将待运算数据的线性地址按照下式映射为二 维无冲突访存地址(X，Y)；

其中，Y为待运算数据所在的目标存储体位置，X为在待运算数据在目标存储体内的行 地址，Addr为待运算数据的的线性地址，W为待运算数据粒度，p为采用低位交叉编址的存 储体个数，mod表示取模运算，N为FFT计算的序列长度。

作为本发明的进一步改进：所述步骤3)中将待运算数据的线性地址按照下式映射为三 维无冲突访存地址(X，Y，Z)；

其中，Y为待运算数据所在的目标存储体组位置，Z为待运算数据在目标存储组中目标 存储体的位置，X为待运算数据在目标存储体内的行地址；Addr为待运算数据的线性地址， G为SIMD宽度且G为2的正整数幂，p为每组存储组中采用低位交叉编址的存储体个数， mod表示取模运算，N为FFT计算的序列长度。

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

1)本发明通过分别针对非SIMD结构以及SIMD结构的双访问微处理器，将单端口存储 体分别组织为一维存储组、二维存储组的多体组织方式，在执行FFT计算时，通过将待运算 数据的线性地址分部映射为二维无冲突访存地址、三维无冲突访存地址，能够有效消除FFT 运算中的访存冲突，实现FFT运算的无冲突并行访存，同时提高了FFT运算效率。

2)本发明针对具有SIMD扩展结构的微处理器，将单端口存储体多体组织为按SIMD方 式操作的二维存储阵列结构，能够支持FFT并行算法的向量化扩展的无冲突访存，从而大幅 提高FFT的运算效率。

3)本发明通过将未采用SIMD结构中待运算数据的线性地址映射为对应的存储体、在存 储体中地址，将采用SIMD结构中待运算数据的线性地址映射为对应的存储组、存储体以及 在存储体中地址，仅改变了访存地址的计算方式，因而所需的硬件开销很小。

附图说明

图1是长度为16的基2FFT蝶形运算的实现原理示意图。

图2是本实施例基于面向FFT并行计算的无冲突存储访问方法的实现流程示意图。

图3是本实施例中非SIMD结构下存储体组织的结构原理示意图。

图4是实施例中SIMD结构下存储体组织的结构原理示意图。

图5是本发明具体实施例中非SIMD结构下存储体组织的结构原理示意图。

图6是本发明具体实施例中SIMD结构下存储体组织的结构原理示意图。

具体实施方式

以下结合说明书附图和具体优选的实施例对本发明作进一步描述，但并不因此而限制本 发明的保护范围。

如图2所示，本实施例面向FFT并行计算的无冲突存储访问方法，步骤包括：

1)判断当前处理器的结构，若为SIMD结构，转入执行步骤3)；否则转入执行步骤2)；

2)配置一个存储组存储运算数据，存储组包括多个并行的单端口存储体；执行FFT计 算时，将待运算数据的线性地址映射为二维无冲突访存地址，二维无冲突访存地址对应为待 运算数据所在的目标存储体以及在目标存储体内地址，根据二维无冲突访存地址对数据进行 访存；

3)配置多个存储组存储运算数据，每个存储组包括多个并行的单端口存储体；执行FFT 计算时，将待运算数据的线性地址映射为三维无冲突访存地址，三维访存地址对应为待运算 数据所在的目标存储组、目标存储体以及在目标存储体内地址，根据三维无冲突访存地址对 数据进行访存。

本实施例中，针对微处理器的双访问存储带宽需求，基于多个单端口存储体sram(Static  RAM)来构建片内存储器，且多个单端口存储体sram支持并行访存，以降低面积和功耗。

本实施例中，步骤2)中多个并行的单端口存储体其中P个存储体按照低位交叉方式进 行编址，且P为大于3的奇数；步骤3)中每个存储组其中P个存储体按照低位交叉方式进 行编址，且P为大于3的奇数。

本实施例中，步骤2)中将待运算数据的线性地址按照式(4)映射为二维无冲突访存地 址(X，Y)；

其中，Y为待运算数据所在的目标存储体位置，X为在待运算数据在目标存储体内的行 地址，Addr为待运算数据的的线性地址，W为待运算数据粒度，p为采用低位交叉编址的存 储体个数，mod表示取模运算，N为FFT计算的序列长度。表示取小于等于Addr/W 的最大整数。

本实施例在未采用SIMD结构的处理器中，假设存储器容量为2^H字节，H为正整数， 待运算数据粒度为W字节，并假设W为2的正整数幂，所有存储体采用或者部分采用低位 交叉编址的结构，其中采用低位交叉编址的存储体为P个(P为不小于3的奇数)。如图3所 示，整个存储器的字节地址为H位，表示为Addr[H-1:0]，以待运算数据粒度为单位的数据地 址为Data_Addr＝Addr/W，数据在存储体中的实际地址可以用二维坐标(X,Y)来表示，其中Y 表示实际访存存储体sram的序号，X表示在选中存储体中待运算数据所在的行地址，存储体 的线性地址Addr和实际地址(X,Y)的映射关系如式(4)所示，实际地址(X,Y)即为映射得到 的二维无冲突访存地址。

在未采用SIMD结构的处理器中采用上述存储体组织方式，进行序列长度为N的FFT运 算(N为2的正整数幂)时，通过双访问并行实现FFT的蝶形运算的过程中可以实现全程无 冲突访存操作。

本实施例中，步骤3)中将待运算数据的线性地址按照下式映射为三维无冲突访存地址 (X，Y，Z)；

其中，Y为待运算数据所在的目标存储体组位置，Z为待运算数据在目标存储组中目标 存储体的位置，X为待运算数据在目标存储体内的行地址；Addr为待运算数据的线性地址， G为SIMD宽度且G为2的正整数幂，P为每组存储组中采用低位交叉编址的存储体个数， mod表示取模运算，N为FFT计算的序列长度。

本实施例在采用SIMD结构处理器中，假设SIMD宽度为G，G为2的正整数幂，将未 采用SIMD结构的存储体结构进行数量为G的SIMD扩展得到SIMD结构的存储体，其中单 个存储结构仍然全部或者部分具有低位交叉编址的结构，并且其中采用低位交叉编址的存储 体为P’个(P’为不小于3的奇数)，每个存储体宽度为W字节。如图4所示，假设存储器容 量为2^H字节，待运算数据宽度为W字节，并假设W为2的整数幂，序列长度为N，整个存 储器的字节地址为H位，表示为Addr[H-1:0]，以待运算数据粒度为单位的数据地址为 Data_Addr＝Addr/W，数据在存储体中的实际地址可以用三维坐标(X,Y,Z)来表示，其中Y表示 实际访存地址在G个区域中位置，Z表示在该区域p个存储体中的位置，X则表示对应的行 地址，整个或者部分存储体的线性地址Addr和实际地址(X,Y,Z)的映射关系如式(5)所示， 实际地址(X,Y,Z)即为映射得到的三维无冲突访存地址。

在采用SIMD结构的处理器中采用上述存储体组织方式，通过双访问进行FFT向量化并 行运算时，可以实现全程无冲突执行。

以下以运算数据宽度W为4，序列长度N为例进一步说明本发明。

如图5所示，本实施例中在非SIMD结构下，采用P＝3个存储体进行低位交叉编址，运 算数据宽度W为4，序列长度N，二维无冲突访存地址用坐标(X，Y)表示，其中Y表示 目标访存存储体sram的序号，X表示待运算数据在目标存储体中的行地址，将待运算数据的 线性地址Addr按式(6)映射为二维无冲突访存地址(X，Y)：

其中，Y表示待运算数据在3个存储体中位置，X表示待运算数据在存储体中对应的行 地址。

如图6所示，本实施例中在SIMD结构下，每组存储体组中采用P＝3个存储体进行低位 交叉编址，运算数据宽度W为4，序列长度N，SIMD宽度取16，则整个存储体组被分成了 16个区域，三维无冲突访存地址用坐标(X，Y，Z)表示，将待运算数据的线性地址Addr 按式(7)映射为三维无冲突访存地址(X，Y，Z)：

其中，Y表示待运算数据在16个区域中位置，Z表示待运算数据在该区域3个存储体中 的位置，X则表示待运算数据在存储体中对应的行地址。

上述只是本发明的较佳实施例，并非对本发明作任何形式上的限制。虽然本发明已以较 佳实施例揭露如上，然而并非用以限定本发明。因此，凡是未脱离本发明技术方案的内容， 依据本发明技术实质对以上实施例所做的任何简单修改、等同变化及修饰，均应落在本发明 技术方案保护的范围内。