Реферат з теми випускної роботи

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

Вступ

Актуальність теми

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

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

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

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

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

Метою роботи є розробка підсистеми топологічного аналізу для мережних динамічних систем у вигляді окремого незалежного програмного модуля РПМС. Основний ресурс, на який буде спрямована робота, – кластер ДонНТУ – MIMD-система з розподіленою пам'яттю.

Задачі роботи

У рамках розробки підсистеми топологічного аналізу повинні бути вирішені наступні задачі:

1. Розроблені структури даних для опису топологій і характеристик МДО.
2. Розроблені алгоритми для аналізу первинної топології, її апроксимації, розбиття вихідного графа на дерево/антидерево.
3. Визначені принципи взаємодії з іншими підсистемами та функціонування в якості складової частини РПМС.

Наукова новизна роботи:

1. Розроблені нові оптимізовані структури даних для опису топології та алгоритми їх обробки.
2. Розроблено спеціальні алгоритми для реалізації розбиття графа на дерево/антидерево та його апроксимації.
3. Розроблені структури даних і спеціальні методи для реалізації обміну інформацією з іншими підсистемами РПМС.
4. Вперше реалізований та досліджений топологічний аналізатор для мережних динамічних систем як незалежний програмний модуль у складі РПМС.

Практична цінність роботи:

1. Реалізовано топологічний аналізатор у складі РПМС для мережних динамічних систем з розподіленими параметрами.
2. Розроблена програмна реалізація алгоритмів для роботи з запропонованим новим підходом до кодування топології.
3. Розроблені алгоритми для оптимального розбиття графа топології на дерево/антидерево та його апроксимації.
4. Розроблені структури даних для кодування графів топології, алгоритми та програмні реалізації використовуються в науково-дослідницькій роботі кафедри КІ факультету КНТ.

↑ Вгору

Аналіз сучасних РПМС

Розподілене паралельне моделююче середовище (РПМС) – це сукупність апаратних засобів, системного та прикладного програмного забезпечення (ПЗ), спільне функціонування яких спрямоване на виконання моделювання роботи СДС.

Характерною особливістю РПМС є здатність виконувати обчислення окремих частин об'єкта одночасно і незалежно один від одного, тобто паралельно. Розпаралелювання дозволяє значно прискорити процес моделювання. Апаратними засобами для цього виступають розподілені системи: комп'ютерні кластери, Grid, паралельні структури з використанням GPU.

На даний момент можна виділити наступні популярні РПМС:

1. Mathworks Simulink – доповнення до середовища Mathworks MatLab для виконання моделювання, симуляції та аналізу СДС. Simulink має бібліотеку з багатим набором елементів і можливістю їх модифікації та розширення. [1]
2. MSC Software EASY5 – середовище для моделювання динамічних фізичних систем, яке використовується багатьма великими компаніями для розробок у технічній авіації, транспортних засобах, сільськогосподарському обладнанні та інших складних системах, поведінка яких описується диференційними рівняннями першого порядку. [2]
3. Visual Solutions VisSim – візуальна мова програмування для вбудованих мікропроцесорів, призначена для моделювання та проектування динамічних систем, що базуються на моделях. VisSim пропонує інтуїтивний інтерфейс для створення блокових діаграм та потужне моделююче ядро. [3]
4. Modelica – об'єктно-орієнтована, декларативна моделююча мова програмування для компонентно-орієнтованого моделювання СДС. Для використання цієї мови розроблено кілька комерційних середовищ, найбільш відомим з яких є Dassault Systemes Dymola. [4]

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

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

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

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

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

↑ Вгору

Принцип декомпозиції РПМС на підсистеми

Факультет комп'ютерних наук і технологій Донецького національного технічного університету має практичний досвід реалізації паралельних моделей для таких обчислювальних систем як MasPar, Intel Paragon, CRAY T3E, NEC SX8, що стало можливим завдяки тривалій співпраці зі Штутгартським університетом Німеччини. Використовуючи вироблені та розвинені концепції, в основі яких лежить структура організації РПМС [5], була проведена декомпозиція всього РПМС на 10 підсистем, UML-діаграма взаємодії яких зображена на рис. 1.

Рисунок 1. Декомпозиція на підсистеми

Передбачається декомпозиція програмного забезпечення (ПЗ) РПМС на наступні підсистеми:

1. Підсистема інформаційних технологій (ПІТ) – забезпечення взаємодії користувача з РПМС (введення топології СДС, завдання параметрів тощо) і можливості використання «зовнішніх» обчислювальних ресурсів, набір прикладів і навчального матеріалу.
2. Підсистема візуалізації (ПВ) – надання можливості ПІТ виводити графічні результати роботи користувачеві (відображення топології та графіків результатів моделювання).
3. Підсистема керування (ПК) – керування послідовністю дій РПМС, реакція на результати виконання кожної підсистеми, забезпечення підтримки запитів підсистем щодо необхідної для роботи інформації.
4. База даних (БД) – збереження даних кожного етапу моделювання (проміжних результатів підсистем) та інформації щодо користувачів, їх запитів та задач.
5. Підсистема топологічного аналізу (ПТА) – введення топології СДС, її кодування, апроксимація, отримання вторинної топології, перетворення топологічних одиниць інформації в зручну для генерування рівнянь форму, виведення результатів аналізу.
6. Підсистема генерування рівнянь (ПГР) – перетворення вихідних апроксимованих рівнянь (моделей) у векторно-матричну форму, генерування дискретних симуляційних моделей для заданого чисельного методу розв'язання.
7. Підсистема паралельних віртуальних симуляційних моделей (ППВСМ) – представлення можливих ієрархій віртуальних паралельних симуляційних моделей (ВПСМ) залежно від рівня розпаралелювання, апріорний аналіз ВПСМ.
8. Підсистема розв’язання рівнянь (ПРР) – розв’язання алгебраїчних, звичайних диференціальних рівнянь і рівнянь частинної похідною з допомогою паралельних чисельних методів, аналіз збіжності, стійкості та точності розв’язання рівнянь, оцінка та оптимізація показників ефективності, формування результатів у зручній для візуалізації формі.
9. Підсистема балансування навантаження (ПБН) – оцінка навантаження віртуальних процесів за рівнями ВПСМ, статичне регулювання навантаження всіх рівнів, специфікація заявок на ресурси РПМС, отримання та аналіз навантаження між процесами і ресурсами цільової обчислювальної системи, порівняльний аналіз способів розпаралелювання за критерієм рівномірного навантаження ресурсів.
10. Підсистема обміну даними (ПОД) – взаємодія та передача даних від основного ПЗ РПМС до локального сервісу, розташованого на кластері; специфікація структур даних і підтримка обміну інформацією між підсистемами.

Тільки ПІТ і ПОД забезпечують взаємодію із зовнішнім середовищем (користувачем і кластерами) та являють собою «інтерфейс» РПМС. При цьому будь-яка кількість користувачів може звертатися до РПМС.

Даний підхід дозволить прискорити розробку РПМС і надати «гнучкість» системі: можливість підлаштовуватися для роботи з різними видами СДС шляхом перемикання всього декількох підсистем.

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

ПТА виконує наступні функції:

1. Введення вихідних даних, що описують топологію МДО і фізичні характеристики його компонент:
   • Отримання топології МДО у вигляді підготовленої структури даних.
   • Читання топології зі спеціалізованого файлу.
2. Процес топологічного аналізу:
   • Розбиття первинної топології на дерево і антидерево.
   • Побудова матриць інцидентності A і незалежних контурів S.
   • Апроксимація гілок графа і формування вторинної топології.
   • Топологічний аналіз за рівнями розпаралелювання.
   • Перетворення топологічних одиниць інформації в зручну для генерування рівнянь форму.
   • Формування результатів.
3. Взаємодія з іншими підсистемами (представлено на UML-діаграмі рис. 2):
   • Отримання вихідних даних з БД за допомогою ПОД.
   • Виконання функцій із заданими параметрами, які визначає ПК на різних етапах роботи РПМС.
   • Передача даних в ПГР.
   • Збереження результатів роботи в БД за допомогою ПОД.

Рисунок 2. Діаграма взаємодії ПТА з іншими підсистемами

Анімація Silverlight: обсяг - 56,1 КБ, розмір - 477х222, тривалість - 15 с, кількість ключових кадрів - 67, багатомовна, запуск програвання за натисненням користувача.

↑ Вгору

Аналіз існуючих робіт

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

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

• Пошукові системи Google, Bing, Yandex, Rambler, Meta и Yahoo! з використанням регіональної фільтрації результатів;
• Суспільство Макса Планка (Max-Planck-Gesellschaft, Мюнхен, Німеччина);
• Бібліографія комп'ютерних наук (The Computer Science Bibliography);
• Мережа знань (Web of Knowledge);
• Інженерна інформація (Engineering Information);
• Система ПроКвест (ProQuest).

Запит робіт за темою топологічного аналізу дав досить велику кількість результатів, але більш докладний розгляд показав, що ці роботи не стосуються СДС або безпосередньої розробки ПТА. За конкретною темою результатів не було знайдено.

Пошук на національному рівні дав лише деякі результати щодо використання таких засобів, як Simulink, UML тощо. Дана тематика не відноситься безпосередньо до розробки топологічного аналізатора.

Локальний пошук по роботах ДонНТУ видав достатню кількість робіт та опублікованих статей з розробки підсистеми топологічного аналізу СДС:

• У роботі [6] запропоновані алгоритми роботи топологічного аналізатора для формування і розв’язання рівнянь МДО з зосередженими параметрами для MIMD-систем, особливістю яких є покрокове перетворення таблиці графа.
• У роботі [7] розроблені алгоритми обробки графів топології та реалізований паралельний топологічний аналізатор МДО з зосередженими параметрами.
• Докладно розглянуто топологічний аналізатор паралельної моделі МДО в роботі [8].
• У роботі [9] та [10] визначені основні функції топологічного аналізатора, його модифікація для МДО з розподіленими параметрами, алгоритми побудови матриці інцидентності та можливі методи апроксимації гілок графа.

Описані в роботі функції ПТА передбачають тісну взаємодію з користувачем завдяки використанню графічного відображення графа МДО і засобів діалогової підтримки для його оперативного редагування. У рамках запропонованої декомпозиції (рис. 1) ПТА не має зв'язку з користувачем, тому завдання організації взаємодії повністю покладається на ПІТ, а графічне відображення вихідних даних і результатів виконує ПВ. Потрібна розробка багатих засобів і структур даних для двосторонньої взаємодії з даними підсистемами.

При введенні даних МДО потрібен спосіб їх подання в такій формі, яка б об'єднувала формалізацію зв'язків, завдання параметрів і вербальний опис важливих для даної предметної галузі компонент. Запропонована у роботі [9] форма таблиці (табл. 1) підходить для вирішення даної проблеми, однак з урахуванням алгоритмів ПГР можлива деяка оптимізація представлених у ній даних.

Таблиця 1 - Таблиця опису топології МДО

Початковий вузол	Кінцевий вузол	Номер гілки	Фізичні параметри гілки	Активний елемент	Коментар

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

Таблиця 2 - Модифікована таблиця інцидентності

	Q1		Q2		...		Qm
	Q11	Q1M1	Q21	Q2M2	...	...	Qm1	QmMm
Ui	...	...	...	...	...	...	...	...

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

Для розбиття вихідного графа на дерево/антидерево потрібен алгоритм, який дозволить отримати приблизно однакову довжину результуючих підграфів. Це дозволить розподілити рівномірно навантаження при використанні IV рівня розпаралелювання.

↑ Вгору

Висновки

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

При написанні даного автореферату магістерська робота ще не завершена. Остаточне завершення: грудень 2011 р. Повний текст роботи та матеріали по темі можуть бути отримані у автора або його керівника після зазначеної дати.

↑ Вгору

Література

1. Simulation and Model-Based Design [Electronic resource] / Інтернет-ресурс. – Режим доступу : www/ URL: http://www.mathworks.com/products/simulink/. – Назва з екрану.
2. Easy5 for Controls and Systems Simulation [Electronic resource] / Інтернет-ресурс. – Режим доступу : www/ URL: http://www.mscsoftware.com/Products/CAE-Tools/Easy5.aspx. – Назва з екрану.
3. VisSim [Electronic resource] / Інтернет-ресурс. – Режим доступу : www/ URL: http://www.vissim.com/. – Назва з екрану.
4. Modelica and Modelica Association [Electronic resource] / Інтернет-ресурс. – Режим доступу : www/ URL: http://www.modelica.org/. – Назва з екрану.
5. Святний В. А. Стан розробок та перспектива інтеграції паралельних моделюючих середовищ з Grid-технологіями [Текст] / В. А. Святний, О. В. Молдованова, А. М. Чут // Наукові праці Донецького національного технічного університету. Серія “Інформатика, кібернетика та обчислювальна техніка” (ІКОТ-2008). Випуск 9 (132). – Донецьк : ДонНТУ, 2008. – С. 103-110.
6. Dissertation (Master: Alexey Smagin, Group: VT-97-v) [Электронный ресурс] / Інтернет-ресурс. – Режим доступу : www/ URL: http://masters.donntu.ru/2002/fvti/smagin/diss/index.html. – Назва з екрану.
7. Давлетханов ДВ Моделирование сетевых динамических объектов Реферат [Електронний ресурс] / Інтернет-ресурс. – Режим доступу : www/ URL: http://masters.donntu.ru/2006/fvti/davlethanov/diss/diss.htm. – Назва з екрану.
8. Топологический анализатор [Електронний ресурс] / Інтернет-ресурс. – Режим доступу : www/ URL: http://www.students.cs.donntu.ru/vt95/vt95g/pererva/topan.html. – Назва з екрану.
9. Молдованова О. В. Способи організації паралельних обчислень в задачах математичного моделювання шахтних вентиляційних мереж [Текст] : дис. … канд. наук : 01.05.02 / Молдованова Ольга Володимирівна. – К., 2008. – 152 с.
10. Чайка МА Автореферат [Електронний ресурс] / Інтернет-ресурс. – Режим доступу : www/ URL: http://masters.donntu.ru/2007/fvti/chayka/diss/index.htm. – Назва з екрану.

↑ Вгору