НАЦІОНАЛЬНА АКАДЕМІЯ НАУК УКРАЇНИ

ІНСТИТУТ ПРОБЛЕМ МОДЕЛЮВАННЯ В ЕНЕРГЕТИЦІ ім. Г.Є. ПУХОВА

СОЛОНІН ОЛЕКСАНДР МИКОЛАЙОВИЧ

УДК 683.1

ОПТИМАЛЬНА ОРГАНІЗАЦІЯ ПРОЦЕСІВ МОДЕЛЮВАННЯ В ПАРАЛЕЛЬНОМУ МОДЕЛЮЮЧОМУ СЕРЕДОВИЩІ

Спеціальність 01.05.02 - “Математичне моделювання та обчислювальні методи”

АВТОРЕФЕРАТ

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

кандидата технічних наук

Київ - 2007

Дисертацією є рукопис.

Робота виконана в Донецькому національному технічному університеті Міністерства освіти та науки України.

Науковий керівник | д.т.н., професор Святний Володимир Андрійович, завідувач кафедри “Електронні обчислювальні машини” Донецького національного технічного університету

Офіційні опоненти: | д.т.н., професор Саух Сергій Євгенович, головний науковий співробітник Інституту проблем моделювання в енергетиці ім. Г.Є. Пухова
НАН України

к.т.н. Ладиженський Юрій Валентинович, доцент кафедри прикладної математики та інформатики Донецького національного технічного університету

Провідна установа | Національний технічний університет України “КПІ”, кафедра автоматизованих систем обробки iнформацiї та управлiння, м. Київ

Захист відбудеться “29” березня 2007 р. о 14 годині на засіданні спеціалізованої вченої ради Д 26.185.01 Інституту проблем моделювання в енергетиці ім. Г.Є. Пухова
НАН України за адресою: м. Київ, вул. Генерала Наумова, 15.

З дисертацією можна ознайомитися у бібліотеці Інституту проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України за адресою: м. Київ, вул. Генерала Наумова, 15.

Автореферат розісланий “28” лютого 2007 р.

Вчений секретар спеціалізованої вченої ради

к.т.н. Семагіна Е.П.

ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ

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

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

Предмет досліджень – процеси обміну інформацією між компонентами ПМС як фактор ефективного рішення задач моделювання.

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

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

1.

2.

3.

4.

5.

Методи дослідження носять теоретичний і експериментальний характер. При проведенні досліджень і розробок по дисертаційній роботі використовувалися методи математичного моделювання, прикладної й обчислювальної математики, теорії диференціальних рівнянь, апарат лінійної алгебри, зокрема теорії матриць, теорія графів. Отримані результати перевірялися шляхом проведення обчислювальних експериментів на ЕОМ CRAY T3E.

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

1.

2.

3.

4.

Практична цінність. Реалізовано дослідний зразок паралельного моделюючого середовища з теледоступом до його ресурсів. Розроблено засоби тестування комунікаційних бібліотек обчислювальних ресурсів ПМС. Система тестів містить у собі:

·

·

·

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

Апробація. Результати роботи доповідалися на симпозіумі по моделюванню ASIM (2002, Німеччина), міжнародній конференції “Інформаційні технології в керуванні енергетичними системами” (ИТУЭС-2005, Україна, Київ), на робочих семінарах кафедри ЕОМ Доннту й обчислювального центра Штутгартського університету (2003, Німеччина).

Зв'язок роботи з науковими програмами, темами, планами. Результати роботи використані у держтемі кафедри ЕОМ H25-2000 УДК 681.3 “Дослідження й розробка засобів програмної підтримки проектування інформаційних технологій і комп'ютерних систем”, у розділі державної програми “Розробка конкурентноздатних методів моделювання складних систем”, експерименти проводилися за темою угоди про наукове співробітництво зі Штутгартським університетом “Розробка розподіленого паралельного моделюючого середовища”

Публікації. Результати роботи опубліковані в 5 статтях у наукових збірниках, які входять до переліку видань ВАК України й в одній статті, написаної в співавторстві, у збірнику праць міжнародного симпозіуму з моделювання ASIM.

Структура й обсяг роботи. Текст дисертації складається з 4 глав, включає 22 рисунки й 1 таблицю, основний текст дисертації займає 102 сторінки.

ОСНОВНИЙ ЗМІСТ ДИСЕРТАЦІЇ

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

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

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

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

В останні роки сформувався новий науковий напрямок, у якому вирішуються проблеми розробки методів і створення апаратно-програмних засобів паралельного моделювання безперервних, дискретних і комбінованих динамічних систем (англ. - Parallel Simulation Technology). Центральною проблемою тут є комплексна розробка паралельних моделюючих середовищ універсального призначення і їх проблемно-орієнтованих варіантів.

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

Рис.1 - Організація ПМС

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

Однієї з головних характеристик паралельних ресурсів моделювання є прискорення R паралельної реалізації моделей СДС, що визначається вираженням:

(1)

де T1 - час рішення задачі моделювання на однопроцесорній системі, а Tn - час рішення тієї ж задачі на n- процесорній системі. Аналіз законів Амдала, що характеризують продуктивність паралельних ресурсів ПМС, показав, що прискорення паралельних моделей СДС істотно залежить від організації обміну інформацією. У рамках ПМС повинні бути вирішені наступні завдання організації обміну даними: складання ефективних паралельних програм, що реалізують моделі СДС; оптимальне відображення паралельних програм на цільові паралельні архітектури; вивід формул, що характеризують вплив процесів обміну інформацією на продуктивність паралельних ресурсів ПМС.

Із усього різноманіття програмних засобів створення паралельних моделей СДС у ПМС тільки для бібліотеки MPI (Message Passing Interface) існує реалізація, що підтримує одночасну роботу з декількома паралельними системами в термінах бібліотеки.

Характерні риси властиві розробці моделей за допомогою бібліотеки MPI:

·

·

·

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

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

Розроблювачі й користувачі паралельних моделей ДСЗП і ДСРП одержують доступ до апаратних ресурсів ПМС, структура якого наведена на рис.2.

Рис. 2- Структурна організація апаратних ресурсів ПМС

З погляду розроблювача паралельних моделей СДС і користувача середовище виглядає так, як показано на рис. 3.

Рис. 3 - Структура ПМС із погляду розроблювача паралельних моделей СДС і користувача

Тут:

·

·

·

·

·

Будемо характеризувати запропоновану структуру ПМС наступними параметрами:

m - кількість РМ (користувачів і розроблювачів ПМС);

n - кількість доступних MIMD - ресурсів;

Xi , i {1..n} - загальна кількість процесорів в i - м обчислювальному ресурсі (ВР);

Yi , i {1..n} - кількість доступних процесорів на даний момент часу в i-м MIMD-ресурсі;

– час затримки доступу до i-го обчислювального ресурсу з боку РМ;

Ti = {T ,.., T } – множина характеристик швидкості обмінів комунікаційної бібліотеки (MPI) i-го обчислювального ресурсу, де k – кількість видів обмінів;

CPUip – пікова продуктивність одного процесора i-го обчислювального ресурсу (при гетерогенності процесорів у ресурсі береться середня пікова продуктивність);

VDATA – обсяг переданих даних (програма й вхідні дані);

CPU – кількість процесорів, необхідна програмі користувача від i-го ОР.

Всі види обміну інформацією, що мають місце в ПМС, розділимо на наступні групи:

F1 – РМ ОР (копіювання програм моделювання й даних);

F2 – РМ {ОР1, …, ОРn} розподіл задачи моделювання між декількома ресурсами ПМС одночасно (копіювання моделей і даних);

F3 – обмін в середині ресурсу (паралельної системи MIMD-типу), тобто, безпосередньо, бібліотеки MPI;

F4 – ОР ОР обмін між ресурсами (розподіл задачи моделювання між декількома ресурсами ПМС одночасно, бібліотека PACX MPI);

F5 – РМ {ОР1, …, ОРn} збір результатів моделювання;

F6 – одержання інформації про умови моделювання;

F7 – обмін між рівнями програмного забезпечення.

Кожна із груп обмінів впливає на час розробки моделей СДС.

У структурі моделюючого програмного забезпечення ПМС організація обміну інформацією займає проміжне положення між системою візуального проектування моделей (СВПМ) і готовою моделюючою MPI-програмою (рис. 4).

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

Виходячи із цього визначимо, які кроки необхідно виконати для оптимізації обмінів:

Р1 – тестування характеристик Ti = { T ,.., T } бібліотек обміну кожного з обчислювальних ресурсів середовища;

Р2 - одержання топологічного опису моделей від СВПМ, його формалізація;

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

Р4 – генерування масштабованої MPI-програми;

Р5 – організація методу масштабування з обліком доступних у сучасний момент ресурсів середовища;

Р1 – Р5 – функції організації обмінів.

Користувач ПМС створює паралельні моделі СДС, які являють собою набір взаємозалежних паралельно працюючих процесів, що реалізують які-небудь формули, розрахунки та інш. Звичайна кількість таких процесів досить велика й перевищує загальну кількість доступних процесорів, проте, у цілому, для такої моделі СДС може бути написана MPI-програма, кожний процес якої відповідає процесу моделі. Така програма могла б бути запущена, якби була доступно необмежена кількість процесорів в одній MIMD-ЕОМ. Назвемо такого виду програму віртуальною MPI-програмою, MIMD-ЕОМ із необмеженою кількістю процесорів – віртуальнюї MIMD-ЕОМ, а такого виду MPI-процеси – віртуальними процесами. Необхідно згрупувати й розподілити віртуальні MPI-процеси на доступній кількості процесорів у доступному ОР ПМС і одержати MPI-программу.

Називатимемо такий процес групування й розподілу віртуальних процесів девіртуалізацією. Отриману програму можна запускати на кількості процесорів ОР від 1 до Xi, при цьому бажано знайти ту кількість процесорів NCPUOPT, на якому буде досягатися мінімум часу моделювання (1 NCPUOPT Xi), тобто оптимізувати MPI-програму та, відповідно, обмін інформацією.

Запропоновано методику інтеграції процесів обміну й етапів побудови моделюючих MPI-програм. Схема одержання робочої MPI-програми показана на рис. 5.

Рис. 5- Схема одержання робочої MPI - програми

Розроблено єдиний підхід до подання складних динамічних систем.

Елементи технологічних схем (ТС), що моделюються, представлено у вигляді зв'язаних один з одним певним чином блоків з деякою кількістю входів і виходів (рис. 6). ТС складається з кінцевої кількості такого виду блоків. Кількість типів блоків також обмежена (звичайно порядку 50 100). Позначимо кількість типів блоків через E, а кількість блоків у ТС через H. Виходи деяких блоків можуть бути пов'язані з їхніми входами. Кожний із блоків ТС може бути розбитий на деяку кількість елементарних блоків, які позначимо через Е , а їхню загальну кількість – через Н.

Рис. 6 - Подання ТС у вигляді графа

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

Перетворення МДО-графа в ТС-граф: нехай G(U, V) – граф МДО, де U – множина вершин графа, V – множина ребер графа. Граф G є замкнутим і орієнтованим. Утворимо новий граф G1 з множиною вершин U1 , кількість елементів якого дорівнює числу ребер графа G, кожній вершині G1 відповідає одне ребро G. Кожній вершині графа G1 відповідають дві вершини графа G – початкова й кінцева. Аналізуючи матрицю інцидентності графа G, можна з'єднати вершини графа G1 у такий спосіб: якщо в G ребро i входить у початкову вершину якого-небудь ребра j, то з'єднуємо відповідному цьому ребру i вершину ii в G1 з вершиною jj, що відповідає ребру j у напрямку від ii до jj ; якщо в G ребро i виходить із кінцевої вершини будь-якого ребра j, то з'єднуємо відповідну цьому ребру i вершину ii в G1 з вершиною jj, що відповідає ребру j у напрямку від ii до jj. Очевидно, що отриманий граф також буде замкнутим.

Таким чином, показана можливість перетворення МДО-графа в ТС - граф.

Перетворення ТС-графа в МДО-граф: нехай G(U, V) – граф ТС, де U – множина вершин графа, V – множина ребер графа. Граф G є орієнтованим. Запропоновано етапи перетворення:

·

·

·

·

·

·

Таким чином, показана можливість перетворення Тс-графа в МДО-граф.

Отже, три типи топологій СДС - ТС, ССА й МДО можуть бути після деяких перетворень зведені до представлення у вигляді графа одного із двох типів ТС- і МДО-графа. До всіх трьох типів топологій СДС можуть бути застосовані єдині методи аналізу й перетворень на основі розгляду їхніх графів.

Елементи, що моделюються, являють собою віртуальні MPI-процеси, тобто у віртуальній моделі й реалізується функція Р2.

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

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

Послідовність побудови результуючої MPI-програми наступна:

· побудова паралельної MIMD-моделі;

· побудова віртуальної MPI-програми, що реалізує модель;

· оптимізація віртуальної MPI - програми;

· генерування програми.

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

· граф обчислювальної MIMD-системи GsEs) являє собою повний граф з погляду застосовуваної MPI-бібліотеки обмінів;

· в кожній групі віртуальних процесів всі процеси працюють в однаковій послідовності періодів процесорних операцій (назвемо їх CPU-операціями) і операцій обміну й синхронізації (назвемо їх MPI-операціями);

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

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

T = F( Ni), (2)

де

Ni – кількість використовуваних процесорів.

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

Очевидно, що кількість процесорів (NCPUOPT), при якому досягається min(T), буде оптимальним рішенням. При цьому Ni - область припустимих значень.

Загальна кількість способів розподілу АР віртуальних процесів на кількості процесорів від 1 до NCPU дорівнює

(3)

Пропонується наступний спосіб пошуку min(T).

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

Тоді, знаючи параметри обчислювального ресурсу, результати тестів комунікаційної бібліотеки ресурсу й кількість CPU- і MPI- періодів роботи програми, можна розрахувати час роботи кожної групи віртуальних процесів на такій “віртуальній ЕОМ”:

Ti = TiCPU + TiMPI, i = 1..k. (4)

Тут:

TiCPU = CPUP * ОРiCPU , ОРCPU – кількість CPU-операцій віртуального процесу;

TiMPI = , f – кількість типів використаних MPI-операцій;

– час виконання MPI-операції j-го типу, визначається системою тестів комунікаційної бібліотеки;

– кількість MPI -операцій j-го типу.

Необхідно зробити сортування отриманих значень по зростанню (убуванню) і визначити Tmin і Tmax .

Введемо ваги груп:

; i = 1..k. (5)

Розподілимо всі доступні процесори обчислювального ресурсу ПМС між групами рівномірно, тобто кожній групі буде відповідати

Ni = quot(Vi*NCPU) (6)

процесорів (quot[F] - ціла частина числа F, а rem[F] - дробова частина).

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

NiOPT (1..Ni).

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

. (7)

Введено наступні допущення:

· при суміщенні віртуальних MPI-процесів і використанні SPMD-моделі програм загальна кількість періодів CPU- і MPI- операцій залишається незмінною;

· у суміщеному MPI-процесі навантаження на процесор (кількість CPU-операцій) збільшується прямо пропорційно кількості процесів, що суміщуються;

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

· усередині групи процеси рівноправні й розподіляються рівномірно між доступними процесорами.

Необхідно розрахувати min(Ti) для кожної групи

min(Ti) = min[Ti(1),…,Ti(NJ)], (8)

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

Ti = F(j, Nj), j = 1..Nj, (9)

цільову функцію Тi визначимо формулою , (10)

де:

ni – кількість віртуальних процесів в i-й групі;

Nj – поточне значення кількості використовуваних процесорів (1 Nj Ni);

TiCPU – час роботи всіх CPU-періодів одного віртуального процесу;

TiMPI(ptр) - час роботи всіх MPI-періодів одиночних обмінів одного віртуального процесу;

TiMPI(coll) - час роботи всіх MPI-періодів колективних обмінів і синхронізації одного віртуального процесу;

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

Показнику min(Ti) відповідає оптимальна для групи кількість процесорів NiOPT.

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

(11)

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

NiAV = quot[NiOPT* ], (12)

де NAV – загальна кількість доступних процесорів.

Такий розподіл означає масштабоване разпаралелювання.

Знайдемо показники й . Тоді

(13)

Таким чином, на NiAV процесорах, що виділені для ni віртуальних процесів i-й групі, процеси розподілені по

() на () процесорах і (+1) – на r процесорах

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

1) при використанні оптимальної кількості процесорів

tREZOPTIM = 2* + (VDATA IN + VDATA OUT )*Vi + tmodel( ) + twait, (14)

де twait=0, при С та twait 0, при > З

2) при використанні максимально доступного числа процесорів

tREZAV = 2* + (VDATA IN + VDATA OUT )*Vi + tmodel(NCPUAV). (15)

Тут

2* – час затримки передачі вихідних даних на ресурс і одержання результатів моделювання;

(VDATA IN + VDATA OUT )*Vi – сумарний час передачі вихідних даних на ресурс і одержання результатів моделювання;

tmodel( ) – апріорна оцінка часу моделювання на оптимальній кількості процесорів;

twait – час затримки постановки завдання на моделювання, що залежить від обчислювального ресурсу. Можливе визначення величини цієї складової за допомогою статистичної обробки результатів роботи ОР.

tmodel(NCPUAV) – апріорна оцінка часу моделювання на доступній кількості процесорів.

Визначивши tREZOPTIM і tREZAV для кожного з ресурсів, знайдемо

tmodel = tREZ = min(tREZOPTIMi, tREZAVi), (16)

де i = 1..Вa .

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

У четвертому розділі “Експериментальне дослідження методу оптимізації обмінів інформацією” проведено експериментальне дослідження системи тестів комунікаційної бібліотеки цільової паралельної архітектури на прикладі MIMD-системи Cray T3E обчислювального центру Штутгартського університету. Показано, що при організації обмінів інформацією в паралельних моделях бажано застосовувати одиночні обміни інформацією між процесами, як більше швидкі в порівнянні з колективними обмінами, а також використовувати повідомлення великого обсягу, тому що при малих обсягах переданої інформації швидкість передачі нижче, ніж при обміні повідомленнями великої розмірності. Результати, отримані в ході тестування, використані для виводу формул розрахунку залежності часу виконання паралельних програм від кількості застосовуваних процесорів. Розрахункова оптимальна кількість процесорів з точністю 4% - 18% збігається з результатами експериментів. Застосування оптимізації віртуальних моделей дозволяє скоротити час роботи моделюючої програми-симулятора в 3 - 4 рази, а кількість застосовуваних процесорів - в 4 - 5 разів.

Результати тестування істотно залежать від реалізації апаратних ресурсів Cray T3E, однак можна виділити загальні закономірності для операцій одиночних обмінів. При розмірі переданих повідомлень від 1024 і приблизно до 40000 – 42000 байт (рис. 7)

швидкість обміну зростає, а при перевищенні повідомленнями цього розміру швидкість залишається незмінної. Із цього можна зробити наступний висновок: при

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

Рис. 7 - Результати тестів швидкості міжпроцесорних обмінів

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

Для одиночних операцій обміну характерно практично однакове поводження функції:

, (17)

Рис.8 - Результат тестування основних колективних операцій MPI

де:

VMPIPTP – швидкість передачі даних (Мбайт/с),

L - розмір переданих даних (байт)

Визначимо параметри А и В функції VMPIPTP(L) по методу обраних точок експериментально отриманих графіків (рис. 7,8).

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

X1 = 0,007 Mb; Y1= 275 Mb/c; X2 = 0,042 Mb; Y2 = 450 Mb/c.

Значення max(VMPIPTP) = 500 Mb для цього типу операцій.

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

,

рішення якої дає наступні значення коефіцієнтів А и В:

А = 3,156; В = 0,86.

Тоді функція (17) прийме вигляд:

(18)

Параметр max(VMPIPTP) для різних одиночних операцій обміну буде приймати наступні значення:

· що не блокують - max(VMPIPTP) = 490;

· по готовності max(VMPIPTP) = 500;

· двонаправлені max(VMPIPTP) = 270.

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

L = L1* ni, (19)

де L1 – обсяг даних, переданих одним віртуальним процесом у період обміну. Після підстановки значення L у формулу (17) одержимо:

(20)

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

(21)

На відміну від одиночних функцій обміну, поводження залежності часу виконання колективних операцій обміну від кількості використовуваних процесорів для кожної з операцій має різний вигляд для операцій MPI Barrier, Broadcast і Gather відповідно:

(22)

де NCPU – кількість використовуваних процесорів.

Час зміни виконання колективних операцій можна виразити узагальнено:

, (23)

де

- час виконання відповідної операції на одному процесорі;

- “коефіцієнт зміни”; так, для операцій Broadcast і Gather “коефіцієнт зміни” дорівнює 0,3 і 3 відповідно, тільки для операції Barrier немає необхідності в такому коефіцієнті.

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

(24)

Використовуючи ці результати, перепишемо формулу (10) у такий спосіб:

(25)

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

Проведені експерименти з вирішувачем рівнянь паралельної моделі мережного динамічного об'єкта (шахтною вентиляційною мережею) показали відхилення розрахункових значень оптимальної кількості процесорів від експериментально визначеного від 4% до 18%.

При цьому оптимальна кількість процесорів 28..32 приблизно в 4 рази менше максимально можливого для використання. Час виконання зменшився до 0,45 с у порівнянні з 2,2 с (рис. 9).

Рис. 9 - Залежність часу виконання MPI -програми, що реалізує паралельну модель, від кількості процесорів

ВИСНОВКИ

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

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

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

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

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

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

5. Експериментальне дослідження системи тестів комунікаційної бібліотеки ЦПОС на прикладі MIMD-ЕОМ Cray T3E обчислювального центру Штутгартського університету показало, що при організації обмінів інформацією в паралельних моделях бажано застосовувати одиночні обміни даними між процесами, як більш швидкі в порівнянні з колективними обмінами.

Результати, отримані в ході тестів, використані для отримання формул розрахунку залежності часу виконання паралельних програм від кількості застосовуваних процесорів. Розрахункова оптимальна кількість процесорів з точністю 4% - 18% збігається з результатами експериментів. Застосування оптимізації віртуальних моделей дозволяє скоротити час роботи програми на суперЕОМ Cray T3E в 3 - 4 рази, а кількість застосовуваних процесорів - в 4 - 5 разів.

ПУБЛІКАЦІЇ ПО ТЕМІ ДИСЕРТАЦІЇ

1.

2.

3.

4.

5.

6.

7.

Особистий внесок здобувача. У статтях, написаних у співавторстві, особистий внесок здобувача полягає в наступному:

[1, 5] - запропоновано виділити в складі паралельного моделюючого середовища підсистему обміну інформацією;

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

АНОТАЦІЯ

Солонін О.М. Оптимальна організація процесів моделювання в паралельному моделюючому середовищі. - Рукопис.

Дисертація на здобуття наукового ступеня кандидата технічних наук за спеціальністю 01.05.02 - математичне моделювання й обчислювальні методи. - Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України, Київ, 2007.

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

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

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

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

Реалізовано дослідний зразок паралельного моделюючого середовища з теледоступом до його ресурсів. Розроблено засоби тестування комунікаційних бібліотек обчислювальних ресурсів ПМС.

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

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

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

АННОТАЦИЯ

Солонин А.Н. Оптимальная организация процессов моделирования в параллельной моделирующей среде. – Рукопись.

Диссертация на соискание ученой степени кандидата технических наук по специальности 01.05.02 – математическое моделирование и вычислительные методы. – Институт проблем моделирования в энергетике им. Г. Е. Пухова, Киев, 2007.

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