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

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

中圖分類號(hào)： TN431.2?34； TP391.72 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)： 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）邏輯是乘積項(xiàng)的異或和表示[1]，因其邏輯表示的緊湊性及其電路實(shí)現(xiàn)的良好可測(cè)試性[2]，在算術(shù)電路、通信電路以及校驗(yàn)電路中得到了廣泛應(yīng)用[1]。這些電路是計(jì)算機(jī)和通信系統(tǒng)中的關(guān)鍵電路，緊湊的邏輯表示有助于降低電路的面積和功耗，良好的可測(cè)試有助于提高系統(tǒng)的可靠性。

當(dāng)器件尺寸進(jìn)入納米規(guī)模，基于納電子器件的可編程陣列結(jié)構(gòu)被認(rèn)為是一種很有前景的納電子電路結(jié)構(gòu)[3]，這種電路結(jié)構(gòu)也非常宜于用來映射MPRM邏輯從而構(gòu)建納電子MPRM電路。納電子MPRM電路面積優(yōu)化問題屬于組合優(yōu)化問題[4]，因其存在指數(shù)級(jí)的解空間，為在較為合理的時(shí)間內(nèi)得到較好的優(yōu)化結(jié)果，常采用智能優(yōu)化方法來解決。遺傳算法（Genetic Algorithm，GA）因其基因編碼的離散特性，非常宜于用來解決納電子MPRM電路面積優(yōu)化問題[5]。盡管粒子群優(yōu)化（Particle Swarm Optimization，PSO）是作為一種用于實(shí)值空間優(yōu)化的技術(shù)被Eberhart R和Kennedy J提出[6]，但近幾年來已有一些文獻(xiàn)提出了可用于納電子MPRM電路面積優(yōu)化的離散粒子群優(yōu)化（Discrete PSO， DPSO）算法以及改進(jìn)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]和差分進(jìn)化算法[11]的啟發(fā)，本文提出基于全離散PSO（Fully Discretized PSO，F(xiàn)DPSO）的納電子MPRM電路面積優(yōu)化算法。該算法僅建立在粒子位置更新方程之上，采用概率變異更新策略[4]維持粒子多樣性，并使用探索概率參數(shù)來平衡算法的全局探索和局部開拓。使用一組輸入數(shù)大于20的MCNC（Microelectronics Center of North Carolina）電路對(duì)算法進(jìn)行了驗(yàn)證，并與其他可用于納電子MPRM電路面積優(yōu)化的智能優(yōu)化算法進(jìn)行了比較。endprint

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

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

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

2.2 FDPSO算法模型

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

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

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

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

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

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

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

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

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

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

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

7） 計(jì)算群中粒子適應(yīng)度值，更新每個(gè)粒子的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é)果沒有改變所累計(jì)次數(shù)達(dá)到[20×lnn]則結(jié)束算法，算法的步驟8）統(tǒng)計(jì)尋優(yōu)結(jié)果沒有改變所累計(jì)的次數(shù)。

3 實(shí)驗(yàn)結(jié)果與分析

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

3.1 實(shí)驗(yàn)設(shè)置

FDPSO算法的參數(shù)設(shè)置為[tm=180]，[N=30]，[Wb=0.7]，[We=0.2，]這些參數(shù)值通過基準(zhǔn)電路的初步實(shí)驗(yà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é)束條件。由于四種算法均具有一定的隨機(jī)性，因此在實(shí)驗(yàn)中對(duì)于每個(gè)基準(zhǔn)電路，每種算法均獨(dú)立運(yùn)行20次，并統(tǒng)計(jì)算法結(jié)果電路面積的平均值以及所花費(fèi)CPU時(shí)間的平均值。

3.2 結(jié)果分析

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

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

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

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

4 結(jié) 語

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

參考文獻(xiàn)

[1] 卜登立，江建慧.使用系數(shù)矩陣變換極性轉(zhuǎn)換的MPRM電路面積優(yōu)化[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，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é)報(bào)，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é)報(bào)（理學(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].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，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é)報(bào)（自然科學(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