intechnguВестник НГУ. Серия: Информационные технологииVestnik NSU. Series: Information Technologies1818-79002410-0420НГУ10.25205/1818-7900-2024-22-1-5-20intechngu-256Research ArticleСтатьиПостроение комплекса автоматизированной отладки фрагментированных программConstructing a Complex for Automated Debugging of Fragmented Programshttps://orcid.org/0000-0001-8247-5736ВласенкоА. Ю.VlasenkoA. Yu.

Власенко Андрей Юрьевич, кандидат технических наук, доцент кафедры параллельных вычислений ФИТ НГУ, научный сотрудник лаборатории синтеза параллельных программ ИВМиМГ СО РАН

Новосибирск

Andrey Yu. Vlasenko, Candidate of Technical Sciences, Associate Proffessor of the Parallel Computations Department, Novosibirsk State University 

Novosibirsk

a.vlasenko@g.nsu.ruhttps://orcid.org/0000-0002-0404-6802МичуровМ. А.MichurovM. A.

Мичуров Михаил Антонович, ассистент кафедры параллельных вычислений ФИТ

Новосибирск

Mihail A. Michurov, Assistant of the Parallel Computations Department

Novosibirsk

m.michurov@g.nsu.ruЦарёвВ. Д.TsarevV. D.

Царёв Василий Дмитриевич, студент ФИТ 

Новосибирск

Vasiliy D. Tsarev, Student of the Faculty of Information Technologies

Novosibirsk

v.tsarev@g.nsu.ruКурбатовМ. А.KurbatovM. A.

Курбатов Максим Андреевич, студент ФИТ 

Новосибирск

Maksim A. Kurbatov, Student of the Faculty of Information Technologies

Novosibirsk

m.kurbatov@g.nsu.ruНовосибирский государственный университет; Институт вычислительной математики и математической геофизики СО РАНРоссияNovosibirsk State University; Institute of Computational Mathematics and Mathematical Geophysics SB RASRussian FederationНовосибирский государственный университетРоссияNovosibirsk State UniversityRussian Federation202416072024221520Copyright © Власенко А.Ю., Мичуров М.А., Царёв В.Д., Курбатов М.А., 20242024Власенко А.Ю., Мичуров М.А., Царёв В.Д., Курбатов М.А.Vlasenko A.Y., Michurov M.A., Tsarev V.D., Kurbatov M.A.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://intechngu.elpub.ru/jour/article/view/256

В статье кратко изложена концепция фрагментированного программирования, а также принципиальное устройство системы автоматического конструирования параллельных программ LuNA (Language for Numerical Algorithms) и одноименного языка программирования. Описаны такие свойства системы LuNA, как возможность работы на вычислительных системах разных типов, динамическая балансировка нагрузки на узлы и процессорные ядра вычислительного кластера и другие.

Целью описываемой в статье работы является создание программного комплекса отладки фрагментированных программ в системе LuNA. В связи с этим приведен ряд ошибок, специфических для фрагментированных программ. Перечислены подходы к отладке параллельных программ и проанализирована их применимость к фрагментированным программам.

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

The paper is devoted to the authors’ tools for automated debugging of fragmented programs in the LuNA (Language for Numerical Algorithms) system. The LuNA system uses approach of fragmented programming, which allows the researcher to design parallel programs in an automated mode.

The main problem discussed in the paper is the detection of errors specific to LuNA programs. The operation algorithms of four developed tools for automated debugging of LuNA programs are described. Three of them are based on the static analysis approach and differ in the intermediate representations used. The first uses an abstract syntax tree (AST). The second uses a data dependency graph (DDG). The third tool generates a Prolog program containing a set of facts about the original LuNA program and rules corresponding to erroneous situations. Due to the use of various intermediate representations, each of the static analysis tools is able to detect its own types of errors. The last tool uses the “post-mortem analysis” approach. Each process of a parallel program collects a trace file during its operation and at the end of the work these files are analyzed by a special utility.

The paper also describes the developed utility for testing automated debugging tools. The set of test programs with various errors, as well as error-free programs, has been developed  for this utility.

The last part describes the designed mechanism for integrating the developed automated debugging tools into a single software package.

фрагментированное программированиесистема LuNAлогические ошибкиавтоматизированная отладкастатический анализ«посмертный анализfragmented programminglogical errorsautomated debuggingstatic analysis“post-mortem analysis” FundingИсследования выполнены в рамках государственного задания ИВМиМГ СО РАН 0251-2022-0005This work was carried out under state contract with ICMMG SB RAS 0251-2022-0005ReferencesMalyshkin V., Perepelkin V., Lyamin A. Trace Balancing Technique for Trace Playback in LuNA System // Malyshkin V. (Eds) Parallel Computing Technologies. PaCT 2023. Lecture Notes in Computer Science. 2023. Vol. 14098. Springer, Cham. P. 4250. DOI: 10.1007/978-3-031-41673-6_4Malyshkin V., Perepelkin V., Lyamin A. Trace Balancing Technique for Trace Playback in LuNA System. In: Malyshkin, V. (eds) Parallel Computing Technologies. PaCT 2023. Lecture Notes in Computer Science, 2023, vol. 14098. Springer, Cham., pp. 42–50. DOI: 10.1007/978-3-031-41673-6_4.Малышкин В. Э. Технология фрагментированного программирования // Вестник ЮУрГУ. Серия: Вычислительная математика и информатика. 2012. № 46 (305).C. 4555. DOI: 10.14529/cmse120104Malyshkin V. E. Technology of fragmented programming. Vestnik YuUrGU. Series: Computational Mathematics and Software Engineering, 2012, no. 46 (305), pp. 45–55 (in Russ.). DOI: 10.14529/cmse120104Зубов М. В., Пустыгин А. Н., Старцев Е. В. Применение универсальных промежуточных представлений для статического анализа исходного программного кода // Доклады Томского гос. ун-та систем управления и радиоэлектроники. 2013. № 1 (27). С. 64–68.Zubov M. V., Pustygin A. N., Starcev E. V. The use of universal intermediate representations for static analysis of the source code. Reports of Tomsk State University of Control Systems and Radioelectronics, 2013, no. 1(27), pp. 64–68.Flederer F., Ostermayer L., Seipel D., Montenegro S. Source Code Verifi cation for Embedded Systems using Prolog // Electronic Proceedings in Theoretical Computer Science. 2016. Vol. 234. P. 88–103. DOI: 10.4204/EPTCS.234.7Flederer F., Ostermayer L., Seipel D., Montenegro S. Source Code Verifi cation for Embedded Systems using Prolog. Electronic Proceedings in Theoretical Computer Science, 2016, vol. 234, pp. 88–103. DOI: 10.4204/EPTCS.234.7Abramson D. A., Watson G., Le P. D. Guard: a tool for migrating scientifi c applications to the .NET Framework // Sloot P. M. A., Tan C. J. K., Dongarra J. J., & Hoekstra A. G. (Eds.) Computational Science – ICCS 2002: International Conference Amsterdam, The Netherlands, April 21–24, 2002 Proceedings. P. 834843. (Lecture Notes in Computer Science; Vol. 2330). Springer. DOI: 10.1007/3-540-46080-2_88Abramson D. A., Watson G., Le P. D. Guard: a tool for migrating scientifi c applications to the .NET Framework. In P. M. A. Sloot, C. J. K. Tan, J. J. Dongarra, & A. G. Hoekstra (Eds.) Computational Science – ICCS 2002: International Conference Amsterdam, The Netherlands, April 21–24, 2002 Proceedings, pp. 834843. (Lecture Notes in Computer Science; Vol. 2330). Springer. DOI: 10.1007/3-540-46080-2_88Bakhtin V. A., Kataev N. A., Kolganov A. S., Yakobovskiy M. V., Zaharov D. A. Automation of programming for promising high-performance computing systems // Malyshkin V. (eds) Parallel Computing Technologies. PaCT 2023. Lecture Notes in Computer Science. Cham: Springer, 2023. Vol. 14098. P. 3–17.Bakhtin V. A., Kataev N. A., Kolganov A. S., Yakobovskiy M. V., Zaharov D. A. Automation of programming for promising high-performance computing systems. In: Malyshkin V. (eds) Parallel Computing Technologies. PaCT 2023. Lecture Notes in Computer Science, Cham: Springer, 2023, vol. 14098, pp. 3–17.Malyshkin V., Vlasenko A., Michurov M. Automated Debugging of Fragmented Programs in LuNA System // Proc. of Mathematical Modeling and Supercomputer Technologies 2022. Communications in Computer and Information Science. 2022. Vol. 1750. P. 266–280. DOI: 10.1007/978-3-031-24145-1_22Malyshkin V., Vlasenko A., Michurov M. Automated Debugging of Fragmented Programs in LuNA System. Proc. of Mathematical Modeling and Supercomputer Technologies 2022. Communications in Computer and Information Science, 2022, vol. 1750, pp. 266–280. DOI: 10.1007/978-3-031-24145-1_22Protze J., Hilbrich T., Schulz M., de Supinski B. R. MPI Runtime Error Detection with MUST: A Scalable and Crash-Safe Approach // Proc. of 43rd International Conference on Parallel Processing Workshops. Minneapolis, MN, USA, 2014, p. 206–215. DOI: 10.1109/ICPPW.2014.37Protze J., Hilbrich T., Schulz M., de Supinski B. R. MPI Runtime Error Detection with MUST: A Scalable and Crash-Safe Approach. Proc. of 43rd International Conference on Parallel Processing Workshops. Minneapolis, MN, USA, 2014, p. 206–215. DOI: 10.1109/ICPPW.2014.37Карпов Ю. Г. MODEL CHECKING. Верификация параллельных и распределенных программных систем. СПб.: БХВ-Петербург, 2010. 560 с.Karpov J. G. MODEL CHECKING. Verifi cation of parallel and distributed software systems. Saint Petersburg, BHV-Peterburg publ., 2010, 560 p. (in Russ.)Holzmann G. J., Joshi R. Model-Driven Software Verifi cation // Graf S., Mounier L. (Eds) Model Checking Software. Proc. of SPIN 2004. Lecture Notes in Computer Science. Vol. 2989. Springer, Berlin, Heidelberg. P. 76–91. DOI: 10.1007/978-3-540-24732-6_6Holzmann G. J., Joshi R. Model-Driven Software Verifi cation. In: Graf S., Mounier, L. (eds) Model Checking Software. Proc. of SPIN 2004. Lecture Notes in Computer Science. Springer, Berlin, Heidelberg, 2004, vol. 2989, p. 7691. DOI: 10.1007/978-3-540-24732-6_6Fokkink W. Distributed Algorithms, second edition: An Intuitive Approach. MIT Press, 2018.272 p.Fokkink W. Distributed Algorithms, second edition: An Intuitive Approach. MIT Press, 2018, 272 p.Касьянов В. Н., Евстигнеев В. А. Графы в программировании: обработка, визуализация и применение. СПб.: БХВ-Петербург, 2003. 1104 c.Kas’janov V. N., Evstigneev V. A. Graphs in programming: processing, visualization and application. Saint Petersburg, BHV-Peterburg publ., 2003, 1104 p. (in Russ.)Белеванцев А. А. Многоуровневый статический анализ исходного кода программ для обеспечения качества программ // Программирование. 2017.Т. 43, № 6. С. 3–25.Belevancev A. A. Multilevel static analysis of the source code to ensure the quality of programs. Programming and Computer Software, 2017, vol. 43, no. 6, p. 325. (in Russ.)Krinke J. Information Flow Control and Taint Analysis with Dependence Graphs. Vancouver: Proc. of 3d International Workshop on Code Based Software Security Assessments (CoBaSSA). 2007. P. 6–9.Krinke J. Information Flow Control and Taint Analysis with Dependence Graphs. Vancouver: Proc. of 3d International Workshop on Code Based Software Security Assessments (CoBaSSA), 2007, p. 69.Kuck D. J., Kuhn R. H., Padua D. A., Leasure B., Wolfe M. Dependence graphs and compiler optimizations // Proc. of the 8th ACM SIGPLAN-SIGACT symposium on Principles of Programming Languages (POPL). 1981. P. 207–218. DOI: 10.1145/567532.567555Kuck D. J., Kuhn R. H., Padua D. A., Leasure B., Wolfe M. Dependence graphs and compiler optimizations. Proc. of the 8th ACM SIGPLAN-SIGACT symposium on Principles of Programming Languages (POPL), 1981, p. 207218. DOI: 10.1145/567532.567555Smaragdakis Y., Bravenboer M. Using Datalog for Fast and Easy Program Analysis // de Moor O., Gottlob G., Furche T., Sellers A. (Eds) Datalog Reloaded. Lecture Notes in Computer Science. Springer, Berlin, Heidelberg, 2010. Vol. 6702. P. 245–251. DOI: 10.1007/978-3-642-24206-9_14Smaragdakis Y., Bravenboer M. Using Datalog for Fast and Easy Program Analysis. In: de Moor O., Gottlob G., Furche T., Sellers A. (eds) Datalog Reloaded. Lecture Notes in Computer Science.. Springer, Berlin, Heidelberg, 2010, vol. 6702, p. 245251. DOI: 10.1007/978-3-642-24206-9_14

The authors declare that there are no conflicts of interest present.