Reinforcement Learning in the Problem of Synthesis of Majority Schemes
Abstract
The article presents an approach to the synthesis of combinational-logic circuits using artificial neural networks (ANNs). The presented method is focused on the use of a perspective basis using the majority function (a Boolean function of three arguments that takes the value "true" if at least two of its inputs are true). This choice is based on emerging nanotechnologies, where the majority element is most easily represented.
The class of applied ANNs is deep networks with reinforcement. Such networks have been actively studied and applied in recent years. There are examples of their effective use for automatic logic circuits optimization.
The original synthesis method proposed in the article with the simplification of circuits that implement the Shannon expansion in all variables of the corresponding function of the logic algebra (FLA). On large schemes, it becomes essential to use some simple but effective techniques for training deep ANN agents with reinforcement. This allows you to distribute calculations into several independent subtasks, each of which is explored and makes performing by agents quicker and easier. Two reinforcement learning algorithms for simplifying schemas are described. They provide a solution to the Exploration-Exploitation conflict, which is the contradiction between exploring the environment to find the optimal episode and using information about the episode considered optimal at the current time. The dependences of the parameters of the synthesized circuits on the number n = 3, …, 10 of FAL variables and the number of network training episodes are presented.
References
2. Cai R., Chen O., Ren A., Liu N., Ding C., Yoshikawa N., Wang Y. A Majority Logic Synthesis Framework for Adiabatic Quantum-Flux-Parametron Superconducting Circuits. Proceedings of the 2019 on Great Lakes Symposium on VLSI (GLSVLSI'19). Association for Computing Machinery, NY, USA; 2019. p. 189-194. (In Eng.) DOI: https://doi.org/10.1145/3299874.3317980
3. Balasubramanian P., Naayagi R.T. Mathematical estimation of logical masking capability of majority/minority gates used in nanoelectronic circuits. 2017 International Conference on Circuits, System and Simulation (ICCSS). IEEE Press, London, UK; 2017. p. 18‑23. (In Eng.) DOI: https://doi.org/10.1109/CIRSYSSIM.2017.8023173
4. Amarú L., Gaillardon P.E., De Micheli G. Majority-Inverter Graph: A Novel Data-Structure and Algorithms for Efficient Logic Optimization. Proceedings of the 51st Annual Design Automation Conference (DAC'14). Association for Computing Machinery, New York, NY, USA; 2014. p. 1-6. (In Eng.) DOI: https://doi.org/10.1145/2593069.2593158
5. Gurov S.I., Zolotarev D.V., Samburskiy A.I. Iskusstvennye nejronnye seti i sintez logicheskih shem [Artificial neural networks and synthesis of logic circuits]. In: Ed. by A. S. Krylov. Applied Mathematics and Computer Science: Proceedings of the CMC MSU Faculty. MAKS Press, Moscow; 2021. No. 68. p. 75-87. Available at: https://www.elibrary.ru/item.asp?id=47319217 (accessed 18.03.2021). (In Russ.)
6. Devraj A.M., Bušić A., Meyn S. Fundamental Design Principles for Reinforcement Learning Algorithms. In: Ed. by K. G. Vamvoudakis, Y. Wan, F. L. Lewis, D. Cansever. Handbook of Reinforcement Learning and Control. Studies in Systems, Decision and Control. 2021; 325:75-137. Springer, Cham. (In Eng.) DOI: https://doi.org/10.1007/978-3-030-60990-0_4
7. Vafashoar R., Morshedlou H., Rezvanian A., Meybodi M.R. Applications of Cellular Learning Automata and Reinforcement Learning in Global Optimization. Cellular Learning Automata: Theory and Applications. Studies in Systems, Decision and Control. 2021; 307:157-224. Springer, Cham. (In Eng.) DOI: https://doi.org/10.1007/978-3-030-53141-6_4
8. Yonekura K., Hattori H. Framework for design optimization using deep reinforcement learning. Structural and Multidisciplinary Optimization. 2019; 60(4):1709-1713. (In Eng.) DOI: https://doi.org/10.1007/s00158-019-02276-w
9. Yan D., Weng J., Huang S., Li C., Zhou Y., Su H., Zhu J. Deep reinforcement learning with credit assignment for combinatorial optimization. Pattern Recognition. 2022; 124:108466. (In Eng.) DOI: https://doi.org/10.1016/j.patcog.2021.108466
10. Butyrlagin N.V., Chernov N.I., Prokopenko N.N., Yugay V. Logical Synthesis and Circuitry of Digital Current Circuits: Polynomial Approach. 2019 27th Telecommunications Forum (TELFOR). IEEE Press, Belgrade, Serbia; 2019. p. 1-4. (In Eng.) DOI: https://doi.org/10.1109/TELFOR48224.2019.8971153
11. Gurov S.I. Majority Algebra for the Synthesis of Combinational Logic Schemes. Review. Taurida Journal of Computer Science Theory and Mathematics. 2020; (2):39-60. Available at: https://www.elibrary.ru/item.asp?id=44600613 (accessed 18.03.2021). (In Russ., abstract in Eng.)
12. Gurov S.I. Review of Works on the use of Majority Boolean Algebra for the Synthesis of Combinational Logic Schemes. Taurida Journal of Computer Science Theory and Mathematics. 2020; (3):59-76. Available at: https://www.elibrary.ru/item.asp?id=46301092 (accessed 18.03.2021). (In Russ., abstract in Eng.)
13. Amarú L., Gaillardon P.-E., Chattopadhyay A., De Micheli G. A Sound and Complete Axiomatization of Majority-n Logic. IEEE Transactions on Computers. 2016; 65(9):2889-2895. (In Eng.) DOI: https://doi.org/10.1109/TC.2015.2506566
14. Chua L., Roska T. The CNN Paradigm. IEEE Transactions on Circuits and Systems I: Fundamental Theory and Applications. 1993; 40(3):147‑156. (In Eng.) DOI: https://doi.org/10.1109/81.222795
15. Haaswijk W., Collins E., Seguin B., Soeken M., Kaplan F., Susstrunk S., De Micheli G. Deep Learning for Logic Optimization Algorithms. 2018 IEEE International Symposium on Circuits and Systems (ISCAS). IEEE Press, Florence, Italy; 2018. p. 1‑4. (In Eng.) DOI: https://doi.org/10.1109/ISCAS.2018.8351885
16. Nair V., Hinton G.E. Rectified Linear Units Improve Restricted Boltzmann Machines. Proceedings of the 27th International Conference on Machine Learning (ICML-10). Haifa, Israel; 2010. p. 807‑814. Available at: https://icml.cc/Conferences/2010/papers/432.pdf (accessed 18.03.2021). (In Eng.)
17. Mazyavkina N., Sviridov S., Ivanov S., Burnaev E. Reinforcement learning for combinatorial optimization: A survey. Computers & Operations Research. 2021; 134:105400. (In Eng.) DOI: https://doi.org/10.1016/j.cor.2021.105400
18. Möller F.J.D., Bernardino H.S., Gonçalves L.B., Soares S.S.R.F. A Reinforcement Learning Based Adaptive Mutation for Cartesian Genetic Programming Applied to the Design of Combinational Logic Circuits. In: Ed. by R. Cerri, R. C. Prati. Intelligent Systems. BRACIS 2020. Lecture Notes in Computer Science. 2020; 12320:18-32. Springer, Cham. (In Eng.) DOI: https://doi.org/10.1007/978-3-030-61380-8_2
19. Zhu K., Liu M., Chen H., Zhao Z., Pan D. Exploring Logic Optimizations with Reinforcement Learning and Graph Convolutional Network. Proceedings of the 2020 ACM/IEEE Workshop on Machine Learning for CAD (MLCAD '20). Association for Computing Machinery, New York, NY, USA; 2020. p. 145-150. (In Eng.) DOI: https://doi.org/10.1145/3380446.3430622
20. Silver D., Huang, A., Maddison, C., et al. Mastering the game of Go with deep neural networks and tree search. Nature. 2016; 529:484-489. (In Eng.) DOI: https://doi.org/10.1038/nature16961
21. Mnih V., Kavukcuoglu K., Silver D., et al. Human-level control through deep reinforcement learning. Nature. 2015; 518:529-533. (In Eng.) DOI: https://doi.org/10.1038/nature14236
22. Machine Learning Proceedings 1991. In: Ed. by L. A. Birnbaum, G. C. Collins. Proceedings of the Eighth International Conference. Morgan Kaufmann, Evanston, Illinois; 1991. 661 p. (In Eng.) DOI: https://doi.org/10.1016/C2009-0-27661-6
23. Brudermueller T., Shung D.L., Stanley A.J., Stegmaier J., Krishnaswamy S. Making Logic Learnable With Neural Networks. arXiv:2002.03847. 2020. Available at: https://arxiv.org/abs/2002.03847 (accessed 18.03.2021). (In Eng.)
24. Somayaji N.S.K., Hu H., Li P. Prioritized Reinforcement Learning for Analog Circuit Optimization With Design Knowledge. 2021 58th ACM/IEEE Design Automation Conference (DAC). IEEE Press, San Francisco, CA, USA; 2021. p. 1231-1236. (In Eng.) DOI: https://doi.org/10.1109/DAC18074.2021.9586189
25. Coello C.A., Zavala R.L.G., García B.M., Aguirre A.H. Ant Colony System for the Design of Combinational Logic Circuits. In: Ed. by J. Miller, A. Thompson, P. Thomson, T. C. Fogarty. Evolvable Systems: From Biology to Hardware. ICES 2000. Lecture Notes in Computer Science. 2000; 1801:21-30. Springer, Berlin, Heidelberg. (In Eng.) DOI: https://doi.org/10.1007/3-540-46406-9_3
This work is licensed under a Creative Commons Attribution 4.0 International License.
Publication policy of the journal is based on traditional ethical principles of the Russian scientific periodicals and is built in terms of ethical norms of editors and publishers work stated in Code of Conduct and Best Practice Guidelines for Journal Editors and Code of Conduct for Journal Publishers, developed by the Committee on Publication Ethics (COPE). In the course of publishing editorial board of the journal is led by international rules for copyright protection, statutory regulations of the Russian Federation as well as international standards of publishing.
Authors publishing articles in this journal agree to the following: They retain copyright and grant the journal right of first publication of the work, which is automatically licensed under the Creative Commons Attribution License (CC BY license). Users can use, reuse and build upon the material published in this journal provided that such uses are fully attributed.
