Sidko A. Runtime for block-recursive matrix algorithms on a supercomputer with distributed memory

Українська версія

Thesis for the degree of Doctor of Philosophy (PhD)

State registration number

0824U002753

Applicant for

Specialization

  • 122 - Комп’ютерні науки

Specialized Academic Board

ДФ 26.314.002

Institute of Software Systems of National Academy of Sciences of Ukraine

Essay

The purpose of the study is to create a new decentralized algorithm for dynamic management of parallel computational processes for block-recursive algorithms and to develop a runtime environment for parallel programs based on this algorithm. The research object is the algorithm for managing the computational process of a multiprocessor computing device (supercomputer) with distributed memory (the runtime's operation algorithm). The subject of the research includes uneven hardware load, the presence of numerical error growth during calculations, and potential physical failures of individual processors. The work employs methods of recursive computations, block matrix calculations, graph theory, algorithm theory, distributed computing, asynchronous computations, dynamic management, and arbitrary-length arithmetic in computational error theory. The scientific results obtained in the dissertation include the proposed methodology for parallelizing matrix block-recursive algorithms, the development of algorithms for a new dynamic decentralized runtime for supercomputers, and the creation of a corresponding software complex designed to solve any matrix tasks that have a block-recursive solution algorithm. A new block-recursive Cholesky decomposition algorithm and a new block-recursive algorithm for inverting a positive-definite symmetric matrix were proposed. An experimental study of the new runtime was conducted using examples of matrix multiplication, Cholesky decomposition, and triangular matrix inversion, demonstrating good scalability of these algorithms. All computational experiments were conducted on the SKIT IC NAS of Ukraine computing complex. The experimental results with the new decentralized dynamic execution environment for all the mentioned algorithms showed good scalability for both dense and sparse matrices with densities of 30% and 3%. This confirms the feasibility of block-recursive parallelization and the correctness of the chosen direction in creating a dynamic supercomputing runtime. The developed software complex can be installed on shared supercomputers as publicly accessible system software. The dissertation materials formed the basis for a textbook on parallel programming and were integrated into the educational process at the National University of Kyiv-Mohyla Academy. The runtime's operation algorithm was implemented in the Java programming language, using OpenMPI for processor communication and MathPartner libraries for matrix operations.

Research papers

Малашонок Г. І. , Сідько А. А. Розподілені обчислення: ДАП-технологія розпаралелювання рекурсивних алгоритмів. Наукові записки НаУКМА. Комп’ютерні науки. Том 1, 2018, с. 25-32. https://doi.org/10.18523/2617-3808.2018.25-32

Сідько А. А. Нова версія середовища виконання MathPar-DAP. Наукові записки НаУКМА. Компʼютерні науки. Том 6, 2023, c. 76-80. https://doi.org/10.18523/2617-3808.2023.6.76-80

Gennadi Malaschonok, Alla Sidko. Supercomputer runtime DAP for matrix block-recursive algorithms. COMPUTER SCIENCE AND INFORMATION TECHNOLOGIES: Selected Papers of CSIT-2021 Conference (27 September–1 October 2021).Yerevan, Armenia. AIP Conference Proceedings. V.2757, Issue 1 (22 May 2023) pp. 0300021-0300027. doi.org/10.1063/5.0137014, ISSN 0094-243X

Малашонок Г. I., А. А. Сiдько. Паралельнi обчислення на розподiленiй пам’ятi: OpenMPI, Java, Math Partner. Пiдручник. Київ: НаУКМА, 2020. – 266 с. ISBN 978-617-7668-14-4

А. Sidko. What’s new in the latest release of MathPar-DAP runtime. Digital Theme UK-Ukraine Research Twinning Conference (27 March – 30 March 2023). https://irp.cdn-website.com/ee30e730/files/uploaded/Final%20Programme%20UA-DIGITAL%202023.pdf

Sidko A., Malaschonok G. Developing the open science infrastructure: a supercomputing platform for large matrix computing. First International Conference "Open Science and Innovation in Ukraine 2022", pp. 24-26. http://doi.org/10.35668/978-966-479-129-5, ISBN: 978-966-479-129-5

Gennadi Malaschonok, Alla Sidko. Supercomputer runtime DAP for matrix block-recursive algorithms. 13th International Conference on Computer Science and Information Technologies (September 2021, Yerevan, Armenia). https://csit.am/2021/proceedings/CHPC/CHPC_1.pdf

Сідько А. А. Малашонок Г.І. Алгоритми децентралізованого управління розподіленими обчисленнями із застосуванням до задач декомпозиції матриць. УкрПрогАсп-2022-1. 1-а Конференція молодих вчених з програмування (26.10.2022, Київ). Зб.матер., ІПС НАНУ, 28 c.

Сідько А.А. Малашонок Г.І. Алгоритми децентралізованого управління розподіленими обчисленнями із застосуванням до задач декомпозиції матриць УкрПрогАсп-2023-2. 2-а Конференція молодих вчених з програмування (17.10.2023, Київ). Зб.матер., ІПС НАНУ, 45 c.

G. I. Malaschonok, A.A. Sidko. Parallel computer algebra: a new scheme for controlling the parallelization of matrix recursive algorithms. Fifth International Conference on High Performance Computing (HPCUA 2018) being held October 22-23, 2018 in Kyiv, Ukraine.

Similar theses