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

厲康平， 汪鵬君， 張會紅（寧波大學電路與系統研究所，浙江寧波 315211）

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

厲康平， 汪鵬君， 張會紅
（寧波大學電路與系統研究所，浙江寧波 315211）

人口遷移算法是一種新的全局優化搜索算法，主要模擬人口隨著經濟重心發生轉移和隨著壓力增加而擴散的機制，其收斂性和全局尋優能力較強。三值固定極性RM（Fixed-polarity Reed-Muller，FPRM）電路的面積大小與其極性有關。通過對人口遷移算法的研究，提出了一種三值FPRM電路面積優化方案。首先根據三值FPRM表達式和電路面積之間的內在聯系，建立面積優化模型；然后利用人口遷移算法對三值FPRM電路進行面積最佳極性搜索；最后對10個MCNC Benchmark電路進行測試。結果表明：與整體退火遺傳算法相比，本文算法在面積和時間上分別平均節省10.04%和56.59%。

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

search

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

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

1　三值FPRM電路面積估計模型和極性轉換技術

1.1三值FPRM電路面積估計模型

n變量的三值FPRM邏輯函數有3n個固定極性，與之對應的有3n個不同的FPRM表達式。當極性為p時，任意三值FPRM邏輯函數的表達式可表示為［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加運算和多輸入模3乘運算組成，因此可以用兩種邏輯運算的數量來表示三值FPRM電路的面積。多輸入運算的輸入、輸出關系復雜程度不同，在估算面積之前需要把多輸入運算分解成二輸入運算，再以二輸入運算的數量來衡量電路面積。三值FPRM電路的面積即為二輸入模3加運算與二輸入模3乘運算的數量之和。

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

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

1.2三值FPRM極性轉換技術

在電路的面積優化過程中，需要進行極性轉換來檢驗每個極性。常用的三值FPRM極性轉換方法有矩陣轉換法（Matrix Transformation Method）和圖形轉換法（Map Transformation Method）［8-9］。然而這兩種方法的極性轉換速度慢，時間復雜度大。文獻［10］提出了一種三值FPRM極性轉換算法，能有效提高極性轉換速度。其基本過程如下：

（1）極性初始化。隨機產生一個極性p，并用三進制表示p=（p1，p2，…，pn）。

（2）根據pi產生與之相應的固定極性GF轉換矩陣G3〈pi〉，如下所示，pi∈｛p1，p2，…，pn｝。

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

（3）將最小項m表示成三進制序列m=（m1，m2，…，mn），其相應的函數值為f（m）。

（4）根據式（2），產生每個最小項的新項πi。

（5）根據式（3），求出所產生的新項對RM系數所作的貢獻v（π），并在索引表中疊加它的貢獻值。

（6）對所有的最小項重復步驟（3）～（5），最后的累加值即為RM表達式系數。

2　基于PMA的三值FPRM電路面積優化

2.1概述

人口遷移算法是一種全局優化的仿生算法，將目標函數的選擇空間模擬成人類的生存空間，將目標函數值模擬成某個地域的吸引力，利用人口流動、遷移和擴散行為搜索可行解，通過個體的流動、遷移和擴散行為找到局部最優解，最后比較多個局部最優解得到全局最優解。

2.2人口遷移與面積優化的關系

基于人口遷移算法的FPRM電路面積優化要將人口遷移與面積優化兩者聯系起來。人口遷移含有以下幾個關鍵要素：人口所在地、人口所在地的吸引力、吸引力最大地點、最大吸引力、人口可移動地表空間、優惠區域、遷往優惠區域、人口壓力導致遷離優惠

區域。FPRM電路面積優化含有以下幾個關鍵要素：極性、相應極性的面積大小、最佳極性、最小面積、可選擇的極性空間、最佳極性所在區間、極性向最佳極性所在區間跳變、跳出局部最佳極性。表2給出了人口遷移到FPRM面積優化的映射。

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

2.3人口移動

2.3.1概述 人口移動是指人口在地域或空間位置上的移動，包括人口流動、人口遷移和人口擴散。人口流動是人口在各自區域內的移動，是帶有自發性質、移動規律較差的人口行為。人口遷移是人口跨越各自區域在整個生存空間上的移動，是帶有選擇性質、移動規律較強的人口行為。人口擴散是指人口在優惠區域壓力達到某一程度后遷往其他區域的人口行為，在一定程度上可以理解為人口遷移。2.3.2 人口流動 在人口遷移算法中，人口流動表示人口在各自區域內帶有某種自發性質的人口行為，將其運用到三值FPRM電路面積優化中表示在某一極性區間內極性的變動。因為人口流動的規律性較差，因此將人口流動處理為隨機的。為了使區域內每個極性的搜索機會相等，將人口流動處理成均勻隨機變動。模擬時，可以在每個極性區間均勻隨機產生多個極性：

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

其中：Δt表示極性區間的半徑；rand（）為隨機函數；centeri表示第i個極性區間的中心。

2.3.3人口遷移 在人口遷移算法中，人口受吸引力最大地點的吸引，遷往優惠區域。在三值FPRM電路面積優化中可以表示為極性向最佳極性所在區間跳變。模擬時，以面積最小所對應的極性為中心，按Δt的大小確定最佳極性所在區間，在此區間內均勻隨機產生若干個極性，替換原有極性。2.3.4 人口擴散 在人口遷移算法中，當優惠區域的人口壓力達到一定程度后，人口就會向外遷移。在三值FPRM電路面積優化中可以表示為當極性區間收縮到一定程度，即Δt＜q（q表示人口壓力，為預先給定的正小量），極性發生跳躍。模擬時可以簡單化處理，在整個極性空間內均勻隨機產生若干個極性，替換原有極性。

2.4參數設置

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

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

2.5面積優化算法

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

（1）初始化。在極性空間內均勻隨機產生w個極性，并根據Δt確定每個極性所在的區域，初始化最佳極性和面積最優值。

（2）極性變動。在各極性區間內隨機變動每個極性，更新最佳極性和面積最優值，隨機變動l次。

（3）極性轉移。以面積最優值對應的極性為中點，按Δt的大小確定最佳極性區間。在該區域內均勻隨機產生w個極性，替換原來的極性，更新最佳極性和面積最優值。

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

（5）極性跳躍。當收縮最佳極性區域到一定程度（Δt＜q）后，在極性空間內均勻隨機產生w個極性，替換原來的極性，更新最佳極性和面積最優值，重復步驟（2）～步驟（4），直到滿足人口擴散次數s，算法結束。

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

3　實驗驗證與分析

本文算法在Windows 7，64位操作系統，Intel （R）Core（TM）i3-2130 CPU 3.40 GHz，4 G RAM運行環境下，用C語言通過VC6.0編譯實現，采用10個MCNC Benchmark電路進行仿真驗證，優化結果與文獻［11］的整體退火遺傳算法進行比較。在進行最佳極性搜索之前需要讀入PLA格式電路，然而目前只有標準的二值PLA格式電路，因此先用文獻［12］中的方法將標準的二值PLA格式電路轉換為三值PLA格式電路，然后運用本文算法進行最佳極性搜索。

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

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

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

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

面積和時間節省的百分比定義如下：

其中：SaveArea和SaveTime表示面積和算法運行時間的節省；AreaWAGA和TimeWAGA表示整體退火遺傳算法的優化面積和優化時間；AreaPMA和TimePMA表示所提算法的優化面積和優化時間。

分析表4數據可知，本文方法優化效果明顯。與文獻［11］的整體退火遺傳算法相比，10個測試電路面積和時間平均節省10.04%和56.59%。

4　結 論

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

［1］ 汪鵬君，王振海，陳耀武，等.固定極性Reed-Muller電路最佳延時極性搜索［J］.浙江大學學報（工學版），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電路延時和面積優化［J］.電路與系統學報，2012，17（5）：75-80.

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

［6］ 周永華，毛宗源.一種新的全局優化搜索算法——人口遷移算法（Ⅱ）［J］.華南理工大學學報（自然科學版），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，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.

［10］ 孫飛，汪鵬君，俞海珍.三值FPRM電路極性間轉換算法及其在面積優化中的應用［J］.浙江大學學報（理學版），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

國家自然科學基金（61234002，61306041）；浙江省自然科學基金（LY13F040003）

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

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