Назарова Ірина Акопівна. Підвищення ефективності паралельних методів розв'язання динамічних задач в багатопроцесорних обчислювальних системах

Краткое описание

Назарова Ірина Акопівна. Підвищення ефективності паралельних методів розв'язання динамічних задач в багатопроцесорних обчислювальних системах : Дис... канд. наук: 05.13.05 2008

Назарова І.А.Підвищення ефективності паралельних методів розв’язання динамічних задач в багатопроцесорних обчислювальних системах.Рукопис.
Дисертація на здобуття наукового ступеня кандидата технічних наук за спеціальністю 05.13.05 Комп’ютерні системи та компоненти. ДВНЗ «Донецький національний технічний університет», Донецьк, 2008.
Дисертація присвячена розробці паралельних методів розв’язання динамічних задач із зосередженими параметрами, які забезпечують підвищення ефективності експлуатації багатопроцесорних обчислювальних систем (ОС).
У дисертації розроблені явні паралельні методи розв’язання нежорстких динамічних задач з контролем локальної похибки, що збільшують балансування загрузки ОС. Запропоновані нові блокові вкладені та екстраполяційні методи задля прискорення вирішення жорстких задач Коші. Розроблені ефективні паралельні експоненціальні методи інтегрування лінійних задач. Реалізовано масштабований рекурсивно-систоличний алгоритм множення щільно-заповнених матриць. Побудовані відображення методів на паралельні системи SIMD, MIMD, кластерної архітектури різних топологій, досліджено якість потенційного та реального паралелізму, обґрунтовано клас паралельних систем для ефективної організації обчислювальних процесів на основі розроблених методів.

Дослідження, проведені в дисертаційній роботі, є новим рішенням наукової задачі, що полягає в підвищенні ефективності багатопроцесорних комп'ютерних систем за рахунок розробки і обґрунтування паралельних чисельних методів вирішення широкого класу комплексних стратегічних і науково-технічних задач, цілеспрямованої структурної і алгоритмічної організації паралельних обчислювальних процесів.
1. Отримано ефективні паралельні обчислювальні схеми методів оцінки локальної похибки для технології локальної екстраполяції, дублювання кроку і вкладених форм при чисельному рішенні нелінійної задачі Коші на основі явних однокрокових схем. Встановлено, що найменш трудомісткими є схеми з симетричними опорними методами малих порядків точності у поєднанні з парними чисельними послідовностями. Показано, що паралельні методи на основі пропорційного та комбінованого розподілу даних за процесорами є найефективнішими, бо дозволяють збільшити балансування завантаження обчислювальної системи.
2. Запропоновано і теоретично обґрунтовано паралельні методи оцінки локальної апостеріорної похибки чисельного рішення задачі Коші для одного диференційного рівняння на основі неявних однокрокових різницевих схем: блоковий-точковий метод з правилом дублювання кроку; вкладені блокові методи на основіі-точкових методів та з використанням методу послідовного підвищення порядку точності; локальна екстраполяція з блоковим однокроковим опорним методом.
Проведено порівняльний аналіз обчислювальних якостей і ефективності неявних однокрокових методів рішення початкової задачі Коші на основі блокових- точкових методів і- стадійних ПНМРК одного і того ж порядку точності. Встановлено, що динамічні характеристики блокових багатоточкових методів практично враз перевершують відповідні характеристики багатостадійних методів для послідовної реалізації і в для паралельної, де число стадій ПНМРК. Виконано узагальнення розроблених неявних паралельних методів рішення нелінійної задачі Коші для систем звичайних диференційних рівнянь.
3. Розроблено паралельні експоненціальні методи рішення лінійної задачі Коші з правилом Рунге і локальною екстраполяцією Річардсона, вкладені методи. Проведено порівняльний аналіз паралельних алгоритмів на основі матричної експоненти і стандартних схем. Незалежно від способу обчислення локальної похибки експоненціальні алгоритми мають меншу обчислювальну складність і кращі показники якості паралелізму в порівнянні зі своїми стандартними аналогами: для правила Рунге враз, вкладених методів враз, для локальної екстраполяції враз, тут кількість стадій порівнюваного ЯМРК,кількість стадій опорного методу для ЯМРК.
Розроблено ефективний рекурсивно-систоличний метод множення щільно заповнених матриць, що прискорює виконання цієї ресурсоємної операції експоненціального методу.
4. Отримано динамічні характеристики потенційного паралелізму: прискорення, ефективність, ступінь паралелізму для всіх запропонованих методів. Розроблено обчислювальні схеми відображення паралельних алгоритмів на структури паралельних ВС з розподіленою пам'яттю, різними топологіями межпроцесорних зв'язків: лінійка/кільце, сітка/тор, гіперкуб.
Досліджено ефективність отриманих обчислювальних схем відображення паралельних алгоритмів на структури ВС залежно від розмірності процесорних полів, моделі обчислень, орієнтованої на SIMD-, MIMD- і CLUSTER-структури різних топологій, комунікаційних констант. Для найбільш ефективного способу оцінки локальної апостеріорної похибки методів вкладених форм оцінено ступінь масштабованості на основі ізоефективного аналізу.
5. Визначено пріоритетні сфери застосування паралельних алгоритмів у поєднанні з паралельною архітектурою:
для нелінійної задачі Коші найбільш ефективними з точки зору обчислювальних і комунікаційних витрат є паралельні методи середніх і малих порядків на основі явних вкладених форм при використанні MIMD-систем з топологією гіперкуб або кластерів з високошвидкісними мережами;
серед методів розв’язання жорстких СЗДР найбільш ефективними є паралельні методи на основі блокових неявних вкладених форм для MIMD-систем з топологією гіперкуб;
для вирішення лінійної задачі Коші меншу часову складність мають вкладені експоненціальні методи, найбільш ефективною топологією є тор за наявності синхронних систем;
переваги чисельних схем, заснованих на технології локальної екстраполяції, виявляються при пошуку високоточних рішень і домінуванні звернень до правої частини СЗДР в порівнянні з іншими обчисленнями.