автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.12, диссертация на тему:Структурированные сети Петри в системах проектирования специализированных процессоров

МШ1СТЕРСТВ0 0СВ1ТИ I НАУКИ УКРА1НИ

ХАРК1ВСБКИЙ ДЕРЖАВШЙ ТЕХН1ЧНИЙ УН1ВЕРСИТЕТ РАДЮЕЛЕКТР0Н1КИ

, СЛЬ"НАНШОВ ДМИТРО БОРИСОВИЧ

О А )] ,.

УДК 519.71: 681.32/34

СТРУКТУРОВАШ МЕРЕЖ1 ПЕТР1 У СИСТЕМАХ ПРОЕКТУБА11ПЯ СГ1ЕЦ1АЛ130ВАНИХ ПРОЦЕСОР1В

05.13.12 - систем» автоматизаци проектувальних роб1т

АВТОРЕФЕРАТ

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

Харюв - 2000

Дисерташею е рукопис.

Робота виконана у Харювському державному техлпчному ушверситеп радюелектрошки, Мнпстерство освш! 1 науки Украшл.

Науковий кер1вник кандидат техшчиих наук

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

Оф1Д1Гпг1 опоненти: доктор техшчних наук, професор Фштненко 1гор Григорович,

Харювська державна академш загоничного транспорту, завщувач кафедри обчислювальноТ техшки та систем керування;

доктор техшчних наук, професор Вайнер Володимир Герасимович, Науково-техшчний центр електроф1зично! обробки НАН Украши, завщувач вщдшом.

Провщна установа Харивський державний полкехшчний ушверситет (кафедра обчислювально! техшки та програмування), Мннстерство освети 1 науки Украши, м. Харгав.

Захист в1дбудеться ". "Т^Зу^/г^-Р_2000 року о годиш

на засщанш спешашзовано!' вчено! ради Д 64.052.02 у Харювському державному техшчному ушверситеп радюелектрошки за адресою: 61166, м. Харив, пр. Лeнiнa, 14.

3 дисерташею можна ознайомитись у б1блютеш Харывського державного техш'чного ушверситету радюелектрошки за адресою: 61166, м. Харюв, пр. Ленша, 14.

Автореферат розшланий " ^^ " ^^ 2000 року.

Вчений секретар спешатзовано! вчено'1 ради

Безкоровайний В.В.

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

Актуальшсть теми. Виникнення ново! шформацшно! технологи е зако-ном1рним етапом удосконалювання процеЫв людино-машинного спшкування, у ход1 розвитку яких були виpoблeнi певш вимоги до Ш€1 технологи. Нова сучас-на шформацшна технолопя повинна бути пристосована до користувача, який не е програмютом за фахсм. Користувач за рахунок ново! технологи одержить можливють самостшно'! робота ¡з системою понять предметно! галуз!, можливють видшення в предметнш галуз! об'екпв 1 зв'язюв, суттевих для виршення задач!. Це вимагае нового ртня «штелектуальностт ЕОМ зокрема, здатност! ЕОМ спшкуватися з користувачем на зрозумшш йому мовг

Ор!ентац!я сучасних САПР на проектування складних обчислювальних систем призвела до виникнення нових мов проектування (наприклад, УНБЬ 1 Verilog), що опнсують не структуру проектованого об'скта, а правила його фун-кшонування. При цьому складнють таких мов проектування пор!вняна з! склад-шстю сучасних мов програмування. Для спрошення пронесу проектування в сучасш САПР почали вводити модул!, що дозволяють описувати функшону-вання об'екта проектування на бшьш просей 1 зрозумшй проектувалышку мов! (електронних схем, таблиць ¡стинносп, блок-схем, кшцевих автомате).

Мереж! Петр! е зручним засобом опису й анал1зу р!вноб!жних процес!в. Можлив1'сть модифшацн мереж! Петр! дозволяе адаптувати й для моделювання практично будь-яких об'екттв ! процеав. Збшьшення складност! об'екпв, що моделюються, призводить до зростання роз\нрносп мереж! Петрь Щоб спрос-тити процес побудови моде.'п I шдвищити и наочшсть, почали використовувати структуроваш мереж! Петр!. Для цього в модел! застосовують структурован! позици, переходи, дуги 1 м!тки.

Проте анал!з ¡снуючих струкгурованих мереж Петр! показуе, що вони орь ентоваш на моделювання систем у певних вузьких предметних галузях ! не мо-жуть бути використащ для моделювання складних систем у довшыпй предмет-нш галуз!. Щоб застосування структурован о!' мереж! Петр! не обмежувалося предметною галуззю, необхщно створити структуровану мережу Петр! в рамках загально! теори, що описуе складш систем» довшьно'! предметно! галуз!. Одще'! з таких теорш е теор1я систем. Тому актуальною для моделювання складних обчислювальних систем е 'розробка структуровано! мереж! Петр!, що задоволь-няе основним положениям сушеного системного пщходу - системологн.

Зп'язок роботн з науковими програмами, планами, темами. Дисерта-цшна робота виконана зг!дно з планом науково-техшчних роб!т Харк!вського державного техничного ушверситету радюелектрошки в рамках держбюджетно'! теми "Розробка математичного забезпечення та програмно-апаратних засоб!в систем контролю ! управл!ния виробничими ! технолопчними процесами", що е частиною программ 40 Миистерства осв!ти ! науки Украши "Методи побудови та створення комп'ютеризованих систем 1 технолог!й".

Мета роботн: розробка структуровано! мереж! Петр! для моделювання складних ¡ерарх!чних багатор!вневих обчислювальних систем на основ! сучас-ного системного шдходу - системологн.

Зада*» дослщження. Зпдно з поставленою метою задачами дослщження в дисертацшнш робот! е:

- анализ структурованих мереж Петр! з метою вибору мереж! Петр1, на основ! яко1 можла розробити мережу Петр! для моделювання складних обчислю-валышх систем;

- розробка структуровано! мереж) Петр!, що задовольняе основним положениям системологи;

- дослщження потужност! моделювання розроблено! структуровано'! мереж! Петр!;

- розробка метод1в анал!зу структуровано! мереж! Петр!;

- розробка метод!в зменшення витрат пам'ят! на збереження структуровано! мереж! Петр!;

- розробка шструментального програмного засобу пщтримки моделювання складних систем на основ! структуровано'! мереж! Петр!;

- розробка спещал!зовано'1 м!кропроцесорно!' системи, що програмуеться структурованою мережею Петр!.

Наукова новизна одержаних резулыттв:

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

- виерше доведено е'кв!валентн!сть р!зноманггних тип!в аналкичних дуг мереж! Петр!; це дозволило показати, що використання аналгтичних дуг значно скорочуе розм!ри мереж! Петр! ¡, таким чином, пщвищуе наочшсть модел! складно'! системи;

- вперше доведено еюмвалентшсть мереж Петр! з анаштичними дугами машинам Тюр!нга; це показуе, що мереж! Петр! з анаштичними дугами можна використовувати для моделювання систем довшьно! складност!;

- удосконалено методику анал!зу мереж Петр! шляхом синтезу двох основних метод!в анал!зу мереж Петр!: дерева досяжност!! матричного р!вняння; це дозволило скоротити час анатзу мереж! Петр! за рахунок обмеження дерева досяжност! за допомогою вектора запуску;

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

Практичне значения одержаних результат. Практична цшшеть отри-маних результате полягае в тому, що:

- розроблено шетрументальний програмйий зас!б пщтримки моделювання складних систем на основ! ¿-мереж1 Петр!; це дозволило'моделювати складн! багагор!внев! ¡ерарх!чш системи, як! зм!шоють свою структуру у пронес! робота;

- розроблено нову структуру та алгоритм роботи процесора Петр! - спещ-ал!зованого процесора, основною особлив!стю якого е програма у вигляд! мереж! Петр!; це дозволило пщвищити надшшеть функщонування процесора та збшьшити його швидкод!ю;

- на осногп процесора Петр1 розроблено метод проектування спещашзова-01 М1кропроцесорно1 системи, що програмуеться ¿-мережею Петр1; застосу-1ння цього методу значно спрошуе розробку ¿ерармчних систем керування.

Результата робота впроваджеш в АТ "Науково-дослщний шститут радю-лм^рювань" у вигляд1 математичних моделей 1 шструментального програмного 1собу при розробщ системи збору, оперативно! обробки та aнaлiзy шформаци ро стаи засоб1в наземного автоматизованого комплексу управлшня косм1чни-и апаратами. Науков! положения 1 внсновки, приведен! в дисертацп, викорис-1Ш при шдготовш курсу "Проектування спещатзованих мшропроцесорних 1стем" на кафедр1 автоматизацп проектування обчислювачьно! технжи Хар-¡вського державного техшчного ушверснтсту радюелектрошки.

Особистий внесок. Основш результата дисертацп одержат особисто ав-зром. У друкованих працях, опублжованих у cпiвaвтopcтвi, автору належить озробка Ь-мереж1 Петр! [1,10,11], доказ пеми I теореми про екв1валентшсть 1алш1чних дуг 1 етвалентшсть мереж Петр1 з анаштичними дугами машинам юршга [7,8], розробка синтезу основних метсдав анашзу мереж Петр!: дерева зсяжносп 1 матричного р1вняння [2,10,11], розробка методу зменшення витрат зм'ят1 на збереження структури мереж1 Петр1 [10,11], розробка методу вибору эмуташйно! структури для синтезу мереж1 Петр1 [5], розробка новоТ структури 1 алгоритму робота процесора Петр1 [8,14], розробка модел1 М13С-процссора а основ12-мереж1 Петр1 [9].

Апробащя результатов дисертацн. Основш результата роботи доповща-кь на: 1-му М1жнародному молодежному форум 1 "Електрошка 1 молодь у XXI :ор1ччГ' (Харюв, 1997 р.), 3-й М1жнароднш конференцп "Теория \ техшка пе-:даш, прийому та обробки шформаци" (Туапсе, 1997 р.), Мгжнародшй мнп-энференцп "Математичне моделювання та шформацшш технологи" (Рос1я, уггород, 1997 р.), 2-му Молод1'жному фору\н "Радюелектрошка ! молодь у XI стор{чч1'" (Харюв, 1998 р.), 2-й мюькш науково-практичнш конференцп ^ктуальш проблеми сучасноТ науки в дослщженнях молодих вчених м. Харко-I" (1998 р.), 7-й М1жнароднш науково-техшчшй конференцп 'Чнформацшш ¡хлологп: наука, техшка, технология, осв1та, здоров'я" (Харк1в, 1999 р.).

Г1убл1кащ1. Основш положения 1 результата дисертацп опублжоваш в 14 1укових працях: 7 статей у науково-техшчних журналах, 2 статп в зб!рниках ^укових праць, 1 стаття в зб1рнику матер1ал!в конференцп, 3 тези доповщей, ззитивне ршення про видачу патенту на винахщ "Процесор Петр!".

Дпссрташя мктить у соп!: вступ, 4 роздои 1 2 додатки. Повний обсяг ди-:ртацн становить 142 стор. При цьому 55 ¡люстрацш займаготь 19 стор.; 3 таб-1И1 - 1 стор.; додатки - 8 стор.; список використаних лггературних джерел у лькост1 104 найменувань -10 стор.

ОСПОВНИЙ ЗМ1СТРОБОТИ

У встуш обгрунтована акгуальшсть теми, сформульоваш мета I задач! ро->ти, вщзначеш наукова новизна! практична цшшсть отриманих результат.

У першому роздЫ проведено а!кшз структурованих мереж Петр1, шстру-

ментальних програмних 3aco6ie на '¿хнш ocHoei, спешал1зованих мкропроцесо-рних пристрслв моделювання мереж Петр1 i спещагпзованих iipouecopiB, що програмуються мережами Петрг

Визначено мету роботи, i сформульоваш ocHOBiri задач! дослщження. Формальна постановка задач! мае такий вигляд. Нехай система 5 складае-ться з множили шдсистем S„ i алгоритм поведшки пщсистеми Sу к-т cuTyauii

описуеться у вигляд1 мереж1 Ilexpi N£ . Таким чином, кожнш пщсистем! S, вщ-

повщае множима Nt алгоритмш иоведшки у вигляд! множили мереж Петр!:

S, i CTat' кожно'1 пщсистеми S, визначаеться марюруванням

М{Р,) позицш Р, мереж1 IleTpi з множини N,. Задача системи S - зм1нювати ал-

горитми поведшки шдсистем у залежносп вщ досягнугих ними сташв

{'W(Pj)}"_[. Таким чииом, на вхщ системи S подаються стали (М(РЛм(Р2),...,М(Рц)) Bcix Fi пщсистсм, а на виход! системи Sз'являеться вектор U'1 ,N2 ,...,Nn , де N' - мережа Пет-pi, що визначае алгоритм поведш-V s2 s„ fj

ки пщсистеми S, у сташ (M(Pi),M(P2),...,A/i(Pn))■

Отже, система S реашзуе деяку функщ'ю

/(М(рАм{Р2),...,A/(P„)) = yv! ,...,N" . ПотрШно розробити мережу Пе-

S1 s2 sn

Tpi N, що описус функцио f.

В другому розд1л1 пропонуеться метод опису багатор!вневих мереж Петр!. Мережа, що мае L pißHiB, назнваеться L-мережею Петр! (вщ англ. level - р1вень).

Нехай А - множима дуг. На множиш А задаеться вшношеиня екв1валентно-CTi р. Клас екв1'валентност1 р називаеться позицию. Фактормножинг

А/р = {р, е множиною позицш. Попм на множиш А задаеться вщношенш

екв1валентност1 т. Клас екв1вапентност1 т називаеться переходом. Фактормно-

жина Л/т = е множиною переходов.

Для кожного класу р, задаеться розбивка р, = l{pj){JO(p,). Множиш l{Pi) називаеться множиною exidma дуг для позицп ph а множина 0(р,) -множиною eiLxidunx дуг для позици . Пот1м для кожного класу tj задаетьс) розбивка tj =l(tJ)[jo(tj).i Множина litj] називаеться множиною exiÖHiix ду. для переходу tj, а множина o{tj) - множиною euxidmix дуг для переходу tj

Розбивка KjiaciB екв1валентностей повинна задовольняти таким умовам:

1. Для будь-якоУ дуги a е /(/>,) ¡снуе перехщ tj е А) т, такий, щояе oifj).

2. Для будь-яко! дуги a е 0(р¡) ¡снуе перехщ tj е А/х, такий, що a е l(t j).

3. Для будь-яко! дуги a е f(t,) ¡снуе позищя /?,- е А/р, така, що a е 0(р,).

4. Для будь-яко! дуги a е ö(fy ) ¡снуе позишя р, е А/р, така, що яе l{Pi)

Нехай N0 - множина цших невщ'емних чисел, R = {<,>, =,<, > - множи-на стандартних вщношень на множшп Nq. Задасться функшя типу V:A->R U{+}- Якщо V(a)eR, то дуга а називаеггься аналШичною. Якщо V(a)="+", то дуга а називаеться трапспортною. Функщя типу повинна задово-льняти таюй yMoei: якщо aeC>(tj), то V(a)="+". Задасться функция ваги IV : А -> Nq, така, що якщо V(a)="+", то W(a0. Задаеться функщя марюру-вання U : А/р -» N0.

Сукупшсть N = (A,Alp,Ali,V}V,M) називаеться мережею Flempi першого pienH.

Транспортна дуга а е l[tj)f]0(pj) дозволяе перехщ tj, якщо

\¥{а)<М{р,). Аналогична дуга а е l{tj)f]0{pj) дозволяе перехщ tj, якщо

(M(pi),W(a))eV(a). Перехщ tj дозволений, якщо yci вхщш дуги tj дозволя-

ють його. Дозволений перехщ можна запустити. Якщо два переходи знаходять-ся в конфл^кп, то вш виршуеться за допомогою прюритету, заданого на множит переход1в. Запуск переходу tj злпнюе марюрування М мереж1 Петр1 N на

нове маршрування М* втзкий споЫб:

M*(p'/) = M(pi)-fF(al)+fV(a2), (1)

де в1 e/ynofo), a2eO{tj)r}l(pi)™ V{a{)="+".

Транспортна дуга а е /(fy)f]0(p;) називаеться конвеерною, якщо W(а) = 0. Вхщна конвеерна дуга завжди дозволяе перехщ tj. Перехщ може ма-ти тщьки одну вхщну конвеерну дугу. При запуску переходу tj вхщна конвеерна дуга а видаляе М(р,) мшж ¡з позицп pt. Якщо перехщ tj мае вихщну

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

сюльки видалила з вщповщно! позицп' вхщна конвеерна дуга переходу tj.

Структура мереэю. ' Flempi другого pienn визначаеться тршкою: NC = (Ас,^с/Рс '^с/тс)' ле " множина дуг мереж) Петр1, рс и тс - вщно-шення екв1валентност1 на множшп Ас, ^с/Рс та ^chc " множини позицш i

переход1в. Нехай Mq = - множина nutok мереж1 Петр! Nc. Розподш mi-

tok по позициях задаеться початковою функшею марюрування Zq \Mq-> AqIpc . Кожнш MiTLti т, за допомогою б1ективного вщображення f\

31ставляеться множина = jp^j}? , позицш першого р1вня: /] \Mq -> Р$, де

Ps = l^j. П0Т1М кожнш' мтп m, за допомогою б1ективного вщображення f2 зютавляеться множина мереж Петр! N$j першого р1вня 3i cni-

льною множиною позицш першого р1впя: /2 :МС ->N$, де = {vy]^_|. Шсля цього кожшй мшц ш,- за допомогою б1ективного вщображення f3 зютав-ляеться початкова мережа Петр! Nfaj- з множини вщповщних мереж Петр!

першого р1вня: /3 \ Mq -*Nsq , де NSq = {^jj^ • Hapeimi, кожшй мггщ от,-за допомогою б1ективного вщображення/4 зштавляеться початкове марируван-

ня множини Ру позицш першого р!вня: /4 де = {v/^^j.

Таким чином, мггщ мереж! Петр! другого р!вня з!ставляеться мережа Петр! першого р!вня. Така м!тка називаеться макрошткою.

Множина Ас дуг мереж! Петр! другого р!вня розбиваеться на пщмножину

А^ вхщних дуг i пщмножину Aq вих!дних дуг. Кожн!й вхщнш дуз! а мереж! Петр! другого р!вня за допомогою вщображення/5 з!ставляеться деяка макром!-тка т, ¡з множини Мс мток мереж! Петр! другого р!вня: /5: А^ -> Mq . Пот!м, яйцо вхщнш дуз! а мереж! Петр! другого р!вня з!ставлена макромпжа т, ¡з множини Мс nhtok мереж! Петр! другого р!вня, то цш дуз! а за допомогою вщображення^ зютавляеться деяке марюрування множини позиц!й Ру першого ршня, з!етавлених макромпщ т,■: /g : А^ —.> М$.

Вхщна дуга а е lilj)(]0{p^) мереж-i Петр! другого р!вня дозволяе перехщ tj, якщо в позищ'! рь знах'одиться ма1фОм!тка mt, що вщповщае дуз! а, i маркь

рування Mg позищй Ру першого р!вня, що вщповщають макром^щ т,-, 31'став-

ленодуз! а: /,{mi)=pk, f5(a)=m,, Д(т,) = М'5, f6(a) = M's. Перехщ другого р1вня дозволений, якщо ус! вхщш дуги переходу tj дозволяють його.

Кожшй вихщнш дуз! а мереж! Петр! другого р!вня за допомогою вщобра-ження fi з!ставляеться деяка макролптка т, iз множини Мс мпок мереж! Петр!

другого р!вня: /7 \Aq ->Мс- По™, якщо вихщнш дуз1 а мереж! Петр! другого р!вня з)'ставлена макром!тка т, !з множини Мс м!ток мереж! Пет-pi другого pip-ня, то цш дуз! а за допомогою воображения/8 з!ставляеться деяка мережа Петр!

j з множини N's, зштавлено!макромггщт,: /g '.Äq-*

Якщо в перехщ входить дуга а, якш вщповщае макромпжа т„ то з переходу повинна виходити дуга ö, котр!й також вщповщае макролитка т,. Якщо з переходу внходить дуга b, якш вщповщае макромггка т,, то в перехщ повинна входити дуга а, котрш також вщповщае макром1тка щ. У перехщ не може вхо-дити дв! дуги, яким зютавлена одна макро\пгка. Аналогично, ¡з переходу не мо-

жуть виходити дв1 дуги, яким зктавлена одна макромгаа.

Якщо перехщ дозволений, то вш може бути запущений. При запуску переходу ¡у макро.лптка перемйцаеться з вхщно! позицп по вщповщнш вхдап'й дуз1,

проходить через переход tj 1 по вщповщнш вихщнш дуз1 помпцаеться у вихщ-

ну позишю переходу . 1]ри цьому мережа Петр!, що вщповщала макромггщ

до запуску переходу, зам!няеться мережею Петр!, 31ставлено1 вихшнш дуз1, по якш макромп-ка потрагшла у вихщну позицио переходу. Приклад 2-мереж! Петр! приведений на рис.1.

Рис. 1. Структура 2-мереж! Петр!

Показано, що 2-мереж! Петр! задовольняють основним положениям сучас-ного системного шдходу - системологн. 3 1хньою допомогого можна моделюва-ти три основн! вида структурних схем двор!вневих !ерарх!чних систем з ураху-ванням основних принцишв координацн роботи п!дсистем.

Якщо макромггщ 2-мереж! Петр! у свою чергу згставити 2-мереж! Петр!, то утвориться 3-мережа Петр!. Мереж! Петр! першого р1'вня вщповщають макро-мггкам 2-мереж Петр!, мереж! Петр! другого р!вня - макромпжам З-мереж! Петре, на третьему ре'вш знаходяться макро.\птк!г З-мереж! Петр!.

¿-мережа Петр! будуеться шляхом з!ставлення макром!ткам 2-мереж! Пет-р1 (£ - 1)-мереж Петре.

У третьому роздЫ зд!йснюеться дослщження ¿-мереж Петр!.

У мережах Петр! першого р!вня використовуються анагитичн! дуги, що яв-ляються узагальненням шпбггорних (стримуючих, блокуючих) дут: ¡нг!б!торна дуга е анал!тичною дугою а, такою ню У(а)="<" та 1У(а)= 1. Вщомо, що мережа Петр! з шпбтрними дугами екв!валентна машин! Тюршга.

Дослшжено екв!валснтшсть аналггичних дуг р!зномаштних тип!в. Для цьо-

го вводиться так! позначення: через а*, позначеиа аналтгчна дуга а, така, що

И'(а)=х та К(а)="у" (наприклад, а1 позначае анал!тичну дугу а, таку, що И/(а)=5 та К(я)="^"); якщо мережа Петр! мае аналггичш дуги, то 1хш типи вказуються в скобках шеля позначення мереж! Петр! (наприклад, А'(>,=) озна-

чае, що мережа Петр! N мае аналгтичш дуги типу ">" та "="; Л^д! означае, що

мережа Петре N мае анаштичш дуги я<).

Доведено так! властивосп мереж Петр! з анал!тичними дутами. Твердження 1. =,<,>)-N*(<,>,Це твердження показуе,

М! • • 1 М> —1

що дуга а> еквшалентна дуз1 а> : дугу я> можна замшити дугою а> ,1 навпаки.

Твердження 2. Л?(<,>,^,=,<)~ Лг*(<, >,*,=)• Це твердження показуе, що дуга я< екв!валентна дуз! я<+1: дугу я< можна зам!нити дугою д<+1, ! навпаки.

Твердження 3. /У(<,>,^,=)~ Це твердження показуе, що дуга

я= екв!валентна дугам та дугу можна зам!нити парою дуг

+1 1 М1— 1 ■

а< тай;, , 1 навпаки.

Твердження 4. N{<,>,*) ~ N*(<,>). Це твердження показуе, що дуга

екв!палентна дугам я> та : дугу а™ можна зам!нити парою дуг я> та навпаки.

Твердження 5. //(<,>) ~ Аг*(<). Це твердження показуе, що дуга я> еквь валентна дугам та +!: дугу я> можна зам!нити парою дуг та

I •

о+ , 1 навпаки.

Лема. Ы(<)~ А^*(р< . Ця лема показуе, що дуга а< екв!валентна мереж!

Петр! з шпб!торшши дугами: дугу я< можна зам!нити мережею Петр! з шпбь торними дугами, ! навпаки. Причому, чим бшьше значения м-, тим бшьше роз-мхр мереж! Петр!, що може замшити дугу . Таким чином, аналогична дуга

о< дозволяе значно зменшити розм!р мереж! Петр!. 3 тверджень 1 -5 та леми випливае теорема.

Теорема А'(<>>,>)~ 1Дя теорема доводить, що мереж! Петр!

з анал!тичними дугами екшвалентш мережам Петр! з ¡нпбггорними дугами, отже, машинам Тюр!нга.

Поведшка 1-мереж! Петр! ¡стотно залежить вщ досяжностч маршрувань у мережах Петр! самого нижнього р!вня ¡ерархн. Тому що мереж! Петр! з анаш-тичними дугами екв!валентш машинам Тюр!нга, то для цих мереж Петр! задача досяжност! нерозв'язна: не ¡снуе сшльного алгоритму, що виршуе задачу дося-жносп для довшьно? мереж! Петр! з анаштичними дугами. Якщо в структур! мереж Петре нижнього р!вня зустр!чаються тшьки транспортн! дуги, то можна використовувати два оснорш методи анатоу таких мереж Петр!: дерево досяжност! ! матричне р!вняння.

Показано, що у випадку, коли матричне р!вняння мае к!нцсву множину рь

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

Визначення 1. Перехщ дозволений вектором запуску, якщо вцшовщний йому компонент вектора запуску не дор)внюе нулю.

Побудова дерева досяжносп зд)йснюеться з урахуванням вектора запуску в такий споЫб. При запуску переходу вщповщний йому компонент вектора запуску зменшуеться на одинишо. Початкова вершина (коршь дерева досяжност)) позначаеться початковим марюруванням мереж1 ) початковим вектором запуску, знайденим ¡з матричного р)вняння. Для кожного переходу що дозволений марюруванням 1 вектором запуску вершини X, створюеться нова вершина з вщ-пов1дним марюруванням 1 вщповщним вектором запуску. Вщ вершини X до ще} ново! вершини веде дуга, позначена Цей процес повторюеться для вах нових вершин.

Урахування вектора запуску гарантуе, що побудоване дерево досяжност) буде кшцевим, тому що, по-перше, на кожному кроку побудови дерева досяжносп один ¡з компонентов вектора запуску зменшуеться на одиницю доти, доки вектор запуску не стане нульовим, по-друге, ¡з кожноТ вершини дерева досяжносп виходить ребер не бшьш, шж число переход!'в у дашй мереж) Петр).

Кр1М того, урахування вектора запуску не дозволяе запускати переходи, дозволен! в поточному мармруванш, але вщповщний компонент яких у вектор! запуску дор1внюе нулю. Таким чином, вектор запуску обмежуе ) спрямовуе по-будову дерева досяжносп.

Для збереження структури ¿-мереж) Петр), що моделюе складну систему, потребуються велим обсяги пам'яп: кожшй макромшц може зютавлятися зна-чна кшьгасть мереж Петр) великого розм1ру.

Розроблено зв'язний запис структури мереж) Петр), застосування якого дозволяе зменшити витрати пам'ят) на збереження модель Для цього вводяться таю визначення.

Визначення 2. Запис

називаеться в1дпов1дтстю позицш ¡з номером д (ц-ю вщповщшстю позицш) ) означае, що позицн/;,а(а=1,2,... ,г) е вхътними, ар1 р ((3=1,2,... ) - вихщними по-зищями для переходу при цьому коефпцент /г,0 показуе кратш'сть позицн

Визначення 3. Запис

(2)

називаеться оберненою в1дпов1дшстю позицш ) визначаеться р)вшстю

(кпР1Гк1ГР„ : кдрл..крр^=^Пря.к]5рр,к1Хрп..кггр1г\. (4)

Вводяться операцп над вщповщностями позицш.

Визначення 4. Операцш выносу позицй над вщповщшстю позицш визнача-еться р1вшстю:

(...; кпрл... кр рр)ц = (...; крр,,... кр) ц рр. (5)

Можна винести будь-яку позицш др (Р=1,2,... переставивши и разом ¡з коефвдентом к^ на мюце позици/?^.

Операщя виносу за дужку над оберненою вщповщшстю позищй визначае-ться аналопчно, замшою в р1вност1 (5) знаив ";" на знаки ":".

Визначення 5. Операщя вкладення ^ визначаеться для двох вщповщностей позищй 13 номерами 1 ql, мають сш'льну пoзицiю ри р4вностями

(...;...а,^¡р, I (... ;..Дд...)с/2 = (... \...Ь,{... (6)

(...;...а,)<2,1/>Д ;...)д2=С-с,(... ;...а,)<?1А... ;...)<?2, (?)

до а,-, Ь, та с, - коефвденти прир,.

Р1вност1 (6) I (7) називаються формулами вкладення вщповщностей (</1-а вщповщшсть вкладена в цг-у вщповщшсть).

Операшя для двох обернених вщповщностей позицш визначаеться аналогично, замшою у формулах (6) 1 (7) знаюв ";" на знаки ":".

Операщя 4- для двох вщповщностей позищй р1зних тишв визначаеться замшою в р1вностях (6) 1 (7) вщповщних знаю'в ";" на знаки ":". Наприклад, операшя вкладення 91-1 обернено! вщповщносп позицш у цг-у вщповщшсть позишй, яю мають сшльну позицпо ри визначаеться, зокрема, р1вшстю

(... : ...«;)«],з;у (... ,...Ьр,...)(ь -(... ;.../;,(...: ...а^1р,..)ц2. (8)

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

Пор1внюються витрати пам'яп при завданш структури мереж1 Петр1 у ви-гляд1 матриць 1 у вигляд1 зв'язного запису. Якщо позначити через п 1 т число вщповщно позицш ( переход1в мереж1 Г1етр1, а через а \ Ь - частку вщповщно нульових 1 ненульових елемент у матрицях шцщенцш, то для пор1вняння ви-трат пам'ят! на збереження структури у вигляд1 зв'язного запису з витратами пам'ят1 М на збереження структури у вигляд1 матриць отримана така формула:

L , (и Л 1 1 — = 1 + (b-a)+- + -—.

М п 2тп

Ця формула показуе, що, тому що на практищ матриц! шцщенцп мгстять не менше 80% нул1Б, зв'язний запис дозволить заощаджувати не менше 50% пам'ятг

Будь-який р!вень ¿-мереж! Петр! е середовшцем, у якому синтезуеться де-яка мережа Петр!, що задовольняе вс!м необхщиим топологгтним характеристикам. Встановлення необхщних зв'язшв м^ж позищями i переходами можна здшсшовати за допомогою комутацшних структур (КС).

Дослщжено питания синтезу мереж Петр! на баз! шструментальних засоб1в гелетрафка. Визначено обмеження, як-i накладае на КС задача синтезу мереж Петр!: КС повинна бути змшаною, реатзовувати неординарш зв'язки i мати можлнвють швидкого перебудування з'еднань. 1снуе багато КС, що задоволь-няють ним обмеженням. Виникае задача вибору КС, оптимально! по деякому параметру. Розглянуто приклад, у якому в якосп параметра, що визначае on6ip КС, береться число точок комутацп КС: оптимального е КС ¡з меншим числом точок комутацп.

У четвертому роздал! розглянуи питания практичного застосування L-мереж Петр!.

Розроблено програмщш продукт "Крос-платформена б!блготека обробки моделей складних систем", призначений для моделювання складних систем до-вшьно! галуз1 на основ! ¿-мереж Петрь Програмна система створена в штегро-ваному середовищ! розробки Borland Delphi v. 3.0. При написанш програми ви-користана б!бл!отека в!зуатьних компонента Delphi - Visual Component Library (VCL). Програмна розробка рсашзуе тага фуикцй: шдтримка багатор!вневих мереж (¡з практично необмеженою к!льгастю шдмереж); п!дтримка множинних атрибупв (кольор!в) мереж першого р1вня; перегляд стану мереж будь-якого р!вня в процеа моделювання; можливють внесения змш у мережу пщ час моделювання; крокове моделювання з детатоащею; вщображення шформацп про модель при Bi3yani3auii; збер!'гання моделей у файлах ¡з структурою, яка пщ-

моделI моделювання

Рис. 2. Структура б!блютеки обробки моделей складних систем.

тримуе подальший розвиток системи; В1зуальне вщображення iepapxii' мереж.

Загальна структура б^блютеки подана у вигдяд1 схеми, наведено! на рис.2.

Пересування шформаци в б!блютещ описуеться в такий cnoci6. Модуль збереження й обробки передае дан) про структуру модел1 модулю в1зуал1зац11 й штерфейсу i модулю реал1защ! моделювання. Модуль в)зуал1зацп й ¡нтерфейсу передае модулю збереження й обробки змшену користувачем структуру мод ел). Також модуль в)зуал1зацп й ¡нтерфейсу керуе процесом моделювання у вщпо-вщному модул) й одержуе назад шформащю про хщ моделювання. Модуль ре-ал)зац)1 моделювання передае модулю збереження й обробки змшену в npoueci моделювання структуру.

Описано правила роботи з програмою.

Наведений приклад використання "Крос-платформено! б)бл)отеки обробки моделей складних систем" для програмно) емуляцн модел) MISC-процесора. Модель побудована з застасуванням принципу двор)вневого програмування на-строювання на приклад) обчислення функцн з використашим 2-мереж) Петр). Алгоритм обчислення функцп поданий у вигляд) мереж) Петр) верхнього р)вня. Щоб показати процес обчислення функцп, макромгтщ мереж) Петр) верхнього р!вня заставлен) мереж) Петр) нижнього р)вня, позицп яких моделюють ком)рки пам'ят) для збереження пролпжних результат)в обчислення функцн, а переходи - необхщш операцп для обчислення uiei функцн.

Запропонована модель вщбивае концепшю епшьного проектування апара-тних i програмних засоб1в (hardware-software codesign). При такому пщход) модель програми i модель виконуючого и процесора об'еднуються в едину модель, подану у вигляд) 2-мереж) Петрк У такий cnoci6 можна простежити за змшою арх)тектури MISC-процесора шд час виконання програми, що дозволяе оптимально адаптувати 1х одну до шшоУ, з метою одночасно! реал)защ1 як високоУ швидкост) роботи, так i високо) точност) обчислень.

Розглянуто питания використання I-мереж Петр) для проектування бага-тор)вневих iepapxi4HHx систем керування на основ) процесора Петр).

Вщмшною рисою процесора Петр) е програма роботи у вигляд! мереж) Пе-rpi. Процесор Петр) складаеться з таких основних блок)в: блок вводу, блок ви-воду, блок програмування, блок топологи, блок розмпгки i блок запуску. Процесор функшонуе в такий cnoci6. Перед початком роботи через блок програмування записуеться алгоритм роботи процесора: структура мереж) Петр) запису-еться в блок топологи, а початкове марюрування - у блок розмпжи. Пот1 через блок вводу в блок розмпжи процесора надходять даш з датчиюв об'екта керування, яи опрацьовуються в)дпов)дно до алгоритму роботи в блощ запуску, ni-сля цього з блока розмггки через блок виводу на виконавч) мехашзми об'екта керування подаються керуюч) сигнали. Пот)м знову вщбуваеться введения да-них i т.д.

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

лнв керування деякими (можливо, усгма) шшими тдсистемами. Для цъого необидно змшити мереж! Петр1. Алгоритм змши можна у свою чергу представи-ти у вигляд! деякоГ мережгПетр!. Для узгодження робота декшькох процесор!в Петр! пропонуеться також застосувати процесор Петр!.

Процесори, що реал1зують алгоритми керування тдсистемами, називають-ся керуючгши процесорами Петри а процесор, що зм1нюе алгоритми керуючих процесор1в, - процесором Петр!, що узгоджуе. Алгоритм змши, який заванта-жуеться у процесор, що узгоджуе, е 2-мережею Петр!, кожна макромшса яко'! являе собою алгоритм керування у вигляд! мереж! Петр!, яка завантажуеться у вщповщний керуючий процесор. Вхщ процесора, що узгоджуе, з'еднусться з виходами керуючих процесор1в, а вихщ процесора, що узгоджуе - ¡з блоками нрограмування керуючих процесор1в, як показано на рис. 3.

Рнс. 3. Двор!внева система керування на основ! процесор!в Петр!.

Таким чином, на вхи процесора, що узгоджуе, подаеться шформац^я про ;тан ус!х шдсистем у вигляд! марк!рувань в!дпов!дних мереж Петр!. Коли ищ-:истема досягне певного стану, поданого марюруваншш мереж! Петр!, запустился де'який перех!д 2-мереж! Петр! процесора, що узгодить, що призведе до ;мши 2-мереж! Петр!. При цьому змшиться значения атрибута, що зютавляе 1акром!ткам структура мереж Петр)'. Нов! значения цього атрибута з виходу фоцесора, що узгоджуе, над!йдуть у блоки профамування керуючих процесо->1в, що спричинить за собою змшу алгоршлнв керування тдсистемами.

Якщо складна система складаеться з дуже великого числа шдсистем, то южлива така ситуащя, при якш шдсистеми об'еднуються в групи, кожна з яко'! находиться тд керуванням деюлькох керуточих процесор1'в Петр! ! одного фоцесора Петр!, що узгоджуе. У цьому випадку виникае необхшистъ узго-гження роботи вс!х процесор!в, що узгоджують. Для цього також можна вико-шстовувати процесор Петр!. Так утворюеться трьохр!внева система керування

на баз1 5-мереж1 Петр!. Аналогично проектуються мультипроцесорш ¡ерарх!чш багатор!внев! системи керування складними об'ектами на основ! ¿-мереж Петрь

Проведено анатз структури й алгоритму роботи процесора Петрг У результат! виявлеш таи суттев! недол!ки:

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

2. Структура мереж! Петр! записуеться у вигляд! матриць шщденцш. При такому гйдход! на практиш матриц! м!стять у середньому 80 % нугпв. Таким чином, апаратш засоби на збережеши структури мереж! Петр! використовую-ться неефективно.

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

Запропоновано нову структуру й алгоритм роботи процесора Петр!. Осно-вш зм!ни полягають в наступному:

1. Модифковано алгоритм роботи. Анал!з переход!в вщбуваеться в двох режимах: аналггико-транспортному ! транспортному. Анал!тико-транспортний режим використовуеться один раз при анашз! дуг перед вибором переходу, що запускаеться першим (з урахуванням пр!оритету) при розлптщ мереж! Петр!, отримано'! шсля вводу данях ¡з датчик!в об'екта керування. Пюля його запуску розм!тка змшиться ! деяка анал!тична дуга може дозволити (заборонити) запуск переходу, забороненого (дозволеного) при розмггщ мереж! Петр;', отримано! ш-сля вводу даних ¡з датчик!в об'екта керування. Отже, алгоритм обробки даних буде виконуватися неправильно. Щоб вшшочити так! випадки, теля запуску першого переходу результата анал!зу анал!тичних дуг не враховуються при транспортному режим!.

2. Структура мереж! Петр! записуеться у вигляд! списку дуг. Вхщна дута с записуеться у вигляд! а = (а1,а2,а^,а^), де а] - номер позици, ¡з яко! виходить дуга, а2 - вага дуги, а3 - тип дуги, а^ - номер переходу, у який входить дуга Вихщна дуга Ь записуеться у вигллд! ¿ = (¿>[,¿>2,63), де ¿>) - номер переходу, ¡: якого виходить дуга, Ъ2 - вдга дуги, 63 - номер позици, у яку входить дуга.

3. Представления структури мереж! Петр! у вигляд! списку дуг дозволж ввести в процесор Петр! конвеерну дугу ! кодувати и вагою "0", що принциповс неможливо при матричному запиа, де вага "0" позиачае вщеутшеть дуги.

4. Дослщження взаемозв'язку м!ж р!зноман!тними типами анаштичних ду: (див. роздш 2) показуе, що використання дуг ус;х ш!стьох тишв недошльно тому що вони виражаються одна через ¡ншу. Тому в процесор! можна обмежи тися використанням тьчьки трьох тип!в анаштичних дуг: ">", "<" та V. Це до зволяе ушф^увати обробку транспортних ! анал!тичних дуг, що значно пщви щуе швидкодпо процесора Петр1! спрощуе його структуру.

За матер!алами дослщження подана заявка на винахщ "Процесор Петр!"

1ауково-дослщним центром патентно! експертизи Держпатенту УкраУни 7.10.99 р. прийнято р1шення про видачу патенту.

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

висновки

У дисертацн вир!шена актуальна наукова задача розробки структуровано! [ереж! Петр! для моделювання складних ¡ерарх!чних багаторшневих обчислю-альннх систем на основ! сучасного системного п!дходу - системологп:

1. На основ! навантажених мереж Петр! розроблено нову модифшашю ме-еж! Петр! - L-мережу Петр!, - яка призначена для моделювання складних ie-арх1чних багатор!вневих систем ¡з структурою, що змшюеться в процеа робо-и. Основною особливютю L-мереж! Петр! е макромтка - мггка, що являеться [ережею Петр!.

2. Доведено екв!валентшсть р!зноман!тних тишв анагнтичних дуг мереж! [етр1. Показано, що використання анагнтичних дут ¡стотно скорочуе розм!ри (ереж! Петр! та шдвшцуе наочн!сть модел! складно!' системи.

3. Доведено екв!валентн!сть мереж Петр! з анаттичшши дугами машинам юршга. Це показуе, що мереж! Петр! з анагитичними дугами можна викорис-эвувати для моделювання систем довшьно! складност!.

4. Удосконалено методику анал!зу мереж Петр! шляхом синтезу двох ос-овних метод!в анал!зу мереж Петр!: дерева досяжносп i матричного р^вняння. [е дозволило скоротити час анал!зу мереж! Петр! за рахунок обмеження дерева осяжност! за допомогою вектора запуску.

5. Одержав подальший розвиток метод скороченого запису структури ме-еж! Петр!. Иого використання дозволяе зменшити витрати пам'ят! на збере-:ення модел!.

6. Розроблено шструментальний програмний 3aci6 пщтримки моделювання кладних систем на основ! L-мереж! Петр!. Вш дозволяе моделювати складш агатор!внев! iepapxi4Hi системи, яю змшюють свою структ>ру у npoueci робот. Показано, що в!н може бути використаний для спшьного проектування апа-атних i програмних засоб!в (hardware-software codesign).

7. Розроблено нову структуру та алгоритм робота процесора Петр! - cneui-цзованого процесора, основною особливютю якого е програма у вигляд! ме-гж! Петр!. Полагоджено помилки функц!онування процесора i збщыиена його [видкод!я.

8. На основ! процесора Петр! розроблений метод проектування cneniani30-iHoi М1кропроцесорно'! системи, що програмуеться L-мережею Петр!. Застосу-зння цього методу значно спрощуе розробку iepapxinimx систем керування.

СПИСОК ОПУБЛ1КОВАНИХ НРАЦЬ ЗА ТЕМОЮ ДИСЕРГАЦП

1. Ельчанинов Д. Б., Лобода В. Г. К анализу двумерных сетей Петри // ТЖ. Автоматизация, телемеханизация и связь в нефтяной промышленности. -1.: ВНИИОЭНГ, 1996. - № 10.-С. 9-11.

2. Ельчанинов Д. Б., Лобода В. Г. Применение двумерных сетей Петри для инженерных сетей в контексте решения задачи достижимости // НТЖ. Автоматизация, телемеханизация и связь в нефтяной промышленности. - М.: ВНИИОЭНГ, 1997. - № 5-6. - С. 9-11.

3. Ельчанинов Д. Б. Об экономии ресурсов ЭВМ при моделировании двумерными сетями Петри // НТЖ. Автоматизация, телемеханизация и связь в нефтяной промышленности. - М.: ВНИИОЭНГ, 1997. - № 9-10. - С. 8-10.

4. Ельчанинов Д. Б. Моделирование иерархических структур ¿-сетями Петри // НТЖ. Автоматизация, телемеханизация и связь в нефтяной промышленности. - М.: ВНИИОЭНГ, 1998. - № 2. - С. 7-8.

5. Белова Н. В., Ельчанинов Д. Б., Лобода В. Г. Коммутационный аспект синтеза ¿-сетей Петри // НТЖ. Автоматизация, телемеханизация и связь в нефтяной промышленности. - М.: ВНИИОЭНГ, 1998. - № 11-12. - С. 13-14.

6. Ельчанинов Д. Б. Микропроцессорные иерархические системы управления на базе ¿-сетей Петри // Сб. статей "Актуальные проблемы современной науки в исследованиях молодых ученых г. Харькова". - X.: АО "Бизнес Ин-форм", 1998.-С. 20-23.

7. Ельчанинов Д. Б., Побеженко В. В., Сысенко И. Ю. Алгоритмы управления на базе сетей Петри с аналитическими дугами // Информационные технологии: наука, техника, технология, образование, здоровье: Сборник научных трудов ХГПУ. Вып. 7. В четырех частях. Ч. 1: - Харьков: Харьк. гос. политехи, унт, 1999.-С. 75-76.

8. Ельчанинов Д. Б., Матейченко В. В. Проектирование процессора Петри // Информационно-управляющие системы на железнодорожном транспорте. -1999,-№4.-С. 35-39.

9. Лобода В.Г., Ельчанинов Д.Б., Цуканов В.Ю. Модели архитектуры MISC-процессора // Радиоэлектроника и информатика, 1999, № 1. - С. 85-89.

10. Ельчанинов Д. Б., Лобода В. Г. Моделирование систем с динамической структурой ¿-сетями Петри // Сб. материалов мини-конф. "Математическое моделирование и информационные технологии". - Белгород: БелГТАСМ, 1997. -С. 179-188.

11. Elchaninov D. В., Loboda V. G. Modelling of systems with dynamic structure by ¿-Petri nets // Theses of conference "Mathematical modeling and information technologies". - Russiya, Belgorod, 1997. - pp. 34-36.

¡2. Ельчанинов Д. Б. О некоторой модификации сети Петри // Тез. докл. 1-го Международного молодежного форума "Электроника и молодежь в XXI веке". - Харьков: ХТУРЭ, 1997. - С. 230.

13. Ельчанинов Д. Б. ¿-сети Петри --инструмент моделирования динамических структур // Тез. докл. 3-й Международной конференции "Теория и техника передачи, приема и обработки информации". - Харьков-Туапсе: ХТУРЭ, 1997.-С. 165-166.

14. Ршення НДЦПЕ Держпатенту Укра'ши вщ 27.10.99 про видачу патенту на винахщ "Процесор ПетрГ / Сльчашнов Д. Б., Матейченко В. В., Лобода В.Г., Петришин Ю. С. - №99010005; Заявл. 04.01.99.

17

АНОТАЦШ

Сльчаншов Д. Б. Структуроваш мереж! Петр! в системах проектуван-ня спец!ал1зованих процесор1в. - Рукопис.

Дисертац1я на здобуття наукового ступеня кандидата техшчних наук за спещалынстю 05.13.12 - системи автоматизацн проектувальних робге. - Харюв-ський державний техшчний ушверситет радюелектрошки, Харюв, 1999.

Дисертащя присвячена розробщ структуровано! мереж! Петр! для моделю-вання складних ¡ерарх!чних багатор1'вневих обчислювальних систем на основ]' сучасного системного шдходу - системологн.

Розроблено структуровану мережу Петр! - ¿-мережа Петр!, - основною особлив!стю яко'1 е макромггка - мггка, що е мережею Петр!. Доведено екв!ва-лентн!сть р1зноманггаих тишв аналшгчних дут мереж! Петр!. Доведено екв!ва-лентшсть мереж Петр! з анаштичними дугами машинам Тюр!нга. Розроблено методику синтезу двох основних метод!в анашзу мереж Петр!: дерева досяжно-ст!! матричного р!вняння. Розроблено метод скороченого загшсу структури мереж! Петр!. Розроблено шструмснталышй програмний зас!б п!дтримки моде-лювання складних систем на основ! ¿-мереж! Петр!. Розроблено нову структуру процесора Петр! - спещагнзованого процесора, основною особливютю якого е програма у вигляд! мереж! Петр!. На основ! процесора Петр! розроблено метод проектування спещ'агшовано! м!кропроцесорно'1 системи, що програмусться ¿-мережею Петр!.

Ключов1 слова: автоматизоване проектування, мереж! Петр!, ]фарх!чш багатор!внев! системи.

АННОТАЦИЯ

Ельчанинов Д. Б. Структурированные сети Петри в системах проектирования специализированных процессоров. - Рукопись.

Диссертация на соискание ученой степени кандидата технических наук по специальности 05.13.12 - системы автоматизации проектных работ. - Харьковский государственный технический университет радиоэлектроники, Харьков, 1999.

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

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

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

Показано, что ¿-сети Петри удовлетворяют основным положениям современного системного подхода - системологии. С их помощью можно моделировать три основных вида структурных схем двухуровневых иерархических систем с учетом основных принципов координации работы подсистем.

В третьем разделе проводится исследование ¿-сетей Петри. Доказана эквивалентность различных типов аналитических дуг сети Петри. Показано, что использование аналитических дуг существенно сокращает размеры сети Петри. Доказана эквивалентность сетей Петри с аналитическими дугами машинам Тьюринга.

Разработана методика синтеза двух основных методов анализа сетей Петри: дерева достижимости и матричного уравнения. Показано, что в случае, когда матричное уравнение имеет конечное множество решений в целых неотрицательных числах, для решения задачи достижимости можно использовать вектор запуска как средство ограничения дерева достижимости.

Разработан метод сокращенной записи структуры сети Петри. Его использование позволяет уменьшить затраты памяти на хранение модели.

Любой уровень ¿-сети Петри является средой, в которой синтезируется некоторая сеть Петри, удовлетворяющая всем необходимым топологическим характеристикам. Установление требуемых связей между позициями и переходами можно осуществлять с помощью коммутационных структур (КС).

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

В четвертом разделе рассмотрены вопросы практического применения ¿-сетей Петри. Разработано инструментальное программное средство поддержки моделирования сложных систем на основе ¿-сети Петри. Программная разработка решшзует следующие функции: поддержка многоуровневых сетей (с практически неограниченным количеством подсетей); поддержка множественных атрибутов (цветов) сетей первого уровня; просмотр состояния сетей любого уровня в процессе моделирования; возможность внесения изменений в сеть во время моделирования; шаговое моделирование с детализацией; отображение информации о модели при визуализации; сохранение моделей в файлах со структурой поддерживающей дальнейшее развитие системы; визуальное отображение иерархии сетей.

Приведен пример использования программы для эмуляции модели М1БС-процессора. Модель построена с применением принципа двухуровневого программирования настройки на примере вычисления функции с использованием 2-сети Петри. Алгоритм вычисления функции представлен в виде сети Петри верхнего уровня. Чтобы показать процесс вычисления функции, макрометке се-

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

Предложенная модель отражает концепцию совместного проектирования ппаратных и программных средств (hardware-software codesign). При таком одходе модель программу и модель выполняющего ее процессора объединя->тся в единую модель, представленную в виде 2-сети Петри. Таким образом ожно проследить за изменением архитектуры MISC-процессора во время вы-олнения программы, что позволяет оптимальным образом адаптировать их руг к другу, с целью одновременной реализации как высокой скорости работы, ж и высокой точности вычислений.

Рассмотрен вопрос использования ¿-сетей Петри для проектирования мно-эуровневых иерархических систем управления на основе процессора Петри, гличительной особенностью которого является программа работы в виде сети етри.

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

Ключевые слова: автоматизированное проектирование, сети Петри, ие-фхические многоуровневые системы.

ABSTRACT

Elchaninov D. В. The structured Petri nets in systems of designing of spe-alized processors. - Manuscript.

Thesis for a candidate's degree by speciality 05.13.12 - Computer-Aided De-gn. - Kharkiv State Technical University of Radioelectronics, Kharkiv, 1999.

The thesis is devoted to development of the structured Petri net for simulation of >mposite hierarchical multilevel computing systems on the basis of modern system >proach - systemology.

The structured Petri net - ¿-net - is developed. The main feature of ¿-net is acrotoken - the token being a Petri net. The equivalence of different types of ana-tical arcs of a Petri net is proved. The equivalence of Petri nets with analytical arcs Turing machines is demonstrated. The technique of synthesis of two main methods ' the analysis of Petri nets (the reachability tree and the matrix equation) is devel->ed. The method of the abbreviated record of a Petri net structure is proposed. The ol software of support of simulation of composite systems is developed on the basis '¿-net. The new structure of the Petri processor is designed. The main feature of the :tri processor is the program as a Petri net. On the basis of the Petri processor the :sign technique of the specialized microprocessor system programmed by ¿-net is oposed.

Keywords: computer-aided design, Petri nets, hierarchical multilevel systems.