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

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

?

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

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

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

?

?

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

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

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

?

?

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

?????

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

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

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

?????

其中,x_i為第i級(jí)變換;C為和差算子;為旋轉(zhuǎn)因子的乘積運(yùn)算;P_N為完全混合算子。其中C和的作用是完成蝶形運(yùn)算,而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è)計(jì)上既不采用FPGA內(nèi)部Block Ram設(shè)計(jì)輸入緩存,也不用分布式存儲(chǔ)方法,而是利用分塊存儲(chǔ)的方式。假設(shè)將存儲(chǔ)器分為4塊,則基于完全混合算子的數(shù)據(jù)讀寫方式如圖3所示。?

?

?

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

?

?

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

?

?

4 實(shí)驗(yàn)結(jié)果?

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

?

?

?

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

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

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

參考文獻(xiàn)?

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

[2] 布朗,施密特.空間太陽(yáng)望遠(yuǎn)鏡評(píng)估研究報(bào)告[M].中國(guó)科學(xué)院北京天文臺(tái),1997.?

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

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