Адаптивний алгоритм розв’язання систем рівнянь з блочно-хмарочосними матрицями

Зростаючі вимоги до якості проєктних рішень, а також використання нових конструктивних матеріалів викликають необхідність у розв’язанні якісно нових задач. Також завжди існує потреба у виконанні розрахунків складних унікальних конструкцій. Тому зростає необхідність у нових методах і підходах, пов’яз...

Full description

Saved in:

Bibliographic Details
Published in:	Проблемы управления и информатики
Date:	2022
Main Authors:	Сидорук, В.А., Єршов, П.С.
Format:	Article
Language:	Ukrainian
Published:	Інститут кібернетики ім. В.М. Глушкова НАН України 2022
Subjects:	Керування системами з розподіленими параметрами, математичне моделювання
Online Access:	https://nasplib.isofts.kiev.ua/handle/123456789/210908
Tags:	Add Tag No Tags, Be the first to tag this record!
Journal Title:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Cite this:	Адаптивний алгоритм розв’язання систем рівнянь з блочно-хмарочосними матрицями / В.А. Сидорук, П.С. Єршов // Проблеми керування та інформатики. — 2022. — № 5. — С. 17-31. — Бібліогр.: 11 назв. — укр.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

_version_	1859556173503528960
author	Сидорук, В.А. Єршов, П.С.
author_facet	Сидорук, В.А. Єршов, П.С.
citation_txt	Адаптивний алгоритм розв’язання систем рівнянь з блочно-хмарочосними матрицями / В.А. Сидорук, П.С. Єршов // Проблеми керування та інформатики. — 2022. — № 5. — С. 17-31. — Бібліогр.: 11 назв. — укр.
collection	DSpace DC
container_title	Проблемы управления и информатики
description	Зростаючі вимоги до якості проєктних рішень, а також використання нових конструктивних матеріалів викликають необхідність у розв’язанні якісно нових задач. Також завжди існує потреба у виконанні розрахунків складних унікальних конструкцій. Тому зростає необхідність у нових методах і підходах, пов’язаних із побудовою та дослідженням коректних комп’ютерних моделей, які адекватно відображають реальну роботу конструкцій. Використання деталізованих математичних моделей призводить до суттєвого зростання розмірів розрахункових (дискретних) задач, а отже, і відповідних матриць. Зазвичай такі матриці мають розріджену структуру та надвеликі розміри. У результаті виникають проблеми ефективного збереження, декомпозиції та обробки таких даних. Застосовуючи структурну регуляризацію матриць, можна вирішувати наступні завдання: компактне збереження даних; швидкий доступ до великих масивів даних та їх обробка; мінімізація обмінів даними між обчислювальними пристроями. Для задач із розрідженими симетричними матрицями блочно-хмарочосного виду запропоновано адаптивний паралельний алгоритм прямого методу, який забезпечує високу ефективність розпаралелювання і враховує структуру розріджених матриць та їх наповненість даними. Розроблений алгоритм дозволяє виконати розподіл між процесами обчислення з блоками ненульових елементів трикутного розвинення розрідженої матриці таким чином, щоб вони проводилися одночасно більшістю процесів. Отримано оцінки кількості арифметичних операцій, що виконуються алгоритмом, та коефіцієнта прискорення. Також отримано часові характеристики і показники прискорення при розв’язанні низки практичних задач моделювання міцності будівельних конструкцій нарізній кількості процесорних ядер із застосуванням різної величини блоків, використовуваних для обчислень. The growing demands for the quality of design solutions, as well as the use of new structural materials, create the need to solve qualitatively new tasks. There is also always a need to perform calculations for complex unique structures. Therefore, the need for new methods and approaches related to the construction and study of correct computer models that adequately reflect the real performance of structures is increasing. The use of detailed mathematical models leads to a significant increase in the size of the computational (discrete) problems, and thus, the corresponding matrices. Such matrices usually have a sparse structure and extremely large dimensions. As a result, problems arise regarding the efficient storage, decomposition, and processing of such data. By applying structural regularization of matrices, the following tasks can be solved: compact data storage; fast access to large arrays of data and their processing; and minimization of data exchange between computing devices. For problems with sparse symmetric block-hierarchical matrices, an adaptive parallel direct method algorithm is proposed, which ensures high efficiency in parallelization and takes into account the structure of sparse matrices and their data filling. The developed algorithm allows for the distribution of computation between processes with blocks of non-zero elements of the triangular decomposition of the sparse matrix in such a way that they are carried out simultaneously by most of the processes. Estimates of the number of arithmetic operations performed by the algorithm and the acceleration factor have been obtained. Time characteristics and acceleration indicators are also presented when solving a series of practical tasks for simulating the strength of building structures on a different number of processor cores using various block sizes for calculations.
first_indexed	2026-03-13T14:09:22Z
format	Article
fulltext	© В.А. СИДОРУК, П.С. ЄРШОВ, 2022 Міжнародний науково-технічний журнал Проблеми керування та інформатики, 2022, № 5 17 КЕРУВАННЯ СИСТЕМАМИ З РОЗПОДІЛЕНИМИ ПАРАМЕТРАМИ, МАТЕМАТИЧНЕ МОДЕЛЮВАННЯ УДК 519.6 В.А. Сидорук, П.С. Єршов АДАПТИВНИЙ АЛГОРИТМ РОЗВ’ЯЗАННЯ СИСТЕМ РІВНЯНЬ З БЛОЧНО-ХМАРОЧОСНИМИ МАТРИЦЯМИ Сидорук Володимир Антонович Інститут кібернетики ім. В.М. Глушкова НАН України, м. Київ, wolodymyr.sydoruk@gmail.com Єршов Павло Сергійович Інститут кібернетики ім. В.М. Глушкова НАН України, м. Київ, yershov.pavel.wsk@gmail.com Зростаючі вимоги до якості проєктних рішень, а також використання но- вих конструктивних матеріалів викликають необхідність у розв’язанні якісно нових задач. Також завжди існує потреба у виконанні розрахунків складних унікальних конструкцій. Тому зростає необхідність у нових ме- тодах і підходах, пов’язаних із побудовою та дослідженням коректних комп’ютерних моделей, які адекватно відображають реальну роботу конструкцій. Використання деталізованих математичних моделей приз- водить до суттєвого зростання розмірів розрахункових (дискретних) за- дач, а отже, і відповідних матриць. Зазвичай такі матриці мають розрі- джену структуру та надвеликі розміри. У результаті виникають проблеми ефективного збереження, декомпозиції та обробки таких даних. Застосо- вуючи структурну регуляризацію матриць, можна вирішувати наступні завдання: компактне збереження даних; швидкий доступ до великих ма- сивів даних та їх обробка; мінімізація обмінів даними між обчислюваль- ними пристроями. Для задач із розрідженими симетричними матрицями блочно-хмарочосного виду запропоновано адаптивний паралельний ал- горитм прямого методу, який забезпечує високу ефективність розпарале- лювання і враховує структуру розріджених матриць та їх наповненість даними. Розроблений алгоритм дозволяє виконати розподіл між проце- сами обчислення з блоками ненульових елементів трикутного розвинен- ня розрідженої матриці таким чином, щоб вони проводилися одночасно більшістю процесів. Отримано оцінки кількості арифметичних операцій, що виконуються алгоритмом, та коефіцієнта прискорення. Також отри- мано часові характеристики і показники прискорення при розв’язанні ни- зки практичних задач моделювання міцності будівельних конструкцій на різній кількості процесорних ядер із застосуванням різної величини бло- ків, використовуваних для обчислень. Ключові слова: математичне моделювання, паралельні алгоритми, змінна розрядність, розріджені матриці. 18 ISSN 2786-6491 Вступ З появою та постійним розвитком паралельних комп’ютерів різної архітекту- ри, які використовуються для математичного моделювання в різних галузях науки та інженерії, дуже великої актуальності набувають проблеми їх ефективного ви- користання та підвищення рівня інтелектуальної інформаційної підтримки корис- тувачів — фахівців у різних предметних областях. Постійне зростання потужностей суперкомп’ютерів відбувається за рахунок ускладнення архітектури багатопроцесорних обчислювальних систем [1–3] із роз- поділеною та ієрархічною спільною пам’яттю, зі складною організацією багато- потокових і векторизованих операцій, із застосуванням різного типу прискорюва- чів, різних видів кеш-пам’яті, систем розпаралелення тощо [4–8]. Використання деталізованих математичних моделей призводить до суттєвого зростання розмірів розрахункових (дискретних) задач, а отже, і відповідних мат- риць. Зазвичай такі матриці мають розріджену структуру та надвеликі розміри. У результаті виникають проблеми ефективного збереження, декомпозиції та об- робки таких даних. Застосовуючи структурну регуляризацію матриць, можна ви- рішувати наступні завдання: компактне збереження даних; швидкий доступ до ве- ликих масивів даних та їх обробка; мінімізація обмінів даними між обчислюваль- ними пристроями. Розглядаючи проблему в такій постановці, приходимо до дискретних матема- тичних моделей із надвеликими об’ємами даних, у яких кількість степенів свобо- ди може перевищувати 10 7 . Для ефективної реалізації таких задач не вистачає на- явних обчислювальних ресурсів сучасних персональних комп’ютерів та робочих станцій. Сьогодні підвищення продуктивності та ефективності таких обчислень мож- ливе лише за рахунок використання новітніх високопродуктивних обчислюваль- них систем. Для ефективного використання таких високопродуктивних рішень необхідно розробляти адаптивні алгоритми та програмне забезпечення нового по- коління, що враховуватиме апаратні та системні особливості комп’ютерів, а також особливості розв’язуваної задачі. Наявність практичних задач великих обсягів, які підлягають математичному моделюванню, та велике розмаїття обчислювальної техніки різної архітектури ставлять перед розробниками алгоритмічно-програмного забезпечення нові зав- даня — створювати адаптивні алгоритми [9, 10] та програми з функціями їх авто- матичного налаштування на змінне комп’ютерне середовище (змішана розряд- ність, багаторозрядна арифметика, змінна топологія міжпроцесорних зв’язків, ба- гаторівневий паралелізм, кешизація обчислень тощо), що забезпечує достовірність комп’ютерних результатів розв’язування задач із наближеними даними при ефектив- ному використанні обчислювальних ресурсів для конкретної задачі. Задачі аналізу міцності складних конструкцій або їхніх елементів виникають у багатьох галузях народного господарства, зокрема в будівництві. Зростаючі ви- моги до якості проєктних рішень, а також використання нових конструктивних матеріалів викликають необхідність розв’язання якісно нових задач. Також зав- жди існує необхідність у виконанні розрахунків складних унікальних конструк- цій. Тому зростає потреба в нових методах і підходах, пов’язаних із побудовою та дослідженням коректних комп’ютерних моделей, які адекватно відображають ре- альну роботу конструкцій. Математично лінійні стаціонарні задачі розрахунку міцності конструкцій пі- сля використання принципу можливих переміщень можуть бути поставлені у не- скінченновимірному функціональному просторі можливих переміщень 0U у ви- Міжнародний науково-технічний журнал Проблеми керування та інформатики, 2022, № 5 19 гляді такої варіаційної задачі: знайти вектор-функцію 0Uu , яка для будь-якої вектор-функції 0Uv (будь-якого можливого переміщення) задовольняє інтегра- льній тотожності ),(),( vflvua  , (1) де симетрична білінійна форма (функціонал) ),( vua пропорційна потенційній енергії деформації, а лінійна (по v) форма ),( vfl пропорційна роботі прикладе- них (зовнішніх) зусиль при навантаженні. Тут і далі mkmk WUU ))(()( 2 ),( 0  — простір Соболєва m-вимірних вектор-функцій; nR — m-вимірна скінченна область із досить гладкою границею  ( 3,2,1m ). Також позначимо m v Lf ))(( 2  вектор розподілених об’ємних сил; m s Lf ))(( 2  — вектор розподілених поверхневих сил;               i j j i ij x u x u u 2 1 )( — складові тензора деформацій;  )()( uu ikki     m ji ijijkl uxc 1, )()(  — складові тензора напруг. Припускається, що коефіцієнти пружності )(xcijkl підпорядковано умовам симетрії jiklklijijkl ccc  , і, крім того, вони задовольняють умові )0const( 0 2 1, 0 1,,    ij m ji klijijkl m ikj c . (2) Тоді білінійна та лінійна форми визначаються так: , , , 1 ( , ) ( ) ( ) m ij kl i j k l a u v u v dx     , ( , ) ( ) ( ) ,V Sl f v f v dx f v d         де )( vu  — евклідів скалярний добуток m-вимірних векторів u та v. Необхідна умова існування розв’язку задачі (1) — сукупність усіх сил, які прикладено до пружного тіла, статично еквівалентна нулю, тобто головний вектор і головний момент цих сил мають дорівнювати нулю: 0   dfdxf SV , 0)()(),(    dfrdxfrvfl SV , (3) де r — радіус-вектор точки області , а )( vu  — векторний добуток. Але розв’язок задач (1)–(3) щодо переміщень не єдиний — можливий рух тіла (посту- пальний перенос і жорсткий поворот) як твердого тіла. Для виділення єдиного розв’язку необхідно, щоб виконувались умови 0  udx , 0)(   dxur , (4) перша з яких виключає довільний поступальний перенос, а друга — довільний жорсткий поворот тіла (конструкції). Для тривимірних моделей умови (3) будуть виконуватись, якщо конструкцію закріплено не менше ніж у трьох точках, які не лежать в одній площині. 20 ISSN 2786-6491 Отже, єдиний розв’язок задачі (1)–(3) існує, якщо  )()( ),1( 0  mUuuU , 0  udx , .0)(   dxur Дискретні моделі При дискретизації наближені розв’язки відповідних задач шукаються у скінчен- новимірному підпросторі hU0 простору .0U Використовуються при цьому проєк- ційні методи, наприклад метод скінченних елементів (МСЕ) та метод скінчен- них різниць (МСР). Для отримання дискретної моделі за допомогою МСЕ у формі переміщень зайнята конструкцією область розбивається на скінченні елементи і визначаються вузли та їх степені свободи (зміщення і кути повороту). Степеням свободи відпо- відають базисні (координатні, апроксимуючі) вектор-функції i ),,2,1( Ni  , які задовольняють головним (кінетичним) умовам. Вектор-функції з підпростору hU0 є кусково-поліноміальними і можуть бути представлені у вигляді лінійної комбінації базисних вектор-функцій:    N i iih xU 1 ).()( (5) Тоді відповідна дискретна задача (для лінійного розрахунку міцності конс- трукції) [5, 6] з урахуванням (4), (5) має вигляд системи лінійних алгебраїчних рі- внянь (СЛАР) .Ax b (6) При побудові алгоритму розв’язування СЛАР із розрідженими матрицями особливе значення має вибір способу зберігання ненульових елементів. Однією з найбільш універсальних схем зберігання розріджених матриць є розріджений ря- дковий формат. Згідно з ним значення ненульових елементів матриці та відповідні стовпчикові індекси зберігаються у двох масивах — AN та JA. Використовується також масив вказівників IA, що відмічають позиції масивів AN та JA, з яких почи- нається опис чергового рядка. Додаткова компонента в ІА містить вказівник пер- шої вільної позиції в AN та JA. Розріджений рядковий формат являє собою одну з найбільш використовува- них схем зберігання розріджених матриць. Ця схема висуває мінімальні вимоги до пам’яті та в той же час виявляється надзвичайно зручною для кількох важливих операцій над розрідженими матрицями: додавання, множення, перестановок ряд- ків та стовпчиків, транспонування і розв’язування систем із розрідженими матри- цями коефіцієнтів як прямими, так й ітераційними методами. Проте, схеми зберігання даних загального виду, такі як, наприклад, розрі- джений рядковий формат, не враховують специфіки портрету матриці. Викорис- тання інформації про її особливості при побудові схеми дає змогу прискорити до- ступ до елементів матриці та виконання операцій над ними. Одним із таких прик- ладів є хмарочосна схема [5]. Часто на практиці, наприклад при розрахунку конструкцій, виникають задачі з симетричними матрицями особливої структури. У верхньому трикутнику таких матриць ненульові значення розміщуються вертикальними смугами по кілька сто- впчиків підряд, що на вигляд нагадує хмарочоси. Таким чином, будь-який рядок верхнього трикутника складається з послідовних груп ненульових та нульових елементів. Оскільки ненульові елементи зберігаються групами, зникає необхід- ність зберігати індекси кожного елемента, що дає змогу зменшити розміри індек- сних масивів. У цьому полягає суть хмарочосної схеми. Міжнародний науково-технічний журнал Проблеми керування та інформатики, 2022, № 5 21 Розглядувана схема є модифікаці- єю розрідженого рядкового формату, поширеного на випадок матриць опи- саного виду. Кожен рядок матриці зада- ється трьома масивами. Числові значен- ня елементів матриці зберігаються у ма- сиві А, що має довжину, рівну кількості ненульових елементів рядка, починаючи з діагонального. Цілочислові масиви I та J містять довжини груп ненульових і нульових елементів відповідно і мають розмір, рівний числу таких груп у рядку. Їхня поелементна сума для кожного ряд- ка співпадає з порядком матриці. Ще один цілочисловий масив К містить зна- чення кількості груп кожного рядка. Та- ким чином, якщо групи елементів мають більше двох елементів, хмарочосна схема вимагає зберігати менше індексів, ніж розріджений рядковий формат, а економія пам’яті тим більша, чим об’ємніші групи ненульових та нульових елементів. Приклад хмарочосної матриці представлено на рис. 1. Адаптивний алгоритм розв’язання лінійної системи При розв’язанні СЛАР (6) вирішальну роль у балансуванні завантаження процесів, враховуючи загальну кількість арифметичних операцій, відіграє роз- поділ даних між процесами при виконанні трикутного розвинення матриці. Розподіл між процесами елементів трикутного розвинення розрідженої матри- ці визначає також розподіл решти даних, що задіяні в обчисленнях. Залежно від розподілу даних можна одержати ту чи іншу алгоритмічну реалізацію пев- ного методу. Для алгоритму U T U-розвинення симетричної матриці блочно-хмарочосної структури використано таку схему обчислень. Розглянемо випадок блочно- розрідженої структури даних. Розглянемо комп’ютер із p CPU та спільною пам’яттю. Нехай А — квадратна матриця порядку n. Розіб’ємо матрицю А на блоки розмірністю s* s. Розміри сітки блоків — ,N N де        s n N , за умови, що n націло ділиться на s, інакше              1 s n N . Приклад матриці блочно-хмарочосної структури наведено на рис. 2. Рис. 2 Рис. 1 22 ISSN 2786-6491 Для виконання факторизації матриці на k-му кроці блочного розвинення ви- користаємо таке співвідношення                      22 1211 T 22 T 12 T 11 2221 1211 0 0 U UU UU U AA AA Ak , (7) де розміри блоків 11A — ,s s 12A — ( ) ,N ks s 22A — ( )( ),N ks N ks  а блоки 12A та 22A враховують розріджену структуру матриці A. Опираючись на (7), реалізуємо метод U T U-розвинення для блоків на k-му кроці за формулами 11 T 1111 UUA  , (8) 12 1T 1112 )( AUU   , (9) 12 T 122222 ~ UUAA  . (10) Зазначимо, що реалізація (8)–(10) на кожному кроці модифікує тільки нену- льові блоки матриці А. Для подальшого представлення матеріалу введемо додаткові позначення: )(kNZ — кількість ненульових блоків у k-му рядку блоків верхнього трикутника без діагонального блоку, kjkj UA , — ненульові блоки у k-му рядку блоків верх- нього трикутника. Кожен з p потоків, використовуваних в обчисленнях, працюватиме з p kNZ )( стовпчиками блоків у матриці А. Паралельний алгоритм U T U-розвинення симетричної матриці блочно- хмарочосної структури реалізується таким чином. Факторизуємо діагональний блок kkkkUUA kk T . (11) У всіх потоках модифікуємо позадіагональні блоки з 12 :A NkjAUU kjkkkj ,,1,)( 1T   . (12) У всіх потоках оновлюємо відповідні блоки з 22A за такими співвідно- шеннями ....,,;...,,1, ~ T NijNkiUUAA kjkiijij  (13) Паралельні алгоритми розв’язання систем із блочно-трикутними матри- цями. Одним із етапів розв’язання систем із розрідженою блочно-хмарочосною матрицею є розв’язання систем із блочними трикутними матрицями. Розглянемо відповідний паралельний алгоритм, який дозволяє ефективно реалізувати обчис- лення, використовуючи декомпозицію даних, що була запропонована вище. Паралельний алгоритм розв’язання системи з нижньою блочно-трикутною матрицею реалізується таким чином. Послідовно для кожного i -го )1,2,1,(  Ni  блочного рядка виконуємо такі макрооперації: розв’язуємо систему з нижньою трикутною матрицею ii byU ii T і паралельно у відповідних потоках модифікуємо k -ті частини вектора правих частин ikk yUbb ik T , .,1 Nik  Міжнародний науково-технічний журнал Проблеми керування та інформатики, 2022, № 5 23 Для останнього рядка розв’язується система NNNN byU T . Паралельний алгоритм розв’язання систем із блочною верхньою трикутною матрицею реалізується таким чином:  виконуємо розв’язання системи з верхньою трикутною матрицею: NNNN yxU  . Для і, 1,1  Ni , у зворотному порядку виконуємо мікрооперації:  у відповідних потоках модифікуємо :iy kikii xUyy  ; Nik ,1 ;  виконуємо розв’язання трикутних систем: * iiii yxU  . Оцінки ефективності та прискорення. Оскільки етап знаходження трикут- ного розвинення матриці найбільш складний за часом і кількістю операцій, сума- рне прискорення програми буде визначатись саме прискоренням алгоритму роз- винення. Для оцінки якості паралельних алгоритмів використовуються такі кри- терії, як коефіцієнти прискорення і ефективності, які відповідно можуть бути визначені таким чином (наприклад, див. [4]): Sр = Т1 / Тр, Eр = Sр / р, (14) де р — кількість процесів, що використовуються для розв’язання задачі; Тр — час розв’язання задачі на комп’ютері з використанням р процесів; Т1 — час роз- в’язання тієї ж задачі на гіпотетичному послідовному комп’ютері з швидкодією одного процесора і оперативною пам’яттю, яка дорівнює сумарній пам’яті, що ви- користовується р процесами. Час виконання послідовного алгоритму для знаходження коефіцієнтів (1) можна обчислити так: T1 = O1 t. А час виконання паралельного алгоритму — так: Tp = max {Tp, 1, Tp,2, … , Tp,p}, Tp, i = Tпар, i + Tпосл, i + Tо, i + Tс, i. Тут t — середній час виконання однієї арифметичної операції (додавання або множення) з плаваючою комою; O1 — кількість таких арифметичних опе- рацій у послідовному алгоритмі; Tпар, i — час, що витрачається i-м процесом на паралельні арифметичні операції; Tпосл, i — час, що витрачається i-м проце- сом на послідовні арифметичні операції; Tо, i — час, що витрачається i-м про- цесом на обмін даними з іншими процесорними пристроями; Tс, i — час, що витрачається i-м процесом на синхронізацію з іншими процесорними при- строями. Для багатопроцесорних (багатоядерних) комп’ютерів час Tp можна визначити і так: Tp = Op t + Oо tо + Oс tс , 24 ISSN 2786-6491 де Op — максимальна кількість арифметичних операцій з плаваючою комою, що виконуються одним процесом у паралельному алгоритмі; Oо, tо — максимальний обсяг (кількість машинних слів) обмінів, що виконуються одним процесом, та час, необхідний для обміну одним машинним словом між двома процесами; Ос, tс — максимальна кількість синхронізацій, що виконуються одним процесом, та час, необхідний для синхронізації двох процесів. Теорема 1. Кількість операцій, виконуваних послідовним алгоритмом, до- рівнює                1 1 2 3 3 1 2 )(3 2 3 N k kNZkNZ s Ns O . Доведення. Розглянемо алгоритм факторизації блочно-хмарочосної матриці. Враховуючи розбиття на блоки, отримаємо, що для кожного з N блочних рядків необхідно провести розвинення діагонального блоку (11), для кожного з 1N блочних рядків )(kNZ раз обчислюються макрооперації (12) для оновлення поза- діагональних блоків верхнього трикутника розвинення та 2 )()( 2 kNZkNZ  вико- нати (13) для оновлення всіх блоків відповідної блочної підматриці. Звідси випливають такі оцінки кількості операцій, виконуваних алгоритмом у процесі обчислень.  Факторизація діагональних блоків: 3 3Ns операцій.  Оновлення позадіагональних блоків:    1 1 3 )(2 N k kNZs операцій.  Оновлення значень у блоках підматриці:    1 1 2 3 2 )()( 2 N k kNZkNZ s операцій. Просумувавши ці величини та спростивши вираз, отримуємо співвідношення              1 1 2 3 3 1 2 )(3)( 2 3 N k kNZkNZ s Ns O . Теорему доведено. Теорема 2. Кількість операцій, виконуваних паралельним алгоритмом, до- рівнює              1 1 2 3 3 2 )(3)( 2 3 N k p p kNZkNZ s p Ns O . Доведення. Використавши попередній розподіл даних та інформацію про кі- лькість виконуваних макрооперацій (11)–(13), знайдемо кількість операцій, вико- нуваних одним потоком при виконанні паралельного алгоритму. Оскільки для виконання алгоритму задіяно p потоків і архітектура ком- п’ютера із спільною пам’яттю, це дозволяє для факторизації діагонального блоку використати один з існуючих алгоритмів розвинення щільних матриць на однову- злових комп’ютерах. Кількість операцій, виконуваних одним потоком, тоді буде оцінюватись величиною p Ns 3 3 операцій. Міжнародний науково-технічний журнал Проблеми керування та інформатики, 2022, № 5 25 Оновлення позадіагональних блоків проводиться незалежно у кожному з p потоків, відповідно виконується    1 1 3 )( 2 N k p kNZ s операцій. Оновлення значень у блоках підматриці також виконується у кожному з p потоків:    1 1 2 3 2 )()( 2 N k p kNZkNZ s операцій. Просумувавши ці величини та спростивши вираз, отримуємо співвідношення 3 21 3 1 ( ) 3 ( ) 2 3 2 N p k Ns NZ k NZ k O s p p              . Теорему доведено. Теорема 3. Прискорення паралельного алгоритму оцінюється величиною 21 1 . ( ) 3 ( ) 1 2* 2 p N c k p S Ns NZ k NZ k t p p                   Доведення. Для знаходження величини прискорення використаємо спів- відношення (14). У ньому вже відомі 1O та рO . Оскільки алгоритм передбачає виконання в межах одного вузла та використовує спільну пам’ять, величи- ною oO можна знехтувати, оскільки фізично обміну даними практично не від- бувається. Кількість синхронізацій при виконанні алгоритму можна оцінити величиною 21 1 ( ) 3 ( ) 2 2 N k Ns NZ k NZ k p p                 , оскільки необхідно двічі робити синхронізації потоків, коли розпочинаємо та завершуємо паралельний регіон. Тут p Ns — кількість синхронізацій при виконанні розвинення діагонального блоку,            1 1 2 2 )(3)(N k p kNZkNZ — кількість синхронізацій, що виконуються під час опе- рації оновлення матриці розвинення. Підставивши всі значення у формулу (14) та провівши відповідні спрощення, отримаємо вираз 21 1 . ( ) 3 ( ) 1 2* 2 p N c k p S Ns NZ k NZ k t p p                   Теорему доведено. Апробація алгоритму. На основі запропонованого паралельного алгоритму було створено програмні модулі, які пройшли апробацію під час розв’язання за- дач розрахунку міцності будівельних конструкцій. Для тестів було обрано поста- новки наступних задач: аналіз напружено-деформованого стану фундаменту буді- влі; статичний розрахунок напружено-деформованого стану промислової будівлі; аналіз міцності конструкції багатоповерхового будинку. Апробація проводилась на вузлах 8-вузлового кластера СКІТ-5 [11] з піковою продуктивністю 100 Тфлопс. Кожен вузол має такі характеристики: 192 про- цесорних ядра (2х AMD EPYC 7642); 256 Гбайт оперативної пам’яті; мережа 26 ISSN 2786-6491 передачі даних між вузлами Infiniband HDR — 200 Гбіт/с. Усі вузли інтегровані з загальним сховищем даних кластерного комплексу обсягом 200 Тбайт та пра- цюють під управлінням операційної системи Ubuntu 20.04. Під час програмної реалізації алгоритму застосовувались: технологія OpenMP — для організації паралелізму між потоками та присвоювання блоків хмарочосів відповідним потокам, а також модулі бібліотеки Intel® Math Kernel Library (Intel® MKL) 2019 — для ефективного виконання математичних операцій; опції компілятора, що дозволяють підвищити ефективність індексних операцій та роботи з пам’яттю на різних рівнях, використовувати при обчисленнях додаткові технології (AVX, SSE2) і проводити операції ділення та знаходження квадратного кореня зі збільшеною розрядністю. У представленій далі таблиці наведено результати апробації паралельного ал- горитму на кількох СЛАР із розрідженими матрицями хмарочосного формату. При цьому для кожної з задач проводилося розв’язання з матрицею вихідної (не- оптимізованої) та переупорядкованої (оптимізованої) структури за допомогою ал- горитму мінімального степеня; у таблиці дані випадки розрізняються значеннями ширини стрічки та заповнення профілю матриць. Таблиця Порядок Ширина стрічки, елементів Наповненість ненульовими елементами, % 1 8 16 32 64 128 44 436 4475 21 0,3 0,0621 0,029 0,016 0,026 0,033 44 436 37 580 2 0,26 0,05 0,0275 0,012 0,018 0,087 283 031 19 530 7 32 5,95 2,77 1,3 1,013 1,45 283 031 281 341 1 5,38 0,83 0,54 0,28 0,18 0,35 661 590 34 242 5 98,8 17,6 10,08 5,47 3,45 5,22 661 590 541 257 1 32,45 5,17 3,08 1,57 1,01 1,55 Далі наведено залежності прискорення алгоритму від кількості процесів для представлених у таблиці задач. Випадок із матрицею вихідної структури позначе- но як «О», а з переупорядкованою структурою — як «П». Статичний розрахунок напружено-деформованого стану промислової споруди. Загальний вигляд конструкції та використовувану скінченно-елементну сітку представлено на рис. 3. Рис. 3 Міжнародний науково-технічний журнал Проблеми керування та інформатики, 2022, № 5 27 Конструкцію розбито на 13 876 скінченних елементів. У результаті сформо- вано скінченно-елементну сітку з 7563 вузлами. Після дискретизації отримано СЛАР із матрицею порядку 44 436. Матриця цієї системи до застосування алгоритму впорядкування має стрічкову структуру (рис. 4, ліворуч) зі щільністю (заповненіс- тю) 21 %. Після застосування алгоритму мінімальної степені для зміни впорядку- вання ненульових елементів матриці вдалося зменшити заповненість до 2 %, хоча при цьому ширина пів стрічки зросла (з 4476 до 27 850). Структуру оптимізованої матриці (до та після упорядкування елементів) представлено на рис. 4, праворуч. Рис. 4 На рис. 5 показано графіки прискорення при розв’язанні СЛАР із матрицями оптимізованої та оригінальної структур із використанням різної кількості потоків та розміром блоку 128 (залежність прискорення від кількості потоків для СЛАР 44 436-го порядку). Рис. 5 Статичний розрахунок напруго-деформованого стану багатоповерхового житлового будинку. Загальний вигляд конструкції багатоповерхового житлового будинку та використана скінченно-елементна сітка представлені на рис. 6, ліво- руч. Конструкція розбита на 121 761 скінченний елемент. Відповідна скінченно- елементна сітка містить 110 265 вузлів. «О» «П» 28 ISSN 2786-6491 Рис. 6 У результаті дискретизації отримано СЛАР порядку 661 590. Вихідна струк- тура матриці цієї системи мала щільність 5 % і півширину стрічки 34 242 (рис. 6, зверху праворуч). Після оптимізації структури матриці щільність впорядкованої структури складала 1 % при пів ширині стрічки, рівній 541 257 (рис. 6, внизу праворуч). На рис. 7 показано графіки прискорень, отриманих при розв’язанні задачі з відповідними розрідженими матрицями на різній кількості потоків із використан- ням розміру блоку 256 (залежність прискорення від кількості потоків для СЛАР 661 590-го порядку). Рис. 7 Аналіз напружено-деформованого стану фундаменту будівлі. Загальний вигляд конструкції фундаменту та використану скінченно-елементну сітку пред- ставлено на рис. 8, внизу. Конструкція розбита на 94 346 скінченних елементів. Відповідна скінченно-елементна сітка містить 97 412 вузлів. У результаті дискретизації отримано СЛАР порядку 283 031. Вихідна струк- тура матриці цієї системи мала щільність 7 % і пів ширину стрічки 19 530 (рис. 8, зверху ліворуч). Після оптимізації структури матриці щільність впорядкованої структури складала 1 % при пів ширині стрічки, що дорівнює 281 341 (рис. 8, зве- рху праворуч). «О» «П» Міжнародний науково-технічний журнал Проблеми керування та інформатики, 2022, № 5 29 Рис. 8 На рис. 9 показано графіки прискорень, отриманих при розв’язанні задачі, з відповідними розрідженими матрицями на різній кількості потоків із використан- ням розміру блоку 160 (залежність прискорення від кількості потоків для СЛАР 283 031-го порядку). Рис. 9 Наведені в таблиці та на рис. 5, 7, 9 результати демонструють залежність ха- рактеристик алгоритму (часу розв’язання задачі, прискорення) від збалансованос- ті завантаження процесів. При цьому чим менший порядок системи, тим складні- ше досягти збалансованості при нарощуванні числа процесів (див. графік на рис. 5). Також проведені дослідження вказують, що значний вплив на прискорен- ня обчислень має і розмір блоку, з яким виконуються обчислення, оскільки він впливає як на швидкість послідовних операцій, так і на кількість операцій, які можуть бути виконані паралельно. Висновок Для задач із розрідженими симетричними матрицями блочно-хмарочосного виду запропоновано адаптивний паралельний алгоритм прямого методу, який за- безпечує високу ефективність розпаралелювання, а також враховує структуру ро- зріджених матриць та їхню наповненість даними. Розроблений алгоритм дозволяє провести розподіл обчислень із блоками ненульових елементів трикутного розви- нення розрідженої матриці таким чином, щоб вони проводилися одночасно біль- шістю процесів. «О» «П» 30 ISSN 2786-6491 Отримано оцінки кількості арифметичних операцій, що виконуються алгори- тмом, та коефіцієнта прискорення. Також отримано часові характеристики та по- казники прискорення при розв’язанні низки практичних задач моделювання міц- ності будівельних конструкцій на різній кількості процесорних ядер із застосу- ванням різної величини блоків, використовуваних для обчислень. Подальші дослідження доцільно направити на пошук алгоритмів переупоря- дкування розріджених матриць, які забезпечували б найвищу ефективність пара- лельних алгоритмів вирішення задач лінійної алгебри, в першу чергу — за раху- нок збалансованості завантаження процесів. V. Sydoruk, P. Yershov ADAPTIVE ALGORITHM FOR SOLVING SYSTEMS OF EQUATIONS WITH BLOCK-SKYSCRAPER MATRICES Volodymyr Sydoruk V.M. Glushkov Institute of Cybernetics of NAS of Ukraine, Kyiv, wolodymyr.sydoruk@gmail.com Pavlo Yershov V.M. Glushkov Institute of Cybernetics of NAS of Ukraine, Kyiv, yershov.pavel.wsk@gmail.com Increasing requirements for the quality of design solutions, as well as the use of new structural materials necessitates the solution of qualitatively new problems. There is always a need to perform calculations of complex unique structures. Therefore, there is a growing need for new methods and ap- proaches related to the construction and study of correct computer models that adequately reflect the real operation of structures. Use of detailed math- ematical models leads to a significant increase in the size of computational (discrete) problems, and hence the corresponding matrices. Usually, such matrices have a sparse structure and extremely large sizes. As a result, there are problems of efficient storage, decomposition and processing of such da- ta. Using structural regularization of matrices it is possible to solve the fol- lowing problems: compact data storage; fast access and processing of large data sets; minimization of data exchanges between computing devices. For the tasks with sparse symmetric matrices of block-skyscraper type, an adap- tive parallel algorithm of the direct method is proposed, which provides high parallelization efficiency, takes into account the structure of sparse matrices and their data content. The developed algorithm allows to distribute between the processes of calculations with blocks of non-zero elements of the trian- gular development of the sparse matrix so that they are carried out simulta- neously by most processes. Estimates of the number of arithmetic operations performed by the algorithm and the speedup factor are obtained. Also ob- tained time characteristics and acceleration rates in solving a number of practical problems of modeling the strength of building structures on differ- ent numbers of processor cores using different sizes of blocks used for cal- culations. Keywords: mathematical modeling, parallel algorithms, variable precision, sparse matrices. Міжнародний науково-технічний журнал Проблеми керування та інформатики, 2022, № 5 31 REFERENCES 1. Sergienko I.V., Molchanov I.N., Khimich A.N. Intelligent technologies of high-performance computing. Cybernetics and Systems Analysis. 2010. Vol. 46 (5). P. 833–844. https://doi.org/ 10.1007/s10559-010-9265-3. 2. Dongarra J., Beckman P., Moore T. et al. The international exascale software project roadmap. The International Journal of High Performance Computing Applications. 2011. Vol. 25 (1). P. 3–60. doi:10.1177/1094342010391989. 3. Сергієнко І.В., Хіміч О.М. Математичне моделювання: Від мелм до екзафлопсів. Вісник НАН України. 2019. № 8. С. 37–50. 4. Khimich A.N., Molchanov I.N., Popov A.V., Chistyakova T.V., and Yakovlev M.F. Paral- lel algorithms to solve problems in calculus mathematics. Kyiv : Naukova Dumka, 2008. 247 с. 5. Khimich A.N., Popov A.V., Polyankova V.V. Algorithms of parallel computations for linear algebra problems with irregularly structured matrices. Cybernetics and Systems Analysis. 2011. Vol. 47. P. 973–985. https://doi.org/10.1007/s10559-011-9377-4. 6. Baranov A.Yu., Popov A.V., Slobodyan Y.E., and Khimich A.N. Mathematical modeling of building constructions using hybrid computing systems. Journal of Automation and Information Sciences. 2017. Vol. 49, N 7. P. 18–32. 7. Khimich A.N., Popov A.V., and Chistyakov O.V. Hybrid algorithms for solving the algebraic eigenvalue problem with sparse matrices. Cybernetics and Systems Analysis. 2017. Vol. 53, N 6. P. 937–949. https://doi.org/10.1007/s10559-017-9996-5. 8. Khimich O.M., Popov O.V., Chistyakov O.V. et al. A parallel algorithm for solving a partial eigenvalue problem for block-diagonal bordered matrices. Cybernetics and Sys- tems Analysis. 2020. Vol. 56. P. 913–923. https://doi.org/10.1007/s10559-020-00311-z. 9. Khimich O.M., Chistyakova T.V., Sidoruk V.A. et al. Adaptive computer technologies for solving problems of computational and applied mathematics. Cybernetics and Systems Analysis. 2021. Vol. 57. P. 990–997. https://doi.org/10.1007/s10559-021-00424-z. 10. Khimich A., Chistyakova T., Sydoruk V., Yershov P. Adaptive algorithms for researching problems in a variable computer environment. Physico-mathematical modelling and infor- mational technologies. 2021. Vol. 33. P. 181–185. https://doi.org/10.15407/fmmit2021. 33.081. http://icybcluster.org.ua/index.php?lang_id=2&menu_id=5. Отримано 07.12.2022 https://doi.org/10.1007/s10559-010-9265-3 https://doi.org/10.1007/s10559-010-9265-3 https://doi.org/10.1177/1094342010391989 https://doi.org/10.1007/s10559-017-9996-5 https://doi.org/10.1007/s10559-020-00311-z https://doi.org/10.1007/s10559-021-00424-z
id	nasplib_isofts_kiev_ua-123456789-210908
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
issn	0572-2691
language	Ukrainian
last_indexed	2026-03-13T14:09:22Z
publishDate	2022
publisher	Інститут кібернетики ім. В.М. Глушкова НАН України
record_format	dspace
spelling	Сидорук, В.А. Єршов, П.С. 2025-12-20T14:11:16Z 2022 Адаптивний алгоритм розв’язання систем рівнянь з блочно-хмарочосними матрицями / В.А. Сидорук, П.С. Єршов // Проблеми керування та інформатики. — 2022. — № 5. — С. 17-31. — Бібліогр.: 11 назв. — укр. 0572-2691 https://nasplib.isofts.kiev.ua/handle/123456789/210908 519.6 10.34229/2786-6505-2022-5-2 Зростаючі вимоги до якості проєктних рішень, а також використання нових конструктивних матеріалів викликають необхідність у розв’язанні якісно нових задач. Також завжди існує потреба у виконанні розрахунків складних унікальних конструкцій. Тому зростає необхідність у нових методах і підходах, пов’язаних із побудовою та дослідженням коректних комп’ютерних моделей, які адекватно відображають реальну роботу конструкцій. Використання деталізованих математичних моделей призводить до суттєвого зростання розмірів розрахункових (дискретних) задач, а отже, і відповідних матриць. Зазвичай такі матриці мають розріджену структуру та надвеликі розміри. У результаті виникають проблеми ефективного збереження, декомпозиції та обробки таких даних. Застосовуючи структурну регуляризацію матриць, можна вирішувати наступні завдання: компактне збереження даних; швидкий доступ до великих масивів даних та їх обробка; мінімізація обмінів даними між обчислювальними пристроями. Для задач із розрідженими симетричними матрицями блочно-хмарочосного виду запропоновано адаптивний паралельний алгоритм прямого методу, який забезпечує високу ефективність розпаралелювання і враховує структуру розріджених матриць та їх наповненість даними. Розроблений алгоритм дозволяє виконати розподіл між процесами обчислення з блоками ненульових елементів трикутного розвинення розрідженої матриці таким чином, щоб вони проводилися одночасно більшістю процесів. Отримано оцінки кількості арифметичних операцій, що виконуються алгоритмом, та коефіцієнта прискорення. Також отримано часові характеристики і показники прискорення при розв’язанні низки практичних задач моделювання міцності будівельних конструкцій нарізній кількості процесорних ядер із застосуванням різної величини блоків, використовуваних для обчислень. The growing demands for the quality of design solutions, as well as the use of new structural materials, create the need to solve qualitatively new tasks. There is also always a need to perform calculations for complex unique structures. Therefore, the need for new methods and approaches related to the construction and study of correct computer models that adequately reflect the real performance of structures is increasing. The use of detailed mathematical models leads to a significant increase in the size of the computational (discrete) problems, and thus, the corresponding matrices. Such matrices usually have a sparse structure and extremely large dimensions. As a result, problems arise regarding the efficient storage, decomposition, and processing of such data. By applying structural regularization of matrices, the following tasks can be solved: compact data storage; fast access to large arrays of data and their processing; and minimization of data exchange between computing devices. For problems with sparse symmetric block-hierarchical matrices, an adaptive parallel direct method algorithm is proposed, which ensures high efficiency in parallelization and takes into account the structure of sparse matrices and their data filling. The developed algorithm allows for the distribution of computation between processes with blocks of non-zero elements of the triangular decomposition of the sparse matrix in such a way that they are carried out simultaneously by most of the processes. Estimates of the number of arithmetic operations performed by the algorithm and the acceleration factor have been obtained. Time characteristics and acceleration indicators are also presented when solving a series of practical tasks for simulating the strength of building structures on a different number of processor cores using various block sizes for calculations. uk Інститут кібернетики ім. В.М. Глушкова НАН України Проблемы управления и информатики Керування системами з розподіленими параметрами, математичне моделювання Адаптивний алгоритм розв’язання систем рівнянь з блочно-хмарочосними матрицями Adaptive algorithm for solving systems of equations with block-skyscraper matrices Article published earlier
spellingShingle	Адаптивний алгоритм розв’язання систем рівнянь з блочно-хмарочосними матрицями Сидорук, В.А. Єршов, П.С. Керування системами з розподіленими параметрами, математичне моделювання
title	Адаптивний алгоритм розв’язання систем рівнянь з блочно-хмарочосними матрицями
title_alt	Adaptive algorithm for solving systems of equations with block-skyscraper matrices
title_full	Адаптивний алгоритм розв’язання систем рівнянь з блочно-хмарочосними матрицями
title_fullStr	Адаптивний алгоритм розв’язання систем рівнянь з блочно-хмарочосними матрицями
title_full_unstemmed	Адаптивний алгоритм розв’язання систем рівнянь з блочно-хмарочосними матрицями
title_short	Адаптивний алгоритм розв’язання систем рівнянь з блочно-хмарочосними матрицями
title_sort	адаптивний алгоритм розв’язання систем рівнянь з блочно-хмарочосними матрицями
topic	Керування системами з розподіленими параметрами, математичне моделювання
topic_facet	Керування системами з розподіленими параметрами, математичне моделювання
url	https://nasplib.isofts.kiev.ua/handle/123456789/210908
work_keys_str_mv	AT sidorukva adaptivniialgoritmrozvâzannâsistemrívnânʹzbločnohmaročosnimimatricâmi AT êršovps adaptivniialgoritmrozvâzannâsistemrívnânʹzbločnohmaročosnimimatricâmi AT sidorukva adaptivealgorithmforsolvingsystemsofequationswithblockskyscrapermatrices AT êršovps adaptivealgorithmforsolvingsystemsofequationswithblockskyscrapermatrices

Адаптивний алгоритм розв’язання систем рівнянь з блочно-хмарочосними матрицями

Institution

Similar Items