|
НАЦІОНАЛЬНА АКАДЕМІЯ НАУК УКРАЇНИ
ІНСТИТУТ ПРОБЛЕМ МАТЕМАТИЧНИХ МАШИН І СИСТЕМ
Гавсієвич Ілля Борисович
УДК 004.94
РОЗПОДІЛЕНА СИСТЕМА
ІМІТАЦІЙНОГО МОДЕЛЮВАННЯ
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.
Будь-який перехід  можна описати
де
 – тип переходу; – час затримки на переході; – процедура перетворення атрибутів; ,  – результат обчислення керуючої процедури. Результат обчислення може бути невизначеним –  , або належати множині вхідних (для переходу типу  ) чи вихідних (для переходу типу  ) позицій,  ,  .
Функція  визначає, чи виконані умови спрацьовування переходу  ;  – означає, що умови спрацьовування виконані й перехід готовий до спрацьовування;  – означає, що умови спрацьовування не виконані. Визначення функції  залежно від типу переходу наведено в таблиці 1.
Таблиця 1
Визначення функції  залежно від типу переходу
Продовження табл. 1
При спрацьовуванні Е-мережевого переходу відбувається переміщення міток із вхідних позицій у вихідні за правилами, визначеними для різних типів переходів.
Зміна розмітки  у нову розмітку  ,  при спрацьовуванні переходу  залежно від його типу, наведена в таблиці 2.
Таблиця 2
Зміна розмітки мережі при спрацьовуванні переходу
Продовження табл. 2
Алгоритм роботи Е-мережевого переходу  можна описати блок-схемою, що наведена на рис. 1.
Алгоритм роботи послідовного планувальника, що керує системою імітаційного моделювання, яка дозволяє досліджувати моделі, описані за допомогою апарату Е-мереж, приведений на рис. 2 – 4.
На блок-схемах були використані такі позначення:
 – поточний модельній час; – список подій;  – подія закінчення затримки переходу  , запланована на момент часу  (таким чином, в даному алгоритмі список подій містить затримані переходи); – проекція вектора  на  -у вісь; якщо  – множина векторів однакової довжини, то  – множина проекцій всіх векторів з  на  -у вісь –  ; – підпрограма, яка з множини пасивних (що не перебувають у стані затримки) переходів виділяє ті, в яких виконані умови спрацьовування; обчислює час затримки на переході; формує події та додає їх у список подій; – підпрограма, яка з множини затриманих переходів виділяє ті, в яких відбулися події закінчення затримки, оновлює список подій і дозволяє спрацьовування переходу.
В роботі для організації паралельного виконання імітаційних моделей використовується процесо-орієнтована парадигма. Представимо традиційну систему імітаційного моделювання, побудовану на базі Е-мереж, як множину процесів  та процес  , і опишемо її формально в межах теорії Communicating Sequential Process (CSP), де
 – процес, реалізуючий роботу Е-мережевого переходу; – процес, реалізуючий роботу планувальника.
Процес  має наступний алфавіт:
 (3)
 .
Формальне визначення процесу  приведено нижче:
 (4)
 .
Стани процесу  показані на рис. 5.
Рис. 5. Стани процесу 
Множину паралельно працюючих переходів  можна визначити
 . (5)
Процес  має наступний алфавіт:
 (6)
 .
Формальне визначення процесу  приведено нижче:
 □ (7)
 ;
  (8)
 ;
  (9)
 .
Стани процесу  показані на рис. 6.
Запуск процесу планувальника можна визначити як
 . (10)
Тоді всю систему в цілому можна визначити
 . (11)
Процес планувальника  і процес окремого переходу  працюють паралельно і синхронізують свою роботу шляхом одночасної участі в подіях з множини спільних подій, що отримані в результаті перетину їхніх алфавітів:
 (12)
 .
| 
