ПАРАЛЕЛЬНА РЕАЛІЗАЦІЯ НЕЯВНИХ БЛОКОВИХ ОДНОКРОКОВИХ МЕТОДІВ ЧИСЕЛЬНОГО РОЗВ’ЯЗАННЯ ЖОРСТКОЇ ЗАДАЧІ КОШІ

Автори: Душинська Н.О., Назарова І.А., Фельдман Л.П.
Донецький національний технічний університет
83000, Донецьк, вул. Артема, 58
e-mail: natalya_sufi@mail.ru, nazarova@r5.donntu.ru, feldman@pmi.donntu.ru

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

Розглядається чисельне розв’язання задачі Коші, асоційоване з вирішенням систем звичайних диференційних рівнянь (СЗДР) першого порядку з відомими початковими умовами:

де права частина системи є в загальному випадку нелінійна функція, яка задає відображення

Задля керування кроком інтегрування для однокрокових блокових методів може бути використана ідея вкладених форм, що була запропонована для оцінки локальної похибки чисельного розв’язання звичайних диференціальних рівнянь методами Рунге-Кути. У даному докладі приведено обґрунтування застосування цього способу оцінки похибки для паралельних вкладених блокових алгоритмів рішення нелінійної задачі Коші для ОДУ на основі наступного підходу: комбінації незалежних формул суміжних порядків точності розв’язку.

Підхід полягає у використанні двох різних незалежних блокових методів суміжних порядків точності на одній і тій же сітці інтегрування :

При цьому перший метод визначає апроксимацію вирішення на основі k - точкового однокрокового методу, а другий - точкового також однокрокового методу. Другий наближений розв’язок в співпадаючих вузлах блоків і сітки використовується для оцінки апостеріорної локальної похибки. Нехай для визначеності основним є блоковий метод нижчого порядку точності, тобто . Локальна похибка наближеного розв’язку за однокроковим k-точковим методом в i-том вузлі блоку для одного рівняння визначається наступною формулою: , і для (k+1)- точкового методу в тому ж вузлі дорівнює: З отриманих співвідношень виходить, що оцінка локальної похибки формули меншого порядку точності, k-точкового методу, приблизно може бути обчислена, як: Такий підхід до оцінки локальної похибки є ефективнішим в порівнянні з правилом Рунге, оскільки при достатній простоті дозволяє зменшити обчислювальні витрати. Так, для вживання правила дублювання кроку необхідно вирішити три системи нелінійних алгебраїчних рівнянь розмірності k, а для застосування вкладеного методу дві системи: одну тієї же розмірності, другу розмірності (k+1) .

Потенційно вкладені блокові методи володіють високим ступенем внутрішнього паралелізму: практично лінійним прискоренням і одиничною ефективністю. Це витікає з приведених нижче співвідношень для коефіцієнтів потенційного прискорення і ефективності алгоритму у випадку, якщо час звернення до правої частини ОДУ домінує над іншими обчисленнями:

, ,

де k - число точок у блоці, а p - число використаних процесорів.

Аналогічний результат маємо для тривіальної правої частини. Відмітимо, що вплив чинника “складність правої частини ОДУ” є таким, що багато в чому визначає якість паралелізму. При однакових значеннях комунікаційних констант і параметрів, які задають унікальний блоковий метод, коефіцієнти прискорення і ефективності зменшуються практично в два рази при переході від домінуючих до тривіальних правих частин. Аналіз теоретичного виконання і обчислювальний експеримент показують, що для виконання групових обмінних операцій в запропонованому алгоритмі ефективними є топології гиперкуб і тор, гірший варіант з'єднання процесорів – кільце.

Окрім топології з'єднання, на величину часу міжпроцесорних обмінів і динамічні характеристики паралелізму істотний вплив мають тип паралельної архітектури і визначені їм машино-залежні константи обміну, такі, як латентність і час передачі одного слова. Відмітимо, що із зростанням величини латентності комунікаційної середи час на реалізацію обмінів збільшується, а прискорення і ефективність алгоритму зменшуються. Аналогічні залежності зв'язують динамічні характеристики і час передачі одного слова. Проте величина латентності є найбільш істотним параметром, ступінь впливу швидкості передачі даних, як правило, зростає при збільшенні об'ємів переданих даних. Отже, ступінь впливу комунікаційних констант традиційний для даних методів і операцій обміну. Збільшення числа точок в блоці приводить до зростання коефіцієнту прискорення та к зменшенню коефіцієнту ефективності . Така залежність пояснюється тим, що число точок блоку пов'язане з числом використовуваних процесорів.

Підсумовуючи всі теоретичні результати та отримані експериментальні залежності, можна зробити висновок, що метод вкладених форм для блокових однокрокових способів рішення нелінійної задачі Коші для ОДУ володіє безперечними перевагами перед правилом Рунге та локальною екстраполяцією.

1. Хайрер Э., Ваннер Г. Решение обыкновенных дифференциальных уравнений. Жесткие и дифференциально-алгебраические задачи. – М.: Мир, 1999. – 685с.