基于全离散粒子群优化的纳电子MPRM电路面积优化算法

摘 要： 针对具有较多输入数的可编程阵列结构纳电子混合极性Reed?Muller电路的面积优化问题，提出一种全离散粒子群优化算法。通过将粒子速度合并到位置更新方程，充分挖掘粒子群优化中的学习因素得到全离散化的粒子更新方程，在此基础之上设计FDPSO算法，并使用探索概率作为算法参数控制算法全局探索与局部开拓间的平衡。对一组输入数大于20的MCNC电路进行优化的实验结果表明，与其他能够用于可编程阵列结构纳电子混合极性Reed?Muller电路面积优化的智能算法相比，全离散粒子群优化算法具有较强的全局收敛能力和结果稳定性，能够以较高时间效率获得较好的优化结果。

关键词： 纳电子； MPRM电路； 面积优化； 粒子群优化； 更新方程； 算法参数

中图分类号： TN431.2?34； TP391.72 文献标识码： 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]，因其逻辑表示的紧凑性及其电路实现的良好可测试性[2]，在算术电路、通信电路以及校验电路中得到了广泛应用[1]。这些电路是计算机和通信系统中的关键电路，紧凑的逻辑表示有助于降低电路的面积和功耗，良好的可测试有助于提高系统的可靠性。

当器件尺寸进入纳米规模，基于纳电子器件的可编程阵列结构被认为是一种很有前景的纳电子电路结构[3]，这种电路结构也非常宜于用来映射MPRM逻辑从而构建纳电子MPRM电路。纳电子MPRM电路面积优化问题属于组合优化问题[4]，因其存在指数级的解空间，为在较为合理的时间内得到较好的优化结果，常采用智能优化方法来解决。遗传算法（Genetic Algorithm，GA）因其基因编码的离散特性，非常宜于用来解决纳电子MPRM电路面积优化问题[5]。尽管粒子群优化（Particle Swarm Optimization，PSO）是作为一种用于实值空间优化的技术被Eberhart R和Kennedy J提出[6]，但近几年来已有一些文献提出了可用于纳电子MPRM电路面积优化的离散粒子群优化（Discrete PSO， DPSO）算法以及改进DPSO算法，如文献[4]的HDPSO（Hybrid multi?valued DPSO）算法，文献[7]的DTPSO（Discrete Ternary PSO）算法，文献[8]中将GA与文献[7]DTPSO算法相结合的GA?DTPSO算法，文献[9]中的SADPSO算法（Simulated Annealing DPSO，SADPSO）。但这些算法要么结果质量较差，要么仅适用于输入数小于20的电路。

受文献[10]和差分进化算法[11]的启发，本文提出基于全离散PSO（Fully Discretized PSO，FDPSO）的纳电子MPRM电路面积优化算法。该算法仅建立在粒子位置更新方程之上，采用概率变异更新策略[4]维持粒子多样性，并使用探索概率参数来平衡算法的全局探索和局部开拓。使用一组输入数大于20的MCNC（Microelectronics Center of North Carolina）电路对算法进行了验证，并与其他可用于纳电子MPRM电路面积优化的智能优化算法进行了比较。endprint

1 纳电子MPRM电路及面积优化问题

本文采用基于纳电子器件的可编程阵列结构实现MPRM逻辑，[n-]输入/[m-]输出的纳电子MPRM电路结构如图1所示。

图1中行线与列线交叉位置处的“NC”为可编程纳电子单元，有2个输入和1个输出，如编号为①的NC所示，其Y表示输出，A和B表示输入，可以采用文献[3]中的Nanocell或者文献[12]中的可编程逻辑门单元。图1中的每一行对应MPRM逻辑中一个乘积项[πi]（[πi]行线，[0≤i≤u-1]），位于虚线左侧的部分称为“AND平面”，其中的列线为[xl]和[xl]（[0≤l≤n-1]），共有[2n]列，如果变量[xl]在[πi]中以原变量形式出现，则[xl]列线与[πi]行线交叉位置的“NC”被编程为与门，并完成如图1中编号为①的可编程单元所示的连接，如果变量[xl]在[πi]中以补变量形式出现，则[xl]列线与[πi]行线交叉位置的“NC”被编程为与门，并完成如图1中编号为②的可编程单元所示的连接，从而实现乘积项[πi]；位于虚线右侧的部分称为“XOR平面”，其中的列线输出函数[fk]，共有[m]列，如果乘积项[πi]属于[fk]，则[fk]列线与[πi]行线交叉位置的“NC”被编程为异或门，并完成如图1中编号为③和④的可编程单元所示的连接，从而实现乘积项间的异或运算。

2 纳电子MPRM电路面积优化算法

2.1 编码和适应度函数

将MPRM逻辑的极性向量[1]作为粒子的位置向量[Dj=[dj，n-1，…，dj，0]]，[dj，l]表示粒子群中索引为[j]的粒子在[n]维搜索空间中第[l]维的位置。

所采用的适应度函数为式（1）中的[C（h）]，首先根据极性向量使用文献[5]中的极性转换方法对MPRM逻辑进行极性转换，然后再计算其对应纳电子MPRM电路的面积[C（h）]。

2.2 FDPSO算法模型

式中：[?]表示下取整；[N]为粒子群规模。

由式（2）和式（3）可以看出，粒子在搜索空间中的移动受到Pbest，Gbest以及Mbest的影响。将Mbest作为合力引导粒子的搜索，可以增强粒子的学习能力，在一定程度上避免由于Gbest的过度吸引导致群搜索陷入局部极小。为了避免群搜索过于发散而引起群搜索爆炸问题，引入[W]因子，使粒子以一定概率受Mbest的吸引。较大的[W]因子意味着粒子以较高概率受Mbest的引导，可以使粒子群搜索更大的区域，增强全局探索能力，较小的[W]因子则意味着粒子以较小概率受Mbest的引导，可使群搜索进行局部开拓，避免发散，促使算法的收敛。

由于群搜索前期阶段侧重于全局探索，后期阶段侧重于局部开拓，因此可以使用随迭代次数线性递减的[W]因子来实现全局探索与局部开拓之间的平衡。假设[Wb∈0，1]和[We∈0，1]分别表示[W]因子的初值和终值，[tm]表示最大迭代次数，则第[t]次迭代时[W]因子的取值由式（4）计算。

2.3 纳电子MPRM电路面积优化算法

根据前述的编码和适应度函数以及FDPSO算法模型，设计基于FDPSO的纳电子MPRM面积优化算法，下面给出其算法描述：

1） 读取电路逻辑网表；

2） 算法参数初始化，包括最大迭代次数[tm]、粒子群规模[N]，[W]因子：[Wb]和[We]；

3） 迭代次数变量[t=0]，Gbest没有改变累计计数变量[v=0]；

4） 初始化粒子群，计算粒子适应度值，更新每个粒子的Pbest以及群最佳Gbest，并记录Gbest的适应度[C0]；

5） 使用式（4）计算当前的[W]因子，使用式（3）计算群体平均最佳Mbest；

6） 对群中每个粒子位置向量的每一维位置：生成随机数[r0∈0，1]和[pmt∈0.01，0.05]以及[r1∈0，1]，使用式（2）更新该位置；

7） 计算群中粒子适应度值，更新每个粒子的Pbest以及群最佳Gbest，并记录Gbest的适应度[C1]；

8） 如果[C1

9） [t=t+1]，如果[t≥tm]或者[v==20×lnn，]则转至步骤10），否则转至步骤5）；

10） 输出最优纳电子MPRM电路，算法结束。

算法步驟9）中的结束条件除了达到最大迭代次数结束之外，还采取了文献[4]中的结束条件，如果在达到最大迭代次数之前FDPSO的寻优结果没有改变所累计次数达到[20×lnn]则结束算法，算法的步骤8）统计寻优结果没有改变所累计的次数。

3 实验结果与分析

将本文的FDPSO算法与文献[8]中的GA?DTPSO算法、文献[9]中的SADPSO算法以及文献[5]中的HGA算法进行比较。四种算法均采用文献[5]中的MPRM逻辑极性转换方法，以及如式（1）所示的成本函数和优化目标，并用C++实现，在Linux下使用g++编译器编译。使用四种算法分别对一组输入数大于20的MCNC电路在配置为Intel Core i3?2350M CPU 6 GB RAM的个人计算机上进行纳电子MPRM电路面积优化。

3.1 实验设置

FDPSO算法的参数设置为[tm=180]，[N=30]，[Wb=0.7]，[We=0.2，]这些参数值通过基准电路的初步实验确定。SADPSO算法的参数设置与文献[9]相同，HGA算法的参数设置与文献[5]相同。

由于FDPSO，SADPSO和HGA算法的群规模均为30，最大迭代次数均为180，因此GA?DTPSO算法的种群规模也设为30，最大迭代次数也设为180，其他参数设置则与文献[8]相同。另外，SADPSO，HGA和GA?DTPSO算法也都采用了与FDPSO算法相同的结束条件。由于四种算法均具有一定的随机性，因此在实验中对于每个基准电路，每种算法均独立运行20次，并统计算法结果电路面积的平均值以及所花费CPU时间的平均值。

3.2 结果分析

表1给出四种算法的运行结果，其中“I/O”表示电路的输入数和输出数，面积和时间分别为算法20次独立运行所得到最优MPRM电路结果的面积平均值以及所花费CPU时间的平均值，时间的单位为s。从表1所示的面积“平均”结果来看，FDPSO算法要优于GA?DTPSO算法，对于这15个电路，相比GA?DTPSO算法，FDPSO算法使电路面积减少了12.56%，FDPSO算法所得结果与SADPSO算法和HGA算法相差不大。从时间“平均”角度看， FPDSO算法分别比GA?DTPSO算法和SADPSO算法降低了22.17%和172.54%的时间开销，FDPSO算法的时间效率要明显优于SADPSO算法和GA?DTPSO算法，FDPSO算法和HGA算法的时间效率相差不大，仅比HGA算法增加了3.39%的时间开销。

尽管从表1中面积的“平均”结果来看，FDPSO算法与HGA算法相差不大，但是对表1中的15个电路而言，除cc，in7和lal外，其余电路FDPSO算法的结果均比HGA算法的结果要好一些，特别是电路ts10，FDPSO算法能够搜索到全局面积最优的电路（20次运行均获得面积为128的电路结果），而HGA算法却无法搜索到全局面积最优电路（20次运行均获得面积为136的电路结果），相对于HGA算法，FDPSO算法将ts10的电路面积降低了5.88%。为对FDPSO和HGA做进一步比较，图2给出了HGA算法和FDPSO算法结果的变异系数（变异系数等于标准差除以均值）[4]，可以通过变异系数来评价算法的寻优能力（全局收敛能力）和算法结果的稳定性，变异系数越小则表示算法的寻优能力和结果稳定性越好。

由图2可以看出，在15个电路中，HGA算法结果的变异系数为0的电路仅有3个，而FDPSO算法却有8个，是HGA算法的2.67倍，并且对于绝大多数电路而言，FDPSO算法结果的变异系数要小于HGA算法。从15个电路结果变异系数的平均值来看，相对于HGA算法，FDPSO算法将变异系数降低了75.76%。可见，尽管从“面积”平均结果来看，FDPSO算法与HGA算法基本相同，但FDPSO算法的寻优能力明显优于HGA算法，FDPSO算法具有更强的全局收敛能力和结果稳定性。

综上所述，FDPSO算法能够获得比GA?DTPSO算法更好的优化结果。在获得基本相同面积平均结果的情况下，FDPSO算法比SADPSO算法具有更高的时间效率，FDPSO算法比HGA算法具有更好的全局收敛能力和结果稳定性。可见，FDPSO算法能够很好地解决具有较多输入数的纳电子MPRM电路的面积优化问题。

4 结 语

本文针对基于纳电子器件可编程阵列构建的纳电子MPRM电路，提出了基于FDPSO的纳电子MPRM电路面积优化算法，该算法模型建立在全离散化的粒子更新方程之上，并且仅需设置4个算法参数，算法结构简单，易用性较强。对一组输入数大于20的电路进行纳电子MPRM电路面积优化的实验结果表明，从总体角度来看，与其他可用于纳电子MPRM电路面积优化的智能优化算法相比，FDPSO算法具有更强的全局收敛能力和结果稳定性，能够得到较好的优化结果，并且具有较高的时间效率，能够很好地解决具有较多输入数的纳电子MPRM电路的面积优化问题。

参考文献

[1] 卜登立，江建慧.使用系数矩阵变换极性转换的MPRM电路面积优化[J].计算机辅助设计与图形学学报，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] 卜登立，江建慧.基于混合多值离散粒子群优化的混合极性Reed?Muller最小化算法[J].电子与信息学报，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].浙江大学学报（理学版），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电路面积优化中的应用[J].计算机辅助设计与图形学学报，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].重庆邮电大学学报（自然科学版），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