基于粗粒度可重構架構的并行FFT算法實現

曹 鵬 楊錦江 梅 晨

(東南大學國家專用集成電路系統工程技術研究中心,南京 210096)

以無線通信和媒體處理為代表的數據流應用對硬件架構平臺的性能提出了較高的要求.DSP(digital signal processer)靈活性好,但由于采用串行計算模式,難以滿足高性能的需求.ASIC(application specific integrated circuit)能針對特定應用定制數據通路和運算模塊,并能提供很好的性能,但難以迅速適應新的應用或當前應用的更新.可重構兼具ASIC的高性能和DSP的高靈活性,通過將運算任務映射到硬件資源上,保證了執行的高并行度,同時能夠根據應用變化通過配置改變其功能,因此得到廣泛采用[1].與細粒度可重構架構FPGA相比,粗粒度可重構架構[2]的區別在于將FPGA中的LUT替換成粗粒度的運算單元,同時簡化了FPGA的互聯類型.近年來眾多粗粒度可重構架構[2]被提出并得到應用.例如,XPP和ADRES架構已經被應用于無線通訊[3-4]和媒體處理[5-6]領域.而作為數字信號處理中的核心運算單元,FFT已經在很多粗粒度可重構架構上被實現,如NoC[7],MorphoSys[8],SmartCell[9], ePUMA[10]等.REMUS_LPP(reconfigurable embedded multimedia system, low performance processor)是可重構嵌入式媒體處理系統的移動版本,已被應用于媒體[11-12]和人臉檢測[13]等算法.本文基于REMUS_LPP實現了并行化的FFT算法,并提出了流水氣泡消除和數據塊位置重排優化技術.實驗結果顯示,本文的FFT性能明顯優于同類并行架構,并有效降低了片上存儲需求.

1 REMUS_LPP架構特征

1.1 REMUS_LPP架構

REMUS-Ⅱ是面向流處理應用的大規模粗粒度可重構陣列.REMUS_LPP作為其移動版本,與REMUS-Ⅱ[12]具有類似的架構,區別在于為了追求更高的能量效率,前者的運算資源為后者的一半.

REMUS_LPP架構的框圖如圖1所示,主要包括3個關鍵模塊:用來加速計算密集型任務的可重構處理單元(reconfigurable computing unit,RPU)、用來加速控制密集型任務的微處理器單元(micro processing unit,μPU)和用于系統總體控制調度的主控核ARM.RPU接收μPU或主控核發出的配置信息,按照配置信息進行相應的運算.系統中還包含一些輔助模塊,如中斷控制器(IntCtrl),DMA控制器和EMI等.這些模塊都通過AHB總線相連,另外在RPU和μPU之間采用一個專用數據通路來實現配置信息在2個模塊間的高速傳輸.

圖1 REMUS_LPP架構框圖

1.2 RPU

RPU主要用來加速執行密集型的計算任務,其內部結構如圖1所示.RPU結構包含4個可重構運算陣列 (reconfigurable computing array, RCA)和一個RPU共享存儲器(RPU shared memory, RSM).RCA作為動態可重構計算單元,包含一個運算陣列(processing element array，PEA)、一個RCA輸入FIFO和一個RCA輸出FIFO(RIF與ROF)、一個常數存儲器(constant memory, CM)和一個RCA中間數據緩存(RCA internal memory, RIM),如圖2(a)所示.PEA的結構如圖2(b)所示,主要由一個8×8的PE(processing element)陣列和8×8的TR(temporary register)陣列組成,數據可以從上一層的PE或TR傳輸到下一層PE或TR中.每個PE實現了簡單的ALU功能,TR作為陣列內的分布式存儲器主要用來暫存運算的中間數據以減少流水的氣泡.由RSM,RIM和TR構成的存儲子系統保證了數據在RPU中傳輸的高效性.

圖2 RPU內部結構圖

1.3 μPU

由圖1可見,μPU包含一個微處理器陣列(micro processing element array，μPEA)和一個郵箱.μPEA主要用來處理控制密集的任務,如生成配置信息等.μPE之間的通信以及μPE與主控之間的通信通過郵箱完成.μPU在生成配置信息后通過專用數據通路傳輸到RPU.

2 FFT算法在REMUS_LPP上的實現

離散傅里葉變換(DFT)是數字信號處理領域的經典算法之一,可表示為

式中,N為點數;旋轉因子WN可由下式計算獲得:

WN=e-2πj/N

快速傅里葉變換(FFT)[14]將傳統離散傅里葉變換的計算量從N2大幅降低到Nlog2(N),但依舊是諸多應用中計算的瓶頸.本文提出一種基于粗粒度可重構架構的FFT實現方案.

根據輸入數據的不同,FFT通常可分為按時間抽取(DIT)和按頻率抽取(DIF)2種.鑒于DIT算法能在蝶形運算的2個分支上獲得更好的計算平衡,本文采用經典的基2FFT算法,從而將N點FFT分為log2(N)個步驟完成,每個步驟執行N/2個2點的DFT.實現該步驟的執行單元被稱為蝶形運算單元(BU),其基本運算公式如下:

Aout=Ain+BinW

Bout=Ain-BinW

式中,輸入Ain,Bin和輸出Aout,Bout以及旋轉因子W都為復數.在算法映射過程中,BU運算被分解為多個實數運算,包括4次加法、2次減法和4次乘法,具體過程如下:

Tmpre=Bin_reWre-Bin_imWim
Tmpim=Bin_reWim+Bin_imWre
Aout_re=Ain_re+Tmpre
Aout_im=Ain_im+Tmpim
Bout_re=Ain_re-Tmpre
Bout_im=Ain_im-Tmpim

式中,Ain_re和Ain_im為輸入Ain的實部和虛部;Bin_re和Bin_im為輸入Bin的實部和虛部;Aout_re和Aout_im為輸出Aout的實部和虛部;Bout_re和Bout_im為輸出Bout的實部和虛部;Tmpre,Tmpim和Wre,Wim分別表示中間結果和旋轉因子的實部和虛部.

2.1 算法并行化

在本文設計中,輸入數據首先經過位反轉排序,然后通過2個步驟完成FFT算法.第1步可被稱為局部串行FFT,輸入數據被等分為p個數據塊,每個N/p的數據塊在編號為0～p-1的執行單元(EU)中獨立執行,分別完成N點FFT的前log2(N/p)階,計算結果存儲在每個EU的局部存儲器中,偽碼如算法1所示.第2步可被稱為數據交換FFT,每個EU只將其上半部分和下半部分的N/(2p)的數據和其配對的EU進行交換,完成N點FFT中剩余的log2p階計算,運算完成后再按同樣的交換規則寫回到對應的EU,從而保證下一階運算進行數據交換的統一性,偽碼如算法2所示.

算法1局部串行FFT

1 Inputc=(c0,c1,…,cN/p-1)

2 Outputc=(c0,c1,…,cN/p-1)

3 fori=0 to log2(N/p)-1

4l=2i

5 fork=0 toN/p-1

6 getwbyjandi

7 if((i*N/p+k)modl=(i*N/p+k)mod 2l)

8c(k)=c(k)+c(k+l)*w

9c(k+l)=c(k)-c(k+l)*w

10 end if

11 end for

12 end for

算法2數據交換FFT

1 Inputc=(c0,c1,…,cN/p-1)

2 Outputc=(c0,c1,…,cN/p-1)

3j=log2(p)+1

4 fore=0 to log2(p)-1 do

5t=2e,v=2j,j=j-1

6 fori←0 top-1 do

7 if (imodt=imod 2t) then

8 Send upperN/(2p) data stored inc[N/(2p)]-c[N/p-1] to the (i+p/v)-th PE.

9 ReceiveN/(2p) data from (i+p/v)-th PE and store them to upperN/(2p) location ofc[].

/*transform*/

10 fork←0 toN/(2p)-1 do

11 getwbyi,kande

12c[k]=c[k]+c[k+N/(2p)] *w

13c[k+N/(2p)]=c[k]-c[k+N/(2p)]*w

14 end for

15 Send upperN/(2p) of transformed data stored inc[N/2p]-c[N/p-1]back to the (i+p/v)-th PE.

16 Receive theN/2ptransformed data from (i+p/v)-th PE and store them back to upperN/(2p) location ofc[].

17 else

18 Send lowerN/(2p) data stored inc[0]-c[N/(2p)-1] to the (i-p/v)-th PE.

19 ReceiveN/(2p) data from (i-p/v)-th PE and store them to lowerN/(2p) location ofc[].

/*transform*/

20 fork←0 toN/(2p)-1 do

21 getwbyi,kande

22c[k]=c[k]+c[k+N/(2p)]*w

23c[k+N/(2p)]=c[k]-c[k+N/(2p)]*w

24 end for

25 Send lowerN/(2p) of transformed data stored inc[0]-c[N/(2p)-1]back to the (i-p/v)-th PE.

26 Receive theN/(2p) transformed data from (i-p/v)-th PE and store them back to lowerN/(2p) location ofc[].

27 end if

28 end for

29 end for

2.2 流水氣泡消除

BU的數據流圖(DFG)如圖3(a)所示.由圖可見,BU運算可利用10個PE在3個周期內完成2點FFT的計算.由于每個RCA中包含規模為8×8的PE陣列,因此能同時實現4個BU.BU的執行過程如圖3(b)所示,分為讀入、計算和寫出3個步驟,其中計算步驟通過3個計算周期完成.雖然輸入A和輸入B可被同時傳輸至運算陣列PEA,但是輸入A在第3個計算周期才被使用,這樣使得下一次的輸入需要等待3個周期才可以進行,產生了流水氣泡.

圖3 優化前的蝶形運算單元DFG圖和流水線

為了提升BU執行效率,對BU的DFG通過插入寄存器的方式進行優化,優化后的DFG如圖4(a)所示.將優化后的DFG映射至RCA時,插入的寄存器采用臨時寄存器TR實現,從而保證所有數據輸入可以連續進行.改進后的BU流水線如圖4(b)所示,和圖3(b)所示的流水線相比,BU的執行效率大幅提高.

圖4 優化后的蝶形運算單元DFG圖和流水線

2.3 數據塊重排

本文將每個RCA作為FFT算法中的EU,共可實現4個EU,每個EU可實現4個BU.每個N/4點子序列存儲在各個RCA的RIM中.

N點FFT共需要進行m階運算(m=log2N),其前log2(N/4)階運算在4個RCA中獨立并行執行,并將運算結果存儲在各自的RIM中.在執行第m階和第m-1階運算時,RIM中的數據被分為上半部分和下半部分,并通過共享存儲器RSM進行數據交換,交換方式如圖5所示,其中RIM0～RIM3分別為RCA0～RCA3中的臨時數據緩存RIM,不同的數字標識RIM中數據的上半部分或下半部分.在進行第m-1階運算前,RIM0～RIM3中的數據塊位置如圖5(a)所示.為進行第m-1階運算,RCA間需先進行數據交換,交換完成后的數據塊位置如圖5(b)所示.當第m-1階運算完成后,各個RIM中的數據再次進行交換,交換完成后的數據塊位置如圖5(a)所示.第m階的執行過程與第m-1階類似,其數據交換后的數據塊位置如圖5(c)所示.

圖5 數據塊位置圖

分析圖5(a)～(c)可見,在數據塊組成形式由圖5(b)(針對第m-1階運算)重排為圖5(c)(針對第m階運算)過程中,考慮到4個RCA均可實現任意數據的第m階運算,可不必將第m-1階運算的結果寫回為圖5(a)的形式,而直接對數據塊位置進行重排,以滿足第m階運算的需求.優化的數據塊重排方式如圖5(d)所示,由圖可見,4組RIM中的數據雖然分布在不同的RCA中,但是其組織形式與圖5(c)無異.通過采用數據塊重排的技術,FFT最后2階計算中的數據不需要將結果寫回,從而有效地減少了RCA間數據傳輸量.

3 結果和比較

3.1 性能分析和實現

基于可重構架構REMUS_LPP實現N點并行FFT運算時,所需時間T可表示為

式中,Tlocal-i表示在N點FFT運算過程中,第i(i=1,2,…,m)階運算在RCA上執行的時間;Tdata-exchange表示RCA間進行數據交換的時間,只在最后2階FFT運算中發生;Tlocal-i包括旋轉因子更新時間TW-update、計算時間Tcalc和數據讀取寫出時間Tload-store;Tdata-exchange包括數據傳輸時間Tdata-transfer和同步時間Tsync.

各階運算執行中讀入-計算-寫出的流水如圖6所示.在計算開始前,需要讀入處理數據并完成旋轉因子更新,后者更新頻度與階數有關,因此整個讀入-計算-寫出流水與階數有關.第m～m-2階FFT運算的流水線如圖6(a)所示.由于數據傳輸完全被旋轉因子的更新打斷,因此讀入、計算與寫出完全串行,執行時間由旋轉因子的更新時間決定.第m-3階FFT運算的流水線如圖6(b)所示.雖然讀入和計算的時間有部分重疊,但流水線依舊被旋轉因子的更新打斷,不同旋轉因子對應的數據塊之間的計算完全沒有重疊時間,導致數據不能連續輸入.而在其余階的運算中,由于旋轉因子更新頻度較低,因此其更新時間可被完全隱藏在計算流水中.第4階FFT運算的流水線如圖6(c)所示,需要更新2次旋轉因子.由于每個RCA上4個BU最多需要4個不同的旋轉因子,因此最多需要4個周期完成各個旋轉因子的更新.隨著每次旋轉因子的更新,需要完成一半數據的傳輸,傳輸時間為N/64個周期.在圖6(c)中,數據傳輸時間大于旋轉因子更新時間,從而使得后者完全被掩蓋在讀入-計算-寫出的流水線中,保證了數據的讀入、計算和寫出完全流水執行.

圖6 FFT各階計算的讀入-計算-寫出流水圖

N點FFT運算的整體性能提升如圖7所示,其中橫坐標表示FFT的點數,縱坐標表示對應點數FFT的執行周期數T.通過采用流水氣泡消除技術(優化1)和數據塊重排技術(優化2),分別有效減少了Tcalc和Tdata-exchange,且收益隨FFT點數的增加而增大.對于2 048點FFT運算,二者分別提升41.10%和7.47%的執行速度,整體執行速度提高了58.55%.

圖7 N點FFT運算性能優化

本文基于REMUS_LPP實現了一款面向移動智能終端的SoC芯片.該芯片采用TSMC 65 nm LP工藝,工作頻率為200 MHz,管芯照片如圖8所示.該芯片面積為38.44 mm2,其中REMUS_LPP的面積為21.6 mm2.

圖8 SoC芯片管芯照片

3.2 比較

將本文FFT算法實現的性能與其他同類并行計算平臺實現結果進行了對比,包括NoC[7],MorphoSys[8],ePUMA[10]和SmartCell[9].平臺硬件實現對比如表1所示.由表可見,REMUS_LPP片上存儲需求僅為SmartCell[9]和MorphoSys[8]的28.1%和7.0%.

表1 并行架構與REMUS_LPP的硬件參數對比

FFT算法在不同平臺上的性能比較如圖9所示.在多種點數計算場景下,基于REMUS_LPP實現的FFT算法的性能提升至其他平臺的2.15～13.60倍.

圖9 FFT算法在不同平臺上的性能比較

4 結語

本文基于粗粒度可重構架構REMUS_LPP提出了一種復數FFT并行化實現方案,通過引入流水線消除和數據塊重排技術優化了性能.本文實現方案的執行速度提升至其他同類并行計算架構的2.15～13.60倍,而片上存儲開銷的需求僅為其他方法的7.0%～28.1%.

)

[1] Cervero T, López S, Callicó G M, et al. Survey of reconfigurable architectures for multimedia applications[C]//SPIEProceedingsofVLSICircuitsandSystemsⅣ. Dresden, Germany, 2009: 736303-01-736303-12.

[2] Hartenstein R. A decade of reconfigurable computing: a visionary retrospective [C]//ProceedingsoftheConferenceonDesign,AutomationandTest. Munich, Germany, 2001: 642-649.

[3] PACT Inc. White paper of reconfiguration on XPP-Ⅲ processor[R]. Munich, Germany: PACT Inc, 2006.

[4] Palkovic M, Cappelle H, Glassee M, et al. Mapping of 40 MHz MIMO SDM-OFDM baseband processing on multi-processor SDR platform [C]//11thIEEEWorkshoponDesignandDiagnosticsofElectronicCircuitsandSystem. Bratislava, Czechoslovakia, 2008: 86-91.

[5] Mei B, Sutter B, Aa T, et al. Implementation of a coarse-grained reconfigurable media processor for AVC decoder [J].JournalofSignalProcessingSystems, 2008,51(1): 225-243.

[6] Mei B, Veredas F J, Masschelein B. Mapping an H.264/AVC decoder onto the ADRES reconfigurable architecture [C]//InternationalConferenceonFieldProgrammableLogicandApplications. Tampere, Finland, 2005: 622-625.

[7] Bahn J H, Yang J S, Bagherzadeh N. Parallel FFT algorithms on network-on-chips [C]//FifthInternationalConferenceonInformationTechnology:NewGenerations. Las Vegas, NV, USA, 2008: 1087-1093.

[8] Kamalizad A H, Pan C, Bagherzadeh N. Fast parallel FFT on a reconfigurable computation platform [C]//15thSymposiumonComputerArchitectureandHighPerformanceComputing. St Paul’s, Brazil, 2003: 254-259.

[9] Cao L, Huang X M. Mapping parallel FFT algorithm onto SmartCell coarse-grained reconfigurable architecture [J].IEICETransactionsonElectronics, 2010,E93C(3): 407-415.

[10] Liu Z Y, Xie Q F, Wang H K, et al. A high performance implementation of non-power-of-two FFT with EPUMA platform[C]//InternationalWorkshoponInformationandElectronicsEngineering. Harbin, China, 2012,29: 3408-3412.

[11] Nguyen K, Cao P, Wang X X, et al. Implementation of H.264/AVC encoder on coarse-grained dynamically reconfigurable computing system [C]//FourthInternationalConferenceonCommunicationsandElectronics. Hue, Vietnam, 2012: 483-488.

[12] Liu B, Cao P, Zhu M, et al. Reconfiguration process optimization of dynamically coarse grain reconfigurable architecture for multimedia applications [J].IEICETransactionsonInformationandSystems, 2012,E95D(7): 1858-1871.

[13] Xiao J, Zhang J G, Zhu M, et al. Fast AdaBoost-based face detection system on a dynamically coarse grain reconfigurable architecture [J].IEICETransactionsonInformationandSystems, 2012,E95D(2): 392-402.

[14] Cooley J W, Tukey J W. An algorithm for the machine calculation of complex Fourier series [J].MathematicsofComputation, 1965,19(90): 297-301.