一種混合結構的新型近似加法器

王保坤，班 恬

（南京理工大學電子工程與光電技術學院，江蘇南京210094）

隨著超大規模集成電路技術的飛速發展，電路中各種錯誤的發生是不可避免的。利用容錯技術可以提高電路的可靠性[1]。近年來，集成電路（Integrated Circuits，IC）設計中由芯片功耗增大所帶來的挑戰引起了人們的廣泛關注[2]。一些具有容錯能力的應用工程（如多媒體處理、模式識別與機器學習等）在計算過程中可容納一些錯誤。對于這些與人類聽覺或視覺等感官有密切關系的應用場合，一些錯誤可以忽略不計。這就為通過降低精度要求而實現節能設計提供了良好的機會。

先前的文獻已經提出了不同種類的近似加法器結構。文獻[3]提出了低位或門加法器（Lower-Part-OR Adder，LOA），它利用精確加法器來計算較高位的和，利用邏輯或門來計算較低位和的近似值。除此之外，不精確部分的最高兩位通過邏輯與門產生進位輸入信號并傳遞給精確部分以提高整個近似加法器的運算精度。相對于經典精確加法器，LOA擁有更少的面積開銷與功率損耗，但其錯誤率卻極高。文獻[4]提出了容錯加法器（Error-Tolerant Adder I，ETAI）。這種加法器利用修改后的邏輯異或門來計算較低位的近似和，用精確加法器計算較高位的精確和。通過實驗測試，該近似加法器對于較小輸入運算的錯誤率較高。為解決這一缺陷，該文獻作者在文獻[5]中提出了ETAII。利用分塊的思想，將整個電路結構分成若干個子加法器模塊，這樣可以將整條進位傳輸路徑截斷成較短路徑，因而減少電路的延時與動態功耗。為進一步提高ETAII的正確率，文獻[5]提出了ETAM。與ETAII僅考慮前一個模塊的進位信號不同，ETAM里的多個進位產生模塊級聯為較高位的模塊提供進位輸入信號。文獻[6]提出了精度可配置加法器（Accuracy-Configurable Approximate Adder，ACA adder）。該近似加法器可以運行在精確模式與近似模式之下。它利用若干個子加法器來計算和的部分值，運算精度較高。但由于電路配置了錯誤檢測與糾正模塊，導致較大的功耗與面積。文獻[7]提出的預測進位選擇加法器（Speculative Carry Select Addition，SCSA）的思想來自于對加法運算進位鏈的推斷。每個子模塊的進位輸出信號僅由該模塊所有位來決定，通過數據選擇器來選擇不同情況下進位輸出信號的數值，這將導致更大的面積與功耗。文獻[8]提出了一種非常有效的進位推斷方法，該方法可保證近似加法器有較低的相對誤差，同時有較少的面積與功耗。

本文提出了一種具有混合結構的新型近似加法器（HYB adder），該加法器可以在計算精度與其他性能參數之間獲取平衡。因為最高有效位在計算中起到了更為重要的作用，因此該加法器從最低位到最高位分別由3種不同精度、不同結構的子模塊組成。

1 混合結構近似加法器（HYB adder）

1.1 近似加法器的結構

以16位加法器為例。將16位加數分成精確部分（高8位）與非精確部分（低8位）。精確部分由經典精確加法器組成，如行波進位加法器（Ripple Carry Adder，RCA）或超前進位加法器（Carry Lookahead Adder，CLA）。非精確部分被分成兩個子模塊，其具體結構如下說明：

1）低位部分：為截斷最低4位加數的進位傳遞路徑，此部分沒有進位產生。圖1為1位精確加法器與1位近似加法器的卡諾圖（二者均不考慮進位輸入信號）。近似加法器將和“10”轉化為“01”，因而此部分可采用邏輯或門來參與計算。這樣做可有效減少電路面積與延時。

圖1 精確1位加法器與近似1位加法器不考慮進位輸入時的卡諾圖

2）中間部分：采用一種省略最低位進位的近似超前進位加法器來計算中間4位加數的和。設加法器第i位的兩個輸入分別為ai、bi，進位輸入為ci。第i位的進位傳遞信號pi與進位產生信號gi的表達式如下所示：

第i位的近似進位輸出與近似和由下式表示：

其中，i＞1。

如果pi=1，ci=ci-1，代表第i-1位的進位輸出信號傳遞到了第i位來。如果gi=1，ci=1，代表了第i位產生了進位輸出。該部分還將為高位精確部分產生一個進位輸入信號，以增加運算的精確度。下圖是16位HYB Adder的電路結構圖：

圖2 16位HYB Adder的電路結構圖

1.2 近似加法器的誤差特性分析

1）錯誤率：將N位近似加法器分成三部分，其中包括m個較高位、p個中間位和l個較低位，即N=m+p+l。

最低部分的誤差分析：當此部分任一位的兩個輸入同時為1時，即產生了進位輸出信號，此時輸出結果錯誤。因此，此部分產生錯誤結果的概率為：

因此，近似超前進位加法器的錯誤率為：

表1列出了l與p取不同值時該近似加法器的錯誤率（k=4）。

表1 l與p取不同值時的錯誤率

2）誤差距離：相對于錯誤率，誤差距離（Error Distance，ED）與平均誤差距離（Mean Error Distance，MED）可更有效地衡量近似電路的運算性能[9]。對于近似加法器來說，ED是指精確的和（S）與近似的和（S’）之差的絕對值，即

其中，S是精確加法器的和，S’是近似加法器的和。

MED指對給定輸入向量下ED的平均值[9]，是評估多位加法器運算性能的有效指標。

其中，P(EDi)是EDi的概率，qi是加法器中第i位的錯誤率。

為計算MED，本文利用Verilog HDL語言搭建了一個有效平臺，其結構如圖3所示：

圖3 計算MED的平臺結構圖

此平臺工作在clk的上升沿，由異步復位信號rst進行初始化。其中，信號x代表精確加法器（Accurate Adder）模塊與近似加法器（Approximate Adder）模塊的輸入數據，其范圍是0～2N-1。比較模塊（Comparator）用以比較兩個加法器產生的輸出（ya與yap）。比較模塊中的計數器（count）用來計算在給定相同輸入下兩個加法器產生不同輸出的個數。由于遍歷所有輸入的組合，qi的值便可由count與2N之比得到。

2 比較與分析

本文將所提出的近似加法器用Verilog HDL語言描繪，并利用28納米的FD-SOI標準單元庫[10]在Cadence RTL Compiler下進行了電路綜合。圖4給出了16位HYB Adder的電路結構圖，其各個部分的位寬為m=8，l=p=4。

圖4 16位近似加法器綜合后的結構圖

圖4中最下方的模塊為HYB Adder中的低位部分，即邏輯或門組成的模塊。中間位置為HYB Adder的中間部分結構，即近似CLA。最上方則為高位部分，是精確加法器RCA模塊。

為了比較HYB Adder與其他加法器在面積、延時、功耗與誤差性能方面的表現，本文也對經典精確加法器RCA以及其他4個已被提出的近似加法器進行了電路綜合，各加法器的子模塊位寬都選擇了4位（k=4），精確部分都使用了相同的RCA電路結構。LOA、ETA-I與HYB加法器的精確部分與不精確部分均為8位位寬。為保證電路可比性，我們沒有將ACA的錯誤檢測與糾正電路考慮進來，因為這樣會增加電路額外的面積開銷與延時。實驗結果如下表所示。

表2 各16位加法器性能參數比較

由于完全利用邏輯或門進行低位運算，LOA擁有比HYB更小的面積與功耗，但HYB中間部分更為精確的運算機制使其比LOA的錯誤率更低。因為截斷了整個或部分的進位傳播路徑，所以ETA-I比HYB的延時與功耗更小。然而由于配置了修改后的異或門與控制信號產生單元，ETA-I的面積開銷比HYB更大。同時，ETA-I高達接近90%的錯誤率可能會限制其在實際工程中的運用。ACA在延時方面優勢最突出，因為其縮短的進位鏈減少了關鍵路徑延時。SCSA運行速度較快且錯誤率較低，但由于進位選擇機制使其配置了包含兩個經典精確加法器的窗口加法器，因此SCSA的面積開銷與功耗在所有加法器中最大。盡管HYB比ACA與SCSA的錯誤率要高出不少，但ACA與SCSA的高位運算精度卻不樂觀，這些都在其平均誤差距離上有所體現。在參與比較的所有加法器中，HYB的平均誤差距離最小，因此HYB在運算電路的應用是有很大意義的。

3 近似加法器在DCT/IDCT中的應用

DCT/IDCT的圖像處理程序中包含了大量的加法、乘法與除法運算[11-13]，我們將此程序中的所有32位的精確加法器替換成了32位的近似加法器（l=8，p=8，m=16）。

通常用峰值信噪比（Peak to Signal Noise Ratio，PSNR）來衡量圖像的失真程度[14-15]，其公式如（10）所示。PSNR的值越大，代表處理過的圖像失真越小。

其中，MAX代表圖像像素值的最大值，MSE為原始圖像I與經過DCT/IDCT重構后的圖像K（二者灰度圖的像素矩陣均為m×n）的均方誤差[16-17]，其定義如下：

表3是利用近似加法器重構后圖像的PSNR值，圖5是重構后的圖像。

表3 精確加法器與近似加法器PSNR值（dB）的比較

圖5 精確加法器與近似加法器重構后的圖像

從表3可以看出，由近似加法器重構后圖像的PSNR值僅僅比精確加法器重構后圖像的PSNR值損失了一點，而這一點損失也可完全被人眼忽略。

4 結束語

本文基于近似的思想，提出了一種新型混合結構的近似加法器HYB Adder。在故意犧牲一定精度的前提下，使加法器在延時、面積與功耗等性能參數方面有較大提升。本文搭建了近似加法器的誤差分析平臺以測試各加法器的錯誤率及誤差距離。HYB Adder的平均誤差距離在所有加法器中最為優秀。本文還利用Cadence RTL Compiler來綜合各加法器電路并得到其各項性能參數。從參數比較表可以看出，本文所提出的HYB Adder的速度與功耗遠遠優于經典精確加法器RCA。最后將近似加法器應用到DCT/ICDT的圖像變換之中，重構后的圖像與精確加法器重構后的圖像幾乎沒有任何差別，由此證明了近似加法器的實用性。