雷元武　陳小文　彭元喜

(國防科學技術大學計算機學院　長沙　410073)

?

DSP芯片中的高能效FFT加速器

雷元武陳小文彭元喜

(國防科學技術大學計算機學院長沙410073)

(leiyuanwu@163.com)

摘要快速傅里葉變換(fast Fourier transform, FFT)是數(shù)字信號處理(digital signal processing, DSP)領域中最耗時的核心算法，該算法的計算性能和計算效率將影響整個應用的執(zhí)行效率.因此，在DSP芯片上設計實現(xiàn)了一個基于矩陣轉置操作的高能效可變長度FFT加速器，采用多種并行策略開發(fā)批量小規(guī)模FFT算法與大規(guī)模Cooley-Tukey FFT算法中指令級和任務級并行.設計“乒乓”多體數(shù)據(jù)存儲器，重疊數(shù)據(jù)搬移和FFT計算之間的開銷，提高FFT加速器計算效率.并基于此存儲器，提出基于基本塊的快速矩陣轉置算法，從而避免對數(shù)據(jù)矩陣的列訪問；提出混合旋轉因子產生策略，結合查表和基于CORDIC算法在線計算方式，最大限度降低旋轉因子產生的硬件開銷.實驗結果表明:FFT加速器原型的峰值能效為146 GFLOPs?W，相比Intel Xeon CPU上的多線程FFTW實現(xiàn)，取得2個數(shù)量級的能效提升.

關鍵詞快速傅里葉變換；加速器；高能效；矩陣轉置；數(shù)字信號處理

隨著半導體技術的發(fā)展，單芯片晶體管數(shù)量和性能持續(xù)以摩爾定律方式增加，當前單芯片已經能夠集成幾十億個晶體管，計算能力達到TFLOPS量級.然而，由于晶體管的物理結構和特征沒有發(fā)生本質變化，單個晶體管的能耗并未隨工藝進步而大幅降低，使得功耗成為處理器性能提升的瓶頸.Hadi等人認為：由于能耗的限制，未來芯片上的功能單元不可能同時持續(xù)處于峰值運行狀態(tài)，這導致實際運行時往往無法將芯片所有的性能完全發(fā)揮出來，即所謂“暗場硅晶”現(xiàn)象[1].

針對特定應用定制加速器是提升計算效率、緩解功耗問題的一種有效的方法.針對特定應用設計相應的硬件結構，使得計算和存儲資源最佳匹配應用的并行特征和存儲模式獲得最高能效.目前，多種新型高效能芯片采用通用處理核和加速計算核相結合的異構多核體系結構，如OpensPlySER[2],QuicklA[3].

快速傅里葉變換(fast Fourier transform, FFT)是數(shù)字信號處理(digital signal processing, DSP)領域中的基本操作，廣泛應用于聲納、圖像、雷達、電信和無線信號處理等領域.通常，在這些應用中，F(xiàn)FT算法的計算開銷所占比重較大.FFT算法的計算效率將直接影響整個應用的執(zhí)行效率.然而，在不同的平臺上，F(xiàn)FT算法的執(zhí)行效率相差很大.在通用處理平臺，如CPU,GPU等處理芯片[4-5]，F(xiàn)FT算法的執(zhí)行效率較低，達不到峰值性能的10%[4].這是因為FFT計算過程中需要以2的冪次方為步長交叉訪問數(shù)據(jù)，這與通用處理器的組相聯(lián)Cache、組相聯(lián)地址映射和DDR存儲器的突發(fā)訪問機制不匹配，從而無法充分發(fā)揮芯片的計算性能，尤其對于大規(guī)模FFT計算，不能將整行數(shù)據(jù)存儲到Cache或者片上存儲器中，需要頻繁訪問片外存儲器，存儲帶寬利用率較低.

針對FFT算法的計算特征和存儲特征定制的FFT加速器能夠獲得高性能、低功耗和高能效.Chung等人預測：相比GPU和CPU，定制FFT加速器能夠獲得100倍和1 000倍的性能加速、2個數(shù)量級的效能提升[6].學者們提出了不同流水和并行FFT體系結構，如陣列并行結構[7-8]、單通路延時轉換結構(SDC)[9]、單通路延時反饋結構(SDF)[10]、多通路延時轉換結構(MDC)[11]、多通路延時反饋結構(MDF)[12]等.但是上述FFT處理器都是針對通信應用設計的，如OFDM,LTE和WiMax等，支持的最大規(guī)模通常小于2048點，這很難滿足雷達等大規(guī)模FFT應用.

目前，部分DSP芯片內部集成了FFT加速器，如TI C55X系列DSP芯片包含一個緊耦合FFT加速器(稱為HWAFFT)[13]，通過使用加速器指令實現(xiàn)HWAFFT與DSP內核協(xié)同工作.然而，HWAFFT僅支持32位定點格式、規(guī)模不超過1024點的FFT計算，這限制了HWAFFT的應用范圍.

對于不同DSP應用，F(xiàn)FT運算規(guī)模差別較大，例如在數(shù)字和無線電通信應用中，F(xiàn)FT規(guī)模通常為K量級(103)，而對于雷達、聲納等應用，F(xiàn)FT規(guī)模能夠可達兆(M)量級(106).因此，需要為可變規(guī)模FFT算法提供高性能和高能效支持，以滿足實時信號處理領域中不同應用需求.我們先前工作[14]在DSP芯片上設計了一個支持可變規(guī)模無轉置操作的FFT加速器，利用DSP芯片上SRAM存儲器的隨機訪問特性來避免大規(guī)模Cooley-Tukey FFT計算過程中對DDR進行矩陣列訪問[15].然而，該方法需要增加2次SRAM和DDR之間的搬移步驟(文獻[14]圖1(B)中的Step1和Step4或圖1(C)中的Step1和Step5)，同時，DSP芯片上的數(shù)據(jù)網(wǎng)絡寬度通常為128 b(或256 b)，在文獻[14] 圖1(B)和圖1(C)中的Step2-1和Step2-2矩陣列讀和列寫過程中，每個時鐘周期同時讀出2列(或4列)數(shù)據(jù)，導致數(shù)據(jù)讀寫和FFT計算無法重疊，從而降低FFT計算效率.

本文在先前工作[14]的基礎上進行優(yōu)化，主要貢獻如下：

1) 設計了“乒乓”多體數(shù)據(jù)存儲器(multi-bank data memory, MBDM)，重疊數(shù)據(jù)搬移和FFT計算之間的開銷，提高FFT加速器計算效率.

2) 提出基于基本塊的快速矩陣轉置算法，復用MBDM，避免對數(shù)據(jù)矩陣的列訪問.

3) 在DSP芯片上設計實現(xiàn)了基于此快速矩陣轉置算法的可變規(guī)模FFT加速器,增加3次快速矩陣轉置來避免文獻[14]中的存儲問題.

4) 提出混合旋轉因子產生策略，結合查表和基于CORDIC算法在線計算方式，最大限度降低旋轉因子產生的硬件開銷.

1Cooley-Tukey FFT算法

FFT加速器中，至少需要將一行數(shù)據(jù)存儲到加速器內部數(shù)據(jù)存儲器中，因此，F(xiàn)FT加速器所需存儲容量隨FFT規(guī)模的增大而線性增加.存儲器容量將成為大規(guī)模FFT加速器設計的主要限制.

本文采用Cooley-Tukey FFT算法來實現(xiàn)大規(guī)模FFT.該算法采用分而治之的思想，使用規(guī)模較小的二維FFT模擬實現(xiàn)規(guī)模較大的一維FFT.對于NF=N1×N2點的FFT可以用N2個N1點和N1個N2點的FFT算法來實現(xiàn)，迭代公式為

X[k1N2+k2]=

其中，0≤k1

從上述公式和圖1(a)可以看出，將初始數(shù)據(jù)從邏輯上看成按行存儲為N1×N2的矩陣，Cooley-Tukey FFT算法可以分為3個步驟：

步驟1. 列方向FFT計算.進行N2次的N1點FFT運算，即執(zhí)行N2次公式：

步驟3. 行方向FFT計算.在步驟2的基礎上進行N1次N2點FFT運算，即執(zhí)行N1次公式:

Fig. 1　The access order of Cooley-Tukey FFT algorithm.圖1　Cooley-Tukey FFT算法中數(shù)據(jù)訪問順序

2FFT加速器的實現(xiàn)

2.1總體結構

如圖2所示，全定制并行FFT加速器掛載于DSP芯片上的高速數(shù)據(jù)網(wǎng)絡中、是數(shù)據(jù)網(wǎng)絡中的一個主機，通過AXI主機數(shù)據(jù)接口訪問到DSP芯片內部存儲器(DSP內核中的Cache、共享存儲器SMC等)和芯片外部存儲器(如DDR3存儲器等).同時，F(xiàn)FT加速器通過AXI從機命令通路完成DSP內核與FFT加速器之間的命令交互.FFT加速器接收來自DSP內核的啟動命令及參數(shù)配置，然后從SMC或DDR3中讀取數(shù)據(jù)進行指定規(guī)模的FFT運算，并將結果寫入到指定位置，最后通過AXI從機命令通路查詢方式或者中斷方式將完成信號及完成情況返回給DSP內核.

Fig. 2　The position of FFT accelerator on DSP chip.圖2　DSP芯片上FFT加速器的位置

Fig. 3　Structure of FFT accelerator.圖3　FFT加速器結構

如圖3(a)所示，F(xiàn)FT加速器主要由FFT控制器、DMA控制器、FFT-PE陣列和異步數(shù)據(jù)命令FIFO組成.異步數(shù)據(jù)命令FIFO用于隔離FFT加速器時鐘域(FFT_CLK)和DSP芯片時鐘域(SYS_CLK)，使得FFT加速器頻率不再受DSP系統(tǒng)頻率限制，可通過單獨調節(jié)FFT_CLK來匹配FFT-PE陣列計算帶寬和AXI數(shù)據(jù)網(wǎng)絡帶寬，從而獲得最佳能效.

FFT控制器控制著整個FFT加速器的運行，將批量FFT計算或大規(guī)模FFT計算分解為若干子操作序列，如DMA讀、DMA寫、DMA矩陣轉置和小規(guī)模FFT計算，并將這些子操作分配到各個執(zhí)行單元，在保證數(shù)據(jù)相關前提下盡可能通過重疊來隱藏延時，提高FFT加速器性能.

DMA控制器負責完成數(shù)據(jù)在SMC，DDR和FFT數(shù)據(jù)存儲器之間搬移，該模塊將DMA讀、DMA寫、DMA矩陣轉置等子操作轉換為一系列AXI總線事務，再以突發(fā)方式訪問片上SMC或者片外DDR存儲器.

FFT計算陣列完成所有計算任務，由N個單存儲器結構的FFT-PE和CORDIC補償旋轉因子產生邏輯組成，并行執(zhí)行多行小規(guī)模FFT運算.如圖3(b)所示，F(xiàn)FT-PE由M個并行的蝶形運算單元、FFT-PE計算控制器、“乒乓”多體結構數(shù)據(jù)存儲器、旋轉因子存儲器等組成，每個FFT-PE能夠完成一行小規(guī)模FFT計算，直接支持最大規(guī)模為Nm.在FFT計算過程中，同一級的蝶形運算不存在數(shù)據(jù)相關，可以并行執(zhí)行.因此，每個FFT-PE設置M個蝶形運算并行完成同一級FFT計算，同時每個蝶形運算單元采用全流水技術提高計算吞吐率.如圖3(c)所示，蝶形運算單元由6個單精度浮點乘法和4個單精度浮點加法組成，采用復數(shù)乘法與蝶形運算的復用結構，能夠以流水方式完成蝶形運算或復數(shù)乘法，減少中間計算結果的規(guī)格化操作，降低硬件開銷，減少計算延時.

FFT加速器支持的運算規(guī)模NF為2的冪次方，根據(jù)規(guī)模NF的大小，將FFT分為：

1) 小規(guī)模FFT算法.規(guī)模NF不超過Nm的FFT運算，通過DMA方式從DDR存儲器或SRAM中讀取數(shù)據(jù)，F(xiàn)FT-PE直接完成一維FFT運算，結果寫回到存儲器指定位置.

2) 大規(guī)模FFT算法.規(guī)模NF滿足Nm

2.2混合旋轉因子產生策略

旋轉因子可以通過查表或者在線計算這2種方式得到.查表方式可以快速獲得旋轉因子，然而查找表的存儲需求隨FFT規(guī)模NF而線性增加，為4×NF字節(jié)，對于大規(guī)模FFT算法，在芯片內部存儲所有旋轉因子的硬件開銷巨大.在線計算方式通常采用數(shù)字迭代算法，如CORDIC算法[16]，計算相應角度正弦值和余弦值，這種方法能夠計算出任意規(guī)模FFT的旋轉因子.然而，以全流水方式實現(xiàn)正弦和余弦在線計算的硬件開銷較大.本文提出混合旋轉因子產生策略，結合查表和在線計算方式，滿足Cooley-Tukey FFT算法需求，最大限度降低硬件開銷.

從Cooley-Tukey FFT算法可以看出，步驟1列方向FFT計算和步驟3行方向FFT計算可視為批量小規(guī)模FFT計算在N個FFT-PE上執(zhí)行，F(xiàn)FT規(guī)模不超過Nm.在每個FFT-PE中，M個蝶形計算單元為了獲得流水吞吐率，每個時鐘周期需要提供M個旋轉因子，因此，在FFT-PE內部設置基于查表方式的多體旋轉因子ROM(M個單端口(Nm2)×64的ROM，如圖3(b)所示)，為M個蝶形計算單元提供旋轉因子數(shù)據(jù).

Cooley-Tukey FFT算法步驟2補償旋轉因子計算過程中，需要NF個補償旋轉因子(對于FFT加速器支持最大規(guī)模為Nm2)，采用查表方式的存儲需求將達到M量級，硬件開銷較大.然而，在整個Cooley-Tukey FFT計算過程中，每個補償旋轉因子只使用一次.我們設計了基于CORDIC算法的補償旋轉因子計算引擎，采用41級全流水方式實現(xiàn).由于步驟2補償旋轉因子計算與步驟1和步驟3批量FFT計算存在數(shù)據(jù)相關性，需要串行執(zhí)行，將步驟1和步驟2相結合，步驟2視為一級FFT計算，以減少數(shù)據(jù)搬移，如圖1(b)中Step1和Step2.同時，相對于步驟1和步驟3，步驟2所需時鐘周期較少，多個FFT-PE可以共享同一個CORDIC補償旋轉因子計算引擎，進一步提高硬件資源利用率.

2.3“乒乓”多體數(shù)據(jù)存儲器(MBDM)

每組多體數(shù)據(jù)存儲器的數(shù)據(jù)以體低位地址交叉方式進行組織，如圖4所示，最大限度將同時訪問的數(shù)據(jù)存儲在不同存儲體中.FFT加速器運算是原位運算，即參與蝶形運算數(shù)據(jù)的原始位置和結果位置相同，對于第i級FFT運算，同一蝶形操作的2個數(shù)據(jù)間隔為2i-1，針對多體存儲器，采用如下訪問策略：

Fig. 4　Organization of data in MBDM.圖4　多體數(shù)據(jù)存儲器的數(shù)據(jù)組織方式

1) 第i級FFT計算，其中2i-1≤M.蝶形運算2個數(shù)據(jù)間隔不超過M，即這2個數(shù)據(jù)存儲在不同的存儲體中.每個存儲體的2個端口設置為一個讀端口和一個寫端口，同時從2個不同存儲體中的讀端口中讀取數(shù)據(jù)，蝶形運算結果通過寫端口寫入各自存儲體中.

2) 第i級FFT計算，其中2i-1>M.蝶形運算2個數(shù)據(jù)存儲在同一存儲體中.因此，只能通過該存儲體的2個端口同時讀才能獲得蝶形運算的2個數(shù)據(jù)；對于結果，需要將存儲體的2個端口設置為寫端口，同時完成寫操作.然而，2M個存儲體中，每個時鐘周期最多M個存儲體進行讀操作和M個存儲體進行寫操作.因此，可以采用存儲體交叉方式流水讀取數(shù)據(jù)，然后，再以交叉方式將數(shù)據(jù)寫入，避免存儲體的讀寫端口沖突，如圖5所示：

NoP refers to no operation in this cycle　Fig. 5　The space-time graph of “Ping-Pong” access mode of MBDM.圖5　多體數(shù)據(jù)存儲器乒乓訪問方式時空圖

3基于基本塊的矩陣轉置算法

FFT加速器通過AXI主機數(shù)據(jù)接口以突發(fā)方式訪問數(shù)據(jù)，需盡量避免對數(shù)據(jù)矩陣的列方式訪問.然而，如圖1(a)所示，在原始Cooley-Tukey FFT算法需要對數(shù)據(jù)矩陣進行3次列訪問(步驟1的讀矩陣、步驟1的寫矩陣和步驟3的寫矩陣).

本文利用FFT加速器內部數(shù)據(jù)存儲器(MBDM)來實現(xiàn)快速矩陣轉置，從而避免對數(shù)據(jù)矩陣的列方式訪問.本文提出基于基本塊的矩陣轉置策略：

1) 將原始N1×N2矩陣分解若干基本塊NB×NB(方陣，NB為2的冪次方)，通過一次按行讀和按列寫操作完成基本塊轉置；

2) 以基本塊為元素，對基本塊矩陣進行轉置，實現(xiàn)整個矩陣的轉置,基本塊矩陣轉置通過控制基本塊轉置的讀、寫地址完成；

3) 充分利用AXI數(shù)據(jù)通路的讀通路與寫通路完全分開，可以重疊讀操作和寫操作的特征，設計“乒乓”結構重疊不同基本塊的讀操作和寫操作.

3.1基本塊轉置算法

Fig. 6　The organization of basic block matrix in MBDM.圖6　多體數(shù)據(jù)存儲器中的基本塊組織

步驟1. 以行的順序連續(xù)讀取一個基本塊的數(shù)據(jù)，并以體交叉方式存儲到一組FFT-PE的數(shù)據(jù)存儲器中.基本塊中相鄰行列號相同的數(shù)據(jù)存儲到不同存儲體內，這樣保證按列讀取時能同時取出相鄰行相同位置的數(shù)據(jù).對于基本塊中任意數(shù)據(jù)E[i][j](0≤i,j

步驟2. 以列順序連續(xù)將數(shù)據(jù)從FFT-PE的數(shù)據(jù)存儲器MBDM中讀出，并以突發(fā)方式寫入到SMC或DDR.

3.2塊矩陣轉置算法

塊矩陣轉置如圖7所示，對于規(guī)模為NF的FFT計算(NF>1024)，NF點的一維數(shù)據(jù)可視為二維矩陣(NB×R)×(NB×C)，其中R>0，C>0.假定初始數(shù)據(jù)矩陣起始地址為A_I，轉換后數(shù)據(jù)矩陣起始地址為A_R，則矩陣中任意一個數(shù)據(jù)(序號為i，j)，則行列位置：

NC=i%(NB×C).

基本塊的行列位置：

基本塊內的行列位置：

NEC=NC%NB=(i%(NB×C))%NB.

矩陣轉置后對應的地址位置：

Addr_Trans[i]=A_R+NER+NB×NBR+

NB×C×(NB×NBC+NEC).

Fig. 7　The transposition of basic block matrix.圖7　基本塊矩陣轉置

塊矩陣轉置采用“乒乓”方式重疊讀、寫時間開銷，首先以行塊的順序讀取基本塊，以列塊順序寫入到目標地址中，除第1個基本塊的讀和最后一個基本塊的寫不能重疊外，其余的都能重疊，最大化利用讀、寫通路的數(shù)據(jù)帶寬.

4實驗及結果

4.1原型系統(tǒng)

在DSP芯片上設計實現(xiàn)了上述FFT加速器原型.該DSP芯片的片上共享存儲器SMC的容量為4 MB，系統(tǒng)時鐘頻率為500 MHz，峰值IO帶寬為8 GBps.FFT加速器原型包含2個FFT-PE，每個FFT-PE包含2個全流水蝶形運算單元，F(xiàn)FT-PE直接支持FFT的最大規(guī)模為1 024，即N=2，M=2，Nm=1024.FFT-PE內部的“乒乓”結構多體數(shù)據(jù)存儲器由8個子存儲體組成，每個子存儲體為一個256×64雙端口RAM.

在45 nm工藝庫下，對FFT加速器原型進行綜合，關鍵路徑延時為0.91 ns、面積為1.22 mm2、功耗為273 mW.FFT-PE計算陣列負責完成FFT算法中所有的計算工作，所占面積較大，約占86.3%.FFT加速器工作在1 GHz下，能夠取得單精度浮點峰值性能和能效分別為40 GFLOPs和146 GFLOPsW.

4.2性能比較與分析

表1對比了3個不同平臺執(zhí)行上小規(guī)模FFT的性能，這些平臺分別為TI TMS320C55X DSP芯片上的FFT加速器HWAFFT[13]、我們先前工作[14]——基于SRAM的無轉置可變規(guī)模FFT加速器和Intel Xeon X5675 CPU平臺上的FFTW函數(shù)庫.Intel CPU為6核12線程處理器，運行頻率為3.07 GHz，在此處理器上運行最快FFT函數(shù)庫——FFTW-3.3-DDL64[17]，該函數(shù)庫利用Intel處理器SSE4 SIMD指令對FFT算法進行自動向量化，加速FFT執(zhí)行.相對于Intel Xeon CPU平臺上的單線程FFTW，我們能夠取得1.14～1.65倍的性能提升，同時取得2個數(shù)量級的能效提升(124 GFLOPSW比0.14 GFLOPSW).相比于TI DSP芯片上的緊耦合FFT加速器HWAFFT，本文的設計能夠取得2.65～4.22倍的性能提升.相比于我們先前工作[14]，本文在數(shù)據(jù)存儲方式、并行任務調度和同步等方面進行優(yōu)化，性能略有提升.

Fig. 8　Performance comparison among different platforms for big size FFT.圖8　不同平臺上大規(guī)模FFT性能對比

圖8對比了3個不同平臺上執(zhí)行大規(guī)模FFT的性能，在Intel Xeon CPU上分別使用單線程和多線程(12線程)版本的FFTW函數(shù)庫的性能進行比較，而在TI TMS320C6678 DSP芯片上采用優(yōu)化后的單核和8核程序[18]的執(zhí)行性能進行比較.圖8(b)中的加速比以TI TMS320C6678 DSP上單核性能來評估.由于Intel Xeon CPU的L2 Cache容量為256 KB，能夠存儲32×103點FFT的數(shù)據(jù)，多核上執(zhí)行多線程Cooley-Tukey FFT通過L2 Cache進行數(shù)據(jù)交互.對于FFT規(guī)模超過32×103點，多線程FFTW必須通過L3 Cache或外部存儲器進行數(shù)據(jù)交互，性能會有所降低.因此，CPU上的多核程序執(zhí)行32×103點FFT運算時取得最高計算性能.相對于Intel CPU上的多線程FFTW，本文提出的FFT加速器性能略低，但是Intel CPU的功耗為FFT加速器的350倍以上(95 W比0.27 W)，F(xiàn)FT加速器能夠取得2個數(shù)量級的能效提升.對于1×106點FFT算法，本文的FFT加速器與多線程FFTW的性能相當.

TI TMS320C6678 DSP芯片的共享L2存儲器的容量為4 MB，能夠存儲256×103點FFT的數(shù)據(jù)，8核FFT程序通過L2存儲器進行數(shù)據(jù)交互.因此，多核DSP版本的FFT程序在256×103點時的性能最高.與單核DSP和多核DSP相比，本文的FFT加速器能夠獲得6.6倍和1.2倍的平均性能提升.

與我們先前工作[14]相比，本文基于FFT加速器內部多體數(shù)據(jù)存儲器實現(xiàn)快速矩陣轉置，并設計了基于矩陣轉置操作的Cooley-Tukey FFT算法，避免文獻[14]中的矩陣列訪問時FFT加速器中計算單元利用率不高、數(shù)據(jù)搬移開銷與FFT計算開銷無法有效重疊的問題.相比于文獻[14]，對于大規(guī)模FFT加速器，本文的FFT加速器能夠獲得2.3倍的平均性能提升.

5結論

在DSP芯片上設計實現(xiàn)了一個基于矩陣轉置操作的高能效FFT加速器，采用多種并行策略、混合旋轉因子產生策略和“乒乓”結構多體數(shù)據(jù)存儲器來提升FFT加速器性能和計算效能,并基于FFT加速器內部多體數(shù)據(jù)存儲器，提出基于基本塊的快速矩陣轉置算法，避免對矩陣的列訪問，進一步提升FFT加速器能效.

參考文獻

[1]Hadi E, Emily B, Remnee S A, et al. Dark silicon and the end of multicore scaling[C]Proc of the 38th Annual Int Symp on Computer Architecture. Piscataway, NJ: IEEE, 2011: 365-376

[2]Jesse B, Ryan C, Chris F, et al. Design, integration and implementation of the DySER hardware accelerator into OpenSPARC[C]Proc of the 18th IEEE Int Symp on High performance Computer Architecture. Piscataway, NJ: IEEE, 2012

[3]Nagabhushan C, Ganapati S, Scott H, et al. QuicklA: Exploring heterogeneous architectures on real prototypes[C]Proc of the 18th IEEE Int Symp on High performance Computer Architecture. Piscataway, NJ: IEEE, 2012

[4]James R G, Sharon M S. A transpose-free in-place SIMD optimized FFT[J]. ACM Trans on Architecture and Code Optimization, 2012, 9(3): 23:1-23:21

[5]Li Y, Zhang Y, Jia H, et al. Automatic FFT performance tuning on OpenCI GPUs[C]Proc of the 7th IEEE Int Conf on Parallel and Distributed Systems. Piscataway, NJ: IEEE, 2011: 228-235

[6]Chung E S, Milder P A, Hoe J C, et al. Single-chip heterogeneous computing—Does the future include custom logic, FPGAs, and GPU?[C]Proc of the 43rd Annual IEEEACM Int Symp on Microarchiecture. Piscataway, NJ: IEEE, 2010: 225-236

[7]Palmer J, Nelson B. A parallel FFT architecture for FPGAs[C]Proc of the 14th Int Conf on Field Programmable Logic and Application. Piscataway, NJ: IEEE, 2004: 948-953

[8]Dou Y, Zhou J, Lei Y, et al. FPGA SAR processor with window memory accesses[C]Proc of the 18th IEEE Int Conf on Application-Specific Systems, Architectures and Processors. Piscataway, NJ: IEEE, 2007: 95-100

[9]Cho T, Lee H. High-speed low-complexity modified radix-25 FFT processor for high rate WPAN applications[J]. IEEE Trans on Very Large Scale Integration Systems, 2013, 21(1): 187-191

[10]Yu C, Yen M H. Area-efficient 128- to 20481536-point pipeline FFT processor for LTE and mobile WiMAX systems[J]. IEEE Trans on Very Large Scale Integration Systems, 2015, 23(9): 1793-1800

[11]Tang S N, Liao C H, Chang T Y. An area-and energy-efficient multimode FFT processor for WPANWLANWMAN systems[J]. IEEE Journal of Solid-State Circuits, 2012, 47(6): 1419-1435

[12]Ayinala M, Brown M, Parhi K K. Pipelined parallel FFT architectures via folding transformation[J]. IEEE Trans on Very Large Scale Integration Systems, 2012, 20(6): 1068-1081

[13]Mckeown M. FFT implementation on the TMS320VC5505, TMS320C5505, and TMS320C5515 DSPs, SPRABB6B[R]. Dallas, Texas: Texas Instruments, 2013

[14]Guo L, Tang Y, Dou Y, et al. Transpose-free variable size FFT accelerator based on-chip SRAM[J]. IEICE Electron Express, 2014, 11(15): 1-8

[15]Guo L, Tang Y, Dou Y, et al. Window memory layout scheme for alternate row-wisecolumn-wise matrix access[J]. IEICE Trans on Information and Systems, 2013, E96-D(12): 874-885

[16]Jack E V. The CORDIC trigonometric computing technique[J]. IRE Trans on Electronic Computers, 1959, 8(3): 330-334

[17]Frigo M, Johnson S G. The design and implementation of FFTW3[J]. Proceeding of the IEEE, 2005, 93(2): 216-231

[18]Li X, Blinka E. Very large FFT for TMS320C6678 processors, spry277[R]. Dallas, Texas: Texas Instruments, 2015

Lei Yuanwu, born in 1982. Received his PhD degree in computer science and technology from National University of Defense Technology (NUDT) in 2012. Assistant researcher at the College of Computer, NUDT. His main research interests include high performance computer architecture, high-performance microprocessor and DSP design.

Chen Xiaowen, born in 1983. Received his PhD degree in microelectronics from NUDT in 2011. Assistant researcher at the College of Computer, NUDT. His main research interests include VLSI design, computer architecture, microarchitecture, SOC, and NOC.

Peng Yuanxi, born in 1966. Professor and PhD supervisor. Received his PhD degree in computer science from NUDT in 2001. His main research interests include high performance computing, on-chip networks, multi-core and many-core architectures.

收稿日期：2016-03-07；修回日期：2016-05-14

基金項目：國家自然科學基金項目(61402499,61502508)；湖南省自然科學基金項目(2015JJ3017)

通信作者：陳小文(xwchen@nudt.edu.cn)

中圖法分類號TP302

A High Energy Efficiency FFT Accelerator on DSP Chip

Lei Yuanwu, Chen Xiaowen, and Peng Yuanxi

(CollegeofComputer,NationalUniversityofDefenseTechnology,Changsha410073)

AbstractFast Fourier transform (FFT) is a most time-consuming algorithm in the domain of digital signal processing (DSP). The performance and energy efficiency of FFT will make significant effect on different DSP applications. Thus, this paper presents a high energy efficiency variable-size FFT accelerator based on matrix transposition on DSP chip. Several parallel schemes are employed to exploit instruction level parallel and task level parallel of batch of small-size FFTs or big-size Cooley-Tukey FFT. A “Ping-Pong” structure of multi-bank data memory (MBDM) is presented to overlap the overhead of data move and FFT calculation. Moreover, based on MBDM, fast matrix transposition algorithm with basic block transposition is presented to avoid the matrix access with column-wise and improve the utilization of DDR bandwidth. Hybrid twiddle factor generating scheme, combining lookup table and on-line calculation with CORDIC, is presented to reduce the hardware for twiddle factor. Experimental results show that our FFT accelerator prototype with power efficiency of 146 GFLOPs?W, achieves energy efficiency improvement by about two orders of magnitude with multi-thread FFTW on Intel Xeon CPU.

Key wordsfast Fourier transform (FFT); accelerator; high energy efficiency; matrix transposition; digital signal processing (DSP)

This work was supported by the National Natural Science Foundation of China (61402499,61502508) and the Natural Science Foundation of Hunan Province of China (2015JJ3017).