基于MODPSO算法的FPRM電路多約束極性優化方法

符 強 汪鵬君 童 楠 王銘波 張會紅

?

基于MODPSO算法的FPRM電路多約束極性優化方法

符 強①②汪鵬君*①童 楠②王銘波①張會紅①

①(寧波大學電路與系統研究所 寧波 315211)②(寧波大學科學技術學院 寧波 315212)

為求解較大規模FPRM邏輯電路中多約束條件下的極性優化問題，該文提出一種基于多目標離散粒子群優化(Multi-Objective Discrete Particle Swarm Optimization, MODPSO)算法的求解方法。首先針對FPRM電路極性設計需要滿足延時短、面積小的多約束要求，構建了多目標決策模型。然后結合極性轉換算法和MODPSO算法，對電路進行最優極性搜索，以獲取電路延時和面積的Pareto最優解集。最后利用17個MCNC Benchmark電路進行測試，并將MODPSO算法與DPSO算法、NSGA-II算法進行實驗對比，結果驗證了算法的有效性。

FPRM邏輯電路；延時與面積優化；極性搜索；Pareto；多目標離散粒子群算法

1 引言

電路邏輯函數既可表示為基于AND/OR/NOT運算的Boolean邏輯，也可表示為基于AND/XOR或者XNOR/OR運算的RM(Reed-Muller)邏輯。與Boolean邏輯電路相比，RM邏輯電路具有較好的可測性，并且在實現奇偶校驗、算術邏輯、通信等功能時具有結構與性能上的顯著優勢，因而得到越來越廣泛的關注。

固定極性RM(Fixed Polarity RM, FPRM)是一種常用的RM邏輯規范表達式，其展開式中的變量以原變量或反變量的形式出現。對于個輸入變量的邏輯函數，有個固定極性，對應種FPRM展開式。在FPRM電路中，不同的極性對應不同的邏輯展開式，相應的電路結構及性能也不相同。因此必須在FPRM極性空間中搜索到最優的電路極性，才能獲取最優的電路延時、面積及功耗等性能指標。

FPRM電路的邏輯設計面向多目標的并行優化，需要綜合考慮延時、面積及功耗等各方面性能，從而提升電路的整體性能，因此FPRM電路極性優化問題實質上是一個多約束條件下的綜合優化問題。目前常見的求解方法中，是通過加權函數法將FPRM電路多目標優化問題轉化為單目標問題進行處理，以達到多個性能指標并行優化的目的。如文獻[4]采用固定權系數，利用目標加權的方法提出求解FPRM電路延時和面積優化問題的方法。文獻[5,6]分別采用固定權重及可變權重研究了FPRM電路面積與功耗的綜合優化問題。然而加權函數法存在幾個問題：(1)對權重系數敏感，不同的權重設置對結果影響較為明顯。(2)權重選擇嚴重依賴先驗知識，較難接近真實的需求折中。(3)難于獲取全部的Pareto最優解。往往只能獲取一個或者少數最優解，弱化了優化結果的決策支持能力。因此需要更為有效的方法來實現FPRM電路邏輯設計中的多目標綜合優化要求。

多目標智能算法近些年發展較快，并在求解多目標優化問題中得到有效應用。此類方法避免了權重設置，利用Pareto準則確定當前解的非支配關系，從中選擇最優個體，引導其余個體進行目標尋優，并通過迭代優化確定適應多個目標函數的最優解集。其中多目標粒子群算法[12]與其他同類算法相比，具有結構簡單，易于實現，收斂速度快，強魯棒性等優點。

延時與面積均為RM邏輯電路設計過程中的關鍵因素，對電路綜合性能起著重要作用。本文針對FPRM電路極性設計中同時考慮延時與面積約束條件的綜合優化問題，提出一種基于Pareto優化準則的多目標離散粒子群算法(MODPSO)，算法中的粒子代表決定FPRM電路延時與面積的電路極性。利用列表技術進行極性轉換，然后通過MODPSO算法搜索電路的Pareto最優極性解集，實現電路延時與面積優化設計。最后將對較大規模MCNC Benchmark電路進行測試以驗證算法有效性。

2 FPRM電路延時與面積優化模型

2.1 極性轉換

(2)

列表轉換技術[13]是一種易于編程實現的快速極性轉換算法，適用于含任意變量數的邏輯函數，常被用于FPRM展開式的極性轉換。實現從極性轉換到極性的列表轉換技術算法描述如表1所示。

表1 從極性轉換到極性的列表轉換技術

BEGIN:初始化，定義集合M, N，并將極性和分別記為 和；將極性下與項序數代表與項，記為 ，并將放入集合M中；FOR TO 0 IF THEN與項生成新與項 ，并存于集合N中；依次將集合N中所有新與項與極性中的與項進行比較，IF 新與項和極性中的與項相同 THEN 在集合M中刪除與該新與項相同的對應與項；ELSE 將該新與項添加到集合M中；END

2.2 延時與面積估算模型

在進行電路延時與面積估算之前，先通過代數法化簡FPRM表達式，以簡化電路結構，利于模型估算優化。代數化簡式可描述為

表2 FPRM電路化簡算法

在電路邏輯級設計中一般采用單位延時模型估計電路延時。將電路的每個多輸入門分解成二輸入AND門或XOR門組合，并將二輸入門的傳輸延時大小定義為一個單位時間，則可利用二輸入門總數表示電路的面積。而二輸入門在關鍵路徑的傳輸延時之和表示電路延時。二輸入門的輸出延遲可表示為[15]

對于化簡后的FPRM電路，通過比較多輸入門的不同分解方式以找到最短的關鍵路徑延時。設為一個FPRM展開式，為第個向量的子展開式，為邏輯分解后的終端節點向量個數。令原始輸入信號的延時為0，則FPRM電路的延遲分解算法可以描述如表3所示。

表3 FPRM電路的延時分解算法

化簡及分解后的電路網絡表示為(),為二輸入門集合。將中的二輸入AND門總數記為，二輸入XOR門總數記為；并將其中關鍵路徑上的二輸入門總數記為。則FPRM電路的延時與面積估算模型可表示為

(5)

(6)

3 多目標離散粒子群優化(MODPSO)

粒子群算法[16]借鑒了鳥群覓食機制，結合粒子自身認知與最優群體提供的社會信息來促進粒子間的信息交流與合作，能迅速定位并捕捉目標。

為利用粒子群算法搜索電路最優極性，對算法進行了離散化，設計了粒子編碼方案、粒子更新機制，并構建了實現電路延時與面積綜合優化的MODPSO方法，以獲取Pareto最優極性解集。

3.1 多目標決策函數

對FPRM電路而言，電路延時長短與面積大小均由電路極性決定。選擇合適的電路極性，才能獲取延時與面積的綜合優化效果。加權函數法為電路延時與面積模型進行權重設定，利用單目標求解方法尋找最優極性。但是面向不同的用戶需求，單一的權重設置較難滿足電路設計的多樣性要求。同時，面積與延時不一定表現出相同的變化趨勢：面積最小的極性下電路的延時有可能較長，而延時最短的極性下電路的面積可能較大。因此選用Pareto優化準則作為粒子群體的進化依據，得出多目標決策函數為

3.2 粒子編碼與更新

在求解FPRM電路延時和面積優化問題時，MODPSO中的搜索空間維度對應于 FPRM電路的變量數。粒子位置對應于電路的極性，最優粒子位置則表示FPRM電路優化搜索中的最優極性。

假設粒子種群中的粒子總數為Population，搜索空間為維，隨機初始化每一個粒子的位置和速度。記第個粒子的位置為,；其飛行速度為。個體最優位置為；粒子種群最優位置為。由于在離散空間進行最優電路極性搜索，因此需要將算法進行離散化處理。可得粒子速度與位置更新式為

(10)

設置外部存儲的最優檔案庫以保存當前進化代數中得到的Pareto 最優解，并在下一代進化時從中選擇帶領粒子種群尋優。為保證粒子的多樣性要求，最優檔案庫的粒子按照擁擠程度排序，并利用輪盤賭方式進行全局最優粒子選擇。

預先設定最優檔案庫規模大小，當其中數量較少時，可將新求得的最優粒子直接放入最優檔案庫中；而當最優檔案庫中的粒子個數達到或超出預定規模要求時，則需要分析新最優粒子與最優檔案庫中原有粒子的支配關系，留下其中更優的部分。

為保證粒子的可控性，對粒子進行速度約束，如式(11)所示。

3.3 Pareto最優極性解集搜索

綜合以上對FPRM延時與面積估算模型、列表轉換技術，以及MODPSO算法設計的分析，提出面向FPRM電路延時與面積綜合優化問題的Pareto最優極性解集搜索方案如表4所示。

4 實驗與分析

本文實驗均在Windows XP操作系統下，通過VC6.0編譯。程序的硬件環境為Inter Pentium CPU G645(2.9 GHz) 1.82 GB RAM。測試電路隨機取用17個PLA格式的MCNC Benchmark電路。

首先將MODPSO算法與利用加權函數法的DPSO算法[4]進行了實驗對比，兩種算法各運行20次。參數設置為：粒子總數Population=40，迭代進化次數Iteration=120。加速因子==2；慣性權重=0.4,=0.9;=4, DPSO算法中的優化權重值為0.5。

表5給出了兩種算法各自運行Benchmark電路獲取的電路延時與面積。其中，“名稱”為測試電路的名稱，“最好”、“最差”分別為MODPSO算法和DPSO算法20次運行所得最好值與最差值，“Del_A”和“Del_D”分別為MODPSO算法和DPSO算法20次運行結果的面積方差與延時方差。

表4 FPRM電路延時與面積綜合優化問題的Pareto最優極性解集搜索方案

從表5數據可以看出，當電路中的延時與面積具有相同變化趨勢，Pareto最優解集中只有唯一解時，DPSO有機會求取滿足最優延時與面積的極性結構，但由于文獻中的DPSO算法將延時與面積權重均固定為0.5，并不適合每個具有不同特征的電路，在電路 in5, s444, x9dn測試中所求得最優解精度不如MODPSO算法，并在大部分電路測試中表現出較大波動性，最差解質量明顯劣于MODPSO算法。MODPSO算法不需要進行權重設置，且針對各種類型的電路均能獲得較好結果。同時其20次運行結果的方差小，具有較強的魯棒性。尤其對于電路a12，由于該電路延時與面積具有不同的變化趨勢，Pareto最優解集中的非劣解不唯一，DPSO算法無法求得全部Pareto最優解，而MODPSO算法能夠穩健獲得Pareto最優解集。

為進一步驗證MODPSO算法在求解FPRM電路延時和面積問題的有效性和可靠性，將算法與NSGA-II算法[10]進行實驗比對。針對每個測試電路，MODPSO算法與NSGA-II算法分別實驗20次，結果如表6所示。其中“次數”表示在20次測試中，獲得最優解的總次數；“時間(s)”為20次測試所花費的總時間。

表5 MODPSO與DPSO算法最優極性對應的延時與面積

表6 MODPSO與NSGA-II算法最優極性對應的延時與面積

從表6中可以看出，在每個測試電路的實驗結果中，NSGA-II算法均有機會獲取最優解，但在20次實驗結果中表現出較大差異性：17個電路測試中求得最優解的平均概率僅為49.68%，且對于a12電路，有9次測試未能獲得Pareto最優解集；而MODPSO算法相比NSGA-II算法具有明顯更優的求解性能，在15個電路測試中均能20次全部獲取最優解，且在17個電路測試中求得最優解的平均概率達到99.4%，表現出良好的算法魯棒能力。

在時間花費上，NSGA-II算法在全部電路測試上花費的總時間為7366.86 s；而MODPSO算法花費的總時間為1987.76 s，僅為前者的26.98%。

就整體測試結果而言，MODPSO算法相比NSGA-II算法，17個測試電路的延時優化率平均值為13.22%，面積優化率平均值為2.51%。延時優化率及面積優化率可描述為

延時優化率=(OD1-OD2)/OD2 (12)

面積優化率=(OA1-OA2)/OA2 (13)

其中OD1, OD2分別為NSGA-II算法、MODPSO算法20次優化結果獲取的延時平均值， OA1, OA2分別為NSGA-II算法、MODPSO算法20次優化結果獲取的面積平均值。

將17個測試電路的20次優化結果之和作為最終測試結果，分析兩種算法的面積與延時迭代進化過程，如圖1，圖2所示。

從圖1，圖2中可以看出， NSGA-II算法進化速度慢，而且較早陷入早熟收斂；而MODPSO算法在進化早期就表現更優的搜索效率，具有更強的全局搜索能力。

5 結束語

針對FPRM電路極性設計中的多目標優化問題，本文提出了一種基于MODPSO算法的極性搜索方法，利用Pareto優化準則進行多目標條件下的粒子優劣性評價，以獲取延時和面積綜合優化的電路最優極性解集。對17個PLA格式的MCNC Benchmark電路進行了測試，實驗結果表明，MODPSO算法避免了加權函數法對權重設置的主觀性，能獲取更加準確、完整的Pareto最優解，提高了電路輔助設計能力。而與加權函數法及NSGA- II算法相比，MODPSO算法在求解精度、速度及魯棒性等方面均具有更好的優化效率。

圖1 電路數據集面積進化曲線

圖2 電路數據集延時進化曲線

[1] MONREIRO C, TAKAHASHI Y, and SEKINE T. Low- power secure S-box circuit using charge-sharing symmetric adiabatic logic for advanced encryption standard hardware design[J].,&, 2015, 9(5): 362-369.

[2] 王倫耀, 夏銀水, 陳偕雄. 邏輯函數的雙邏輯綜合與優化[J]. 計算機輔助設計與圖形學學報, 2012, 24(7): 961-967.

WANG Lunyao, XIA Yinshui, and CHEN Xiexiong. Logic synthesis and optimization based on dual logic[J].-&, 2012, 24(7): 961-967.

[3] 卜登立, 江建慧. 基于混合多值離散粒子群優化的混合極性 Reed-Muller 最小化算法[J]. 電子與信息學報, 2013, 35(2): 361-367.doi: 10.3724/SP.J.1146.2012.00790.

BU Dengli and JIANG Jianhui. Hybrid multi-valued discrete particle Swarm optimization algorithm for mixed-polarity Reed-Muller minimization[J].&, 2013, 35(2): 361-367. doi: 10.3724/ SP.J.1146.2012.00790.

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

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

[5] WANG Pengjun, LI Kangping, and ZHANG Huihong. PMGA and its application in area and power optimization for ternary FPRM circuit[J]., 2016, 37(1): 015007.

[6] DAS A and PRADHAN S N. Thermal aware FPRM based AND-XOR network synthesis of logic circuits[C]. IEEE 2nd International Conference on Recent Trends in Information System(ReTIS). IEEE, Kolkata, India, 2015: 497-502. doi: 10.1109/ReTIS.2015.7232930.

[7] 姜興龍, 梁廣, 劉會杰, 等. 一種新型的低軌存儲轉發通信星座設計方法[J]. 電子與信息學報, 2014, 36(3): 676-682.doi: 10.3724/SP.J.1146.2013.00551.

JIANG Xinglong, LIANG Guang, LIU Huijie,. A new design method of store and forward LEO communication satellite constellation[J].&, 2014, 36(3): 676-682. doi: 10.3724/ SP.J.1146.2013.00551.

[8] ESFAHANI I J, YOO C K, KALOGIROU SOTERIS A,. An optimization algorithm-based pinch analysis and GA for an off-grid batteryless photovoltaic-powered reverse osmosis desalination system[J]., 2016, 91: 233-248.

[9] SRIVASTAV A and AGRAWAL S. Multi-objective optimization of hybrid backorder inventory model[J]., 2016, 51: 76-84.

[10] MARTINEZ-VARGAS A, DOMINGUEZ-GUERRERO J, ANDRADE á G,. Application of NSGA-II algorithm to the spectrum assignment problem in spectrum sharing networks[J]., 2016, 39: 188-198.

[11] YUAN Y, XU H, WANG B,. A new dominance relation-based evolutionary algorithm for many-objective optimization[J]., 2016, 20(1): 16-37.

[12] HOAI BACH NGUYEN, XUE Bing, LIU Lü,. New mechanism for archive maintenance in PSO-based multi- objective feature selection[J]., 2016: 1-20. doi: 10.1007/s00500-016-2128-8.

[13] JASSANI B A Al, URQUHART N, and ALMAINI A E A. Manipulation and optimization techniques for Boolean logic[J]., 2010, 4(3): 227-239.

[14] 汪鵬君, 王振海, 陳耀武, 等. 固定極性Reed-Muller電路最優延時極性搜索[J]. 浙江大學學報: 工學版, 2013, 47(2): 361-366.doi: 10.3785/j.issn.1008-973X.2013.02.026.

WANG Pengjun, WANG Zhenhai, CHEN Yaowu,. Searching the best polarity for fixed polarity Reed-Muller circuits based on delay model[J].(), 2013, 47(2): 361-366. doi: 10.3785/j.issn.1008-973X. 2013.02.026.

[15] CORTADELLA J. Timing-driven logic bi-decomposition[J].-, 2003, 22(6): 675-685.

[16] AMINBAKHSH S and SONMEZ R. Discrete particle swarm optimization method for the large-scale discrete time–cost trade-off problem[J]., 2016, 51: 177-185.

Multi-constrained Polarity Optimization of Large-scale FPRM Circuits Based on Multi-objective Discrete Particle Swarm Optimization

FU Qiang①②WANG Pengjun①TONG Nan②WANG Mingbo①ZHANG Huihong①

①(,,315211,)②(,,315212,)

For multi-constrained polarity optimization of large-scale FPRM circuits, a Multi-Objective Discrete Particle Swarm Optimization (MODPSO) algorithm is proposed. Firstly, the multi-objective decision model is established according to the delay-area trade-off of large-scale FPRM circuits. Secondly, combined with tabular technique and MODPSO, the best polarities of delay and area are searched for large-scale FPRM circuits, to obtain the Pareto optimal set for delay and area. Finally, the algorithm MODPSO is compared with the algorithm DPSO and NSGA-II on MCNC Benchmarks with PLA format, and the results verify the effectiveness of the MODPSO.

FPRM circuits; Delay-area trade-off; Polarity search; Pareto; Multi-Objective Discrete Particle Swarm Optimization (MODPSO)

TN79+1; TP391.72

A

1009-5896(2017)03-0717-07

10.11999/JEIT160458

2016-05-05；改回日期：2016-10-18；

2016-12-20

汪鵬君 wangpengjun@nbu.edu.cn

國家自然科學基金(61306041, 61234002)，“十二五”浙江省高校重點學科—計算機應用技術，浙江省教育廳科研項目(Y201326770)，寧波市自然科學基金(2014A610069，2015A610107)

The National Natural Science Foundation of China (61306041, 61234002), The Twelfth Five-Year Plan of Zhejiang Province Key Discipline (Computer Application Technology), The Scientific Research Fund of Zhejiang Provincial Education Department (Y201326770), The Ningbo Natural Science Foundation (2014A610069, 2015A610107)

符 強： 男，1975年生，講師，博士生，研究方向為低功耗集成電路理論及優化設計.

汪鵬君： 男，1966年生，博士，教授，博士生導師，研究方向為多值邏輯和低功耗集成電路理論及優化設計.

童 楠： 女，1981年生，講師，碩士，研究方向為多目標智能優化方法.

王銘波： 男，1994年生，碩士生，研究方向為低功耗集成電路理論及優化設計.