PETSc - Набір процедур та структур даних для паралельного вирішення наукових задач із моделями, що описуються у вигляді диференціальних рівнянь із частинними похідними. Пропонує лінійні вирішувачі, які реалізовані за допомогою точкового та блокового алгоритму Якобі, адитивного метода, за допомогою LU-, QR-розвинення, метода Крилова та інш. А також - нелінійні вирішувачі, побудовані на методі Ньютона.

    Задача розробки вирішувачів для мережного динамічного об'єкта (МДО) є наступної: для системи , що сформована генератором рівнянь у вигляді, що відображує опис топології МДО, розробити алгоритми та програми вирішення, що є збудованими на послідовних та паралельних чисельних методах.

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

     Серед ряду задач, поставлених для досягнення мети, можна виділити наступні:

Мережний динамічний об’єкт з розподіленими параметрами як об’єкт моделювання

    Мережні об’єкти використовуються у багатьох галузях техніки. Прикладами таких об’єктів можуть бути електричні мережі, нафтопроводи та ін. Об’єктом дослідження є шахтна вентиляційна мережа (ШВМ) [2].

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

    Всі динамічні системи можна розділити на два класи:
- системи з зосередженими параметрами;
- системи з розподіленими параметрами;

     Системи із зосередженими параметрами описуються за допомогою кінцевої кількості алгебраїчних та звичайних диференціальних рівнянь для змінних, які залежать від часу. Системи з розподіленими параметрами описуються за допомогою диференціальних рівнянь у часткових похідних. Тут змінна стану в кожний момент часу – це функція відносно однієї або декількох координат простору. Надалі будемо розглядати перехідні аеродинамічні процеси в ШВМ, елементи якої розглядаються як об’єкти з розподіленими параметрами.

     Топологія мережного об’єкту представляється у вигляді графа. Кожний мережний об’єкт залежить від зовнішніх граничних умов. До них відносяться тиски в початкових вузлах, які з’єднані з атмосферою, та тиски у вузлах, до яких підключені вентилятори, які створюють постійний тиск. Якщо розглядати окрему гілку з індексом і, то процеси зміни значення потоку повітря Q_i та тиску P_i представляються у вигляді наступних рівнянь [2]:

де P_i– значення тиску в і-ій гілці; r_i – питомий аеродинамічний опір;
а – швидкість звуку в повітрі; S_i – площа перетину гілки;
х – координата вздовж гілки.

    Після апроксимації цих рівнянь за методом прямих [1] отримуємо наступні системи рівнянь для j-го елемента гілки, дискретної з шагом :

    Для моделювання ШВМ необхідним кроком є вибір чисельного методу. Відомими є наступні:
- метод Ейлера;
- метод Адамса-Башфорта;
- метод Рунге-Кутта;
- блокові методи.

    Перші три чисельних методи мають одну спільну рису – вони ґрунтуються на послідовних алгоритмах обчислення. Останній метод надає можливість знаходження декількох значень потоку повітря та тиску одночасно, що є актуальним для вирішення таких складних задач з великим обсягом обчислень та може значно зменшити тривалість розрахунків.

Паралельний блоковий чисельний метод

Паралельні блокові чисельні методи розв’язують задачу Коши. Для одного звичайного диференціального рівняння першого порядку задача Коши має наступний вигляд [1]:

    Паралельні блокові чисельні методи розв’язування задачі Коши поділяються на однокрокові та багатокрокові методи. На рис. 1 наведена схема розбиття на N блоків однокрокового k-точкового метода.

Рисунок 1 – Схема розбиття на блоки однокрокового k-точкового метода

    У ході чисельного розв’язування задачі Коши для кожного наступного блока нові k значень обчислюються водночас. На рис. 2 представлено шаблон однокрокової k-точкової різницевої схеми.

Рисунок 2 – Шаблон однокрокової k-точкової різницевої схеми

    Формула для обчислення нових k значень є наступною:

    Для визначення коефіцієнтів a_i,j та b_i треба побудувати інтерполяційний багаточлен Лагранжа L_k(t) із вузлами інтерполяції t_n , i, i = 0,1,…,k та відповідними до них значеннями F_n,i = f(t_n, i, u_n, i) та проінтегрувати у границях (t_n, t_n + i* ) . Для двохточкового блокового методу значення у кожній точці n-блоку треба обчислювати за наступними формулами:

Приклад обчислення однієї гілки ШВМ блоковим чисельним методом.

    Розглянемо невелику гілку ШВМ, що складається лише з чотирьох вузлів.

    Припустимо, що початковий вузол з’єднаний з атмосферою, а до останнього підключені вентилятори, які створюють постійний тиск у гілці. Таким чином, значення тиску на початку та на кінці гілки є постійним. Процеси зміни значення потоку повітря Q та тиску P представляються у вигляді наступних рівнянь:

    Розв’яжемо цю систему рівнянь за паралельним блоковим однокроковим двохточковим методом (k=2). На рис. 3 показано, яким чином підгілки розбиваються на блоки за цим методом.

Рисунок 3 – Розбиття підгілки на блоки за однокроковим двохточковим методом

    Значення потоку повітря Q та тиску P у кожній точці блоку обчислюються за формулами:

    Треба зазначити, що додатковий індекс q є порядковим номером рівнянь у системі. U_n,q,0 – це значення потоку повітря Q або тиску P у початковій точці блоку. У першому блоці ця змінна дорівнює початковим вхідним даним для потоку повітря Q або тиску P. У наступних блоках змінна U_n,q,0 має значення U_n-1,q,2. Обчислимо значення потоку повітря Q₁(1) у точках блоку.

    Обчислимо значення потоку повітря P₂(2) у точках блоку.

    Вирішення такої системи у явному вигляді є неможливим через взаємозалежність правих та лівих частин рівнянь. Обчислити таку систему рівнянь можна за допомогою ітераційного методу. На першій ітерації знаходиться приблизне значення U_n,q,1 та U_n,q,2 , а з кожною наступною ітерацією це значення уточнюється. Припустимо, що S – це номер ітерації. У загальному вигляді кількість ітерацій повинна дорівнювати кількості точок у блоці
    Перша ітерація(S=0):

де і – номер точки (і=1..2), U_n,q,i⁽⁰⁾ – значення U_n,q,i на першій ітерації.

    Наступна ітерація (S=S+1):

Послідовній алгоритм обчислення однієї гілки ШВМ блоковим чисельним методом.

    На рис. 4 наведено загальний послідовний алгоритм обчислення однієї гілки ШВМ паралельним блоковим однокроковим двохточковим методом для одного блока.

Рисунок 4 – Загальний послідовний алгоритм обчислення однієї гілки ШВМ за паралельним блоковим однокроковим двохточковим методом для одного блока

    Було проведено ряд модельних експериментів, метою яких було встановити працездатність послідовної імплементації блокового однокрокового двохточкового методу та порівняння його з послідовною програмою, що реалізує метод Адамса – Башфорта. Об’єктом моделювання є тестова виробка ШВМ з наступними аеродинамічними параметрами: довжина однієї гілки L = 2000 м, площа перетину гілки S=7 м², питомий аеродинамічний опір r_уд = 0.00048 Hc²/м⁹.

    Іншими характеристиками дискретної моделі виробки є: М – кількість елементів довжиною , на які розбивається виробка; – часовий крок апроксимації рівнянь за чисельним методом.
    Результати проведених експериментів привели до наступних висновків:

1. Збільшення чи зменшення часового кроку апроксимації рівнянь призводить до зміни характеру процесів Q₁(t) та Q_M(t) при фіксованому значенні кількості вузлів М в одній гілці та стрибкоподібному впливі Р(t). Від точності вибору часового кроку апроксимації рівнянь залежить ефективність та швидкість тривання технологічного процесу. У іншому випадку процеси Q(t) можуть піти у розбіг.

2. Збільшення кількості вузлів М в одній гілці призводить до збільшення часу тривання технологічного процесу.

3. Реалізація поставленою задачі блоковим чисельним методом, у порівнянні із методом Адамса-Башфорта, дає більший виграш у часі (приблизно у два рази).

    Розроблений послідовний алгоритм обчислення однієї гілки ШВМ паралельним блоковим однокроковим двохточковим методом та дослідження його результатів є першим кроком до побудови паралельного МІМD-вирішувача мережного динамічного об’єкта.

Підхід до розпаралелювання мережних динамічних об’єктів.

     На рисунку 5 представлені чотири можливих рівня розпаралелювання. Обмін даними між процесами здійснюється за допомогою механізму обміну повідомленнями MPI (Message Passing Interface) [5].

     На найнижчому рівні кожний процес займається вирішуванням лише одного рівняння. На другому рівні процесу відводиться вирішення окремою ділянки гілки. На третьому рівні паралельно розраховується кожна гілка або вузол. Та на останньому рівні граф МДО розподіляється на окремі частини.

Рисунок 5 – Рівні розаралелюваня мережних динамічних об’єктів.

    У разі розпаралелення ШВС за першим рівнем, отримуємо наступну схему обміну даними між процесами:

    Якщо піднятися до другого рівня розпаралелювання, на якому кожний процес буде розраховувати значення потоку повітря Q_i та тиску P_i, то схема обміну даними між процесами дещо зміниться:

    Після порівняння наведених вище схем можна побачити, що кількість обмінів даними між процесами на двох рівнях розпаралелювання однакова. Таким чином час передавання даних на другому рівні розпаралелювання ШВО зменшиться в два рази.

Підсумки

У цій роботі була розроблена послідовна імплементація блокового однокрокового двохточкового методу, було проведено ряд експериментів для порівняння її з послідовною програмою, що реалізує метод Адамса – Башфорта.

    Вже розроблені паралельні імплементації обчислення однієї гілки ШВО блоковим методом на перших двох рівнях розпаралелювання.

     Дальше планується провести дослідження останніх двох рівнів розпаралелювання вже всього моделюючого об'єкту та ряд експериментів, щодо ефективності та способів розпаралелювання саме блочного чисельного метода.

Список літератури

1. Фельдман Л.П., Петренко А.І., Дмитрієва О.А. Чисельні методи в інформатиці. – К.:Видавнича група ВНV, 2006. – 480с.
2. Абрамов Ф.А., Фельдман Л.П., Святный В.А. Моделирование динамических процессов рудничной аэрологии.К.:Наук.думка, 1981.–284с.
3. Святный В.А., Молдованова О.В., Перерва Л.О. Проблемно орієнтоване паралельне моделююче середовище для динамічних мережних об’єктів. Наукові праці ДонДТУ, серія «ІКОТ», вип. 29, 2001, с 246-253.
4. C/C++. Программирование на языке высокого уровня / Т.А. Павловская. – СПб.: Питер, 2004. – 461 с.
5. MPI 2.0 Standart www.mpi-forum.org/docs