王一琛, 王倫耀, 夏銀水, 儲著飛

基于近似計算技術(shù)的FPRM邏輯功耗優(yōu)化

王一琛, 王倫耀*, 夏銀水, 儲著飛

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

提出了一種基于近似計算技術(shù)的Fixed Polarity Reed-Muller(FPRM)邏輯功耗優(yōu)化算法, 該算法包括基于信號概率和跳變密度的固定極性Reed-Muller(RM)函數(shù)動態(tài)功耗模型, 基于遺傳算法的以功耗優(yōu)化為導(dǎo)向的RM邏輯極性搜索方法, 以及利用雙銳積運(yùn)算的RM邏輯錯誤率計算方法. 在錯誤率的約束下, 通過有選擇性地刪減部分乘積項, 實現(xiàn)功耗優(yōu)化. 提出的算法用C語言實現(xiàn), 并用MCNC Benchmark電路測試. 結(jié)果表明: 與原始FPRM電路功耗相比, 在平均錯誤率為3.21％時, 電路動態(tài)功耗平均減少了22.77％.

近似計算; 錯誤率; 極性搜索; 功耗優(yōu)化

邏輯功能正確一直是傳統(tǒng)數(shù)字邏輯在設(shè)計時的首要條件, 且為保證功能正確不惜犧牲電路的面積、功耗、時延等性能指標(biāo). 但在有些應(yīng)用中,如圖像、音頻處理, 待處理的數(shù)據(jù)具有一定的容錯性, 在某一范圍內(nèi)的計算錯誤不會影響電路的實際應(yīng)用, 待處理數(shù)據(jù)的這種容錯特性意味著可以適當(dāng)降低計算精度, 進(jìn)而實現(xiàn)電路其他性能指標(biāo)的提升, 這種非精確計算稱之為近似計算. 利用近似計算技術(shù)實現(xiàn)電路的邏輯優(yōu)化稱為近似優(yōu)化. 目前,近似計算已成為數(shù)字集成電路設(shè)計中一個新的重要策略.

邏輯函數(shù)通常采用2種基本形式, 既可采用基于“與/或/非”運(yùn)算的傳統(tǒng)布爾(Traditional Boolean, TB)邏輯, 也可采用基于“與/異或”運(yùn)算的Reed- Muller(RM)邏輯. 目前, 在TB邏輯上開展的研究主要包括基于近似計算的二級邏輯電路優(yōu)化[1-3]、多級邏輯電路優(yōu)化[4-5]等. 多數(shù)優(yōu)化算法以乘積項為基礎(chǔ)實現(xiàn)近似函數(shù)的構(gòu)造和近似度計算, 但是也有基于偽乘積項[6]或借助二元決策圖(Binary Decision Diagram, BDD)來實現(xiàn)[7].

除TB邏輯外, RM邏輯正吸引越來越多研究者的興趣, 其原因包括: (1)隨著集成電路技術(shù)的發(fā)展, 構(gòu)成RM邏輯的“異或”門無論是速度、功耗還是面積都獲得極大的改進(jìn), 使之更加適合實際應(yīng)用. (2)與TB邏輯相比, RM邏輯在算術(shù)及通信電路、可逆邏輯設(shè)計[8]、可測試方面等應(yīng)用具有優(yōu)勢. (3)近一半的電路, 如采用RM邏輯進(jìn)行綜合可獲得更加簡單的結(jié)果. (4)有些新的器件具有“異或”特性, 相比互補(bǔ)金屬氧化物半導(dǎo)體(Complementary Metal Oxide Semiconductor, CMOS)電路, 新器件在“異或”運(yùn)算實現(xiàn)將變得極為簡單.

目前, 已有不少RM邏輯功耗優(yōu)化方法, 包括RM函數(shù)極性搜索方法、多輸入XOR門陣列分解方法; 搜索方法包括遺傳算法[9]、粒子群算法[10]、Min-Huffman算法[11]等. 上述優(yōu)化算法均沒有涉及錯誤引入對功耗優(yōu)化的影響.

本文主要研究近似計算技術(shù)在RM邏輯電路功耗優(yōu)化中的應(yīng)用, 提出了一種利用近似計算技術(shù)實現(xiàn)FPRM邏輯電路功耗優(yōu)化的方法, 即建立以信號概率和跳變密度為參數(shù)的RM邏輯電路動態(tài)功耗數(shù)學(xué)模型;并在錯誤率約束下, 利用提出的優(yōu)化策略刪減部分乘積項, 實現(xiàn)FPRM邏輯電路動態(tài)功耗的優(yōu)化.

1 RM邏輯電路的動態(tài)功耗數(shù)學(xué)模型

邏輯電路的功耗包括靜態(tài)功耗和動態(tài)功耗, 動態(tài)功耗是功耗的主要部分, 由電路中所有節(jié)點電容充放電引起, 可用式(1)表示:

式中:dp為動態(tài)功耗;為電路總節(jié)點數(shù);dd為電源電壓;c為第個節(jié)點的等效電容;w為第個節(jié)點的開關(guān)活動率, 其大小等于第個節(jié)點單位時間內(nèi)平均充放電次數(shù).

從式(1)可知, 只要減小任何一個參數(shù)都可以實現(xiàn)電路的動態(tài)功耗優(yōu)化. 本研究主要通過降低電路開關(guān)活動率w來實現(xiàn)電路的功耗優(yōu)化.

對于第個節(jié)點w, 其大小與加在該節(jié)點上的信號的概率()和跳變密度()有關(guān). 其中()等于信號在時間內(nèi)取值為邏輯1的比例.

信號的跳變密度()等于在單位時間內(nèi)的跳變次數(shù), 即在時間內(nèi)的跳變次數(shù)n()與比值.

從式(3)跳變密度定義可看出, 信號的跳變密度和開關(guān)活動性本質(zhì)一致, 因此本研究用信號跳變密度來表示開關(guān)活動性.

RM邏輯是由“與/異或”運(yùn)算構(gòu)成的二級邏輯,因此RM邏輯電路功耗估算可以通過對與門陣列和異或門陣列功耗估算來實現(xiàn). 考慮到多輸入邏輯門均可以分解成二輸入邏輯門的組合, 因此本研究通過對二輸入與門和異或門功耗的估算來實現(xiàn)RM邏輯電路的功耗估算.

對于輸入為1和2, 輸出為2的二輸入與門,設(shè)1和2的信號概率分別為(1)和(2), 跳變密度分別為(1)和(2). 考慮到二輸入與門中只有一個輸入信號為高電平時, 另一個信號的跳變才能傳輸?shù)捷敵龆? 因此輸出端2的跳變密度(2)可以表示為:

式中:∈[1,2,…,],≠.

對于有個輸入變量的異或門, 由于輸入端的任何跳變都會引起輸出端的變化, 因此輸出端的跳變密度(y)就等于各輸入信號跳變密度之和, 即:

利用式(5)和式(6)可以計算出由個與門,個異或門構(gòu)成的RM邏輯電路所有內(nèi)部節(jié)點的總的跳變密度RM, 即:

式中:AND()表示第個與門輸出跳變密度;XOR()表示第個異或門輸出跳變密度.

在RM邏輯電路的功耗優(yōu)化中, 極性變換是實現(xiàn)RM邏輯電路功耗優(yōu)化的一種有效手段. 以式(8)為例:

假設(shè)3個輸入變量的概率與跳變密度分別為(1,2,3)=(0.7,0.8,0.3),(1,2,3)=(0.2,0.4,0.1),則由式(5)~(7)可以得到: 當(dāng)極性分別為6和0時, 式(8)的RM函數(shù)對應(yīng)總的信號跳變密度分別為0.244和0.878. 因此, 可以通過極性變換實現(xiàn)RM邏輯電路的功耗優(yōu)化[12].

2 近似RM邏輯的錯誤率計算方法

基于近似計算的RM邏輯函數(shù)優(yōu)化可以通過增減原函數(shù)的乘積項來實現(xiàn)RM邏輯函數(shù)面積優(yōu)化, 減少電路節(jié)點數(shù), 從而實現(xiàn)RM邏輯函數(shù)功耗優(yōu)化.

顯然式(9)要比式(8)簡單. 從圖1可知, 通過引入特定的錯誤可實現(xiàn)RM邏輯函數(shù)的簡化. 圖1(b)中可能的輸入有23=8種, 只有輸入(x1x2x3)=(011)時, 輸出錯誤, 因此錯誤率為1/8.

圖2 原函數(shù)及其近似邏輯函數(shù)的卡諾圖表示

從圖2的例子中不難發(fā)現(xiàn), RM邏輯與TB邏輯近似優(yōu)化不同, 主要表現(xiàn)在: (1)引入取值為“0”的某些乘積項, 可簡化RM表達(dá)式, 但不增加錯誤輸出. (2)在錯誤率計算方面, 對于TB邏輯而言, 可以直接通過比較近似函數(shù)的乘積項集合與原函數(shù)的乘積項集合的差異, 得到引起錯誤輸出的乘積項的集合, 進(jìn)而計算出錯誤率. 但對RM邏輯, 近似函數(shù)的乘積項集合與原函數(shù)的乘積項集合的差異不一定就是引起錯誤輸出的乘積項的集合, 因為差異部分可能包含了偶數(shù)次邏輯覆蓋, 即RM邏輯與TB邏輯的錯誤率計算方法不同. 上述差異使得原來適用TB邏輯近似優(yōu)化的方法不能直接用于RM邏輯的近似優(yōu)化.

算法1 double_disj_sharp (er,out)

圖3 利用雙銳積運(yùn)算去除RM邏輯中的偶數(shù)次邏輯覆蓋

3 基于近似計算技術(shù)的FPRM邏輯電路功耗優(yōu)化算法

基于近似計算的FPRM邏輯電路功耗優(yōu)化算法大致可分為2個部分: (1)是利用遺傳算法實現(xiàn)以功耗優(yōu)化為導(dǎo)向的RM邏輯的極性搜索, 得到功耗優(yōu)化下的FPRM表達(dá)式; (2)引入近似計算技術(shù), 在錯誤率約束下, 通過刪除FPRM函數(shù)中特定的乘積項實現(xiàn)功耗的進(jìn)一步優(yōu)化.

算法2為基于近似計算技術(shù)的FPRM邏輯電路功耗優(yōu)化代碼, 其中為了方便實現(xiàn)TB邏輯向FPRM邏輯轉(zhuǎn)化, 先將測試電路表示為不相交乘積項之“或”形式, 然后利用基于不相交乘積項列表技術(shù)[17]實現(xiàn)TB邏輯向FPRM邏輯轉(zhuǎn)化.

算法2 FPRM_pwr_opt_ap(dis)

算法2中step1用遺傳算法實現(xiàn)以功耗優(yōu)化為導(dǎo)向的FPRM函數(shù)極性搜索, 得到FPRM函數(shù)的乘積項構(gòu)成集合RM_pwr; step2用式(5)計算RM_pwr中各RM乘積項的跳變密度, 并按照跳變密度進(jìn)行降序排序; step3按照乘積項的跳變密度大小從大到小試探性地逐個刪除, 并將刪除的乘積項放到er; step4利用雙銳積運(yùn)算去除er中乘積項之間偶數(shù)次覆蓋, 并將不存在偶數(shù)次覆蓋的乘積項存儲在out; step5中[out]表示乘積項集合out包含的最小項的數(shù)量. 由于雙銳積后的乘積項均為不相交乘積項, 因此[out]大小等于每個不相交乘積項包含的最小項數(shù)量的和. 另外,為函數(shù)的輸入變量數(shù).

在執(zhí)行step3到step5過程中, 如果移除某一乘積項p后, 發(fā)現(xiàn)>0, 則程序會放棄刪除, 轉(zhuǎn)而試探性往下刪除其他乘積項, 并判斷是否符合錯誤率約束條件. 循環(huán)執(zhí)行step3到step5, 直到無法滿足≤0,0為設(shè)定的錯誤率.

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

本文提出的RM邏輯功耗優(yōu)化算法在win7 64位操作系統(tǒng)4GB內(nèi)存環(huán)境下運(yùn)行, 用C語言編程實現(xiàn), 采用MCNC Benchmark電路進(jìn)行驗證. 在多輸出邏輯函數(shù)處理時, 常用的處理方法是將多輸出函數(shù)轉(zhuǎn)化為單輸出函數(shù), 然后按照單輸出函數(shù)進(jìn)行處理. 本文只有輸出相等的乘積項才進(jìn)行比較處理. 文中遺傳算法種群最大個體為30, 最大迭代數(shù)為50, 染色體交叉率為55％, 變異率為16％. 電路的功耗用電路內(nèi)部節(jié)點總的跳變密度表示. 實驗中每個電路輸入信號的概率與跳變密度隨機(jī)產(chǎn)生, 并將近似計算的錯誤率閾值設(shè)置為不大于5％.

表1為實驗結(jié)果, 其中“//”分別對應(yīng)測試電路的輸入數(shù)、輸出數(shù)和乘積項數(shù);pr表示功耗減少百分比, 運(yùn)算時間單位為秒:

式中:Power(_)和Power()分別表示在相同輸入信號下原電路和經(jīng)近似計算優(yōu)化后電路總的信號跳變密度.

表1 實驗結(jié)果

從表1可知, 在錯誤率閾值5％的前提下, RM邏輯的功耗優(yōu)化明顯. 如電路sym10和pcle等電路功耗少了56.29％和50.31％, 優(yōu)化效果明顯. 但也有部分電路, 如pm1和cc電路功耗減少不明顯, 分別減少了7.48％和6.63％, 其主要原因是在采用FPRM形式下, pm1和cc的乘積項之間相互交疊比較復(fù)雜, 刪除少量的乘積項就會帶來較大的錯誤率, 導(dǎo)致在誤差閾值內(nèi)優(yōu)化的功耗有限. 反之, 在FPRM形式下, 電路sym10和pcle存在部分乘積項,這些乘積項與其他乘積項交疊程度不大, 而對應(yīng)的信號密度比較大. 因此, 通過刪除這些乘積項,在減少總的信號跳變密度的同時又能較好地控制錯誤率的增加, 從而得到較好的優(yōu)化效果.

本文提出的算法可以處理輸入為85個變量的大電路, 其關(guān)鍵原因在于無論是RM邏輯的極性搜索還是RM函數(shù)的錯誤率求解, 均基于乘積項, 而不是最小項. 因此, 待處理電路的乘積項的數(shù)量會影響算法的運(yùn)行時間. 此外, 考慮到邏輯函數(shù)的乘積項數(shù)量與輸入變量的數(shù)量無關(guān), 所以本文算法可以實現(xiàn)大函數(shù)的FPRM的功耗優(yōu)化.

5 結(jié)論

本文提出了一種基于近似計算技術(shù)的RM邏輯功耗優(yōu)化算法, 該算法利用遺傳算法, 結(jié)合提出的以信號概率和跳變密度為參數(shù)的RM函數(shù)動態(tài)功耗數(shù)學(xué)模型和以功耗優(yōu)化為導(dǎo)向的極性搜索, 得到功耗優(yōu)化后的FPRM表達(dá)式, 然后利用提出的基于雙銳積運(yùn)算的RM函數(shù)的錯誤率計算方法, 通過有選擇性地刪除某些FPRM乘積項, 實現(xiàn)在錯誤率約束下的FPRM邏輯的功耗優(yōu)化. 提出的優(yōu)化算法用MCNC電路進(jìn)行了測試, 在平均錯誤率約束為3.21％時, 測試電路功耗的平均功耗減少了22.77％.

[1] Shin D, Gupta S K. Approximate logic synthesis for error tolerant applications[C]//Design, Automation & Test in Europe Conference & Exhibition, 2010:957-960.

[2] Zou C, Qian W, Han J. DPALS: A dynamic programming-based algorithm for two-level approximate logic synthesis[C]//IEEE 11th International Conference on ASIC, 2015:1-4.

[3] Ichihara H, Inaoka T, Iwagaki T, et al. Logic simplification by minterm complement for error tolerant application[C]//33rd IEEE International Conference on Computer Design, 2015:94-100.

[4] Miao J, Gerstlauer A, Orshansky M. Multi-level approximate logic synthesis under general error constraints[C]//IEEE ACM International Conference on Computer-Aided Design, 2014:504-510.

[5] Wu Y, Qian W K. An efficient method for multi-level approximate logic synthesis under error rate constraint [C]//Proceedings of the 53rd Annual Design Automation Conference. New York, USA: ACM Press, 2016:1-6.

[6] Bernasconi A, Ciriani V. 2-spp approximate synthesis for error tolerant applications[C]//17th Euromicro Con- ference on Digital System Design, 2014:411-418.

[7] Soeken M, Gro?e D, Chandrasekharan A, et al. BDD minimization for approximate computing[C]//21st Asia and South Pacific Design Automation Conference, 2016: 474-479.

[8] Mozammel H A K. Design of reversible synchronous sequential circuits using pseudo reed-muller expressions [J]. IEEE Transactions on Very Large Scale Integration Systems, 2014, 22(11):2278-2286.

[9] 尹浩凱, 馬雪嬌, 夏銀水. 基于近似邏輯的不完全指定FPRM函數(shù)的功耗優(yōu)化[J]. 寧波大學(xué)學(xué)報(理工版), 2019, 32(3):28-34.

[10] 俞海珍, 汪鵬君, 張會紅, 等. 基于三值多樣性粒子群算法的MPRM電路綜合優(yōu)化[J]. 電子學(xué)報, 2017, 45(7): 1601-1607.

[11] Wang X, Lu Y, Zhang Y, et al. Probabilistic modeling during power estimation for mixed polarity reed-muller logic circuits[C]//Green Computing & Communications, IEEE, 2013:1414-1418.

[12] 瞿婷, 王倫耀, 羅文強(qiáng), 等. 大函數(shù)ISFPRM面積優(yōu)化方法[J]. 電子學(xué)報, 2018, 46(5):1101-1106.

[13] Liang J, Han J, Lombardi F. New metrics for the reliability of approximate and probabilistic adders[J]. IEEE Transactions on Computers, 2013, 62(9):1760- 1771.

[14] Miao J, Gerstlauer A, Orshansky M. Approximate logic synthesis under general error magnitude and frequency constraints[C]//Proceedings of the International Con- ference on Computer-Aided Design, 2013:779-786.

[15] 王倫耀, 夏銀水, 陳偕雄. 邏輯函數(shù)的雙邏輯綜合與優(yōu)化[J]. 計算機(jī)輔助設(shè)計與圖形學(xué)學(xué)報, 2012, 24(7): 961-967.

[16] 王倫耀, 夏銀水, 陳偕雄, 等. 基于不相交乘積項的邏輯探測和拆分算法[J]. 電子學(xué)報, 2012, 40(10):2091- 2096.

[17] 王玉花, 王倫耀, 夏銀水. 基于不相交項并行列表技術(shù)的FPRM實現(xiàn)[J]. 電子與信息學(xué)報, 2014, 36(9):2258- 2264.

Power optimization for FPRM logic using approximate computing technique

WANG Yichen, WANG Lunyao*, XIA Yinshui, CHU Zhufei

( Faculty of Electrical Engineering and Computer Science, Ningbo University, Ningbo 315211, China )

A power optimization algorithm based on approximate computing technique is proposed for FPRM logic circuits. The algorithm includes FPRM logic circuits dynamic power estimation model based on signal probability and transition density, a genetic algorithm for RM logic power optimization using polarity searching, and the error rate calculation for RM logic using double sharp product operation. Under the constraint of error rate, some product terms are selectively deleted to reduce power consumption. The proposed algorithm is implemented in C programming language and tested under MCNC benchmarks. The experimental results show that using the approximate computing technique presented in this work, the average dynamic power can be reduced by 22.77％ with the average error rate of 3.21％.

approximate computation; error rate; polarity searching; power consumption optimization

TN47; TP391

A

1001-5132（2020）01-0045-06

2019?05?28.

寧波大學(xué)學(xué)報（理工版）網(wǎng)址: http://journallg.nbu.edu.cn/

國家自然科學(xué)基金（U1709218, 61871242）; 浙江省自然科學(xué)基金（LY19F040004）; 寧波市自然科學(xué)基金（2019A610077）.

王一?。?993－）, 女, 浙江舟山人, 在讀碩士研究生, 主要研究方向: 邏輯綜合與優(yōu)化. E-mail: 543746091@qq.com

王倫耀（1972－）, 男, 浙江寧波人, 教授, 主要研究方向: 邏輯綜合與優(yōu)化. E-mail: wanglunyao@nbu.edu.cn

（責(zé)任編輯 史小麗）