分段式高性能近似加法器設(shè)計(jì)

李凱磊,楊文強(qiáng),王倫耀

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

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

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

1 相關(guān)工作

1.1 研究現(xiàn)狀

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

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

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

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

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

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

圖1 ETA-II 加法器

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

1.2 計(jì)算誤差評(píng)價(jià)指標(biāo)

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

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

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

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

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

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

加法器精度(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”,也稱(chēng)為CON 塊;第二部分為加法器中間部分,位寬為n/4,用一個(gè)二輸入邏輯門(mén)代替一位全加器,這部分電路也稱(chēng)TP 塊.剩余部分為精確計(jì)算部分,由RCA 構(gòu)成.

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

2.1.1 CON 塊

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

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

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

顯然,對(duì)于位寬為n/4的CON 塊,為了使CON 塊對(duì)應(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]的每一位單獨(dú)進(jìn)行基本二輸入邏輯運(yùn)算所得,且每一位不產(chǎn)生也不接收任何進(jìn)位信號(hào),從而減少電路面積和時(shí)延.

從表1 可知,XOR 門(mén)的輸出與加法器的求和輸出一致,但沒(méi)有進(jìn)位信號(hào);OR 門(mén)的4 個(gè)輸出中有3個(gè)與加法器的輸出一致,而AND 門(mén)只有1 個(gè)輸出與加法器的輸出一樣.因此,在TP 塊中不考慮AND 門(mén).

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

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

2.1.3 RCA 塊

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

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

2.2 三段式非精確加法器誤差分析及改進(jìn)

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

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

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

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

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

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

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

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

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

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

3 實(shí)驗(yàn)結(jié)果

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

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

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

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

表4 各16 位加法器計(jì)算誤差比較

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

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

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

4 總結(jié)

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