An Efficient and Fast Area Optimization Approach for Mixed Polarity Reed-Muller Logic Circuits

Yuhao ZHOU; Zhenxue HE; Jianhui JIANG; Xiaojun ZHAO; Fan ZHANG; Limin XIAO; Xiang WANG

doi:10.23919/cje.2022.00.407

Article Contents

Article Navigation > Chinese Journal of Electronics > 2023 > Accepted Manuscript

ZHOU Yuhao, HE Zhenxue, JIANG Jianhui, et al., “An Efficient and Fast Area Optimization Approach for Mixed Polarity Reed-Muller Logic Circuits,” Chinese Journal of Electronics, vol. x, no. x, pp. 1–16, xxxx doi: 10.23919/cje.2022.00.407

Citation:

ZHOU Yuhao, HE Zhenxue, JIANG Jianhui, et al., “An Efficient and Fast Area Optimization Approach for Mixed Polarity Reed-Muller Logic Circuits,” Chinese Journal of Electronics, vol. x, no. x, pp. 1–16, xxxx doi: 10.23919/cje.2022.00.407

Citation:

PDF( 11575 KB)

An Efficient and Fast Area Optimization Approach for Mixed Polarity Reed-Muller Logic Circuits

doi: 10.23919/cje.2022.00.407

Yuhao ZHOU^1
,,
Zhenxue HE^{2, 3
,
,},
Jianhui JIANG^1
,,
Xiaojun ZHAO^2
,,
Fan ZHANG^2
,,
Limin XIAO^4
,,
Xiang WANG^5
,

1.
School of Software Engineering, Tongji University, Shanghai 201804, China
2.
Key Laboratory of Agricultural Big Data of Hebei Province, Hebei Agricultural University, Baoding 071001, China
3.
School of Computer and Communication Engineering, Northeastern University at Qinhuangdao, Qinhuangdao 066004, China
4.
School of Computer Science and Engineering, Beihang University, Beijing 100191, China
5.
School of Electronic and Information Engineering, Beihang University, Beijing 100191, China

More Information

Author Bio:
ZHOU Yuhao is a PhD candidate in the School of Software Engineering, Tongji University, China. He has authored some academic articles which have been published in refereed international journals, such as IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS, ACM TRANSACTIONS ON DESIGN AUTOMATION OF ELECTRONIC SYSTEMS, APPLIED SOFT COMPUTING, etc. His research interests include Reed-Muller circuits area optimization based on XNOR/OR, power optimization, low power integrated circuits design, computer aided design and intelligent optimization algorithm. (Email: zhouyuhao@tongji.edu.cn)

HE Zhenxue received the Ph.D. degree in computer architecture from Beihang University, Beijing, China, in 2018. He is currently a Full Associate Professor with Hebei Agricultural University. He has authored or coauthored more than 40 articles in peer-reviewed journals and proceedings, such as IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS, IEEE TRANSACTIONS ON SERVICES COMPUTING, IEEE SENSORS JOURNAL, and JOURNAL OF COMPUTER SCIENCE AND TECHNOLOGY. His research interests include low power integrated circuits design and optimization, multiple-valued logic circuits, combinatorial optimization, and intelligent algorithm. (Email:hezhenxue@buaa.edu.cn)

JIANG Jianhui received the BE, ME, and PhD degrees in traffic information engineering and control from Shanghai Tiedao University (in April 2000, it was merged to Tongji University) in 1985, 1988, and 1999, respectively. During 1994–2000, he was an associate professor in computer science and technology at Shanghai Tiedao University. Since 2000, he has been a full professor in computer science and technology at Tongji University. During 2007–2011, he was the chair of the Department of Computer Science and Technology, Tongji University. Since 2011, he is the associate dean of the School of Software Engineering, Tongji University. He is the vice director of Technical Committee on Fault-tolerant Computing, Chinese Computer Federation (CCF). He has served on several program committees of national or international symposiums or workshops. He has co-authored two books and published more than 200 technical papers. His current research interests include dependable systems and networks, software reliability engineering, and VLSI/SoC testing and fault-tolerance. He is a senior member of CCF. (Email:jhjiang@tongji.edu.cn)

ZHAO Xiaojun received the B.S. degree from Sichuan Normal University, Chengdu, China, in 2013, and received the M.S. degree from Xidian University, Xian, China, in 2016. She is currently a lecturer in Hebei Agricultural University. Her research interests include electronics design automation, intelligent algorithm, signal detection, and data processing. (Email: jaja028@126.com)

ZHANG Fan received the Ph.D. degree in computer science from Hebei Agricultural University, Baoding, China, in 2013. She is currently a Full Associate Professor with Hebei Agricultural University. She has authored or coauthored more than 20 articles in peer-reviewed journals and proceedings. Her research interests include low power integrated circuit design and optimization, Agricultural informatization. (Email: ellenzhang0911@126.com)

XIAO Limin received the bachelor’s degree in computer science (major) and physics (minor) from the Department of Computer Science, Tsinghua University, Beijing, China, in 1993, and the M.S. and Ph.D. degrees in computer science from the Institute of Computer Science, Chinese Academy of Sciences, Beijing, in 1996 and 1998, respectively. He is currently a Professor with the School of Computer Science and Engineering, Beihang University, China. He is a senior member of the Chinese Computer Society, the director of the Institute of Computer System Architecture, a member of the Electronic Science and Technology Committee of the Ministry of Industry and Information Technology, a distinguished expert of the Expert Committee of the China Information and Electronic Engineering Technology Development Strategy Research Center of the Chinese Academy of Engineering, a member of the Big Data Expert Committee of the Chinese Computer Society, member of the High-Performance Computing Committee, member of the Fault Tolerant Computing Committee, and member of the Cloud Computing Expert Committee of the Chinese Institute of Electronics. He has authored or coauthored more than 300 articles in peer-reviewed journals and proceedings. His work has been cited more than 4000 times at Google scholar with an h-index of 30. His main research areas include computer architecture, computer system software, high-performance computing, virtualization, and cloud computing. He is a Senior Member of CCF and a Senior member of IEEE. (Email: 930111386@qq.com)

WANG Xiang received the Ph.D. degree in engineering from the School of Information Technology, Peking University, Beijing, China, in 2004. He is currently a Professor with the School of Electronic and Information Engineering, Beihang University, China. He has served on the editorial boards of several international journals, such as IEEE TRANSACTIONS ON VERY LARGE SCALE INTEGRATION SYSTEMS, IEEE TRANSACTIONS ON DEPENDABLE AND SECURE COMPUTING, SCIENCE CHINA, CHINESE PHYSICS LETTERS, ACTA ELECTRONICA SINICA, JOURNAL OF SEMICONDUCTOR, JOURNAL OF ELECTRONICS, and CHINESE JOURNAL OF ELECTRONICS. He is currently a TPC member of the IEEE Conference Organizing Committee, Vice Chairman of the Conference, and Chairman of the Conference. His main research areas include very large-scale integration, micro-nano systems, genetic circuits, and aerospace information networks. He is a Senior Member of IEEE. (Email: wxiang@buaa.edu.cn)
Corresponding author: Email: hezhenxue@buaa.edu.cn
Received Date: 2022-11-29
Accepted Date: 2023-03-22

Available Online: 2023-10-10

Abstract

Abstract

At present, area has become one of the main bottlenecks restricting the development of integrated circuits. The area optimization approaches of existing XNOR/OR-based mixed polarity Reed-Muller (MPRM) circuits have poor optimization effect and efficiency. Since the area optimization of MPRM logic circuits is a combinatorial optimization problem, we propose a whole annealing adaptive bacterial foraging algorithm (WAA-BFA), which includes individual evolution based on Markov chain and Metropolis acceptance criteria, and individual mutation based on adaptive probability. In addition, we propose a fast polarity conversion algorithm (FPCA) due to the low conversion efficiency of existing polarity conversion approaches. Finally, we propose an MPRM circuits area optimization approach (MAOA), which uses the FPCA and WAA-BFA to search for the best polarity corresponding to the minimum circuits area. The experimental results show that MAOA is effective and can be used as a promising EDA tool.
- Area optimization,
- Combinatorial optimization problem,
- Fast polarity conversion algorithm,
- Mixed polarity Reed–Muller,
- Bacterial foraging algorithm

FullText(HTML)

References(45)

References

[1]	H. W. Chen, X. Y. Xue, C. S. Liu, et al., “Logic gates based on neuristors made from two-dimensional materials,” Nature Electronics, vol. 4, no. 6, pp. 399–404, 2021. doi: 10.1038/s41928-021-00591-z
[2]	P. Yin, Z. Shu, Y. J. Xia, et al., “A low-area and low-power comma detection and word alignment circuits for JESD204B/C controller,” IEEE Transactions on Circuits and Systems I:Regular Papers, vol. 68, no. 7, pp. 2925–2935, 2021. doi: 10.1109/TCSI.2021.3072772
[3]	S. H. Gunther, F. Binns, D. M. Carmean, et al., “Managing the impact of increasing microprocessor power consumption,” Intel Technology Journal, vol. 5, no. 1, pp. 1–9, 2001.
[4]	M. Chen, R. R. Zheng, Y. T. Fu, et al., “An analog control strategy with multiplier-less power calculation circuit for flyback microinverter,” IEEE Transactions on Power Electronics, vol. 36, no. 8, pp. 8617–8621, 2021. doi: 10.1109/TPEL.2021.3056382
[5]	H. Liang, Y. S. Xia, L. B. Qian, et al., “Low power 3-input AND/XOR gate design,” Journal of Computer-Aided Design & Computer Graphics, vol. 27, no. 5, pp. 940–945, 2015. (in Chinese) doi: 10.3969/j.issn.1003-9775.2015.05.021
[6]	Z. X. He, L. M. Xiao, F. Gu, et al., “An efficient and fast polarity optimization approach for mixed polarity Reed-Muller logic circuits,” Frontiers of Computer Science, vol. 11, no. 4, pp. 728–742, 2017. doi: 10.1007/s11704-016-5259-2
[7]	P. J. Wang, Z. H. Wang, R. Xu, et al., “Conversion algorithm for MPRM expansion,” Journal of Semiconductors, vol. 35, no. 3, article no. 035007, 2014. doi: 10.1088/1674-4926/35/3/0350070
[8]	D. L. Bu and J. H. Jiang, “An efficient optimization algorithm for multi-output MPRM circuits with very large number of input variables,” in Proceedings of the 2014 IEEE 7th Joint International Information Technology and Artificial Intelligence Conference, Chongqing, China, pp. 228–232, 2014.
[9]	A. Das and S. N. Pradhan, “Design time temperature reduction in mixed polarity dual Reed-Muller network: A NSGA-II based approach,” Advances in Electrical and Computer Engineering, vol. 20, no. 1, pp. 99–104, 2020. doi: 10.4316/AECE.2020.01013
[10]	C. Carvalho and G. V. G. L. Neumann, “The next-to-minimal weights of binary projective Reed-Muller codes,” IEEE Transactions on Information Theory, vol. 62, no. 11, pp. 6300–6303, 2016. doi: 10.1109/TIT.2016.2611527
[11]	Z. X. He, Y. H. Pan, K. J. Wang, et al., “Area optimization for MPRM logic circuits based on improved multiple disturbances fireworks algorithm,” Applied Mathematics and Computation, vol. 399, article no. 126008, 2021. doi: 10.1016/j.amc.2021.126008
[12]	A. Das and S. N. Pradhan, “Area-power-temperature aware AND-XOR network synthesis based on shared mixed polarity Reed-Muller expansion,” International Journal of Intelligent Systems and Applications, no. IJISA, pp. 35–46, 2018. doi: 10.5815/ijisa.2018.12.04
[13]	X. Wang, R. Zhang, W. K. Wang, et al. , “Polarity searching for MPRM logic circuit based on improved adaptive genetic algorithm, ” in Proceedings of the 2015 IEEE 12th Intl Conf on Ubiquitous Intelligence and Computing and 2015 IEEE 12th Intl Conf on Autonomic and Trusted Computing and 2015 IEEE 15th Intl Conf on Scalable Computing and Communications and Its Associated Workshops, Beijing, China, pp. 1354–1358, 2015.
[14]	Y. H. Zhou, Z. X. He, T. Wang, et al., “Area and power optimization approach for mixed polarity Reed-Muller logic circuits based on multi-strategy bacterial foraging algorithm,” Applied Soft Computing, vol. 130, article no. 109720, 2022. doi: 10.1016/j.asoc.2022.109720
[15]	Z. X. He, L. M. Xiao, Z. S. Huo, et al., “Fast minimization of fixed polarity Reed-Muller expressions,” IEEE Access, vol. 7, pp. 24843–24851, 2019. doi: 10.1109/ACCESS.2019.2899035
[16]	M. H. A. Khan, “An ASIC architecture for generating optimum mixed polarity Reed-Muller expression,” Engineering Letters, vol. 13, no. 3, pp. 236–243, 2006.
[17]	H. Z. Yu, P. J. Wang, D. S. Wang, et al., “Discrete ternary particle swarm optimization for area optimization of MPRM circuits,” Journal of Semiconductors, vol. 34, no. 2, article no. 025011, 2013. doi: 10.1088/1674-4926/34/2/025011
[18]	A. Das, Y. C. Hareesh, and S. N. Pradhan, “NSGA-II based thermal-aware mixed polarity dual Reed-Muller network synthesis using parallel tabular technique,” Journal of Circuits, Systems and Computers, vol. 29, no. 15, article no. 020008, 2020. doi: 10.1142/S021812662020008X
[19]	R. Drechsler, M. Theobald, and B. Becker, “Fast OFDD-based minimization of fixed polarity Reed-Muller expressions,” IEEE Transactions on Computers, vol. 45, no. 11, pp. 1294–1299, 1996. doi: 10.1109/12.544485
[20]	R. Drechsler, B. Becker, and N. Drechsler, “Genetic algorithm for minimisation of fixed polarity Reed-Muller expressions,” IEE Proceedings-Computers and Digital Techniques, vol. 147, no. 5, pp. 349–353, 2000. doi: 10.1049/ip-cdt:20000743
[21]	U. Kalay, D. V. Hall, and M. A. Perkowski, “A minimal universal test set for self-test of EXOR-sum-of-products circuits,” IEEE Transactions on Computers, vol. 49, no. 3, pp. 267–276, 2000. doi: 10.1109/12.841130
[22]	B. A. Al Jassani, N. Urquhart, and A. E. A. Almaini, “Manipulation and optimisation techniques for Boolean logic,” IET Computers & Digital Techniques, vol. 4, no. 3, pp. 227–239, 2010. doi: 10.1049/iet-cdt.2009.0007
[23]	E. Zaitseva, V. Levashenko, I. Lukyanchuk, et al., “Application of generalized Reed–Muller expression for development of non-binary circuits,” Electronics, vol. 9, no. 1, article no. 12, 2020. doi: 10.3390/electronics9010012
[24]	Y. H. Zhou, Z. X. He, C. Chen, et al., “An efficient power optimization approach for fixed polarity Reed-Muller logic circuits based on metaheuristic optimization algorithm,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 41, no. 12, pp. 5380–5393, 2022. doi: 10.1109/TCAD.2022.3149720
[25]	C. F. Liu, J. F. Wang, and Y. J. Y. T. Leung, “Integrated bacteria foraging algorithm for cellular manufacturing in supply chain considering facility transfer and production planning,” Applied Soft Computing, vol. 62, pp. 602–618, 2018. doi: 10.1016/j.asoc.2017.10.034
[26]	H. Y. Cai, L. Q. Ran, L. D. Zou, et al., “Heuristic hybrid bacterial foraging algorithm for the pose detection of backlight units,” Automatic Control and Computer Sciences, vol. 54, no. 3, pp. 229–237, 2020. doi: 10.3103/S0146411620030025
[27]	S. Das, S. Dasgupta, A. Biswas, et al., “On stability of the chemotactic dynamics in bacterial-foraging optimization algorithm,” IEEE Transactions on Systems, Man, and Cybernetics - Part A:Systems and Humans, vol. 39, no. 3, pp. 670–679, 2009. doi: 10.1109/TSMCA.2008.2011474
[28]	F. L. Ye, C. Y. Lee, Z. J. Lee, et al., “Incorporating particle swarm optimization into improved bacterial foraging optimization algorithm applied to classify imbalanced data,” Symmetry, vol. 12, no. 2, article no. 229, 2020. doi: 10.3390/sym12020229
[29]	C. Zhang, Y. W. Yu, Y. F. Wang, et al., “Takagi-Sugeno fuzzy neural network hysteresis modeling for magnetic shape memory alloy actuator based on modified bacteria foraging algorithm,” International Journal of Fuzzy Systems, vol. 22, no. 4, pp. 1314–1329, 2020. doi: 10.1007/s40815-020-00826-9
[30]	Y. Liu, L. W. Tian, and L. N. Fan, “The hybrid bacterial foraging algorithm based on many-objective optimizer,” Saudi Journal of Biological Sciences, vol. 27, no. 12, pp. 3743–3752, 2020. doi: 10.1016/j.sjbs.2020.08.021
[31]	J. J. Hu, N. F. Jin, P. Li, et al., “An improved bacterial foraging algorithm for multi-modal problems,” Journal of Physics:Conference Series, vol. 1631, article no. 012069, 2020. doi: 10.1088/1742-6596/1631/1/012069
[32]	W. Shao and Y. J. Zuo, “Computing the halfspace depth with multiple try algorithm and simulated annealing algorithm,” Computational Statistics, vol. 35, no. 1, pp. 203–226, 2020. doi: 10.1007/s00180-019-00906-x
[33]	T. Wang, Y. L. Zhang, N. N. Xiong, et al., “An effective edge-intelligent service placement technology for 5g-and-beyond industrial IoT,” IEEE Transactions on Industrial Informatics, vol. 18, no. 6, pp. 4148–4157, 2022. doi: 10.1109/TII.2021.3114300
[34]	Z. Shen, Q. H. Yang, and H. Jiang, “Multichannel neighbor discovery in Bluetooth low energy networks: Modeling and performance analysis,” IEEE Transactions on Mobile Computing, vol. 22, no. 4, pp. 2262–2280, 2023. doi: 10.1109/TMC.2021.3113349
[35]	F. S. Makri, Z. M. Psillakis, and A. N. Arapis, “On the concentration of runs of ones of length exceeding a threshold in a Markov chain,” Journal of Applied Statistics, vol. 46, no. 1, pp. 85–100, 2019. doi: 10.1080/02664763.2018.1455815
[36]	M. Tripathi, L. K. Singh, S. Singh, et al., “A comparative study on reliability analysis methods for safety critical systems using petri-nets and dynamic flowgraph methodology: A case study of nuclear power plant,” IEEE Transactions on Reliability, vol. 71, no. 2, pp. 564–578, 2022. doi: 10.1109/TR.2021.3109059
[37]	I. A. W. Abdul Razak, I. Z. Abidin, Y. K. Siah, et al., “An hour ahead electricity price forecasting with least square support vector machine and bacterial foraging optimization algorithm,” The Indonesian Journal of Electrical Engineering and Computer Science, no. IJEECS, pp. 748–755, 2018. doi: 10.11591/ijeecs.v10.i2.pp748-755
[38]	M. A. Awadallah, “Variations of the bacterial foraging algorithm for the extraction of PV module parameters from nameplate data,” Energy Conversion and Management, vol. 113, pp. 312–320, 2016. doi: 10.1016/j.enconman.2016.01.071
[39]	D. M. Xiao, Y. Wang, K. F. He, et al., “A harmonic suppression method of variable frequency drive based on bacterial foraging algorithm,” International Journal of Computing Science and Mathematics, vol. 7, no. 1, pp. 76–86, 2016. doi: 10.1504/IJCSM.2016.076043
[40]	B. Subudhi and R. Pradhan, “Bacterial foraging optimization approach to parameter extraction of a photovoltaic module,” IEEE Transactions on Sustainable Energy, vol. 9, no. 1, pp. 381–389, 2018. doi: 10.1109/TSTE.2017.2736060
[41]	J. Yi, D. Huang, S. Y. Fu, et al., “Multi-objective bacterial foraging optimization algorithm based on parallel cell entropy for aluminum electrolysis production process,” IEEE Transactions on Industrial Electronics, vol. 63, no. 4, pp. 2488–2500, 2016. doi: 10.1109/TIE.2015.2510977
[42]	M. A. Sahib, A. R. Abdulnabi, and M. A. Mohammed, “Improving bacterial foraging algorithm using non-uniform elimination-dispersal probability distribution,” Alexandria Engineering Journal, vol. 57, no. 4, pp. 3341–3349, 2018. doi: 10.1016/j.aej.2017.12.010
[43]	P. Sindhuja and P. Ramamoorthy, “An improved fuzzy enabled optimal multipath routing for wireless sensor network,” Cluster Computing, vol. 22, no. 5, pp. 11689–11697, 2019. doi: 10.1007/s10586-017-1452-9
[44]	D. M. Zambrano Zambrano, D. Vélez, Y. Daza, et al., “Parametric analysis of BFOA for minimization problems using a benchmark function,” Enfoque UTE, vol. 10, no. 3, pp. 67–80, 2019. doi: 10.29019/enfoque.v10n3.490
[45]	S. Yang, “Logic synthesis and optimization benchmarks user guide version 3.0, ” in Proceedings of 1989 MCNC International Workshop on Logic Synthesis, pp. 1–44, 1991. (查阅网上资料, 未找到出版地信息, 请补充)