Розподілена система імітаційного моделювання

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

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

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

ІНСТИТУТ ПРОБЛЕМ МАТЕМАТИЧНИХ МАШИН І СИСТЕМ

05.13.06 - Автоматизовані системи управління та прогресивні інформаційні технології

АВТОРЕФЕРАТ

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

Розподілена система імітаційного моделювання

Гавсієвич Ілля Борисович

Київ - 2006

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

Робота виконана в Інституті проблем математичних машин і систем НАН України.

Науковий керівникдоктор технічних наук, професор

Литвинов Віталій Васильович,

Інститут проблем математичних машин і систем НАН України,

завідувач відділу

Офіційні опоненти:доктор технічних наук, професор

Томашевський Валентин Миколайович,

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

автоматизованих систем обробки інформації та управління

доктор технічних наук, професор

Волошин Олексій Федорович,

Київський національний університет імені Тараса Шевченка, професор

кафедри математичних методів еколого-економічних досліджень

Провідна установаІнститут кібернетики ім. В.М. Глушкова НАН України,

відділ теорії цифрових математичних машин і систем, м. Київ

Захист відбудеться “ 26 ” квітня 2006 р. о 14 годині на засіданні

спеціалізованої вченої ради Д 26.204.01 в Інституті проблем математичних

машин і систем НАН України за адресою: 03187, Київ - 187, проспект Академіка Глушкова, 42.

З дисертацією можна ознайомитись у науковій бібліотеці Інституту проблем математичних машин і систем НАН України за адресою: 03187, Київ - 187, проспект Aкадеміка Глушкова, 42.

Автореферат розісланий “ 17 ” березня 2006 р.

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

кандидат технічних наукХодак В.І.

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

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

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

Застосування РСІМ дозволить:

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

по-друге, розподілені моделі можуть виявитися істотним фактором у затвердженні напрямку напівнатурного моделювання. Вони щонайкраще дозволяють сполучати реально функціонуючі модулі й елементи досліджуваних систем з програмними системними імітаторами. Безумовно, таке застосування РСІМ може виявитися незамінним при створенні тренажерів, іспитових стендів та різного роду інформаційно-керуючих і аналітичних систем;

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

Питанням розподіленого імітаційного моделювання присвячені сотні робіт вітчизняних та закордонних вчених: Гусєва В.В, Казимира В.В., Литвинова В.В., Мар'яновича Т.П., Браянта Р.Е., Місри Д., Фуджімото Р.М., Ченді К.М. та інш. Однак питання використання формальних методів опису структури та процесу функціонування імітаційних моделей в розподіленому обчислювальному середовищі освітлені недостатньо і потребують подальшої розробки.

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

Зв'язок роботи з науковими програмами, планами, темами. Основні дослідження за темою дисертації проводилися в межах виконання науково-дослідних робіт Інституту проблем математичних машин і систем НАН України:

“Розробка методів та інструментальних засобів програмної інженерії для систем прийняття рішень у задачах з просторово-часовою інформацією” (НДР шифр “ИНЖПРОГ”, 2000-2002, № ДР 0100U000810);

“Розробка та дослідження алгоритмів, програмно-технічних архітектур захисту інформації в телефонних та комп'ютерних мережах” (НДР шифр “ТЕЛЕЗАХИСТ”, 2002-2007, № ДР 0102U002728).

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

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

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

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

3.Реалізація розподіленої системи імітаційного моделювання на основі прогресивних інформаційних технологій.

4.Експериментальна перевірка теоретичних досліджень на прикладі розподіленої системи імітаційного моделювання.

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

Об'єкт дослідження: розподілене імітаційне моделювання.

Предмет дослідження: методи синхронізації в розподіленому імітаційному моделюванні.

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

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

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

2.Теоретично обґрунтоване положення про неефективність використання алгоритму класичного послідовного планування подій в Е-мережах при розподіленому моделюванні.

3.Вперше на основі консервативної схеми розроблений метод синхронізації паралельного виконання Е-мережевих переходів, що використовує NULL-повідомлення для запобігання взаємних блокувань.

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

5.Розроблено та досліджено напівнатурні моделі програмно-апаратного комплексу захисту телефонних і комп'ютерних мереж, алгоритму передачі даних для мультиплексора МП-30Е та апаратно-програмного комплексу оповіщення абонентів.

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

підтримка стандартів High Level Architecture, Common Object Request Broker Architecture, Message Passing Interface та Petri Net Markup Language;

орієнтація на багатопроцесорні комп'ютери, мережі персональних комп'ютерів та MPI-кластери;

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

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

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

Особистий внесок здобувача. Результати, що виносяться на захист, отримані особисто. У роботах [1-4, 6, 7] авторові дисертації належать всі теоретичні і практичні результати, окрім постановки цілей і задач досліджень. У роботі [5] - аналіз комунікаційних підсистем. Авторові також належить програмна реалізація РСІМ, дослідження її властивостей; створення та дослідження імітаційних моделей.

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

Міждержавна науково-методична конференція “Комп'ютерне моделювання” (Дніпродзержинськ, 2000);

Міжнародна науково-технічна конференція “Автоматизація: проблеми, ідеї, рішення” (Севастополь, 2003);

Міжнародна науково-технічна конференція “Системи підтримки прийняття рішень. Теорія та практика, СППР '2005” (Київ, 2005).

Публікації. Основні результати дисертації опубліковані в 7 наукових працях: з них 4 - статті в наукових фахових журналах, затверджених ВАК України для спеціальності 05.13.06, і 3 - статті в збірниках матеріалів конференцій.

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

ОСНОВНИЙ ЗМІСТ РОБОТИ

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

Перший розділ присвячений огляду літературних джерел по темі дисертації й існуючих наробітків у даному напрямку. Досліджуються проблеми розподіленого імітаційного моделювання; визначається клас розв'язуваних прикладних задач; робляться огляди можливих апаратно-програмних платформ; проводиться вибір математичної основи опису структури та процесу функціонування моделей; розглядається консервативна й оптимістична схеми; обговорюються засоби реалізації РСІМ; приводяться дані існуючих систем імітаційного моделювання (СІМ): Georgia Tech Time Warp (GTW), General Purpose Simulation System (GPSS), СІМ часових мереж Петрі; формулюються задачі дослідження.

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

Формально Е-мережу можливо визначити п'ятіркою:

, (1)

де

- кінцева непуста множина позицій;

- кінцева непуста множина переходів, ;

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

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

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

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

Будь-який перехід можна описати

	для переходів типу ,  або	(2)
	для переходу типу
	для переходу типу ,

де

- тип переходу;

- час затримки на переході;

- процедура перетворення атрибутів;

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

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

Таблиця 1

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

Графічне зображення	Формула
		якщо
		інакше,
	де,
		якщо
		інакше,
	де
		якщо
		інакше,
	де
		якщо
		інакше,
	де,
		якщо
		інакше,
	де,

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

Зміна розмітки у нову розмітку , при спрацьовуванні переходу залежно від його типу, наведена в таблиці 2.

Таблиця 2

Зміна розмітки мережі при спрацьовуванні переходу

Графічне зображення	Формула
	,
	,
	,
	, ,
	, ,

Алгоритм роботи Е-мережевого переходу можна описати блок-схемою, що наведена на рис. 1.

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

Рис. 1. Алгоритм роботи Е-мережевого переходу	Рис. 2. Алгоритм роботи послідовного планувальника

На блок-схемах були використані такі позначення:

- поточний модельній час;

- список подій; - подія закінчення затримки переходу , запланована на момент часу (таким чином, в даному алгоритмі список подій містить затримані переходи);

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

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

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

Рис. 3. Алгоритм підпрограми	Рис. 4. Алгоритм підпрограми

В роботі для організації паралельного виконання імітаційних моделей використовується процесо-орієнтована парадигма. Представимо традиційну систему імітаційного моделювання, побудовану на базі Е-мереж, як множину процесів та процес , і опишемо її формально в межах теорії Communicating Sequential Process (CSP), де

- процес, реалізуючий роботу Е-мережевого переходу;

- процес, реалізуючий роботу планувальника.

Процес має наступний алфавіт:

(3)

.

Формальне визначення процесу приведено нижче:

(4)

.

Стани процесу показані на рис. 5.

Рис. 5. Стани процесу

Множину паралельно працюючих переходів можна визначити

. (5)

Процес має наступний алфавіт:

(6)

.

Формальне визначення процесу приведено нижче:

 ?  (7)

;

? (8)

;

? (9)

.

Стани процесу показані на рис. 6.

Запуск процесу планувальника можна визначити як

. (10)

Тоді всю систему в цілому можна визначити

. (11)

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

(12)

.

Рис. 6. Стани процесу SCHEDULER(time, EL)

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

На основі консервативної схеми розробимо метод синхронізації виконання Е-мережевих переходів.

1.Введемо функцію - локальний модельний час переходу :

. (13)

2.Введемо функцію - часова відмітка останньої події позиції : одержання мітки, видалення мітки, одержання NULL-повідомлення (див. далі):

. (14)

3.Введемо функцію - нижня часова межа з всіх вхідних повідомлень (повідомлень, отриманих від вхідних позицій) переходу :

. (15)

4.Розіб'ємо множину вхідних позицій переходу на дві непересічні підмножини - вхідних вільних і вхідних зайнятих позицій:

,

, (16)

.

5.Розіб'ємо множину вихідних позицій переходу на дві непересічні підмножини - вихідних вільних і вихідних зайнятих позицій:

,

, (17)

.

6.Введемо функцію - умова гарантії відсутності наведених помилок (causality errors - помилки, що можуть виникати у разі паралельного чи розподіленого імітаційного моделювання) у майбутньому для переходу ; - означає, що умова виконується; - означає, що умова не виконується. Визначення функції залежно від типу переходу наведено в таблиці 3.

Таблиця 3

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

Тип	Формула
		якщо
		інакше,
	де
		якщо
		інакше,
	де

7.Введемо функцію - момент часу початку затримки переходу . Визначення функції залежно від типу переходу приведено в таблиці 4.

Таблиця 4

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

Тип	Формула
	,де ,
	, де
	,де
	,де ,
	,де ,

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

Таблиця 5

Зміни розмітки мережі та часових відміток позицій

при спрацьовуванні переходу залежно від його типу

Тип	Формула
	;
	;
	;
	; ;
	; ;

9.Для запобігання взаємних блокувань (deadlock) введемо процедуру посилання нульових (NULL) повідомлень, яку формально можна описати так:

; (18)

.

10.Модифікований алгоритм роботи Е-мережевого переходу можна описати блок-схемою, що приведена на рис. 7.

Тепер уся система складається з множини процесів , реалізуючих роботу модифікованого Е-мережевого переходу . Стани процесу наведені на рис. 8.

Рис. 7. Модифікований алгоритм роботи Е-мережевого переходу	Рис. 8. Стани процесу

Процес має алфавіт:

(19)

.

Формальне визначення процесу наведено нижче:

(20)

;

. (21)

Множину паралельно працюючих переходів можна визначити

. (22)

Розроблені формальні описи на CSP також можуть бути використані для аналізу і верифікації, у тому числі за допомогою спеціалізованих програм, таких як Process Behavior Exploration (ProBE) та Failures-Divergence Refinement (FDR), розроблених Formal Systems (Europe) Ltd.

У третьому розділі розглядаються питання реалізації РСІМ на основі стандарту High Level Architecture (HLA), компонентної технології Common Object Request Broker Architecture (CORBA) і мови програмування Java, а також на основі стандарту Message Passing Interface (MPI). Обговорюються механізми підтримки розподіленого та напівнатурного моделювання, реалізація зберігання Е-мережевих моделей на основі стандарту Petri Net Markup Language (PNML). Розглядається генерація псевдовипадкових чисел, збір та накопичення первинної статистичної інформації; графічний інтерфейс користувача.

Технологічною базою реалізації РСІМ є пакет Java 2 Software Development Kit, Standard Edition (j2sdk1.4.2) від Sun Microsystems, Inc. Для реалізації РСІМ, орієнтованої на MPI кластер, використовуються такі пакети і бібліотеки: LAM/MPI, JTHREADS/C++ (pthreads), libxml++ (libxml, libsigc++, glibmm).

Для забезпечення підтримки нової мережі в стандарті PNML необхідно визначити її властивості у відповідних файлах-визначеннях Petri Net Type Definition. Фрагмент графічного представлення опису Е-мережі в PNML показано на рис. 9.

Рис. 9. Фрагмент графічного представлення опису Е-мережі в PNML

Елементи графічного інтерфейсу користувача РСІМ (редактор Е-мережі та налагоджувач) наведені на рис. 10.

Рис. 10. Графічні редактор Е-мережі та налагоджувач

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

Результати дослідження продуктивності РСІМ на багатопроцесорному комп'ютері, в обчислювальній мережі та на MPI-кластері наведено на рис. 11 - 13 відповідно.

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

Рис. 11. Результати дослідження продуктивності РСІМ

на багатопроцесорному комп'ютері

Рис. 12. Результати дослідження продуктивності РСІМ в обчислювальній мережі

Рис. 13. Результати дослідження продуктивності РСІМ на MPI-кластері

Імітаційна модель програмного забезпечення пристрою конфіденційного зв'язку приведена на рис. 14. У разі напівнатурного моделювання фрагмент моделі T4-S7-T5 замінявся двома мобільними телефонами, які працювали в режимі передачі даних.

Рис. 14. Імітаційна модель програмного забезпечення

пристрою конфіденційного зв'язку

У додатку А представлено опис імітаційної моделі програмного забезпечення пристрою конфіденційного зв'язку за допомогою PNML.

Додаток Б містить довідки про впровадження результатів дисертаційної роботи.

ВИСНОВКИ

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

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

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

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

3.На основі консервативної схеми розроблений метод синхронізації виконання

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

4.На базі запропонованого теоретичного методу та з урахуванням існуючих стандартів High Level Architecture, Common Object Request Broker Architecture, Message Passing Interface, Petri Net Markup Language розроблена розподілена система імітаційного моделювання, орієнтована на багатопроцесорні комп'ютери, мережі персональних комп'ютерів, MPI-кластери. Дана система включає механізми підтримки напівнатурного моделювання, технологію зберігання Е-мережевих моделей і графічний інтерфейс користувача.

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

6.За допомогою розробленої системи імітаційного моделювання побудовані та досліджені напівнатурні моделі програмно-апаратного комплексу захисту телефонних і комп'ютерних мереж, алгоритмів перетворення даних для мультиплексора МП-30Е та апаратно-програмного комплексу оповіщення абонентів. Розподілений характер процесу моделювання дозволив залучити до досліджень територіально-віддалену групу розроблювачів, що значно (в 2 рази) скоротило час розробки й виконання моделей.

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

1.Казимир В.В., Гавсієвич І.Б. Порівняльна характеристика та принципи реалізації програмних компонентних технологій // Вісн. Черніг. держ. технол. ун-ту. - 2000. - №1. - С. 172-176.

2.Литвинов В.В., Казимир В.В., Гавсиевич И.Б. Распределенная система имитационного моделирования на основе архитектуры CORBA // Математичні машини і системи. - 2000. - № 2,3. - С. 111-114.

3.Гавсиевич И.Б., Казимир В.В. Распределенная система имитационного моделирования ТП // Міждержавна науково-методична конференція “Комп'ютерне моделювання”. Тези доповідей. - Дніпродзержинськ. - 2000. - 29 червня - 1 липня. - С. 93-94.

4.Lytvynov V., Kazymyr V., Havsiyevych I. CORBA-based distributed simulation system with E-nets specification // Автоматизація: проблеми, ідеї, рішення: Матеріали міжнародної науково-технічної конференції. - Севастополь: Вид-во СевНТУ. - 2003. - 26 - 30 травня. - С. 60-63.

5.Семенец C.В., Гавсиевич И.Б. Обзор программных архитектур ОС мобильных систем // Математичні машини і системи. - 2003. - №1. - С. 119-134.

6.Литвинов В.В., Казимир В.В., Гавсиевич И.Б. Анализ алгоритма работы Е-сетевого перехода при традиционном и распределенном моделировании с помощью алгебры взаимодействующих процессов // Міжнародна науково-технічна конференція “Системи підтримки прийняття рішень. Теорія і практика”. - Київ: ІПММС НАНУ. - 2005. - 7 червня. - С. 139-143.

7.Литвинов В.В., Казимир В.В., Гавсієвич І.Б. Алгоритм паралельного виконання та синхронізації Е-мережі // Математичні машини і системи. - 2005. - № 4.- C. 72-83.

АНОТАЦІЯ

Гавсієвич І. Б. Розподілена система імітаційного моделювання. - Рукопис.

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

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

В роботі розроблений формалізований опис алгоритмів роботи Е-мережевого переходу та планувальника подій у термінах алгебри взаємодіючих послідовно-паралельних процесів. Теоретично обґрунтоване положення про неефективність використання алгоритму класичного послідовного планування подій в Е-мережах при розподіленому моделюванні. На основі консервативної схеми розроблений метод синхронізації паралельного виконання Е-мережевих переходів, що використовує NULL-повідомлення для запобігання взаємних блокувань. На базі запропонованого теоретичного методу та з урахуванням існуючих стандартів High Level Architecture, Common Object Request Broker Architecture, Message Passing Interface (MPI), Petri Net Markup Language розроблена розподілена система імітаційного моделювання, орієнтована на багатопроцесорні комп'ютери, мережі персональних комп'ютерів, MPI-кластери. Дана система включає механізми підтримки напівнатурного моделювання, технологію зберігання Е-мережевих моделей і графічний інтерфейс користувача.

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

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

АННОТАЦИЯ

Гавсиевич И. Б. Распределенная система имитационного моделирования. - Рукопись.

Диссертация на соискание ученой степени кандидата технических наук по специальности 05.13.06 - Автоматизированные системы управления и прогрессивные информационные технологии. - Институт проблем математических машин и систем НАН Украины, Киев, 2005.

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

В работе сформулирована и решена актуальная научно-прикладная задача, связанная с разработкой теоретических и практических основ построения распределенных систем имитационного моделирования на основе усовершенствования формального аппарата Е-сетей за счет применения дополнительных механизмов синхронизации в рамках консервативного подхода. Основным результатом диссертации является разработка системы имитационного моделирования, которая позволяет проводить построение и исследование моделей сложных систем в распределенной вычислительной среде.

В результате анализа существующих систем распределенного имитационного моделирования были выделены следующие основные их характеристики: базовая аппаратно-программная платформа, математическая основа распределенной системы имитационного моделирования, используемая схема синхронизации выполнения распределенных моделей, технологическая база реализации распределенной системы имитационного моделирования. Сформулирована задача по усовершенствованию аппарата Е-сетей для целей распределенного имитационного моделирования, которая сводится к разработке метода синхронизации срабатывания Е-сетевых переходов с учетом модельного времени.

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

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

На базе предложенного теоретического метода и с учетом существующих стандартов High Level Architecture, Common Object Request Broker Architecture, Message Passing Interface (MPI), Petri Net Markup Language разработана распределенная система имитационного моделирования, ориентированная на многопроцессорные компьютеры, сети персональных компьютеров, MPI-кластеры. Данная система включает механизмы поддержки полунатурного моделирования, технологию хранения Е-сетевых моделей и графический интерфейс пользователя.

На примере моделей систем массового обслуживания проведено исследование возможностей разработанной системы моделирования и достоверности получаемых результатов. Проведено исследование производительности распределенной системы имитационного моделирования на многопроцессорном компьютере, в вычислительной сети и на MPI-суперкомпьютере. Полученные результаты показали эффективность применения распределенного моделирования, что выражается в уменьшении времени проведения экспериментов от 1,3 до 2,9 раза для различных вычислительных архитектур.

С помощью разработанной системы имитационного моделирования построены и исследованы полунатурные модели программно-аппаратного комплекса защиты телефонных и компьютерных сетей, алгоритмов преобразования данных для мультиплексора МП-30Е и аппаратно-программного комплекса оповещения абонентов. Распределенный характер процесса моделирования позволил привлечь к исследованиям территориально-удаленную группу разработчиков, что значительно (в 2 раза) сократило время разработки и выполнения моделей.

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

ABSTRACT

Havsiyevych I. B. Distributed Simulation System. - Manuscript.

Dissertation to gain the candidate degree of technical sciences on specialty 05.13.06 - Automated control systems and progressive information technologies” - The Institute of Mathematical Machines and Systems Problems NAS of the Ukraine, Kyiv, 2005.

The dissertation is devoted to theoretical and practical problems of distributed simulation systems development by E-nets improvements with using conservative approach.

In this paper the formal description of E-nets transition's algorithm and sequential scheduler's algorithm were described on Communication Sequential Processes language. It was shown that it is not efficient to use the classic sequential scheduler in case of E-nets in distributed environment. The method of parallel E-nets execution based on conservative approach and method of deadlock avoidance with using NULL-messages was developed.

The distributed simulation system was implemented with using Java, C++ languages, High Level Architecture, Common Object Request Broker Architecture, Message Passing Interface (MPI), Petri Net Markup Language standards and supports scaled-down simulation, model storage feature and Graphical User Interface.

The results adequacy was verified with using queue models. The performance of simulation system on multiprocessor machine, inside Local Area Network created from usual personal computers and on the MPI-cluster was analyzed.

Key words: distributed simulation, parallel program synchronization, E-nets, conservative approach, communication sequential processes, results adequacy, performance.

Размещено на Allbest.ru

...