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

Размещено на http://www.allbest.ru/

Державний вищий навчальний заклад

«Донецький національний технічний університет»

УДК 519.711.3:681.5.01

Автореферат

дисертації на здобуття наукового ступеня кандидата технічних наук

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

05.13.05 - Комп'ютерні системи та компоненти

Назарова Ірина Акопівна

Донецьк 2008

Загальна характеристика роботи

паралельний метод динамічна задача

Актуальність теми. Застосування паралельних обчислювальних систем стало останнім часом одним з основних напрямків розвитку сучасної комп'ютерної науки у провідних країнах світу. Насьогодні склалося широке коло науково-технічних і комплексних стратегічних задач, вирішення яких неможливе без застосування високопродуктивних обчислювальних систем з паралельною архітектурою. Ефективність їх використання насамперед залежить від рівня розвитку паралельних прикладних методів і відповідних їм паралельних систем програмування. Моделювання багатовимірних динамічних процесів, що описуються системами звичайних диференціальних рівнянь (СЗДР), належить до класу задач, для вирішення яких використання багатопроцесорних структур не лише виправдане, але й необхідне. Вагомі внески до розробки теоретико-математичних основ розпаралелювання обчислень внесли Воєводін В.В., Воєводін Вл.В., Гергель В.П., Gupta A., Kumar D. Проблемам проектування нових багатопроцесорних, кластерних архітектур, Grid-технологій присвячені роботи груп учених під керівництвом Самофалова К.Г., Петренка А.І., Забродіна О.В. Методи підвищення ефективності спеціалізованих паралельних обчислювальних систем досліджувалися в роботах Маліновського Б.Н., Боюна В.П., Каляєва І.А. Не дивлячись на результати численних досліджень в області паралельних обчислень, роботи в цьому напрямку не втрачають своєї актуальності і потребують подальшого розвитку у зв'язку з масовим поширенням паралельних обчислювальних систем.

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

Зв'язок роботи з науковими програмами, планами, темами. Основні дослідження по темі дисертації проводилися на кафедрі прикладної математики і інформатики ДВНЗ ДонНТУ в рамках виконання науково-дослідницьких робіт з держбюджетних тем, які включені до плану фундаментальних досліджень, затверджених МОН України: ГТ-11-2000 «Наукові основи оптимізації структур високопродуктивних обчислювальних систем і методи реалізації паралельних алгоритмів» (№ ДР 0202U002619), Д-1-03 «Методи алгоритмізації, топологічного відображення і оптимізації структур паралельних і розподілених обчислювальних систем» (№ ДР 0103U001824), Д-1-06 «Розробка алгоритмічних методів підвищення ефективності моделювання складних систем в паралельних обчислювальних середовищах» (№ ДР 0106U001266), в яких здобувач приймала участь як виконавець.

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

- аналіз існуючих чисельних методів розв'язання динамічних задач із зосередженими параметрами для систем звичайних диференційних рівнянь, виявлення можливостей та особливостей їх розпаралелювання;

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

- розробка та обґрунтування паралельних методів чисельного розв'язання нелінійних жорстких динамічних задач на основі блокових багатоточкових і повністю неявних однокрокових кінцево-різницевих схем з покроковим контролем локальної похибки;

- підвищення ефективності паралельного розв'язання лінійних задач Коші з контролем похибки на кожному кроці інтегрування;

- відображення отриманих методів на паралельні обчислювальні системи SIMD-, MIMD- та CLUSTER-архітектур з різними топологічними характеристиками і розмірами процесорних полів.

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

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

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

Наукова новизна отриманих результатів полягає в наступному:

- удосконалено явні паралельні методи розв'язання нежорстких динамічних задач на основі екстраполяції Річардсона, що збільшують балансування завантаження за рахунок пропорційного та комбінованого засобів розбиття даних;

- вперше запропоновано та обґрунтовано паралельні блокові вкладені і екстраполяційні методи розв'язання нелінійної задачі Коші для звичайних диференційних рівнянь на основі неявних однокрокових схем, які дозволяють прискорити вирішення жорстких задач;

- вперше запропоновані паралельні методи інтегрування лінійних СЗДР з постійними коефіцієнтами при використанні матричної експоненти на базі альтернативних засобів оцінки локальної похибки, що мінімізують обчислювальні ресурси у порівнянні із стандартними схемами розв'язання задачі Коші;

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

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

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

Результати дисертаційного дослідження використано Державним підприємством «НТЦ проблем енергозбереження» Міністерства вугільної промисловості України для моделювання поведінки багатоканатних скіпових підіймальних установок; в науково-дослідницьких роботах Донецького національного технічного університету: «Наукові основи оптимізації структур високопродуктивних обчислювальних систем і методи реалізації паралельних алгоритмів», «Методи алгоритмізації, топологічного відображення і оптимізації структур паралельних і розподілених обчислювальних систем», «Розробка алгоритмічних методів підвищення ефективності моделювання складних систем в паралельних обчислювальних середовищах»; у навчальному процесі при виконанні науково-дослідницьких, дипломних та магістерських робіт, при підготовці лекційних курсів «Структури обчислювальних систем та паралельні обчислення», «Чисельні методи в інформатиці» на кафедрі ПМІ ДВНЗ ДонНТУ та на кафедрі технічної інформатики у Державному університеті інформатики та штучного інтелекту.

Особистий внесок здобувача. Всі основні положення і результати дисертаційної роботи, що виносяться на захист, отримані автором самостійно.

Апробація результатів роботи. Основні положення і результати дисертаційної роботи були оприлюднені та отримали позитивну оцінку на наступних конференціях та семінарах:

II, ІV Міжнародні науково-практичні семінари «Високопродуктивні паралельні обчислення на кластерних системах», Нижегородський державний університет ім. М. І. Лобачевського, Самарський державний аерокосмічний університет (м. Нижній Новгород, 2002р., м. Самара, 2004р.); V-VIІ Міжнародні науково-практичні конференції «Інтелектуальні і багатопроцесорні системи», Державний університет інформатики та штучного інтелекту, Таганрогський державний радіотехнічний університет (м. Кацивелі, 2004, 2006рр., м. Дивноморськ, 2005р.);

XII, XIV, XVI Міжнародні конференції з обчислювальної механіки та прикладних програмних систем, Російська академія наук, Державний технічний університет «Московський авіаційний інститут» (м. Владимир, 2003р., м. Алушта, 2005-2007рр.); V, VІ Міжнародні науково-практичні конференції студентів, аспірантів та молодих вчених «Системний аналіз та інформаційні технології», Національний технічний університет України «Київський політехнічний інститут», Інститут прикладного системного аналізу (м. Київ, 2003-2004 рр.); Міжнародна наукова конференція «Моделювання-2006», Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України, (м. Київ, 2006р.); V, VI Міжнародні конференції з нерівновагих процесів в соплах і струменях NPNJ, Санкт-Петербурзький державний університет, Балтійський державний технічний університет (м. Самара, 2004р., м. Санкт-Петербург, 2006р.); III міжнародна наукова конференція «Паралельні обчислення і задачі управління» PACO-2006, Інститут проблем управління ім. В.А. Трапезнікова РАН (м. Москва, 2006р.); І, ІІ Міжнародні науково-технічні конференції «Моделювання і комп'ютерна графіка», Донецький національний технічний університет (м. Донецьк, 2005, 2007рр.).

Публікації. Основні результати дисертаційної роботи опубліковані в 29 наукових працях, з них 11 статей у виданнях, включених в перелік ВАК України, 18 публікацій у працях міжнародних наукових конференцій та семінарів, 10 наукових праць написані без співавторів.

Структура і обсяг дисертаційної роботи. Дисертація складається з вступу, 4 розділів, висновків, списку використаних джерел з 128 найменувань, розташованого на 13 сторінках, і додатку. Повний обсяг дисертації складає 183 сторінки друкарського тексту, з них 162 сторінки основного тексту, містить 78 рисунків (у тому числі 21 - на окремих сторінках) і 15 таблиць.

Основний зміст роботи

В першому розділі “Сучасні високопродуктивні обчислювальні системи і паралельні методи розв'язання динамічних задач із зосередженими параметрами” проведено огляд сучасних архітектур та класів високопродуктивних паралельних обчислювальних систем, описано базові топологічні структури, наведено основні принципи і методику розпаралелювання, виконано аналіз динамічних характеристик якості паралельних обчислень, проаналізовано сучасні методи розв'язання динамічних задач, які описуються системами звичайних диференційних рівнянь. На основі огляду відомих робіт зроблені висновки про стан проблеми в досліджуваній області, обґрунтований прийнятий напрям розробок, сформульована мета досліджень. Виконано постановку задачі дисертаційного дослідження, що направлене на підвищення ефективності паралельних обчислювальних систем за рахунок розпаралелювання відомих та розробки нових чисельних методів розв'язання динамічних задач для СЗДР з контролем локальної похибки.

У другому розділі “Підвищення ефективності паралельних обчислювальних систем різних топологій при розв'язанні нелінійної задачі Коші явними однокроковими методами” запропоновані та дослідженні явні методи чисельного розв'язання СЗДР з оцінкою локальної апостеріорної похибки, які використаються для моделювання динамічних систем із зосередженими параметрами. Розроблені методи орієнтовані на використання у паралельних системах SIMD-, MIMD-, CLUSTER-архітектур з розподіленою пам'яттю та різними топологіями з'єднання процесорних елементів та процесорів, значно скорочують час інтегрування, а, отже, й час моделювання поведінки динамічних систем.

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

При чисельному рішенні нелінійної задачі Коші для системи звичайних диференційних рівнянь:

(1)

на основі явних однокрокових -стадійних схем:

(2)

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

1) подвоювання кроку за правилом Рунге;

2) вкладені методи Рунге-Кутти (ВМРК);

3) технологія локальної екстраполяції Річардсона (ЛЕР).

При розробці паралельних обчислювальних схем для локальної екстраполяції досліджені: а) засоби розбиття процесорів на групи, що обчислюють конкретну апроксимацію; б) ступінь впливу порядку та властивостей опорного методу на динамічні характеристики технології в цілому. Визначено, що найменш трудомісткими є чисельні схеми з симетричними опорними методами, які допускають розклад за ступенями , малих порядків точності у поєднанні з парними чисельними послідовностями для генерації сіток інтегрування. Показано, що в наслідок неоднорідності обчислювального процесу ЛЕР паралельні методи на основі пропорційного та комбінованого розподілу даних за процесорами найбільш ефективні, тому що дозволяють збільшити балансування завантаження обчислювальної системи.

У розділі приведено обчислювальні схеми розроблених паралельних методів та їх відображення на різноманітні багатопроцесорні структури з розподіленою пам'яттю. Досліджено ефективність методів в залежності від типу архітектури паралельної обчислювальної системи (SIMD, MIMD і кластери), топології міжпроцесорного з'єднання, комунікаційних констант: латентність та швидкість передачі даних, а також розміру початкової задачі, складності її правої частини. Встановлено, що найбільш ефективними для запропонованих методів являються MIMD-системи топології гіперкуб. Для SIMD-систем звернення до правої частини СЗДР виконуються послідовно, що істотно впливає на характеристики паралелізму: коефіцієнти реального прискорення та ефективності для синхронних систем незначні навіть при тривіальних правих частинах.

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

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

Визначено пріоритетні області застосування розроблених паралельних методів розв'язання динамічних задач у поєднанні з багатопроцесорною архітектурою:

- для методів невеликих порядків найбільш ефективними з точки зору обчислювальних і комунікаційних затрат являються паралельні вкладені методи на базі явних однокрокових схем з топологією гіперкуб;

- переваги явних схем з локальною екстраполяцією Річардсона проявляються при пошуку високоточного розв'язку для складних правих частин.

Третій розділ “Паралельні неявні однокрокові методи чисельного розв'язання жорстких задач та їх реалізація в багатопроцесорних структурах” присвячено розробці, обґрунтуванню та дослідженню ефективності паралельних методів розв'язання динамічних задач на основі неявних однокрокових схем з контролем локальної похибки.

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

- не існує відповідних послідовних аналогів, тому потрібно розробити та обґрунтувати метод оцінки локальної похибки;

- зміна кроку інтегрування можлива тільки після виконання обчислень у всіх вузлах поточного -го блоку;

- при умові незадовільної оцінки локальної похибки практично всі обчислення для точок блоку виявляться даремними (деякі звернення до правої частини СЗДР можуть бути використані знову).

Ідея вкладених форм при застосуванні до блокових методів для ЗДР реалізується на основі двох різних підходів: комбінації незалежних формул суміжних порядків точності; комбінації спеціально підібраних формул різних порядків на базі методу послідовного підвищення порядку точності. Перший підхід полягає у використанні двох різних незалежних блокових методів суміжних порядків точності на одній і тій же сітці інтегрування :

(3)

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

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

(4)

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

(5)

Проведено порівняльний аналіз неявних однокрокових методів розв'язання нелінійної задачі Коші на основі блокових -точкових (БМ) і -стадійних повністю неявних методів Рунге-Кутти (ПНМРК). Для того, щоб порівняння чисельних методів було коректним, необхідно забезпечити один і той же порядок точності наближеного розв'язку, а також отримати рішення у ідентичній кількості нових точок. Показано, що за динамічними характеристиками якості блокові методи перевищують багатостадійні практично в разів для послідовної і в разів - для паралельної реалізацій. Здійснено узагальнення методів, що реалізують різницеві -точкові однокрокові блокові схеми для розв'язання систем звичайних диференційних рівнянь, на основі: системного паралелізму (обмежено розміром СЗДР, m); блокового паралелізму (обмежено кількістю точок у блоці, k). Встановлено, що багатопроцесорна реалізація блокових методів для СЗДР, що використовує обидва типа паралелізму, має найбільшу ефективність як для прискорення обчислень, так і для використання паралельного обладнання.

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

У четвертому розділі “Розробка і аналіз ефективності методів розв'язання лінійної задачі Коші з контролем покрокової похибки для масивно-паралельних систем” запропоновані спеціальні паралельні методи інтегрування лінійних динамічних задач з постійними коефіцієнтами:

(6)

що орієнтовані на використання в MPP-системах типу IBM RS/6000 SP2, Intel Paragon, МВС-1000. Як показали дослідження, урахування специфіки задачі дозволяє отримати більш ефективні паралельні обчислювальні методи, ніж у випадку стандартних чисельних схем. Точний розв'язок задачі Коші виду (6) потребує обчислення матричної експоненти: де . Наближений розв'язок на кроці можна побудувати, використовуючи апроксимацію матричної експоненти відрізком ряду Тейлора:

1) для однорідної системи:

(7)

2) для неоднорідної системи:

(8)

Отримані обчислювальні схеми інтегрування (7)-(8) відповідають різницевому методу порядку , на їх основі побудовані паралельні експоненціальні методи розв'язання лінійної задачі з контролем похибки на кроці. Запропоновані методи особливо ефективні при розв'язанні задач з великою константою Ліпшиця і потребують меншого об'єму обчислень у порівнянні зі стандартними методами рішення задачі (6). Переваги експоненціального методу для реалізації в масивно-паралельних системах:

1) можливість введення підготовчого етапу і винесення в нього найбільш ресурсоємних операцій (матричне множення), не залежних від кроку інтегрування;

2) для вкладених форм застосування експоненціального методу робить практично непотрібними обчислення за формулою вищого порядку точності:

(9)

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

У розділі проведено порівняльний аналіз паралельних методів з використанням матричної експоненти і стандартних явних -стадійних чисельних схем. Встановлено, що незалежно від способу обчислення локальної похибки, паралельні методи, засновані на використанні матричної експоненти, мають меншу тимчасову складність (як теоретичну, так і отриману на основі чисельного експерименту) і кращі показники якості паралелізму в порівнянні із стандартними аналогами. Наприклад, для правила Рунге в , вкладених методів в , для технології локальної екстраполяції в разів, де кількість стадій явного опорного методу. Значення і можуть бути поправлені на величину, що задає різницю між кількістю стадій та порядком точності методу і зростає з ростом порядку методу.

Для прискорення найбільш ресурсоємної операції експоненціального методу, матричного добутку, запропоновано: паралельний алгоритм на основі комбінації швидкого рекурсивного і систоличного алгоритмів; модифікацію систоличного алгоритму, яка знімає обмеження на порядок перемножуваних матриць. Рекурсивно-систоличний метод складається з використання блокового систоличного алгоритму матричного множення на верхньому рівні, між процесорами, і серії застосувань рекурсивного методу Штрассена на нижньому рівні, тобто на кожному з процесорів. Використання розробленого рекурсивно-систоличного методу дозволило в раз прискорити виконання цієї найбільш ресурсоємної операції при вирішенні лінійних СЗДР на основі експоненти. Розроблений алгоритм є таким, що масштабується для будь-якого числа процесорів і будь-якого порядку початкових матриць. Для запропонованого алгоритму визначено оптимальні значення: -глибини рекурсії і величини мінімального блоку перемножуваних матриць. Друга модифікація систоличного алгоритму з блоковим розбиттям виконує послідовну реалізацію систоличного множення блоків матриць порядку, кратного ширині процесорного поля.

Розроблено обчислювальні схеми відображення отриманих паралельних алгоритмів на структури паралельних ВС з розподіленою пам'яттю. Оскільки при рішенні лінійної задачі обчислення є однорідними, то переваги мають SIMD-архітектури. Для MIMD-структур значні витрати на ініціалізацію обмінів компенсуються використанням блокових варіантів алгоритмів. Для даних паралельних застосувань топологічним вирішенням, що адекватно відображує логічний зв'язок між незалежними процесами, є квадратна сітка або її замкнутий еквівалент - 2D-тор. На такій топологічній схемі ефективно виконуються матричні операції, що являються основними складовими експоненціальних форм. Для кожного з наведених алгоритмів розраховано трудомісткості здобуття чисельного вирішення, отримано характеристики паралелізму, які свідчать про високу ефективність експоненціальних методів.

Висновки

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

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

2. Запропоновано і теоретично обґрунтовано паралельні методи оцінки локальної апостеріорної похибки чисельного рішення задачі Коші для одного диференційного рівняння на основі неявних однокрокових різницевих схем: блоковий -точковий метод з правилом дублювання кроку; вкладені блокові методи на основі і -точкових методів та з використанням методу послідовного підвищення порядку точності; локальна екстраполяція з блоковим однокроковим опорним методом.

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

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

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

4. Отримано динамічні характеристики потенційного паралелізму: прискорення, ефективність, ступінь паралелізму для всіх запропонованих методів. Розроблено обчислювальні схеми відображення паралельних алгоритмів на структури паралельних ВС з розподіленою пам'яттю, різними топологіями межпроцесорних зв'язків: лінійка/кільце, сітка/тор, гіперкуб. Досліджено ефективність отриманих обчислювальних схем відображення паралельних алгоритмів на структури ВС залежно від розмірності процесорних полів, моделі обчислень, орієнтованої на SIMD-, MIMD- і CLUSTER-структури різних топологій, комунікаційних констант. Для найбільш ефективного способу оцінки локальної апостеріорної похибки методів вкладених форм оцінено ступінь масштабованості на основі ізоефективного аналізу.

5. Визначено пріоритетні сфери застосування паралельних алгоритмів у поєднанні з паралельною архітектурою:

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

- серед методів розв'язання жорстких СЗДР найбільш ефективними є паралельні методи на основі блокових неявних вкладених форм для MIMD-систем з топологією гіперкуб;

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

- переваги чисельних схем, заснованих на технології локальної екстраполяції, виявляються при пошуку високоточних рішень і домінуванні звернень до правої частини СЗДР в порівнянні з іншими обчисленнями.

Основні результати дисертаційної роботи висвітлено в наступних публікаціях

1. Назарова И.А. Эффективность параллельных алгоритмов оценки локальной апостериорной погрешности для численного решения задачи Коши / Л. П. Фельдман, И. А. Назарова // Электронное моделирование. - 2007. - Т.29, № 3. - С. 11-25.

2. Назарова И.А. Параллельные алгоритмы численного решения задачи Коши для систем обыкновенных дифференциальных уравнений / Л. П. Фельдман, И. А. Назарова // Математическое моделирование. - 2006. - Т.18, № 9. - С. 17-31.

3. Назарова И.А. Параллельные блочные алгоритмы умножения матриц для мультикомпьютеров с распределенной памятью / Л. П. Фельдман, И. А. Назарова, А. В. Хорошилов // Наукові праці Донецького національного технічного університету. Серія: "Інформатика, кібернетика та обчислювальна техніка", випуск 8(120). - Донецьк, ДонНТУ, 2007. - С. 297-309.

4. Назарова И.А. Экспоненциальные методы решения линейной решения задачи Коши с альтернативными способами оценки локальной погрешности для массивно-параллельных компьютерных систем / И. А. Назарова // Научно-теоретический журнал ИПИИ НАН Украины "Искусственный интеллект", №4, 2007. - Донецк: ИПИИ, 2007. - С.474-482.

5. Назарова И.А. Эффективность применения технологии локальной экстраполяции в параллельных алгоритмах численного решения задачи Коши / И. А. Назарова // Научно-теоретический журнал ИПИИ НАН Украины "Искусственный интеллект", №3, 2006. - Донецк: ИПИИ, 2006. - С. 192-202.

6. Назарова И.А. Параллельные полностью неявные методы численного решения жестких задач для СОДУ / И. А. Назарова // Научно-теоретический журнал ИПИИ МОН и НАН Украины "Искусственный интеллект", №3, 2005. - Донецк: ИПИИ, 2005. - С. 185-193.

7. Назарова И.А. Повышение эффективности параллельных вычислительных систем при решении задачи Коши неявными методами Рунге-Кутты / И. А. Назарова // Наукові праці Донецького національного технічного університету. Серія: " Інформатика, кібернетика та обчислювальна техніка", випуск 93. - Донецьк: ДонНТУ, 2005.- С. 58-67.

8. Назарова И.А. Эффективность численного решения нежестких СОДУ с контролем локальной погрешности для компьютеров с распределенной памятью / И. А. Назарова // Научно-теоретический журнал ИПИИ НАН Украины "Искусственный интеллект", №3, 2004. - Донецк: ИПИИ, 2004. - С. 212-215.

9. Назарова И.А. Применение технологии локальной экстраполяции для высокоточного решения задачи Коши на SIMD-структурах / Л. П. Фельдман, И. А. Назарова // Наукові праці Донецького національного технічного університету. Серія: " Інформатика, кібернетика та обчислювальна техніка", випуск 70. - Донецьк: ДонНТУ, 2003. - С. 98-107.

10. Назарова И.А. Особенности использования методов Рунге-Кутты при моделировании параллельных процессов / Л. П. Фельдман, И. А. Назарова // Праці Луганського відділення Міжнародної Академії інформатизації.- Луганськ: Східноукраїнський національний університет ім. В.Даля, 2003. - №2(7). - С. 73-77.

11. Назарова И.А. Параллельная реализация численного решения нежестких обыкновенных дифференциальных уравнений вложенным методом Кутты-Мерсона / Л. П. Фельдман, И. А. Назарова // Наукові праці Донецького національного технічного університету. Серія: "Проблеми моделювання та автоматизації проектування динамічних систем", випуск 52. - Донецьк: ДонНТУ, 2002. - С. 106-112.

12. Назарова И.А. Эффективность параллельных алгоритмов вложенных методов Рунге-Кутты при моделировании сложных динамических систем / Л. П. Фельдман, И. А. Назарова // Материалы II Международного научно-практического семинара "Высокопроизводительные параллельные вычисления на кластерных системах". - Нижний Новгород: Изд-во ННГУ, 2002. - С. 294-301.

13. Назарова И.А. Моделирование сложных динамических систем на базе вложенных методов Рунге-Кутты / Л. П. Фельдман, И. А. Назарова // Сборник трудов международной научно-технической конференции "Компьютерные технологии в управлении, диагностике и образовании". - Тверь: Тверской государственный технический университет, 2002. - С. 150-152.

14. Назарова И.А. Параллельные методы решения СОДУ большой размерности при моделировании сложных систем / И. А. Назарова // Тези доповідей учасників V Міжнародної науково-практичної конференції "Системний аналіз та інформаційні технології". - К.: НТУУ КПІ, 2003. - С. 87-88.

15. Назарова И.А. Методы контроля шаговой погрешности при параллельном решении систем обыкновенных дифференциальных уравнений / Л. П. Фельдман, И. А. Назарова // Тезисы докладов 12 Международной конференции по вычислительной механике и современным прикладным программным системам, Владимир.- М.: МАИ, 2003. - т. 2. - С. 619-620.

16. Назарова И.А. Моделирование сложных динамических систем на высокопроизводительных компьютерах с распределенной памятью / И. А. Назарова, В. А. Шаповалов // Тези доповідей учасників VІ Міжнародної науково-практичної конференції Системний аналіз та інформаційні технології. - К.: НТУУ "КПІ", 2004. - С. 189-191.

17. Назарова И.А. Эффективность параллельного численного решения нежестких систем обыкновенных дифференциальных уравнений с контролем локальной погрешности / И. А. Назарова, Л. П. Фельдман // Тезисы докладов XX Международного семинара по струйным, отрывным и нестационарным течениям. - Санкт-Петербург. - СПб.: ИПЦ СПбГУТД, 2004. - С. 201-202.

18. Назарова И.А. Масштабируемый параллельный алгоритм численного решения линейных СОДУ для компьютеров с распределенной памятью / И. А. Назарова, Л. П. Фельдман // Тезисы докладов V Международной конференции по неравновесным процессам в соплах и струях (NPNJ-2004). - М.: Вузовская книга, 2004. - С. 153-155.

19. Назарова И.А. Эффективность способов оценки апостериорной локальной погрешности при параллельном решении систем линейных однородных ОДУ / Л. П. Фельдман, И. А. Назарова // Материалы четвертого Международного научно-практического семинара "Высокопроизводительные параллельные вычисления на кластерных системах". - Самара: СГАУ, 2004. - С. 255-263.

20. Назарова И.А. Параллельные алгоритмы численного решения задачи Коши для СОДУ / И. А. Назарова // Донбас-2020: наука і техніка - виробництву: Матеріали III науково-практичної конференції. Донецьк, 30-31 травня 2004р. - Донецьк: ДонНТУ Міністерство освіти і науки, 2004. - С. 522 - 527.

21. Назарова И.А. Разработка и анализ эффективности параллельных алгоритмов итерационных методов решения СОДУ для мультипроцессоров с распределенной памятью / И. А. Назарова, Л. П. Фельдман // Материалы международной конференции по вычислительной механике и современным прикладным программным системам. - М.: Вузовская книга, 2005. - С. 343-345.

22. Назарова И.А. Масштабируемые параллельные алгоритмы численного решения жестких систем обыкновенных дифференциальных уравнений для многопроцессорных вычислительных систем с распределенной памятью // Материалы международной научно-технической конференции "Интеллектуальные и многопроцессорные системы: ИМС`2005".- Таганрог-Донецк-Минск: Изд-во ТРТУ, т.1, 2005. - С. 218-220.

23. Назарова И.А. Масштабируемый параллельный алгоритм численного решения задачи Коши для ВС с распределенной памятью / И. А. Назарова // Тези доповідей Міжнародної науково-практичної конференції "Сучасні проблеми і досягнення в галузі радіотехніки, телекомунікацій та інформаційних технологій". - Запоріжжя: ЗНТУ, 2006. - С. 173-175.

24. Назарова И.А. Масштабируемые параллельные алгоритмы численного решения задачи Коши для СОДУ / И. А. Назарова // Сборник трудов международной конференции "Моделирование - 2006". - Киев: Институт проблем моделирования в энергетике им. Г.Е. Пухова НАН Украины, 2006. - С. 335-340.

25. Назарова И.А. Эффективность отображения параллельных алгоритмов численного решения СОДУ на вычислительные структуры различных топологий / Л. П. Фельдман, И. А. Назарова // Материалы седьмой международной научно-технической конференции "Интеллектуальные и многопроцессорные системы: ИМС`2006".- Таганрог: Изд-во ТРТУ, т.1, 2006. - С.269-272.

26. Назарова И.А. Параллельные алгоритмы численного решения задачи Коши для мультипроцессоров с распределенной памятью / Л. П. Фельдман, И. А. Назарова // Труды III международной конференции "Параллельные вычисления и задачи управления" PACO 2006 памяти И.В. Прангишвили. - М.: Институт проблем управления им. В.А. Трапезникова РАН, 2006. - С. 184-196.

27. Назарова И.А. Параллельные экстраполяционные схемы высокоточного решения задачи Коши для мультикомпьютеров с распределенной памятью / И. А. Назарова, Л. П. Фельдман // Тезисы докладов VІ Международной конференции по неравновесным процессам в соплах и струях, 26 июня-1июля 2006 г. Санкт-Петербург. - М.: Вузовская книга, 2006. - С. 255-257.

28. Назарова И.А. Параллельная реализация технологии локальной экстраполяции симметричных методов решения задачи Коши для кластерных систем / Л. П. Фельдман, И. А. Назарова // Материалы XV международной конференции по вычислительной механике и современным прикладным программным системам (ВМСППС-2007), Алушта, Крым, 25-31 мая 2007. - М.: Вузовская книга, 2007. - С. 485-487.

29. Назарова И.А. Алгоритмические методы повышения эффективности параллельных ВС при численном решении СОДУ с контролем погрешности на шаге / И. А. Назарова // Материалы II международной конференции “Моделирование и компьютерная графика”, Донецк: ДонНТУ, 2007. - С. 202-205.

Аннотация

Назарова И.А. Повышение эффективности параллельных методов решения динамических задач в многопроцессорных вычислительных системах. - Рукопись.

Диссертация на соискание ученой степени кандидата технических наук по специальности 05.13.05 - Компьютерные системы и компоненты. - ГВУЗ «Донецкий национальный технический университет», Донецк, 2008.

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

В диссертации разработаны явные параллельные методы решения нежестких динамических задач с контролем локальной апостериорной погрешности, ускоряющие процесс интегрирования и увеличивающие балансировку загрузки параллельной системы за счет пропорционального и комбинационного способов разбиения данных. Для технологии локальной экстраполяции Ричардсона исследованы вопросы оптимального соотношения порядка опорного численного метода, свойств симметричности и способов генерации сеток интегрирования. Для наиболее эффективного способа оценки локальной апостериорной погрешности методов вложенных форм оценена степень масштабируемости. Предложены и обоснованы параллельные методы оценки локальной апостериорной погрешности численного решения задачи Коши для одного дифференциального уравнения на основе блочных неявных одношаговых разностных схем: блочный -точечный метод с правилом дублирования шага; вложенные блочные методы на основе - и -точечных методов и с использованием метода последовательного повышения порядка точности; локальная экстраполяция с блочным одношаговым опорным методом. Проведено обобщение разработанных неявных параллельных методов решения нелинейной задачи Коши на решение систем обыкновенных дифференциальных уравнений.

Проведен сравнительный анализ вычислительных качеств и эффективности неявных одношаговых методов решения общей задачи Коши на основе блочных -точечных методов и -стадийных ПНМРК одного и того же порядка точности. Установлено, что динамические характеристики блочных многоточечных методов практически в раз превосходят соответствующие характеристики многостадийных методов для последовательной реализации и в для параллельной, где - число стадий ПНМРК.

Для линейных динамических задач предложены специальные экспоненциальные параллельные методы интегрирования с контролем погрешности на шаге, позволяющие сократить временные затраты по сравнению со стандартными методами решения. Разработан масштабируемый параллельный метод блочного умножения плотно-заполненных матриц на основе рекурсивного и систолического алгоритмов, ускоряющий выполнение этой ресурсоемкой операции. Проведен сравнительный анализ параллельных алгоритмов интегрирования линейных начальных задач на основе известных численных схем и алгоритмов с использованием матричной экспоненты. Вне зависимости от способа вычисления локальной погрешности, экспоненциальные параллельные методы имеют меньшую вычислительную сложность и лучшие показатели качества параллелизма по сравнению со своими стандартными аналогами.

Для всех разработанных методов построены схемы отображения на параллельные структуры SIMD-, MIMD- и кластерной архитектур с распределенной памятью и различными топологиями межпроцессорных связей: линейка/кольцо, решетка/тор, гиперкуб. Исследовано качество потенциального и реального параллелизма в зависимости от размера процессорного поля, параметров метода и начальной задачи, характеристик коммутационной среды, определены области приоритетного использования параллельных методов в сочетании с параллельной архитектурой, на которой они реализованы.

Результаты диссертационной работы были внедрены в Государственном предприятии «НТЦ проблем энергосбережения» Министерства угольной промышленности Украины для исследования динамики многоканатных скиповых подъемных установок с целью сокращения времени моделирования и оптимизации режима их использования. Предложенные в работе методы использовались в процессе выполнения научно-исследовательских госбюджетных тем кафедры прикладной математики и информатики ГВУЗ ДонНТУ: Н-18-95 «Алгоритмическое и программное обеспечение вычислительных систем и информационных технологий», ГТ-11-2000 «Научные основы оптимизации структур высокопроизводительных вычислительных систем и методы реализации параллельных алгоритмов», Д-1-03 «Методы алгоритмизации, топологического отображения и оптимизации структур параллельных и распределенных вычислительных систем», Д-1-06 «Разработка алгоритмических методов повышения эффективности моделирования сложных систем в параллельных вычислительных средах». Материалы диссертации использовались в учебном процессе при выполнении научно-исследовательских, дипломных и магистерских работ, при подготовке лекционных курсов «Структуры вычислительных систем и параллельные вычисления», «Численные методы в информатике» на кафедре прикладной математики и информатики ГВУЗ ДонНТУ и на кафедре технической информатики Государственного университета информатики и искусственного интеллекта.

Ключевые слова: многопроцессорные вычислительные системы, топология, параллельные методы, многомерные динамические задачи, системы обыкновенных дифференциальных уравнений, коэффициенты эффективности и ускорения.

Анотація

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

Дисертація на здобуття наукового ступеня кандидата технічних наук за спеціальністю 05.13.05 - Комп'ютерні системи та компоненти. - ДВНЗ «Донецький національний технічний університет», Донецьк, 2008.

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

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

Ключові слова: багатопроцесорні обчислювальні системи, топологія, паралельні методи, багатовимірні динамічні задачі, системи звичайних диференціальних рівнянь, коефіцієнти ефективності і прискорення.

Annotation

Nazarova I.А. Rise of the efficiency of the parallel methods to decision of dynamic tasks in multiprocessor calculable systems. - Manuscript.

Thesis for candidate's degree in technical science by specialty 05.13.05 - Computing systems and components. - Donetsk National Technical University, Donetsk, 2008.

Dissertation is devoted development of parallel methods of decision of dynamic tasks with the concentrated parameters, which provide the increase of efficiency of exploitation of the multiprocessor computer systems (OS).

In dissertations the explicit parallel methods for decision nonstiff dynamic tasks with estimations of local a posterior error, that increase balancing of load of OS are worked up. A new block embedded and extrapolation implicit methods to solution of stiff Cauchy's problem are offered. The effective parallel exponential methods of integration of linear tasks are developed. The scalable recursive-systolic algorithm for multiplication of dense matrix is realized. There was built a reflection of methods on the parallel systems of SIMD, MIMD, cluster architecture of different topologies, researched the potential and real parallelism and grounded class of the parallel systems for effective organization of calculable processes on the basis of the developed methods.

Key words: multiprocessor calculable systems, topology, parallel methods, multidimensional dynamic tasks, systems of ordinary differential equations, efficiency and speedup.

...