《電子技術(shù)應(yīng)用》
您所在的位置:首頁 > 可編程邏輯 > 業(yè)界動態(tài) > 基于FPGA的內(nèi)積算法優(yōu)化

基于FPGA的內(nèi)積算法優(yōu)化

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

  摘 要: 針對在FPGA中直接運(yùn)用分布式算法" title="分布式算法">分布式算法實(shí)現(xiàn)內(nèi)積運(yùn)算時(shí),內(nèi)積運(yùn)算的系數(shù)大小、存儲資源、運(yùn)算速度" title="運(yùn)算速度">運(yùn)算速度難于達(dá)到最佳配置的問題,從算法、存儲規(guī)模、查表" title="查表">查表速度三個(gè)方面進(jìn)行了詳細(xì)的分析和討論,并給出了相應(yīng)的優(yōu)化和改進(jìn)措施。


  關(guān)鍵詞: FPGA 內(nèi)積算法 優(yōu)化


  基于分布式算法通過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è)查找表,該表存儲了所有可能的組合值,即可以預(yù)先計(jì)算這2M個(gè)值,并存入查找表(LUT)中,用Xmn作為查找表的地址信號,將查找表的輸出結(jié)果移位(2-1運(yùn)算)和相加,經(jīng)過N-1個(gè)周期即可直接獲得乘法累加的結(jié)果。這樣就將復(fù)雜的乘法累加運(yùn)算轉(zhuǎn)化為移位相加運(yùn)算。為提高運(yùn)算速度,采用并行運(yù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ù)小,則可以方便地通過FPGA豐富的查找表結(jié)構(gòu)實(shí)現(xiàn);如果系數(shù)大,則將占用FPGA大量的存儲資源,使運(yùn)算速度降低。同時(shí)N-1個(gè)周期也使查表時(shí)間過長,運(yùn)算速度降低。
  本文針對系數(shù)大小、存儲資源、運(yùn)算速度的配置問題,對算法進(jìn)一步改進(jìn)、優(yōu)化,使算法達(dá)到存儲規(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ù)對稱性。如果不考慮正負(fù)號,則只有2M-1種不同結(jié)果。存儲規(guī)模減少了一半。用φmn作為LUT的地址信號,查找表存儲器上一半地址對應(yīng)的預(yù)存值將會是下一半的取負(fù)。其硬件電路簡化結(jié)構(gòu)如圖2所示。


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

  

  雖然經(jīng)過算法優(yōu)化后存儲規(guī)模減少了一半,但查找表的規(guī)模隨著m呈指數(shù)增加。為了進(jìn)一步減少所用查找表的規(guī)模,可采用減小m的方法來實(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é)構(gòu)如圖4所示。


  用分布式算法將復(fù)雜的內(nèi)積運(yùn)算轉(zhuǎn)化為移位相加運(yùn)算,可清晰地表示內(nèi)積結(jié)果。針對實(shí)現(xiàn)過程中系數(shù)大小、存儲資源、運(yùn)算速度的最佳配置問題,從存儲規(guī)模、算法、查表速度三個(gè)方面對算法進(jìn)行進(jìn)一步改進(jìn)和優(yōu)化。算式推導(dǎo)過程層次清楚,電路結(jié)構(gòu)合理,使內(nèi)積算法達(dá)到存儲規(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)基帶信號成形的研究[J].電子技術(shù)應(yīng)用,2004;30(5):67~69
4 單長虹,劉小平.基于VHDL語言的快速查表電路[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

本站內(nèi)容除特別聲明的原創(chuàng)文章之外,轉(zhuǎn)載內(nèi)容只為傳遞更多信息,并不代表本網(wǎng)站贊同其觀點(diǎn)。轉(zhuǎn)載的所有的文章、圖片、音/視頻文件等資料的版權(quán)歸版權(quán)所有權(quán)人所有。本站采用的非本站原創(chuàng)文章及圖片等內(nèi)容無法一一聯(lián)系確認(rèn)版權(quán)者。如涉及作品內(nèi)容、版權(quán)和其它問題,請及時(shí)通過電子郵件或電話通知我們,以便迅速采取適當(dāng)措施,避免給雙方造成不必要的經(jīng)濟(jì)損失。聯(lián)系電話:010-82306118;郵箱:aet@chinaaet.com。
主站蜘蛛池模板: a国产片| 污版网站| 亚洲黄色大片 | 欧美18-19| 精品欧美一区二区在线看片 | 5g影院天天爽爽 | 免费一级黄色毛片 | 亚洲国产成人在线视频 | 欧美激情国内自拍偷 | 国产精品成人va在线观看 | 深夜成人福利 | 国产情侣草莓视频在线 | 一级一级一片在线观看 | 午夜极品| 女bbbbxxxx毛片视频0 | 波多野结衣一级视频 | 亚洲自拍偷拍图 | 日本韩国一区二区三区 | 在线欧美69v免费观看视频 | 欧美激情精品久久久久久不卡 | 特级黄视频 | 免费黄色大片 | 轻轻啪qqp.cc | 五月天婷婷久久 | a级精品九九九大片免费看 a级精品国产片在线观看 | 日本欧美韩国专区 | 成人免费视频软件网站 | 天天操天天射天天爽 | h肉动漫在线视频无修无遮挡 | 最新亚洲情黄在线网站无广告 | www.av在线免费观看 | 欧美在线导航 | 制服丝袜第一页在线观看 | 99热成人精品免费久久 | 日韩三级伦理片 | 性欧美video另类hd亚洲人 | 久久精品国产国产精品四凭 | 色综合网站国产麻豆 | 日韩中文字幕在线观看视频 | 亚洲1区2区3区4区 | 欧美日韩成人午夜免费 |