《電子技術應用》
您所在的位置:首頁 > 可編程邏輯 > 業界動態 > 基于FPGA的內積算法優化

基于FPGA的內積算法優化

2008-03-31
作者:肖順文,陳亞軍

  摘 要: 針對在FPGA中直接運用分布式算法" title="分布式算法">分布式算法實現內積運算時,內積運算的系數大小、存儲資源、運算速度" title="運算速度">運算速度難于達到最佳配置的問題,從算法、存儲規模、查表" title="查表">查表速度三個方面進行了詳細的分析和討論,并給出了相應的優化和改進措施。


  關鍵詞: FPGA 內積算法 優化


  基于分布式算法通過FPGA查找表" title="查找表">查找表實現內積運算,實現如下算法:

  

  其中:Am為固定系數,Xm為輸入數據(Xm<1)。利用分布式算法將內積運算轉化為移位求和實現,用二進制補碼表示,將Xm表示成如式(2)形式:

  

  式(3)中,由于Xmn的取值為0或1,所以存在2M 種不同的結果。如果事先構造一個查找表,該表存儲了所有可能的組合值,即可以預先計算這2M個值,并存入查找表(LUT)中,用Xmn作為查找表的地址信號,將查找表的輸出結果移位(2-1運算)和相加,經過N-1個周期即可直接獲得乘法累加的結果。這樣就將復雜的乘法累加運算轉化為移位相加運算。為提高運算速度,采用并行運算。其硬件電路簡化結構如圖1所示。


  直接運用分布式算法實現內積運算,雖然實現了把復雜的內積運算轉化為移位相加運算,但其查找表的規模隨著系數呈指數增加。如果系數小,則可以方便地通過FPGA豐富的查找表結構實現;如果系數大,則將占用FPGA大量的存儲資源,使運算速度降低。同時N-1個周期也使查表時間過長,運算速度降低。
  本文針對系數大小、存儲資源、運算速度的配置問題,對算法進一步改進、優化,使算法達到存儲規模小、運算速度快,進一步提高運算的性能。

1 算法的優化
  將Xm用下式表示:

  

  根據二進制補碼的運算,-Xm可表示為:

  

  存在2M種不同的結果,但其中φmn的取值為±1,結果呈現出正負對稱性。如果不考慮正負號,則只有2M-1種不同結果。存儲規模減少了一半。用φmn作為LUT的地址信號,查找表存儲器上一半地址對應的預存值將會是下一半的取負。其硬件電路簡化結構如圖2所示。


  其中括號內的地址為X的下一半地址。該地址查找上一半地址對應的預存值,同時作為Ctrl控制加/減器,完成下一半地址和上一半地址對應的預存值的正負轉換,送到累加器,經過N-1個周期即可獲得乘法累加的結果。
2 存儲規模的優化
  由圖2可知,算法優化后式(8)可以簡化為:

  

  雖然經過算法優化后存儲規模減少了一半,但查找表的規模隨著m呈指數增加。為了進一步減少所用查找表的規模,可采用減小m的方法來實現。式(9)中可以定義為:

  

3 查表速度優化
  為便于并行處理,可將圖3中的查找表設計為相同深度,則每一個輸人數據Xm(N-1),分為C(為了與FPGA的4輸入LUT相關,令C為4的倍數)段,則xmn可以表示為:

  


  從式(12)并結合圖4可以看出,查找表只需N/c-1個周期就可以得到內積的結果。與前面需N-1個周期相比較,速度提高了近c倍,實現了高速、高效運算處理。其硬件電路簡化結構如圖4所示。


  用分布式算法將復雜的內積運算轉化為移位相加運算,可清晰地表示內積結果。針對實現過程中系數大小、存儲資源、運算速度的最佳配置問題,從存儲規模、算法、查表速度三個方面對算法進行進一步改進和優化。算式推導過程層次清楚,電路結構合理,使內積算法達到存儲規模小、運算速度快的目的,性能得到大大提高。
參考文獻
1 褚振勇.FPGA設計與應用[M].西安:西安電子科技大學出版社,2002
2 徐以濤,王呈貴,王金龍.基于DA算法的FIR濾波器硬件實現[J].解放軍理工大學學報:自然科學版,2003;4(3):22~25
3 梁學東,卜 天,田日才.基于分布式算法和FPGA實現基帶信號成形的研究[J].電子技術應用,2004;30(5):67~69
4 單長虹,劉小平.基于VHDL語言的快速查表電路[J].半導體技術,2002;27(11):42~46
5 畢占坤,吳伶錫.FIR數字濾波器分布式算法的原理及FPGA實現[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

本站內容除特別聲明的原創文章之外,轉載內容只為傳遞更多信息,并不代表本網站贊同其觀點。轉載的所有的文章、圖片、音/視頻文件等資料的版權歸版權所有權人所有。本站采用的非本站原創文章及圖片等內容無法一一聯系確認版權者。如涉及作品內容、版權和其它問題,請及時通過電子郵件或電話通知我們,以便迅速采取適當措施,避免給雙方造成不必要的經濟損失。聯系電話:010-82306118;郵箱:aet@chinaaet.com。
主站蜘蛛池模板: 日韩欧美中文字幕一区 | 欧美在线视频免费播放 | 日韩精品成人 | 中文字幕日本一区波多野不卡 | 国产精品小黄鸭一区二区三区 | 91导航在线 | 久久国产欧美 | yy4080午夜一毛片 | 无遮羞成人的动漫在线观看 | 日韩欧美在线观看成人 | 最近中文字幕高清视频2019 | 免费观看黄色a一级录像 | 天天干夜夜曰 | 国产综合色在线视频 | 久久99精品波多结衣一区 | 国产黄色片在线观看 | 涩涩亚洲 | 在线国产一区 | 国产成人精品日本亚洲专区6 | 性欧美极品xxxx欧美一区二区 | 天天拍夜夜添久久精品中文 | 日韩欧美高清在线观看 | 男女性潮高片无遮挡禁18 | 成年做羞羞免费观看视频网站 | 色天使久久综合给合久久97色 | 么公又大又硬又粗又爽小说 | 免费国产好深啊好涨好硬视频 | 国产成人永久免费视频 | 欧美成a人片在线观看 | 久久精品成人欧美大片免费 | 欧美日韩在线精品一区二区三区 | 激情综合色五月丁香六月亚洲 | 伊人久久亚洲综合天堂 | 欧美一级欧美三级在线 | 美女被草网站 | 国产白丝丝高跟在线观看 | 国产精品香蕉在线一区二区 | 欧美日韩亚洲国内综合网俺 | 最近2019免费中文字幕6 | 国产xxxx做受性欧美88 | 黄网站免费在线 |