一種用於FFT處理器的數據無衝突存取方法與流程
2023-06-06 00:48:16 2
本發明涉及FFT處理器的存取方法技術領域，特別是涉及一種用於FFT處理器的數據無衝突存取方法。
背景技術：
FFT是離散傅立葉變換(DFT)的一種快速實現方法，可以將數據在時域和頻域之間進行轉換。由於FFT是計算密集型算法，通常採用專用硬體進行FFT運算處理。基於存儲的(memory-based)架構是一種常用的FFT專用硬體架構。基於存儲的FFT架構，即，FFT處理器，其至少包括一個存儲器、一組處理單元和一個控制單元。
FFT處理器可以採用數據無衝突算法同時存取多個數據用於處理單元做蝶形運算，存儲器還需要同時存儲多個數據用於保存當前蝶形運算的結果。為了解決同時存取多個數據時的數據衝突問題，需要一種用於FFT處理器的數據無衝突存取方法以保證需要的數據能夠並行無衝突存取。
通常基於存儲架構的FFT處理器的處理單元支持較大基的單蝶形單元運算和較小基的多蝶形單元運算，比如處理單元同時支持一個基四和兩個基二運算。但是大部分現有的數據無衝突存取算法只能支持特定的FFT處理器中的處理單元，有些數據無衝突存取算法無法同時支持較大基的單蝶形單元運算和較小基的多蝶形單元運算。
技術實現要素：
(一)要解決的技術問題
本發明的目的是提供一種用於FFT處理器的數據無衝突存取方法，以解決FFT處理器同時支持較大基的單蝶形單元運算和較小基的多蝶形單元運算時的數據衝突問題。
(二)技術方案
為了解決上述技術問題，本發明提供一種用於FFT處理器的數據無衝突存取方法，包括：基於數據堆計算公式以獲得待存取數據所在的堆；計算所述待存取數據在所述堆中的地址，從而確定出所述待存取數據在FFT處理器的存儲器組中的地址。
其中，基於FFT處理器的並行度以及FFT處理器內的最大基構建第一平衡方程，所述第一平衡方程為
P＝Nmax＝2L，
其中，P為FFT處理器的並行度，Nmax為FFT處理器內的最大基，L為2的冪指數。
其中，將FFT運算的總點數N總按照混合基算法分解為m級蝶形運算，每一級蝶形運算的點數為N1,N2........Nm，待存取數據在每一級蝶形運算中可由n1，n2.......nm來確定，其中，
ni(i＝1,2,3····m)分別代表待存取數據在第i級的蝶形運算中的排序。
其中，所述數據堆計算公式為
其中，bank為待存取數據在存儲器組中的堆，ai(i＝1,2,3·····m)為ni或ni的位倒序，modNmax為對Nmax進行取模運算。
其中，當FFT運算的總點數N總按照混合基算法分解為m級蝶形運算時，若m≥2，則至少有一個ai滿足
其中，為ni的位倒序，ni為待存取數據在第i級蝶形運算的排序。
其中，在計算所述待存取數據在所述堆中的地址，從而確定出所述待存取數據在FFT處理器的存儲器組中的地址的步驟中，當FFT處理器中的總點數N總小於等於Nmax時，所述待存取數據在所述堆中的存儲地址都相同，即，addr＝0；當FFT處理器中的總點數N總大於Nmax時， 所述待存取數據在所述堆中的存儲地址有兩種選擇。
其中，若在m級蝶形運算中有一個級為j級，j級滿足
1≤j＜m，
N0×N1×…×Nj≤Nmax，
N0×N1×…×Nj+1＞Nmax，
則所述待存取數據的地址方程為
addr＝Nm…Nj+2n′j+1+…+Nmnm-1+nm，
其中，addr為待存取數據的地址，m代表蝶形運算的級，Nm為第m級蝶形運算的點數，nm為待存取數據在第m級蝶形運算中的排序。
其中，n』j+1為nj+1的高位比特，＞＞為右移符號，為對向上取整。
其中，若在m級蝶形運算中有一個級為j級且j級滿足
1＜j≤m，
Nj…Nm≤Nmax，
Nj-1…Nm＞Nmax，
則所述待存取數據的地址方程為
addr＝Nj-1…N2n1+…+Nj-1nj-2+nj-1，
其中，N′j-1為Nj-1的高位比特，n′j-1為nj-1的高位比特。
其中，
其中，N′j-1為nj-1的高位比特，Nj-1為第j-1級蝶形運算的點數，＞＞ 為右移符號，Nmax為FFT處理器內的最大基，n』j-1為nj-1的高位比特，nj-1為待存取數據在第j-1級蝶形運算中的排序，Nm為第m級蝶形運算的點數。Nj為第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＝Nmax＝2L，
其中，P為FFT處理器的並行度，Nmax為FFT處理器內的最大基，L為2的冪指數。
在一個實施例中，將FFT運算的總點數N總按照混合基算法分解為m級蝶形運算，每一級蝶形運算的點數為N1,N2........Nm，待存取數據在每一級蝶形運算中可由n1，n2.......nm來確定，其中，
ni(i＝1,2,3·····m)分別代表待存取數據在第i級的蝶形運算中的排序。
為優化上述技術方案中的步驟S410，在上述技術方案的基礎上，該數據堆計算公式為
其中，bank為待存取數據在存儲器組中的堆，ai(i＝1,2,3·····m) 為ni或ni的位倒序，modNmax為對Nmax進行取模運算。
ni(i＝1，2，…m)的數據位寬為L比特，不滿L比特的通過高位補零達到L比特。
需要說明的是，位倒序是將數據按照比特位倒序輸出，結果的最高位是位倒序前的最低位，結果的次高位是位倒序的次低位，依次類推。
在一個實施例中，當FFT運算的總點數N總按照混合基算法分解為m級蝶形運算時，若m≥2，則至少有一個aj滿足
其中，ai(i＝1，2，3·····m)為ni的位倒序，ni為待存取數據在每一級蝶形運算中的排序。
在一個實施例中，在計算所述待存取數據在所述堆中的地址，從而確定出所述待存取數據在FFT處理器的存儲器組中的地址的步驟中，當FFT處理器中的總點數N總小於等於Nmax時，所述待存取數據在所述堆中的存儲地址都相同，即，addr＝0。
在一個具體的實施例中，當FFT運算的總點數N總小於16時，所述待存取數據在所述堆中的存儲地址都相同，即，addr＝0。
在另一個實施例中，在計算所述待存取數據在所述堆中的地址，從而確定出所述待存取數據在FFT處理器的存儲器組中的地址的步驟中，當FFT處理器中的總點數N總大於Nmax時，所述待存取數據在所述堆中的存儲地址有兩種選擇。
若在m級蝶形運算中有一個級為j級且j級滿足
1≤j＜m，
N0×N1×…×Nj≤Nmax，
N0×N1×…×Nj+1＞Nmax，
則所述待存取數據的地址方程為
addr＝Nm…Nj+2n′j+1+…+Nmnm-1+nm，
其中，m代表蝶形運算的級，addr為待存取數據的地址，Nm為第m級蝶形運算的點數，nm代表待存取數據在第m級蝶形運算中排在第nm個數。
在一個具體的實施例中，當FFT處理器中的總點數N總大於16時，若在m級蝶形運算中有一個級為j級且j級滿足
1≤j＜m，
N0…Nj≤16，
N0…Nj+1＞16，
且
其中，n』j+1為nj+1的高位比特，＞＞為右移符號，為對向上取整。
在第i個階段的運算中，控制單元需要每次從存儲器中存取K個數據，這K個數據組成一個數據塊。每個周期控制單元從存儲器中讀取一個數據塊到運算單元，並將運算單元得出的結果數據塊存入存儲器中。
如果，Ni＝16則K＝16。每個數據塊包含一個基16蝶形的數據。每個數據塊有ni＝(0，1，…，15)和相同的nk(K不等於i)。
如果Ni≠16，則每個數據塊中包含多個蝶形單元的待存取數據。相同的蝶形單元中有ni＝(0，1，…，Ni-1)，每個數據塊中不同的蝶形單元有不同的nj和相同的nk(K不等於i或j)。其中j的取值為
以216點FFT為例。假設
待存取數據的存儲公式為：
bank＝(n1+n2+n3+n4)mod16，
addr＝9n,2+3n3+n4，
其中，
，
在數據輸入階段，數據並行度為9，同時輸入的數據有相同的n1,n2和n3＝(0,1,2)，n4＝(0,1,2)。
在第一個階段的運算中，數據塊中相同的基8蝶形單元中有n1＝(0,1,…,7)，不同的基8單元有n2＝(0,1)或n2＝(2)，分別對應同時進行兩個或一個基8運算。
在第二個階段的運算中，數據塊中相同的基3蝶形單元中有n2＝(0,1,2)，不同的基3單元有n1＝(0,1,2,3)或n1＝(4,5,6,7)，對應同時進行四個基3運算。
在第三個階段的運算中，數據塊中相同的基3蝶形單元中有n3＝(0,1,2)，不同的基3單元有n1＝(0,1,2,3)或n1＝(4,5,6,7)，對應同時進行四個基3運算。
在第四個階段的運算中，數據塊中相同的基3蝶形單元中有n4＝(0,1,2)，不同的基3單元有n3＝(0,1,2)，對應同時進行三個基3運算。
在數據輸出階段，數據並行度為8，同時輸出的數據有相同的n2，n3，n4和n1＝(0，1，2，3，4，5，6，7)。
若在m級蝶形運算中有一個級為j級且j級滿足
1＜j≤m，
Nj…Nm≤Nmax，
Nj-1…Nm＞Nmax，
則所述待存取數據的地址方程為
addr＝N′j-1…N2n1+…+N′j-1nj-2+n′j-1，
其中，N′j-1為Nj-1的高位比特，n′j-1為nj-1的高位比特。
在一個實施例中，
其中，N′j-1為Nj-1的高位比特，Nj-1為第j-1級蝶形運算的點數，＞＞為右移符號，Nmax為FFT處理器內的總點數，n』j+1為nj-1的高位比特，nj-1為待存取數據在第j-1級蝶形運算中的排序，Nm為第m級蝶形運算的點數。Nj為第j級蝶形運算的點數。
綜上所述，該方法支持較大基的單蝶形單元運算和較小基的多蝶形單元運算，可以充分利用FFT處理器的硬體並行度，從而能夠避免在同時存取多個待存取數據時發生數據衝突的問題。
以上所述僅為本發明的較佳實施例而已，並不用以限制本發明，凡在本發明的精神和原則之內，所作的任何修改、等同替換、改進等，均應包含在本發明的保護範圍之內。