基于粗粒度可重構(gòu)架構(gòu)的并行FFT算法實現(xiàn)

曹 鵬 楊錦江 梅 晨

(東南大學(xué)國家專用集成電路系統(tǒng)工程技術(shù)研究中心,南京 210096)

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

1 REMUS_LPP架構(gòu)特征

1.1 REMUS_LPP架構(gòu)

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

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

圖1 REMUS_LPP架構(gòu)框圖

1.2 RPU

RPU主要用來加速執(zhí)行密集型的計算任務(wù),其內(nèi)部結(jié)構(gòu)如圖1所示.RPU結(jié)構(gòu)包含4個可重構(gòu)運算陣列 (reconfigurable computing array, RCA)和一個RPU共享存儲器(RPU shared memory, RSM).RCA作為動態(tài)可重構(gòu)計算單元,包含一個運算陣列(processing element array，PEA)、一個RCA輸入FIFO和一個RCA輸出FIFO(RIF與ROF)、一個常數(shù)存儲器(constant memory, CM)和一個RCA中間數(shù)據(jù)緩存(RCA internal memory, RIM),如圖2(a)所示.PEA的結(jié)構(gòu)如圖2(b)所示,主要由一個8×8的PE(processing element)陣列和8×8的TR(temporary register)陣列組成,數(shù)據(jù)可以從上一層的PE或TR傳輸?shù)较乱粚覲E或TR中.每個PE實現(xiàn)了簡單的ALU功能,TR作為陣列內(nèi)的分布式存儲器主要用來暫存運算的中間數(shù)據(jù)以減少流水的氣泡.由RSM,RIM和TR構(gòu)成的存儲子系統(tǒng)保證了數(shù)據(jù)在RPU中傳輸?shù)母咝?

圖2 RPU內(nèi)部結(jié)構(gòu)圖

1.3 μPU

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

2 FFT算法在REMUS_LPP上的實現(xiàn)

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

式中,N為點數(shù);旋轉(zhuǎn)因子WN可由下式計算獲得:

WN=e-2πj/N

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

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

Aout=Ain+BinW

Bout=Ain-BinW

式中,輸入Ain,Bin和輸出Aout,Bout以及旋轉(zhuǎn)因子W都為復(fù)數(shù).在算法映射過程中,BU運算被分解為多個實數(shù)運算,包括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分別表示中間結(jié)果和旋轉(zhuǎn)因子的實部和虛部.

2.1 算法并行化

在本文設(shè)計中,輸入數(shù)據(jù)首先經(jīng)過位反轉(zhuǎn)排序,然后通過2個步驟完成FFT算法.第1步可被稱為局部串行FFT,輸入數(shù)據(jù)被等分為p個數(shù)據(jù)塊,每個N/p的數(shù)據(jù)塊在編號為0～p-1的執(zhí)行單元(EU)中獨立執(zhí)行,分別完成N點FFT的前l(fā)og2(N/p)階,計算結(jié)果存儲在每個EU的局部存儲器中,偽碼如算法1所示.第2步可被稱為數(shù)據(jù)交換FFT,每個EU只將其上半部分和下半部分的N/(2p)的數(shù)據(jù)和其配對的EU進行交換,完成N點FFT中剩余的log2p階計算,運算完成后再按同樣的交換規(guī)則寫回到對應(yīng)的EU,從而保證下一階運算進行數(shù)據(jù)交換的統(tǒng)一性,偽碼如算法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數(shù)據(jù)交換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的數(shù)據(jù)流圖(DFG)如圖3(a)所示.由圖可見,BU運算可利用10個PE在3個周期內(nèi)完成2點FFT的計算.由于每個RCA中包含規(guī)模為8×8的PE陣列,因此能同時實現(xiàn)4個BU.BU的執(zhí)行過程如圖3(b)所示,分為讀入、計算和寫出3個步驟,其中計算步驟通過3個計算周期完成.雖然輸入A和輸入B可被同時傳輸至運算陣列PEA,但是輸入A在第3個計算周期才被使用,這樣使得下一次的輸入需要等待3個周期才可以進行,產(chǎn)生了流水氣泡.

圖3 優(yōu)化前的蝶形運算單元DFG圖和流水線

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

圖4 優(yōu)化后的蝶形運算單元DFG圖和流水線

2.3 數(shù)據(jù)塊重排

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

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

圖5 數(shù)據(jù)塊位置圖

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

3 結(jié)果和比較

3.1 性能分析和實現(xiàn)

基于可重構(gòu)架構(gòu)REMUS_LPP實現(xiàn)N點并行FFT運算時,所需時間T可表示為

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

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

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

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

圖7 N點FFT運算性能優(yōu)化

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

圖8 SoC芯片管芯照片

3.2 比較

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

表1 并行架構(gòu)與REMUS_LPP的硬件參數(shù)對比

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

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

4 結(jié)語

本文基于粗粒度可重構(gòu)架構(gòu)REMUS_LPP提出了一種復(fù)數(shù)FFT并行化實現(xiàn)方案,通過引入流水線消除和數(shù)據(jù)塊重排技術(shù)優(yōu)化了性能.本文實現(xiàn)方案的執(zhí)行速度提升至其他同類并行計算架構(gòu)的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.