基于模擬退火遺傳算法的三值FPRM電路功耗優(yōu)化

厲康平，汪鵬君，張會紅

(寧波大學(xué) 電路與系統(tǒng)研究所, 浙江 寧波 315211)

?

基于模擬退火遺傳算法的三值FPRM電路功耗優(yōu)化

厲康平，汪鵬君*，張會紅

(寧波大學(xué) 電路與系統(tǒng)研究所, 浙江 寧波 315211)

摘要：在三值FPRM(Fixed-Polarity Reed-Muller)邏輯函數(shù)中,n變量函數(shù)有3n個固定極性.針對不同極性下FPRM電路功耗不同的特點，研究了三值FPRM邏輯表達式,提出一種基于模擬退火遺傳算法的三值FPRM電路功耗優(yōu)化方法.首先,根據(jù)三值邏輯函數(shù)表達式和開關(guān)信號傳遞理論,建立三值FPRM電路功耗估計模型;再利用模擬退火遺傳算法對三值FPRM電路進行功耗最佳極性搜索,得到了功耗最低的FPRM電路;最后對13個MCNC Benchmark電路進行仿真.結(jié)果表明:與0極性相比,搜索到的最佳極性功耗平均節(jié)省了73.98%.

關(guān)鍵詞：三值邏輯函數(shù); FPRM電路; 模擬退火遺傳算法; 功耗

LI Kangping, WANG Pengjun, ZHANG Huihong.

(InstituteofCircuitsandSystems,NingboUniversity,Ningbo315211,ZhejiangProvince,China)

隨著集成電路規(guī)模的擴大，集成度不斷提高,數(shù)字電路的功耗與面積等問題尤顯突出[1].傳統(tǒng)的數(shù)字電路大都采用二值邏輯,但其信息含量低已成為制約集成電路發(fā)展的主要因素.多值邏輯電路增加了單線攜帶信息的能力,能有效提高空間或時間的利用率,減少數(shù)字系統(tǒng)的連線,節(jié)省電路面積與成本[2].其中，基數(shù)為3的三值邏輯因其基數(shù)最小,而較易實現(xiàn),具有代表性.

任意三值邏輯函數(shù)均可用布爾邏輯和Reed-Muller(RM)邏輯來表示[3].與傳統(tǒng)的布爾邏輯電路相比,基于RM邏輯的電路在功耗和面積等方面具有巨大的優(yōu)勢.此外,用RM邏輯表示的電路可測性更強,電路結(jié)構(gòu)更加緊湊[4-5].固定極性(Fixed-Polarity Reed-Muller, FPRM)是RM邏輯常用的表達方式.在三值FPRM邏輯函數(shù)中,n變量函數(shù)有3n個固定極性,對應(yīng)于3n個不同的三值FPRM表達式,其表達式的復(fù)雜程度由極性決定.因此,極性對三值FPRM電路的功耗和面積等性能產(chǎn)生了很大的影響.對較小規(guī)模的電路進行優(yōu)化時,可用窮舉法遍歷每個極性,但在優(yōu)化較大規(guī)模電路時,由于極性與變量存在指數(shù)關(guān)系，使得搜索空間急劇增加,窮舉法很難在有限的時間內(nèi)得到優(yōu)化結(jié)果[6].因此,需要尋求一種高效智能算法來提高搜索效率,以便盡快得到三值FPRM電路的最優(yōu)或近最優(yōu)極性.

模擬退火遺傳算法[7]是一種改進型的遺傳算法.單純的遺傳算法局部尋優(yōu)能力差,容易出現(xiàn)早熟現(xiàn)象[8].將模擬退火算法引入到經(jīng)典遺傳算法中,結(jié)合2種算法的優(yōu)化操作,可以提高算法的全局搜索能力,大大提高算法的效率.筆者通過研究三值FPRM邏輯表達式和模擬退火遺傳算法,提出了一種基于模擬退火遺傳算法的三值FPRM電路功耗優(yōu)化方法.

1三值FPRM表達式及極性轉(zhuǎn)換技術(shù)

1.1三值FPRM表達式

任何n變量的三值FPRM表達式都可表示為如下形式[9]:

(1)

表查找表

1.2三值FPRM極性轉(zhuǎn)換技術(shù)

國內(nèi)外許多專家學(xué)者對多值RM邏輯尤其對RM邏輯極性轉(zhuǎn)換進行了研究[10-12].極性轉(zhuǎn)換包括Boolean邏輯展開式到RM邏輯展開式的轉(zhuǎn)換和RM邏輯展開式不同極性間的轉(zhuǎn)換.矩陣轉(zhuǎn)換法(Matrix Transformation Method)和圖形轉(zhuǎn)換法(Map Transformation Method)是常用的多值FPRM極性轉(zhuǎn)換方法.然而上述2種極性轉(zhuǎn)換方法速度慢、時間復(fù)雜度大.文獻[12]提出了一種三值FPRM極性轉(zhuǎn)換算法,能有效提高轉(zhuǎn)換速度.其基本過程表述如下:

(1)極性初始化:隨機產(chǎn)生一個極性p,并用三進制表示p=(p1,p2,…,pn);

(4)根據(jù)新項產(chǎn)生公式,每個最小項的新項為πi：

(2)

(5)根據(jù)貢獻值計算公式：

(3)

(6)對所有的最小項重復(fù)步驟(3)～(5),最后的累加值即為RM表達式系數(shù).

表2　GF(3)互補變量和轉(zhuǎn)換矩陣

2基于模擬退火遺傳算法的三值FPRM電路功耗最佳極性搜索

2.1三值FPRM電路功耗估計模型

要實現(xiàn)三值FPRM電路功耗的最佳極性搜索,首先需要建立三值FPRM電路的功耗估計模型.分析式(1)可知,三值FPRM邏輯函數(shù)由多輸入模3加和模3乘運算組成,因此三值FPRM電路可以表示為由多輸入模3加和模3乘門組成.多輸入門的輸入輸出關(guān)系復(fù)雜程度不同,且在工藝上大多使用二輸入門,所以在電路映射之前,往往需要把多輸入模3加和模3乘門分解成一系列二輸入模3加和模3乘門,因此三值FPRM電路的功耗可看成由二輸入模3加和模3乘門引起.電路的開關(guān)活動性與功耗成正比,其值直接反映電路功耗的大小,因此可以用開關(guān)活動性表示電路的功耗.門電路的開關(guān)活動性可以用其輸出端的信號概率表示.

假設(shè)信號x=1和x=2的概率為在一段足夠長時間內(nèi)測得信號x=1和x=2的時間與總的測量時間之比,分別記作Px1和Px2.根據(jù)模3加和模3乘運算的輸入輸出關(guān)系和信號概率傳遞規(guī)律,可以分別推出二輸入模3加和模3乘門的輸出信號概率.

圖1　模3加和模3乘真值表Fig.1　The truth tables of modulo-3 addition and modulo-3 multiplication

二輸入模3加門輸出信號概率:

Px1·(1-Py1-Py2)+

(1-Px1-Px2)·Py1+Px2·Py2,

(4)

Px2·(1-Py1-Py2)+

1-Px1-Py1+(1-Px1+Px2)·Py2.

(5)

二輸入模3乘門輸出信號概率：

(6)

(7)

2.2模擬退火遺傳算法

傳統(tǒng)遺傳算法只有子代參與競爭,子代和父代之間沒有競爭關(guān)系,容易導(dǎo)致父代中優(yōu)秀個體的缺失,出現(xiàn)早熟和局部尋優(yōu)能力差等現(xiàn)象.模擬退火算法局部搜索能力強,能有效彌補遺傳算法的缺陷.模擬退火遺傳算法結(jié)合遺傳算法和模擬退火算法的優(yōu)點,并允許父代參與競爭,能有效提高算法的尋優(yōu)能力.

2.2.1構(gòu)建適應(yīng)度函數(shù)

本文搜索的三值FPRM電路功耗最佳極性為一個整數(shù)值,因此可以用其三進制形式作為本算法的編碼方式.在極性搜索過程中需要對極性進行評價,本文以功耗優(yōu)化為目的,將極性對應(yīng)的三值FPRM電路功耗作為評價標準,以此構(gòu)建適應(yīng)度函數(shù).在模擬退火遺傳算法中,適應(yīng)度函數(shù)值越大表示個體越優(yōu)秀,但功耗最佳極性要求功耗越小越好.因此,為了便于兩者結(jié)合,采用功耗的倒數(shù)來表示適應(yīng)度,設(shè)置適應(yīng)度函數(shù)如下:

f(i)=(1/poweri)×b,

(8)

其中poweri表示對應(yīng)極性下的三值FPRM電路功耗,b為放大系數(shù).

2.2.2交叉和變異操作

交叉操作能把父代中的優(yōu)秀基因遺傳給下一代,是遺傳算法中的一個重要操作,起核心作用.本文通過一致交叉方法實現(xiàn)交叉操作:首先以一定概率選取父代中的2個個體F1和F2,同時隨機產(chǎn)生一個等長的二進制碼A;然后根據(jù)父代個體和二進制碼A產(chǎn)生2個子代個體S1和S2.交叉過程如圖1所示:當(dāng)二進制碼A對應(yīng)位為1時,子代S1繼承父代F1的基因,子代S2繼承父代F2的基因;當(dāng)二進制碼A對應(yīng)位為0時,子代S1繼承父代F2的基因,子代S2繼承父代F1的基因.

圖2　一致交叉操作Fig.2　The operation of uniform crossover

變異操作是遺傳算法的另一個重要操作,表示種群中某些個體的基因發(fā)生了突變.變異操作是一種局部隨機搜索,能防止算法早熟.本文變異操作的具體步驟為:以一個小概率選擇需要變異的個體,隨機產(chǎn)生變異位,變換變異位的值,變換規(guī)則為“0→1，1→2，2→0”.

2.2.3模擬退火選擇操作

模擬退火選擇操作是模擬退火遺傳算法與傳統(tǒng)遺傳算法的不同之處,它允許父代參加競爭,使父代中的優(yōu)秀個體得以保存.本文的模擬退火選擇操作為:首先根據(jù)適應(yīng)度值的大小對父代和子代進行排序;然后在父代和子代群體中各自選擇適應(yīng)度值最優(yōu)的2w/3個個體,組成新的群體;最后對新群體進行退火選擇,選取w個個體組成新的種群.個體i被選取的概率為:

(9)

其中,f(i)表示個體i的適應(yīng)度值;Tk表示退火溫度,Tk=1/ln(k/T0+1),k=1,2,…;w表示種群規(guī)模;T0表示起始溫度.

2.3算法描述

算法的基本步驟:

(1)讀入PLA格式的MCNC Benchmark電路,運用三值積之和表達式到三值FPRM表達式的轉(zhuǎn)換技術(shù),將三值最小項表達式轉(zhuǎn)換到0極性下的三值FPRM表達式;

(2)生成父代種群:隨機產(chǎn)生w個用三進制表示的整數(shù),計算父代種群個體的適應(yīng)度;

(3)生成子代種群:父代種群通過交叉和變異操作產(chǎn)生子代種群,計算子代種群個體的適應(yīng)度;

(4)進行模擬退火選擇操作產(chǎn)生新的父代種群,計算新的父代種群個體適應(yīng)度;

(5)重復(fù)步驟(3)和(4),直到滿足最大演化代數(shù),輸出最佳極性及其對應(yīng)的電路功耗.

在進行最佳極性搜索之前需要讀入PLA格式電路,然而目前只有標準的二值PLA格式電路,因此先用文獻[13]所提方法將標準的二值PLA格式電路轉(zhuǎn)換為三值PLA格式電路,然后運用上述所提算法進行最佳極性搜索.

3仿真結(jié)果與分析

本文所提算法在Windows 7 64位操作系統(tǒng),Intel(R) Core(TM) i3-2130 CPU 3.40 GHZ, 4 G RAM運行環(huán)境下,用C語言通過VC6.0編譯實現(xiàn),隨機選取13個MCNC Benchmark電路進行仿真,搜索到的最佳極性與0極性比較.為計算三值FPRM電路的開關(guān)活動性,隨機產(chǎn)生15組輸入信號概率:(P1,P2)={(0.21,0.53),(0.49,0.30),(0.33,0.24),(0.68,0.13),(0.15,0.26),(0.57,0.22),(0.18,0.51),(0.71,0.24),(0.08,0.35),(0.57,0.32),(0.46,0.28),(0.17,0.05),(0.32,0.43),(0.14,0.72),(0.25,0.61)}.

三值FPRM電路功耗最佳極性搜索結(jié)果如表3所示.其中,列1和列2分別為電路名稱和輸入/輸出變量個數(shù);列3～5分別表示0極性下二輸入模3加的門數(shù)量、二輸入模3乘的門數(shù)量和電路功耗;列6～9分別表示所提算法搜索到的最佳極性、最佳極性下三值FPRM電路二輸入模3加的門數(shù)量、二輸入模3乘的門數(shù)量和電路功耗.

表3　三值FPRM電路功耗的最佳極性搜索結(jié)果

與0極性相比，最佳極性在模3加的門數(shù)量、模3乘的門數(shù)量以及功耗上節(jié)省的百分比如表4所示.模3加的門數(shù)量、模3乘的門數(shù)量和功耗節(jié)省的百分比定義如下:

(10)

(11)

(12)

其中,SaveMod3-A、SaveMod3-M和SavePower分別表示模3加的門數(shù)量、模3乘的門數(shù)量和功耗的節(jié)省;Mod3-A0、Mod3-M0和Power0表示0極性下模3加的門數(shù)量、模3乘的門數(shù)量和功耗大小;Mod3-ASAGA、Mod3-MSAGA和PowerSAGA表示所提算法搜索到的最佳極性下模3加的門數(shù)量、模3乘的門數(shù)量和功耗大小.

表4　三值FPRM電路門數(shù)和功耗節(jié)省百分比

分析數(shù)據(jù)可知,所提方法搜索到的最佳極性與0極性相比優(yōu)化效果明顯,其中clpl電路在模3加的門數(shù)量、模3乘的門數(shù)量和功耗上分別節(jié)省了80.00%,66.67%和89.78%,13個測試電路在模3加的門數(shù)量、模3乘的門數(shù)量和功耗上分別平均節(jié)省了57.64%,46.25%和73.98%.

4結(jié)論

通過對三值FPRM邏輯表達式的研究，建立了三值FPRM電路功耗估計模型,并結(jié)合三值FPRM極性轉(zhuǎn)換技術(shù),提出了一種基于模擬退火遺傳算法的三值FPRM電路功耗最佳極性搜索方法.所提方法在Windows 7操作系統(tǒng)下,基于C語言通過VC6.0編譯實現(xiàn),對13個MCNC Benchmark電路進行仿真，結(jié)果表明,所提方法搜索到的最佳極性與0極性相比具有較好的優(yōu)化效果.

參考文獻(References)：

[1]鄭雪松,汪鵬君,楊乾坤.基于絕熱多米諾邏輯的三值移位寄存器設(shè)計[J].浙江大學(xué)學(xué)報：理學(xué)版,2014,41(4):427-431.

ZHENG Xuesong, WANG Pengjun, YANG Qiankun. Design of ternary shift register based on adiabatic domino logic[J]. Journal of Zhejiang University: Science Edition, 2014, 41(4): 427-431.

[2]汪鵬君,楊乾坤,鄭雪松.三值絕熱多米諾加法器開關(guān)級設(shè)計[J].電子與信息學(xué)報,2012,34(10):2514-2519.

WANG Pengjun, YANG Qiankun, ZHENG Xuesong. Design of ternary adiabatic domino adder on switch-level[J]. Journal of Electronics & Information Technology,2012, 34(10): 2514-2519.

[3]RAFIEV A, MOKHOV A, BUMS F P, et al. Mixed radix reed-muller expansions[J]. IEEE Transactions on Computers, 2012, 61(8): 1189-1202.

[4]Al JASSANI B A, URQUHART N, ALMAINI A E A. Manipulation and optimisation techniques for Boolean logic[J]. IET Computers & Digital Techniques, 2010, 4(3): 227-239.

[5]RAHAMAN H, DAS D K, BHATTACHARYA B B. Testable design of AND-EXOR logic networks with universal test sets[J]. Computers & Electrical Engineering, 2009, 35(5): 644-658.

[6]王振海,汪鵬君,俞海珍,等.基于PSO算法的FPRM電路延時和面積優(yōu)化[J].電路與系統(tǒng)學(xué)報, 2012,17(5):75-80.

WANG Zhenhai, WANG Pengjun, YU Haizhen, et al. Delay and area optimization for FPRM circuits based on PSO algorithm[J]. Journal of Circuits and Systems, 2012, 17(5): 75-80.

[7]賈偉娜,劉順蘭.模擬退火遺傳算法在DOA估計技術(shù)中的應(yīng)用[J].Computer Engineering and Applications,2014, 50(12): 266-270.

JIA Weina, LIU Shunlan. Application of simulated annealing genetic algorithm in DOA estimation technique[J]. Computer Engineering and Applications, 2014, 50(12)：266-270.

[8]王小平,曹立明.遺傳算法:理論,應(yīng)用及軟件實現(xiàn)[M].西安：西安交通大學(xué)出版社,2002.

WANG Xiaoping，CAO Liming. Genetic Algorithm: Theory, Application and Software Implementation[M]. Xi’an：Xi’an Jiaotong University Press，2002.

[9]FALKOWSKI B J, FU C. Polynomial expansions over GF (3) based on fastest transformation[C]//Proceedings of the 33rd International Symposium on Multiple-Valued Logic. Washington: IEEE Computer Society, 2003: 40-45.

[10]FALKOWSKI B J, FU C. Fastest classes of linearly independent transforms over GF (3) and their properties[J]. IEE Proceedings-Computers and Digital Techniques,2005, 152(5): 567-576.

[11]FU C, FALKOWSKI B J. Ternary fixed polarity linear Kronecker transforms and their comparison with ternary Reed Muller transform[J]. Journal of Circuits, Systems and Computers,2005, 14(4): 721-733.

[12]孫飛,汪鵬君,俞海珍.三值FPRM電路極性間轉(zhuǎn)換算法及其在面積優(yōu)化中的應(yīng)用[J].浙江大學(xué)學(xué)報:理學(xué)版,2014,41(1):43-48.

SUN Fei, WANG Pengjun, YU Haizhen, et al. Ternary FPRM circuit conversion algorithm between polarities and its application in area optimization[J]. Journal of Zhejiang University: Science Edition, 2014, 41(1): 43-48.

[13]FALKOWSKI B J, LOZANO C C, RAHARDJA S. Column polarity matrix algorithm for ternary fixed polarity Reed-Muller expansions[J]. Journal of Circuits, Systems and Computers,2006, 15(2): 243-262.

The search of the best power polarity of ternary FPRM circuit based on simulated annealing genetic algorithm. Journal of Zhejiang University(Science Edition), 2016,43(2):190-194,199

Abstract:For n-variable ternary FPRM (Fixed-Polarity Reed-Muller) logic function, there are 3n fixed polarities. The power of ternary FPRM circuit with different polarities is different from each other. A scheme searching for the best polarity on the power of ternary FPRM circuit is proposed. Firstly, according to the ternary FPRM logic function expression and the switch signal transmission theory, a power estimation model for ternary FPRM circuit is established. Secondly, simulated annealing genetic algorithm (SAGA) is used to search for the best polarity, so as to get the best power consumption FPRM circuit. Finally, 13 MCNC benchmarks are used to verify the effectiveness of the proposed method. Results show that the optimized ternary FPRM circuits save 73.98% power in average than the corresponding FPRM circuits under polarity 0.

Key Words:ternary logic function; FPRM circuit; simulated annealing genetic algorithm; power consumption

中圖分類號：TN 79

文獻標志碼：A

文章編號：1008-9497(2016)02-190-05

DOI:10.3785/j.issn.1008-9497.2016.02.012

作者簡介：厲康平(1991-)，男，碩士研究生，主要從事高信息密度和低功耗集成電路理論及設(shè)計研究.*通信作者,ORCID:http://orcid.org/0000-0002-1461-3719,E-mail:wangpengjun@nbu.edu.cn.

基金項目：浙江省自然科學(xué)基金資助項目(LY13F040003)；國家自然科學(xué)基金資助項目(61234002，61306041).

收稿日期：2015-03-24.