一种用于FFT处理器的数据无冲突存取方法

摘要

本发明涉及FFT处理器的存取方法技术领域，公开了一种用于FFT处理器的数据无冲突存取方法，包括：基于数据堆计算公式以获得待存取数据所在的堆；计算所述待存取数据在所述堆中的地址，从而确定出所述待存取数据在FFT处理器的存储器组中的地址。该方法具有支持较大基的单蝶形单元运算和较小基的多蝶形单元运算，可以充分利用FFT处理器的硬件并行度，从而能够避免在同时存取多个待存取数据时发生数据冲突的问题的优点。

说明书

技术领域

本发明涉及FFT处理器的存取方法技术领域，特别是涉及一种用于FFT处理器的数据无冲突存取方法。

背景技术

FFT是离散傅里叶变换(DFT)的一种快速实现方法，可以将数据在时域和频域之间进行转换。由于FFT是计算密集型算法，通常采用专用硬件进行FFT运算处理。基于存储的(memory-based)架构是一种常用的FFT专用硬件架构。基于存储的FFT架构，即，FFT处理器，其至少包括一个存储器、一组处理单元和一个控制单元。

FFT处理器可以采用数据无冲突算法同时存取多个数据用于处理单元做蝶形运算，存储器还需要同时存储多个数据用于保存当前蝶形运算的结果。为了解决同时存取多个数据时的数据冲突问题，需要一种用于FFT处理器的数据无冲突存取方法以保证需要的数据能够并行无冲突存取。

通常基于存储架构的FFT处理器的处理单元支持较大基的单蝶形单元运算和较小基的多蝶形单元运算，比如处理单元同时支持一个基四和两个基二运算。但是大部分现有的数据无冲突存取算法只能支持特定的FFT处理器中的处理单元，有些数据无冲突存取算法无法同时支持较大基的单蝶形单元运算和较小基的多蝶形单元运算。

发明内容

(一)要解决的技术问题

本发明的目的是提供一种用于FFT处理器的数据无冲突存取方法，以解决FFT处理器同时支持较大基的单蝶形单元运算和较小基的多蝶形单元运算时的数据冲突问题。

(二)技术方案

为了解决上述技术问题，本发明提供一种用于FFT处理器的数据无冲突存取方法，包括：基于数据堆计算公式以获得待存取数据所在的堆；计算所述待存取数据在所述堆中的地址，从而确定出所述待存取数据在FFT处理器的存储器组中的地址。

其中，基于FFT处理器的并行度以及FFT处理器内的最大基构建第一平衡方程，所述第一平衡方程为

P＝N_max＝2^L，

其中，P为FFT处理器的并行度，N_max为FFT处理器内的最大基，L为2的幂指数。

其中，将FFT运算的总点数N_总按照混合基算法分解为m级蝶形运算，每一级蝶形运算的点数为N₁,N₂........N_m，待存取数据在每一级蝶形运算中可由n₁，n₂.......n_m来确定，其中，

n_i(i＝1,2,3····m)分别代表待存取数据在第i级的蝶形运算中的排序。

其中，所述数据堆计算公式为

其中，bank为待存取数据在存储器组中的堆，a_i(i＝1,2,3·····m)为n_i或n_i的位倒序，modN_max为对N_max进行取模运算。

其中，当FFT运算的总点数N_总按照混合基算法分解为m级蝶形运算时，若m≥2，则至少有一个a_i满足

其中，为n_i的位倒序，n_i为待存取数据在第i级蝶形运算的排序。

其中，在计算所述待存取数据在所述堆中的地址，从而确定出所述待存取数据在FFT处理器的存储器组中的地址的步骤中，当FFT处理器中的总点数N_总小于等于N_max时，所述待存取数据在所述堆中的存储地址都相同，即，addr＝0；当FFT处理器中的总点数N_总大于N_max时，>

其中，若在m级蝶形运算中有一个级为j级，j级满足

1≤j＜m，

N₀×N₁×…×N_j≤N_max，

N₀×N₁×…×N_j+1＞N_max，

则所述待存取数据的地址方程为

addr＝N_m…N_j+2n′_j+1+…+N_mn_m-1+n_m，

其中，addr为待存取数据的地址，m代表蝶形运算的级，N_m为第m级蝶形运算的点数，n_m为待存取数据在第m级蝶形运算中的排序。

其中，n’_j+1为n_j+1的高位比特，＞＞为右移符号，为对向上取整。

其中，若在m级蝶形运算中有一个级为j级且j级满足

1＜j≤m，

N_j…N_m≤N_max，

N_j-1…N_m＞N_max，

则所述待存取数据的地址方程为

addr＝N_j-1…N₂n₁+…+N_j-1n_j-2+n_j-1，

其中，N′_j-1为N_j-1的高位比特，n′_j-1为n_j-1的高位比特。

其中，

其中，N′_j-1为n_j-1的高位比特，N_j-1为第j-1级蝶形运算的点数，＞＞>max为FFT处理器内的最大基，n’_j-1为n_j-1的高位比特，n_j-1为待存取数据在第j-1级蝶形运算中的排序，N_m为第m级蝶形运算的点数。N_j为第j级蝶形运算的点数。

(三)有益效果

本发明提供的用于FFT处理器的数据无冲突存取方法，与现有技术相比，具有如下优点：

该方法支持较大基的单蝶形单元运算和较小基的多蝶形单元运算，可以充分利用FFT处理器的硬件并行度，从而能够避免在同时存取多个待存取数据时发生数据冲突的问题。

附图说明

图1为本申请的实施例的用于FFT处理器的数据无冲突存取方法的步骤流程示意图；

图2为本申请的实施例的用于FFT处理器的数据无冲突存取方法的位倒序示意图。

具体实施方式

下面结合附图和实施例，对本发明的具体实施方式作进一步详细描述。以下实例用于说明本发明，但不用来限制本发明的范围。

如图1所示，图1示意性地显示了该数据无冲突存取方法的步骤流程示意图。该方法包括：

步骤S410，基于数据堆计算公式以获得待存取数据所在的堆。

步骤S420，计算所述待存取数据在所述堆中的地址，从而确定出所述待存取数据在FFT处理器的存储器组中的地址。

基于存储的FFT处理器的硬件数据用于无线通信系统(4G和WLAN)，其并行度为16，可以最多支持同时处理一个基16、两个基8、两个基5、四个基4、四个基3或八个基2蝶形运算。

FFT处理器可以支持8至8192点的2的整数幂FFT运算和12 至2400点的非2的整数幂DFT运算(可以用基2、基3、基5完成运算)。该FFT处理器的存储器包含一个或多个存储器组，每个寄存器组包含P个堆。在每一级蝶形运算中，存储器从一个确定的存储器组中读取待存取数据，并将该待存取数据送入处理单元，然后，将处理单元的结果保存到同一个或另一个确定的存储器组中。待存取数据在存储器组中的地址由其所在的堆和其在堆中的地址唯一确定。由此可知，若想确定出待存取数据在存储器组中的地址，则首先应当确定出待存取数据在存储器组中的堆，即，通过步骤S410便可获得。然后，确定出该待存取数据在堆中的地址，即通过步骤S420便可获得。

该方法支持较大基的单蝶形单元运算和较小基的多蝶形单元运算，可以充分利用FFT处理器的硬件并行度，从而能够避免在同时存取多个待存取数据时发生数据冲突的问题。

为优化上述技术方案中的步骤S410，基于FFT处理器的并行度以及FFT处理器内的总点数构建第一平衡方程，所述第一平衡方程为

P＝N_max＝2^L，

其中，P为FFT处理器的并行度，N_max为FFT处理器内的最大基，L为2的幂指数。

在一个实施例中，将FFT运算的总点数N_总按照混合基算法分解为m级蝶形运算，每一级蝶形运算的点数为N₁,N₂........N_m，待存取数据在每一级蝶形运算中可由n₁，n₂.......n_m来确定，其中，

n_i(i＝1,2,3·····m)分别代表待存取数据在第i级的蝶形运算中的排序。

为优化上述技术方案中的步骤S410，在上述技术方案的基础上，该数据堆计算公式为

其中，bank为待存取数据在存储器组中的堆，a_i(i＝1,2,3·····m)>i或n_i的位倒序，modN_max为对N_max进行取模运算。

n_i(i＝1，2，…m)的数据位宽为L比特，不满L比特的通过高位补零达到L比特。

需要说明的是，位倒序是将数据按照比特位倒序输出，结果的最高位是位倒序前的最低位，结果的次高位是位倒序的次低位，依次类推。

在一个实施例中，当FFT运算的总点数N_总按照混合基算法分解为m级蝶形运算时，若m≥2，则至少有一个a_j满足

其中，a_i(i＝1，2，3·····m)为n_i的位倒序，n_i为待存取数据在每一级蝶形运算中的排序。

在一个实施例中，在计算所述待存取数据在所述堆中的地址，从而确定出所述待存取数据在FFT处理器的存储器组中的地址的步骤中，当FFT处理器中的总点数N_总小于等于N_max时，所述待存取数据在所述堆中的存储地址都相同，即，addr＝0。

在一个具体的实施例中，当FFT运算的总点数N_总小于16时，所述待存取数据在所述堆中的存储地址都相同，即，addr＝0。

在另一个实施例中，在计算所述待存取数据在所述堆中的地址，从而确定出所述待存取数据在FFT处理器的存储器组中的地址的步骤中，当FFT处理器中的总点数N_总大于N_max时，所述待存取数据在所述堆中的存储地址有两种选择。

若在m级蝶形运算中有一个级为j级且j级满足

1≤j＜m，

N₀×N₁×…×N_j≤N_max，

N₀×N₁×…×N_j+1＞N_max，

则所述待存取数据的地址方程为

addr＝N_m…N_j+2n′_j+1+…+N_mn_m-1+n_m，

其中，m代表蝶形运算的级，addr为待存取数据的地址，N_m为第m级蝶形运算的点数，n_m代表待存取数据在第m级蝶形运算中排在第n_m个数。

在一个具体的实施例中，当FFT处理器中的总点数N_总大于16时，若在m级蝶形运算中有一个级为j级且j级满足

1≤j＜m，

N₀…N_j≤16，

N₀…N_j+1＞16，

且

其中，n’_j+1为n_j+1的高位比特，＞＞为右移符号，为对向上取整。

在第i个阶段的运算中，控制单元需要每次从存储器中存取K个数据，这K个数据组成一个数据块。每个周期控制单元从存储器中读取一个数据块到运算单元，并将运算单元得出的结果数据块存入存储器中。

如果，N_i＝16则K＝16。每个数据块包含一个基16蝶形的数据。每个数据块有n_i＝(0，1，…，15)和相同的n_k(K不等于i)。

如果N_i≠16，则每个数据块中包含多个蝶形单元的待存取数据。相同的蝶形单元中有n_i＝(0，1，…，N_i-1)，每个数据块中不同的蝶形单元有不同的n_j和相同的n_k(K不等于i或j)。其中j的取值为

以216点FFT为例。假设

待存取数据的存储公式为：

bank＝(n₁+n₂+n₃+n₄)mod16，

addr＝9n,₂+3n₃+n₄，

其中，

，

在数据输入阶段，数据并行度为9，同时输入的数据有相同的n₁,n₂和n₃＝(0,1,2)，n₄＝(0,1,2)。

在第一个阶段的运算中，数据块中相同的基8蝶形单元中有n₁＝(0,1,…,7)，不同的基8单元有n₂＝(0,1)或n₂＝(2)，分别对应同时进行两个或一个基8运算。

在第二个阶段的运算中，数据块中相同的基3蝶形单元中有n₂＝(0,1,2)，不同的基3单元有n₁＝(0,1,2,3)或n₁＝(4,5,6,7)，对应同时进行四个基3运算。

在第三个阶段的运算中，数据块中相同的基3蝶形单元中有n₃＝(0,1,2)，不同的基3单元有n₁＝(0,1,2,3)或n₁＝(4,5,6,7)，对应同时进行四个基3运算。

在第四个阶段的运算中，数据块中相同的基3蝶形单元中有n₄＝(0,1,2)，不同的基3单元有n₃＝(0,1,2)，对应同时进行三个基3运算。

在数据输出阶段，数据并行度为8，同时输出的数据有相同的n₂，n₃，n₄和n₁＝(0，1，2，3，4，5，6，7)。

若在m级蝶形运算中有一个级为j级且j级满足

1＜j≤m，

N_j…N_m≤N_max，

N_j-1…N_m＞N_max，

则所述待存取数据的地址方程为

addr＝N′_j-1…N₂n₁+…+N′_j-1n_j-2+n′_j-1，

其中，N′_j-1为N_j-1的高位比特，n′_j-1为n_j-1的高位比特。

在一个实施例中，

其中，N′_j-1为N_j-1的高位比特，N_j-1为第j-1级蝶形运算的点数，＞＞为右移符号，N_max为FFT处理器内的总点数，n’_j+1为n_j-1的高位比特，n_j-1为待存取数据在第j-1级蝶形运算中的排序，N_m为第m级蝶形运算的点数。N_j为第j级蝶形运算的点数。

综上所述，该方法支持较大基的单蝶形单元运算和较小基的多蝶形单元运算，可以充分利用FFT处理器的硬件并行度，从而能够避免在同时存取多个待存取数据时发生数据冲突的问题。

以上所述仅为本发明的较佳实施例而已，并不用以限制本发明，凡在本发明的精神和原则之内，所作的任何修改、等同替换、改进等，均应包含在本发明的保护范围之内。