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

Національний Технічний Університет України

«Київський Політехнічний Інститут»

діденко Дмитро Георгійович

УДК 004.94

Мультиагентна система дискретно-подійного імітаційного моделювання OpenGPSS

05.13.06 - Інформаційні технології

АВТОРЕФЕРАТ

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

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

Київ - 2010

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

Робота виконана на кафедрі автоматизованих систем обробки інформації і управління факультету інформатики та обчислювальної техніки Національного технічного університету України «Київський політехнічний інститут».

Науковий керівник: доктор технічних наук, професор Томашевський Валентин Миколайович, Національний технічний університет України «Київський політехнічний інститут», професор кафедри автоматизованих систем обробки інформації та управління факультету інформатики та обчислювальної техніки

Офіційні опоненти:

доктор технічних наук, професор Зайченко Юрій Петрович, Навчально-науковий комплекс «Інститут прикладного системного аналізу» Національного технічного університету України «Київський політехнічний інститут», професор кафедри математичних методів системного аналізу

доктор технічних наук, професор Казимир Володимир Вікторович, Інститут проблем математичних машин і систем НАН України, провідний науковий співробітник

З дисертацією можна ознайомитися в бібліотеці Національного технічного університету України «Київський політехнічний інститут» за адресою: 03056, просп. Перемоги 37, корп. 35.

Вчений секретар

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

доктор технічних наук Новіков О.М.

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

Актуальність теми дослідження

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

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

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

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

Зв'язок роботи з науковими програмами, планами, темами

Основні дослідження по темі дисертації тісно пов'язані з науковими дослідженнями, які проводяться кафедрою автоматизованих систем обробки інформації та управління (АСОІУ) факультету інформатики та обчислювальної техніки (ФІОТ) Національного технічного університету України «Київський політехнічний інститут» (НТУУ «КПІ»).

Мета і завдання дослідження

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

Апріорними вимогами до такої системи є:

- використання мови імітаційного моделювання GPSS;

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

- використання відкритих технологій;

- прозорість виконання задач користувача;

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

- підтримка моделей з великою кількістю прогонів;

- багатокористувацький режим роботи.

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

- аналіз існуючих підходів у проектуванні сучасних РСІМ;

- проектування та формалізація агентної архітектури РСІМ;

- удосконалення методу синхронізації модельного часу між агентами РСІМ;

- створення транслятора для мови імітаційного моделювання GPSS;

- формалізація розподіленого імітаційного моделювання прогонів моделей (тиражування);

- реалізація агентів і їх взаємодії, транслятора мови GPSS і тиражування експериментів в РСІМ;

- дослідження роботи імітаційної системи OpenGPSS в послідовному режимі та в режимі тиражування.

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

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

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

В дослідженні використано методи:

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

- абстрагування та математичного моделювання для створення імітаційних систем;

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

- обробки формальних мов для трансляції GPSS-програм;

- прийняття рішень при проектуванні архітектури системи.

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

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

вперше:

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

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

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

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

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

Практичне значення одержаних результатів

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

Агентну архітектуру можна використовувати для побудови нових розподілених обчислювальних систем. Матеріали дисертаційного дослідження доцільно використовувати у навчальних дисциплінах вузів, які пов'язані з моделюванням та розподіленими обчисленнями, наприклад, «Моделювання систем», «Компонентне програмування та розподілені системи» та ін.

Робота з РСІМ доступна у режимі онлайн через Інтернет портал Київського центру імітаційного моделювання за адресою http://www.simulation.kiev.ua.

«Науково-дослідний інститут прикладних інформаційних технологій» використовує РСІМ OpenGPSS у процесі розробки програмного забезпечення для прийняття управлінських рішень.

Особистий внесок здобувача

Усі матеріали, що представлені до захисту особисто отримані автором. У роботах [2, 5-12] автору дисертації належать всі теоретичні та практичні результати, крім постановки завдання та ідей теоретичних досліджень. У роботі [1] автором запропонована і формалізована агента архітектура РСІМ. Автору також належить програмна реалізація системи моделювання, дослідження її властивостей, а також побудова та дослідження імітаційних моделей. У статті [3] автор проводив порівняння систем моделювання в різних режимах роботи. На програмну систему OpenGPSS автором отримано свідоцтво № 22543 (від 05.11.2007) на реєстрацію авторського права на твір комп'ютерна програма «Мультиагентна система дискретно-подійного імітаційного моделювання OpenGPSS».

Апробація роботи

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

- XI Міжнародна наукова практична конференція «Інформаційні технології в економіці, менеджменті і бізнесі. Проблеми науки, практики і освіти» (м. Київ, 27-28 січня 2005 р.);

- Міжнародна наукова конференція «Інтелектуальні системи прийняття рішень та прикладні аспекти інформаційних технологій. (м. Євпаторія, 15-18 травня 2006 р.);

- XII Міжнародна наукова практична конференція «Інформаційні технології в економіці, менеджменті і бізнесі. Проблеми науки, практики і освіти» (м. Київ, 23-24 листопада 2006 р.);

- Друга науково-практична конференція з міжнародною участю «Математичне та імітаційне моделювання систем МОДС'2007» (м. Київ, 25-29 червня 2007 р.);

- Третья всероссийская научно-практическая конференция «Имитационное моделирование. Теория и практика» (Росія, м. Санкт-Петербург, 17-19 жовтня 2007 р.);

- XI Міжнародна науково-технічна конференція «Системний аналіз та інформаційні технології САІТ-2009» (м. Київ, 26-30 травня 2009 р.);

- Четверта науково-практична конференція з міжнародною участю «Математичне та імітаційне моделювання систем МОДС'2009» (м. Київ, 25-29 червня 2009 р.);

- Четвёртая всероссийская научно-практическая конференция по имитационному моделированию и его применению в науке и промышленности «Имитационное моделирование. Теория и практика» (Росія, м. Санкт-Петербург, 21-23 жовтня 2009 р.).

Публікації

За матеріалами дисертації опубліковано 12 наукових праць: три з яких у фахових збірниках зі спеціальності 05.13.06, вісім статей у збірниках матеріалів конференцій та одне - авторське свідоцтво на твір.

Обсяг та структура дисертації

Дисертація складається із вступу, чотирьох розділів, висновків, одного додатку, а також списку використаних джерел з 113 найменувань. Обсяг роботи становить 145 сторінки основного тексту, включаючи 18 рисунків та 41 таблицю.

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

В першому розділі «Постановка мети та завдань дослідження» розглянуті літературні джерела по темі дисертації. Виявляються і досліджуються проблеми розподіленого імітаційного моделювання та встановлюється клас розв'язуваних прикладних задач. Розглянуті вимоги апаратно-програмних систем та методи синхронізації модельного часу для РСІМ (консервативні та оптимістичні).

У другому розділі «Розробка архітектури системи» описується агентна архітектура системи, структура кластера моделювання та взаємодія вузлів моделювання між собою.

Під сервером імітаційного моделювання (SS) в роботі розуміється система дискретно-подійного імітаційного моделювання, яка призначена для зберігання моделей, об'єктів та проведення розподілених імітаційних експериментів. В якості сховища для моделей та даних на сервері використовується СУБД Oracle. Під кластером моделювання (SC) розуміється розподілене середовище для створення, виконання та керування імітаційним моделюванням у гетерогенній обчислювальній мережі, який складається з множини взаємодіючих серверів імітаційного моделювання.

Під агентом у системі OpenGPSS будемо розуміти програмну систему, яка має наступні властивості: автономність, реактивність, активність, комунікативність.

Система OpenGPSS використовує технологію взаємодіючих агентів, базується на кластері та підтримує динамічну переконфігурацію кластера у випадку відмови або при підключенні нового серверу. Інформація про мережеву топологію кластера використовується лише на системному рівні, що забезпечує прозорість імітації для користувачів. В GPSS-програмі немає директив для розпаралелювання, яке використовується у мовах паралельного програмування, наприклад у HPF та OpenMP Fortran.

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

Розглянемо більш детально архітектуру сервера моделювання SS, яка складається з взаємодіючих агентів: агент імітаційного моделювання AgSim, агент реплікації AgRep; агент розподілення навантаження AgSpl; агент синхронізації AgSnc; агент прийомо-передачі повідомлень AgTrf; агент продуктивності серверу AgPwr; агент взаємодії з користувачем AgUsr; агент збирання сміття AgGbr.

Нехай - множина активних агентів i-го сервера, де n - кількість серверів імітаційного моделювання у кластері.

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

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

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

Будь-яка зміна структури GPSS-моделі (перевизначення параметрів об'єктів при повторному виконанні операторів визначення з іншими значеннями операндів або додавання нових блоків) приводить до «застаріння» попереднього завдання та створенню на її основі нового.

При видаленні j-го завдання, цей агент переносить завдання зі списку активних завдань в список застарілих завдань та знищує всі списки i-го серверу від j-го завдання за допомогою оператору

Агент синхронізації AgSnc визначає завершення моделювання, коли вхідні списки агентів прийомо-передачі повідомлень для j-того завдання і списки СМП та СПП порожні, а також проводить розподілене підтвердження - синхронізує об'єкти на серверах. Після цього, за запитом користувача, агент AgUsr генерує стандартний звіт з результатами моделювання.

Агент реплікації AgRep копіює всі нові завдання з i-го серверу на z-й

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

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

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

Агент прийомо-передачі повідомлень AgTrf забезпечує обмін повідомленнями між серверами та підтримує цілісність системи відносно модельного часу

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

Неправильна послідовність повідомлень виникає тоді, коли приходять повідомлення з відмітками на раніший час, ніж поточний модельний час, у результаті чого виконуються відкати. Відкат можна розділити на дві частини: відновлення стану завдання серверу SS та видалення недійсних повідомлень з кластеру SC.

Для реалізації оптимістичної синхронізації використовуються черги вихідних повідомлень D та черги вхідних повідомлень Q. В якості алгоритму синхронізації використовується модифікований алгоритм віртуального часу (TimeWrap) Джефферсона з часовими вікном. Основою цього алгоритму є поняття антіповідомлення та поглинання повідомлення, за допомогою яких вирішується проблема визначення неправильної послідовності повідомлень і часткового відкату (відкат недійсних повідомлень). При цьому проблема відновлення стану j-го завдання на i-му сервері при відкаті вирішується засобами СУБД Oracle.

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

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

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

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

Механізм відкату активізується, коли агент AgTrf на вході отримує ранішнє повідомлення за це повідомлення, що відстає. Відкат передбачає відновлення стану j-го завдання i-го серверу SS (стан значень змінних) на стан до ранішнього повідомлення і скасування недійсних повідомлень шляхом відправки відповідних антіповідомлень. При відкаті локальний час переводиться назад та встановлюється рівним модельному часу повідомлення, що відстає, шляхом відновлення стану вузла моделювання на цей момент з черг агенту AgTrf.

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

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

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

Агент розділення навантаження AgSpl розподіляє навантаження серед серверів у кластері в залежності від структури GPSS-моделі (статичний аналіз) та навантаження серверів, отриманої від агенту AgPwr (динамічний аналіз). Робота агенту описується наступним оператором

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

На агент розділення навантаження також покладено виконання переконфігурації у випадку відмови одного з серверів. Відмова визначається агентом AgSnc на основі списку , який зберігається у агента AgTrf. Після цього на множині залежних серверів відбувається відкат до контрольної точки. Далі агент AgSpl знову розподіляє навантаження на нову множину серверів (виключається сервер, що відмовив) і моделювання продовжується. При додаванні нового серверу SS у кластері SC переконфігурація не відбувається до чергового запуску агенту розділення навантаження.

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

В системі OpenGPSS використовується оптимістичний підхід синхронізації, та агент AgSnc використовується як механізм глобального контролю. Агент підраховує глобальний віртуальний модельний час # для кожного завдання серверу (мінімум модельного часу всіх необроблених або частково-оброблених повідомлень або антіповідомлень.) Всі повідомлення та антіповідомлення, які зберігаються в СМП, у вхідних та вихідних чергах повідомлень агенту AgTrf з модельним часом меншим за глобальний час , можуть бути видалені з відповідних списків для всього кластеру.

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

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

Несуперечність моделей у точках зберігання необхідна для забезпечення відмовостійкості моделі (у разі відмови одного з серверів інформація виявляється скопійованою на інші сервери). Робота агенту захищена від відмов - використовується розподілена транзакція з двофазним підтвердженням 2PC. Перша фаза починається перед визначенням агентом глобального віртуального часу #. В контрольних точках всі об'єкти та всі списки на серверах однакові, чим досягається несуперечність проведення імітації. Оновлення даних про об'єкти відбуваються шляхом посилання повідомлень з модельним часом про стани об'єктів агентами AgTrf потрібних серверів, на яких, у випадку випередження часу , відбуваються відкати. При успішному проведені фази оновлення, виконується фаза підтвердження транзакції та на кожному сервері виконується фіксація транзакції (commit).

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

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

Агент продуктивності серверу AgPwr періодично проводить оцінку завантаженості процесору та розміри СМП, СПП, вхідних та вихідних черг агенту прийому-передачі повідомлень. При розмірах списків більше встановлених відбувається невідкладений запуск агенту AgSpl з використанням оператору #, агенту AgSnc з використанням оператору та (або) агенту AgGbr з використанням оператору .

Дані про завантаженість процесору зберігаються в СУБД Oracle за допомогою системного пакету dbms_application_info і доступні іншим агентам та завданням.

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

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

Транслятор складається з наступних частин:

1. Лексичний аналізатор, який транслює вхідну мову у внутрішній формат.

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

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

4. Синтаксичне дерево, в якому зберігається внутрішня структура вхідної GPSS-програми.

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

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

Етапами трансляції вхідної GPSS-програми є:

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

2) синтаксичний аналіз (побудова абстрактного синтаксичного дерева);

3) семантичний аналіз (побудова внутрішнього представлення моделі);

4) генерація коду (створення коду імітаційної моделі на внутрішній мові).

При обробці арифметичних виразів, транслятор використовує польський інверсний запис (ПОЛІЗ) для підвищення швидкості підрахунку чисельного значення арифметичного виразу, коли проводиться попередній синтаксичний розбір у стек вузлів, який складається з елементів згідно польського інверсного запису.

В четвертому розділі «Реалізація інтерпретатора OpenGPSS» описується реалізація системи моделювання мовою PL\SQL та проведення розподіленого імітаційного експерименту (або тиражування). Реалізовані сутності мови моделювання GPSS: одноканальні пристрої (Facility), багатоканальні пристрої (Storage), черги (Queue), функції (Function), логічні перемикачі (Logic Switch), матриці (Matrix), зберігаємі величини (Save Value), таблиці (Table), списки користувачів (User Chain), генератори (Generate). На прикладі розглядається особливості GPSS-програми, імітаційний експеримент для якої можна розділити на незалежні частини, паралельно їх обрахувати, а потім зібрати результат.

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

Розглянемо задачу керування запасами роботизованого цеху: деталі, які необхідні для роботи цеху, знаходяться в цеховому бункері і на складі. В цеховому бункері може зберігатися до 300 комплектів деталей, потреба в яких виникає через 8 ± 2 секунд і складає один комплект. У випадку зменшення запасів до трьох комплектів на протязі 3 хвилин формується вимога на поповнення запасів цехового бункеру до повного об'єму (300 комплектів), яка відправляється на склад, де на протязі 60 ± 20 с відбувається комплектування і за 180 ± 15 с виконується доставка та перезавантаження деталей у бункер. Промоделювати роботу цеху протягом місяця роботи. Знайти ймовірність простою цеху із-за відсутності деталей. Текст GPSS-програми для системи GPSS World приведений в табл. 1.

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

Текст тестової GPSS-програми (частина програми)

;одиниця модельного часу - секунда

**************Заявки з цехового бункеру************************

GENERATE 8,2

************В бункері залишилось менше чотири комплекти********

Low_bunker TEST NE X$Shop_Bunker,4,If_low_bunker

TEST E X$Shop_Bunker,0,Non_zero

***Запам'ятовуємо кількість відсутніх комплектів, які потрібні для виробництва**

LINK Denied,FIFO

************комплект йде на збирання і виходить з моделі**********

Non_zero SAVEVALUE Shop_Bunker-,1

TRANSFER ,Term

...

**************Моделюємо протягом 1-го місяця******************

GENERATE 604800 ;21#8#60#60

SAVEVALUE Timeout_probability,(CC$Denied/N$Low_bunker)

TERMINATE 1

*************Обчислювальний експеримент**********************

START 1

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

Таблиця 1

Порівняння результатів послідовного моделювання

Показник	Значення	GPSS/PC	GPSS World	OpenGPSS (один вузол)
Модельний час	604800	604800	604800
Ланцюг користувача DENIED
SIZE	Кількість транзактів у ланцюгу користувача	0	0	0
AVE.CONT	Середня довжина ланцюга користувача	0,60	0,609	0,6071
ENTRIES	Кількість входів транзактів у ланцюг користувача	4761	4819	4828
MAX	Максимальна довжина ланцюга користувача	23	23	23
AVE.TIME	Середній час перебуття транзакту в ланцюзі користувача	76,21	76,435	76,7269
Значення зберігаємої величини SHOP_BUNKER	239	249	237
Значення зберігаємої величини TIMEOUT_PROBABILITY	0,059	0,060	0,0600

Результати моделювання дещо відрізняються із-за різних датчиків псевдо-випадкових чисел (ДПЧ).

Розподілені обчислювальні експерименти (тиражування)

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

Тобто замість того щоб запускати програму моделювання три рази як раніше, виконуються комп'ютерні прогони за допомогою команд керування START, CLEAR і RMULT. В загальному випадку проміжні результати статистики можна зберігати у файлі командою WRITE (аналог команди RESULT).

За допомогою команди RMULT встановлюються початкові значення для всіх датчиків псевдовипадкових чисел. Команда START запускає обчислювальний експеримент. У GPSS-програмі можливо декілька разів використовувати команду START, для отримання проміжних результатів моделювання. Команда CLEAR очищує всю статистику системи і видаляє всі транзакти з моделі. Після виконання команди CLEAR уся система, крім ДПЧ, знаходиться у початковому стані. Команда WRITE заносить результати моделювання у тимчасовий буфер результатів, для збереження значень при наступному аналізі результатів (наприклад, за допомогою команди ANOVA).

Текст модифікованої GPSS-програми (фрагмент)

…

*************Обчислювальні експерименти***********************

CLEAR

RMULT 1,2,8,5,8,2,8

START 1

CLEAR

RMULT 5,1,6,6,7,1,1

START 1

CLEAR

RMULT 2,2,5,2,8,9,3

START 1

Сегмент обчислювального експерименту (СОЕ) - це послідовність команд керування, яка починається командою CLEAR або RMULT, містить не більш ніж по одній команді CLEAR, RMULT, START і закінчується командою START або RESULT. Сегменти обчислювального експерименту розділяються на два типи: залежні і незалежні.

Залежні сегменти обчислювального експерименту (ЗСОЕ) - такі СОЕ, які не містять команду RMULT або не містять команду CLEAR. Дані в таких сегментах залежать від передісторії станів системи, що моделюється.

Незалежні сегменти обчислювального експерименту (НСОЕ) - це такі СОЕ, які обов'язково складаються з послідовності команд CLEAR, RMULT, START. Саме послідовність команд CLEAR, RMULT заставляє систему “забути” свої попередні стани, тобто сегмент не залежить від передісторії станів системи.

Кадр сегмента обчислювального експерименту (КСОЕ) - це послідовність СОЕ, яка починається з одного НСОЕ, та включає в себе всі ЗСОЕ, які залежать від цього початкового сегменту.

Наявність послідовності команд CLEAR, RMULT, START, дозволяє виділити незалежні СОЕ, множину яких позначимо #, причому #. Усі інші СОЕ відносимо до залежних, множина - . Зауважимо, що перший СОЕ в моделі завжди незалежний, тому він належить множині .

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

З побудови КСОЕ випливає незалежність кадрів один від одного.

Нехай - множина КСОЕ на i-му вузлі для j-го завдання , тоді множина всіх кадрів на i-му вузлі . Результати проведення всіх СОЕ з КСОЕ позначимо, об'єднання результатів по всім КСОЕ i-го сервера дає загальний результат - .

Тобто проведення одного КСОЕ дає один і тільки один результат з множини .

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

Система OpenGPSS автоматично виділяє множину КСОЕ, які можуть одночасно виконуватись на різних вузлах кластера. Після запуску j-ої GPSS-моделі агент користувача AgUsr, який виконує функцію транслятора і переводить GPSS-текст у внутрішній формат та виділяє кадри СОЕ:

Агент реплікації AgRep копіює GPSS-модель та всі КСОЕ на інші вузли: тому кожний вузол повністю зберігає інформацію про модель та експеримент для запобігання втрат даних у разі вимкнення одного з вузлів.

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

Агент імітаційного моделювання AgSim виконує КСОЕ на i-му вузлі:

Агент реплікації AgRep, реалізований мовою PL/SQL, періодично копіює таблиці результатів REPORT и REPORT_DETAIL на інші вузли:

Потім AgRep виконує збирання результатів - об'єднання результатів всіх СОЕ для подальшого виконання та аналізу загальних результатів і завершує ОЕ.

Розглянемо приклад. Розділимо модифіковану GPSS-програму з табл. 3 на сегменти, отримаємо три СОЕ, які наведені в таблиці 4.

СОЕ1 - незалежний, тому що це перший СОЕ та його виконання ні від чого не залежить; СОЕ2 та СОЕ3 - також незалежні, тому що виконуються команди CLEAR, RMULT, які встановлюють “початковий” стан системи.

Таблиця 2

Уривок тексту GPSS-програми з сегментами (фрагмент)

Команди GPSS	Сегменти	Кадри сегментів
…
CLEAR	СВЕ1 (НСОЕ)	КСОЕ1
RMULT 1,2,8,5,8,2,8
START 1
CLEAR	СВЕ2 (НСОЕ)	КСОЕ2
RMULT 5,1,6,6,7,1,1
START 1
CLEAR	СВЕ3 (НСОЕ)	КСОЕ3
RMULT 2,2,5,2,8,9,3
START 1
	Неявне автоматичне зібрання результатів

З прикладу видно, що початкові значення всіх ДПЧ, які використовувались раніше обов'язково повинні бути перевизначені командою RMULT.

Проведемо з GPSS-програмою, яка наведена в табл. 4, обчислювальний експеримент в системі OpenGPSS для кількості вузлів кластера один, два та три вузла. Незалежні СОЕ можуть безпечно виконуватись на різних вузлах кластера імітаційного моделювання з подальшим збиранням результатів, що приводить до зменшення часу на проведення імітаційного експерименту. Якщо кластер складається з одного вузла, то всі СОЕ виконуються на ньому. При наявності двох вузлів: на одному вузлі виконуються два сегмента, а третій НСОЕ виконується на другому вузлі. Для трьох вузлів - кожен сегмент виконується на окремому вузлі. Середнє арифметичне результатів наведене в табл. 3.

Таблиця 3

Порівняння результатів розподіленого моделювання

Показник	Розшифровка	GPSS/PC	GPSS World	OpenGPSS (один вузол)	OpenGPSS (два вузла)	OpenGPSS (три вузла)
Астрономічний час моделювання, секунди	4	3	10	12	12
Модельний час	604800	604800	604800	604800	604800
Ланцюг користувача DENIED
SIZE	Кількість транзактів у ланцюгу користувача	0	0	0	0	0
AVE.CONT	Середня довжина ланцюга користувача	0,60	0,609	0,6071	0,6091	0,5934
ENTRIES	Кількість входів транзактів у ланцюг користувача	4761	4819	4828	4816	4735
MAX	Максимальна довжина ланцюга користувача	23	23	23	23	23
AVE.TIME	Середній час перебуття транзакту в ланцюзі користувача	76,21	76,435	76,7269	76,5235	75,7537
Значення зберігаємої величини SHOP_BUNKER	239	249	237	255	251
Значення зберігаємої величини TIMEOUT_PROBABILITY	0,059	0,060	0,0600	0,0600	0,0591

Системи GPSS/PC та GPSS World не можуть працювати в розподіленому режимі, тому для них наведена інформація при послідовному проведенні експерименту. Як видно з табл. 5 результати моделювання знову «приблизно» однакові.

Порівняння швидкості моделювання

Розглянемо, як розмір прогону впливає на швидкість моделювання, для чого в нашій останній GPSS-програмі у рядку «GENERATE 604800», де відбувається моделювання протягом 1-го місяця (604800=21день*8годин*60хвилин*60секунд), будемо використовувати 2,3,..12 місяців. Усі експерименти для OpenGPSS будемо проводити для різної кількості вузлів кластера. Результати проведення експериментів відображені на рис. 2., де по осі абсцис відкладено кількість місяців в прогоні, а по осі ординат - астрономічний час в секундах.

Рис.1. Залежність астрономічного часу моделювання від кількості місяців в прогоні

Система GPSS/PC є 16-ти бітною прикладною програмою і на моделях з великою кількістю транзактів (більше 9-го місяця) видає помилку «брак пам'яті». GPSS World на початку графіку (1-5 місяців) затрачує приблизно однаковий час на відповідні прогони. Значення астрономічного часу для системи з двома вузлами «приблизно» таке саме як і для одного вузла, тому що GPSS-програма містить три (непарне число) сегмента, із-за чого один з вузлів «чекає» другий вузол поки той послідовно моделює два сегменти, після чого виконується неявне збирання результатів. Швидкість збільшується але не в два рази. На тренд, що відображає час для трьох вузлів, на початку моделювання впливають накладні витрати, але на відрізку 9-12 місяців система моделювання OpenGPSS випереджає GPSS World.

ВИСНОВКИ

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

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

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

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

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

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

6. Запропоновано підхід розділення експерименту над GPSS-програмою, який раніше виконувався лише послідовно, на незалежні частини для подальшого паралельного виконання на вузлах кластера та зібрання результатів, що підвищує продуктивність і надійність системи та зменшує час моделювання. Отримані практичні результати підтверджують можливість автоматичного розділення експерименту на незалежні частини для підвищення швидкості моделювання (швидкість моделювання підвищилась у 1,3 рази на кластері з трьома вузлами).

7. Теоретичні результати реалізовано як система моделювання OpenGPSS, яка доступна для використання на порталі Київського центру імітаційного моделювання http://www.simulation.kiev.ua для онлайн роботи. Система OpenGPSS застосовується на кафедрі автоматизованих систем обробки інформації та управління ФІОТ НТУУ «КПІ» для проведення лабораторних робіт з дисципліни «Моделювання систем», а також у «Науково-дослідному інституті прикладних інформаційних технологій» для прийняття управлінських рішень у процесі розробки програмного забезпечення.

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

1. Томашевский В.Н., Диденко Д.Г. Агентная архитектура распределенной дискретно-событийной системы имитационного моделирования OpenGPSS // Системні дослідження та інформаційні технології. м. Київ - 2006. - № 4. - С. 123-132.

2. Дiденко Д.Г. Реалізація тиражування обчислювального експерименту в розподіленій системі моделювання OpenGPSS // Наукові вісті. м. Київ - 2007. - № 5. - С. 49-53.

3. Томашевський В.М., Діденко Д.Г. Порівняння результатів роботи систем імітаційного моделювання OpenGPSS та GPSS/PC // Вісник НТУУ «КПІ». Інформатика, управління та обчислювальна техніка: Зб. наук. пр. - К.: Век+. - 2008. - № 49. - С. 47-53.

4. Свідоцтво №22543 (від 05.11.2007) на реєстрацію авторського права на твір комп'ютерна програма «Мультиагентна система дискретно-подійного імітаційного моделювання OpenGPSS».

5. Діденко Д.Г. Агентная архитектура распределенной дискретно-событийной системы моделирования бизнес-процессов // X Міжнародна наукова практична конференція «Інформаційні технології в економіці, менеджменті та бізнесі. Проблеми науки, практики і освіти, м. Київ. - 2006. - С.131-135.

6. Діденко Д.Г. Агент реплікації в розподіленій дискретно-подійній системі імітаційного моделювання OpenGPSS // Міжнародна наукова конференція «Інтелектуальні системи прийняття рішень та прикладні аспекти інформаційних технологій, м. Євпаторія. - 2006. - т.1 - С.264-266.

7. Діденко Д.Г. Реплікація в розподіленій дискретно-подійній системі імітаційного моделювання OpenGPSS // X Міжнародна наукова практична конференція «Інформаційні технології в економіці, менеджменті і бізнесі. Проблеми науки, практики і освіти, м. Київ. - 2006. - С.135-139.

8. Диденко Д.Г. Тиражирование независимых сегментов вычислительного эксперимента в распределенной дискретно-событийной системе имитационного моделирования OpenGPSS // Друга науково-практична конференція з міжнародною участю «Математичне та імітаційне моделювання систем МОДС'2007», м. Київ. - 2007. - С.157-160.

9. Диденко Д.Г. Взаимодействие агентов в распределенной дискретно-событийной системе имитационного моделирования OpenGPSS // Третья всероссийская научно-практическая конференция «Имитационное моделирование. Теория и практика» (ИММОД-2007), г. Санкт-Петербург. - 2007. - т.1 - С.272-276.

10. Диденко Д.Г. Сравнение скорости проведения экспериментов в системах имитационного моделирования OpenGPSS и GPSS/PC // XI Міжнародна науково-технічна конференція «Системний аналіз та інформаційні технології» (САІТ-2009), м. Київ. - 2009. - С.485-486.

11. Діденко Д.Г. Особливості переходу від послідовного моделювання у системі GPSS\World до розподіленого моделювання у системі OpenGPSS // Четверта науково-практична конференція з міжнародною участю «Математичне та імітаційне моделювання систем МОДС'2009», м. Київ. - 2009. - С.197-201.

12. Диденко Д.Г. От последовательного моделирования в системе GPSS\World к распределённому моделированию в OpenGPSS // Четвёртая всероссийская научно-практическая конференция по имитационному моделированию и его применению в науке и промышленности «Имитационное моделирование. Теория и практика» (ИММОД-2009), г. Санкт-Петербург. - 2009. - т.1 - С.251-256.

АНОТАЦІЇ

Діденко Д.Г. Мультиагентна система дискретно-подійного імітаційного моделювання OpenGPSS. - Рукопис.

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

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

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

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

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

Отримано результати, які підтверджують можливість автоматичного розділення експерименту на незалежні частини для підвищення швидкості моделювання (при цьому швидкість моделювання підвищилась у 1,3 рази на кластері з трьома вузлами).

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

Диденко Д.Г. Мультиагентная система дискретно-событийного имитационного моделирования OpenGPSS. - Рукопись.

Диссертация на соискание учёной степени кандидата технических наук по специальности 05.13.06 - Информационные технологии. - Национальный технический университет Украины «Киевский политехнический институт», Киев, 2010.

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

Предложена агентная архитектура распределенной системы имитационного моделирования. Формализована работа каждого агента в системе OpenGPSS. Агенты реализованы как программные компоненты (пакеты) языком PL\SQL в СУБД Oracle. Для отката состояния узла при оптимистической синхронизации используются транзакции СУБД. Кластер имитационного моделирования не имеет статически выделенного главного узла, а при необходимости каждый раз определяет его динамически, что повышает отказоустойчивость всего кластера. Использование агентов в имитационных системах повышает масштабируемость, отказоустойчивость и надежность, при незначительном снижении производительности из-за избыточности данных, и поддержания целостности имитаций.

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

...