摘? 要: 針對基-2 FFT處理算法,采用分塊存儲思想,將存儲器、處理機數(shù)據(jù)交換網(wǎng)絡(luò)模型進(jìn)行優(yōu)化。優(yōu)化后的網(wǎng)絡(luò)模型數(shù)據(jù)通路數(shù)僅為20,降低為原來的4%以下,且不隨FFT計算點數(shù)增多而增加。整個設(shè)計在Virtex系統(tǒng)芯片XCV800上實現(xiàn)。?

??? 關(guān)鍵詞: 實時信號處理;并行計算;FFT;網(wǎng)絡(luò)模型?

?

??? 實時信號處理系統(tǒng)^[1]廣泛應(yīng)用于圖像處理、語音處理、智能儀表、通信以及自動控制等領(lǐng)域。FFT/DFT作為數(shù)字信號處理(DSP)系統(tǒng)中常用的積分變換算法被普遍使用。同時FFT運算的計算量很大,往往構(gòu)成實時信號處理的計算瓶頸。本文以空間太陽望遠(yuǎn)鏡的相關(guān)跟蹤系統(tǒng)為研究背景^[2],考慮我國可應(yīng)用到航天環(huán)境的高可靠性的電子系統(tǒng)其主頻往往不高于25MHz,所以采用并行計算的策略。通過對計算資源與速度的平衡分析,選擇在FPGA內(nèi)構(gòu)造兩個蝶形處理器實現(xiàn)并行計算。兩個處理機采用共享存儲器模式^[3]。如果在存儲數(shù)據(jù)與處理機之間采用傳統(tǒng)數(shù)據(jù)總線方式,需要總線仲裁器對總線的請求進(jìn)行分時應(yīng)答,難以實現(xiàn)數(shù)據(jù)從源節(jié)點到目標(biāo)節(jié)點的實時傳輸;而采用點對點任意連接的網(wǎng)狀結(jié)構(gòu)會使設(shè)計復(fù)雜度大幅增加。因此,本文針對FFT運算特點,設(shè)計了存儲器與并行機的網(wǎng)絡(luò)模型。該網(wǎng)絡(luò)模型沒有數(shù)據(jù)傳輸延遲,但結(jié)構(gòu)得到了極大簡化。?

1 并行FFT結(jié)構(gòu)分析?

??? 本文針對32×32點序列的圖像進(jìn)行FFT變換?？梢圆捎眯辛凶儞Q的形式,對于每行/列數(shù)據(jù)可以用基-2算法^[4]進(jìn)行計算?；?2算法計算的核心為蝶形運算。為了實現(xiàn)并行處理,在FPGA內(nèi)部構(gòu)造出兩個蝶形運算模塊,結(jié)構(gòu)如圖1。?

?

?

??? 圖1中RAM為FPGA塊存儲器,存放原始數(shù)據(jù)和FFT之后的最終結(jié)果?！癇ase-2 Core”為蝶形運算單元,圖中為兩個蝶形運算單元并列構(gòu)成雙核結(jié)構(gòu),其中每個蝶形運算單元的輸入和輸出都是兩個數(shù)據(jù)通道。Input Buffer是存儲器與蝶形運算單元之間的數(shù)據(jù)緩存,它逐行接收從存儲器RAM發(fā)來的數(shù)據(jù),然后按一定順序發(fā)送給兩個處理單元,并緩存中間結(jié)果。Output Buffer為輸出緩存,它將FFT最后一級的計算結(jié)果進(jìn)行緩存,等待主存儲器RAM空閑時再發(fā)送過去。?

2 處理機與存儲器網(wǎng)絡(luò)模型?

??? 雙核處理器的數(shù)據(jù)輸入和輸出都是4個通道,每個通道均為復(fù)數(shù)形式的18位浮點數(shù)據(jù)(共計36位寬度)。4個通道同時工作意味著有相對應(yīng)的4個并行的存儲器通道。而輸入序列是存儲在輸入緩存中的兩行/列共64點數(shù)據(jù)。如果輸入緩存采用FPGA內(nèi)部的Block Ram方式實現(xiàn),則難以實現(xiàn)4個通道同時工作。因為32點的基-2FFT共分5級運算,每一級運算請求的數(shù)據(jù)順序不同,即使構(gòu)造4端口的存儲器也無法實現(xiàn)同時讀取任意4個數(shù)據(jù)。如果用FPGA內(nèi)部的查找表(LUT,Look Up Table)實現(xiàn)分布式存儲,則存儲器與雙核處理器組成的網(wǎng)絡(luò)結(jié)構(gòu)如圖2。?

?

?

??? 圖2中上方的圓形區(qū)域代表存儲的數(shù)據(jù),下方的圓形區(qū)域代表雙核處理器的4個通道。如果每個數(shù)據(jù)都可能進(jìn)入雙核處理器的每一個輸入端,則數(shù)據(jù)通路如同圖2的網(wǎng)絡(luò)結(jié)構(gòu)。假設(shè)上方的數(shù)據(jù)點數(shù)為M,下方的數(shù)據(jù)通路為N,則連接復(fù)雜度計算公式為:?

?????

其中,P為通路個數(shù),不同方向表示不同的通路,即公式中的系數(shù)2。對于本文情況,數(shù)據(jù)點M為64,計算通路N為4,所以連接復(fù)雜度為512。?

3 基于P_N算子的網(wǎng)絡(luò)模型簡化?

??? 在基于FFT的蝶形運算中,并非所有數(shù)據(jù)都有進(jìn)入任何數(shù)據(jù)通道的可能性,而是按照一定的規(guī)律順序進(jìn)入4個計算通道。根據(jù)并行FFT算法,并行FFT可以表示為如下遞歸形式^[5]:?

?????

其中,x_i為第i級變換;C為和差算子;為旋轉(zhuǎn)因子的乘積運算;P_N為完全混合算子。其中C和的作用是完成蝶形運算,而P_N的作用是將數(shù)據(jù)進(jìn)行重排。因此可以根據(jù)數(shù)據(jù)重排規(guī)律進(jìn)行網(wǎng)絡(luò)優(yōu)化。?

??? P_N算子的作用是將序列(a,b,c,d)轉(zhuǎn)化為序列(a,c,b,d)。假設(shè)輸入序列和輸出序列均轉(zhuǎn)化為二維形式:?

?????

??? 這樣完全混合算子的作用相當(dāng)于矩陣的轉(zhuǎn)置。因此設(shè)計上既不采用FPGA內(nèi)部Block Ram設(shè)計輸入緩存,也不用分布式存儲方法,而是利用分塊存儲的方式。假設(shè)將存儲器分為4塊,則基于完全混合算子的數(shù)據(jù)讀寫方式如圖3所示。?

?

?

??? 圖3中圓形區(qū)域表示存儲的分塊,4個存儲區(qū)域構(gòu)成一個緩存整體。為了實現(xiàn)矩陣的轉(zhuǎn)置,將讀和寫的控制分開,讀取序列為上半?yún)^(qū)和下半?yún)^(qū),寫入序列為左半?yún)^(qū)和右半?yún)^(qū)。圖中實心圓形為活動存儲單元,空心圓形為非活動存儲單元。圖中上兩個矩形分別代表讀取的兩種模式,下兩個矩形則代表寫入的兩種模式。通過讀取和寫入的不同實現(xiàn)了序列的轉(zhuǎn)置。圖3中同時只有兩個存儲區(qū)域活動代表雙核處理器的一個計算單元,即兩個計算通道。另外兩個計算通道情況相同?；谝陨显O(shè)計模型,實際的數(shù)據(jù)連接模型如圖4。

?

?

??? 圖4中,上面8個圓形為存儲區(qū)域,下面4個圓形為計算通路。根據(jù)建模分析所有的連接情況如圖中的網(wǎng)絡(luò),其中箭頭代表方向。該圖形左右對稱,分別代表兩個相同的處理單元。它們之間的交叉線表示在FFT最后一級運算時存在數(shù)據(jù)交換。經(jīng)初步分析,優(yōu)化后的網(wǎng)絡(luò)模型的數(shù)據(jù)復(fù)雜度僅為20。這樣通過將輸入緩沖存儲器劃分為8個模塊后,可以使設(shè)計的復(fù)雜度減少25.6倍,即降低為原來的4%以下。而且,隨著計算點數(shù)的增加,網(wǎng)絡(luò)的規(guī)模保持不變。根據(jù)這種方法得到單處理器和多處理器的復(fù)雜度如表1所示。?

?

?

4 實驗結(jié)果?

??? 根據(jù)優(yōu)化模型分別設(shè)計相應(yīng)的輸入緩存Input Buffer和輸出緩存Output Buffer。分別對這兩個單元進(jìn)行控制信號仿真,仿真波形見圖5、圖6。?

?

?

?

??? 圖5、圖6中“rl”為行列變換轉(zhuǎn)換控制信號。對于輸出緩存,“we”和“en”分別為寫和讀控制信號?？梢钥闯?在行變換和列變換的狀態(tài)下,分別對應(yīng)16次讀寫信號。整個FFT的時間可以從緩存的工作狀態(tài)估算出來,即190μs～300μs之間,約110μs。?

??? 對于32×32點的二維FFT,每行/列變換需要分為5級運算,每次蝶形運算同時有4個數(shù)據(jù)到達(dá)。因此完成一次二維FFT共需要32×32×2×5/4=2 560個時鐘周期。工作在25MHz的主頻下,計算時間約為102μs。估算時間與仿真波形時間相近,可見整個計算過程中數(shù)據(jù)交換不存在網(wǎng)絡(luò)延時。?

??? 綜上所述,在FPGA片內(nèi)實現(xiàn)并行計算時,存儲器采用FPGA內(nèi)的“Block RAM”很難滿足多通道數(shù)據(jù)計算的需求,而分布式存儲模式則隨FFT計算點數(shù)增多而消耗過多資源。通過對特定FFT算法進(jìn)行分析,改為分塊式存儲,將網(wǎng)絡(luò)模型進(jìn)行了簡化,使存儲單元與處理器之間的數(shù)據(jù)通道數(shù)縮減為20,并且不隨FFT計算點數(shù)的增多而增多,將資源消耗控制在一定規(guī)模以內(nèi)。整個并行FFT計算在Virtex XCV800上實現(xiàn),經(jīng)測試,計算時間僅為110μs,符合設(shè)計需求。?

參考文獻(xiàn)?

[1] 蘇濤,何學(xué)輝,呂林夏,等.實時信號處理系統(tǒng)設(shè)計[M].西安:西安電子科技大學(xué)出版社,2006?

[2] 布朗,施密特.空間太陽望遠(yuǎn)鏡評估研究報告[M].中國科學(xué)院北京天文臺,1997.?

[3] 曾泳泓,成禮智,周敏.數(shù)字信號處理的并行算法[M].長沙:國防科技大學(xué)出版社,1999.?

[4] 胡廣書.數(shù)字信號處理[M].北京:清華大學(xué)出版社,1997.?