陳海燕，楊　超，劉　勝，劉　仲

(國防科學(xué)技術(shù)大學(xué)計算機學(xué)院，湖南長沙410073)

?

一種高效的面向基2 FFT算法的SIMD并行存儲結(jié)構(gòu)

陳海燕，楊超，劉勝，劉仲

(國防科學(xué)技術(shù)大學(xué)計算機學(xué)院，湖南長沙410073)

摘要:隨著SIMD(Single Instruction Multiple Data stream)結(jié)構(gòu)DSP(Digital Signal Processor)片上集成了越來越多的處理單元，并行訪存的靈活性及帶寬效率對實際運算性能的影響越來越大．本文詳細分析了一般SIMD結(jié)構(gòu)DSP中基2 FFT(Fast Fourier Transform)并行算法面臨的訪存問題，采用簡單的部分地址異或邏輯完成SIMD并行訪存地址轉(zhuǎn)換，實現(xiàn)了FFT運算的無沖突SIMD并行訪存;提出了幾種帶特殊混洗模式的向量訪存指令，可完全消除SIMD結(jié)構(gòu)下基2 FFT運算時需要的額外混洗指令操作．最后將其應(yīng)用于某16路SIMD數(shù)字信號處理器YHFT-Matrix2中向量存儲器VM的優(yōu)化設(shè)計．測試結(jié)果表明，采用該SIMD并行存儲結(jié)構(gòu)優(yōu)化的VM以增加18％的硬件開銷實現(xiàn)了FFT運算全流水無沖突并行訪存和100％并行訪存帶寬利用率;相比優(yōu)化前的設(shè)計，不同點數(shù)FFT運算可獲得1.32～2.66的加速比．

關(guān)鍵詞:快速傅里葉變換;單指令多數(shù)據(jù)流;低位交叉;并行存儲;訪問沖突;數(shù)據(jù)混洗

1　引言

無線通信、圖像匹配、視頻解碼等各類流媒體應(yīng)用需求的不斷增長對微處理器的運算能力提出了更高的要求，單指令多數(shù)據(jù)流(Single Instruction Multiple Data stream，SIMD)擴展結(jié)構(gòu)因其硬件控制結(jié)構(gòu)簡單、能開發(fā)大量的數(shù)據(jù)級并行，可在相對較低的功耗下實現(xiàn)高數(shù)據(jù)吞吐率計算能力等特性，已成為各類通用或嵌入式微處理器的重要擴展，如Intel的SSE1/SSE2/SSE3［1］、ARM的ARMv6架構(gòu)［2］、Michigan大學(xué)的AnySP［3］等．SIMD擴展能有效開發(fā)子字數(shù)據(jù)并行;在具有連續(xù)、對齊等規(guī)則向量訪存模式的應(yīng)用中具有很好的加速性能．但訪存模式較復(fù)雜情況下，其性能并未隨SIMD擴展可執(zhí)行資源的增長而線性增加［4］，其中額外的數(shù)據(jù)混洗置換操作造成的低SIMD訪存帶寬利用率是其中的一個重要原因．J．W．庫利和T．W．圖基提出的FFT［5］是無線通信等各類嵌入式應(yīng)用的核心算法，具有很高的數(shù)據(jù)密集性、并行性;如何在SIMD結(jié)構(gòu)DSP中實現(xiàn)高效的基于存儲結(jié)構(gòu)的FFT算法、獲得高吞吐率的實際運算性能，設(shè)計一個支持連續(xù)數(shù)據(jù)流訪問的無沖突、高帶寬利用率的SIMD并行訪存結(jié)構(gòu)成為關(guān)鍵．

傳統(tǒng)的FFT硬件加速器通常采用基于流水的單路徑延時反饋結(jié)構(gòu)［6］或基于存儲結(jié)構(gòu)［7］．前一結(jié)構(gòu)使用大量并行的蝶形運算單元實現(xiàn)多級蝶形運算的流水并行，針對特定點數(shù)、固定基FFT算法具有很高的數(shù)據(jù)吞吐率，但要耗費大量硬件資源，缺乏靈活性，不適合SIMD結(jié)構(gòu)DSP;后一種結(jié)構(gòu)針對特定一套蝶形運算單元，基于同址存儲機制，能有效控制面積和功耗，但難以獲得較高的FFT加速性能，但對其進行SIMD擴展和并行訪存結(jié)構(gòu)優(yōu)化，SIMD結(jié)構(gòu)DSP可望在有效的功耗預(yù)算下獲得較高的FFT運算性能．

針對基于存儲結(jié)構(gòu)的FFT實現(xiàn)，人們對如何為蝶形運算提供連續(xù)的并行數(shù)據(jù)已進行了大量研究．文獻［8，9］都使用了多個單端口RAM實現(xiàn)特定蝶形運算單元的無沖突并行訪存;文獻［10］基于同址存儲機制實現(xiàn)了一種連續(xù)數(shù)據(jù)流混合基FFT無沖突訪存，但地址轉(zhuǎn)換使用了取模運算，邏輯過于復(fù)雜;文獻［11］使用簡單的地址異或邏輯就實現(xiàn)了基2 FFT算法的無沖突并行訪存．這些存儲結(jié)構(gòu)都專注于一兩個特定基蝶形運算單元，都未說明SIMD結(jié)構(gòu)下如何實現(xiàn)無沖突地址轉(zhuǎn)換以及多個蝶形運算單元之間的數(shù)據(jù)混洗．而對于SIMD結(jié)構(gòu)研究中，支持SIMD寬度非對齊訪問可加速H．264/AVC、FIR等算法［12］，但不會提高FFT向量化訪存效率．文獻［13］通過設(shè)計質(zhì)數(shù)個存儲體的方式避免SIMD并行訪存沖突，但地址轉(zhuǎn)換邏輯復(fù)雜，且存在一定未映射的存儲空間浪費．文獻［14，15］針對FFT或特定應(yīng)用算法定制專用混洗操作指令，以提高相應(yīng)算法的計算性能，避免全交叉開關(guān)實現(xiàn)任意模式數(shù)據(jù)混洗造成的過高功耗和面積開銷;但并行訪存數(shù)據(jù)仍未直接用于SIMD運算單元的計算，需要進行兩個向量寄存器間額外的混洗指令操作，使SIMD并行訪存的數(shù)據(jù)帶寬直接利用率只有50％;增加了代碼量和計算周期，還要占用較多的向量寄存器資源．隨著SIMD寬度和數(shù)據(jù)帶寬的增大，不斷增加的向量寄存器端口數(shù)和交叉開關(guān)使硬件面積急劇增長，造成后端物理設(shè)計難以實現(xiàn)等問題．

本文分析了一般多寬度SIMD結(jié)構(gòu)DSP實現(xiàn)FFT算法時面臨的并行訪存沖突和數(shù)據(jù)跨步混洗問題，在文獻［11］的基礎(chǔ)上進一步提出了用于FFT向量化加速的SIMD并行存儲結(jié)構(gòu)，采用乒乓存儲結(jié)構(gòu)和地址異或邏輯相結(jié)合的方式實現(xiàn)了低開銷、低延時的SIMD并行訪存地址轉(zhuǎn)換．同時提出了帶特殊混洗模式的SIMD訪存指令，并將其應(yīng)用于某16路SIMD數(shù)字信號處理器YHFT-Matrix2的向量存儲器VM的優(yōu)化設(shè)計，不僅實現(xiàn)了SIMD結(jié)構(gòu)中基2 FFT向量化運算的無沖突訪存，而且完全消除了FFT運算所需的向量寄存器間的混洗指令操作，使得FFT運算的SIMD訪存數(shù)據(jù)帶寬利用率達到100％．

2　SIMD結(jié)構(gòu)DSP中FFT向量化算法面臨的問題

2.1SIMD并行存儲結(jié)構(gòu)

SIMD結(jié)構(gòu)DSP集成了M路同構(gòu)的運算單元(PE0～PEM－1)和多組向量寄存器，M路運算單元按SIMD方式操作．為了尋址計算簡單快捷，一般選擇M =2m，m為大于0的整數(shù)，并配置同樣路數(shù)的共享存儲陣列SM0～SMM－1，如圖1所示．SM0～SMM－1按低位交叉全局統(tǒng)一編址以支持對應(yīng)的PE運算訪存．為充分開發(fā)PE的計算能力，共享存儲陣列通常支持兩條SIMD并行訪存指令，能一拍為每個PE的運算提供兩個操作數(shù)．由于容量相同的雙端口存儲體的面積和訪問延遲比單端口存儲體通常大30％以上，受限于芯片的面積和功耗，片上大容量存儲器通常選擇多個單端口靜態(tài)隨機存儲體(SRAM)組織存儲器;每個SM又按Q個單端口SRAM存儲體低位交叉組織以提供并行訪存帶寬，一般Q = 2q，q為大于0的整數(shù)．這樣能以較低的地址產(chǎn)生硬件開銷為PE提供并行訪存帶寬．SIMD結(jié)構(gòu)的存儲陣列執(zhí)行一條SIMD向量訪存指令時，通常提供一組跨步為1的向量訪存數(shù)據(jù)，為M個PE提供訪存地址A起始的M個連續(xù)數(shù)據(jù)訪存;而PE對存儲陣列中數(shù)據(jù)的非連續(xù)或非對齊訪問需要利用專門的指令通過混洗對齊網(wǎng)絡(luò)在向量寄存器上實現(xiàn)數(shù)據(jù)對齊．

2.2面向FFT算法的SIMD訪存模式

根據(jù)基2 FFT算法原理［5］，長度為N(假設(shè)N = 2n，n為正整數(shù))的序列X的FFT需要n級蝶形運算;每級蝶形運算又需要進行N/2次基本蝶形運算．在上述M 路SIMD結(jié)構(gòu)DSP實現(xiàn)該算法時，M個PE一次可并行完成M個基本蝶形運算，那么每級蝶形運算中，每個PE要進行N/(2M)次基本蝶形運算;在不考慮系數(shù)情況下，需要N/(2M)次雙操作數(shù)SIMD加載和N/(2M)次雙操作數(shù)(即中間運算結(jié)果) SIMD存儲操作．由于FFT運算中每個源操作數(shù)和中間結(jié)果只會在一個基本蝶形運算中使用一次，為提高存儲器容量的使用效率，每級運算的中間結(jié)果采用“同址存儲”，即基本蝶形運算的兩數(shù)之和、兩數(shù)之差分別存回第一、第二個操作數(shù)的原位置．因此SIMD結(jié)構(gòu)中每個PE實現(xiàn)某級蝶形運算中的一個基本蝶形運算時，一個SM每次為對應(yīng)PE提供的兩個操作數(shù)的訪存地址A1、A2存在如下關(guān)系:

其中n為N點基2頻域抽取FFT運算需要的蝶形運算總級數(shù)，n = log2N; r為當前基本蝶形運算所處的級數(shù)，r =1，2，3，…，n．

將N點基2FFT算法在上述M路SIMD結(jié)構(gòu)DSP實現(xiàn)時，一個PE進行某級蝶形運算需要的雙操作數(shù)訪存地址存在以下幾種情況:

(1)當|A2－A1|＞= M，即2n－r＞=2m時，則在當前蝶形運算級數(shù)r＜= n－m的蝶形運算中，M路SIMD結(jié)構(gòu)中每個PE進行基本蝶形運算的兩個操作數(shù)均來自同一SM;如果每個SM由Q = 2q個單端口存儲體構(gòu)成，根據(jù)兩整數(shù)取模同余條件［16］，可得到如下結(jié)論:

(a)當|A2－A1|能整除M* Q，即當r＜= n－m－q時，A1、A2對2m + q取模同余，即:

此時，地址A1、A2訪問同一個SM中的同一存儲體，即M路SIMD結(jié)構(gòu)中每個PE進行基本蝶形運算的兩個操作數(shù)均來自同一SM中的同一個存儲體;每次基本蝶形運算的并行訪存都存在沖突．

(b)當n－m－q＜r＜= n－m時，每個PE進行基本蝶形運的兩個操作數(shù)來自同一SM中的不同存儲體，不存在訪存沖突．通常，為了不浪費訪存帶寬，Q與所支持的并行訪存指令數(shù)相等．

(c)當Q取大于1的奇數(shù)時，M* Q不是2的正整數(shù)冪，|A2－A1| modM* Q就不等于0，前(n－m)級蝶形運算的所有并行訪存均不存在訪問沖突．

因此，如果M路SIMD結(jié)構(gòu)中每個SM按2q個SRAM存儲體低位交叉組織存儲器來提供雙操作數(shù)訪存，前(n－m－q)級中的基本蝶形運算存在大量的SIMD并行訪存沖突;將顯著降低SIMD并行訪存帶寬利用率，影響實際計算性能．如果按奇數(shù)個體組織存儲體則消除了此沖突，但該方式地址計算邏輯需要實現(xiàn)訪存地址整除求余的運算，其硬件實現(xiàn)復(fù)雜度遠遠大于Q等于2q時的移位邏輯．對于M路SIMD結(jié)構(gòu)，兩條SIMD訪存指令就需要2M個這樣的尋址單元;而且對于雙訪存操作，奇數(shù)個存儲體還帶來了冗余的訪存帶寬，這些都會造成較大的面積和延時開銷．

(2)當|A2－A1|＜M，即r＞n－m時，在最后的m級蝶形運算中，由于每個PE進行基本蝶形運算的兩個操作數(shù)的地址間距|A2－A1|小于M，每個PE進行一次基本蝶形運算的兩個操作數(shù)將來自不同的SM，此時又需要對各PE運算使用的向量寄存器中的數(shù)據(jù)實現(xiàn)m種模式的混洗指令操作，這也會降低SIMD訪存帶寬的利用率．

因此，在基于上述單端口SRAM多體低位交叉方式實現(xiàn)并支持SIMD雙訪問的一般SIMD并行存儲結(jié)構(gòu)中，F(xiàn)FT并行運算將存在大量的向量訪存沖突和額外的數(shù)據(jù)混洗指令操作，降低了SIMD訪存數(shù)據(jù)帶寬利用率，導(dǎo)致M路SIMD功能單元無法進行全流水連續(xù)的運算，將顯著降低FFT的實際運算性能．根據(jù)上述分析，本文下面提出了一種支持FFT算法無沖突連續(xù)訪存和特殊數(shù)據(jù)訪存模式的低硬件開銷的SIMD并行訪存結(jié)構(gòu)．

3　面向FFT算法加速的SIMD并行存儲結(jié)構(gòu)

3.1快速地址變換

文獻［11］提出了一種針對序列長度和并行存儲模塊數(shù)均為2的正整數(shù)冪的基2 FFT算法的無沖突訪存尋址方法，使用地址按位異或邏輯和地址旋轉(zhuǎn)單元結(jié)合的訪存地址產(chǎn)生器，能支持不同序列長度的FFT無沖突并行訪存．本文在其基礎(chǔ)上，針對上述M路SIMD并行存儲結(jié)構(gòu)設(shè)計了一種低硬件開銷、適用于序列長度為2n的FFT運算無沖突訪存的地址變換方法．

對于上述M路SIMD并行存儲陣列，假設(shè)基2 FFT算法SIMD訪存的數(shù)據(jù)字地址為n位，字粒度為w位字節(jié)，則SIMD訪存數(shù)據(jù)的字節(jié)地址A可分為圖2所示的幾個域: SM的地址R3，為log2M = m位;每個SM中SRAM的體地址R2，為log2Q = q位;數(shù)據(jù)在某個SM中SRAM字節(jié)地址，由R1、R4構(gòu)成．

對于序列長度N =2n的頻域抽取基2 FFT運算，在前r級(r =1，2，…，n－m)的蝶形運算中，M路SIMD結(jié)構(gòu)中每個PE進行基本蝶形運算的兩個操作數(shù)均來自同一SM;只需對SM中的SRAM體地址R2進行轉(zhuǎn)換，根據(jù)文獻［11］，可得到以下地址轉(zhuǎn)換方法:

(1)將地址A［n + w－1: w + m］從低到高位按q位分組，構(gòu)成一組向量F0，F(xiàn)1，…，F(xiàn)p－1，將最后不能湊成q位的高e位看做向量L，其中p = (n－m) /q向下取整，e = (n－m) mod q，若e =0，則無向量L．

(2)若e! =0，則設(shè)置q位向量G，將(n－m)位地址的低(q－gcd(q，e) )位作為G的低位，gcd為求最大公約數(shù)運算;高位由0補齊;再將向量G向左循環(huán)移動g = (n－m－q) mod q位，得到向量O．

(3)如果e! =0，將所有向量Fi(其中i =0，1，…，p －1)和向量O、向量L按位異或;如果e = 0，則只將所有向量Fi按位異或，即可生成新的R2地址．

根據(jù)上面的結(jié)論，如果e =0，則無需產(chǎn)生向量O和L的邏輯，即無需地址旋轉(zhuǎn)單元，地址轉(zhuǎn)換邏輯只增加了p個q位向量的按位異或邏輯．對于支持雙訪問的SIMD并行存儲結(jié)構(gòu)，單個SM中滿足雙訪問帶寬的SRAM體至少為Q = 2q= 2，即q = 1，新的R2地址= ^A ［n + w－1: w + m］，這里“^”表示對向量進行按位異或的邏輯運算符．

3.2支持數(shù)據(jù)混洗的SIMD并行訪存

頻域抽取基2 FFT運算的最后m級蝶形運算中，由于每個PE進行基本蝶形運算的兩個操作數(shù)的地址跨步|A2－A1 |小于M，一次基本蝶形運算的兩個操作數(shù)將來自不同的SM，需要實現(xiàn)log2M = m種PE間數(shù)據(jù)混洗和對齊．如果用SIMD并行訪存指令實現(xiàn)這幾類數(shù)據(jù)混洗模式訪問，就可以消除額外的混洗指令操作，減少向量寄存器訪問端口的壓力，提高SIMD訪存的效率，并減少FFT并行運算的代碼密度．

圖3示例了SIMD寬度M =16時，使用兩條并行的特殊SIMD訪存指令VLS0/VLS1的混洗訪存，實現(xiàn)了基2 FFT中4級蝶形運算需要的SIMD并行訪問數(shù)據(jù)跨步為8、4、2、1共四種混洗模式．通過在正常的SIMD并行訪存流水線中增加支持這四種模式數(shù)據(jù)交換與對齊單元即可實現(xiàn)．

4　應(yīng)用與測評

4.1YHFT-Matrix2的總體結(jié)構(gòu)

本文用上述方法對一款自主研發(fā)的32位數(shù)字信號處理器YHFT-Matrix2的向量存儲器VM進行設(shè)計優(yōu)化和測評．YHFT-Matrix2采用VLIW + SIMD技術(shù)和標量單元(SU)、向量單元(VU)并行結(jié)構(gòu)，以充分開發(fā)指令級和數(shù)據(jù)級并行．標、向量單元共享取指單元和指令派發(fā)部件，實現(xiàn)標量、向量數(shù)據(jù)的并行處理，其結(jié)構(gòu)框圖如圖4.其向量單元VU包含16路SIMD結(jié)構(gòu)的向量運算單元VPU和程序員可見的片上大容量向量存儲器VM．VPU內(nèi)集成16個同構(gòu)的PE和32深度的向量寄存器文件(VRF)，每個PE有1個乘法、1個ALU和1個支持混洗模式可編程的全交叉結(jié)構(gòu)混洗單元［17］，可并行執(zhí)行三條SIMD向量運算指令．VM為16個PE運算提供向量數(shù)據(jù)訪存，容量為1MB，由16個向量存儲體(VB0～VB15)按地址低位交叉組織，且采用支持SIMD非對齊并行訪存結(jié)構(gòu)［18］．VM可同時支持兩條SIMD訪存指令和DMA讀/寫三請求并行訪問，一拍可為VPU中的每個PE提供兩個32位字操作數(shù)訪存．為支持多請求并行訪問，VM采用了高、低位地址統(tǒng)一編址，即按低位地址方式組織16個VB，每個VB采用了4組單端口SRAM，將4* 16 =64個SRAM按高、低位地址交叉方式組織，低位交叉滿足SIMD并行訪存帶寬需求;而按地址最高位交叉構(gòu)成的乒乓存儲結(jié)構(gòu)又可減少SIMD訪存和DMA讀/寫并行訪問的沖突，隱藏運算數(shù)據(jù)傳輸延時．

4.2對YHFT-Matrix2的并行訪存優(yōu)化

(1) SIMD訪存的地址變換

VM地址空間為1MB，其字節(jié)地址為A［19: 0］，A［19］尋址每個VB內(nèi)按高位地址組織的上或下一半地址空間，和A［18: 7］一起構(gòu)成單個VB中的每個SRAM存儲體內(nèi)的字地址; A［6］用來尋址每個VB內(nèi)上或下半地址空間中的某個SRAM存儲體，A［5: 2］表示16個VB的地址索引．由于VB中上或下地址空間分別由2 個SRAM體按低位交叉組織;根據(jù)上文，q = 1，e = 0，只需要對尋址的上或下地址空間的兩個SRAM的體地址A［6］進行轉(zhuǎn)換得到A'［6］，即可滿足向量訪存指令無沖突SIMD并行訪存的需求，即:

以256點為例，假設(shè)其原存儲字地址為VM的255 ～0;進行地址變換優(yōu)化后，根據(jù)式(3)，256個數(shù)據(jù)將如圖5所示地址存儲．因此在基2 FFT的前4級蝶形運算中，每個PE基本蝶形運算的雙操作數(shù)都可實現(xiàn)無沖突并行訪存．同時對于基4算法，所需操作數(shù)也可以分兩次無沖突訪存實現(xiàn)．

(2)支持FFT算法混洗的SIMD并行訪存

對于16路SIMD結(jié)構(gòu)，在頻域基2 FFT蝶形運算的最后4級或者基4蝶形運算的最后兩級需要進行SIMD雙訪存數(shù)據(jù)混洗操作．VM需要設(shè)計如圖3所示的4種帶特殊混洗模式的向量訪存指令，在VM原來向量訪存流水線中增加了訪存前、后四種模式的數(shù)據(jù)混洗對齊邏輯，如圖6所示，通過SIMD并行訪存指令，直接為每個PE提供基本蝶形運算所需的兩個操作數(shù)．

4.3性能分析

(1)面積代價

對VM進行上述優(yōu)化，用部分地址位異或邏輯改寫地址A［6］，增加訪存前、后混洗單元，然后基于某廠家65nm工藝和1.3ns的時鐘周期對優(yōu)化后的VM進行邏輯綜合，在相同綜合約束下，優(yōu)化前后的VM均滿足時序要求．優(yōu)化前后的綜合面積如表1所示．結(jié)果表明，面向FFT的并行訪存優(yōu)化結(jié)構(gòu)比原來VM的訪存控制邏輯的面積增加18％，但由于該方法不需要可編程混洗單元，VM與混洗單元控制邏輯的面積和減少了32％．

(2)單精度浮點基2 FFT的運算性能

基于YHFT-Matrix2指令集體系結(jié)構(gòu)和軟件流水編程技術(shù)，編寫了128～4096點浮點單精度FFT匯編測試程序，對采用上述SIMD并行訪存優(yōu)化設(shè)計前后的VM進行性能測試，得到表2所示測試結(jié)果．

從表2中可以看出，采用簡單的地址變換后完全消除了基2 FFT SIMD并行訪存沖突引起的訪存停頓;支持帶數(shù)據(jù)混洗SIMD訪存操作，則消除了SIMD結(jié)構(gòu)中FFT蝶形運算需要的額外混洗指令，減少了軟件流水的最小迭代間隔，使實際的SIMD向量訪存帶寬利用率達到100％．使用優(yōu)化后的VM，YHFT-Matrix2獲得了1.32到2.66的加速比，特別是點數(shù)大于512點后，由于軟件循環(huán)流水性能的提高，取到了更好的加速效果．

表1　YHF-Matrix2 VM優(yōu)化前后面積對比(均不含存儲體面積)

表2　VM優(yōu)化前后浮點單精度FFT性能比較

5　結(jié)論

本文針對SIMD結(jié)構(gòu)數(shù)字信號處理器中基2 FFT算法的訪存模式存在的問題，提出了一種支持FFT算法無沖突并行訪存和數(shù)據(jù)混洗的SIMD并行存儲結(jié)構(gòu)，能以較低的硬件開銷實現(xiàn)FFT算法無沖突SIMD方式并行訪存，消除了SIMD結(jié)構(gòu)中向量寄存器間的混洗操作，使SIMD訪存帶寬利用率達到100％，有效提高了SIMD結(jié)構(gòu)DSP的FFT運算性能，該方法應(yīng)用于基4 FFT算法同樣有效．

參考文獻

［1］Intel Corporation．Intel 64 and IA-32 Architectures Software De-veloper Manuals，Volume1: Basic Architecture［OL］．http: / / www．intel．com/products/processor/manuals，2015-01-05.

［2］ARM Corporation．The Architecture for the Digital World ［OL］．http: / /www．a(chǎn)rm．com /zh/products/processors/ technologies/dsp-simd．php，2015-01-05.

［3］Woh M，Seo S，Mahlke S，et al．AnySP: anytime anywhere anyway signal processing［A］．Proceedings of the 36th Annual International Symposium on Computer Architecture ［C］．Austin，Texas，USA: ACM，2009.128－139.

［4］Deepu Talla，Lizy Kurian John，Doug Burger．Bottlenecks in multimedia processing with SIMD style extensions and architectural enhancements［J］．IEEE Transactions on Computers，2003，52(8) : 1015－1030.

［5］James W Cooley，John W Tukey．An algorithm for the machine calculation of complex Fourier series［J］．Mathematics of Computation，1965，19(90) : 297－301.

［6］Yun-Nan Chang，Keshal K Parhi．An efficient pipelined FFT architecture［J］．IEEE Transactions on Circuits and Systems-II: Analog and Digital Signal Processing，2003，50 (6) : 322－325.

［7］B M Baas．A low-power，high-performance，1024-point FFT processor［J］．IEEE Journal of Solid-State Circuits，1999，34(3) : 380－387.

［8］Stephen Richardson，Ofer Shacham，et al．An area-efficient minimum-time FFT schedule using single-ported memory ［A］．Proceedings of 2013 IFIP/IEEE 21st International Conference on VLSI-SoC［C］．Istanbul，Turkey: IEEE，2013.39－44.

［9］Ji-yang Yu，Yang Li．An efficient conflict-free parallel memory access scheme for dual-butterfly constant geometry radix-2 FFT processor［A］．ICSP2008 Proceedings ［C］．Beijing，China: IEEE，2008.458－461.

［10］Chen-Fong Hsiao，Yuan Chen，Chen-Yi Lee．A Generalized mixed-radix algorithm for memory-based FFT processors［J］．IEEE Transactions on Circuits and Systems-II: Express Briefs，2010，57(1) : 26－30.

［11］Jarmo H Takala，Tuomas S Jawinen，Harri T Sorokin．Conflict-free parallel memory access scheme for FFT processors［A］．ISCAS ' 03［C］．Thailand: IEEE，2003.IV524－527.

［12］Alvarez M，Salami E，Ramirez A，et al．Performance impact of unaligned memory operations in SIMD extensions for video codec applications［A］．IEEE International Symposium on Performance Analysis of Systems＆Software ［C］．California，USA: IEEE，2007.62－71.

［13］Hoseok Chang，Junho Cho，Wonyong Sung．Performance evaluation of a SIMD architecture with a multi-bank vector memory unit［A］．2006 IEEE Workshop on Signal Processing Systems Design and Implementation (SIPS' 06)［C］．Banff，Alta: IEEE，2006.71－76.

［14］Kai Zhang，Shuming Chen，Sheng Liu，et al．Accelerating the data shuffle operations for FFT algorithms on SIMD DSPs optimizing data permutations for SIMD devices［A］．Proceedings of International Conference on ASIC (ASICON 2011)［C］．Xiamen，China: IEEE，2011.683－686.

［15］Praveen Raghavan，Satyakiran Munaga，et al．A customized cross-bar for data-shuffling in domain specific SIMD processors［J］．Lecture Notes in Computer Science，2007，4415: 57－68.

［16］張彥仲，沈乃漢．快速傅里葉變換及沃爾什變換［M］．北京:航空工業(yè)出版社，1989.97－98.

［17］萬江華，劉勝，等．具有高效混洗模式存儲器的可編程混洗單元［J］．國防科技大學(xué)學(xué)報，2011，33(6) :31－35.Wan Jianghua，Liu Sheng，et al．A programmable shuffle unit with the efficient shuffle pattern memory［J］．Journal of National University of Defense Technology，2011，33 (6) : 31－35.(in Chinese)

［18］陳海燕，劉勝，劉仲，陳書明．面向SDR應(yīng)用的向量訪存控制器［J］．國防科技大學(xué)學(xué)報，2012，34(3) : 98－102.Chen Haiyan，Liu Sheng，Liu Zhong，Chen Shuming．The design and optimization of the vector memory applying for SDR［J］．Journal of National University of Defense Technology，2012，34(3) : 98－102.(in Chinese)

陳海燕(通信作者)女，1967年生，四川南充人．1989年、1992年分別獲得國防科技大學(xué)工學(xué)學(xué)士和碩士學(xué)位．現(xiàn)為國防科技大學(xué)計算機學(xué)院研究員、碩士生導(dǎo)師．研究方向為微處理器體系結(jié)構(gòu)、VLSI設(shè)計．

E-mail: hychen608@163.com

楊超男，1990年生于河南南陽．2013年畢業(yè)于國防科技大學(xué)計算機學(xué)院網(wǎng)絡(luò)工程專業(yè)，現(xiàn)為國防科技大學(xué)計算機學(xué)院碩士研究生，研究方向為微處理器設(shè)計．

E-mail: 896331663@ qq．com

劉勝男，1984年生于河南南陽，現(xiàn)為國防科學(xué)技術(shù)大學(xué)計算機學(xué)院助理研究員，研究方向為高性能微處理器設(shè)計．

E-mail: liusheng83@ nudt．edu．cn

劉仲男，1971年生于湖南邵東．2005年獲得國防科學(xué)技術(shù)大學(xué)計算機科學(xué)與技術(shù)專業(yè)博士學(xué)位，現(xiàn)為國防科學(xué)技術(shù)大學(xué)計算機學(xué)院研究員，主要從事芯片驗證與性能評測、嵌入式應(yīng)用與算法優(yōu)化等方面的研究工作．

E-mail: zhongliu@ nudt．edu．cn

An Efficient SIMD Parallel Memory Structure for Radix-2 FFT Computation

CHEN Hai-yan，YANG Chao，LIU Sheng，LIU Zhong
(College of Computer，National University of Defense Technology，Changsha，Hunan 410073，China)

Abstract:As more and more execution units are integrated in the digital signal processor(DSP) with single instruction multiple data stream(SIMD) extension，the flexibility and bandwidth efficiency of parallel memory access have significant effects on its whole practical performance．Based on detailed analysis of the memory access problems for radix-2 fast Fourier transform (FFT) algorithm in general SIMD DSP，this paper used parts of the address bit XOR logic to realize memory access address translation，and achieved conflict-free parallel SIMD memory accesses for FFT computation．Then several memory access instructions with special shuffle modes were brought forward，which could completely eliminate extra shuffling instruction operations of radix-2 FFT algorithm in the SIMD architecture．Finally，the vector memory(VM) in 16-way SIMD DSP YHFT-Matrix2 was optimized by above methods．The test results show that the optimized VM can realize fully pipelined conflict-free memory accesses and 100％ parallel memory access bandwidth utilization with increase of 18％ area overheads．Compared with the design before optimization，the performance of different points radix-2 FFT can achieve speedup ranging from 1.32 to 2.66.

Key words:FFT; SIMD; low-order interleave; parallel memory; access conflict; data shuffle

作者簡介

基金項目:國家自然科學(xué)基金(No．61472432)

收稿日期:2015-03-30;修回日期: 2015-05-28;責(zé)任編輯:覃懷銀

DOI:電子學(xué)報URL: http: / /www．ejournal．org．cn10．3969/j．issn．0372-2112．2016．02．001

中圖分類號:TP303

文獻標識碼:A

文章編號:0372-2112 (2016) 02-0241-06