Efficient Algorithms for Parallelizing Tridiagonal Systems of Equations
Loading...
Date
2021
Journal Title
Journal ISSN
Volume Title
Publisher
НМетАУ, Дніпро
Abstract
ENG: The article is devoted to the development of the maximal parallel forms of mathematical models with a tridiagonal structure. The example of solving the Dirichlet and Neumann problems by the method of straight lines and the sweep method for the heat equation illustrates the direct fundamental features of constructing parallel algorithms. It is noted that the study of the heat and mass transfer processes is run through their numerical modeling based on modern computer technology. It is shown that with the multiprocessor computing systems’ development, there disappear the problems of increasing their peak performance. On the other hand, building such systems, as a rule, requires standard network technologies, mass-produced processors, and free software. The noted circumstances aim at solving the so-called big problems. It should be borne in mind that the classical approach to solving the tridiagonal structure models based on multiprocessor computing systems is far more time-consuming compared to single-processor computing facilities. That is explained by the recurrence relations that make the basis of classical methods. Therefore, the proposed studies are relevant and aim at the distributed algorithms development for solving applied problems. The proposed research aims to construct the maximal parallel forms of mathematical models with a tridiagonal structure. The paper proposes the schemes to implement parallelization algorithms for applied problems and their mapping to parallel computing systems. Parallelization of tridiagonal mathematical models by the method of straight lines and the sweeping method allows designing absolutely stable algorithms with the maximum parallel form and, therefore, the minimum possible time for their implementation on parallel computing devices. It is noteworthy that in the proposed algorithms, the computational errors of the input data are separated from the round-off errors inherent in a PC. The proposed approach can be used in various branches of metallurgical, thermal physics, economics, and ecology problems in the metallurgical industry.
UKR: Статтю присвячено розробці максимально паралельних форм математичних моделей, які мають тридіагональну структуру. Безпосередньо принципові особливості конструювання паралельних алгоритмів ілюструються на прикладі розв’язків задач Діріхле та Неймана методом прямих і методом прогонки для рівнянь теплопровідності. Відзначається, що дослідження процесів тепло - і масообміну реалізується шляхом їх числового моделювання на основі застосування сучасних засобів обчислювальної техніки. Показано, що з розвитком багатопроцесорних обчислювальних систем зникають проблеми в збільшенні їх пікової продуктивності. З іншого боку, для побудови таких систем, як правило, застосовують стандартні мережеві технології, процесори масового виробництва, вільне програмне забезпечення. Зазначені обставини й спрямовані на розв’язок так званих великих задач. При цьому необхідно мати на увазі, що застосування класичного підходу до розв’язку моделей тридіагональних структур на основі використання багатопроцесорних обчислювальних систем відзначаються набагато більшими часовими витратами в порівнянні з однопроцесорними обчислювальними засобами. Це пояснюється застосуванням рекурентних співвідношень, які покладені в основу класичних методів. Отже, для паралельних обчислювальних систем необхідно окремо конструювати процес векторизації обчислень. У зв'язку з цим запропоновані дослідження є актуальними і спрямованими на розвиток розподілених алгоритмів розв’язку прикладних задач. Мета запропонованих досліджень полягає в конструюванні максимально паралельних форм математичних моделей тридіагональних структур. Запропоновані в даній роботі схеми спрямовані на реалізацію алгоритмів розпаралелювання прикладних задач і їх відображення на паралельні обчислювальні системи. Розпаралелювання тридіагональних математичних моделей методом прямих і методом прогонки дозволяє конструювати абсолютно стійкі алгоритми, що мають максимальну паралельну форму і, отже, мінімально можливий час їх реалізації на паралельних обчислювальних пристроях. Помітимо, що в запропонованих алгоритмах відокремлено обчислювальні похибки вхідних даних від похибок округлення, властиві ПЕОМ. Запропонований підхід може бути використаним в різних галузях металургійної теплофізики, економіки, а також задач екології металургійної промисловості.
UKR: Статтю присвячено розробці максимально паралельних форм математичних моделей, які мають тридіагональну структуру. Безпосередньо принципові особливості конструювання паралельних алгоритмів ілюструються на прикладі розв’язків задач Діріхле та Неймана методом прямих і методом прогонки для рівнянь теплопровідності. Відзначається, що дослідження процесів тепло - і масообміну реалізується шляхом їх числового моделювання на основі застосування сучасних засобів обчислювальної техніки. Показано, що з розвитком багатопроцесорних обчислювальних систем зникають проблеми в збільшенні їх пікової продуктивності. З іншого боку, для побудови таких систем, як правило, застосовують стандартні мережеві технології, процесори масового виробництва, вільне програмне забезпечення. Зазначені обставини й спрямовані на розв’язок так званих великих задач. При цьому необхідно мати на увазі, що застосування класичного підходу до розв’язку моделей тридіагональних структур на основі використання багатопроцесорних обчислювальних систем відзначаються набагато більшими часовими витратами в порівнянні з однопроцесорними обчислювальними засобами. Це пояснюється застосуванням рекурентних співвідношень, які покладені в основу класичних методів. Отже, для паралельних обчислювальних систем необхідно окремо конструювати процес векторизації обчислень. У зв'язку з цим запропоновані дослідження є актуальними і спрямованими на розвиток розподілених алгоритмів розв’язку прикладних задач. Мета запропонованих досліджень полягає в конструюванні максимально паралельних форм математичних моделей тридіагональних структур. Запропоновані в даній роботі схеми спрямовані на реалізацію алгоритмів розпаралелювання прикладних задач і їх відображення на паралельні обчислювальні системи. Розпаралелювання тридіагональних математичних моделей методом прямих і методом прогонки дозволяє конструювати абсолютно стійкі алгоритми, що мають максимальну паралельну форму і, отже, мінімально можливий час їх реалізації на паралельних обчислювальних пристроях. Помітимо, що в запропонованих алгоритмах відокремлено обчислювальні похибки вхідних даних від похибок округлення, властиві ПЕОМ. Запропонований підхід може бути використаним в різних галузях металургійної теплофізики, економіки, а також задач екології металургійної промисловості.
Description
G. Shvachych: ORCID 0000-0002-9439-5511; O. Ivashchenko: ORCID 0000-0003-4394-6907; O. Bilyi: ORCID 0000-0003-1234-5404
Keywords
multiprocessor system, tridiagonal structure, method of straight lines, algorithms, thermal physics, parallel forms, багатопроцесорна система, трьохдіагональна структура, метод прямих ліній, алгоритми, теплофізика, паралельні форми, КПМ та ОТ, КЛВ
Citation
Shvachych G. G., Vozna N. J., Ivashchenko O. V., Bilyi O. P., Moroz D. M. Efficient Algorithms for Parallelizing Tridiagonal Systems of Equations. System Technologies. Dnipro, 2021. Т. 5. № 136. С. 110–119. DOI: 10.34185/1562-9945-5-136-2021-11.