Засоби оптимізації розв'язання задач лінійної алгебри на комп'ютерах гібридної архітектури
| dc.contributor.advisor | Дробязко, Ірина Павлівна | |
| dc.contributor.author | Дученко, Олександр Сергійович | |
| dc.date.accessioned | 2022-01-18T13:10:39Z | |
| dc.date.available | 2022-01-18T13:10:39Z | |
| dc.date.issued | 2021 | |
| dc.description.abstracten | Actuality of theme. Computer modeling and conducting appropriate computer experiments are an integral part of modern research and development. The use of computational experiment to solve practical problems allows for multivariate calculations, which significantly reduces the time and cost of the objects being modeled. In many cases, modeling requires the solution of linear algebra problems, which usually take up most of the total time to solve the whole problem. Such problems arise, for example, in construction when calculating the strength of structures, in aircraft construction, mechanical engineering, economics, sociology and more. The matrices of computational problems that arise in mathematical modeling, firstly, have very large orders, and secondly, they are often sparse. To solve such problems, it is necessary to use high-performance computer systems and create algorithms that take into account both the structure of input data and the capabilities of technical means. Hybrid supercomputers are the most effective technology today, such as computers with multi-core processors and graphics accelerators that combine MIMD and SIMD architectures. There are various parallel algorithms and software for solving problems on hybrid computers. However, the problem of increasing productivity remains relevant. When modeling each applied problem, unique systems of linear algebraic equations emerge, which are described by sparse matrices of arbitrary structure. The use of special algorithms for rearranging the elements of a sparse matrix will speed up calculations by increasing data density, reducing the number of interprocess data exchanges etc. The analysis of the structure of the sparse matrix for further selection of the rearrangement algorithm is proposed to be performed using a neural network. Therefore, the increase in the productivity of processing sparse matrices is in the plane of analysis of the input data, namely the structure of the sparse matrix by means of neural networks. The purpose: to optimize the process of solving problems of linear algebra with sparse data structures on computers of hybrid architecture by finding the optimal algorithm for rearranging the elements of matrices. The object of research is the processes of solving problems of linear algebra in computer modeling of complex objects. The subject of research is methods, algorithms and software for solving systems of equations and regularization of the structure of sparse matrices, which are the representation of these systems. Research methods: comparative and empirical methods, neural network theory, machine learning in image classification problems. Scientific novelty: a method for predicting the optimal algorithm for regularization of the structure of a sparse matrix using a reduced image of its structure is proposed; the use of a neural network to perform image analysis of the structure of a sparse matrix is proposed; a software module has been developed that implements the proposed methods for predicting the optimal algorithm for regularizing the structure of a sparse matrix. Practical novelty: the developed optimization tools will increase the efficiency of solving problems of computer modeling of complex objects with matrix calculations, namely: to increase the productivity of calculations and reduce the amount of memory used. Approbation of dissertation results: the main provisions and results of the work were presented and discussed at conferences: Integrated intellectual robotechnical complexes (IIRTC-2021). Fourteenth International Science and Technical Conference May 18-19, 2021, Kyiv, Ukraine. – C.: NAU, 2021; Applied Mathematics and Computing. XIV Scientific and Practical Conference of Undergraduates and Postgraduates of AMC-2021, Faculty of Applied Mathematics, November 17-19, 2021, Kyiv, Ukraine. – C.: KPI, 2021. Publications: 2 scientific papers have been published on the topic of research - abstracts of reports at conferences. Structure and scope of work: the master's dissertation consists of an introduction, four chapters, a conclusion, a list of used sources and appendices. The introduction contains a description of the problems that arise in computer modeling of complex objects and processes, which are described by systems of linear algebraic equations, as well as the relevance of research. The first section contains basic theoretical information on sparse matrices and their application in computer simulation, as well as the main types of matrices. The section provides an overview of the works of both foreign and domestic scientists on the solution of SLARs of very large orders. The second section contains an analysis of well-known algorithms for regularizing the structure of sparse matrices. The section describes neural networks and substantiates the feasibility of their use to solve the problem of analysis of the structure of a sparse matrix. The third section contains a description of the proposed solutions and their software implementation, as well as a software module to predict the optimal algorithm for regularization of the structure of sparse matrices. The fourth section contains an analysis of the results obtained during the experimental research and recommendations for further improvement of the proposed solutions. Conclusions contain the results of the work done. The master's dissertation is presented on XX sheets, contains XX appendices, XX sources, XX figures and XX tables. | uk |
| dc.description.abstractuk | Актуальність теми. Комп’ютерне моделювання та проведення відповідних комп’ютерних експериментів є невід’ємною складовою сучасних наукових досліджень та технічних розробок. Застосування обчислювального експерименту для розв’язання практичних задач дає змогу проводити багатоваріантні розрахунки, що значно скорочує час і вартість об’єктів, які моделюються. У багатьох випадках при моделюванні потрібно розв’язувати задачі лінійної алгебри, що, як правило, займає більшу частину загального часу розв’язування задачі. Такі задачі виникають, наприклад, у будівництві при розрахунку міцності конструкцій, у літакобудуванні, машинобудуванні, економіці, соціології тощо. Матриці розрахункових задач, що виникають при математичному моделюванні, по-перше, мають надвеликі порядки, по-друге, найчастіше вони є розрідженими. Для розв’язування задач такого обсягу необхідно використовувати високопродуктивні комп’ютерні системи та створювати алгоритми, які враховують як структуру вхідних даних, так і можливості технічних засобів. Найбільш ефективними технічними засобами на сьогоднішній день є суперкомп’ютери гібридної архітектури, наприклад, комп’ютери з багатоядерними процесорами та графічними прискорювачами, які поєднують MIMD- та SIMD-архітектури. Для рішення задач на комп’ютерах гібридної архітектури існують різні паралельні алгоритми і відповідне програмне забезпечення. Проте проблема підвищення продуктивності залишається актуальною. При моделюванні кожної прикладної задачі виникають унікальні системи лінійних алгебраїчних рівнянь, які описуються розрідженими матрицями довільної структури. Використання спеціальних алгоритмів перевпорядкування елементів розрідженої матриці дозволить прискорити обчислення шляхом збільшення щільності даних, зменшення кількості міжпроцесних обмінів даними тощо. Аналіз структури розрідженої матриці для подальшого вибору алгоритму перевпорядкування пропонується виконувати за допомогою нейронної мережі. Отже, підвищення продуктивності обробки розріджених матриць знаходиться в площині аналізу вхідних даних, а саме структури розрідженої матриці засобами нейронних мереж. Мета роботи: оптимізація процесу розв’язання задач лінійної алгебри з розрідженими структурами даних на комп’ютерах гібридної архітектури шляхом знаходження оптимального алгоритму перевпорядкування елементів матриць. Об’єктом дослідження є процеси розв’язання задач лінійної алгебри при комп’ютерному моделюванні складних об’єктів. Предметом дослідження є методи, алгоритми та програмні засоби розв’язування систем рівнянь та регуляризації структури розріджених матриць, які є представленням цих систем. Методи досліджень: порівняльний та емпіричний методи, теорія нейронних мереж, машинне навчання в задачах класифікації зображень. Наукова новизна: запропоновано спосіб передбачення оптимального алгоритму регуляризації структури розрідженої матриці, що використовує зменшене зображення її структури; запропоновано використання нейронної мережі для виконання аналізу зображення структури розрідженої матриці; розроблено програмний модуль, що реалізує запропоновані способи передбачення оптимального алгоритму регуляризації структури розрідженої матриці. Практична цінність: розроблені засоби оптимізації дозволять підвищити ефективність вирішення задач комп’ютерного моделювання складних об’єктів з матричними обчисленнями, а саме: підвищити продуктивність обчислень та зменшити обсяг використовуваної пам’яті. Апробація результатів дисертації: основні положення і результати роботи представлені та обговорювались на конференціях: Інтегровані інтелектуальні робототехнічні комплекси (ІІРТК-2021). Чотирнадцята міжнародна науково-практична конференція 18-19 травня 2021 р., Київ, Україна. – К.: НАУ, 2021; Прикладна математика та комп’ютинг. XIV науково-практична конференція магістрантів та аспірантів ПМК-2021 факультету прикладної математики 17 – 19 листопада 2021 р., Київ, Україна. – К.:КПІ, 2021. Публікації: за темою досліджень опубліковано 2 наукові праці – тези доповідей на конференціях. Структура та обсяг роботи: магістерська дисертація складається з вступу, чотирьох розділів, висновку, списку використаних джерел та додатків. Вступ містить опис проблем, що виникають при комп’ютерному моделюванні складних об’єктів та процесів, які описуються системами лінійних алгебраїчних рівнянь, а також актуальність напрямку досліджень. Перший розділ містить основні теоретичні відомості щодо розріджених матриць та їх застосування при комп’ютерному моделюванні, а також основні види матриць. У розділі наведено огляд праць як зарубіжних так і вітчизняних вчених, присвячених розв’язуванню СЛАР надвеликих порядків,. Другий розділ містить аналіз загальновідомих алгоритмів регуляризації структури розріджених матриць. У розділі описано нейронні мережі та обґрунтовано доцільність їх використання для вирішення задачі аналізу структури розрідженої матриці. Третій розділ містить опис запропонованих рішень та їх програмної реалізації, а також програмного модуля для передбачення оптимального алгоритму регуляризації структури розріджених матриць. Четвертий розділ містить аналіз результатів, отриманих під час проведення експериментальних досліджень, та рекомендації щодо подальшого вдосконалення запропонованих рішень. Висновки містять підсумки виконаної роботи. Магістерська дисертація представлена на ХХ аркушах, містить ХХ додатків, ХХ джерел, ХХ рисунків і ХХ таблиць. | uk |
| dc.format.page | 105 с. | uk |
| dc.identifier.citation | Дученко, О. С. Засоби оптимізації розв'язання задач лінійної алгебри на комп'ютерах гібридної архітектури : магістерська дис. : 123 Комп’ютерна інженерія / Дученко Олександр Сергійович. – Київ, 2021. – 105 с. | uk |
| dc.identifier.uri | https://ela.kpi.ua/handle/123456789/45927 | |
| dc.language.iso | uk | uk |
| dc.publisher | КПІ ім. Ігоря Сікорського | uk |
| dc.publisher.place | Київ | uk |
| dc.subject | перевпорядкування елементів | uk |
| dc.subject | нейронна мережа | uk |
| dc.subject | algorithm of rearrangement | uk |
| dc.subject | neural network | uk |
| dc.subject.udc | 004.8 | uk |
| dc.title | Засоби оптимізації розв'язання задач лінійної алгебри на комп'ютерах гібридної архітектури | uk |
| dc.type | Master Thesis | uk |
Файли
Контейнер файлів
1 - 1 з 1
Вантажиться...
- Назва:
- Dudchenko_magistr.pdf
- Розмір:
- 2.48 MB
- Формат:
- Adobe Portable Document Format
- Опис:
Ліцензійна угода
1 - 1 з 1
Ескіз недоступний
- Назва:
- license.txt
- Розмір:
- 9.1 KB
- Формат:
- Item-specific license agreed upon to submission
- Опис: