Volume 4(69)

Contents

M.P. Bakulina. AN EFFICIENT COMPRESSION ALGORITHM USING DICTIONARY-TYPE DATA TRANSFORMATION.

N.G. Bredikhin, S.V. Scherbakova. COMMUNITY DETECTION IN THE MULTIPLEX NETWORK OF SCIENTIFIC JOURNAL AUTHORS.

A.R. Gerb, E.E. Deviatykh, G.A. Omarova. COMPARISON OF FIRST, SECOND AND THIRD GENERATION GRAPH REDUCTION METHODS IN CHEMICAL KINETICS MODELS.

O.G. Monakhov, E.A. Monakhova. GENERATION OF MULTI-LEVEL REGULAR NETWORKS BASED ON THE COMPOSITION OPERATION OF MODIFIED CHORDAL GRAPHS USING LARGE LANGUAGE MODELS.

M.A. Usova, I.G. Lebedev, A.A. Shtanyuk, K.A. Barkalov. A GLOBAL OPTIMIZATION ALGORITHM FOR TUNING HYPERPARAMETERS OF MACHINE LEARNING METHODS.

V.E. Malyshkin, V.A. Perepelkin, V.A. Spirin. AUTOMATIC PROGRAM CONSTRUCTION WITH ACCELERATORS USAGE BASED ON THE ACTIVE KNOWLEDGE CONCEPT IN LUNA SYSTEM.

 

M.P. Bakulina

Institute of Computational Mathematics and Mathematical Geophysics SB RAS, 630090, Novosibirsk, Russia

AN EFFICIENT COMPRESSION ALGORITHM USING DICTIONARY-TYPE DATA TRANSFORMATION

DOI: 10.24412/2073-0667-2025-4-5-10

EDN: KUQHBT

The problem of efficient lossless compression for dictionary-type data is considered. For such data, the coding algorithm is based on the use of a dictionary formed from the text received for compression. It is also known that data processing, such as BWT, can improve the text compression ratio. In this paper, an efficient dictionary-type data compression algorithm based on the modification of BWT is proposed. Experimental results are presented. The results confirm the increase in the data compression ratio by the proposed algorithm compared to the classic archiver bzip2.
Key words: dictionary, BWT-transformation, compression ratio, encoding time, archiver.

The research was carried out within the framework of a state assignment of the Institute of Computational Mathematics and Mathematical Geophysics SB RAS (ICM&MG SB RAS) 0251-2022-0005.

References:

  1. Burrows, M. A block sorting lossless data compression algorithm. M. Burrows, D. Wheeler, Technical Report 124, Digital Equipment Corporation, 1994. P. 18.
  2. Ryabko B. Ya. Data compression by means of a “book stack” // Problems of Information Transmission. 1980, V. 16: (4). P. 265–269.
  3. Hmelev D. V. Preobrazovanie Barrouza-Willera, massiv suffiksov i szhatie slovarei // Vse o szhatii dannyh, izobrazhenii i video. [Electron. Res.]: http://compression.ru/download/articles/ bwt/khmelev_2003_bwt.pdf.
  4. 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. P. 943–955.

Bibliographic reference: http://problem-info.sscc.ru/ru/node/142#1

Bredikhin, N.G. Scherbakova S. V.

Institute of Computational Mathematics and Mathematical Geophysics SB RAS, 630090, Novosibirsk, Russia

COMMUNITY DETECTION IN THE MULTIPLEX NETWORK OF SCIENTIFIC JOURNAL AUTHORS

DOI: 10.24412/2073-0667-2025-4-11-24

EDN: TWNDJO

The article presents a model of a multiplex network reflecting a real scheme of collaboration of authors of a scientific journal. The initial data are extracted from the XML archive of the journal articles. The model is presented as a two-layer graph, the vertices of which correspond to the authors of the articles, and the edges — to binary relations of co-authorship and citation. The purpose of the work is to identify non-intersecting communities of authors of the network and is achieved in two stages. At the first phase, the network is reduced to the form of an undirected graph Gf using “flattening algorithm”, this allows to apply the known algorithms of community detection intended for single-layer networks. So, at the second phase, two traditional clustering algorithms, Walktrap and Infomap, based on the “random walk” method are applied to the flattened network. The result of the algorithm is a set of identifiers of nodes included in the community, by which the original multilayer network structure can be restored. The comparison of the algorithms’ results is made using the randadjusted_rand and nmi indices. For Gf, all indices demonstrate a high level of similarity in the algorithms’ results. The parameter c, which characterizes the degree of overlapping of layers at the community level, serves as a characteristic of multilayering. The study of this parameter showed that most communities have a zero value, i.e. the communities consist of vertices of one of the layers. It should be noted that these are the actors of the co-authorship layer, while the citation layer contains 37 % of single nodes. The results of the analysis are presented in the form of tables.
Key words: multiplex network, scientific community, co-authorship, citation, modularity, bibliometrics.

This work was carried out under state contract with ICMMG SB RAS (FWNM-2025-0005).

References

  1. Barab´asi A-L., P´osfai M. Network Science. Cambridge Univ. Press. 456 p. ISBN 1107076269.
  2. 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.
  3. 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.
  4. Distel’ R. Teoriya grafov. Novosibirsk: Izd-vo In-ta matematiki, 2002. 336 s. ISBN 5-86134-101-X.
  5. Peel L., Larremore D. B., Clauset A. The ground truth about metadata and community detection in networks // Sci. Adv. 2017. V. 3, iss. 5. e1602548. DOI: 10.1126/scadv.1602548.
  6. 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.
  7. 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.
  8. Magnani M., Hanteer O., Interdonato R., Rossi L., Tagarelli A. Community detection in multiplex networks // arXiv: 0911.1824. DOI: 10.48550/arXiv.1910.07646.
  9. 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.
  10. 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.
  11. 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.
  12. 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.
  13. 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.
  14. 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.
  15. 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.
  16. Bianconi G. Multilayer networks. Structure and functions. Oxford. 2018. Online ISBN: 9780191815676.
  17. Lancichinetti A., Fortunato S. Consensus clustering in complex networks // Sci. Rep. 2012. V. 2. Art. num. 336. DOI: 10.1038/srep00336.
  18. Mondragon R. J., Iacovacci J., Bianconi G. Multilink communities of multiplex networks // arXiv:1706.09011. DOI: 10.48550/arXiv.1706.09011.
  19. 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.
  20. Bredihin S. V., Shcherbakova N. G. Vzveshennaya mul’tipleksnaya set’ avtorov nauchnogo zhurnala // Probl. inform. 2025. N 1. S. 45–59. DOI: 10.24412/2073-0667-2025-1-45-59.
  21. Bredihin S. V., Shcherbakova N. G. Strukturnye svojstva mul’tipleksnoj seti avtorov nauchnogo zhurnala // Probl. inform. 2025. N 2. S. 8–18. DOI: 10.24412/2073-0667-2025-2-5-18.
  22. 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.
  23. Wagner S., Wagner D. Comparing clusterings — An overview. 2007. DOI: 10.5445/IR/1000011477. https://publikationen.bibliothek.kit.edu/1000011477.
  24. 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.
  25. 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.
  26. 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.
  27. 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.
  28. 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.
  29. De Domenico M., Nicosia V., Arenas A., Latora V. Structural reducibility of multilayer networks // Nature Communic. 2015. V. 6. 6864. DOI: 10.1038/ncomms7864.
  30. 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.
  31. Pons P., Latapy M. Computing communities in large networks using random walks. 2006. arXiv: physics/0512106. DOI: 10.48550/arXiv. physics/0512106.
  32.  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.

A.R. Gerb, E.E. Deviatykh*, G.A. Omarova

Institute of Computational Mathematics and Mathematical Geophysics SB RAS, 630090, Novosibirsk, Russia
*Novosibirsk State University, 630090, Novosibirsk, Russia

COMPARISON OF FIRST, SECOND AND THIRD GENERATION GRAPH REDUCTION METHODS IN CHEMICAL KINETICS MODELS

DOI: 10.24412/2073-0667-2025-4-25-37

EDN: VBFMRT

A detailed description of the mechanisms of chemical reactions of hydrocarbon oxidation includes many different pathways and sets of elementary reactions, which makes it difficult to use large-size models to calculate complex combustion phenomena. To address this problem, methods of reduction of chemical kinetic mechanisms are applied. In this paper, a comparative analysis of the performance of graph reduction methods of different generations is carried out. The initial kinetic mechanism is represented as an oriented graph, the nodes of which correspond to chemical substances, the arcs reflect the dependencies between substances. The advantage of these methods lies in their lower computational costs and their ability to form rather compact reduced models.

Key words: graph, reduction, chemical kinetics model, DRG, DRGEP, PFA, GPS.

References:

  1. Turanyi V. Reduction of large reaction mechanisms // New J. Chemistry. 1990. V. 14. N 1 P. 795–803.
  2. 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. N 2. P. 107–130.
  3. Massias A., et al. An algorithm for the construction of global reduced mechanisms with CSP data // Combust. and Flame. 1999. V. 117. N 4. P. 685–708.
  4. Lu T., Ju Y., Law P. K. Complex CSP for chemistry reduction and analysis // Combust. and Flame. 2001. V. 126. N 1–2. P. 1445–1455.
  5. 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.
  6. Rabitz H., Kramer M., Dacol D. Sensitivity analysis in chemical kinetics // Annual Rev. of Phys. Chem. 1983. V. 34, N 1. P. 419–461.
  7. 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, N 9. P. 1760–1770.
  8. 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.
  9. 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.
  10. 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.
  11. 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.
  12. 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, N 7. P. 1298–1307.
  13. Pepiot-Desjardins P., Pitsch H. An efficient error-propagation-based reduction method for large chemical kinetic mechanisms // Combust. and Flame. 2008. V. 154, N 12. P. 6781.
  14. 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.
  15. 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.
  16. Yen J. Y. Finding the k shortest loopless paths in a network // Manag. Sci. 1971. V. 17. P. 712–7
  17. Gerb A. R., Deviatykh E. E., Omarova G. A. Metody grafovoi reduktcii v modeliakh himicheskoi kinetiki // Probl. inform. 2024. N 3 (64).
  18. 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.
  22.  The CRECK Modeling Group. Detailed kinetic mechanisms. [Electron. Res.]: http:// creckmodeling.chem.polimi.it/menu-kinetics/menu-kinetics-detailed-mechanisms/.

O.G. Monakhov, E.A. Monakhova

Institute of Computational Mathematics and Mathematical Geophysics SB RAS, 630090, Novosibirsk, Russia

GENERATION OF MULTI-LEVEL REGULAR NETWORKS BASED ON THE COMPOSITION OPERATION OF MODIFIED CHORDAL GRAPHS USING LARGE LANGUAGE MODELS

DOI: 10.24412/2073-0667-2025-4-38-51

EDN: VRVDCR

The paper is devoted to the development and study of a new class of topologies for communication networks used in multiprocessor systems and networks-on-chip. The primary goal of this paper is to solve the problem of network topology optimization. Key network characteristics are its diameter (the maximum shortest distance between any two nodes) and the average distance between nodes: the smaller these parameters, the lower the data transmission latency and the higher the overall system performance. The goal of this paper is to propose a new network construction model that achieves better performance (smaller average distance) compared to existing optimal circulant networks with the same hardware costs (i.e., the same number of nodes and links). The paper proposes a new method for constructing multi-level networks and introduces a new operation, multi-level composition, which allows the use of a wide range of regular graphs, previously proposed as computing system structures, as layer elements, combining them optimally. In this paper, the operation of multi-level composition is applied to a class of chordal rings and modified chordal graphs. The essence of the method is as follows: 1. Level creation: The network is constructed from several (m) levels. Each level is a regular graph (in this paper, a chordal graph g1). In the first step, m disconnected copies of this graph are created. 2. Level connection: All nodes from all levels are connected to each other via a second, “global” graph (G2), which is also chordal. The result is a new, more complex regular network G, which is the sum of the graphs G1 (intra-level connections) and G2 (inter-level connections). To find the best configuration of such a network (i.e., to find the generators for graphs g1 and G2), the authors use the Simulated Annealing algorithm. This algorithm allows for efficient finding of parameters that minimize the average distance in the resulting network. The algorithm for synthesizing optimal multi-level networks was developed using large language models and implemented in sequential and parallel versions on the Kunpeng cluster. The authors conducted numerical simulations and compared their multi-layer networks with the best known circulant networks (C). Optimal (suboptimal) multi-layer regular networks of degrees 4 and 6 were obtained. The influence of multi-layer network parameters on the average distance including the number of levels was studied. The paper presents the key experimental results. (1) Improvement: in some configurations, for degree 4, the improvement reached more than 3 times compared to optimal circulant networks. (2) Scalability: the advantage of the new approach becomes more pronounced with an increasing number of nodes in the network. This makes it promising for building large computing systems and networks. (3) Use of AI in development: an interesting feature of the work is that the authors used large language models (LLM), such as Gemini-2.5Pro, to assist in writing and parallelizing C code for running simulations. According to the authors’ estimates, this reduced development time by 20–30 %. The article demonstrates the effectiveness of the new approach and convincingly demonstrates that the proposed multi-level composition operation is a new tool for constructing high-performance network topologies. The practical significance of the article lies in the fact that the resulting networks can be used to design real multiprocessor systems and networks-on-chip, providing lower latency and improved performance. The proposed method is general and can be applied in the future to other classes of graphs, not just chordal ones, opening up new avenues for research. The paper utilizes modern artificial intelligence tools and demonstrates the successful integration of modern AI assistants into scientific research and the development of complex software. Future work is planned to explore the use of other classes of graphs to obtain multi-level regular networks, as well as to theoretically study their characteristics and the possibility of constructing efficient routing algorithms in such networks.
Supported by the state assignment of ICMMG SB RAS N FWNM-2025-0005.
Key words: chordal network, average distance, parametric description, circulant network, optimal graph, large language model.

References:

  1. Multilevel Network Analysis for the Social Sciences: Theory, Methods and Applications. Lazega, E., Snijders, T. (eds.). // Cham, Heidelberg: Springer. 2016.
  2. Kivela M., Arenas A., Barthelemy M., Gleeson J. P., Moreno Y., Porter M. Multilayer Networks // Journal of Complex Networks. 2014. N 2 (3).
  3. Kalney A. M. Modeli mnogourovnevyh setej (kratkij obzor) // Problemy informatiki. 2021. N P. 5–20.
  4. Kalney A. M., Rodionov A. S. Analiz nadezhnosti mnogourovnevyh setej s nenadezhnymi vershinami // Problemy informatiki. 2020. N 2. P. 5–15.
  5. Hwang F. K. A survey on multi-loop networks // Theoret. Computer Science. 2003. V. 299.
  6. Reyes, M. A., Dalfo, C., Fiol, M. A. Structural and Spectral Properties of Chordal Ring, Multi-Ring, and Mixed Graphs // Symmetry, 2024. 1 1135.
  7. Gutierrez J., Riaz T., Pedersen J., Labeaga S., Madsen O. Degree 3 networks topological routing // Image Processing and Communication. 2009. N 14.
  8. 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.
  9. Monakhova, E. A., Monakhov, O. G. Metod avtomaticheskogo poiska semejstv optimal’nyh hordal’nyh kol’cevyh setej // Diskretnyj analiz i issledovanie operacij. 2024. N 1. P. 85–108.
  10. Monakhova, E. A., Monakhov, O. G., Otkrytie analiticheskih zavisimostej parametrov optimal’nyh hordal’nyh setej na osnove analiza dannyh // Problemy informatiki. 2023. N 4.
  11. 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).
  12. Arden B. W. and Lee H. Analysis of Chordal Ring Network // IEEE Trans. on Computers. 1981. N C-30.
  13.  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.
  14. Huang, X., Ramos, A. F., Deng, Y. Optimal circulant graphs as low-latency network topologies // J. of Supercomputing. 2022. N 78. P. 13491–13510.
  15. 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.
  16. Monakhova E. A Survey on Undirected Circulant Graphs // Discrete Mathematics, Algorithms and Applications. 2012. N 4 (1). 1250002.
  17. Monakhov O., Monakhova E. A Class of Parametric Regular Networks for Multicomputer Architectures // Computacion y Sistemas. 2000. N 4. P. 85–93.
  18. Karpenko A. P. Sovremennye algoritmy poiskovoj optimizacii. Algoritmy, vdohnovlennye prirodoj // Moskva: MGTU im. N. E. Baumana, 2017.

M.A. Usova, I.G. Lebedev, A.A. Shtanyuk, K.A. Barkalov

Lobachevsky State University, 603022, Nizhny Novgorod, Russia

A GLOBAL OPTIMIZATION ALGORITHM FOR TUNING HYPERPARAMETERS OF MACHINE LEARNING METHODS

DOI: 10.24412/2073-0667-2025-4-52-72

EDN: XGFNEQ

The paper discusses the problem of finding the best combination of hyperparameters of machine learning and artificial intelligence methods. In many cases, the efficiency (in a given metric) of the resulting solution for different values of hyperparameters can be quite different. In such problems, a significant issue is the potential for incorrect operation of the investigated artificial intelligence and machine learning methods within certain (a priori unknown) subregions of the hyperparameters search domain. Furthermore, the computational complexity of tuning makes manual or exhaustive search inappropriate. These characteristics have required the development of various intelligent automatic hyperparameter optimization methods. From a mathematical point of view, such a task can be represented as the problem of finding a global minimum of a function, given in the form of a “black box” and computable only in some part of the search domain. In this case, each computation of the objective function value at some point of the feasible domain may require significant computing resources. The objective function is assumed to satisfy the Lipschitz condition. The existence of subdomains where the objective function is undefined can be interpreted as the existence of some hidden, a priori unknown constraints of the problem. The authors propose an approach to solving this type of problem, which is an extension of the information-statistical global search algorithm (GSA) and takes into account the presence of undefined values of the objective function at some points. The algorithm partitions the search space with trial points and evaluates the characteristics of subregions based on the objective function values computed at their boundaries. If the function value at a point is unknown, the algorithm employs an estimate for this value, considering the size of the subregion under investigation. To minimize the number of redundant trials in subdomains where the function is not defined, the method parameter was used that regulates the number of trial points in regions of non-computability. The solution of multidimensional problems implemented through reducing them to one-dimensional optimization problems using space-filling curves (Peano curves). The article provides a detailed description and a flowchart of the operation of the proposed search algorithm. The implementation of the global search algorithm for the case of a not everywhere computable objective function (GSA-N) was based on the iOpt open source framework of intelligent optimization methods. To carry out the experiments, a generator of test problems with hidden constraints GKLS-HC was developed. It is based on the GKLS generator, which allows generating multiextremal functions with specified properties (number of minima, their regions of attraction, etc.). In the GKLS-HCgenerator, these functions were spoiled by areas of non-computability in the form of ellipsoids (the coordinates of centers and radii were generated randomly). The experimental results presented in the paper, obtained on a series of GKLS-HC test problems, demonstrate the reliability of global search and the efficiency of the developed algorithm. By adjusting the parameter , it was possible to achieve the same performance of GSA-N operation as the basic GSA. The paper also considered the behavior of global optimization algorithms of the scipy.optimize library when solving problems with non-computable domains. In this study, the differential evolution and brute force methods showed the worst results, failing to solve this type of problem at all. The DIRECT and SHGO methods, although they solved the problems, were less effective than the developed GSA-N. Experiments were also conducted with hyperparameter tuning problems where undefined values of the quality metric arise. In these problems, certain hyperparameter combinations caused the method to return infinite values for the objective function. The LinearSVC classification algorithm was successfully tuned. GSA-N effectively solved the problem, identifying a better hyperparameter combination compared to standard scikit-learn algorithms. A time series prediction method from the FEDOT framework was also configured. During this experiment, GSA-N was compared to tuning algorithms from the popular Optuna framework. GSA-N achieved comparable performance in terms of the obtained the target metric value, significantly surpassing Optuna in solution time.
Key words: machine learning, hyperparameter tuning, global optimization, black-box functions, partially defined functions.
The work was carried out with the support of the Ministry of Science and Higher Education of the Russian Federation (state assignment N FSWR-2023-0034) and Scientific and Educational Mathematical Center “Mathematics of Future Technologies”.

References:

  1. 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.
  2. 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.
  3. Frazier P. I. A Tutorial on Bayesian Optimization // arXiv. 2018.
  4. Archetti F., Candelieri A. Bayesian Optimization and Data Science. Cham: Springer Briefs in Optimization, 2019.
  5. Jones D., Martins J. The direct algorithm: 25 years later // J. Glob. Optim. 2021. V. 79, N 3. P. 521–566.
  6. Paulaviсius R. and Zilinskas J. Simplicial Global Optimization. New York: Springer, 2014.
  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.
  8. Sergeev Ya. D., Kvasov D. E. Diagonalnye metody globalnoj optimizacii. M.: Fizmatlit, 200
  9. Liberti L., Kucherenko S. Comparison of deterministic and stochastic approaches to global optimization // Int. Trans. Oper. Res. 2005. V. 12. P. 263–285.
  10. 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, N 1. P. 435.
  11. Stripinis L., Paulavicius R. A new DIRECT-GLh algorithm for global optimization with hidden constraints // Optim. Lett. 2021. V. 15, N 6. P. 1865–1884.
  12. Audet C., Batailly A., Kojtych S. Escaping unknown discontinuous regions in blackbox optimization // SIAM J. Optim. 2022. V. 32, N 3. P. 1843–1870.
  13. Candelieri A. Sequential model based optimization of partially defined functions under unknown constraints // J. Glob. Optim. 2019. V. 79, N 2. P. 281–303.
  14. Barkalov K. A., Strongin R. G. Metod globalnoj optimizacii s adaptivnym poryadkom proverki ogranichenij // Zhurn. vy‘chisl. matem. i matem. fiz. 2002. T. 42, N 9. S. 1338–1350.
  15. 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, N 16. P. 11853–11865.
  16. Sergeyev Y. D., Strongin R. G., Lera D. Introduction to Global Optimization Exploiting Space-Filling Curves. New York: Springer Briefs in Optimization, 2013.
  17. Strongin R. G., Sergeyev Y. D. Global optimization with non-convex constraints. Sequential and parallel algorithms. Dordrecht: Kluwer Academic Publishers, 2000.
  18. 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.
  19. 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, N P. 3665.
  20. 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.
  21. 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. N 42. 20 P. 1492–1503.
  22. Sysoev A. V., Kozinov E. A., Barkalov K. A., Lebedev I. G., Karchkov D. A., Rodionov D. M. Frejmvork metodov intellektualnoj evristicheskoj optimizacii iOpt // V kn.: Superkompyuternye dni v Rossii: Trudy mezhdunarodnoj konferencii. 2023. S. 179–185.
  23. Ishodnyj kod frejmvorka iOpt. [Electron. Res.]: https://github.com/aimclub/iOpt (data obrasheniya: 26.01.2025).
  24. Dokumentaciya iOpt. [Electron. Res.]: https://iopt.readthedocs.io/ru/latest/ (data obrasheniya: 26.01.2025).
  25. 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, N 4. P. 469–480.
  26. 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.
  27. 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, N 1.
  28. Gablonsky J., Kelley C. A Locally-Biased form of the DIRECT Algorithm // Journal of Global Optimization. 2001. V. 21. P. 27–37.
  29. 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.
  30. Endres S. C., Sandrock C., Focke W. W. A simplicial homology algorithm for lipschitz optimisation // Journal of Global Optimization. 2018.
  31. 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, N 4. P. 232.
  32. Automated modeling and machine learning framework FEDOT. [Electron. Res.]: https:// github.com/aimclub/FEDOT (data obrashheniya: 25.07.2025).
  33. Xu N. Time Series Analysis on Monthly Beer Production in Australia // Highlights in Science, Engineering and Technology. 2024. V. 94. P. 392–401.
  34.  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.

Bibliographic reference: http://problem-info.sscc.ru/ru/node/142#5

V.E. Malyshkin******, V.A. Perepelkin******, V.A. Spirin*** 

*Novosibirsk State University, 630090, Novosibirsk, Russia
**Institute of computational mathematics and mathematical geophysics SB RAS, 630090, Novosibirsk, Russia
***Novosibirsk State Technical University, 630073, Novosibirsk, Russia

AUTOMATIC PROGRAM CONSTRUCTION WITH ACCELERATORS USAGE BASED ON THE ACTIVE KNOWLEDGE CONCEPT IN LUNA SYSTEM

DOI: 10.24412/2073-0667-2025-4-73-88

EDN: ZCPPTC

As accelerators are designed for specific types of computations (e.g., GPUs, NPUs, FPGAs), they can significantly improve the performance of corresponding programs. In fact, most of the computing power in modern multicomputers is provided by accelerators. However, using accelerators in programs requires knowledge of system programming, which makes development more difficult for experts in other domains. For example, it is necessary to manage data transfers between CPUs and accelerators, implement load balancing, and schedule computations on accelerators. Achieving good efficiency requires different optimization methods in different subject domains. One way to reduce the labor costs of developing programs that use accelerators is to offload some complex routine tasks from humans to an automation system. Such systems can lower the required level of competence for developing efficient programs by performing automatic program construction. Potentially, these automation systems can also produce programs with higher efficiency than average hand-coded implementations. Since no universal automation approach exists for such systems, it is necessary to develop various approaches for particular classes of applied problems and types of accelerators. One method that can be applied here is the active knowledge concept [1]. Automatic construction of parallel programs using the active knowledge concept is performed based on computational models (CMs). CMs are designed to represent knowledge in a certain subject domain. For simplicity, a CM can be viewed as a bipartite directed graph consisting of operations and variables. Each variable represents a certain value within the subject domain. Each operation represents the derivation of its output variables (on outgoing arcs) from its input variables (on incoming arcs). Operations are supplied with code fragments (CFs) in the form of conventional subroutines (procedures). To solve a problem in this CM’s subject domain, we define a VW-task on the CM, where Vis the set of input variables and W is the set of output variables to be computed. A VW-plan is then derived from the VW-task (if it exists). A VW-plan is a subgraph of the CM containing the necessary operations and variables to compute the variables in W from the variables in V. Using the VW-plan, a program can be constructed that takes values for the variables in V and computes values for the intermediate variables and the variables in W. Such programs can be parallel if different variables can be evaluated independently. The actual program construction (VW-plan derivation and/or program generation) is performed by an active knowledge system. An example of such a system, explored in this paper, is the LuNA system [2, 3]. The LuNA system takes a prepared VW-plan and performs program generation; the generated program is then executed by the runtime system. The runtime system uses a thread pool to schedule and execute operations. The thread pool consists of one queue and multiple worker threads that take available tasks from the queue and execute them. In a distributed system, multiple instances of the runtime system can execute the generated program. These instances communicate to decide which operation will be executed on which node. In this paper, we consider an extension of the LuNA runtime system to support accelerators. In particular, we examine the Huawei Ascend neural processor [4]. We propose a high-level specification called CoFaNA (Code Fragment Notation for Accelerators) for describing computations to be executed on the Ascend accelerator. We also propose an extension of the thread pool to perform computations executed on both CPUs and Ascends. The thread pool was extended to have three queues: one for tasks to be executed on CPUs, another for tasks to be executed on Ascends, and a third for heterogeneous tasks that can be executed on either CPUs or Ascends. We also split the worker threads into two groups: one group can execute tasks on CPUs (including heterogeneous tasks), and the other group can execute tasks on Ascends. Next, based on the implementation of support for the Ascend accelerator, we propose a subsystem that can potentially use any accelerator. By implementing support for a particular accelerator in a separate extension module (plugin), the subsystem can use subprograms from this module during program generation and execution in the runtime system. An extension module implements interfaces for the code generator, context, and thread pool, and also provides metainformation. This metainformation is used during program generation to link necessary shared libraries. The context is used to initialize or deinitialize libraries used in the extension module. The code generator can parse various high-level specifications (for example, the CoFaNA format for the Ascend accelerator). The thread pool can be implemented in various ways to use accelerators more efficiently. An experimental study of using the Ascend accelerator was carried out on an Atlas 800 server [11]. We considered the problems of block multiplication of dense matrices and convolution of seismic traces [10]. The results show that LuNA implementations have execution times comparable to hand-coded C++ programs. The CoFaNA format helped to reduce the labor costs required to develop programs that use the Ascend accelerator. In conclusion, this research explored the automatic construction of programs that use accelerators, based on the active knowledge concept. As a result of the work, the LuNA system was extended to support the Huawei Ascend accelerator and potentially other accelerators. In the future, we plan to implement support for other accelerators and, if necessary, expand the subsystem. We also plan to research improvements for using the Huawei Ascend processor in the LuNA system: expanding the CoFaNA format, considering alternative implementations of the thread pool, and automatically selecting the precision of floating-point numbers based on the properties of the applied problem being solved.

Key words: active knowledge, LuNA system, accelerator, Huawei Ascend processor, automatic program construction, high-level specification, subsystem for accelerators support.

Supported by the state assignment of ICMMG SB RAS N FWNM-2025-0005.

References:

  1. Malyshkin V. E. Active Knowledge, LuNA and Literacy for Oncoming Centuries // LNCS, V. 9465. 2015. P. 292–303. DOI: 10.1007/978-3-319-25527-9_19.
  2.   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. V. 6873, P. 53–61. DOI: 10.1007/978-3-642-23178-0_5.
  3. Malyshkin V. E., Perepelkin V. A. Postroenie baz aktivnyh znanij dlya avtomaticheskogo konstruirovaniya reshenij prikladnyh zadach na osnove sistemy LuNA // Parallel’nye vychislitel’nye tekhnologii — XVIII vserossijskaya nauchnaya konferenciya s mezhdunarodnym uchastiem, PaVT’2024, g. Chelyabinsk, 2–4 aprelya 2024 g. Korotkie stat’i i opisaniya plakatov. Chelyabinsk: Izdatel’skij centr YUUrGU, 2024. P. 57–68. DOI: 10.14529/pct2024 (In Russian).
  4. Liang X. Ascend AI Processor Architecture and Programming: Principles and Applications of CANN. Elsevier, 2020. DOI: 10.1016/C2020-0-00270-7.
  5. Malyshkin V., Perepelkin V., Schukin G. Scalable Distributed Data Allocation in LuNA Fragmented Programming System // The Journal of Supercomputing, 2017. V. 73, Iss. 2, Springer. P. 726–732. DOI: 10.1007/s11227-016-1781-0.
  6. Malyshkin V. E., Perepelkin V. A., Schukin G. A. Distributed Algorithm for Data Allocation in Luna Fragmented Programming System // “Problems of informatics”. 2017, N 1. P. 74–88.
  8. AscendCL architecture and basic concepts [Electron. Res.]: https://www.hiascend.com/ document/detail/zh/CANNCommunityEdition/82RC1alpha001/appdevg/aclcppdevg/aclcppdevg_   000004.html.
  9. Spirin V. A. Razrabotka algoritmov avtomatizacii primeneniya NPU v sisteme LuNA// Parallel’nye vychislitel’nye tekhnologii — XVIII vserossijskaya nauchnaya konferenciya s mezhdunarodnym uchastiem, PaVT’2024, g. Chelyabinsk, 2–4 aprelya 2024 g. Korotkie stat’i i opisaniya plakatov. Chelyabinsk: Izdatel’skij centr YUUrGU, 2024. P. 165–176. DOI: 10.14529/pct2024 (In Russian).
  10. Khairetdinov M. S. Algoritmy potochnoj svertki v zadachah aktivnogo vibrosejsmoakusticheskogo monitoringa / M. S. Khairetdinov, G. M. Voskobojnikova, G. S. Seduhina// Geosibir’, 2017 (In Russian).
  11. Laboratoriya iskusstvennogo intellekta i informacionnyh tehnologiy (In Russian) [Electron. Res.]: https://icmmg.nsc.ru/ru/content/pages/laboratoriya-iskusstvennogo-intellekta-i-informacionnyh-tehnologiy.
  12. Chen L. Deep learning and practice with mindspore. Springer Nature, 2021. DOI: 10.1007/978-981-16-2233-5.
  13. 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.
  14. 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.
  15. 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.
  16. 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.
  17. 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.
  18. 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.

Bibliographic reference: http://problem-info.sscc.ru/ru/node/142#6