摘 要： 針對在FPGA中直接運用分布式算法" title="分布式算法">分布式算法實現(xiàn)內積運算時，內積運算的系數(shù)大小、存儲資源、運算速度" title="運算速度">運算速度難于達到最佳配置的問題，從算法、存儲規(guī)模、查表" title="查表">查表速度三個方面進行了詳細的分析和討論，并給出了相應的優(yōu)化和改進措施。
關鍵詞： FPGA 內積算法 優(yōu)化
基于分布式算法通過FPGA查找表" title="查找表">查找表實現(xiàn)內積運算，實現(xiàn)如下算法：
其中：Am為固定系數(shù)，Xm為輸入數(shù)據(jù)(Xm<1)。利用分布式算法將內積運算轉化為移位求和實現(xiàn)，用二進制補碼表示，將Xm表示成如式(2)形式：
式(3)中，由于Xmn的取值為0或1，所以
存在2M 種不同的結果。如果事先構造一個查找表，該表存儲了所有可能的組合值，即可以預先計算這2M個值，并存入查找表（LUT）中，用Xmn作為查找表的地址信號，將查找表的輸出結果移位(2-1運算)和相加，經(jīng)過N-1個周期即可直接獲得乘法累加的結果。這樣就將復雜的乘法累加運算轉化為移位相加運算。為提高運算速度，采用并行運算。其硬件電路簡化結構如圖1所示。
直接運用分布式算法實現(xiàn)內積運算,雖然實現(xiàn)了把復雜的內積運算轉化為移位相加運算，但其查找表的規(guī)模隨著系數(shù)呈指數(shù)增加。如果系數(shù)小，則可以方便地通過FPGA豐富的查找表結構實現(xiàn)；如果系數(shù)大，則將占用FPGA大量的存儲資源，使運算速度降低。同時N-1個周期也使查表時間過長，運算速度降低。
本文針對系數(shù)大小、存儲資源、運算速度的配置問題，對算法進一步改進、優(yōu)化，使算法達到存儲規(guī)模小、運算速度快，進一步提高運算的性能。
1 算法的優(yōu)化
將Xm用下式表示：
根據(jù)二進制補碼的運算，-Xm可表示為：
存在2M種不同的結果，但其中φmn的取值為±1，結果呈現(xiàn)出正負對稱性。如果不考慮正負號，則只有2M-1種不同結果。存儲規(guī)模減少了一半。用φmn作為LUT的地址信號，查找表存儲器上一半地址對應的預存值將會是下一半的取負。其硬件電路簡化結構如圖2所示。
其中括號內的地址為X的下一半地址。該地址查找上一半地址對應的預存值，同時作為Ctrl控制加/減器，完成下一半地址和上一半地址對應的預存值的正負轉換，送到累加器，經(jīng)過N-1個周期即可獲得乘法累加的結果。
2 存儲規(guī)模的優(yōu)化
由圖2可知，算法優(yōu)化后式(8)可以簡化為：
雖然經(jīng)過算法優(yōu)化后存儲規(guī)模減少了一半，但查找表的規(guī)模隨著m呈指數(shù)增加。為了進一步減少所用查找表的規(guī)模，可采用減小m的方法來實現(xiàn)。式(9)中
可以定義為：
3 查表速度優(yōu)化
為便于并行處理,可將圖3中的查找表設計為相同深度，則每一個輸人數(shù)據(jù)Xm(N-1)，分為C(為了與FPGA的4輸入LUT相關，令C為4的倍數(shù))段，則xmn可以表示為：
從式(12)并結合圖4可以看出，查找表只需N/c-1個周期就可以得到內積的結果。與前面需N-1個周期相比較，速度提高了近c倍，實現(xiàn)了高速、高效運算處理。其硬件電路簡化結構如圖4所示。
用分布式算法將復雜的內積運算轉化為移位相加運算，可清晰地表示內積結果。針對實現(xiàn)過程中系數(shù)大小、存儲資源、運算速度的最佳配置問題，從存儲規(guī)模、算法、查表速度三個方面對算法進行進一步改進和優(yōu)化。算式推導過程層次清楚，電路結構合理，使內積算法達到存儲規(guī)模小、運算速度快的目的，性能得到大大提高。
參考文獻
1 褚振勇．FPGA設計與應用［M］．西安：西安電子科技大學出版社，2002
2 徐以濤，王呈貴，王金龍．基于DA算法的FIR濾波器硬件實現(xiàn)［J］．解放軍理工大學學報：自然科學版，2003；4(3)：22～25
3 梁學東，卜 天，田日才.基于分布式算法和FPGA實現(xiàn)基帶信號成形的研究［J］．電子技術應用，2004；30(5)：67～69
4 單長虹，劉小平．基于VHDL語言的快速查表電路［J］．半導體技術，2002；27(11)：42～46
5 畢占坤，吳伶錫.FIR數(shù)字濾波器分布式算法的原理及FPGA實現(xiàn)［J］.電子技術應用，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