Квантование матриц модели Изинга для комбинаторной оптимизации на RISC-V с использованием Lichee Pi 4A
Александр Михайлович БРАТЕНКОВ,
Надежда Олеговна СТЕПИНА,
Игорь Валерьевич НИКИФОРОВ,
Ольга Андреевна ЮСУПОВА https://doi.org/10.15514/ISPRAS-2026-38(4)-23
Аннотация
В работе рассматривается проблема низкой эффективности программной реализации алгоритмов комбинаторной оптимизации на RISC-V процессорах. Основное препятствие – квадратичный рост матрицы взаимодействия модели Изинга, который при использовании чисел с плавающей точкой двойной точности приводит к высокому уровню кэш-промахов и падению производительности. Цель исследования – повышение эффективности решения комбинаторных задач на RISC-V платформе за счёт уменьшения разрядности матрицы с использованием методов квантования. Предложенный подход реализует три класса методов округления: простое, стохастическое и восемь схем диффузионного округления. Новизна работы заключается в систематическом сравнении этих методов на трёх классических NP-трудных задачах, а также в анализе их эффективности в зависимости от структуры задачи и доступной разрядности данных. Разработан программный прототип для платы Lichee Pi 4A, интегрирующий квантование матрицы с алгоритмом имитации отжига, который адаптирован для целочисленных типов данных. Эксперименты проведены на трёх NP-трудных задачах: коммивояжёра, о рюкзаке и максимального разреза графа, с разрядностью от 2 до 16 бит. Результаты показывают, что эффективность квантования зависит от структуры задачи. Для задачи максимального разреза диффузионное округление улучшает качество решения на 10% по сравнению с неквантованной матрицей. Для задачи о рюкзаке диффузионные методы не дают преимущества перед простым округлением, а стохастическое требует не менее 8 бит. Для задачи коммивояжёра диффузионное округление эффективно только на 2 битах. Оценка производительности на Lichee Pi 4A показывает, что переход с матрицы двойной точности на 8-битную целочисленную сокращает время выполнения в 3,6–4,7 раза и снижает долю кэш-промахов с 2,64% до 0,13–0,25%. Наилучшая производительность достигается с матрицей int8 и аккумулятором int32. Результаты позволяют решать задачи комбинаторной оптимизации большего размера на RISC-V системах с ограниченными ресурсами.
Об авторах
Александр Михайлович БРАТЕНКОВ
Санкт-Петербургский политехнический университет Петра Великого
Россия
Россия
Бакалавр высшей школы программной инженерии Санкт-Петербургского политехнического университета Петра Великого по специальности 09.04.03 – «Технология разработки и сопровождения качественного программного продукта». Область научных интересов – архитектура RISC-V, высокопроизводительные вычисления, низкоуровневое программирование.
Надежда Олеговна СТЕПИНА
Санкт-Петербургский политехнический университет Петра Великого
Россия
Россия
Ассистент высшей школы программной инженерии Санкт-Петербургского политехнического университета Петра Великого. В 2023 году окончила Санкт-Петербургский государственный политехнический университет по специальности «Программная инженерия». В 2024 году стала аспирантом по специальности 2.3.5 – «Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей». Область научных интересов – разработка программного обеспечения, машинное обучение, высокопроизводительные вычисления, IoT и embedded-системы.
Игорь Валерьевич НИКИФОРОВ
Санкт-Петербургский политехнический университет Петра Великого
Россия
Россия
Кандидат технических наук по специальности «Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей», доцент высшей школы программной инженерии Санкт-Петербургского политехнического университета Петра Великого. Автор 100 научных публикаций. Область научных интересов – разработка программного обеспечения, имитационное моделирование, аналитика больших данных, распределенные вычисления.
Ольга Андреевна ЮСУПОВА
Санкт-Петербургский политехнический университет Петра Великого
Россия
Россия
Старший преподаватель высшей школы программной инженерии Санкт-Петербургского политехнического университета Петра Великого. В 2009 году окончила Санкт-Петербургский государственный политехнический университет по направлению «Информатика и вычислительная техника». Имеет второе высшее образование в области экономики по специальности – «Прикладная информатика в экономике». Является автором учебных пособий, научных статей. Сфера профессиональных интересов охватывает математическое моделирование, системный анализ, тестирование и верификацию программного обеспечения.
Список литературы
1. Cui E., Li T., Wei Q. RISC-V instruction set architecture extensions: A survey. IEEE Access, 2023, vol. 11, pp. 24696-24711. DOI: 10.1109/ACCESS.2023.3246491.
2. Cherepanov N.I., Stepina N.O., Nikiforov I.V. Improving image analysis and processing performance on the RISC-V platform with Lichee Pi 4A. Trudy ISP RAN/Proc. ISP RAS, 2025, vol. 37, issue 5, pp. 157-172. DOI: 10.15514/ISPRAS-2025-37(5)-12.
3. Volokitin V.D., Vasiliev E.P., Kozinov E.A., Kustikova V.D., Liniov A.V., Rodimkov Y.A., Sysoyev A.V., Meyerov I.B. Vectorization of gradient boosting of decision trees prediction in the CatBoost library for RISC-V processors. Lobachevskii Journal of Mathematics, 2024, vol. 45, no. 1, pp. 130-142. DOI: 10.1134/S1995080224010530.
4. Pirova A., Vodeneeva A., Kovalev K., Ustinov A., Kozinov E., Liniov A., Volokitin V., Meyerov I. Performance optimization of BLAS algorithms with band matrices for RISC-V processors. Future Generation Computer Systems, vol. 174, 2026, 107936, 12 p. DOI: 10.1016/j.future.2025.107936.
5. Arianyan E., Gholipour N., Maleki D., Ghorbani N., Sepahvand A., Goudarzi P. A Systematic Review and Classification of HPC-Related Emerging Computing Technologies. Electronics, 2025, vol. 14, no. 12, 2476. DOI: 10.3390/electronics14122476.
6. Bourgeois N., Escoffier B., Paschos V. Th. An Introduction to Exponential Time Exact Algorithms for Solving NP-Hard Problems. In Mahjoub R. A. (ed.) Progress in Combinatorial Optimization. London: ISTE; Hoboken, NJ: John Wiley & Sons, 2012, pp. 443-468. Zbl 1242.90188.
7. Yang X.-S. Nature-Inspired Metaheuristic Algorithms. 2nd ed. Luniver Press, 2010. 160 p.
8. Gao Y., Chen G., Qi L., et al. Photonic Ising machines for combinatorial optimization problems. Applied Physics Reviews, 2024, vol. 11. DOI: 10.1063/5.0216656.
9. Mohseni N., McMahon P.L., Byrnes T. Ising machines as hardware solvers of combinatorial optimization problems. Nature Reviews Physics, 2022, vol. 4, pp. 363-379. DOI: 10.1038/s42254-022-00440-8.
10. Yamamoto K., Kawamura K., Ando K., et al. STATICA: A 512-spin 0.25M-weight annealing processor with an all-spin-updates-at-once architecture for combinatorial optimization with complete spin-spin interactions. IEEE Journal of Solid-State Circuits, 2021, vol. 56, no. 1, pp. 165-178. DOI: 10.1109/JSSC.2020.3027702.
11. Chen J., Yu Z., Zhu X. A 28 nm Ising machine with adaptive majority voter and reduction algorithms for high-performance combinatorial optimization. Microelectronics Journal, 2025, vol. 157. DOI: 10.1016/j.mejo.2025.106589.
12. Sato Y., Konoshima M., Tamura H., Ohkubo J. Characterization of Locality in Spin States and Forced Moves for Optimizations. Journal of the Physical Society of Japan, 2024, vol. 93, 044802. DOI: 10.7566/JPSJ.93.044802.
13. Oku D., Tawada M., Tanaka S., Togawa N. How to reduce the bitwidth of an Ising model by adding auxiliary spins. IEEE Transactions on Computers, 2022, vol. 71, no. 1, pp. 223-234. DOI: 10.1109/TC.2020.3045112.
14. Cui D., Kawahara T. Proposal and validation of annealing-processor-calculation method using error-diffusion rounded interaction matrix. 2024 IEEE Asia Pacific Conference on Circuits and Systems (APCCAS), Taipei, Taiwan, 2024, pp. 50-54. DOI: 10.1109/APCCAS62557.2024.00017.
15. Cui D., Megumi T., Endo A., Kawahara T. Dual scalable annealing processing system that scales number of spins and interaction bit width simultaneously. IEEE Access, 2025, vol. 13, pp. 52592-52606. DOI: 10.1109/ACCESS.2025.3553542.
16. Щербина О.А. Метаэвристические алгоритмы для задач комбинаторной оптимизации (обзор). Таврический вестник информатики и математики, 2014, № 1 (24), стр. 2-17. / Shcherbina O. A. Metaheuristic algorithms for combinatorial optimization problems (review). Tavricheskiy Vestnik Informatiki i Matematiki, 2014, no. 1 (24), pp. 2-17 (in Russian).
17. Lucas A. Ising formulations of many NP problems. Frontiers in Physics, 2014, vol. 2, article 5, 27 p. DOI: 10.3389/fphy.2014.00005.
18. Pardalos P.M., Du D.-Z., Graham R.L. (eds.) Handbook of Combinatorial Optimization. 2nd ed. New York: Springer, 2013. 3409 p.
19. Korte B., Vygen J. Combinatorial Optimization: Theory and Algorithms. 6th ed. Berlin: Springer, 2018. (Algorithms and Combinatorics, vol. 21). DOI: 10.1007/978-3-662-56039-6.
20. Pathria R.K., Beale P.D. Statistical Mechanics. 4th ed. Academic Press, 2022. 944 p.
21. Mohseni N., McMahon P.L., Byrnes T. Ising machines as hardware solvers of combinatorial optimization problems. Nature Reviews Physics, 2022, vol. 4, pp. 363-379. DOI: 10.1038/s42254-022-00440-8.
22. Kirkpatrick S., Gelatt C.D., Vecchi M.P. Optimization by simulated annealing. Science, 1983, vol. 220, no. 4598, pp. 671-680. DOI: 10.1126/science.220.4598.671.
23. Hajek B. Cooling schedules for optimal annealing. Mathematics of Operations Research, 1988, vol. 13, no. 2, pp. 311-329. DOI: 10.1287/moor.13.2.311.
24. Metropolis N., Rosenbluth A.W., Rosenbluth M.N., Teller A.H., Teller E. Equation of state calculations by fast computing machines. The Journal of Chemical Physics, 1953, vol. 21, no. 6, pp. 1087-1092. DOI: 10.1063/1.1699114.
25. Ferreira A.L.C., Toral R. Projected single-spin-flip dynamics in the Ising model. Physical Review E, 2007, vol. 76, no. 1, pp. 1-10. DOI: 10.1103/PhysRevE.76.011117.
26. Garofalo A., et al. A 3 TOPS/W RISC-V parallel cluster for inference of fine-grain mixed-precision quantized neural networks. 2023 IEEE Computer Society Annual Symposium on VLSI (ISVLSI), 2023. DOI: 10.1109/ISVLSI59297.2023.00045.
27. Martínez H., Castelló A., Igual F. D., Quintana-Ortí E.S. The Cambrian explosion of mixed-precision matrix multiplication for quantized deep learning inference. arXiv preprint, 2025. DOI: 10.48550/arXiv.2506.11728.
28. Floyd R. W., Steinberg L. An adaptive algorithm for spatial grey scale. Journal of the Society for Information Display, 1976, vol. 17, pp. 75-77.
29. Gupta S., Agrawal A., Gopalakrishnan K., Narayanan P. Deep learning with limited numerical precision. Proceedings of the 32nd International Conference on Machine Learning (ICML), 2015, pp. 1737-1746.
30. Armeniakos G., Maras A., Xydis S., Soudris D. MaRVIn: A cross-layer mixed-precision RISC-V framework for DNN inference, from ISA extension to hardware acceleration. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2025. DOI: 10.48550/arXiv.2509.15187.
31. Quantizing Ising model matrices for combinatorial optimization on RISC-V with Lichee Pi 4A. GitLab repository. Available at: https://gitlab.com/risc-v-spbstu/the_interaction_matrix_with_edm/, accessed 01.06.2026.
Рецензия
Для цитирования:
БРАТЕНКОВ А.М., СТЕПИНА Н.О., НИКИФОРОВ И.В., ЮСУПОВА О.А. Квантование матриц модели Изинга для комбинаторной оптимизации на RISC-V с использованием Lichee Pi 4A. Труды Института системного программирования РАН. 2026;38(4):143-160. https://doi.org/10.15514/ISPRAS-2026-38(4)-23
For citation:
BRATENKOV A.M., STEPINA N.O., NIKIFOROV I.V., YUSUPOVA O.A. Quantizing Ising Model Matrices for Combinatorial Optimization on RISC-V with Lichee Pi 4A. Proceedings of the Institute for System Programming of the RAS (Proceedings of ISP RAS). 2026;38(4):143-160. https://doi.org/10.15514/ISPRAS-2026-38(4)-23
Послать статью по эл. почте 