李凱磊,楊文強,王倫耀

（寧波大學 信息科學與工程學院,浙江 寧波 315211）

在數(shù)字電路設(shè)計中,邏輯正確是設(shè)計的首要目標.但在實際應(yīng)用中,如涉及圖像、音頻處理等多媒體應(yīng)用方面,因人類感知能力限制,即使存在一定范圍內(nèi)的錯誤輸出,也不影響人們的視聽效果.實際應(yīng)用中的容錯特性為邏輯電路的優(yōu)化提供了一條新途徑.利用近似計算技術(shù)實現(xiàn)電路邏輯優(yōu)化,其本質(zhì)就是通過降低電路的輸出精度來實現(xiàn)電路簡化,進而達到電路的功耗、面積或者時延等性能指標的優(yōu)化.

在集成電路設(shè)計中,加法器是一種被廣泛應(yīng)用的電路單元,加法器性能與整個系統(tǒng)性能關(guān)系密切.高性能加法器設(shè)計一直是學術(shù)界和工業(yè)界高度關(guān)注的問題[1-2].在誤差允許的情況下,引入近似加法器是提高加法器性能的一種有益嘗試.考慮到近似加法器的輸出誤差與發(fā)生錯誤輸出位的權(quán)重有關(guān),權(quán)重到高的輸出位發(fā)生錯誤將引起更大的誤差,并且輸出誤差的大小也是近似加法器設(shè)計過程中一個關(guān)鍵指標,為此本文提出了一種三段式加法器設(shè)計,該設(shè)計基本思想是在低權(quán)重輸出位用簡單的邏輯門,甚至常數(shù)來代替全加器,而在高權(quán)重部分則采用精確加法器來實現(xiàn),從而在誤差大小與電路性能之間實現(xiàn)折中.

1 相關(guān)工作

1.1 研究現(xiàn)狀

已有的近似加法器在結(jié)構(gòu)上大致分為二段式和多段式兩種類型[3].

二段式近似加法器包含兩部分,即由精確加法器構(gòu)成MSB(More Significant Bits)部分,以及由近似加法器構(gòu)成的LSB(Less Significant Bits)部分,其中,LSB 部分一般采用無進位近似加法器.此類近似加法器的每一位都單獨進行運算,不產(chǎn)生或接收進位信號,因而可以減少因進位產(chǎn)生的延時,進而提高電路的運算速度.

二段式近似加法器的這種結(jié)構(gòu)可以在增加有限輸出誤差的情況下,實現(xiàn)電路面積、延遲以及功耗等優(yōu)化.現(xiàn)有的低位或門加法器(Lower Part OR Adder,LOA)[4]、容錯加法器I(Error Tolerant Adder-I,ETA-I)[5]等均為二段式近似加法器.

其中,ETA-I 加法器的精確部分由行波進位加法器實現(xiàn),近似部分每一位求和運算全部使用XOR模塊代替.該模塊在第i位輸入Ai和Bi分別在“00”“01”或“10”的時候進行正常XOR 運算;而在“11”的時候,從第i位開始至最低位,求和的輸出結(jié)果全部被設(shè)置為“1”.此類加法器的輸出誤差比較小,但因其高位部分由傳統(tǒng)的精確加法器構(gòu)成,且通過XOR 門以及控制模塊組成低位,因此相對于某些近似加法器電路,其電路面積開銷較大.

現(xiàn)有多段式近似加法器包括精度可配置加法器II(Accuracy Configurable Approximate Adder-II,ACA-II)[6]、容錯加法器II(Error Tolerant Adder-II,ETA-II)[7]、預(yù)測進位選擇加法器(Speculative Carry Select Addition,SCSA)[8]和通用精度可配置加法器(Generic Accuracy Configurable Adder,GeAr)[9]等.多段式加法器一般由多個并行子加法器模塊組成,每個子加法器模塊分為MSB 部分與LSB 部分.其中MSB 部分用于輸出一部分求和結(jié)果,LSB 部分用于預(yù)測進位信號,并傳遞給MSB 部分,不用于求和計算.最后所有子加法器MSB 部分的求和結(jié)果組合起來即為此類近似加法器的最終求和輸出.此類多段式加法器雖然可以顯著降低延遲,但是因其由多個子加法器模塊構(gòu)成,電路面積相較于其他近似加法器增加很多.

ETA-II 加法器結(jié)構(gòu)如圖1 所示,n位加法器被分割成m個子加法器模塊,每個模塊中包含1 個k位行波進位加法器(Ripple Carry Adder,RCA)模塊,以及1 個k位超前進位加法器(Carry Lookahead Adder,CLA)模塊,分別用于2 個加數(shù)對應(yīng)字段求和以及進位信號預(yù)測.

圖1 ETA-II 加法器

從圖1 可知,ETA-II 多段式加法器第h個子加法模塊的進位僅僅與當前k位輸入和第(h-1)個子加法模塊的k位輸入有關(guān),1 ≤h≤ (m-1),因此該加法器可以將進位鏈深度由原來的n縮短到2k,進而顯著減小電路時延.但同時因進位鏈被截斷,使得在某些輸入組合下,ETA-II 會產(chǎn)生很大的誤差.以圖2 所示12 位加法器為例,該加法器包含3 個子加法模塊,本文稱之為ETA-II-3 加法器.當輸入2 個12 位的加數(shù)為A[11:0]=“000011111111”(255)和B[11:0]=“000000000001”(1)時,由于處于高位子加法模塊的進位來自于次高位子加法電路的進位輸出,在圖2 所示的輸入組合時,次高位子加法電路的進位輸出為0,導(dǎo)致該12位加法器最終的輸出為0,而不是256,產(chǎn)生很大誤差.

1.2 計算誤差評價指標

近似加法器的計算誤差通常采用誤差距離(Error Distance,ED),以及與誤差距離緊密相關(guān)的平均誤差距離(Mean Error Distance,MED)、相對誤差距離(Relative Error Distance,RED)、平均相對誤差距離(Mean Relative Error Distance,MRED)和歸一化誤差距離(Normalized Mean Error Distance,NMED)等指標來衡量[10].

誤差距離(EED)定義為近似加法器所獲得的值與正確結(jié)果之間差值的絕對值.式(1)中Rc和Re分別表示正確值和近似值,且均用十進制表示:

平均誤差距離(EMED)為α個誤差距離取平均值:

相對誤差距離(ERED)是誤差距離與正確值比:

平均相對誤差距離(EMRED)為α個相對誤差距離取平均值:

歸一化誤差距離是平均誤差距離的歸一化:

加法器精度(Accuracy,ACC)表示特定輸入的輸出“正確”程度,其值范圍為0%～100%,定義為:

最低可接受精度(Minimum Acceptable Accuracy,MAA)表示近似加法器輸出結(jié)果精度最低的百分值,而可接受結(jié)果概率(Acceptance Probability,AP)是指加法器精度高于最小可接受精度的概率,0≤AAP≤1:

2 三段式高性能非精確加法器

2.1 三段式低功耗非精確加法器介紹

本文提出的三段式n位高性能非精確加法器結(jié)構(gòu)如圖3 所示,n=4z,z∈ {1,2,3,4,…} .該近似加法器被分割成三部分.第一部分為加法器低位部分,位寬為n/4,這部分每一位的輸出結(jié)果被設(shè)置為常數(shù)“1”,也稱為CON 塊;第二部分為加法器中間部分,位寬為n/4,用一個二輸入邏輯門代替一位全加器,這部分電路也稱TP 塊.剩余部分為精確計算部分,由RCA 構(gòu)成.

圖3 三段式高性能非精確加法器結(jié)構(gòu)圖

2.1.1 CON 塊

CON 塊為常數(shù)塊,即無論A[n/4 -1:0]和B[n/4 -1:0]輸入什么值,輸出結(jié)果S[n/4 -1:0]將全部被置為常數(shù),這樣將使延遲、面積和功耗得到大幅度降低.由于平均誤差距離是衡量近似加法器的一個關(guān)鍵指標,CON 塊的常數(shù)輸出設(shè)置應(yīng)該盡可能引入較小的平均誤差.

設(shè)A、B為2 個加數(shù),A、B為整數(shù),且0≤A≤K-1,0 ≤B≤K-1.則A、B可以產(chǎn)生K2種輸入組合.設(shè)Si為其中一種輸入組合的和,0≤i≤(K2-1),則所有輸入情況下加法器輸出的求和結(jié)果為:

因此,其求和的平均值為:

顯然,對于位寬為n/4的CON 塊,為了使CON 塊對應(yīng)的平均誤差距離最小,CON 塊的輸出應(yīng)該為 2n/4-1,即置CON 塊的所有輸出為“1”.

2.1.2 TP 塊

TP 塊輸出結(jié)果S[n/2 -1:n/4]由A[n/2 -1:n/4]和B[n/2 -1:n/4]的每一位單獨進行基本二輸入邏輯運算所得,且每一位不產(chǎn)生也不接收任何進位信號,從而減少電路面積和時延.

從表1 可知,XOR 門的輸出與加法器的求和輸出一致,但沒有進位信號;OR 門的4 個輸出中有3個與加法器的輸出一致,而AND 門只有1 個輸出與加法器的輸出一樣.因此,在TP 塊中不考慮AND 門.

表1 TP 塊邏輯門選擇與半加器結(jié)果比較

相比OR 門,雖然在4 個輸入組合中,XOR 門的輸出均與加法器和的輸出一樣,但由于在TP 塊中各位之間沒有進位,因此在2 個加數(shù)的某一位輸入均為“1”時,XOR 門的輸出實際上是“0”,而OR 門的輸出為“1”,反而OR 門引起的誤差更小.另外,對于二輸入OR 門而言,只有其中一個輸入為“0”時,另一個的輸入變化才能引起輸出變化,而二輸入XOR 門的任何輸入變化都會反映到輸入端,因此相比OR 門,XOR 門對輸入的變化更敏感,其動態(tài)功耗也將更大.此外,XOR 的電路面積要比OR 門大.在本文中,將同時給出OR 門和XOR 替代全加器后的電路性能比較結(jié)果.

2.1.3 RCA 塊

三段加法器的高位部分由精確加法器組成.對于一個n位二進制,其對應(yīng)的十進制可表示為:

從上式可知,由于高位權(quán)重大于低位權(quán)重,因此同樣某一位上出錯,高位錯誤引起的誤差會更大,這也就是TSA 加法器在高位采用精確加法器的原因.本文設(shè)計中,高位部分采用行波加法器,此類加法器結(jié)構(gòu)簡單,但進位鏈長.由于本設(shè)計中將進位鏈進行了截斷,長度只有原來的一半,因此可有效減少整個電路的時延.

2.2 三段式非精確加法器誤差分析及改進

由圖3 結(jié)構(gòu)可知,該近似加法器產(chǎn)生誤差的情況均取決于TP 塊和CON 塊.相比與CON 塊,TP塊在圖3 的結(jié)構(gòu)中處于高位段.因此TP 塊和CON塊引起誤差的大小主要由TP 塊決定.

從表1 可知,在二進制加法中,某一位的2 個加數(shù)的4 種輸入組合中,當TP 塊中的二輸入邏輯門采用XOR 門時,求和輸出均正確,但是在輸入組合為“11”時,沒有產(chǎn)生進位.當TP 塊中的二輸入邏輯門采用OR 門時,在輸入組合為“11”時,求和輸出錯誤,同時沒有產(chǎn)生進位,其他3 種輸入組合均正確.從上面分析不難看出,TP 塊產(chǎn)生的求和輸出結(jié)果小于正確值.為減少TP 塊的誤差距離,本文將TP 進行了如下改進.

假設(shè)TP 塊長度為L,則將第位的二輸入邏輯門輸出用常量“1”來代替.同時,考慮到TP 塊最高位為“1”時,肯定會產(chǎn)生進位輸出,因此將TP 塊結(jié)構(gòu)改進為圖4 所示結(jié)構(gòu).

圖4 改進后TP 塊結(jié)構(gòu)圖

表2 為在位寬為16 位情況下,圖4 結(jié)構(gòu)的TP塊與圖3 結(jié)構(gòu)的TP 塊在隨機輸入情況下與正確值的錯誤誤差比較結(jié)果.

表2 修改后16 位TP 模塊加法精度比較

表2 中,TPOR和TPXOR分別表示TP 塊中二輸入邏輯門采用OR 門和XOR 門后電路的各性能參數(shù),TPOR-1和TPXOR-1分別表示采用圖4 結(jié)構(gòu)后的電路性能參數(shù).并且表2 中,各誤差參數(shù)是在隨機產(chǎn)生105種輸入組合,利用MATLAB 模擬得到.面積和功耗參數(shù)利用Design Complier 在fast_1v32c0 工藝庫下得到.

通過表2 可知,在8 位寬下,TP 塊采用OR 門所產(chǎn)生的計算誤差相較于采用XOR 門要小,且在電路功耗和電路面積方面的表現(xiàn)也比采用XOR 門要好.采用圖4 結(jié)構(gòu)的TPOR-1與僅由OR 門構(gòu)成的TPOR相比,在計算精度和減小電路開銷方面均有提升.

結(jié)合表2 的結(jié)果,本文提出的近似加法器的結(jié)構(gòu)如圖5 所示,并稱該電路為TSA 加法器.其中,在TP 塊中采用二輸入OR 門.

圖5 TSA 加法器結(jié)構(gòu)圖

3 實驗結(jié)果

本節(jié)將對文中提出的近似加法器與幾種經(jīng)典的近似加法器在面積、延遲、功耗和精度等方面的特性進行比較.為獲得加法器電路的面積、功耗和時延數(shù)據(jù),先將近似加法器用Verilog HDL 語言描述,然后用Design Complier進行綜合得到,其中綜合過程中用到的工藝庫為fast_1v32c0.表3 即為實驗結(jié)果.

表3 各16 位加法器電路性能比較

表3 中,近似加法器LOA、ETA-I、ETA-II-2、ETCA[11]和TSA 的加數(shù)位寬均為16 位,且高8 位均采用RCA 精確加法器.從表中可以看出,本文所提出的TSA 近似加法器總體性能較好.由于TSA 中間部分采用部分精確電路,通過OR 門代替一位全加器,低位部分每一位輸出結(jié)果都被設(shè)置為常數(shù)1,這種設(shè)計有利于TSA 在面積、功耗和時延上的優(yōu)化.相較于RCA 面積、功耗、功耗延遲積(Power Delay Product,PDP)和面積延遲積(Area Delay Product,ADP)分別下降約43%、57%、85%和81%.與ETCA 相比,TSA 加法器在面積、功耗和面積功耗積方面分別有大約15%、9%、22%的改善,相對于LOA、ETA-I、ETA-II-2 各方面都具有不同程度的提高.由于上述電路均采用進位鏈截斷技術(shù),進位鏈長度相仿,因此各電路的時延均接近.而ETA-II-2 由于將求和運算與進位信號預(yù)測分為兩部分,導(dǎo)致時延比較長.

計算誤差是衡量近似加法器的一個關(guān)鍵指標.本文中各近似加法器的計算誤差是利用MATLAB對各近似加法器進行建模,并輸入105個隨機數(shù)進行仿真獲得.表4 即為各近似加法器計算誤差仿真結(jié)果.

表4 各16 位加法器計算誤差比較

不難看出,TSA 近似加法器因TP 塊采用OR門,低位部分直接被置為“1”,其計算誤差與ETCA 和ETA-I 相比略有增加,但相較于ETA-II-2和LOA 在平均誤差距離、歸一化誤差距離以及平均相對誤差距離均有改進,其中與ETA-II-2 相比,上述指標分別提高了約52%、52%和67%.

對不同位寬的TSA 加法器和MAA 下AP 的仿真結(jié)果見表5.對于不同MAA(MAA＜100%)值,位寬越大,其AP 值越趨近于100%,因此本文所提出的加法器在位寬較大的加法計算中也具有極大優(yōu)勢.

表5 不同位寬和MAA 下TSA 加法器的AP 值 %

4 總結(jié)

由于加法器的計算誤差大小與錯誤發(fā)生的位置關(guān)系密切,相比于權(quán)重大的輸出位發(fā)生錯誤,權(quán)重小的輸出位錯誤引起的誤差要小很多.針對加法器此特點,本文三段式近似加法器將加法器分成三段,其中權(quán)重高的段用精確加法器實現(xiàn),達到降低誤差目的,中間和低位部分采用OR門和常數(shù),且各位之間不存在進位關(guān)系.這種設(shè)計顯著降低了電路面積和功耗,同時也對計算誤差與電路性能改善進行了折中.與傳統(tǒng)精確加法器行波進位加法器相比,該加法器的面積、功耗、功耗延遲積和面積延遲積分別下降約43%、57%、85%和81%.與現(xiàn)有分段式近似加法器相比,總體性能有明顯改善.