一種低開銷的近似乘法器設計

謝迎娟，折夏煜，褚嘉敏，王 亮，蔡 莉，王海濱，韓光潔

1(河海大學 物聯(lián)網(wǎng)工程學院，南京 211100) 2(北京微電子技術(shù)研究所，北京 100076) 3(中國科學院 近代物理研究所，蘭州 730000) 4(江蘇省輸配電裝備技術(shù)重點實驗室，江蘇 常州 213000) E-mail：wanghaibin@hhu.edu.cn

1 引 言

在過去的幾十年里，各種先進的計算系統(tǒng)得到廣泛的開發(fā)和應用.超級計算機日新月異，各類計算中心和服務器無處不在，已經(jīng)深度融入人類生產(chǎn)生活的方方面面.但與此同時，一方面，傳統(tǒng)的計算系統(tǒng)在一些重要的物理限制(如功耗、面積等指標)下不能有效地進一步增強性能，摩爾定律已經(jīng)接近極限；另一方面，對于一部分產(chǎn)業(yè)來說，計算系統(tǒng)需要得到精確的結(jié)果[1]，但在越來越多的應用系統(tǒng)中，并不需要嚴格意義上的正確結(jié)果.例如，圖像處理算法的計算通常在像素級進行，輕微的質(zhì)量缺陷是可以容忍的，人類視覺系統(tǒng)無法察覺.人們越來越認識到，過度的精確性從來就不是免費的，它消耗了我們的時間和世界的能源.因此，通過犧牲不必要的精度，可以在功率和性能上獲得極大的優(yōu)化.

近似計算(Approximate Computing)利用計算結(jié)果的準確性來優(yōu)化系統(tǒng)資源的使用，是加速處理器的最可行方法之一[2].對于許多可以接受不準確結(jié)果的系統(tǒng)來說，如人工智能、機器學習[3]、數(shù)字信號處理(Digital Signal Processing，DSP)、多媒體、機器學習和模式識別[4]等，它已經(jīng)成為一種比傳統(tǒng)計算架構(gòu)更可取的新方案.受人腦容錯能力的啟發(fā)，近似計算在不犧牲功能和“感知”的情況下通過適當?shù)亟档陀嬎憔?，來協(xié)調(diào)和權(quán)衡計算質(zhì)量(例如，精度)和計算消耗(例如，功耗和面積)[5].

近似計算可以應用于硬件和軟件以及不同的系統(tǒng)層[6].在電路級，由于其在許多計算應用中的重要作用，近似算法單元的設計得到了廣泛的研究.近些年來，各種近似加法器已經(jīng)被提出，以達到降低功耗和延遲的目的.而相比于加法器，乘法器的結(jié)構(gòu)更加復雜，面積和功耗往往是同位寬加法器的數(shù)倍，因此近似乘法器對性能的優(yōu)化更加可觀.相比于精確乘法器，近似乘法器通過適當?shù)胤艑掃\算精度，簡化或刪除部分運算電路，不僅可以節(jié)省開銷，并且能夠優(yōu)化電路中關鍵路徑的延時，加快計算速度[7].對于一些處理過程本身就是不精確的應用來說，近似乘法器甚至可以對原有的不精確部分進行補償，得到更好的處理結(jié)果.

本文基于精確二進制乘法器，提出了操作數(shù)裁剪模塊和低開銷部分積累加算法，設計了一種新型近似乘法器.并對該近似乘法器的誤差特性和開銷性能進行仿真，與主流輸入級近似方法進行對比.

2 相關工作

一般地，在數(shù)字電路中，近似計算可以運用于近似乘法器的3個部分：

1)輸入級近似：

通過編碼或者直接截斷的方式，減少了部分積的產(chǎn)生和運算過程.1962年，J.N.Mitcheu提出了對數(shù)乘法器，即將兩個二進制乘數(shù)通過以2為底的對數(shù)運算轉(zhuǎn)化為其近似的二進制對數(shù)，再通過加法器將二者相加，最后將和還原為近似積[8].但是將數(shù)字轉(zhuǎn)化為近似對數(shù)時較為麻煩，導致功耗增加.迭代對數(shù)乘法器(Iterative Logarithmic Multiplier，ILM)是以精度為代價對其進行改進的簡潔算法，但是誤差比對數(shù)乘法器大.G.Zervakis等人利用部分積穿孔技術(shù)實現(xiàn)了乘法運算的近似，并以穿孔位置及大小為變量對近似乘法器的精度和開銷進行了分析比較[9].S.Vahdat等人提出了基于截斷和舍入的動態(tài)近似乘法器(Truncation-and Rounding-based Scalable Approximate Multiplier，TOSAM)，獲得了較高的精確度，但是功耗降低的程度有限[10].S.Narayanamoorthy等人提出的加強型靜態(tài)片段法乘法器(Enhanced Static Segment Multiplier，ESSM)主要思想為采用多個固定片段，當判斷高位的片段為全0時采用下一個片段[11].另外，動態(tài)范圍無偏乘法器(Dynamic Range Unbiased Multiplier，DRUM)[12]和基于取整的乘法器(Rounding-Based Approximate，RoBA)[13]也是兩種誤差較小的近似算法，但是面積與功耗較大.其中，DRUM引入了最高有效位檢測模塊(Leading-One Detector，LOD)，動態(tài)地對最有效的位進行乘法運算.

2)部分積產(chǎn)生級近似：

通過在相乘的過程中避免低位部分積的產(chǎn)生，從而減少相乘的運算步驟.生成部分乘積的一種簡單方法是將乘數(shù)的每一位乘上被乘數(shù)，這可以通過簡單的邏輯運算來實現(xiàn).另一種方法是將乘法器編碼為高基數(shù)，并將已編碼的乘法器乘以被乘數(shù).隨著基數(shù)的增加，對乘法器的編碼就變得更加復雜.因此，為了降低復雜度，可以使用近似編碼器來生成部分乘積[14].W.Liu等人提出了兩種有效的以4為基數(shù)近似Booth編碼器[15].

3)部分積求和級近似：

通過對重要位(即高位)精確求和而對不重要位(即低位)近似求和，從而縮短進位鏈，減小延時開銷.H.R.Mahdiani等人提出了一種不精確的陣列乘法器，將部分積樹中一些最不重要的列作為常數(shù)忽略掉[16].另外，在高速乘法器的設計中，壓縮器或計數(shù)器被廣泛用于加速部分積的求和.O.Akbari等人提出了4種近似4∶2的壓縮器并運用于乘法運算中[17].M.Ha和S.Lee提出了一種近似4∶2的壓縮器，并在部分積累積步驟中引入了誤差恢復模塊，提高了乘法的精度[18].

本文將針對乘法器的輸入級，設計新型近似乘法器，并與主流近似乘法器進行比較.

3 近似乘法器實現(xiàn)

3.1 精確二進制乘法器

精確乘法器的二進制運算流程如圖1所示.其中，操作數(shù)A和操作數(shù)B為乘法的輸入項的二進制表示，可寫為：

圖1 乘法器的運算流程Fig.1 Operation flow of the reference multiplier

(1)

(2)

其中，n1、n2分別是儲存兩個二進制操作數(shù)A、B的寄存器位寬，ai、bi分別是二進制操作數(shù)A、B從低位開始第i位的值(i≥0).

對于位乘積模塊，本文采用將乘數(shù)的每一位乘上被乘數(shù)的邏輯運算方法生成部分積樹.對部分積樹進行累加，得到乘積的二進制輸出O：

O=A×B

(3)

3.2 基于穿孔的近似乘法器

一般地，將操作數(shù)中2的指數(shù)越大的位稱為高位，反之為低位.高位為重要位，即高位被更改比低位對乘法結(jié)果的影響更大.

基于穿孔的近似乘法器從低位開始舍去操作數(shù)的部分位，在可接受精確度范圍內(nèi)減少部分積累加步驟.通過改變穿孔起點和長度，實現(xiàn)運算精度和開銷之間的權(quán)衡.

在該近似乘法器中，設置操作數(shù)的穿孔起點及長度分別為j、k，則穿孔后進行位乘積的輸入項為：

(4)

(5)

生成部分積樹后，進行累加，得到乘積的二進制輸出Oq：

Oq=Aq×Bq；

(6)

3.3 基于操作數(shù)裁剪的新型近似乘法器

本節(jié)將基于精確乘法器的二進制運算流程，提出操作數(shù)裁剪方法和低開銷部分積累加算法，設計一種新型近似乘法器.運算流程圖如圖2所示，通過以下4步實現(xiàn)：

圖2 基于操作數(shù)裁剪的近似乘法器運算流程Fig.2 Operation flow of the proposed approxiamte multiplier

1)操作數(shù)裁剪

操作數(shù)A和B操作數(shù)為該近似乘法器的輸入項.

首先，根據(jù)儲存兩個二進制操作數(shù)A、B的寄存器位寬，設置分別對A和B進行近似操作的截取間隔數(shù)k、l(k、l為正整數(shù)).

根據(jù)截取間隔數(shù)k、l確定A和B的近似標志位，設A的近似標志位：

Ac=or(a2k+2，a2k+3，…，an1-1)

(7)

記B的近似標志位：

Bc=or(b2l+2，b2l+3，…，bn2-1)

(8)

其次，根據(jù)近似標志位Ac、Bc確定簡化的乘法輸入項.圖3為對操作數(shù)A進行截取操作的示意圖.

圖3 操作數(shù)截取操作示意圖Fig.3 Diagram of operand pruning

若Ac=0，表示二進制操作數(shù)A從低位開始的第2k+2位-第n1-1位均為零，則將A左移兩位；若Ac=1，表示二進制操作數(shù)A從低位開始的第2k+2位-第n1-1位不全為零，則不對A進行移位操作.

最后，對二進制操作數(shù)A的第0位-第2k-1位進行近似截取操作，保留第0位及第k位，去除第1-第k-1位及第k+1-第2k-1位，共去除2k-2位，同時更新第2k位的值a′2k，得到簡化的乘法輸入項Ap，表示為：

(9)

其中，當0

a′2k=or(and(a2k-1，ak-1)，a2k)

(10)

當k≥3時，

a′2k=or(and(a2k-1，a2k-2)，a2k)

(11)

同樣地，對B進行移位和截取操作.

若Bc=0，表示二進制操作數(shù)B從低位開始的第2l位-第n2-1位均為零，則將B左移兩位；若Bc=1，表示二進制操作數(shù)B從低位開始的第2l位-第n2-1位不全為零，則不對B進行移位操作.

對二進制操作數(shù)B的第0位-第2l-1位進行近似截取操作，保留第0位-第l位，去除第1-第l-1位及第l+1-第2l-1位，共去除2l-2位，同時更新第2l位的值b′2l，得到簡化的乘法輸入項Bp，表示為：

(12)

其中，當l<3時，

b′2l=or(and(b2l-1，bl-1)，b2l)

(13)

當l≥3時，

b′2l=or(and(b2l-1，b2l-2)，b2l)

(14)

2)位乘積

通過位乘積模塊，得到部分積樹.同樣地，該模塊生成部分乘積所使用的方法是將乘數(shù)的每一位乘上被乘數(shù)，通過簡單的邏輯運算來實現(xiàn).

3)部分積累加

當對部分積進行累加時，記部分積樹的第m行部分積為Dm(m=1，2，…，P).

累加的具體操作為：首先，分別利用全加器和半加器對D1、D2、D3、D4按位進行累加操作，得到新的部分積D′3和D′4；然后分別利用全加器和半加器對D′3、D′4、D5按位進行累加操作，得到新的部分積D″4和D″5；重復累加操作，直到所有部分積都累加完成得到最終乘法結(jié)果O，O為二進制操作數(shù).

需要注意的是，累加操作一共執(zhí)行P-2步，其中第一步后部分積減少兩行，其余P-3步后部分積每次減少一行.

4)移位

在輸入項截取模塊中，根據(jù)近似標志位Ac、Bc的大小確定是否對A、B進行移位操作.因此，在部分積累加模塊后，需要根據(jù)Ac、Bc的大小對部分積累加結(jié)果進行移位操作，得到最終的乘積輸出Op：

Op=Ap×Bp

(15)

3.4 開銷分析

以8位乘法器為例，分析精確和近似乘法器的開銷.

對于精確乘法器，通過位乘積運算得到的部分積樹共有8行.圖4(a)為對部分積樹進行累加的過程簡化圖，其中一個黑點代表一個數(shù)據(jù)，如圖例所示，虛線框內(nèi)包含兩個數(shù)據(jù)的為加法器，加法器內(nèi)包含3個數(shù)據(jù)的為全加器.

由圖4(a)可得，基于部分積樹，每一步運算后部分積減少一行.因此，8位精確乘法器一共需7步計算得到最終的結(jié)果.

對于基于穿孔的近似乘法器，設置j=0，k=2，則位乘積運算得到的部分積樹共有6行，圖4(b)為累加操作的簡化過程.基于部分積樹，基于穿孔的近似乘法器一共需要5步計算得到最終的結(jié)果.相比于精確乘法器，基于穿孔的近似乘法器將部分積累加步驟減少了2步.

對于本文提出的基于操作數(shù)裁剪的近似乘法器，設置k=l=2，則乘法器的輸入項更新為：

(16)

(17)

其中，

a′4=or(and(a3，a1)，a4)

(18)

b′4=or(and(b3，b1)，b4)

(19)

在該近似乘法器中，通過裁剪輸入項的部分位，使得對部分積樹進行累加時，第1步操作實現(xiàn)對前4行的累加，即前4行部分積樹內(nèi)同一位只包含兩個或3個部分積.圖4(c)為k和l均設置為2時，8位近似乘法器的部分積累加過程.若k和l設置為1，則該近似乘法器無法實現(xiàn)低功耗部分積累計算法；若k和l設置為3，則會大大降低乘法計算的精度.所以，對于8位近似乘法器，本文將k和l均設置為2.

圖4 8位乘法器的部分積累加簡化圖Fig.4 Accumulation of partial products of(left)the reference 8-bit multiplier，(middle)the perforated-based 8-bit approximate multiplier，(right)the proposed 8-bit approximate multiplier

位乘積運算得到的部分積樹一共6行，基于部分積樹，該近似乘法器一共需要4步計算得到最終的結(jié)果.因此，相比于8位精確乘法器，本文所提出的近似乘法器將部分積累加步驟減少了約42.8%.

同理，為了滿足低功耗部分積累加算法要求并保證精度需求，對于10位近似乘法器，將k和l均設置為3，則乘法器的輸入項更新為：

英國Romax科技有限公司是世界領先的工程技術(shù)咨詢公司，總部位于英國諾丁漢，在齒輪箱、軸承和機械傳動系統(tǒng)方面擁有豐富的經(jīng)驗和近30年的咨詢歷史。Romax出色的工程團隊和高級虛擬產(chǎn)品開發(fā)與仿真軟件RomaxDESIGNER家族系列產(chǎn)品，為全球傳動汽車、新能源汽車、軌道交通等工業(yè)領域的大型設備供應商提供設計、分析及認證支持等服務。

(20)

(21)

其中，

a′6=or(and(a4，a5)，a6)

(22)

b′6=or(and(b4，b5)，b6)

(23)

位乘積運算得到的部分積樹一共6行，圖5為位累加算法的簡化過程.由圖5可知，基于部分積樹，該近似乘法器一共需要4步計算得到最終的結(jié)果.

圖5 10位近似乘法器的部分積累加簡化圖Fig.5 Accumulation of partial products of the proposed 10-bit approximate multiplier

而對于10位二進制精確乘法器，一共需要9步部分積累加步驟.因此，近似乘法器將部分積累加步驟減少了約56%.

對于本文所提出的近似乘法器，其操作數(shù)裁剪方法和低功耗部分積累加算法是通用的.對于不同位寬的乘法器，通過設置k和l的數(shù)值，決定輸入項需要裁剪的位，就可實現(xiàn)低功耗的部分積累加算法.

4 實驗結(jié)果與分析

4.1 誤差特性仿真

各種近似算法單元差別較大.通常地，在近似乘法器設計完成后，以下幾個指標可以用于綜合衡量其誤差特性：

1)誤差率.指近似計算單元錯誤輸出占總輸出的比例，可以反應近似計算單元出錯的頻率；

2)平均誤差距離.指近似輸出與精確輸出的差值，大量輸入下的平均效應能更好地反應近似計算單元的誤差累積效應，平均誤差距離越大，誤差累積越嚴重，對輸出質(zhì)量影響越大.近似計算單元的所有輸入具有隨機性，可以認為呈現(xiàn)均勻分布，因此對所有輸入下的誤差距離求均值即可獲得平均誤差距離；

3)最大誤差距離.指近似計算單元在單次計算中可能出現(xiàn)的最大誤差，反應最大的誤差嚴重程度.最大誤差距離越大，越容易對應用的結(jié)果產(chǎn)生嚴重影響.

在本文中，使用6000對操作數(shù)來衡量8位近似乘法器的誤差特性，數(shù)值大小為0-255的隨機正整數(shù)，仿真結(jié)果如表1所示.除了本文所提出的基于操作數(shù)裁剪的近似乘法器以及精確乘法器，與基于穿孔的近似乘法器、DRUM、ESSM等主流輸入級近似方法也進行了對比分析.

由表1可知，DRUM是一種精度較高的近似乘法器，平均誤差距離和最大誤差距離分別為0.84%和6.35%.這是因為它引入了兩個最高有效位檢測模塊，以及兩個多路復用器選擇進行乘法運算的數(shù)據(jù)位，動態(tài)地對最有效的位進行乘法運算.但是在實際應用中，該乘法器會導致較大的面積與功耗開銷.

表1 近似乘法器誤差特性仿真結(jié)果Table 1 Simulation results of error characteristics of approximate multipliers

基于穿孔的近似乘法器精度非常低，其最大誤差距離為100%，并不會隨著參數(shù)改變而降低.這是因為該近似乘法器處理簡單，保留輸入項中高位的數(shù)據(jù)而舍去低位的數(shù)據(jù)，如果當輸入項數(shù)值較小或者保留位的值均為0時，就會導致該次結(jié)果的誤差距離為100%.

與之相比，本文所提出的近似乘法器精度有很大的提升，平均誤差距離和最大誤差距離分別為3.01%和20.47%.這是因為，本文所提出的基于操作數(shù)裁剪的近似乘法器在對輸入項裁剪之前，考察了高位全為0的情況.若高位不全為0，則直接裁剪；若高位全為0，則進行移位操作后裁剪，在部分積累加結(jié)束后再進行一次移位操作得到最終結(jié)果.另外，該近似乘法器在裁剪之后，更新了輸入項中部分高位，彌補了數(shù)據(jù)裁剪對精度的影響.

ESSM與基于操作數(shù)裁剪的近似乘法器一樣，進行了高位考察及移位操作，保證了較高的精確度，其平均誤差距離和最大誤差距離分別為1.62%和8.75%.

4.2 性能評估

基于Xilinx Vivado 2019.1平臺，本節(jié)將比較精確乘法器、本文提出的基于操作數(shù)裁剪的近似乘法器、基于穿孔的近似乘法器、DRUM、ESSM的性能與資源開銷，具體包括查找表(Look-up-tables，LUTs)資源使用量、寄存器資源使用量和片上功耗等.

以8位二進制乘法器為例，圖6展示了LUT使用量、功耗開銷以及平均誤差距離的三維圖.為便于在圖中展示，將精確乘法器、基于操作數(shù)裁剪的近似乘法器、基于穿孔的近似乘法器分別記作PM、TRU-M、PER-M.

從圖6中可以看出，一個8位精確乘法器的LUT使用量和片上功耗分別為72和14.7w.PER-M乘法器減少了資源使用和功耗開銷，其LUT使用量和片上功耗以及分別為35和9.9w，但是該乘法器誤差很大，平均誤差距離約為7%.

圖6 多種近似乘法器LUT使用量、片上功耗以及平均誤差距離的三維圖Fig.6 3-D graph of LUT usage，power consumption on chip and average error distance of various approximate multipliers

DRUM和ESSM是兩種精度較高的乘法器，平均誤差距離分別約為0.8%和1.6%，但是資源使用量和功耗較大，LUT使用量分別為93和69，片上功耗分別為14.3w和12.9w.

本文所提出的近似乘法器的LUT使用量、片上功耗以及平均誤差距離分別為60、7.8和3%，以3%的精度損失減少了約16.7%的資源使用和46.9%的片上功耗.

5 結(jié) 論

基于精確二進制乘法器，本文設計了一種新型近似乘法器.對于8位和10位二進制乘法器，利用操作數(shù)裁剪模塊和低開銷部分積累加算法，可以將部分積累加步驟分別減少約42.8%和56%.

本章對各個乘法器進行了實現(xiàn)，并采用誤差率、平均誤差距離和最大誤差距離衡量了誤差特性.結(jié)果顯示，本文所提出的近似乘法器的精度相比于基于穿孔的近似乘法器有很大的提升，平均誤差距離和最大誤差距離分別為3.01%和20.47%.由性能評估可知，相比于精確乘法器，該近似乘法器以3.01%的精度損失減少了約16.7%的資源使用和46.9%的片上功耗.