2025 №4(69)

С О Д Е Р Ж А Н И Е

Бакулина М. П. Эффективный алгоритм сжатия с помощью преобразования данных словарного типа
Бредихин С. В., Щербакова Н. Г. Выявление сообществ в мультиплексной сети авторов научного журнала
Герб А. Р., Девятых Е. Е., Омарова Г. А . Сравнение методов графовой редукции первого, второго и третьего поколения в моделях химической кинетики
Монахов О. Г., Монахова Э. А. Генерация многоуровневых регулярных сетей на основе операции композиции модифицированных хордальных графов с использованием больших языковых моделей
Усова М. А., Лебедев И. Г., Штанюк A. A., Баркалов К. А. Алгоритм глобальной оптимизации для настройки гиперпараметров методов машинного обучения
Малышкин В. Э., Перепелкин В. А., Спирин В. А. Обеспечение автоматического конструирования программ с использованием спецвычислителей на основе концепции активных знаний в системе LuNa

М.П. Бакулина

Институт вычислительной математики и математической геофизики СО РАН, 630090, Новосибирск, Россия

ЭФФЕКТИВНЫЙ АЛГОРИТМ СЖАТИЯ С ПОМОЩЬЮ ПРЕОБРАЗОВАНИЯ ДАННЫХ СЛОВАРНОГО ТИПА

УДК 519.722
DOI: 10.24412/2073-0667-2025-4-5-10
EDN: KUQHBT

Рассматривается задача эффективного сжатия без потерь для данных словарного типа. Для таких данных алгоритм кодирования основан на использовании словаря, формируемого по тексту, поступающему для сжатия. Известно также, что предварительная обработка данных, например, BWT-преобразование, может улучшить коэффициент сжатия текста. В данной работе предлагается эффективный алгоритм сжатия данных словарного типа, основанный на модификации BWT-преобразования. Приведены экспериментальные результаты, подтверждающие увеличение степени сжатия данных предложенным алгоритмом по сравнению с классическим архиватором.

Ключевые слова: словарь, BWT-преобразование, степень сжатия, время кодирования, архиватор.

Исследования выполнены в рамках государственного задания ИВМиМГ СО РАН 0251-2022-0005.

Список литературы

Burrows M. A block sorting lossless data compression algorithm // M. Burrows, D. Wheeler. Technical Report 124, Digital Equipment Corporation, 1994. 18 pages.
Рябко Б. Я. Data compression by means of a «book stack» // Problems of Information Transmission. 1980, V. 16: (4). P. 265–269.\
Хмелев Д. В. Преобразование Барроуза-Уилера, массив суффиксов и сжатие словарей // Все о сжатии данных, изображений и видео: сайт. [Эл. Рес.]: http://compression.ru/download/ articles/bwt/khmelev_2003_bwt.pdf.
Bell T. C., Cleary J. H., Witten I. H. Text compression // T. C. Bell, J. H. Cleary, I. H. Witten, Prentice Hall. Englewood Cliffs, 1990. С. 318.
K¨arkk¨ainen J., Sanders P. Simple linear work suffix array construction // In 30th International Colloquium on Automata, Languages and Programming, number 2719 in LNCS. 2003. С. 943–95

Библиографическая ссылка: Бакулина М. П. Эффективный алгоритм сжатия с помощью преобразования данных словарного типа //"Проблемы информатики", 2025, № 4, с.5-11. DOI: 10.24412/2073-0667-2025-4-5-10.

С.В. Бредихин, Н.Г. Щербакова

Институт вычислительной математики и математической геофизики СО РАН, 630090, Новосибирск, Россия

ВЫЯВЛЕНИЕ СООБЩЕСТВ В МУЛЬТИПЛЕКСНОЙ СЕТИ АВТОРОВ НАУЧНОГО ЖУРНАЛА

УДК 519.177
DOI: 10.24412/2073-0667-2025-4-11-24
EDN: TWNDJO

Представлена модель мультиплексной сети, отражающая реальную схему сотрудничества авторов научного журнала. Исходные данные извлечены из XML-архива статей журнала. Модель выполнена в виде двухслойного графа, вершины которого соответствуют авторам статей, а ребра — бинарным отношениям соавторства и цитирования. Цель работы состоит в выявлении непересекающихся сообществ авторов сети и достигается в два этапа. На первом этапе сеть приводится к виду неориентированного графа, на втором к построенному графу применяются два традиционных алгоритма кластеризации, основанные на методе случайного блуждания. Выполнен вычислительный эксперимент.

Ключевые слова: мультиплексная сеть, научное сообщество, соавторство, цитирование, модульность, библиометрия.

Исследования выполнены в рамках государственного задания ИВМиМГ СО РАН (FWNM-2025-0005).

Список литературы

Barab´asi A-L., P´osfai M. Network Science. Cambridge Univ. Press. 456 p. ISBN 1107076269.
Radicchi F., Castellano C., Cecconi F., Loreto V., Parisi D. Defining and identifying communities in networks // PNAS. 2004. V. 101. P. 2658–2663. DOI: 10.1073/pnas.0400054101.
Fortunato S. Community detection in graphs // Phys. Rep. 2010. V. 486, iss. 3–5. P. 75–174. DOI: 10.1016/j.physrep.2009.11.002.
Дистель Р. Теория графов. Новосибирск: Изд-во Ин-та математики, 2002. 336 с. ISBN 5-86134-101-X.
Peel L., Larremore D. B., Clauset A. The ground truth about metadata and community detection in networks // Sci. Adv. 2017. V. 3, iss. e1602548. DOI: 10.1126/scadv.1602548.
Newman M. E. J. Modularity and community structure in networks // Proc. Natl. Acad. Sci. USA. 200 V. 103. P. 8577–8582. DOI: 10.1037/pnas.0601602103.
Newman M. E. J., Girvan M. Finding and evaluating community structure in networks // Phys. Rev. E. 2004. V. 69. 026113. DOI: 10.1103/PhysRevE.69. 026113.
Magnani M., Hanteer O., Interdonato R., Rossi L., Tagarelli A. Community Detection in Multiplex Networks // arXiv: 0911.1824. DOI:10.48550/arxiv: 0911.1824.
Interdonato R., Tagarelli A., Ienco D., Sallaberry A., Poncelet P. Node-centric community detection in multilayer networks with layer-coverage diversification bias // Proc. of the 8th Conf. on Complex Networks. 2017. P. 57–66. Springer Intern. Publ., 2017. DOI: 10.48550/arXiv.1704.03441.
Jeub L. G. S., Mahoney M. W., Mucha P. J., Porter M. A. A local perspective on community structure in multilayer networks // Network Sci. 2017. V. 5, iss. 2. P. 144–163. DOI: 48550/arXiv.1510.05185.
Kim J., Lee J-G. Community detection in multi-layer graphs: A survey // ACM SIGMOD Record. 2015. V. 44, iss. 3. P. 37–48. DOI: 10.1145/2854006.2854012.
Huang X., Chen D., Ren T., Wang D. A survey of community detection methods in multilayer networks // Data Mining and Knowledge Discovery. 2021. V. 35. P.1–45. DOI:10.1007/s10618-020-00716-6.
Mucha P. J., Richardson T., Macon K., Porter M. A., Onnela J. P. Community structure in time-dependent, multiscale, and multiplex networks // Science. 2010. V. 328, iss. 5980. P. 876–878. DOI: 10.1126/science.1184819.
De Domenico M., Lancichinetti A., Arenas A., Rosvall M. Identifying modular flows on multilayer networks reveals highly overlapping organization in interconnected systems // Phys. Review. 2015. X 5, 011027. DOI: 10.1103/PhysRevX.5. 011027.
Afsarmanesh N., Magnani M. Finding overlapping communities in multiplex networks // Proc. of the 2018 Intern. conf. on Social Informatics, 2018. DOI: 10.48550/arXiv.1602.03746.
Bianconi G. Multilayer networks. Structure and functions. Oxford. 2018. Online ISBN: 9780191815676.
Lancichinetti A., Fortunato S. Consensus clustering in complex networks // Sci. Rep. 2012. V.2. Art. num. 336. DOI: 10.1038/srep00336.
Mondragon R. J., Iacovacci J., Bianconi G. Multilink communities of multiplex networks // arXiv:1706.09011. DOI: 10.48550/arXiv.1706.09011.
De Domenico M., Sol´e-Ribalta A., Cozzo E., Kivel¨a M., Moreno Y., Porter M. A., G´omez S., Arenas A. Mathematical formulation of multilayer networks // Phys. Rev. 2013. X 3. 041022. DOI:10.1103/PhysRevX.3.041022.
Бредихин С. В., Щербакова Н. Г. Взвешенная мультиплексная сеть авторов научного журнала // Пробл. информ. 2025. № 1. С. 45–59. DOI: 10.24412/2073-0667-2025-1-45-59.
Бредихин С. В., Щербакова Н. Г. Структурные свойства мультиплексной сети авторов научного журнала // Пробл. информ. 2025. № 2. С. 8–18. DOI: 10.24412/2073-0667-2025-2-5-18.
Boccaletti S., Bianconi G., Criado R., del Genio C. I., G´omez-Garden˜es J., Romance M., Sendin˜a-Nadal I., Wang Z., Zanin M. The structure and dynamics of multilayer networks // Phys. Rep. 2014. V. 544, iss, 1. P. 1–1 DOI: 10.1016/j.physrep.2014.07.001.
Wagner S., Wagner D. Comparing clusterings — An overview. 2007. DOI: 10.5445/IR/1000011477. https://publikationen.bibliothek.kit.edu/1000011477.
Collins L. M., Dent C. W. Omega: A general formulation of the Rand index of cluster recovery suitable for non-disjoint solutions // Multivariate Behav. Res. 1988. V. 23, iss. 2. P. 231–242. DOI: 10.1207/s15327906mbr2302_6.
Murray G., Carenini G., Ng R. Using the omega index for evaluating abstractive community detection // Proc. of Workshop on Evaluation Metrics and System Comparison for Automatic Summarization, Montr´eal (Canada), 2012. Assoc. for Comput. Linguistics. P. 10–18.
Hanteer O., Rossi L. The meaning of dissimilar: An evaluation of various similarity quantification approaches used to evaluate community detection solutions // Proc. of the IEEE/ACM Intern. conf. on Advances in Social Networks Analysis and Mining, Vancouver (Canada), 2019. P. 513–518. DOI: 10.1145/3341161.3342941.
Berlingerio M., Coscia M., Giannotti F. Finding and characterizing communities in multidimensional networks // Intern. conf. on Advances in Social Networks Analysis and Mining (ASONAM). P. 490–494. IEEE Computer Society Washington, DC, USA, 2011. DOI: 10.1107/ASONAM.2011.104.
Kim J., Lee J.-G., Lim S. Differential flattening: A novel framework for community detection in multi-layer graphs // ACM Trans. on Intell. Syst. and Technol. (TIST). 2016. V. 8, iss. 2. P. 27:1–27:23. DOI: 10.1145/2898362.
De Domenico M., Nicosia V., Arenas A., Latora V. Structural reducibility of multilayer networks// Nature Communic. 2015. V. 6. 6864. DOI: 10.1038/ncomms7864.
Bianconi G. Statistical mechanics of multiplex networks: entropy and overlap // Phys. Rev. E. 2013. V. 87, iss. 6. 062806. DOI: 10.1103/PhysRevE.87.062806.
Pons P., Latapy M. Computing communities in large networks using random walks. 2006. arXiv: physics/0512106. DOI: 10.48550/arXiv.physics/0512106.
Rosvall M., Axelsson D., Bergstrom C. T. Map equation. // Eur. Phys. J. 2009. V. 178. P. 13–23. DOI: 10.1140/epjst/e2010-01179-1.

Библиографическая ссылка: Бредихин С. В., Щербакова Н. Г. Выявление сообществ в мультиплексной сети авторов научного журнала //"Проблемы информатики", 2025, № 4, с.11-24. DOI: 10.24412/2073-0667-2025-4-11-24.

А.Р. Герб, Е.Е. Девятых*, Г.А. Омарова

Институт вычислительной математики и математической геофизики СО РАН, 630090, Новосибирск, Россия
*Новосибирский Государственный Университет, 630090, Новосибирск, Россия

СРАВНЕНИЕ МЕТОДОВ ГРАФОВОЙ РЕДУКЦИИ ПЕРВОГО, ВТОРОГО И ТРЕТЬЕГО ПОКОЛЕНИЯ В МОДЕЛЯХ ХИМИЧЕСКОЙ КИНЕТИКИ

УДК 519.17+51-7
DOI: 10.24412/2073-0667-2025-4-25-37
EDN: VBFMRT

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

Ключевые слова: граф, редукция, модель химкинетики, DRG, DRGEP, PFA, GPS.

Исследование выполнено в рамках научной программы Национального центра физики и математики, направление № 2 «Математическое моделирование на супер-ЭВМ экса- и зеттафлопсной производитель-ности. Этап 2023–2025».

Список литературы

Turanyi V. Reduction of large reaction mechanisms // New J. Chemistry. 1990. V. 14. № 1 P. 795–803.
Tomlin A. S., Pilling M. J., Turanyi T., Merkin J. H., Brindley J. Mechanism reduction for the oscillatory oxidation of hydrogen: sensitivity and quasi-steady-state analyses // Combust. and Flame. 199 V. 91. № 2. P. 107–130.
Massias A., et al. An algorithm for the construction of global reduced mechanisms with CSP data // Combust. and Flame. 1999. V. 117. № 4. P. 685–708.
Lu T., Ju Y., Law P. K. Complex CSP for chemistry reduction and analysis // Combust. and Flame. 2001. V. 126. № 1–2. P. 1445–1455.
Peters N. Flame calculations with reduced mechanisms — an outline /Reduced kinetic mechanisms for applications in combustion systems. Berlin, Heidelberg: Springer Berlin Heidelberg,1993.P.3–14.
Rabitz H., Kramer M., Dacol D. Sensitivity analysis in chemical kinetics // Annual Rev. of Phys. Chem. 1983. V. 34, № 1. P. 419–461.
Niemeyer K. E., Sung C.-J., Raju M. P. Skeletal mechanism generation for surrogate fuels using directed relation graph with error propagation and sensitivity analysis // Combust. and Flame. 2010.V. 157, № 9. P. 1760–1770.
Mauersberger G. ISSA (iterative screening and structure analysis) a new reduction method and its application to the tropospheric cloud chemical mechanism RACM/CAPRAM2.4 // Atmosph. Environ. 2005. V. 39, iss. 2324. P. 4341–4350.
Zeuch T., Moreac G., Ahmed S., Mauss F. A comprehensive skeletal mechanism for the oxidation of n-heptane generated by chemistry-guided reduction // Combust. and Flame. 2008. V. 155. P. 651–674.
Pepiot-Desjardins P., Pitsch H. An automatic chemical lumping method for the reduction of large chemical kinetic mechanisms // Combust. Theory and Modell. 2008. V. 12, iss. 6. P. 1089–1108.
Lu T., Law C. K. A directed relation graph method for mechanism reduction // Proc. of the Combust. Institute. 2005. V. 30, iss. 1. P. 1333–1341.
Sun W., Chen Z., Gou X., Ju Y. A path ux analysis method for the reduction of detailed chemical kinetic mechanisms // Combustion and Flame. 2010. V. 157, № 7. P. 1298–1307.
Pepiot-Desjardins P., Pitsch H. An efficient error-propagation-based reduction method for large chemical kinetic mechanisms // Combust. and Flame. 2008. V. 154, № 12. P. 6781.
Gao X., Yang S., Sun W. A global pathway selection algorithm for the reduction of detailed chemical kinetic mechanisms // Combust. and Flame. 2016. V. 167. P. 238–247. DOI: 10.1016/j.combustame.2016.02.007.
Dijkstra E. W. A note on two problems in connection with graphs // Numer. Math. 1959. V. 1.P. 269–271. https://doi.org/10.1007/BF01386390.
Yen J. Y. Finding the k shortest loopless paths in a network // Manag. Sci. 1971. V. 17. P. 712–7
Герб А. Р., Девятых Е. Е., Омарова Г. А. Методы графовой редукции в моделях химической кинетики // Пробл. информ. 2024. № 3 (64).
Goodwin D. G., Moffat H. K., Speth R. L. Cantera: An object-oriented software toolkit for chemical kinetics, thermodynamics, and transport processes. [Electron. Res.]: http://www.cantera. org.
[Electron. Res.]: https://eigen.tuxfamily.org/index.php?title=Main_Page.
[Electron. Res.]: https://www.boost.org/doc/libs/1_83_0/doc/html/program_options.
[Electron. Res.]: https://github.com/jbeder/yaml-cpp.
The CRECK Modeling Group. Detailed kinetic mechanisms. [Electron. Res.]: http:// creckmodeling.chem.polimi.it/menu-kinetics/menu-kinetics-detailed-mechanisms/.

Библиографическая ссылка: Герб А. Р., Девятых Е. Е., Омарова Г. А . Сравнение методов графовой редукции первого, второго и третьего поколения в моделях химической кинетики //"Проблемы информатики", 2025, № 4, с.25-37. DOI: 10.24412/2073-0667-2025-4-25-37.

О.Г. Монахов, Э.А. Монахова

Институт вычислительной математики и математической геофизики СО РАН, 630090, Новосибирск, Россия

ГЕНЕРАЦИЯ МНОГОУРОВНЕВЫХ РЕГУЛЯРНЫХ СЕТЕЙ НА ОСНОВЕ ОПЕРАЦИИ КОМПОЗИЦИИ МОДИФИЦИРОВАННЫХ ХОРДАЛЬНЫХ ГРАФОВ С ИСПОЛЬЗОВАНИЕМ БОЛЬШИХ ЯЗЫКОВЫХ МОДЕЛЕЙ

УДК 519.8 + 519.7
DOI: 10.24412/2073-0667-2025-4-38-51
EDN: VRVDCR

Предложена новая модель топологий сетей связи для многопроцессорных систем и сетей на кристалле — класс многоуровневых регулярных параметрически задаваемых сетей (графов). В качестве элементов уровней можно использовать известные регулярные графы, предложенные ранее в качестве структур вычислительных систем, объединяя их оптимальным образом. В данной работе в качестве элементов построения при генерации многоуровневых сетей рассмотрены хордальные графы, которые объединялись с помощью предложенной операции многоуровневой композиции. При синтезе многоуровневых сетей применен алгоритм моделирования отжига для определения оптимальных параметров генерируемой топологии, минимизирующих среднее расстояние сети при заданном числе узлов, числе уровней и степени узлов. Алгоритм синтеза оптимальных сетей разработан с помощью больших языковых моделей и реализован в последовательной и параллельной версиях на кластере Kunpeng 920. Построенные многоуровневые сети имеют лучшие структурные характеристики, чем циркулянтные сети при одинаковых затратах оборудования (количестве узлов и линий связи).

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

Работа выполнена при финансовой поддержке бюджетным проектом ИВМиМГ СО РАН (код проекта FWNM-2025-0005).

Список литературы

Multilevel Network Analysis for the Social Sciences: Theory, Methods and Applications. Lazega, E., Snijders, T. (eds.). // Cham, Heidelberg: Springer. 2016.
Kivela M., Arenas A., Barthelemy M., Gleeson J. P., Moreno Y., Porter M. Multilayer Networks// Journal of Complex Networks. 2014. N 2 (3).
Кальней А. М. Модели многоуровневых сетей (краткий обзор) // Проблемы информатики. 2021. № С. 5–20.
Кальней А. М., Родионов А. С. Анализ надежности многоуровневых сетей с ненадежными вершинами // Проблемы информатики. 2020. № 2. С. 5–15.
Hwang F. K. A survey on multi-loop networks // Theoret. Computer Science. 2003. V. 299.
Reyes, M. A., Dalfo, C., Fiol, M. A. Structural and Spectral Properties of Chordal Ring, Multi-Ring, and Mixed Graphs // Symmetry, 2024. 1 1135.
Gutierrez J., Riaz T., Pedersen J., Labeaga S., Madsen O. Degree 3 networks topological routing// Image Processing and Communication. 2009. N 14.
Ledzinski, D., Smigiel, S., Zabludowski, L. Analyzing methods of network topologies based on chordal rings //Turkish Journal of Electrical Engineering and Computer Sciences. 201 V.26:N 3, Article 25.
Монахова, Э. А., Монахов, О. Г.Метод автоматического поиска семейств оптимальных хордальных кольцевых сетей //Дискретный анализ и исследование операций. 2024.V.31.№ 1.С.85–08.
Монахова, Э. А., Монахов, О. Г.Открытие аналитических зависимостей параметров оптимальных хордальных сетей на основе анализа данных//Проблемы информатики,.2023.№ 4.С.37–48.
Ahmad M., Zahid Z., Zavaid M., and Bonyah E. Studies of Chordal Ring Networks via Double Metric Dimensions // Math. Problems in Engineering. 2022. (ArticleID 8303242).
Arden B. W. and Lee H. Analysis of Chordal Ring Network // IEEE Trans. on Computers. 1981. N C-30.
Morillo P., Comellas F., Fiol M. A. The optimization of Chordal Ring Networks // Communication Technology, Eds. Q. Yasheng and W. Xiuying. World Scientific, 1987. P. 295–299.
Huang, X., Ramos, A. F., Deng, Y. Optimal circulant graphs as low-latency network topologies// J. of Supercomputing. 2022. N 78. P. 13491–13510.
Deng Y., Guo M., Ramos A. F., Huang X., Xu Z., Liu W. Optimal low-latency network topologies for cluster performance enhancement // J. Supercomput, 2020. N 76 (12). P. 9558–9584.
Monakhova E. A Survey on Undirected Circulant Graphs // Discrete Mathematics, Algorithms and Applications. 2012. N 4 (1). 1250002.
Monakhov O., Monakhova E. A Class of Parametric Regular Networks for Multicomputer Architectures // Computacion y Sistemas. 2000. N 4. P. 85–93.
Карпенко А. П. Современные алгоритмы поисковой оптимизации. Алгоритмы, вдохнов-ленные природой // Москва: МГТУ им. Н. Э. Баумана, 2017. 448 с.

Библиографическая ссылка: Монахов О. Г., Монахова Э. А. Генерация многоуровневых регулярных сетей на основе операции композиции модифицированных хордальных графов с использованием больших языковых моделей//"Проблемы информатики", 2025, № 4, с.38-51. DOI: 10.24412/2073-0667-2025-4-38-51.

М.А. Усова, И.Г. Лебедев, A.A. Штанюк, К.А. Баркалов

ННГУ им. Н.И. Лобачевского, 603022, Нижний Новгород, Россия

АЛГОРИТМ ГЛОБАЛЬНОЙ ОПТИМИЗАЦИИ ДЛЯ НАСТРОЙКИ ГИПЕРПАРАМЕТРОВ МЕТОДОВ МАШИННОГО ОБУЧЕНИЯ

УДК 519.853.4
DOI: 10.24412/2073-0667-2025-4-52-72
EDN: XGFNEQ

В статье рассматриваются задачи поиска наилучшего сочетания гиперпараметров методов машинного обучения и искусственного интеллекта. В таких задачах актуальной является проблема некорректной работы исследуемых методов ИИ и МО в некоторых (заранее неизвестных) подобластях области изменения гиперпараметров. С математической точки зрения такая задача может быть представлена как задача поиска глобального минимума функции, заданной в виде «черного ящика» и не всюду определенной в области поиска. Существование подобластей, где целевая функция является неопределенной, можно интерпретировать как наличие некоторых скрытых, заранее неизвестных ограничений. Предложен подход к решению такого рода задач, который является расширением информационно-статистического алгоритма глобального поиска и учитывает наличие неопределенных значения целевой функции в некоторых точках. В рамках предложенного алгоритма проводится разбиение области поиска точками испытаний и оцениваются характеристики подобластей на основе значений целевой функции, вычисленных на их границах. В случае отсутствия информации о значениях функции в алгоритме используется оценка, учитывающая размер исследуемой подобласти. Для сокращения количества испытаний в подобластях, в которых функция не определена, введен специальный параметр метода, позволяющий регулировать число точек испытаний в области невычислимости. Изложено подробное описание и приведена схема работы модифицированного алгоритма глобального поиска. Продемонстрированы результаты его сравнения с другими известными алгоритмами глобальной оптимизации, полученные при проведении численных экспериментов как с тестовыми функциями, так и с модельными задачами настройки гиперпараметров, в которых возникают неопределенные значения оптимизируемой метрики качества.

Ключевые слова: машинное обучение, настройка гиперпараметров, глобальная оптимизация, функции вида «черный ящик», частично определенные функции.

Работа выполнена при поддержке Министерства науки и высшего образования РФ (проект № FSWR-2023-0034) и научно-образовательного математического центра «Математика технологий будущего».

Список литературы

Zhou J. , Qiu Y., Zhu S., Armaghani D. J. , Li C., Nguyen H. , Yagiz S. Optimization of support vector machine through the use of metaheuristic algorithms in forecasting TBM advance rate // Eng. Appl. Artif. Intell. 202 V. 97. P. 104015. DOI: 10.1016/j.engappai.2020.104015.
Yang W., Xia K., Fan S., Wang L., Li T., Zhang J., Feng Y. A Multi-Strategy Whale Optimization Algorithm and Its Application // Eng. Appl. Artif. Intell. 202 V. 108. P. 104558. DOI: 10.1016/j.engappai.2021.104558.
Frazier P. I. A Tutorial on Bayesian Optimization // arXiv. 2018. DOI: 10.48550/arXiv.1807.02811.
Archetti F., Candelieri A. Bayesian Optimization and Data Science. Cham: Springer Briefs in Optimization, 2019. DOI: 10.1007/978-3-030-24494-1.
Jones D., Martins J. The direct algorithm: 25 years later // J. Glob. Optim. 2021. V. 79, № 3.P. 521–566. DOI: 10.1007/s10898-020-00952-6.
Paulaviсius R. and Zilinskas J. Simplicial Global Optimization. New York: Springer, 2014. DOI: 10.1007/978-1-4614-9093-7.
Paulavicius R., Sergeyev Y. D., Kvasov D. E., Zilinskas J. Globally-biased BIRECT algorithm with local accelerators for expensive global optimization // Expert Syst. Appl. 2020. V. 144. P. 113052. DOI: 10.1016/j.eswa.2019.113052.
Сергеев Я. Д., Квасов Д. Е. Диагональные методы глобальной оптимизации. М.: Физматлит, 200
Liberti L., Kucherenko S. Comparison of deterministic and stochastic approaches to global optimization // Int. Trans. Oper. Res. 2005. V. 12. P. 263–285.
Sergeyev Y. D., Kvasov D. E., Mukhametzhanov M. S. On the efficiency of nature-inspired metaheuristics in expensive global optimization with limited budget // Sci. Rep. 2018. V. 8, № 1.P. 435.
Stripinis L., Paulavicius R. A new DIRECT-GLh algorithm for global optimization with hidden constraints // Optim. Lett. 2021. V. 15, № 6. P. 1865–1884. DOI: 10.1007/s11590-021-01726-z.
Audet C., Batailly A., Kojtych S. Escaping unknown discontinuous regions in blackbox optimization // SIAM J. Optim. 2022. V. 32, № 3. P. 1843–1870. DOI: 10.1137/21m1420915.
Candelieri A. Sequential model based optimization of partially defined functions under unknown constraints // J. Glob. Optim. 2019. V. 79, № 2. P. 281–303. DOI: 10.1007/s10898-019-00860-4.
Баркалов К. А., Стронгин Р. Г. Метод глобальной оптимизации с адаптивным порядком проверки ограничений // Журн. вычисл. матем. и матем. физ. 2002. Т. 42, № 9. С. 1338–1350.
Strongin R. G., Barkalov K. A., Bevzuk S. A. Global optimization method with dual Lipschitz constant estimates for problems with non-convex constraints // Soft Comput. 2020. V. 24, № 16. P. 11853–11865. DOI: 10.1007/s00500-020-05078-1.
Sergeyev Y. D., Strongin R. G., Lera D. Introduction to Global Optimization Exploiting Space-Filling Curves. New York: Springer Briefs in Optimization, 2013. DOI: 10.1007/978-1-4614-8042-6.
Strongin R. G., Sergeyev Y. D. Global optimization with non-convex constraints. Sequential and parallel algorithms. Dordrecht: Kluwer Academic Publishers, 2000.
Usova M. A., Barkalov K. A. An Algorithm for Finding the Global Extremum of a Partially Defined Function // Communications in Computer and Information Science. 2024. V. 1914. P. 147–161. DOI: 10.1007/978-3-031-52470-7_13.
Barkalov K. A., et al. On solving the problem of finding kinetic parameters of catalytic isomerization of the pentane-hexane fraction using a parallel global search algorithm // Mathematics. 2022. V. 10, № P. 3665. DOI: 10.3390/math10193665.
Gubaydullin I. M., Enikeeva L. V., Barkalov K. A., Lebedev I. G., Silenko D. G. Kinetic modeling of isobutane alkylation with mixed c4 olefins and sulfuric acid as a catalyst using the asynchronous global optimization algorithm // Commun. Comput. Inf. Sci. 2022. V. 1618. P. 293–306. DOI: 10.1007/978-3-031-11623-0_
Barkalov K. A., Lebedev I. G., Gergel V. P. Parallel Global Search Algorithm with Local Tuning for Solving Mixed-Integer Global Optimization Problems//Lobachevskii Journal of Mathematics. V. 7.№ 42. 2021. P. 1492–1503.
Сысоев А. В., Козинов Е. А., Баркалов К. А., Лебедев И. Г., Карчков Д. А., Родионов Д. М. Фреймворк методов интеллектуальной эвристической оптимизации iOpt // В кн.: Суперкомпью-терные дни в России: Труды международной конференции. 2023. С. 179–185.
Исходный код фреймворка iOpt. [Электрон. рес.]: https://github.com/aimclub/iOpt (дата обращения: 26.01.2025).
Документация iOpt. [Электрон. рес.]: https://iopt.readthedocs.io/ru/latest/ (дата об-ращения: 26.01.2025).
Gaviano M., Kvasov D. E., Lera D., Sergeyev Y. D. Software for generation of classes of test functions with known local and global minima for global optimization // ACM Trans. Math. Softw. 2003. V. 29, № 4. P. 469–480.
Storn R., Price K., Differential Evolution — a Simple and Efficient Heuristic for Global Optimization over Continuous Spaces // Journal of Global Optimization. 1997. V. 11. P. 341–359.
Xiang Y, Gubian S, Suomela B, Hoeng J. Generalized Simulated Annealing for Efficient Global Optimization: the GenSA Package for R // The R Journal. 2013. V. 5, № 1.
Gablonsky J., Kelley C. A Locally-Biased form of the DIRECT Algorithm // Journal of Global Optimization. 2001. V. 21. P. 27–37.
Wales D. J., Doye J. P. K. Global Optimization by Basin-Hopping and the Lowest Energy Structures of Lennard-Jones Clusters Containing up to 110 Atoms // Journal of Physical Chemistry A. 1997. V. 101. P. 5111.
Endres S. C., Sandrock C., Focke W. W. A simplicial homology algorithm for lipschitz optimisation // Journal of Global Optimization. 2018.
Filippou K., Aifantis G., Papakostas G. A., Tsekouras G. E. Structure learning and hyperparameter optimization using an automated machine learning (AutoML) pipeline // Information. 2023. V. 14, № 4. P. 232.
Automated modeling and machine learning framework FEDOT. [Электрон. рес.]: https:// github.com/aimclub/FEDOT (дата обращения: 25.07.2025).
Xu N. Time Series Analysis on Monthly Beer Production in Australia // Highlights in Science, Engineering and Technology. 2024. V. 94. P. 392–401. DOI: 10.54097/4z3krj13.
Akiba T., Sano S., Yanase T., Ohta T., Koyama M. Optuna: A Next-Generation Hyperparameter Optimization Framework // In Proceedings: 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. 2019. P. 2623–2631. DOI: 10.1145/3292500.3330701.

Библиографическая ссылка: Усова М. А., Лебедев И. Г., Штанюк A. A., Баркалов К. А. Алгоритм глобальной оптимизации для настройки гиперпараметров методов машинного обучения //"Проблемы информатики", 2025, № 4, с.52-72. DOI: 10.24412/2073-0667-2025-4-52-72.

В.Э. Малышкин**, В.А. Перепелкин**, В.А. Спирин*

Новосибирский национальный исследовательский государственный университет, 630090, Новосибирск, Россия
**Институт вычислительной математики и математической геофизики СО РАН, 630090, Новосибирск, Россия
***Новосибирский государственный технический университет, 630073, Новосибирск, Россия

ОБЕСПЕЧЕНИЕ АВТОМАТИЧЕСКОГО КОНСТРУИРОВАНИЯ ПРОГРАММ С ИСПОЛЬЗОВАНИЕМ СПЕЦВЫЧИСЛИТЕЛЕЙ НА ОСНОВЕ КОНЦЕПЦИИ АКТИВНЫХ ЗНАНИЙ В СИСТЕМЕ LUNA

УДК 004.4'242
DOI: 10.24412/2073-0667-2025-4-73-88
EDN: ZCPPTC

Спецвычислители, такие как GPU или NPU, ориентированы на определенный характер вычислительной нагрузки, что позволяет в значительной степени повысить их производительность. Разработка эффективных программ, использующих спецвычислители, является трудоемкой задачей, так как требует знаний и навыков в области системного программирования. В частности, разработка таких программ затруднительна для специалистов других профилей. В работе рассматривается автоматическое конструирование параллельных программ с использованием спецвычислителей. Автоматизация направлена на снижение трудоемкости разработки и исполнения программ с получением приемлемой эффективности. Предлагаемое в работе решение основывается на концепции активных знаний и реализуется в системе активных знаний LuNA. Рассматривается расширение архитектуры исполнительной системы для поддержки спецвычислителей на примере представителя нейронных процессоров Huawei Ascend. Поддержка спецвычислителя обеспечивается отдельным слабосвязанным модулем. Приводятся результаты экспериментального исследования решения задач блочного умножения плотных матриц и корреляционной свертки сейсмотрасс с использованием спецвычислителя.

Ключевые слова: концепция активных знаний, система LuNA, спецвычислитель, процессор Huawei Ascend, автоматическое конструирование программ, высокоуровневая спецификация, подсистема поддержки спецвычислителей.

Работа выполнена в рамках государственного задания ИВМиМГ СО РАН FWNM-2025-0005.

Список литературы

Malyshkin V. E. Active Knowledge, LuNA and Literacy for Oncoming Centuries // LNCS, Т. 9465. 2015. P. 292–303. DOI: 10.1007/978-3-319-25527-9_19.
Malyshkin V. E., Perepelkin V. A. LuNA Fragmented Programming System, Main Functions and Peculiarities of Run-Time Subsystem // Proceedings of the 11th International Conference on Parallel Computing Technologies (PaCT-2011), LNCS, 2011. Т. 6873, P. 53–61. DOI: 10.1007/978-3-642-23178-0_5.
Малышкин В. Э., Перепелкин В. А. Построение баз активных знаний для автоматического конструирования решений прикладных задач на основе системы LuNA // Параллельные вычис-лительные технологии — XVIII всероссийская научная конференция с международным участием, ПаВТ’2024, г. Челябинск, 2–4 апреля 2024 г. Короткие статьи и описания плакатов. Челябинск: Издательский центр ЮУрГУ, 2024. С. 57–68. DOI: 10.14529/pct2024.
Liang X. Ascend AI Processor Architecture and Programming: Principles and Applications of CANN. Elsevier, 2020. DOI: 10.1016/C2020-0-00270-7.
Malyshkin V., Perepelkin V., Schukin G. Scalable Distributed Data Allocation in LuNA Fragmented Programming System // The Journal of Supercomputing, 2017. Т. 73, Iss. 2, Springer. P. 726–732. DOI: 10.1007/s11227-016-1781-0.
Малышкин В. Э., Перепелкин В. А., Щукин Г. А. Распределенный алгоритм управления данными в системе фрагментированного программирования LuNA // Проблемы информатики, 2017. № 1(34). С. 74–88.
Using Operator Samples [Electron. Res.]: https://www.hiascend.com/document/detail/zh/ CANNCommunityEdition/82RC1alpha001/opdevg/tbeaicpudevg/atlasopdev_10_0025.html.
AscendCL architecture and basic concepts [Electron. Res.]: https://www.hiascend.com/ document/detail/zh/CANNCommunityEdition/82RC1alpha001/appdevg/aclcppdevg/aclcppdevg_ 000004.html.
Спирин В. А. Разработка алгоритмов автоматизации применения NPU в системе LuNA // Параллельные вычислительные технологии — XVIII всероссийская научная конференция с меж-дународным участием, ПаВТ’2024, г. Челябинск, 2–4 апреля 2024 г. Короткие статьи и описания плакатов. Челябинск: Издательский центр ЮУрГУ, 2024. С. 165-176. DOI: 10.14529/pct2024.
Хайретдинов М. С. Алгоритмы поточной свертки в задачах активного вибросейсмоакусти-ческого мониторинга / М. С. Хайретдинов, Г. М. Воскобойникова, Г. С. Седухина // Геосибирь, 2017.
Лаборатория искусственного интеллекта и информационных технологий [Электрон. Рес.]: https://icmmg.nsc.ru/ru/content/pages/laboratoriya-iskusstvennogo-intellekta-i-informacionnyh-tehnologiy.
Chen L. Deep learning and practice with mindspore. Springer Nature, 2021. DOI: 10.1007/978-981-16-2233-5.
Feng W., Maghareh R., Wang K. T. A. Extending DPC++ with Support for Huawei Ascend AI Chipset // International Workshop on OpenCL. 2021. P. 1–4. DOI: 10.1145/3456669.3456684.
Gu R., Becchi M. A comparative study of parallel programming frameworks for distributed GPU applications // Proceedings of the 16th ACM International Conference on Computing Frontiers. 2019. P. 268–273. DOI: 10.1145/3310273.3323071.
Robson M. P., Buch R., Kale L. V. Runtime coordinated heterogeneous tasks in Charm++ // 2016 Second International Workshop on Extreme Scale Programming Models and Middlewar (ESPM2). IEEE, 2016. P. 40–43. DOI: 10.1109/ESPM2.2016.011.
Bauer M. et al. Legion: Expressing locality and independence with logical regions // SC’12: Proceedings of the International Conference on High Performance Computing, Networking, Storage and Analysis. IEEE, 2012. P. 1–11. DOI: 10.1109/SC.2012.71.
Augonnet C. et al. StarPU: a unified platform for task scheduling on heterogeneous multicore architectures // Euro-Par 2009 Parallel Processing: 15th International Euro-Par Conference, Delft, The Netherlands, August 25–28, 2009. Proceedings 15. Springer Berlin Heidelberg, 2009. P. 863–874. DOI: 10.1007/978-3-642-03869-3_80.
Ayguad´e E. et al. An extension of the StarSs programming model for platforms with multiple GPUs // Euro-Par 2009 Parallel Processing: 15th International Euro-Par Conference, Delft, The Netherlands, August 25–28, 2009. Proceedings 15. Springer Berlin Heidelberg, 2009. P. 851–862. DOI: 10.1007/978-3-642-03869-3_79.

Библиографическая ссылка: Малышкин В. Э., Перепелкин В. А., Спирин В. А. Обеспечение автоматического конструирования программ с использованием спецвычислителей на основе концепции активных знаний в системе LuNa//"Проблемы информатики", 2025, № 4, с.73-88. DOI: 10.24412/2073-0667-2025-4-73-88.

Main menu

You are here

2025 №4(69)

Languages