基于人口遷移算法的三值FPRM電路面積最佳極性搜索

厲康平， 汪鵬君， 張會(huì)紅（寧波大學(xué)電路與系統(tǒng)研究所，浙江寧波 315211）

基于人口遷移算法的三值FPRM電路面積最佳極性搜索

厲康平， 汪鵬君， 張會(huì)紅
（寧波大學(xué)電路與系統(tǒng)研究所，浙江寧波 315211）

人口遷移算法是一種新的全局優(yōu)化搜索算法，主要模擬人口隨著經(jīng)濟(jì)重心發(fā)生轉(zhuǎn)移和隨著壓力增加而擴(kuò)散的機(jī)制，其收斂性和全局尋優(yōu)能力較強(qiáng)。三值固定極性RM（Fixed-polarity Reed-Muller，F(xiàn)PRM）電路的面積大小與其極性有關(guān)。通過(guò)對(duì)人口遷移算法的研究，提出了一種三值FPRM電路面積優(yōu)化方案。首先根據(jù)三值FPRM表達(dá)式和電路面積之間的內(nèi)在聯(lián)系，建立面積優(yōu)化模型；然后利用人口遷移算法對(duì)三值FPRM電路進(jìn)行面積最佳極性搜索；最后對(duì)10個(gè)MCNC Benchmark電路進(jìn)行測(cè)試。結(jié)果表明：與整體退火遺傳算法相比，本文算法在面積和時(shí)間上分別平均節(jié)省10.04%和56.59%。

人口遷移算法；三值FPRM電路；面積優(yōu)化；極性搜索

search

任意三值邏輯函數(shù)均可以用布爾邏輯和Reed-Muller（RM）邏輯來(lái)表示［1］，與傳統(tǒng)的布爾邏輯相比，基于RM邏輯的通信電路、奇偶校驗(yàn)電路、運(yùn)算電路等具有更緊湊的結(jié)構(gòu)［2］和更好的可測(cè)性［3］。RM邏輯通常采用固定極性（Fixed-polarity Reed-Muller，F(xiàn)PRM）和混合極性（Mixed-polarity Reed-Muller，MPRM）兩種表達(dá)方式。在n變量的三值FPRM邏輯函數(shù)中有3n個(gè)固定極性，對(duì)應(yīng)3n個(gè)不同的三值FPRM表達(dá)式，其表達(dá)式的簡(jiǎn)單與復(fù)雜程度由極性決定，因此，極性對(duì)三值FPRM電路的功耗、面積等性能指標(biāo)產(chǎn)生很大的影響。對(duì)較小規(guī)模的電路進(jìn)行優(yōu)化時(shí)，可以使用窮舉法遍歷每個(gè)極性；對(duì)較大規(guī)模電路進(jìn)行優(yōu)化時(shí)，由于極性與變量存在指數(shù)關(guān)系使得搜索空間急劇增加，窮舉法很難在有限的時(shí)間內(nèi)得到優(yōu)化結(jié)果。因此，需要尋求一種高效、智能的算法提高搜索效率，以便盡快得到三值FPRM電路的最優(yōu)或近最優(yōu)極性［4］。

人口遷移算法（Population Migration Algorithm，PMA）是周永華等［5］根據(jù)人口遷移規(guī)律提出的一種新的全局優(yōu)化搜索算法，主要模擬人口隨著經(jīng)濟(jì)重心發(fā)生轉(zhuǎn)移和隨著壓力增加而擴(kuò)散的機(jī)制。人口遷移算法是一種概率搜索算法［6］，實(shí)現(xiàn)全局并行搜索，并在搜索過(guò)程中不斷地向可能包含最優(yōu)解的空間轉(zhuǎn)移，尋找最優(yōu)或近最優(yōu)解。人口遷移算法原理簡(jiǎn)單易操作，與遺傳算法相比［5］，部分函數(shù)的優(yōu)化效果明顯提高，且收斂性和全局尋優(yōu)能力較強(qiáng)。本文在三值FPRM電路極性優(yōu)化中結(jié)合人口遷移算法，提出了一種基于人口遷移算法的三值FPRM電路面積最佳極性搜索方法。

1　三值FPRM電路面積估計(jì)模型和極性轉(zhuǎn)換技術(shù)

1.1三值FPRM電路面積估計(jì)模型

n變量的三值FPRM邏輯函數(shù)有3n個(gè)固定極性，與之對(duì)應(yīng)的有3n個(gè)不同的FPRM表達(dá)式。當(dāng)極性為p時(shí)，任意三值FPRM邏輯函數(shù)的表達(dá)式可表示為［7］

表1　查找表Table 1 Look up table of

表1　查找表Table 1 Look up table of

pjijx·ijj 0 0 1 0 1 x j 0 2 x 2j 1 0 1 1 1 x j⊕1 1 2 （x j⊕1）2 2 0 1 2 1 x j⊕2 2 2 （x j⊕2）2

分析公式（1）可知，三值FPRM電路由多輸入模3加運(yùn)算和多輸入模3乘運(yùn)算組成，因此可以用兩種邏輯運(yùn)算的數(shù)量來(lái)表示三值FPRM電路的面積。多輸入運(yùn)算的輸入、輸出關(guān)系復(fù)雜程度不同，在估算面積之前需要把多輸入運(yùn)算分解成二輸入運(yùn)算，再以二輸入運(yùn)算的數(shù)量來(lái)衡量電路面積。三值FPRM電路的面積即為二輸入模3加運(yùn)算與二輸入模3乘運(yùn)算的數(shù)量之和。

根據(jù)面積估計(jì)模型，可以設(shè)置人口遷移算法中吸引力的大小。在人口遷移算法中，吸引力越大表示人口所在地的經(jīng)濟(jì)水平越高。面積最佳極性要求面積越小越好，因此，為了便于兩者結(jié)合，采用面積的倒數(shù)表示吸引力。設(shè)置吸引力函數(shù)如下：

其中：attraction表示吸引力大小，其值越大表示面積優(yōu)化效果越好；No._of_Mod3-A表示二輸入模3加運(yùn)算的數(shù)量；No._of_Mod3-M表示二輸入模3乘運(yùn)算的數(shù)量；a為放大系數(shù)。

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

在電路的面積優(yōu)化過(guò)程中，需要進(jìn)行極性轉(zhuǎn)換來(lái)檢驗(yàn)每個(gè)極性。常用的三值FPRM極性轉(zhuǎn)換方法有矩陣轉(zhuǎn)換法（Matrix Transformation Method）和圖形轉(zhuǎn)換法（Map Transformation Method）［8-9］。然而這兩種方法的極性轉(zhuǎn)換速度慢，時(shí)間復(fù)雜度大。文獻(xiàn)［10］提出了一種三值FPRM極性轉(zhuǎn)換算法，能有效提高極性轉(zhuǎn)換速度。其基本過(guò)程如下：

（1）極性初始化。隨機(jī)產(chǎn)生一個(gè)極性p，并用三進(jìn)制表示p=（p1，p2，…，pn）。

（2）根據(jù)pi產(chǎn)生與之相應(yīng)的固定極性GF轉(zhuǎn)換矩陣G3〈pi〉，如下所示，pi∈｛p1，p2，…，pn｝。

其中π=（π1，π2，…，πn），vi=G〈pi〉3［πi，mi］，i=1，2，…，n。

（3）將最小項(xiàng)m表示成三進(jìn)制序列m=（m1，m2，…，mn），其相應(yīng)的函數(shù)值為f（m）。

（4）根據(jù)式（2），產(chǎn)生每個(gè)最小項(xiàng)的新項(xiàng)πi。

（5）根據(jù)式（3），求出所產(chǎn)生的新項(xiàng)對(duì)RM系數(shù)所作的貢獻(xiàn)v（π），并在索引表中疊加它的貢獻(xiàn)值。

（6）對(duì)所有的最小項(xiàng)重復(fù)步驟（3）～（5），最后的累加值即為RM表達(dá)式系數(shù)。

2　基于PMA的三值FPRM電路面積優(yōu)化

2.1概述

人口遷移算法是一種全局優(yōu)化的仿生算法，將目標(biāo)函數(shù)的選擇空間模擬成人類(lèi)的生存空間，將目標(biāo)函數(shù)值模擬成某個(gè)地域的吸引力，利用人口流動(dòng)、遷移和擴(kuò)散行為搜索可行解，通過(guò)個(gè)體的流動(dòng)、遷移和擴(kuò)散行為找到局部最優(yōu)解，最后比較多個(gè)局部最優(yōu)解得到全局最優(yōu)解。

2.2人口遷移與面積優(yōu)化的關(guān)系

基于人口遷移算法的FPRM電路面積優(yōu)化要將人口遷移與面積優(yōu)化兩者聯(lián)系起來(lái)。人口遷移含有以下幾個(gè)關(guān)鍵要素：人口所在地、人口所在地的吸引力、吸引力最大地點(diǎn)、最大吸引力、人口可移動(dòng)地表空間、優(yōu)惠區(qū)域、遷往優(yōu)惠區(qū)域、人口壓力導(dǎo)致遷離優(yōu)惠

區(qū)域。FPRM電路面積優(yōu)化含有以下幾個(gè)關(guān)鍵要素：極性、相應(yīng)極性的面積大小、最佳極性、最小面積、可選擇的極性空間、最佳極性所在區(qū)間、極性向最佳極性所在區(qū)間跳變、跳出局部最佳極性。表2給出了人口遷移到FPRM面積優(yōu)化的映射。

表2　人口遷移到FPRM面積優(yōu)化映射Table 2 Mapping of population migration to FPRM area optimization

2.3人口移動(dòng)

2.3.1概述 人口移動(dòng)是指人口在地域或空間位置上的移動(dòng)，包括人口流動(dòng)、人口遷移和人口擴(kuò)散。人口流動(dòng)是人口在各自區(qū)域內(nèi)的移動(dòng)，是帶有自發(fā)性質(zhì)、移動(dòng)規(guī)律較差的人口行為。人口遷移是人口跨越各自區(qū)域在整個(gè)生存空間上的移動(dòng)，是帶有選擇性質(zhì)、移動(dòng)規(guī)律較強(qiáng)的人口行為。人口擴(kuò)散是指人口在優(yōu)惠區(qū)域壓力達(dá)到某一程度后遷往其他區(qū)域的人口行為，在一定程度上可以理解為人口遷移。2.3.2 人口流動(dòng) 在人口遷移算法中，人口流動(dòng)表示人口在各自區(qū)域內(nèi)帶有某種自發(fā)性質(zhì)的人口行為，將其運(yùn)用到三值FPRM電路面積優(yōu)化中表示在某一極性區(qū)間內(nèi)極性的變動(dòng)。因?yàn)槿丝诹鲃?dòng)的規(guī)律性較差，因此將人口流動(dòng)處理為隨機(jī)的。為了使區(qū)域內(nèi)每個(gè)極性的搜索機(jī)會(huì)相等，將人口流動(dòng)處理成均勻隨機(jī)變動(dòng)。模擬時(shí)，可以在每個(gè)極性區(qū)間均勻隨機(jī)產(chǎn)生多個(gè)極性：

Xi=2×Δt×rand（）＋（centeri－Δt）（5）

其中：Δt表示極性區(qū)間的半徑；rand（）為隨機(jī)函數(shù)；centeri表示第i個(gè)極性區(qū)間的中心。

2.3.3人口遷移 在人口遷移算法中，人口受吸引力最大地點(diǎn)的吸引，遷往優(yōu)惠區(qū)域。在三值FPRM電路面積優(yōu)化中可以表示為極性向最佳極性所在區(qū)間跳變。模擬時(shí)，以面積最小所對(duì)應(yīng)的極性為中心，按Δt的大小確定最佳極性所在區(qū)間，在此區(qū)間內(nèi)均勻隨機(jī)產(chǎn)生若干個(gè)極性，替換原有極性。2.3.4 人口擴(kuò)散 在人口遷移算法中，當(dāng)優(yōu)惠區(qū)域的人口壓力達(dá)到一定程度后，人口就會(huì)向外遷移。在三值FPRM電路面積優(yōu)化中可以表示為當(dāng)極性區(qū)間收縮到一定程度，即Δt＜q（q表示人口壓力，為預(yù)先給定的正小量），極性發(fā)生跳躍。模擬時(shí)可以簡(jiǎn)單化處理，在整個(gè)極性空間內(nèi)均勻隨機(jī)產(chǎn)生若干個(gè)極性，替換原有極性。

2.4參數(shù)設(shè)置

人口遷移算法需設(shè)置5個(gè)參數(shù)：人口規(guī)模w、人口流動(dòng)次數(shù)l、人口壓力參數(shù)q、收縮系數(shù)c，人口擴(kuò)散次數(shù)s。人口遷移算法的參數(shù)設(shè)置對(duì)優(yōu)化效果會(huì)產(chǎn)生重要影響。人口規(guī)模決定參與搜索最佳極性的人口基數(shù)，規(guī)模越大，人口基數(shù)越大；人口流動(dòng)次數(shù)決定搜索次數(shù)，流動(dòng)次數(shù)越多，搜索次數(shù)越多；人口壓力參數(shù)決定搜索區(qū)域的極限范圍，人口壓力參數(shù)越小，搜索區(qū)域的極限范圍越小；收縮系數(shù)決定搜索區(qū)域的收縮速度，收縮系數(shù)越??；收縮速度越慢。人口擴(kuò)散次數(shù)決定跳出局部最優(yōu)解的概率，人口擴(kuò)散次數(shù)越多，跳出局部最優(yōu)解的概率越高。增大人口規(guī)模w，增加人口流動(dòng)次數(shù)l和人口擴(kuò)散次數(shù)s，減小人口壓力參數(shù)q和收縮系數(shù)c，可以使搜索更充分，增加找到全局最優(yōu)極性的概率。另外，減小人口壓力參數(shù)q和收縮系數(shù)c還可以提高搜索精度。

人口遷移算法的參數(shù)為事先設(shè)置好的固定值，然而在三值FPRM電路優(yōu)化中，電路的規(guī)模存在很大差異，如果參數(shù)值固定會(huì)影響算法的搜索效率。針對(duì)此問(wèn)題，本文結(jié)合人口遷移算法和三值FPRM電路，提出了一種動(dòng)態(tài)參數(shù)設(shè)置法，參數(shù)設(shè)置隨電路規(guī)模的變化而變化。具體參數(shù)設(shè)置如下：人口規(guī)模為三值FPRM電路的輸入變量個(gè)數(shù)；人口流動(dòng)次數(shù)為極性所在區(qū)間的半徑大小Δt，其大小由式（4）求得；人口壓力參數(shù)為Δt/10；收縮系數(shù)c=0.3；人口擴(kuò)散次數(shù)設(shè)置為s=15（小規(guī)模電路）或s=2（較大規(guī)模電路）。這是因?yàn)楫?dāng)電路規(guī)模較小時(shí)，人口流動(dòng)次數(shù)較小，需要增加人口擴(kuò)散次數(shù)提高搜索能力；而電路規(guī)模較大時(shí)，人口流動(dòng)次數(shù)較大，僅僅需要進(jìn)行人口擴(kuò)散防止陷入局部最優(yōu)解。Δt=3w/w2（6）其中w表示人口規(guī)模，即三值FPRM電路的輸入變量個(gè)數(shù)。

2.5面積優(yōu)化算法

本文算法的基本流程如下：

（1）初始化。在極性空間內(nèi)均勻隨機(jī)產(chǎn)生w個(gè)極性，并根據(jù)Δt確定每個(gè)極性所在的區(qū)域，初始化最佳極性和面積最優(yōu)值。

（2）極性變動(dòng)。在各極性區(qū)間內(nèi)隨機(jī)變動(dòng)每個(gè)極性，更新最佳極性和面積最優(yōu)值，隨機(jī)變動(dòng)l次。

（3）極性轉(zhuǎn)移。以面積最優(yōu)值對(duì)應(yīng)的極性為中點(diǎn)，按Δt的大小確定最佳極性區(qū)間。在該區(qū)域內(nèi)均勻隨機(jī)產(chǎn)生w個(gè)極性，替換原來(lái)的極性，更新最佳極性和面積最優(yōu)值。

（4）收縮最佳極性區(qū)間。令Δt=（1－c）Δt （c為收縮系數(shù)，0＜c＜1），收縮極性所在區(qū)間，重復(fù)步驟（3），直到Δt＜q。

（5）極性跳躍。當(dāng)收縮最佳極性區(qū)域到一定程度（Δt＜q）后，在極性空間內(nèi)均勻隨機(jī)產(chǎn)生w個(gè)極性，替換原來(lái)的極性，更新最佳極性和面積最優(yōu)值，重復(fù)步驟（2）～步驟（4），直到滿足人口擴(kuò)散次數(shù)s，算法結(jié)束。

基于PMA算法的三值FPRM電路面積優(yōu)化偽代碼如下：

3　實(shí)驗(yàn)驗(yàn)證與分析

本文算法在Windows 7，64位操作系統(tǒng)，Intel （R）Core（TM）i3-2130 CPU 3.40 GHz，4 G RAM運(yùn)行環(huán)境下，用C語(yǔ)言通過(guò)VC6.0編譯實(shí)現(xiàn)，采用10個(gè)MCNC Benchmark電路進(jìn)行仿真驗(yàn)證，優(yōu)化結(jié)果與文獻(xiàn)［11］的整體退火遺傳算法進(jìn)行比較。在進(jìn)行最佳極性搜索之前需要讀入PLA格式電路，然而目前只有標(biāo)準(zhǔn)的二值PLA格式電路，因此先用文獻(xiàn)［12］中的方法將標(biāo)準(zhǔn)的二值PLA格式電路轉(zhuǎn)換為三值PLA格式電路，然后運(yùn)用本文算法進(jìn)行最佳極性搜索。

三值FPRM電路面積最佳極性搜索結(jié)果如表3所示。表中InputsB為二值電路輸入變量個(gè)數(shù)，Inputs T為三值電路輸入變量個(gè)數(shù)，Polarity表示最佳極性，Mod3-A，M表示模3加，模3乘運(yùn)算數(shù)量，Time為算法的運(yùn)行時(shí)間。

與整體退火遺傳算法相比，本文算法在面積和時(shí)間上節(jié)省的百分比如表4所示。

表3　三值FPRM電路面積最佳極性搜索結(jié)果Table 3 Search results of the best area polarity of ternary FPRM circuit

表4　三值FPRM電路面積和時(shí)間節(jié)省百分比Table 4 Percentage saves of the area for ternary FPRM circuit and the optimization time

面積和時(shí)間節(jié)省的百分比定義如下：

其中：SaveArea和SaveTime表示面積和算法運(yùn)行時(shí)間的節(jié)省；AreaWAGA和TimeWAGA表示整體退火遺傳算法的優(yōu)化面積和優(yōu)化時(shí)間；AreaPMA和TimePMA表示所提算法的優(yōu)化面積和優(yōu)化時(shí)間。

分析表4數(shù)據(jù)可知，本文方法優(yōu)化效果明顯。與文獻(xiàn)［11］的整體退火遺傳算法相比，10個(gè)測(cè)試電路面積和時(shí)間平均節(jié)省10.04%和56.59%。

4　結(jié) 論

本文通過(guò)對(duì)人口遷移算法的研究，提出了一種三值FPRM電路面積優(yōu)化方案。通過(guò)對(duì)10個(gè)MCNC Benchmark電路進(jìn)行仿真驗(yàn)證表明，本文方案優(yōu)化后極性與整體退火遺傳算法相比具有明顯的優(yōu)化效果。由于人口遷移算法發(fā)展較晚，本身還存在缺陷，因此在今后的研究中，將利用算法融合思想對(duì)人口遷移算法加以改進(jìn)，使優(yōu)化效果更明顯。

［1］ 汪鵬君，王振海，陳耀武，等.固定極性Reed-Muller電路最佳延時(shí)極性搜索［J］.浙江大學(xué)學(xué)報(bào)（工學(xué)版），2013，47（2）：361-366.

［2］ AL JASSANI B A，URQUHART N，ALMAINI A E A. Manipulation and optimization techniques for Boolean logic ［J］.IET Computers and Digital Techniques，2010，4（3）：227-239.

［3］ RAHAMAN H，DAS D K，BHATTACHARYA B B. Testable design of AND-EXOR logic networks with universal test sets［J］.Computers and Electrical Engineering，2009，35 （5）：644-658.

［4］ 王振海，汪鵬君，俞海珍，等.基于PSO算法的FPRM電路延時(shí)和面積優(yōu)化［J］.電路與系統(tǒng)學(xué)報(bào)，2012，17（5）：75-80.

［5］ 周永華，毛宗源.一種新的全局優(yōu)化搜索算法——人口遷移算法（I）［J］.華南理工大學(xué)學(xué)報(bào)（自然科學(xué)版），2003，31（3）：1-5.

［6］ 周永華，毛宗源.一種新的全局優(yōu)化搜索算法——人口遷移算法（Ⅱ）［J］.華南理工大學(xué)學(xué)報(bào)（自然科學(xué)版），2003，31（4）：41-43.

［7］ FALKOWSKI B J，CHENG Fu.Polynomial expansions over GF（3）based on fastest transformation［C］//33rd International Symposium on Multiple-Valued Logic.Tokyo，Japan：IEEE，2003：40-45.

［8］ FALKOWSKI B J，CHENG Fu.Fastest classes of linearly independent transforms over GF（3）and their properties［J］. IEE Proceedings-Computers and Digital Techniques，2005，152（5）：567-576.

［9］ CHENG FU，F(xiàn)ALKOWSKI 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.

［10］ 孫飛，汪鵬君，俞海珍.三值FPRM電路極性間轉(zhuǎn)換算法及其在面積優(yōu)化中的應(yīng)用［J］.浙江大學(xué)學(xué)報(bào)（理學(xué)版），2014，41 （1）：43-48.

［11］ SUN Fei，WANG Pengjun，YU Haizhen.Best polarity searching for ternary FPRM logic circuit area based on whole annealing genetic algorithm［C］//2013 IEEE 10th International Conference on ASIC（ASICON）.Shenzhen：IEEE，2013：1-4.［12］ 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.

Best Area Polarity Searching for Ternary FPRM Circuit Based on Population Migration Algorithm

LI Kang-ping， WANG Peng-jun， ZHANG Hui-hong
（Institute of Circuits and Systems，Ningbo University，Ningbo 315211，Zhejiang，China）

Population migration algorithm（PMA）is a new global search optimization algorithm.It simulates the mechanism that population moves along with the transformation of economic center and population diffuses with the pressure increasing.The polarity of ternary FPRM（Fixed-polarity Reed-Muller）circuit determines its area.By analyzing PMA algorithm，this paper proposes an area optimization scheme for ternary FPRM circuit.Firstly，according to the internal relation between the ternary FPRM expression and the circuit area，an area optimization model is established.Secondly，the PMA is utilized to search the best polarity for the area of FPRM circuit.Finally，ten MCNC Benchmark circuits are tested，which show that compared with the whole annealing genetic algorithm，the proposed algorithm can save 10.04%and 56.59%respectively on average on the area and the time.

population migration algorithm；ternary FPRM circuit；area optimization；polarity

TP332.2

A

1006-3080（2016）01-0104-06 DOI：10.14135/j.cnki.1006-3080.2016.01.017

2015-03-24

國(guó)家自然科學(xué)基金（61234002，61306041）；浙江省自然科學(xué)基金（LY13F040003）

厲康平（1991-），男，碩士生，主要從事高信息密度和低功耗集成電路理論及設(shè)計(jì)方面的研究。

汪鵬君，E-mail：wangpengjun@nbu.edu.cn