-
摘要:
混合极性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.
-
表 1 算法参数
Table 1. Algorithm parameters
参数 种群 最大迭
代次数值不变
次数火花数 变异率 交叉率 蜜源位置
不变次数WOA 80 110 GA 50 0.08 0.8 ABC 60 9 ERWOA 40 130 5 30 表 2 混合极性转换实验数据
Table 2. Experimental data of mixed polarity conversion
电路 I/O 运行时间/s ${R_{ {\text{save}} } }$/% area1 area2 算法1 算法2 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 表 3 极性间转换实验数据
Table 3. Experimental data for conversion between different polarities
电路 I/O 运行时间/s $ {R_{{\text{save}}}} $/% area3 area4 算法3 算法4 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 表 4 算法实验数据
Table 4. Experiment data of algorithm
电路 I/O WOA GA ABC ERWOA 最优值 最差值 标准差 平均值 最优值 最差值 标准差 平均值 最优值 最差值 标准差 平均值 最优值 最差值 标准差 平均值 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 -
[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.033BU 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-12LONG 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.201409010TAN 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. -