基于ERWOA的多输出MPRM电路面积优化

何俊才; 何振学; 王福顺; 霍志胜; 肖利民

doi:10.13700/j.bh.1001-5965.2021.0410

基于ERWOA的多输出MPRM电路面积优化

doi: 10.13700/j.bh.1001-5965.2021.0410

何俊才^{1, 2},
何振学^{1, 2, ,},
王福顺¹,
霍志胜^{3, 4},
肖利民⁵

1.
河北农业大学智能农业装备研究院，保定 071001
2.
河北农业大学河北省农业大数据重点实验室，保定 071001
3.
北京航空航天大学高性能计算平台，北京 100191
4.
北京航空航天大学软件学院，北京 100191
5.
北京航空航天大学计算机学院，北京 100191

基金项目: 国家自然科学基金(62102130)；中央引导地方科技发展项目基金(226Z0201G)；河北省自然科学基金(F2020204003)；河北省青年拔尖人才计划项目(BJ2019008)；河北省高等学校科学技术研究项目(QN2022095)；河北省省属高等学校基本科研业务费研究项目(KY2022073)

详细信息

通讯作者:
E-mail：hezhenxue@buaa.edu.cn

中图分类号: V443；TP391.72
计量
- 文章访问数: 179
- HTML全文浏览量: 12
- PDF下载量: 11
- 被引次数: 0
出版历程
- 收稿日期: 2021-07-20
- 录用日期: 2021-08-29
- 网络出版日期: 2021-09-14
- 整期出版日期: 2023-05-31

Circuit area optimization of multi-output MPRM based on ERWOA algorithm

HE Juncai^{1, 2},
HE Zhenxue^{1, 2
, ,},
WANG Fushun¹,
HUO Zhisheng^{3, 4},
XIAO Limin⁵

1.
Intelligent Agricultural Equipment Research Institute，Hebei Agricultural University，Baoding 071001，China
2.
Key Laboratory of Agricultural Big Data of Hebei Province，Hebei Agricultural University，Baoding 071001，China
3.
High Performance Computing Platform，Beihang University，Beijing 100191，China
4.
School of Software，Beihang University，Beijing 100191，China
5.
School of Computer Science and Engineering，Beihang University，Beijing 100191，China

Funds: National Natural Science Foundation of China (62102130); Central Government Guides Local Science and Technology Development Fund Project (226Z0201G); Hebei Natural Science Foundation (F2020204003); Science and Technology project of Hebei Education Department (BJ2019008); Science and Technology Research Projects of Higher Education Institutions in Hebei Province (QN2022095); Basic Scientific Research Funds Research Project of Hebei Provincial Colleges and Universities (KY2022073)

More Information

Corresponding author: E-mail：hezhenxue@buaa.edu.cn

摘要

摘要:
混合极性Reed-Muller（MPRM）电路面积优化已成为集成电路设计领域的研究热点。MPRM电路面积优化是在众多的MPRM表达式中寻找与项个数最少的MPRM表达式，属于组合优化问题。为此，提出一种具有爆炸和重启机制的鲸鱼优化算法（ERWOA）。同时，提出一种多输出MPRM电路面积优化方法，该方法利用改进的鲸鱼优化算法和改进的混合极性转换算法搜索含与项个数最少的MPRM电路。基于MCNC Benchmark测试电路的实验结果表明：改进后的混合极性转换算法与基于列表技术的混合极性转换算法相比，转换效率最大提升了99.93%，与基于列表技术的极性间转换算法相比，转换效率最大提升了99.96%；改进后的鲸鱼优化算法与遗传算法相比，节省电路面积百分比最高为18.32%，平均为5.54%，与人工蜂群算法相比，节省电路面积百分比最高为14.41%，平均为5.00%。
- 组合优化问题 /
- 鲸鱼优化算法 /
- 重启机制 /
- 爆炸机制 /
- 遗传算法
Abstract:
Mixed polarity Reed-Muller (MPRM) circuit area optimization has become a research hotspot in the field of integrated circuit design. It is a combinatorial optimization, aiming at finding the MPRM expression with the least number of terms among many MPRM expressions. A explosion strategy and restart strategy based whale optimization algorithm (ERWOA) is proposed. In addition, a multi-output MPRM circuit area optimization method is proposed, which uses the improved whale algorithm and the improved polarity conversion algorithm to search for the MPRM circuit with the least number of AND terms. Results on the MCNC Benchmark circuits show that the proposed algorithm increases the conversion efficiency by 99.93% and 99.96% at most, compared with the mixed polarity and inter-polarity conversion algorithms based on the list technology, respectively. Compared with the genetic algorithm and the artificial bee colony algorithm, the improved whale optimization algorithm saves the circuit area up to 18.32% with an average of 5.54%, and 14.41% with an average of 5.00%, respectively.
- combinatorial optimization /
- whale optimization algorithm /
- restart strategy /
- explosion mechanism /
- genetic algorithm

HTML全文

图 1 爆炸过程

Figure 1. Explosion process

下载: 全尺寸图片幻灯片

图 2 方法流程

Figure 2. Algorithm flowchart

下载: 全尺寸图片幻灯片

图 3 newcond电路收敛曲线

Figure 3. Convergence curves of newcond circuit

下载: 全尺寸图片幻灯片

图 4 misex3电路收敛曲线

Figure 4. Convergence curves of misex3 circuit

下载: 全尺寸图片幻灯片

图 5 in0收敛曲线

Figure 5. Convergence curves of in0 circuit

下载: 全尺寸图片幻灯片

图 6 b2电路收敛曲线

Figure 6. Convergence curves of b2 circuit

下载: 全尺寸图片幻灯片

表 1 算法参数

Table 1. Algorithm parameters

参数	种群	最大迭代次数	值不变次数	火花数	变异率	交叉率	蜜源位置不变次数
WOA	80	110
GA	50				0.08	0.8
ABC	60						9
ERWOA	40	130	5	30

下载: 导出CSV

表 2 混合极性转换实验数据

Table 2. Experimental data of mixed polarity conversion

电路	I/O	运行时间/s		${R_{ {\text{save}} } }$/%	area1	area2
电路	I/O	算法1	算法2	${R_{ {\text{save}} } }$/%	area1	area2
misex1	8/7	0	0	0	60	60
ex1010	10/10	0.01	0.01	0	1023	1023
misex3	14/14	0.41	0.07	82.93	6028	6028
table3	14/14	2.31	0.12	94.81	5509	5509
t481	16/1	6.54	0.23	96.48	41	41
al2	16/47	20.68	0.46	97.78	358	358
ryy6	16/1	3.55	0.17	95.21	80	80
spla	16/46	95.48	1.04	98.91	34852	34852
t2	17/16	17.01	0.54	96.83	2490	2490
table5	17/15	319.47	1.17	99.63	74504	74504
in2	19/10	750.73	2.01	99.73	6315	6315
shift	19/16	7306.43	4.75	99.93	128	128
mark1	20/31	5792.21	5.26	99.91	163838	163 838

下载: 导出CSV

表 3 极性间转换实验数据

Table 3. Experimental data for conversion between different polarities

电路	I/O	运行时间/s		$ {R_{{\text{save}}}} $/%	area3	area4
电路	I/O	算法3	算法4	$ {R_{{\text{save}}}} $/%	area3	area4
misex1	8/7	0	0	0	128	128
ex1010	10/10	0.01	0.01	0	810	810
misex3	14/14	4.58	0.16	96.51	12281	12281
table3	14/14	0.54	0.07	87.04	3273	3273
t481	16/1	16.74	0.25	98.51	42016	42016
al2	16/47	70.71	0.54	99.24	65536	65536
ryy6	16/1	1.98	0.09	95.45	19710	19710
spla	16/46	51.34	0.59	98.85	42177	42177
t2	17/16	313.76	1.07	99.66	50032	50032
table5	17/15	45.14	0.75	98.34	28668	28668
in2	19/10	6405.11	3.40	99.95	420176	420176
shift	19/16	5774.48	2.29	99.96	524033	524033
mark1	20/31	15102.41	6.42	99.96	524512	524512

下载: 导出CSV

表 4 算法实验数据

Table 4. Experiment data of algorithm

电路	I/O	WOA				GA				ABC				ERWOA
电路	I/O	最优值	最差值	标准差	平均值	最优值	最差值	标准差	平均值	最优值	最差值	标准差	平均值	最优值	最差值	标准差	平均值
max512	9/6	201	295	20.46	205.85	201	215	3.13	202.75	201	204	0.78	201.30	201	201	0	201.00
ex1010	10/10	810	1011	45.16	823.15	810	926	26.15	890.10	810	879	24.16	820.15	810	810	0	810
newcond	11/2	48	52	1.30	49.00	48	51	0.78	48.30	48	52	1.19	48.70	48	48	0	48.00
br1	12/8	23	46	5.04	24.50	23	25	0.44	23.10	23	27	1.07	23.50	23	23	0	23.00
amd	14/24	104	108	1.16	104.60	104	118	3.04	107.40	104	125	4.60	106.50	104	104	0	104.00
misex3	14/14	1421	1731	82.15	1493.65	1421	1832	114.48	1632.00	1421	1964	143.53	1663.25	1421	1472	11.12	1423.55
in0	15/11	242	408	35.82	254.15	242	269	8.32	251.75	242	265	7.35	251.00	242	243	0.46	242.30
newtpla	15/5	38	40	0.59	38.45	38	39	0.46	38.30	38	45	1.50	38.80	38	39	0.22	38.05
b2	16/17	333	373	12.57	344.90	333	370	11.25	347.50	333	453	30.43	362.20	333	333	0	333.00
b9	16/5	105	251	32.06	116.30	105	161	14.63	128.55	105	233	28.80	117.15	105	105	0	105.00
in1	16/17	333	376	14.54	345.20	333	390	15.18	359.15	333	482	43.55	371.65	333	333	0	333.00
pdc	16/40	683	752	17.69	696.10	694	757	27.02	724.10	683	917	55.12	714.20	683	693	4.00	685.00

下载: 导出CSV

参考文献(21)

[1]	WANG Y C, WANG L Y. Power optimization for FPRM logic using approximate computing technique[C]//2019 IEEE 13th International Conference on ASIC (ASICON). Piscataway: IEEE Press, 2020: 1-4.
[2]	HE Z X, WU X Q, WANG C, et al. Delay optimization for ternary fixed polarity Reed-Muller circuits based on multilevel adaptive quantum genetic algorithm[J]. International Journal of Intelligent Systems, 2021, 36(10): 5981-6006. doi: 10.1002/int.22538
[3]	周宇豪, 何振学, 梁新艺, 等. 基于BABFA的XNOR/OR电路面积优化[J]. 北京航空航天大学学报, 2022, 48(10): 2031-2039. ZHOU Y H, HE Z X, LIANG X Y, et al. Optimization of XNOR/OR circuit area based on BABFA[J]. Journal of Beijing University of Aeronautics and Astronautics, 2022, 48(10): 2031-2039(in Chinese).
[4]	XIAO L M, HE Z X, RUAN L, et al. Optimization of best polarity searching for mixed polarity reed-muller logic circuit[C]//2015 28th IEEE International System-on-Chip Conference (SOCC). Piscataway: IEEE Press, 2016: 275-280.
[5]	FU Q, WANG P J, TONG N, et al. Integrated polarity optimization of MPRM circuits based on improved multi-objective particle swarm optimization[J]. Chinese Journal of Electronics, 2020, 29(5): 833-840. doi: 10.1049/cje.2020.07.005
[6]	卜登立. 基于概率表达式的MPRM电路功耗计算方法[J]. 电子学报, 2018, 46(12): 3060-3067. doi: 10.3969/j.issn.0372-2112.2018.12.033 BU D L. Probability expression based power estimation method for MPRM circuits[J]. Acta Electronica Sinica, 2018, 46(12): 3060-3067(in Chinese). doi: 10.3969/j.issn.0372-2112.2018.12.033
[7]	WANG X, ZHANG R, WANG W K, et al. Polarity searching for MPRM logic circuit based on improved adaptive genetic algorithm[C]//IEEE 12th International Conference on Ubiquitous Intelligence and Computing and 2015 IEEE 12th International Conference on Autonomic and Trusted Computing and 2015 IEEE 15th International Conference on Scalable Computing and Communications and Its Associated Workshops (UIC-ATC-ScalCom). Piscataway: IEEE Press, 2016: 1354-1358.
[8]	李辉, 汪鹏君, 王振海. 混合极性列表技术及其在MPRM电路面积优化中的应用[J]. 计算机辅助设计与图形学学报, 2011, 23(3): 527-533. LI H, WANG P J, WANG Z H. Tabular techniques for mixed-polarity and its application in area optimization of MPRM circuits[J]. Journal of Computer-Aided Design & Computer Graphics, 2011, 23(3): 527-533(in Chinese).
[9]	WANG P J, LI H, WANG Z H. MPRM expressions minimization based on simulated annealing genetic algorithm[C]//IEEE International Conference on Intelligent Systems and Knowledge Engineering. Piscataway: IEEE Press, 2011: 261-265.
[10]	李辉. 混合极性Reed-Muller逻辑电路功耗和面积优化[D]. 宁波: 宁波大学, 2011. LI H. Power and area optimization of mixed polarity reed-muller logic circuits[D]. Ningbo: Ningbo university, 2011(in Chinese).
[11]	卜登立, 江建慧, 罗文浪. 基于2个阶段遗传算法的MPRM电路面积与SER折中优化[J]. 计算机辅助设计与图形学报, 2017, 29(10): 1924-1934. BU D L, JIANG J H, LUO W L. Two-phase GA based area and SER trade-off algorithm for MPRM circuits[J]. Journal of Computer-Aided Design & Computer Graphics, 2017, 29(10): 1924-1934(in Chinese).
[12]	卜登立, 江建慧. 基于混合多值离散粒子群优化的混合极性Reed-Muller最小化算法[J]. 电子与信息学报, 2013, 35(2): 361-367. BU D L, JIANG J H. 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(in Chinese).
[13]	MIRJALILI S, LEWIS A. The whale optimization algorithm[J]. Advances in Engineering Software, 2016, 95: 51-67. doi: 10.1016/j.advengsoft.2016.01.008
[14]	龙文, 蔡绍洪, 焦建军, 等. 求解大规模优化问题的改进鲸鱼优化算法[J]. 系统工程理论与实践, 2017, 37(11): 2983-2994. doi: 10.12011/1000-6788(2017)11-2983-12 LONG W, CAI S H, JIAO J J, et al. Improved whale optimization algorithm for large scale optimization problems[J]. Systems Engineering-Theory & Practice, 2017, 37(11): 2983-2994(in Chinese). doi: 10.12011/1000-6788(2017)11-2983-12
[15]	ABDEL-BASSET M, EL-SHAHAT D, SANGAIAH A K. A modified nature inspired meta-heuristic whale optimization algorithm for solving 0-1 knapsack problem[J]. International Journal of Machine Learning and Cybernetics, 2019, 10(3): 495-514. doi: 10.1007/s13042-017-0731-3
[16]	STRUMBERGER I, BACANIN N, TUBA M L, et al. Resource scheduling in cloud computing based on a hybridized whale optimization algorithm[J]. Applied Sciences, 2019, 9(22): 4893. doi: 10.3390/app9224893
[17]	GAUTAM A, BISWAS M. Whale optimization algorithm based edge detection for noisy image[C]//2018 Second International Conference on Intelligent Computing and Control Systems (ICICCS). Piscataway: IEEE Press, 2019: 1878-1883.
[18]	VARMA D, TRACHTENBERG E A. Computation of Reed-Muller expansions of incompletely specified Boolean functions from reduced representations[J]. IEE Proceedings E Computers and Digital Techniques, 1991, 138(2): 85-92. doi: 10.1049/ip-e.1991.0011
[19]	TAN Y, ZHU Y C. Fireworks algorithm for optimization[C]//Proceedings of the First International Conference on Advances in Swarm Intelligence - Volume Part I. New York: ACM, 2010: 355-364.
[20]	谭营, 郑少秋. 烟花算法研究进展[J]. 智能系统学报, 2014, 9(5): 515-528. doi: 10.3969/j.issn.1673-4785.201409010 TAN Y, ZHENG S Q. Recent advances in fireworks algorithm[J]. CAAI Transactions on Intelligent Systems, 2014, 9(5): 515-528(in Chinese). doi: 10.3969/j.issn.1673-4785.201409010
[21]	KRISHNAKUMAR K. Micro-genetic algorithms for stationary and non-stationary function optimization[C]//Proceedings SPIE 1196, Intelligent Control and Adaptive Systems, 1990, 1196: 289-296.