基于Pareto支配的MPRM电路面积与功耗优化*

闫盼盼，俞海珍，史旭华，万 凯

(宁波大学信息科学与工程学院，浙江 宁波 315211)

1 引言

随着集成电路(IC)技术的发展，电路集成度正在迅速增加[1,2]。功耗和面积已经成为IC设计中不容忽视的问题，在电路设计流程的各个阶段都需要考虑电路面积和功耗。

任何逻辑电路都可以由基于AND/OR/NOT形式的布尔逻辑，也可以由基于AND/XOR或OR/XNOR形式的RM(Reed-Muller)逻辑来表示。随着集成电路优化设计的发展，以RM逻辑表示的逻辑电路在功耗、面积、速度和可测试性方面比用传统布尔逻辑表示的逻辑电路更具优势[3]。

RM逻辑主要分为固定极性RM FPRM(Fixed-Polarity Reed-Muller)和混合极性RM MPRM(Mixed-Polarity Reed-Muller)。MPRM展开式的极性搜索空间庞大，包含了FPRM展开式的所有极性。因此，MPRM具有比FPRM更大的优化空间和更好的优化效果。极性直接决定MPRM逻辑电路的表达形式，然后影响电路的面积和功耗，并且其优化是在特定空间中搜索1个或多个极性，使其目标函数获得最优值。但是，MPRM电路也有其劣势，它的极性搜索空间庞大，使其电路性能优化的时间和空间复杂度很高。因此，需要寻找一种有效的算法来解决MPRM逻辑电路的这个问题。粒子群算法、遗传算法、免疫算法都是目前比较常用的智能算法[4 - 6]。由于粒子群算法相比其它算法具有收敛速度快、鲁棒性好等优点，获得了越来越多的关注。此外，它具有内在的并行搜索机制，特别适用于传统方法难以解决的复杂优化问题。国内外很多学者对粒子群算法进行研究，取得了一些成果。文献[7]提出一种多目标量子粒子群算法，采用共享学习机制和双势阱模型避免算法发生过早收敛；文献[8]提出了一种分群多目标粒子群算法，采用向量法划分子区域，不同子区域采用不同的搜索策略进行寻优操作，保持算法的多样性；文献[9]提出了一种三值多样性粒子群算法，采用广泛学习策略和三值变异操作进行算法改进，以保持种群多样性策略，从而有效地克服算法的早熟收敛问题。

综上所述，本文在离散三值粒子群优化算法研究的基础上，结合混合极性的特征，对文献[9]中采用三值多样性粒子群算法求解MPRM电路综合优化问题主要作了如下改进:(1)采用Pareto支配关系构造外部集；(2)采用快速排序的方法在种群中搜索非支配解集；(3)对粒子进行边界约束处理。通过加入上述3种改进策略，提出一种多目标三值多样性粒子群MOTDPSO(Multi-Objective Ternary Diversity Particle Swarm Optimization)算法。利用MOTDPSO算法对MPRM电路进行最佳功耗和面积的综合优化，得到Pareto前沿，实现面积和功耗的折衷优化，并通过实验进行了验证。粒子的位置、速度更新公式参考文献[9]。

2 MPRM电路面积和功耗估计模型

在混合极性OR/XNOR电路中，对于任意1个n变量的逻辑函数极性P对应的OR/XNOR展开式如式(1)所示：

(1)

由式(1)可知，OR/XNOR电路实际是由多输入XNOR 和OR操作组成的，而多输入的XNOR 和OR操作可以分解为二输入的XNOR 和OR操作，二输入的XNOR 和OR操作项数之和则表示电路面积。

多输入OR操作分解如式(2)所示，根据式(2)，Si可由mi个二输入OR操作得到。

(2)

多输入XNOR 和OR操作具体分解如式(3)和式(4)所示，根据式(3)和式(4)将多输入XNOR 和OR操作分解成二输入OR操作和二输入XNOR操作，它们的最终项数可表示为:

(3)

(4)

混合极性OR/XNOR电路面积Earea可表示为:

Earea=No_of_OR+No_of_XNOR=

(5)

目前集成电路的主要形式是CMOS电路，对于一个由n个门组成的电路，其总动态功耗的表达式为:

(6)

(7)

在式(7)中可看到，开关活动性的大小仅与P(g)有关，P(g)是输出信号g的概率。根据文献[10，11]可将多输入XNOR和OR分解为一系列二输入XNOR和OR。分解完成后，把XNOR门和OR门的开关活动性进行相加，从而得到整个MPRM逻辑电路的开关活动性，通过开关活动性的总和来权衡电路的功耗。

3 基于MOTDPSO算法的MPRM电路面积与功耗优化

3.1 基于Pareto支配的三值粒子群算法

在用Pareto支配概念进行算法改进的过程中，涉及3个集合：

(1)种群：由算法中的所有粒子组合而成。

(2)非支配集：保存了每一代中的非支配解。

(3)外部集：保存了种群从初始到目前搜索到的所有非支配解。

上述3个集合中，非支配集是保存种群的每一代的非支配解的集合。外部集的更新是通过非支配集按照支配关系插入外部集，进而构成新的外部集。种群更新是由于个体和全局最优位置的更新。

3.1.1 边界约束处理

部分粒子会超出定义的边界范围，这种情况会发生在粒子进行速度、位置更新以及变异的过程中，这样可能导致的结果是，最终搜索到的最优值不在定义域范围内。本文采用式(8)进行处理：

(8)

其中，[xmin,j,xmax,j]表示第j维的取值范围。

如果经过运动之后粒子到了一个新的位置，此时超出了边界，可将粒子设定在边界上，使得粒子的速度大小减为原来的一半，方向与原来反向。

3.1.2 非支配集

本文中非支配集的构造采用快速排序的方法，如算法1所示。

算法1 构造非支配集

Step 1 选择1个个体i∈S，并且i为种群S的第1个个体；

Step 2 将选择的第1个个体i与种群中其他个体进行比较,S被分为patr1和part2。

Step 2.1 如果part2被i支配,即i支配part2，清除part2;

Step 2.2 如果part1不被i支配，保留part1；

Step 2.2.1 如果i不被part1中其他个体支配，将i放入非支配集NP中；

Step 2.2.2 如果i被part1中其他个体支配，清除i；

Step 3S=patrt1，重复上述过程，直到S=∅。

3.1.3 个体最优位置

根据PSO算法的原理，个体最优位置可解释为个体i从初始化到目前为止的最优位置，如式(9)所示：

(9)

式(9)解释为，如果粒子i支配个体最优位置，粒子i的当前位置就被定为个体最优位置；如果粒子i不支配个体最优位置，则个体最优位置保持不变。

3.1.4 外部集

本文中，外部集的更新是通过非支配集按照支配关系插入外部集，进而构成新的外部集。如算法2所示。

算法2 外部集的选取

Step 1 当外部集为∅时，将初始种群的非支配集NP中的个体放入外部集中；

Step 1 当外部集不为∅时，选取1个个体i∈NP，将i与外部集中的个体进行比较支配关系；

Step 2.1 如果i被外部集中的某些个体支配，则i不能进入外部集；

Step 2.2 如果i不被外部集中的某些个体支配，将i放入外部集，外部集中被个体i支配的那些个体要被剔除；

Step 3 重复上述循环直至比较完毕。

3.1.5 全局最优位置

全局最优位置是从外部集中选取的。算法开始时，全局最优位置为粒子本身位置；接着，在每一代中，先计算拥挤距离，按照拥挤距离对外部集进行降序；然后从外部集的前10%的粒子中随机选择1个粒子的位置为全局最优位置。

3.2 MOTDPSO算法在MPRM电路综合优化上的应用

结合以上所述的三值多样性粒子群算法和混合极性OR/XNOR电路的极性转换，本文提出了一种改进的三值粒子群算法，将该算法应用于MPRM电路功耗和面积优化。算法流程具体描述如图1所示。

Figure 1 Flow chart of MPRM circuit power consumption and area optimization based on MOTDPSO algorithm图1 MOTDPSO算法优化MPRM电路功耗和面积流程图

4 实验数据与分析

本文用C语言实现MOTDPSO算法，在Windows 10操作系统下，通过VS2010编译，程序的硬件环境为Intel(R) Core(TM)i5-8250U@1.60 GHz 8 GB RAM，测试电路均采用PLA格式MCNC基准电路,对18个MCNC电路进行了面积与功耗优化，得到了Pareto最优解集和Pareto前沿。

图2给出了电路rd530、5xp10以及misex10的Pareto前沿。从图2中可以看出，这3个电路的面积与功耗的Pareto前沿不是严格的凸函数，其余电路的Pareto前沿也是如此。这也证实了使用Pareto支配进行MPRM电路面积与功耗优化的重要性。

Figure 2 Pareto frontier of MPRM circuit area and power consumption图2 MPRM电路面积与功耗Pareto前沿

表1给出了在18个MCNC电路上运行MOTDPSO算法的结果，其中“benchmark”表示测试电路的名称，“inputs”表示测试电路的输入变量个数；“N_PF”表示Pareto最优解集的大小；“面积增加”和“功耗减少”分别表示所选择的最优解相对于面积最小解所引起的面积增加和功耗降低的比率。“所选择的最优解”是根据效率因子“E=功耗减少/面积增加”所选取的最终解，其选取的原则：(1)如果存在E>1的最优解，则所选择的最优解要使E的值最大化；(2)如果不存在E>1的最优解，则所选择的最优解就是面积最小解。此原则是基于以尽可能小的面积开销获得更低的功耗。

从表1可以看出，这18个电路的Pareto最优解集都包含多个非支配最优解，特别是table3，其非支配最优解的数量达到了62个。这也证实了使用Pareto支配概念进行MPRM电路面积与可靠性优化的有效性。

根据效率因子E所选择的最终解中，有3个电路所选择的最优解就是面积最小最优解，因为找不到E小于1的最优解，换句话说，虽然可以降低功耗，但是面积开销较大。对于剩余的15个电路，所选择的最优解的E均大于1；特别是t481，在不到1%的面积开销下，功耗减少了4.26%，其最终解的E为4.84。对于表1的电路，从平均值看，相对于面积最小解，所选择的最终解面积增加了5.30%，并且功耗减少了8.18% 。

Table 1 Area and power consumption optimization results using MOTDPSO algorithm表1 MOTDPSO算法面积与功耗优化结果

为了进一步验证MOTDPSO算法求解MPRM电路面积与功耗优化的有效性，将其与NSGA-II[12]算法进行实验比对。将上述2种算法分别测试20次,对20次结果的最优解求平均值。表2给出了在18个MCNC电路上运行上述2种算法的结果。表中“benchmark”和“inputs”分别为测试电路的名称和输入变量个数，“area”和“power”分别为测试20次电路最优解的平均面积和功耗，“S(area)”和“S(power)”表示电路面积和功耗的优化率，计算公式如下所示：

(10)

(11)

其中，SA1(SP1)、SA2(SP2)分别表示对NSGA-II和MOTDPSO算法测试20次搜索到的最优解的平均面积和功耗。

由表2可知，MOTDPSO算法相比NSGA-II算法能获得更小的电路面积和功耗。比如pcle电路，MOTDPSO算法相比于NSGA-II算法面积和功耗分别优化了8.50%和13.83%。在misex3电路中，即使MOTDPSO算法搜索到的最佳极性电路面积有所增加，但功耗减少了。根据18个Benchmark电路的测试结果可知，MOTDPSO算法相比NSGA-II算法，电路面积与功耗平均优化率分别为4.29%和6.02%。最后，将2种算法运行20次的面积与功耗进行方差计算，NSGA-II算法面积与功耗方差为5.64和8.56，MOTDPSO算法面积与功耗方差分别为4.87和6.35，所以MOTDPSO算法具有良好的鲁棒性。

5 结束语

针对MPRM电路的面积与功耗综合优化问题，本文提出了一种基于MOTDPSO算法的MPRM电路面积与功耗最佳极性搜索方案。在三值多样性粒子群算法求解MPRM电路综合优化问题的基础上，对超出定义的边界范围的粒子执行边界约束处理，并结合Pareto支配概念来改进算法;然后建立了基于Pareto支配的三值粒子群算法的粒子与MPRM电路极性之间的参数映射关系，并结合面积与功耗估计模型以及 OR/XNOR电路混合极性转换方法，将该算法应用于MPRM电路的功耗和面积优化。最后对18个PLA格式MCNC Benchmark电路进行测试，与NSGA-II算法搜索到的最优解相比，MOTDPSO算法有较好的优化效果和鲁棒性。

Table 2 Optimal solution data and optimization rate of MOTDPSO and NSGA-II algorithms表2 MOTDPSO与NSGA-II算法最优解和优化率