-
摘要:
基于XNOR/OR的固定极性Reed-Muller(FPRM)电路面积优化是当前集成电路设计领域的研究热点之一。由于基于XNOR/OR的FPRM电路面积优化属于组合优化问题,提出了一种二进制自适应细菌觅食算法(BFA)。该算法在复制操作中加入概率模式,提高种群多样性,采用模糊规则对复制概率和迁移概率进行修正,提高算法的收敛速度。使细菌在邻域内进行搜索,替代细菌群体感应机制中的斥力操作,细菌无需感应其他个体位置对其的影响。提出一种基于XNOR/OR的FPRM电路面积优化方法,利用提出的二进制自适应细菌觅食算法搜索电路面积最小的FPRM电路。基于MCNC Benchmark电路的实验结果表明:面积最大优化率为18%,时间最大节省率为46%。
-
关键词:
- 面积优化 /
- 细菌觅食算法(BFA) /
- 复制概率 /
- 模糊规则 /
- 固定极性Reed-Muller (FPRM)
Abstract:XNOR/OR-based fixed polarity Reed-Muller (FPRM) circuit area optimization is one of the current research hotspots in the field of integrated circuit design. However, the existing XNOR/OR-based FPRM circuit area optimization method has problems such as poor optimization effect and low optimization efficiency. Since XNOR/OR-based FPRM circuit area optimization is a combinatorial optimization problem, a binary adaptive bacterial foraging algorithm (BFA) is first proposed. The algorithm adds a probability model to the replication operation to improve the diversity of the population, and uses fuzzy rules to modify the replication probability and migration rate to improve the convergence speed of the algorithm. This algorithm allows bacteria to search in the neighborhood, replacing the repulsion operation in the quorum sensing mechanism of bacteria, and bacteria no longer need to sense the influence of other individual positions on it. In addition, an XNOR/OR-based FPRM circuit area optimization method is proposed. This method uses the proposed binary adaptive bacterial foraging algorithm to search for the FPRM circuit with the smallest circuit area. The experimental results based on the MCNC Benchmark circuit show that the maximum area optimization rate reaches 18%, and the maximum time saving rate reaches 46%.
-
表 1 Pc模糊控制表
Table 1. Pc Fuzzy control table
Am Ac B C S B C P VP C S C P S VS S C 表 2 Pm模糊控制表
Table 2. Pm Fuzzy control table
Am Ac B C S B C S VS C P C S S VP P C 表 3 四种算法在面积优化上的实验结果
Table 3. Experimental results of four algorithms on area optimization
算法 统计指标 rd53 Con1 rd84 clip alu3 br1 br2 amd alu4 table5 bcc bcd 测试电路输入变量个数 5 7 8 9 10 11 12 14 14 17 26 26 TGA best 19 25 55 441 4 266 142 469 619 267 127 383 average 25 25 56.6 441.7 4.5 266 201.3 469.5 619.3 267 153.3 388.3 TBFA best 19 25 55 441 4 266 142 469 619 267 207 599 average 23 25 56.5 453.7 4.5 308.5 185.3 469.3 684.3 276 295 660.2 IBFA best 19 25 55 466 4 266 134 459 619 279 207 599 average 19 25 55 466.6 4.5 294.3 158.3 465 619 291.3 393.6 599 BABFA best 19 25 55 441 4 266 134 447 596 255 107 311 average 19 25 55 441 4 266 134 451 596 255.6 112.4 311.6 save_best save1 0 0 0 0 0 0 6 5 4 4 16 19 save2 0 0 0 0 0 0 6 5 4 4 48 48 save3 0 0 0 5 0 0 0 3 4 9 48 48 save_average save1 24 0 3 0 11 0 33 4 4 4 27 20 save2 17 0 3 3 11 14 28 4 13 7 62 53 save3 0 0 0 5 11 10 15 3 4 12 71 48 表 4 四种算法在时间上的实验结果
Table 4. Experimental results of four algorithms on time
算法 统计指标 rd53 con1 rd84 clip alu3 br1 br2 amd alu4 table5 bcc bcd 测试电路输入变量个数 5 7 8 9 10 11 12 14 14 17 26 26 TGA CPU运行时间/s 0.139 1.328 1.495 1.295 0.89 1.17 1.821 1.93 1.832 2.703 3.81 2.4 TBFA CPU运行时间/s 0.174 0.879 0.88 1.589 1.2 1.14 1.423 1.081 1.456 1.053 3.423 1.83 IBFA CPU运行时间/s 0.13 0.8 0.97 1.35 0.84 1.12 2.341 0.89 2.13 1.12 2.512 1.01 BABFA CPU运行时间/s 0.11 0.724 0.85 1.22 0.72 0.723 1.021 0.55 1.001 0.81 1.01 0.52 save1_TGA 21 45 43 6 19 38 44 72 45 70 73 78 Save2_TBFA 37 18 3 23 40 37 28 49 31 23 70 72 Save3_IBFA 15 10 12 10 14 35 56 38 53 28 60 49 -
[1] PASSINO K M. Biomimicry of bacterial foraging for distributed optimization and control[J]. IEEE Control Systems Magazine, 2002, 22(3): 52-67. doi: 10.1109/MCS.2002.1004010 [2] SUPRIYONO H, TOKHI M O. Bacterial foraging algrithm with adaptable chemotactic step size[C]//International Conference on Computational Intelligence, Communication Systems and Networks. Piscataway: IEEE Press, 2010: 72-77. [3] MAJHI B, MAJHI R, PANDA G, et al. Efficient prediction of stock market indices using adaptive bacterial foraging optimization (ABFO) and BFO based techniques[J]. Expert Systems with Application, 2009, 36(6): 10097-10104. doi: 10.1016/j.eswa.2009.01.012 [4] TREATY M, MISHAP S. Bacteria foraging-based solution to optimize both real power loss and voltage stability limit[J]. IEEE Transactions on Power Systems, 2007, 22(1): 240-248. doi: 10.1109/TPWRS.2006.887968 [5] AMARESH S. Estimation of minimum energy consumption index in a protected farm using bacteria foraging optimization algorithm: Estimation of minimum energy consumption index in protected farms[J]. International Journal of Energy Optimization and Engineering, 2019, 8(3): 1-19. doi: 10.4018/IJEOE.2019070101 [6] LIU C F, WANG J F, JOSEPH Y. Integrated bacteria foraging algorithm for cellular manufacturing in supply chain considering facility transfer and production planning[J]. Applied Soft Computing, 2018, 62: 602-618. doi: 10.1016/j.asoc.2017.10.034 [7] CAI H Y, RAN L Q, ZOU L D, et al. Heuristic hybrid bacterial foraging algorithm for the pose detection of backlight units[J]. Automatic Control and Computer Sciences, 2020, 54(3): 229-237. doi: 10.3103/S0146411620030025 [8] YE F L, LEE C Y, LEE Z J, et al. Incorporating particles warm optimization into improved bacterial foraging optimization algorithm applied to classify imbalanced data[J]. Symmetry, 2020, 12(2): 229. doi: 10.3390/sym12020229 [9] ZHANG C, YU Y, WANG Y, et al. Takagisugeno fuzzy neural network hysteresis modeling for magnetic shape memory alloy actuator based on modified bacteria foraging algorithm[J]. International Journal of Fuzzy Systems, 2020, 22(4): 1314-1329. doi: 10.1007/s40815-020-00826-9 [10] LIU Y, TIAN L, FAN L. The hybrid bacterial foraging algorithm based on many-objective optimizer[J]. Saudi Journal of Biological Sciences, 2020, 27(12): 3743-3752. doi: 10.1016/j.sjbs.2020.08.021 [11] 李珺. 细菌觅食优化算法的研究与改进[D]. 兰州: 兰州交通大学, 2018: 21-31.LI J. Research and improvement of optimization algorithm for bacterial foraging[D]. Lanzhou: Lanzhou Jiao Tong University, 2018: 21-31(in Chinese). [12] HU J J, JIN N F, LI P, et al. An improved bacterial foraging algorithm for multi-modal problems[J]. Journal of Physics, 2020, 1631(1): 012069. [13] 邓莉, 鲁瑞华. 一种改进的抑制早熟收敛的模糊遗传算法[J]. 计算机科学, 2007, 34(11): 150-153. https://www.cnki.com.cn/Article/CJFDTOTAL-JSJA200711041.htmDENG L, LU R H. An improved fuzzy inheritance to inhibit precocious convergence algorithm[J]. Computer Science, 2007, 34(11): 150-153(in Chinese). https://www.cnki.com.cn/Article/CJFDTOTAL-JSJA200711041.htm [14] 李擎, 郑德玲, 唐勇, 等. 一种新的模糊遗传算法[J]. 北京科技大学学报, 2001, 23(1): 85-89. https://www.cnki.com.cn/Article/CJFDTOTAL-BJKD200101023.htmLI Q, ZHENG D L, TANG Y, et al. A new fuzzy genetic algorithm[J]. Journal of University of Science and Technology Beijing, 2001, 23(1): 85-89(in Chinese). https://www.cnki.com.cn/Article/CJFDTOTAL-BJKD200101023.htm [15] 张会红, 汪迪生, 戴静. 基于模糊遗传算法的XNOR/OR展开式最小化研究[J]. 宁波大学学报, 2013, 26(3): 35-39. https://www.cnki.com.cn/Article/CJFDTOTAL-NBDZ201303009.htmZHANG H H, WANG D S, DAI J. XNOR/OR expansion minimization based on fuzzy genetic algorithm[J]. Journal of Ningbo University, 2013, 26(3): 35-39(in Chinese). https://www.cnki.com.cn/Article/CJFDTOTAL-NBDZ201303009.htm -