Обучение с подкреплением  в задаче синтеза мажоритарных схем

Sergey Isaevich Gurov; Dmitry Vitalievich Zolotarev; Alexander Ilyich Samburskiy

doi:10.25559/SITITO.17.202102.295-307

Sergey Isaevich Gurov Московский государственный университет имени М.В. Ломоносова http://orcid.org/0000-0001-5486-1357
Dmitry Vitalievich Zolotarev Московский государственный университет имени М.В. Ломоносова http://orcid.org/0000-0002-5349-2147
Alexander Ilyich Samburskiy Московский государственный университет имени М.В. Ломоносова http://orcid.org/0000-0003-1188-0229

DOI: https://doi.org/10.25559/SITITO.17.202102.295-307

Аннотация

В статье изложен подход к синтезу комбинационно логических схем с применением искусственных нейронных сетей (ИНС). Излагаемый метод ориентирован на использование перспективного базиса, использующего функцию большинства (булева функция от трёх аргументов, которая принимает значение "истина", если истинны хотя бы два из её входов). Такой выбор обусловлен возникающими нанотехнологиями, в которых представление элемента большинства наиболее осуществляется особенно просто.
Класс применяемых ИНС – глубокие сети с подкреплением. Такие сети активно изучаются и применяются в последнее время. Известны примеры их эффективного использования для автоматической оптимизации логических схем.
Предложенный в статье оригинальный синтеза метод с упрощения схем, реализующих разложение Шеннона по всем переменным соответствующей функции алгебры логики (ФАЛ). На больших схемах становится существенным использование некоторых простых, но действенных приёмов обучения агентов глубокой ИНС с подкреплением. Это позволяет распределить вычисления на несколько независимых подзадач, каждая из которых исследуется и выполняется агентами проще и быстрее. Описаны два алгоритма обучения с подкреплением для упрощения схем. Они обеспечивают решение конфликта Exploration-Exploitation, заключающегося в противоречии между исследованием среды для поиска оптимального эпизода и использованием информации об эпизоде, считающимся оптимальным на текущий момент времени. Представлены зависимостей параметров синтезированных схем от числа n = 3, …, 10 переменных ФАЛ и количества эпизодов обучения сети.

Сведения об авторах

Sergey Isaevich Gurov, Московский государственный университет имени М.В. Ломоносова

старший научный сотрудник, доцент кафедры математических методов прогнозирования, факультет вычислительной математики и кибернетики, кандидат физико-математических наук, доцент

Dmitry Vitalievich Zolotarev, Московский государственный университет имени М.В. Ломоносова

студент факультета вычислительной математики и кибернетики

Alexander Ilyich Samburskiy, Московский государственный университет имени М.В. Ломоносова

студент факультета вычислительной математики и кибернетики

Литература

1. Soeken M., Amarú L.G., Gaillardon P.-E., De Micheli G. Exact synthesis of majority inverter graphs and its applications. IEEE Transactions on Computer Aided Design of Integrated Circuits and Systems. 2017; 36(11):1842-1855. (In Eng.) DOI: https://doi.org/10.1109/TCAD.2017.2664059
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