摘 要： 針對(duì)在FPGA中直接運(yùn)用分布式算法" title="分布式算法">分布式算法實(shí)現(xiàn)內(nèi)積運(yùn)算時(shí),，內(nèi)積運(yùn)算的系數(shù)大小,、存儲(chǔ)資源,、運(yùn)算速度" title="運(yùn)算速度">運(yùn)算速度難于達(dá)到最佳配置的問(wèn)題,，從算法,、存儲(chǔ)規(guī)模,、查表" title="查表">查表速度三個(gè)方面進(jìn)行了詳細(xì)的分析和討論,，并給出了相應(yīng)的優(yōu)化和改進(jìn)措施。
關(guān)鍵詞： FPGA 內(nèi)積算法 優(yōu)化
基于分布式算法通過(guò)FPGA查找表" title="查找表">查找表實(shí)現(xiàn)內(nèi)積運(yùn)算，實(shí)現(xiàn)如下算法：
其中：Am為固定系數(shù),，Xm為輸入數(shù)據(jù)(Xm<1),。利用分布式算法將內(nèi)積運(yùn)算轉(zhuǎn)化為移位求和實(shí)現(xiàn)，用二進(jìn)制補(bǔ)碼表示,，將Xm表示成如式(2)形式：
式(3)中,，由于Xmn的取值為0或1，所以
存在2M 種不同的結(jié)果,。如果事先構(gòu)造一個(gè)查找表,，該表存儲(chǔ)了所有可能的組合值，即可以預(yù)先計(jì)算這2M個(gè)值,，并存入查找表（LUT）中，用Xmn作為查找表的地址信號(hào),，將查找表的輸出結(jié)果移位(2-1運(yùn)算)和相加,，經(jīng)過(guò)N-1個(gè)周期即可直接獲得乘法累加的結(jié)果。這樣就將復(fù)雜的乘法累加運(yùn)算轉(zhuǎn)化為移位相加運(yùn)算,。為提高運(yùn)算速度,，采用并行運(yùn)算。其硬件電路簡(jiǎn)化結(jié)構(gòu)如圖1所示,。
直接運(yùn)用分布式算法實(shí)現(xiàn)內(nèi)積運(yùn)算,雖然實(shí)現(xiàn)了把復(fù)雜的內(nèi)積運(yùn)算轉(zhuǎn)化為移位相加運(yùn)算,，但其查找表的規(guī)模隨著系數(shù)呈指數(shù)增加。如果系數(shù)小,，則可以方便地通過(guò)FPGA豐富的查找表結(jié)構(gòu)實(shí)現(xiàn),；如果系數(shù)大，則將占用FPGA大量的存儲(chǔ)資源,，使運(yùn)算速度降低,。同時(shí)N-1個(gè)周期也使查表時(shí)間過(guò)長(zhǎng)，運(yùn)算速度降低,。
本文針對(duì)系數(shù)大小,、存儲(chǔ)資源、運(yùn)算速度的配置問(wèn)題,，對(duì)算法進(jìn)一步改進(jìn),、優(yōu)化，使算法達(dá)到存儲(chǔ)規(guī)模小,、運(yùn)算速度快,，進(jìn)一步提高運(yùn)算的性能。
1 算法的優(yōu)化
將Xm用下式表示：
根據(jù)二進(jìn)制補(bǔ)碼的運(yùn)算,，-Xm可表示為：
存在2M種不同的結(jié)果,，但其中φmn的取值為±1，結(jié)果呈現(xiàn)出正負(fù)對(duì)稱性。如果不考慮正負(fù)號(hào),，則只有2M-1種不同結(jié)果,。存儲(chǔ)規(guī)模減少了一半。用φmn作為L(zhǎng)UT的地址信號(hào),，查找表存儲(chǔ)器上一半地址對(duì)應(yīng)的預(yù)存值將會(huì)是下一半的取負(fù),。其硬件電路簡(jiǎn)化結(jié)構(gòu)如圖2所示。
其中括號(hào)內(nèi)的地址為X的下一半地址,。該地址查找上一半地址對(duì)應(yīng)的預(yù)存值,，同時(shí)作為Ctrl控制加/減器，完成下一半地址和上一半地址對(duì)應(yīng)的預(yù)存值的正負(fù)轉(zhuǎn)換,，送到累加器,，經(jīng)過(guò)N-1個(gè)周期即可獲得乘法累加的結(jié)果。
2 存儲(chǔ)規(guī)模的優(yōu)化
由圖2可知,，算法優(yōu)化后式(8)可以簡(jiǎn)化為：
雖然經(jīng)過(guò)算法優(yōu)化后存儲(chǔ)規(guī)模減少了一半,，但查找表的規(guī)模隨著m呈指數(shù)增加。為了進(jìn)一步減少所用查找表的規(guī)模,，可采用減小m的方法來(lái)實(shí)現(xiàn),。式(9)中
可以定義為：
3 查表速度優(yōu)化
為便于并行處理,可將圖3中的查找表設(shè)計(jì)為相同深度，則每一個(gè)輸人數(shù)據(jù)Xm(N-1),，分為C(為了與FPGA的4輸入LUT相關(guān),，令C為4的倍數(shù))段，則xmn可以表示為：
從式(12)并結(jié)合圖4可以看出,，查找表只需N/c-1個(gè)周期就可以得到內(nèi)積的結(jié)果,。與前面需N-1個(gè)周期相比較，速度提高了近c(diǎn)倍,，實(shí)現(xiàn)了高速,、高效運(yùn)算處理。其硬件電路簡(jiǎn)化結(jié)構(gòu)如圖4所示,。
用分布式算法將復(fù)雜的內(nèi)積運(yùn)算轉(zhuǎn)化為移位相加運(yùn)算,，可清晰地表示內(nèi)積結(jié)果。針對(duì)實(shí)現(xiàn)過(guò)程中系數(shù)大小,、存儲(chǔ)資源,、運(yùn)算速度的最佳配置問(wèn)題，從存儲(chǔ)規(guī)模,、算法,、查表速度三個(gè)方面對(duì)算法進(jìn)行進(jìn)一步改進(jìn)和優(yōu)化。算式推導(dǎo)過(guò)程層次清楚,，電路結(jié)構(gòu)合理,，使內(nèi)積算法達(dá)到存儲(chǔ)規(guī)模小,、運(yùn)算速度快的目的，性能得到大大提高,。
參考文獻(xiàn)
1 褚振勇．FPGA設(shè)計(jì)與應(yīng)用［M］．西安：西安電子科技大學(xué)出版社,，2002
2 徐以濤，王呈貴,，王金龍．基于DA算法的FIR濾波器硬件實(shí)現(xiàn)［J］．解放軍理工大學(xué)學(xué)報(bào)：自然科學(xué)版,，2003；4(3)：22～25
3 梁學(xué)東,，卜 天,，田日才.基于分布式算法和FPGA實(shí)現(xiàn)基帶信號(hào)成形的研究［J］．電子技術(shù)應(yīng)用，2004,；30(5)：67～69
4 單長(zhǎng)虹,，劉小平．基于VHDL語(yǔ)言的快速查表電路［J］．半導(dǎo)體技術(shù)，2002,；27(11)：42～46
5 畢占坤,，吳伶錫.FIR數(shù)字濾波器分布式算法的原理及FPGA實(shí)現(xiàn)［J］.電子技術(shù)應(yīng)用，2004,；30(7)
6 Wang Wei，Swamy M.N.S,，Ahmad,，M.O.Novel Design and FPGA Implemention of DA-RNS FIR Filters［J］.Journal of Circuits，Systems and Computers,，2004,；13(06)：1233～1249
7 Girard Patrick，Hbron Olivier,，Pravossoudovitch Serge et al.Delay Fault Testing of Look-Up Tables in SRAM-Based FPGAs［J］．Journal of Electronic Testing,，2005；21(1)：43～55
8 Lu Shyue-Kung,，Yeh Fu-Min,，Shih Jen-Sheng.Fault Detection and Fault Diagnosis Techniques for Lookup Table FPGAs［J］．VLSI Design 2002；15(1)：397～406