国产日韩欧美一区二区三区三州_亚洲少妇熟女av_久久久久亚洲av国产精品_波多野结衣网站一区二区_亚洲欧美色片在线91_国产亚洲精品精品国产优播av_日本一区二区三区波多野结衣 _久久国产av不卡

?

位寬優(yōu)化中乘法運算的一種自動范圍分析方法

2014-06-06 03:06孫瑞一
哈爾濱工業(yè)大學學報 2014年3期
關鍵詞:比雪夫比率復雜度

孫瑞一,張 巖

(哈爾濱工業(yè)大學深圳研究生院網絡環(huán)境智能計算重點實驗室,518055 廣東深圳)

位寬優(yōu)化中乘法運算的一種自動范圍分析方法

孫瑞一,張 巖

(哈爾濱工業(yè)大學深圳研究生院網絡環(huán)境智能計算重點實驗室,518055 廣東深圳)

乘法是硬件平臺中最基本的非線性運算,而且在自動位寬優(yōu)化過程中,目前的范圍分析方法沒有在精確的范圍分析結果和計算復雜度之間做很好折衷.為了在較低的計算復雜度前提下更準確地分析乘法運算結果的范圍,提出了改進的仿射近似法(NAA).在改進的仿射近似法中,利用額外噪聲項來表示近似產生的誤差,并根據誤差的特點把誤差分成兩部分,在不增加計算復雜度的前提下更準確地估計誤差的范圍.新方法的計算復雜度是O(M1),其中M1是乘法的兩個操作數中非零噪聲個數的和.實例分析表明,利用該方法得到的乘法結果范圍的準確程度是用簡單估計法得到的準確程度的1.47倍,和切比雪夫近似法的準確度接近.

位寬優(yōu)化;范圍分析;乘法;仿射算術;仿射近似法

在硬件系統的設計中,為了得到較高的數據精度及動態(tài)范圍,算法模型都用浮點數表示.但是在硬件上實現浮點運算的代價很大,為了提高運行速度、降低功耗、節(jié)省面積,在硬件實現階段數據一般都采用定點數表示.將浮點數轉化為定點數的過程被稱為位寬優(yōu)化,也叫做定點化.位寬優(yōu)化的目的是在滿足系統規(guī)格要求的前提下尋找最佳的定點數位寬組合使系統的代價(面積、功耗、速度等)最小.位寬優(yōu)化包括范圍分析(對整數部分的優(yōu)化)和精度分析(對小數部分的優(yōu)化)兩個步驟.

位寬優(yōu)化是NP-h(huán)ard問題[1],常用的分類方法有動態(tài)法[2-6]和靜態(tài)法[7-10].動態(tài)法通過對大量的測試向量進行反復的蒙特卡洛仿真來確定信號的位寬.它的結果質量較高,但優(yōu)化時間長,甚至占到整個設計周期的50%以上[11].而且,動態(tài)法不能保證測試向量沒有覆蓋到的情況也滿足系統規(guī)格要求.靜態(tài)法使用代碼分析手段來推導出信號的位寬,它不需要測試向量,所以它的執(zhí)行速度快、人為干擾因素小,而且簡便易行,適于大規(guī)模系統的自動優(yōu)化分析.

在硬件平臺,如Xilinx公司的FPGA或全定制的ASIC芯片中,乘法運算是最基本也是最常用的非線性運算.其他的非線性運算,如除法、余弦、對數等超越函數一般都是通過加、減、乘這些基本運算計算的.但是目前乘法運算的范圍分析的靜態(tài)法得不到范圍的精確解,所以對乘法運算結果的位寬優(yōu)化的準確程度就關系到整個電路的位寬優(yōu)化的準確程度.本文討論基于靜態(tài)法的對乘法結果的范圍分析方法.

區(qū)間算術(interval arithmetic,IA)是1960年由Moore[12]提出的解決范圍分析的方法.Cmar等[13]首次采用IA對信號的變化范圍進行分析.但是IA在估計信號范圍時過于保守,甚至不切實際.

仿射算術(affine arithmetic,AA)保留了區(qū)間之間的相關性,這使得它比IA更精確.AA非常適于對線性操作結果的范圍分析.但是AA不能為乘法等非線性操作提供準確的仿射形式.為解決該問題,Stolfi等[14]提出了乘法的仿射近似法,包括簡單估計法和切比雪夫近似法.簡單估計法計算效率高,但誤差較大,分析范圍最多可達到真實范圍的4倍.這種誤差沿著數據流累積到輸出,會導致誤差爆炸,這限制了它在大系統中的應用;切比雪夫近似法利用比簡單估計法更精確的仿射形式,實現較好的范圍分析結果,但是它的計算過程太復雜所以不適合在大系統中應用.

為了解決計算效率和計算復雜度之間的問題,Zhang等[15]提出了一種叫N-級近似的,在分析精度和復雜度之間作折中的方法.其分析結果比用簡單估計法得到的準確,比切比雪夫近似法簡單.但是仍不能滿足大系統對分析范圍的精度和復雜度的要求.Pang等[16]提出了一種新的范圍分析方法,它混合了傳統的IA、AA和算術變換(arithmetic transform,AT),能得到比 AA更精確的范圍結果,但是執(zhí)行時間比AA長很多.所有這些對AA的改進方法,都以犧牲計算復雜度為代價來換取分析的精度.它們都是把自變量的仿射形式看成是一個整體,沒有考慮仿射形式中的每一個噪聲,這樣就忽略了不同噪聲之間的獨立性和相同噪聲在不同變量中的相關性.

為了更簡便、更精確的實現對乘法運算結果的范圍分析,本文提出一種名為改進的仿射近似法(novel affine arithmetic approximation,NAA)的新的仿射近似法.NAA利用一個仿射形式近似的表示乘法運算的結果,并利用增加的額外噪聲項來表示近似產生的誤差.為了利用現有方法忽略的獨立性和相關性,這個誤差用各個噪聲來表示,并且在不增加計算復雜度的前提下更準確的估計誤差的范圍,從而減少了新增噪聲的系數.這種方法能比簡單估計法得到更準確的分析范圍,而且計算復雜度和簡單估計法一樣,比切比雪夫近似法更簡單.

1 仿射算術

為了更清楚的分析仿射近似的過程和更方便的推導NAA,首先介紹仿射算術的基礎知識.

仿射算術用一次多項式的仿射形式^x表示一個未知的信號x為

式中:εi=[-1,1].對于未知信號 x,x0表示它的中心值;εi為第i個噪聲,代表信號x的一個獨立的、未知的噪聲源;xi為這個噪聲的系數;xiεi、x0+xiεi分別為噪聲項.

令x0=(xmax+xmin)/2,x1=(xmax-xmin)/2,信號的范圍區(qū)間ˉx=[xmin,xmax]可以轉化為等價的仿射形式為

AA通過與計算鏈中的其他信號共享噪聲εi來保留信號之間的相關性.

乘法的簡單估計法的仿射形式為

這種方法的分析結果誤差很大,但是其計算復雜度是O(M1),其中M1=max(n1,n2),n1、n2分別為信號x、y中非零噪聲的個數.

式中:m、n分別為(x-x0)(y-y0)的最大值和最小值.

計算最值m和n的計算復雜度是O(M2log M2),其中 M2=n1+n2.

2 乘法的改進的仿射近似法

2.1 算法分析

自變量為仿射形式的乘法,可以表示為

因為z不是仿射形式,選擇一個仿射形式fz來近似的表示它.式(1)的前3項組成了一個仿射形式,為了簡單,把這個仿射形式作為近似的仿射形式,即

式中:fz為z的近似表示,所以fz與z之間存在誤差,引入一個新的獨立噪聲項來表示這個誤差df,即

計算df的真實最大值和最小值的計算量難以承受,所以dfmax、dfmin分別為df的近似最大值和近似最小值.dfmax、dfmin與真實的最大值和最小值越接近,^z的形式越準確.

綜上所述,z的仿射形式可以記為

2.2 仿射形式

df可以表示為

式中:εi,εj=[-1,1].估計df的近似的最大值和最小值的最簡單的方法就是把εi,εj的最大值和最小值代入.根據式(2),當 i=j時,有 xiyjεiεj=.把εi,εj=[-1,1]代入,xiyi估計的近似的最大值和最小值比xiyjεiεj更精確,而且沒有增加計算復雜度.因此把df分成兩部分,即

距離df可以記為

d1的最大值和最小值分別為

和它等價的仿射形式為

d2的最大值和最小值分別為

和它等價的仿射形式為

計算一次乘法要引入兩個獨立噪聲會使接下來的計算噪聲越來越多.所以需要化簡根據式(4),的范圍為

和它等價的仿射形式為

式(4)中的εn+1和εn+2之間有相關性,但是將df分為d1和d2并沒有考慮它們之間的相關性,所以df的真實范圍一定比的范圍小,這是過估計.因此,NAA的準確程度比切比雪夫近似法的準確程度稍低.

2.3 乘法的改進的仿射近似法的表達式及計算復雜度分析

有了式(2)和新引入的式(5),乘法的改進的仿射近似法的表達式為

設n1、n2分別為^x、^y中非零噪聲的個數,M1=max(n1,n2)為n1和n2的最大值,M2=n1+n2,則切比雪夫近似法的計算復雜度為 O(M2log M2)[14].簡單估計法的計算復雜度為O(M1).

為了計算NAA的計算復雜度,把式(6)改寫為

式(7)的計算復雜度為

可以看出,NAA的計算復雜度和簡單估計法的一樣,都是O(M1).很明顯M1<M2,所以有O(M1)<O(M2log M2).根據計算復雜度的分析,NAA比切比雪夫近似法要簡單.

3 實例分析

為了比較NAA的性能,本文以包含乘法的計算為例.第1個實例是多項式近似.第2個實例是B-splines.這兩個實例均來自于文獻[8].第3個實例是多變量多項式,來自于文獻[17-19].將仿射算術用C++實現,乘法分別采用簡單估計法、切比雪夫近似法和改進的仿射近似法.這些實例的計算平臺是內存為2.99 G的Intel(R)Pentium(R)CPU G630@2.7 GHz的32位雙核PC.

3.1 實例

實例1 多項式近似

對 y=ln(1+x),x=[0,1]的多項式近似進行信號范圍分析,采用文獻[20]的4級多項式表達為

其中,5個四舍五入到小數點后第4位的系數由多項式曲線擬合的方法獲得.

實例2 B-splines

B-splines常用于圖像卷繞,它的基本函數B0、B1、B2、B3分別定義如下,其中,輸入 u= [0,1].

實例3 變量多項式

考察表1中的8個多變量多項式.

表1 多變量多項式函數及輸入范圍

3.2 3種方法分析范圍的比較

利用仿射近似法計算得到的變量范圍用分析范圍來表示.用分析范圍比率來表示分析范圍的準確程度.分析范圍比率是用3種方法得到的分析范圍的區(qū)間間隔(ymax-ymin)與真實范圍的區(qū)間間隔的比值,表示了分析范圍的區(qū)間間隔是真實范圍的區(qū)間間隔的倍數.其中,ymax、ymin分別為變量的最大值和最小值.分析范圍比率越接近1說明分析范圍越接近真實范圍.

表2給出了用3種方法計算得到的3個例子的分析范圍和范圍比率.它顯示了利用NAA計算得到的分析范圍全部覆蓋了真實的輸出范圍.對于這些例子,利用簡單估計法計算得到的范圍比率從1.04~281.19;利用切比雪夫近似法計算得到的范圍比率從1.03~233.66;利用NAA計算得到的范圍比率從1.03~221.78.利用NAA得到的范圍比率是利用簡單估計法得到的范圍比率的0.18~0.99倍,范圍比率倍數的平均是0.68倍;利用NAA計算得到的范圍的比率是利用切比雪夫近似法計算得到的范圍比率的0.33~1.39倍,范圍比率倍數的平均是0.99倍.這說明,平均來看,利用NAA計算得到的分析范圍的準確程度是用簡單估計法計算得到的分析范圍的準確程度的1.47倍,和切比雪夫近似法的分析范圍的準確度接近.

表2 3種方法分析范圍和范圍比率的比較

對于實例3中的第7個函數,利用3種靜態(tài)法得到的范圍比率都在200以上.這是因為這個函數最終的乘法中的兩個乘數都包含很多乘法,每一次乘法運算都會產生誤差,而且這兩個乘數都是相同自變量的函數,它們的相關性很強,這種情況下兩個乘數的誤差會相互放大,使最終得到的范圍結果比真實范圍大很多.所以靜態(tài)法不適用于對這種情況的范圍分析,動態(tài)法會得到更準確的分析范圍.

從表2可以看出,這3種方法有一個共同的不足之處,即分析范圍的下限誤差較大.這是因為當變量x用仿射形式表示時,x的范圍是相對于x0中心對稱的.在計算過程中,x0是由計算鏈中變量決定的,很難保證它是在x范圍的中心.當^x要滿足變量范圍的上限或下限時,由于x0不在x范圍的中心,^x表示的x范圍的下限或上限就有了較大的誤差.在本文所舉的例子中,都是上限大于下限的,所以表現為分析范圍下限誤差較大.

3.3 3種方法整數位寬和執(zhí)行時間的比較

變量的整數位寬可以由變量范圍推導.表3列出了3種方法得到的輸出變量位寬和CPU運行時間.B-splines的4個基本函數是在同一個程序中完成的,所以只有一個CPU時間.NAA最多比簡單估計法節(jié)省2個bit位寬,比切比雪夫近似法最多節(jié)省1個bit位寬.與簡單估計法相比,NAA需要0.95~1.39倍的CPU時間,而切比雪夫近似法需要54.01~57.97倍的 CPU時間.NAA和簡單估計法有著近似的執(zhí)行時間,不到切比雪夫近似法執(zhí)行時間的1/50.

表3 3種方法得到的整數位寬和CPU時間的比較

4 結論

1)利用一個仿射形式近似的表示乘法運算的結果,并利用額外噪聲項來表示近似產生的誤差.

2)把近似產生的誤差分成兩部分,分別用兩個噪聲來表示,能得到更精確的近似誤差的范圍.

3)與以往的范圍分析的改進方法相比,新方法在不增加計算復雜度的前提下的,更準確的估計變量的范圍.實例分析顯示NAA的分析范圍的準確程度和切比雪夫近似法的準確程度接近,比簡單估計法更準確.而且,它的計算復雜度和簡單估計法的一樣,都是O(M1),比切比雪夫近似法的小.

[1]CONSTANTINIDES G,WOEGINGER G.The complxity ofmultiple wordlength assignment[J]. Applied Mathematics Letters,2002,15(2):137-140.

[2]KUM K I,SUNG W.Combined word-length optimization and highlevel synthesis of digital signal processing systems[J].IEEE Trans on Computer-Aided Design Integrated Circuits,and Systems,2001,20(8):921-930.

[3]CAFFARENA G,CARRERAS C,LOPEZ J A,et al.SQNR estimation of fixed-point DSP algorithms[J].Eurasip Journal on Advances in Signal Processing,2010,2010(21):1-12.

[4]朱珂,華林,周曉方,等.JPEG2000中小波濾波器的定點分析及其VLSI實現[J].固體電子學研究與進展,2004,24(4):466-471,504.

[5]馬志強,季振洲,胡銘曾.基于超窄數據的低功耗數據Cache方案[J].計算機研究與發(fā)展,2007,44(5):775-781.

[6]BANCIU A,CASSEAU E,MENARD D,et al.Stochastic modelingforfloating-pointto fixed-point conversion[C]//Proceedings of IEEE Workshop on Signal Processing Systems(SiPS).Beirut,Lebanon:IEEE Computer Society Press,2011:180-185.

[7]SARBISHEI O,RADECKA K,ZILIC Z.Analytical optimization of bit-widths in fixed-point LTI systems[J].IEEE Trans on Computer-Aided Design of Integrated Circuits and Systems,2012,31(3):343-355.

[8]LEE D-U,GAFFAR A A,CHEUNG R C,et al.Accuracy guaranteed bit-width optimisation[J].IEEE Trans on Computer-Aided Design of Integrated Circuits and Systems,2006,25(10):1990-2000.

[9]ROCHER R,MENARD D,SCALART P.Analytical approach for numerical accuracy estimation of fixed-point systems based on smooth operations[J].IEEE Trans on Circuits and Systems I-Regular Papers,2012,59(10):2326-2339.

[10]KINSMAN A B,NICOLICI N.Computational vectormagnitude-based range determination for scientific abstract data types[J].IEEE Trans on Computers,2011,60(11):1652-1663.

[11]KEDING H,WILLEMS M, COORS M, et al.FRIDGE:a fixed-point design and simulation environment[C]//Proceedings of Design,Automation and Test in Europe.Paris:DATE,1998:429-435.

[12]MOORE R E.Interval Arithmetic and Automatic Error Analysis in Digital Computing[D].California:Stanford University,1962.

[13]CMAR R,RIJNDERS L,SCHAUMONT P,et al.A methodology and design environment for DSP ASIC fixed point refinement[C]//Proceedings of Design,Automation and Test in Europe.Munich:ACM,1999:271-276.

[14]STOLFI J,de FIGUEIREDO L H.Self-validated Numerical Methods and Applications[M].Rio De Janeiro:Brazilian Mathematics Colloquium monograph,IMPA,1997.

[15]ZHANG Linsheng,ZHANG Yan,ZHOU Wenbiao.Tradeoff between Approximation accuracy and complexity for range analysis using affine arithmetic[J].Journal of Signal Processing Systems,2010,61(3):279-291.

[16]PANG Y,RADECKA K.An efficient algorithm of performing range analysisforfixed-pointarithmetic circuits based on SAT checking[C]//Proceedings of IEEE International Symposium on Circuits and Systems(ISCAS).Rio de Janeiro,BRAZIL:IEEE Computer Society Press,2011:1736-1739.

[17]SHEKHAR N,KALLA P,ENESCU F.Equivalence verification of arithmetic datapaths with multiple wordlength operands [C]//Proceedings of Design,Automation and Test in Europe.Munich:DATE,2006:824-829.

[18]GOPALAKRISHNAN S,KALLA P,MEREDITH M B,et al.Finding linear building-blocks for RTL synthesis of polynomial datapaths with fixed-size bit-vectors[C]//Proceedings of International Conference on Computer-Aided Design.San Jose:IEEE Computer Society Press,2007:143-148.

[19]SHOU Huahao,SONG Wenhao,SHEN Jie,et al.A recursive taylor method for ray casting algebraic surfaces[C]//Proceedings ofInternationalConference on Computer Graphics and Virtual Reality,Las Vegas:CGVR,2006:196-204.

[20]HORNER W G.A new method of solving numerical equations of all orders,by continuous approximation[J].Philosophical Transactions of the Royal Society of London,1819,109:308-335.

A range analysis in automatic word length optimization for multiplication

SUN Ruiyi,ZHANG Yan
(Key Laboratory of Network Oriented Intelligent Computation,Shenzhen Graduate School,Harbin Institute of Technology,518055 Shenzhen,Guangdong,China)

To achieve more accurate result and lower computational complexity of range analysis for multiplication in automatic word length optimization,this paper presents a novel refined affine approximation method of multiplication for range analysis in automatic word length optimization,which is named novel affine arithmetic approximation(NAA).In NAA,a new noise term represents the error which is caused by approximation.This error is estimated more accurately without increasing the computational complexity.The computational complexity of NAA is O(M1),where M1denotes the total of the nonzero noise of the two multipliers.In experiments,the accuracy of the range using NAA is 1.47 times of that using trivial range estimation,and the same as that using Chebyshev approximation.

word-length optimization;range analysis;multiplication;affine arithmetic;affine approximation method

TP391.72

A

0367-6234(2014)03-0043-06

2013-02-27.

深圳市科技研發(fā)基礎研究計劃資助項目(JC201005260168A).

孫瑞一(1980—),女,博士研究生;

張 巖(1969—),男,教授,博士生導師.

張 巖,ianzh@foxmail.com.

(編輯 張 紅)

猜你喜歡
比雪夫比率復雜度
一類具有時滯及反饋控制的非自治非線性比率依賴食物鏈模型
一種低復雜度的慣性/GNSS矢量深組合方法
第四類切比雪夫型方程組的通解
求圖上廣探樹的時間復雜度
基于方差的切比雪夫不等式的推廣及應用
基于切比雪夫有理逼近方法的蒙特卡羅燃耗計算研究與驗證
切比雪夫多項式零點插值與非線性方程求根
某雷達導51 頭中心控制軟件圈復雜度分析與改進
一種適用于微弱信號的新穎雙峰值比率捕獲策略
出口技術復雜度研究回顧與評述