基于全離散粒子群優(yōu)化的納電子MPRM電路面積優(yōu)化算法

摘 要： 針對具有較多輸入數(shù)的可編程陣列結(jié)構(gòu)納電子混合極性Reed?Muller電路的面積優(yōu)化問題，提出一種全離散粒子群優(yōu)化算法。通過將粒子速度合并到位置更新方程，充分挖掘粒子群優(yōu)化中的學(xué)習(xí)因素得到全離散化的粒子更新方程，在此基礎(chǔ)之上設(shè)計FDPSO算法，并使用探索概率作為算法參數(shù)控制算法全局探索與局部開拓間的平衡。對一組輸入數(shù)大于20的MCNC電路進行優(yōu)化的實驗結(jié)果表明，與其他能夠用于可編程陣列結(jié)構(gòu)納電子混合極性Reed?Muller電路面積優(yōu)化的智能算法相比，全離散粒子群優(yōu)化算法具有較強的全局收斂能力和結(jié)果穩(wěn)定性，能夠以較高時間效率獲得較好的優(yōu)化結(jié)果。

關(guān)鍵詞： 納電子； MPRM電路； 面積優(yōu)化； 粒子群優(yōu)化； 更新方程； 算法參數(shù)

中圖分類號： TN431.2?34； TP391.72 文獻(xiàn)標(biāo)識碼： A 文章編號： 1004?373X（2018）04?0078?05

Abstract： In allusion to the area optimization problem of programmable array?structured nanoelectronic mixed?polarity Reed?Muller （MPRM） circuit with many input numbers， a fully discretized particle swarm optimization （FDPSO） algorithm is proposed. The learning factors in particle swarm optimization are fully mined by integrating particle velocity into the location update equation to obtain the fully discretized particle update equation. On this basis， FDPSO algorithm is designed and the exploration probability is used as the algorithm parameter to control the balance between global exploration and local exploitation of the algorithm. The optimization experiment for microelectronics center of North Carolina （MCNC） circuit whose input numbers are larger than 20 was carried out. The results show that， in comparison with other intelligent algorithms that can be applied to area optimization of programmable array?structured nanoelectronic MPRM circuit， FDPSO algorithm has stronger global convergence capability and result stability， and can achieve better optimization results with higher time efficiency.

Keywords： nanoelectronic； MPRM circuit； area optimization； particle swarm optimization； update equation； algorithm parameter

0 引 言

混合極性Reed?Muller（Mixed?Polarity RM，MPRM）邏輯是乘積項的異或和表示[1]，因其邏輯表示的緊湊性及其電路實現(xiàn)的良好可測試性[2]，在算術(shù)電路、通信電路以及校驗電路中得到了廣泛應(yīng)用[1]。這些電路是計算機和通信系統(tǒng)中的關(guān)鍵電路，緊湊的邏輯表示有助于降低電路的面積和功耗，良好的可測試有助于提高系統(tǒng)的可靠性。

當(dāng)器件尺寸進入納米規(guī)模，基于納電子器件的可編程陣列結(jié)構(gòu)被認(rèn)為是一種很有前景的納電子電路結(jié)構(gòu)[3]，這種電路結(jié)構(gòu)也非常宜于用來映射MPRM邏輯從而構(gòu)建納電子MPRM電路。納電子MPRM電路面積優(yōu)化問題屬于組合優(yōu)化問題[4]，因其存在指數(shù)級的解空間，為在較為合理的時間內(nèi)得到較好的優(yōu)化結(jié)果，常采用智能優(yōu)化方法來解決。遺傳算法（Genetic Algorithm，GA）因其基因編碼的離散特性，非常宜于用來解決納電子MPRM電路面積優(yōu)化問題[5]。盡管粒子群優(yōu)化（Particle Swarm Optimization，PSO）是作為一種用于實值空間優(yōu)化的技術(shù)被Eberhart R和Kennedy J提出[6]，但近幾年來已有一些文獻(xiàn)提出了可用于納電子MPRM電路面積優(yōu)化的離散粒子群優(yōu)化（Discrete PSO， DPSO）算法以及改進DPSO算法，如文獻(xiàn)[4]的HDPSO（Hybrid multi?valued DPSO）算法，文獻(xiàn)[7]的DTPSO（Discrete Ternary PSO）算法，文獻(xiàn)[8]中將GA與文獻(xiàn)[7]DTPSO算法相結(jié)合的GA?DTPSO算法，文獻(xiàn)[9]中的SADPSO算法（Simulated Annealing DPSO，SADPSO）。但這些算法要么結(jié)果質(zhì)量較差，要么僅適用于輸入數(shù)小于20的電路。

受文獻(xiàn)[10]和差分進化算法[11]的啟發(fā)，本文提出基于全離散PSO（Fully Discretized PSO，F(xiàn)DPSO）的納電子MPRM電路面積優(yōu)化算法。該算法僅建立在粒子位置更新方程之上，采用概率變異更新策略[4]維持粒子多樣性，并使用探索概率參數(shù)來平衡算法的全局探索和局部開拓。使用一組輸入數(shù)大于20的MCNC（Microelectronics Center of North Carolina）電路對算法進行了驗證，并與其他可用于納電子MPRM電路面積優(yōu)化的智能優(yōu)化算法進行了比較。endprint

1 納電子MPRM電路及面積優(yōu)化問題

本文采用基于納電子器件的可編程陣列結(jié)構(gòu)實現(xiàn)MPRM邏輯，[n-]輸入/[m-]輸出的納電子MPRM電路結(jié)構(gòu)如圖1所示。

圖1中行線與列線交叉位置處的“NC”為可編程納電子單元，有2個輸入和1個輸出，如編號為①的NC所示，其Y表示輸出，A和B表示輸入，可以采用文獻(xiàn)[3]中的Nanocell或者文獻(xiàn)[12]中的可編程邏輯門單元。圖1中的每一行對應(yīng)MPRM邏輯中一個乘積項[πi]（[πi]行線，[0≤i≤u-1]），位于虛線左側(cè)的部分稱為“AND平面”，其中的列線為[xl]和[xl]（[0≤l≤n-1]），共有[2n]列，如果變量[xl]在[πi]中以原變量形式出現(xiàn)，則[xl]列線與[πi]行線交叉位置的“NC”被編程為與門，并完成如圖1中編號為①的可編程單元所示的連接，如果變量[xl]在[πi]中以補變量形式出現(xiàn)，則[xl]列線與[πi]行線交叉位置的“NC”被編程為與門，并完成如圖1中編號為②的可編程單元所示的連接，從而實現(xiàn)乘積項[πi]；位于虛線右側(cè)的部分稱為“XOR平面”，其中的列線輸出函數(shù)[fk]，共有[m]列，如果乘積項[πi]屬于[fk]，則[fk]列線與[πi]行線交叉位置的“NC”被編程為異或門，并完成如圖1中編號為③和④的可編程單元所示的連接，從而實現(xiàn)乘積項間的異或運算。

2 納電子MPRM電路面積優(yōu)化算法

2.1 編碼和適應(yīng)度函數(shù)

將MPRM邏輯的極性向量[1]作為粒子的位置向量[Dj=[dj，n-1，…，dj，0]]，[dj，l]表示粒子群中索引為[j]的粒子在[n]維搜索空間中第[l]維的位置。

所采用的適應(yīng)度函數(shù)為式（1）中的[C（h）]，首先根據(jù)極性向量使用文獻(xiàn)[5]中的極性轉(zhuǎn)換方法對MPRM邏輯進行極性轉(zhuǎn)換，然后再計算其對應(yīng)納電子MPRM電路的面積[C（h）]。

2.2 FDPSO算法模型

式中：[?]表示下取整；[N]為粒子群規(guī)模。

由式（2）和式（3）可以看出，粒子在搜索空間中的移動受到Pbest，Gbest以及Mbest的影響。將Mbest作為合力引導(dǎo)粒子的搜索，可以增強粒子的學(xué)習(xí)能力，在一定程度上避免由于Gbest的過度吸引導(dǎo)致群搜索陷入局部極小。為了避免群搜索過于發(fā)散而引起群搜索爆炸問題，引入[W]因子，使粒子以一定概率受Mbest的吸引。較大的[W]因子意味著粒子以較高概率受Mbest的引導(dǎo)，可以使粒子群搜索更大的區(qū)域，增強全局探索能力，較小的[W]因子則意味著粒子以較小概率受Mbest的引導(dǎo)，可使群搜索進行局部開拓，避免發(fā)散，促使算法的收斂。

由于群搜索前期階段側(cè)重于全局探索，后期階段側(cè)重于局部開拓，因此可以使用隨迭代次數(shù)線性遞減的[W]因子來實現(xiàn)全局探索與局部開拓之間的平衡。假設(shè)[Wb∈0，1]和[We∈0，1]分別表示[W]因子的初值和終值，[tm]表示最大迭代次數(shù)，則第[t]次迭代時[W]因子的取值由式（4）計算。

2.3 納電子MPRM電路面積優(yōu)化算法

根據(jù)前述的編碼和適應(yīng)度函數(shù)以及FDPSO算法模型，設(shè)計基于FDPSO的納電子MPRM面積優(yōu)化算法，下面給出其算法描述：

1） 讀取電路邏輯網(wǎng)表；

2） 算法參數(shù)初始化，包括最大迭代次數(shù)[tm]、粒子群規(guī)模[N]，[W]因子：[Wb]和[We]；

3） 迭代次數(shù)變量[t=0]，Gbest沒有改變累計計數(shù)變量[v=0]；

4） 初始化粒子群，計算粒子適應(yīng)度值，更新每個粒子的Pbest以及群最佳Gbest，并記錄Gbest的適應(yīng)度[C0]；

5） 使用式（4）計算當(dāng)前的[W]因子，使用式（3）計算群體平均最佳Mbest；

6） 對群中每個粒子位置向量的每一維位置：生成隨機數(shù)[r0∈0，1]和[pmt∈0.01，0.05]以及[r1∈0，1]，使用式（2）更新該位置；

7） 計算群中粒子適應(yīng)度值，更新每個粒子的Pbest以及群最佳Gbest，并記錄Gbest的適應(yīng)度[C1]；

8） 如果[C1

9） [t=t+1]，如果[t≥tm]或者[v==20×lnn，]則轉(zhuǎn)至步驟10），否則轉(zhuǎn)至步驟5）；

10） 輸出最優(yōu)納電子MPRM電路，算法結(jié)束。

算法步驟9）中的結(jié)束條件除了達(dá)到最大迭代次數(shù)結(jié)束之外，還采取了文獻(xiàn)[4]中的結(jié)束條件，如果在達(dá)到最大迭代次數(shù)之前FDPSO的尋優(yōu)結(jié)果沒有改變所累計次數(shù)達(dá)到[20×lnn]則結(jié)束算法，算法的步驟8）統(tǒng)計尋優(yōu)結(jié)果沒有改變所累計的次數(shù)。

3 實驗結(jié)果與分析

將本文的FDPSO算法與文獻(xiàn)[8]中的GA?DTPSO算法、文獻(xiàn)[9]中的SADPSO算法以及文獻(xiàn)[5]中的HGA算法進行比較。四種算法均采用文獻(xiàn)[5]中的MPRM邏輯極性轉(zhuǎn)換方法，以及如式（1）所示的成本函數(shù)和優(yōu)化目標(biāo)，并用C++實現(xiàn)，在Linux下使用g++編譯器編譯。使用四種算法分別對一組輸入數(shù)大于20的MCNC電路在配置為Intel Core i3?2350M CPU 6 GB RAM的個人計算機上進行納電子MPRM電路面積優(yōu)化。

3.1 實驗設(shè)置

FDPSO算法的參數(shù)設(shè)置為[tm=180]，[N=30]，[Wb=0.7]，[We=0.2，]這些參數(shù)值通過基準(zhǔn)電路的初步實驗確定。SADPSO算法的參數(shù)設(shè)置與文獻(xiàn)[9]相同，HGA算法的參數(shù)設(shè)置與文獻(xiàn)[5]相同。

由于FDPSO，SADPSO和HGA算法的群規(guī)模均為30，最大迭代次數(shù)均為180，因此GA?DTPSO算法的種群規(guī)模也設(shè)為30，最大迭代次數(shù)也設(shè)為180，其他參數(shù)設(shè)置則與文獻(xiàn)[8]相同。另外，SADPSO，HGA和GA?DTPSO算法也都采用了與FDPSO算法相同的結(jié)束條件。由于四種算法均具有一定的隨機性，因此在實驗中對于每個基準(zhǔn)電路，每種算法均獨立運行20次，并統(tǒng)計算法結(jié)果電路面積的平均值以及所花費CPU時間的平均值。

3.2 結(jié)果分析

表1給出四種算法的運行結(jié)果，其中“I/O”表示電路的輸入數(shù)和輸出數(shù)，面積和時間分別為算法20次獨立運行所得到最優(yōu)MPRM電路結(jié)果的面積平均值以及所花費CPU時間的平均值，時間的單位為s。從表1所示的面積“平均”結(jié)果來看，F(xiàn)DPSO算法要優(yōu)于GA?DTPSO算法，對于這15個電路，相比GA?DTPSO算法，F(xiàn)DPSO算法使電路面積減少了12.56%，F(xiàn)DPSO算法所得結(jié)果與SADPSO算法和HGA算法相差不大。從時間“平均”角度看， FPDSO算法分別比GA?DTPSO算法和SADPSO算法降低了22.17%和172.54%的時間開銷，F(xiàn)DPSO算法的時間效率要明顯優(yōu)于SADPSO算法和GA?DTPSO算法，F(xiàn)DPSO算法和HGA算法的時間效率相差不大，僅比HGA算法增加了3.39%的時間開銷。

盡管從表1中面積的“平均”結(jié)果來看，F(xiàn)DPSO算法與HGA算法相差不大，但是對表1中的15個電路而言，除cc，in7和lal外，其余電路FDPSO算法的結(jié)果均比HGA算法的結(jié)果要好一些，特別是電路ts10，F(xiàn)DPSO算法能夠搜索到全局面積最優(yōu)的電路（20次運行均獲得面積為128的電路結(jié)果），而HGA算法卻無法搜索到全局面積最優(yōu)電路（20次運行均獲得面積為136的電路結(jié)果），相對于HGA算法，F(xiàn)DPSO算法將ts10的電路面積降低了5.88%。為對FDPSO和HGA做進一步比較，圖2給出了HGA算法和FDPSO算法結(jié)果的變異系數(shù)（變異系數(shù)等于標(biāo)準(zhǔn)差除以均值）[4]，可以通過變異系數(shù)來評價算法的尋優(yōu)能力（全局收斂能力）和算法結(jié)果的穩(wěn)定性，變異系數(shù)越小則表示算法的尋優(yōu)能力和結(jié)果穩(wěn)定性越好。

由圖2可以看出，在15個電路中，HGA算法結(jié)果的變異系數(shù)為0的電路僅有3個，而FDPSO算法卻有8個，是HGA算法的2.67倍，并且對于絕大多數(shù)電路而言，F(xiàn)DPSO算法結(jié)果的變異系數(shù)要小于HGA算法。從15個電路結(jié)果變異系數(shù)的平均值來看，相對于HGA算法，F(xiàn)DPSO算法將變異系數(shù)降低了75.76%?？梢?，盡管從“面積”平均結(jié)果來看，F(xiàn)DPSO算法與HGA算法基本相同，但FDPSO算法的尋優(yōu)能力明顯優(yōu)于HGA算法，F(xiàn)DPSO算法具有更強的全局收斂能力和結(jié)果穩(wěn)定性。

綜上所述，F(xiàn)DPSO算法能夠獲得比GA?DTPSO算法更好的優(yōu)化結(jié)果。在獲得基本相同面積平均結(jié)果的情況下，F(xiàn)DPSO算法比SADPSO算法具有更高的時間效率，F(xiàn)DPSO算法比HGA算法具有更好的全局收斂能力和結(jié)果穩(wěn)定性。可見，F(xiàn)DPSO算法能夠很好地解決具有較多輸入數(shù)的納電子MPRM電路的面積優(yōu)化問題。

4 結(jié) 語

本文針對基于納電子器件可編程陣列構(gòu)建的納電子MPRM電路，提出了基于FDPSO的納電子MPRM電路面積優(yōu)化算法，該算法模型建立在全離散化的粒子更新方程之上，并且僅需設(shè)置4個算法參數(shù)，算法結(jié)構(gòu)簡單，易用性較強。對一組輸入數(shù)大于20的電路進行納電子MPRM電路面積優(yōu)化的實驗結(jié)果表明，從總體角度來看，與其他可用于納電子MPRM電路面積優(yōu)化的智能優(yōu)化算法相比，F(xiàn)DPSO算法具有更強的全局收斂能力和結(jié)果穩(wěn)定性，能夠得到較好的優(yōu)化結(jié)果，并且具有較高的時間效率，能夠很好地解決具有較多輸入數(shù)的納電子MPRM電路的面積優(yōu)化問題。

參考文獻(xiàn)

[1] 卜登立，江建慧.使用系數(shù)矩陣變換極性轉(zhuǎn)換的MPRM電路面積優(yōu)化[J].計算機輔助設(shè)計與圖形學(xué)學(xué)報，2013，25（1）：126?135.

BU Dengli， JIANG Jianhui. Area optimization of MPRM circuits utilizing coefficient matrix transformation based polarity conversion [J]. Journal of computer?aided design & computer graphics， 2013， 25（1）： 126?135.

[2] DRECHSLER R， HENGSTER H， SCHAFER H， et al. Testability of 2?level AND/EXOR circuits [J]. Journal of electronic testing： theory and applications， 1999， 14（3）： 219?225.

[3] HASELMAN M， HAUCK S. The future of integrated circuits： a survey of nanoelectronics [J]. Proceedings of the IEEE， 2010， 98（1）： 11?38.

[4] 卜登立，江建慧.基于混合多值離散粒子群優(yōu)化的混合極性Reed?Muller最小化算法[J].電子與信息學(xué)報，2013，35（2）：361?367.

BU Dengli， JIANG Jianhui. Hybrid multi?valued discrete particle swarm optimization algorithm for mixed?polarity Reed?Muller minimization [J]. Journal of electronics & information technology， 2013， 35（2）： 361?367.

[5] 卜登立.基于混合遺傳算法的MPRM最小化[J].浙江大學(xué)學(xué)報（理學(xué)版），2016，43（2）：184?189.

BU Dengli. Hybrid genetic algorithm for MPRM minimization [J]. Journal of Zhejiang University （Science edition）， 2016， 43（2）： 184?189.endprint

[6] EBERHART R， KENNEDY J. A new optimizer using particle swarm theory [C]// Proceedings of the 6th International Symposium Micro Machine and Human Science. Nagoya： IEEE， 1995： 39?43.

[7] YU H Z， WANG P J， WANG D S， et al. Discrete ternary particle swarm optimization for area optimization of MPRM circuits [J]. Journal of semiconductors， 2013， 34（2）： 118?123.

[8] 俞海珍，蔣志迪，汪鵬君，等.GA?DTPSO算法及其在混合極性XNOR/OR電路面積優(yōu)化中的應(yīng)用[J].計算機輔助設(shè)計與圖形學(xué)學(xué)報，2015，27（5）：946?952.

YU H Z， JIANG Z D， WANG P J， et al. GA?DTPSO algorithm and its application in area optimization of mixed polarity XNOR/OR circuits [J]. Journal of computer?aided design & computer graphics， 2015， 27（5）： 946?952.

[9] 卜登立.基于SADPSO的MPRM最小化算法[J].重慶郵電大學(xué)學(xué)報（自然科學(xué)版），2016，28（2）：226?232.

BU Dengli. MPRM minimization algorithm based on SADPSO [J]. Journal of Chongqing University of Posts and Telecommunications （Natural science edition）， 2016， 28（2）： 226?232.

[10] GAO H， XU W. A new particle swarm algorithm and its globally convergent modifications [J]. IEEE transactions on systems， man， and cybernetics， 2011， 41（5）： 1334?1351.

[11] DAS S， SUGANTHAN P N. Differential evolution： a survey of the state?of?the?art [J]. IEEE transactions on evolutionary computation， 2011， 15（1）： 4?31.

[12] O′CONNOR I， LIU J， NAVARRO D， et al. Dynamically reconfigurable logic gate cells and matrices using CNTFETs [C]// Proceedings of the 3rd International Conference on Design and Technology of Integrated Systems in Nanoscale Era. Tunisia： IEEE， 2008： 1?6.endprint