УДК 681.3.06, 519.8
В.В. ЛИТВИНОВ, В.В. КАЗИМИР, І.Б. ГАВСІЄВИЧ
АЛГОРИТМ ПАРАЛЕЛЬНОГО ВИКОНАННЯ ТА СИНХРОНІЗАЦІЇ Е-МЕРЕЖІ
Abstract: The paper is devoted to theoretical and practical problems of performing E-nets imitation models with using conservative approach. The E-nets transitions algorithm and sequential scheduler&s algorithm were formalized. The parallel processes of transitions and scheduler were marked out and described on Hoare&s CSP language.
Анотація: В статті розглядаються принципи паралельного виконання Е-мережевих імітаційних моделей на основі процесо-орієнтованої парадигми та створення алгоритму синхронізації паралельних ділянок в межах консервативного підходу з застосуванням методу запобігання взаємних блокувань на базі NULL-повідомлень. Для досягнення поставленої мети формалізовано алгоритми роботи Е-мережевого переходу та планувальника при традиційному послідовному моделюванні, виділено паралельні процеси переходів і планувальника, а також розроблено їхній формальний опис за допомогою процесної алгебри CSP Т. Хоара. Ключові слова: розподілене імітаційне моделювання, синхронізація паралельних програм, Е-мережі, консервативна схема, CSP.
Аннотация: В статье рассматриваются принципы параллельного выполнения Е-сетевых имитационных моделей на основе процессо-ориентированной парадигмы и построения алгоритма синхронизации параллельных участков в рамках консервативного подхода с применением метода предотвращения взаимных блокировок на базе NULL-сообщений. Для достижения поставленной цели формализовано алгоритм работы Е-сетевого перехода и планировщика при традиционном последовательном моделировании, выделены параллельные процессы переходов и планировщика, а также разработано их формальное описание с помощью процессной алгебры CSP Т. Хоара.
Сучасні тенденції в області інформаційних технологій виносять на порядок денний питання створення розподілених систем імітаційного моделювання (РСІМ), здатних реалізувати додаткові переваги моделювання як методу дослідження складних систем [1, 2].
При створенні РСІМ необхідно враховувати:
- цільову апаратно-програмну платформу;
- математичну основу РСІМ;
- схему синхронізації паралельних ділянок;
- засоби реалізації РСІМ.
У роботі будемо орієнтуватися на розподілені апаратні платформи, що складаються із звичайних персональних комп&ютерів, об&єднаних у локальні мережі, а також на MPI-кластери. Для формалізованого опису структури й процесу функціонування в РСІМ будемо використовувати математичний апарат Е-мереж [3, 4]. В роботі була обрана базова консервативна схема синхронізації виконання паралельних процесів на базі NULL-повідомлень [5, 6]. Технологічною базою побудови РСІМ послужить специфікація CORBA [7].
Метою даної статті є розробка принципів паралельного виконання Е-мережевих імітаційних моделей на основі процесо-орієнтованої парадигми та створення алгоритму синхронізації паралельних ділянок у межах консервативного підходу з застосуванням методу запобігання взаємних блокувань на базі NULL-повідомлень.
Формально Е-мережу EN можливо визначити п&ятіркою:
EN = (P, T, Pre, Post, ju0), (1)
де P - кінцева непуста множина позицій;
T - кінцева непуста множина переходів; множини переходів і позицій не
перетинаються, T О P = 0;
Pre: T U P — { 0,1} - вхідна функція; Pre(t, p ) = 1 - означає, що існує дуга, яка веде з позиції p Є P до переходу t Є T; Pre(t, p) = 0 - означає, що такої дуги не існує. Тоді IN(t) = { p є PI Pre(t, p) = 1} - множина всіх вхідних позицій переходу t Є T;
Post: T U P — { 0,1} - вихідна функція; Post(t, p) = 1 - означає, що існує дуга, яка веде від переходу t Є T у позицію pЄ P ; Post(t, p) = 0 - означає, що такої дуги не існує. Тоді OUT(t) = {p Є P|Post(t, p) = 1} - множина всіх вихідних позицій переходу t Є T;
¡: P —— {0,1} - функція розмітки, що визначає маркування або стан позиції; ¡( p) = 0 - означає, що позиція p Є P вільна (не містить мітку); ¡(p) = 1 - означає, що позиція зайнята (містить метку); ¡0 - початкова розмітка мережі.
В даній роботі розглянемо базисний набір переходів, який визначається множиною типів
D = {"T","F"," J","X","Y"}.
Будь-який перехід tЄ T можна описати:
& d t z) для переходів типу "T", "F" або "J"
p = < (d,t, z,rx), для переходу типа "X" (2)
(d, t, z, ry), ,,
для переходу "Y" ,
де d Є D - тип переходу;
tЄ - час затримки на переході; z - процедура перетворення атрибутів;
rx, ry - результат обчислення керуючої процедури. Результат обчислення може бути невизначеним - FAIL або належати множині вхідних (для переходу типу "Y") чи вихідних (для переходу типу "X") позицій, rx Є OUT(t )u{ FAIL}, ry Є IN (t )u{ FAIL}.
Функція Enabled: T — {0,1} визначає, чи виконані умови спрацьовування переходу t Є T; Enabled(t) =1 - означає, що умови спрацьовування виконані й перехід готовий до спрацьовування; Enabled (t) = 0 - означає, що умови спрацьовування не виконані.
Визначення функції Enabled (t) залежно від типу переходу наведено в табл. 1.
Таблиця 1. Визначення функції Enabled (t) залежно від типу переходу
in out Щ<-з f 1, якщо \\ju(in)= і]л[и(оиГ ) = 0] Enabled (t ) = < 10, інакше, де in є IN(t), out є OUT(t)
in (•> “F ~Q& .-O- V oum Enabled (t ) = < де in 1, якщо \\m(in) = і]л л \\"out є OUT(t): m(out) = 0] 0, інакше, Є IN (t)
f IN(t)< I .(•>* out <) " Enabled (t ) = < де ou 1, якщо \\"in є IN(t): /u(in) = і] л л \\m(out ) = 0] 0, інакше, it є OUT(t)
in (•> rx <” > oum ) Enabled (t ) = < де in 1, якщо [m(in) = і]л л \\rx Ф FAIL] л \\m(rx) = 0] 0 інакше, є IN(t), rx є OUT(t)
IN (t) -► ry ‘Y out О Enabled (t ) = < де ry 1, якщо \\ry Ф FAIL]л \\m(ry) = 1]л л \\m(out )=0] ,0, інакше, ;є IN (t), out є OUT (t)
При спрацьовуванні Е-мережевого переходу відбувається переміщення міток із вхідних позицій у вихідні за правилами, визначеними для різних типів переходів.
Зміна розмітки /ц(р) у нову розмітку JLl&(p), "Р Є [IN (t )u OUT (t)] при спрацьовуванні переходу t Є T залежно від його типу, наведені в табл. 2.
Таблиця 2. Зміна розмітки мережі при спрацьовуванні переходу
in ® out 0+0 “T” /{in ) = 0, //{out ) = 1
“F р0і >оищ -oj /{in ) = 0, V out є OUT {t): /{out ) = 1
Продовження табл.2
ще, < && \\ out «М j” т&(т )= 0, m(rx) = 1, V out є [OUT(t) \\ {rx}]: ¡/(out) = /u(out)
J®* IN®< гу “&l out М А ) 0 г m(in )= 0, /(rx) = 1, V out є [OUT(t) \\ {rx}]: /(out) = /(out)
Г®* out -Н 4 ) /(ry )= 0, V in є [IN(t) \\ {ry}]: /(in) = /(in),
«к ‘"1 • г / (out) = 1
Алгоритм роботи Е-мережевого переходу можна описати блок-схемою, що наведена на рис. 1.
Алгоритм роботи планувальника, що керує системою імітаційного моделювання, яка дозволяє досліджувати моделі, описані за допомогою апарату Е-мереж, приведений на рис. 2 - 4.
На блок-схемах були використовуються такі позначення:
- time - поточний модельний час;
- EL - список подій; (t, tim^j - подія закінчення затримки переходу t Є T,
запланована на момент часу time (таким чином, у даному алгоритмі список подій містить затримані переходи);
- PkV - проекція вектора V на k-у вісь; якщо W - множина векторів однакової довжини, то PkW - множина проекцій усіх векторів з W на k-у вісь -pW = \\pkw\\wЄ W};
- SCHEDULER1 - підпрограма, яка з множини пасивних (що не перебувають у стані затримки) переходів виділяє ті, в яких виконані умови спрацьовування; обчислює час затримки на переході; формує події та додає їх у список подій;
- SCHEDULER2 - підпрограма, яка з множини затриманих переходів виділяє ті, в яких відбулися події закінчення затримки, оновлює список подій і дозволяє спрацьовування переходу.
Затримка на час т
Процедура перетворення г І
Спрацьовування переходу
Рис. 1. Алгоритм роботи переходу І Є Т Рис. 2. Алгоритм роботи планувальника
Рис. 3. Алгоритм підпрограми SCHEDULER1 Рис. 4. Алгоритм підпрограми SCHEDULER2 4. Організація паралельного виконання імітаційних моделей
Представимо традиційну систему імітаційного моделювання, побудовану на базі Е-мереж, як множину процесів TRANSITION (t) та процес SCHEDULER(time,EL) і опишемо її формально в межах теорії CSP [8], де
- TRANSITION (t) - процес, реалізуючий роботу Е-мережевого переходу t є T;
- SCHED ULER(time, EL) - процес, реалізуючий роботу планувальника.
Процес TRANSITION (t) має такий алфавіт:
a TRANSITION(t) = { condition.t, conditionFail. t, (3)
conditionOk. t, delay. t, activate. t, deactivate, t, transformation. t, fire. t}.
Формальне визначення процесу TRANSITION (t) приведено нижче:
TRANSITION(t) = condition.t ®
(conditionFail.t ® TRANSITION (t )
| conditionOk. t ® delay. 11 ® activate. t ? time ® deactivate. t ® transformation. t ® fire. t ® TRANSITION(t ) ). Стани процесу TRANSITION (t ) показані на рис. 5.
Множину паралельно працюючих переходів TRANSITIONS можна визначити:
TRANSITIONS =||tîT TRANSITION (t ).
Процес SCHED ULER(time, EL) має такий алфавіт:
a SCHEDULERtime, EL) = { condition,conditionFail, conditionOk, delay, activate,nextEvent,deactivate }. Формальне визначення процесу SCHEDULER(time,EL) приведено нижче: SCHEDULER(time, EL) = SCHEDULERl(time,EL) □
SCHEDULERitime, EL) ; SCHEDULERl(time,EL) = \\tïEL [condition.t ®
(conditionFail. t ® SCHEDULER{time,EÜ)
| conditionOk. t ® delay. t ? t ® activate. t ! time ® SCHEDULERtime, EL è {t}) ) ] ; SCHEDULER2(time,EL)= \\tîEL [nextEvent.t ®
deactivate, t ® SCHEDULERÜtime, EL \\ {t}) ].
Стани процесу SCHEDULEF(time,EL) показані на рис. 6.
conditionFail.t
Рис. 5. Стани процесу TRANSITION (t ) Рис.6. Стани процесу SCHED ULER (tim e, EL )
Запуск процесу планувальника можна визначити як
SCHED ULE = SCHED ШЕФ, 0).
Тоді всю систему в цілому можна визначити:
SYSTEM = SCHEDULE|| TRANSITIONS
Процес планувальника SCHEDULER(time,EL) і процес окремого переходу TRANSITION (t)
працюють паралельно і синхронізують свою роботу шляхом одночасної участі в подіях з множини подій, яка отримана в результаті перетину їхніх алфавітів:
Використання традиційного планувальника, заснованого на глобальному списку подій при описаній вище організації паралельного виконання, не є ефективним через велику кількість повідомлень між планувальником і окремим переходом.
У даній роботі пропонується не використовувати глобальне керування модельним часом, а реалізувати планування в кожному переході локально і розробити спеціальні механізми синхронізації модельного часу між переходами.
На основі консервативної схеми синхронізації та методу запобігання взаємних блокувань на базі ШИ-повідомлень розробимо модифікації Е-мереж для синхронізації виконання паралельних ділянок.
a SCHED ULERtime, EL) n a TRANSITION(t) { condition.t, conditionFail. t,conditionOk. t, delay. t,activate. t deactivate, t}.
Lvt : T ® Â+ .
Ts : Р ®^+.
нижня часова границя з усіх вхідних
outb (t)={p є out(t)|m(p)=1}, outf (t )={ p є ouT(t)|m(p)=0}, (17)
OUTB (t) n OUTF (t) = 0, OUTB (t) u OUTF (t) = OUT (t).
Таблиця 3. Визначення функції Єожегуаі^е(ї) залежно від типу переходу
in out ®+о “Т” Conservative(t) = 1
in “F > оиці) oJ Conservative(t) = 1
г®* im < " ’ І®* out 4J 1” Conservative(t) = 1
іп (•> ... j>OL/7>(f) ■ • • > OUTdt) <•)] Conservative(t) = < де MINq 1, якщо [" out є OUTB (t): Ts (out) > MINof (t) ] інакше, F (t) = min[ Ts(out)], Vout є OUTF (t)
INB(t) < inf(q < ► &О out о г Conservative(t) = < де MINib 1 якщо [V in є INf (t): ’ Ts(in )> MIN1b (t)] ß’ інакше, 3(t) = min [ Ts (in) ], V in є INB (t)
Таблиця 4. Визначення функції АеіІуаіеТ8 (і) залежно від типу переходу
in out 0~Ь© “Т” ActivateTS (t) = max [ Ts (in), Ts (out) ], де in є IN(t), out є OUT(t)
in “F _*/ * ^ V OUT(t) J ActivateTS (t) = max( Ts(in), [max( Ts(out)), Vout є OUT(t)]), де in Є IN(t)
IN(t) < V % out “K * ) j” ActivateTS(t) = max( [max( Ts(in)), Vin є IN(t) ], Ts(out)), де out Є OUT(t)
in rx ) фт: ■N. V OUT(t) J ActivateTS (t) = max[ Ts(in), Ts(rx) ], де in є IN(t), rx є OUT(t)
IN(t) < (•> “Y out M A J 0 ActivateTS (t) = max[ Ts(ry), Ts(out) ], де ry є IN(t), out є OUT(t)
зміна часової відмітки Ts(p) на нову часову відмітку Ts&(p), Vp Є [IN (t )u OUT (t)] при
спрацьовуванні переходу tЄ Tзалежно від його типу наведені в табл. 5.
V in є INB (t): [ ju&(in) = /(in), Ts&(in) = Lvt(t) ]; (18)
V out є OUTF (t): [ /(out) = /(out), Ts&(out) = Lvt(t) ].
Таблиця 5. Зміни розмітки мережі та часових відміток позицій при спрацьовуванні переходу залежно від його типу
in ® out 0+0 “T" m(in ) = 0, Ts&(in ) = Lvt (t); ¡¿(out ) = 1, Ts (out ) = Lvt (t)
in/& “ _*/ * \\ V OUT(t) ¡¿(in ) = 0, Ts&(in ) = Lvt (t); V out є OUT (t): [¿(out ) = 1, Ts& (out ) = Lvt (t)]
IN{f)< out " V in є IN(t): [ ¿&(in) = 0, Ts&(in) = Lvt(t) ]; ¿(out ) = 1, Ts& (out ) = Lvt (t)
in у rx “H ^ ) X" Л V 0UT(t) J ¿(in ) = 0, Ts(in ) = Lvt (t); ¿(rx ) = 1, Ts&(rx ) = Lvt (t); V out є [ OUT (t) \\ { rx}]: [ ¿(out) = ¿(out), Ts& (out) = Ts(t) ]
IN(t) < { ► (•> “V out -K Д ) • ¿(ry) = 0, Ts (ry) = Lvt(t); Vin є [IN(t)\\ {ry}]: [ ¿(in ) = ¿(in ), Ts& (in ) = Ts(in ) ]; ¿(out) = 1, Ts (out) = Lvt(t)
Тепер уся система складається з множини процесів MTRANSITION(t), реалізуючих роботу модифікованого Е-мережевого переходу t Є T. Цей процес має алфавіт:
a MTRANSITION(t) = {lowBound. t conservative. t, (19)
conservativeFail. t, conservativeOk. t, condition. t, conditionFail. t, conditionOk. t, delay. t, activate. t, deactivate.t,transformation.t,fire.t,nullMessages.t }.
Формальне визначення процесу MTRANSITION (t) наведено нижче:
MTRANSITION(t) = lowBound. t ® conservative. t ® (20)
(conservativeFail. t ® MTRANSITION2(t)
| conservativeOk. t ® condition.t ®
(conditionFail. t ® MTRANSITION2(t)
| conditionOk. t ® delay. t! t ® activate. t ? time ® deactivate. t ®
transformation. t ® fire. t ® MTRANSITION2(t)); MTRANSITION2(t) = nullMessages. t ® MTRANSITION(t). Стани процесу MTRANSITION (t) наведені на рис. 8.
Множину паралельно працюючих переходів MTRANSITIONS можна визначити:
MTRANSITIONS = \\fT MTRANSITION(t).
Розроблені у роботі формальні описи на CSP також можуть бути використані для аналізу і верифікації за допомогою спеціалізованих програм, таких як Process Behavior Exploration (ProBE) та Failures-Divergence Refinement (FDR), розроблених Formal Systems (Europe) Ltd [9].
Рис. 7. Модифікований алгоритм роботи Е-мережевого переходу t є T
transformation, і
deactivate, і
Рис. 8. Стани процесу MTRANSITION( t)
В роботі розроблені принципи паралельного виконання Е-мережевих імітаційних моделей на основі процесо-орієнтованої парадигми та створення алгоритму синхронізації паралельних ділянок в межах консервативного підходу з застосуванням методу запобігання взаємних блокувань на базі ЫиИ-повщомлень.
Для досягнення поставленої мети формалізовано алгоритми роботи Е-мережевого переходу та планувальника при традиційному послідовному моделюванні, виділено паралельні процеси переходів і планувальника, а також розроблено їхній формальний опис за допомогою процесної алгебри СЭР Т. Хоара.
Алгоритм паралельного виконання Е-мережевих моделей може бути реалізований в інших розподілених системах імітаційного моделювання. Формальні описи паралельних процесів переходів і планувальника мовою ОБР можуть бути застосовані в подальших розробках і верифікації паралельних програм.
СПИСОК ЛІТЕРАТУРИ