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

厲康平，汪鵬君，張會紅

(寧波大學 電路與系統研究所, 浙江 寧波 315211)

?

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

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

(寧波大學 電路與系統研究所, 浙江 寧波 315211)

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

關鍵詞：三值邏輯函數; FPRM電路; 模擬退火遺傳算法; 功耗

LI Kangping, WANG Pengjun, ZHANG Huihong.

(InstituteofCircuitsandSystems,NingboUniversity,Ningbo315211,ZhejiangProvince,China)

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

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

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

1三值FPRM表達式及極性轉換技術

1.1三值FPRM表達式

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

(1)

表查找表

1.2三值FPRM極性轉換技術

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

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

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

(2)

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

(3)

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

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

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

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

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

假設信號x=1和x=2的概率為在一段足夠長時間內測得信號x=1和x=2的時間與總的測量時間之比,分別記作Px1和Px2.根據模3加和模3乘運算的輸入輸出關系和信號概率傳遞規律,可以分別推出二輸入模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模擬退火遺傳算法

傳統遺傳算法只有子代參與競爭,子代和父代之間沒有競爭關系,容易導致父代中優秀個體的缺失,出現早熟和局部尋優能力差等現象.模擬退火算法局部搜索能力強,能有效彌補遺傳算法的缺陷.模擬退火遺傳算法結合遺傳算法和模擬退火算法的優點,并允許父代參與競爭,能有效提高算法的尋優能力.

2.2.1構建適應度函數

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

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

(8)

其中poweri表示對應極性下的三值FPRM電路功耗,b為放大系數.

2.2.2交叉和變異操作

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

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

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

2.2.3模擬退火選擇操作

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

(9)

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

2.3算法描述

算法的基本步驟:

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

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

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

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

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

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

3仿真結果與分析

本文所提算法在Windows 7 64位操作系統,Intel(R) Core(TM) i3-2130 CPU 3.40 GHZ, 4 G RAM運行環境下,用C語言通過VC6.0編譯實現,隨機選取13個MCNC Benchmark電路進行仿真,搜索到的最佳極性與0極性比較.為計算三值FPRM電路的開關活動性,隨機產生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電路功耗最佳極性搜索結果如表3所示.其中,列1和列2分別為電路名稱和輸入/輸出變量個數;列3～5分別表示0極性下二輸入模3加的門數量、二輸入模3乘的門數量和電路功耗;列6～9分別表示所提算法搜索到的最佳極性、最佳極性下三值FPRM電路二輸入模3加的門數量、二輸入模3乘的門數量和電路功耗.

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

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

(10)

(11)

(12)

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

表4　三值FPRM電路門數和功耗節省百分比

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

4結論

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

參考文獻(References)：

[1]鄭雪松,汪鵬君,楊乾坤.基于絕熱多米諾邏輯的三值移位寄存器設計[J].浙江大學學報：理學版,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]汪鵬君,楊乾坤,鄭雪松.三值絕熱多米諾加法器開關級設計[J].電子與信息學報,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電路延時和面積優化[J].電路與系統學報, 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估計技術中的應用[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]王小平,曹立明.遺傳算法:理論,應用及軟件實現[M].西安：西安交通大學出版社,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電路極性間轉換算法及其在面積優化中的應用[J].浙江大學學報:理學版,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-)，男，碩士研究生，主要從事高信息密度和低功耗集成電路理論及設計研究.*通信作者,ORCID:http://orcid.org/0000-0002-1461-3719,E-mail:wangpengjun@nbu.edu.cn.

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

收稿日期：2015-03-24.