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

МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ

ХАРКІВСЬКИЙ ДЕРЖАВНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ РАДІОЕЛЕКТРОНІКИ

УДК 519.71: 681.32/34

Автореферат

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

СТРУКТУРОВАНІ МЕРЕЖІ ПЕТРІ У СИСТЕМАХ ПРОЕКТУВАННЯ СПЕЦІАЛІЗОВАНИХ ПРОЦЕСОРІВ

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

ЄЛЬЧАНІНОВ ДМИТРО БОРИСОВИЧ

Харків - 2000

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

Робота виконана у Харківському державному технічному університеті радіоелектроніки, Міністерство освіти і науки України.

Науковий керівник

кандидат технічних наук Лобода Віталій Гаврилович,

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

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

доктор технічних наук, професор Філіппенко Ігор Григорович,

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

доктор технічних наук, професор Вайнер Володимир Герасимович,

Науково-технічний центр електрофізичної обробки НАН України, завідувач відділом.

Провідна установа

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

Захист відбудеться " 26 " грудня 2000 року о 13 годині на засіданні спеціалізованої вченої ради Д 64.052.02 у Харківському державному технічному університеті радіоелектроніки за адресою: 61166, м. Харків, пр. Леніна, 14.

З дисертацією можна ознайомитись у бібліотеці Харківського державного технічного університету радіоелектроніки за адресою: 61166, м. Харків, пр. Леніна, 14.

Автореферат розісланий " 24 " листопада 2000 року.

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

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

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

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

Орієнтація сучасних САПР на проектування складних обчислювальних систем призвела до виникнення нових мов проектування (наприклад, VHDL і Verilog), що описують не структуру проектованого об'єкта, а правила його функціонування. При цьому складність таких мов проектування порівняна зі складністю сучасних мов програмування. Для спрощення процесу проектування в сучасні САПР почали вводити модулі, що дозволяють описувати функціонування об'єкта проектування на більш простій і зрозумілій проектувальнику мові (електронних схем, таблиць істинності, блок-схем, кінцевих автоматів).

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

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

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

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

Задачі дослідження. Згідно з поставленою метою задачами дослідження в дисертаційній роботі є:

аналіз структурованих мереж Петрі з метою вибору мережі Петрі, на основі якої можна розробити мережу Петрі для моделювання складних обчислювальних систем;

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

дослідження потужності моделювання розробленої структурованої мережі Петрі;

розробка методів аналізу структурованої мережі Петрі;

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

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

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

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

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

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

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

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

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

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

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

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

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

Результати роботи впроваджені в АТ "Науково-дослідний інститут радіовимірювань" у вигляді математичних моделей і інструментального програмного засобу при розробці системи збору, оперативної обробки та аналізу інформації про стан засобів наземного автоматизованого комплексу управління космічними апаратами. Наукові положення і висновки, приведені в дисертації, використані при підготовці курсу "Спеціалізовані архітектури ЕОМ" на кафедрі автоматизації проектування обчислювальної техніки Харківського державного технічного університету радіоелектроніки.

Особистий внесок. Основні результати дисертації одержані особисто автором. У друкованих працях, опублікованих у співавторстві, автору належить розробка L-мережі Петрі [1,10,11], доказ леми і теореми про еквівалентність аналітичних дуг і еквівалентність мереж Петрі з аналітичними дугами машинам Тюрінга [7,8], розробка синтезу основних методів аналізу мереж Петрі: дерева досяжності і матричного рівняння [2,10,11], розробка методу зменшення витрат пам'яті на збереження структури мережі Петрі [10,11], розробка методу вибору комутаційної структури для синтезу мережі Петрі [5], розробка нової структури та алгоритму роботи процесора Петрі [8,14], розробка моделі MISC-процесора на основі 2-мережі Петрі [9].

Апробація результатів дисертації. Основні результати роботи доповідались на: 1-му Міжнародному молодіжному форумі "Електроніка і молодь у XXI сторіччі" (Харків, 1997 р.), 3-й Міжнародній конференції "Теорія і техніка передачі, прийому та обробки інформації" (Туапсе, 1997 р.), Міжнародній міні-конференції "Математичне моделювання та інформаційні технології" (Росія, Бєлгород, 1997 р.), 2-му Молодіжному форумі "Радіоелектроніка і молодь у XXI сторіччі" (Харків, 1998 р.), 2-й міській науково-практичній конференції "Актуальні проблеми сучасної науки в дослідженнях молодих вчених м. Харкова" (1998 р.), 7-й Міжнародній науково-технічній конференції "Інформаційні технології: наука, техніка, технологія, освіта, здоров'я" (Харків, 1999 р.).

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

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

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

петрі мережа структурований пам'ять

У вступі обгрунтована актуальність теми, сформульовані мета і задачі роботи, відзначені наукова новизна і практична цінність отриманих результатів.

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

Визначено мету роботи, і сформульовані основні задачі дослідження.

Формальна постановка задачі має такий вигляд. Нехай система S складається з множини підсистем Si, і алгоритм поведінки підсистеми Si у k-ій ситуації описується у вигляді мережі Петрі . Таким чином, кожній підсистемі Si відповідає множина Ni алгоритмів поведінки у вигляді множини мереж Петрі: , і стан кожної підсистеми Si визначається маркіруванням M(Pi) позицій Pi мережі Петрі з множини Ni. Задача системи S - змінювати алгоритми поведінки підсистем у залежності від досягнутих ними станів . Таким чином, на вхід системи S подаються стани (M(P1), M(P2),…, M(Pn)) всіх її підсистем, а на виході системи S з'являється вектор , де - мережа Петрі, що визначає алгоритм поведінки підсистеми Si у стані (M(P1), M(P2),…, M(Pn)).

Отже, система S реалізує деяку функцію f(M(P1), M(P2),…, M(Pn)). Потрібно розробити мережу Петрі N, що описує функцію f.

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

Нехай A - множина дуг. На множині A задається відношення еквівалентності . Клас еквівалентності називається позицією. Фактормножина є множиною позицій. Потім на множині A задається відношення еквівалентності . Клас еквівалентності називається переходом. Фактормножина є множиною переходів.

Для кожного класу pi задається розбивка pi = I(pi) O(pi). Множина I(pi) називається множиною вхідних дуг для позиції pi, а множина O(pi) - множиною вихідних дуг для позиції pi. Потім для кожного класу tj задається розбивка tj = I(tj) O(tj). Множина I(tj) називається множиною вхідних дуг для переходу tj, а множина O(tj) - множиною вихідних дуг для переходу tj. Розбивка класів еквівалентностей повинна задовольняти таким умовам:

Для будь-якої дуги aI(pi) існує перехід tj A/, такий, що aO(tj).

Для будь-якої дуги aO(pi) існує перехід tj A/, такий, що aI(tj).

Для будь-якої дуги aI(tj) існує позиція pi A/, така, що aO(pi).

Для будь-якої дуги aO(tj) існує позиція pi A/, така, що aI(pi).

Нехай N0 - множина цілих невід'ємних чисел, R={<,>,,=,,} - множина стандартних відношень на множині N0. Задається функція типу V: AR{+}. Якщо V(a)R, то дуга a називається аналітичною. Якщо V(a)=”+”, то дуга a називається транспортною. Функція типу повинна задовольняти такій умові: якщо aO(tj), то V(a)=”+”. Задається функція ваги W: A N0, така, що якщо V(a)=”+”, то W(a) 0. Задається функція маркірування M: A/ N0.

Сукупність N = (A, A/, A/, V, W, M) називається мережею Петрі першого рівня.

Транспортна дуга aI(tj) O(pi) дозволяє перехід tj, якщо W(a) M(pi). Аналітична дуга aI(tj) O(pi) дозволяє перехід tj, якщо (M(pi), W(a)) V(a). Перехід tj дозволений, якщо усі вхідні дуги tj дозволяють його. Дозволений перехід можна запустити. Якщо два переходи знаходяться в конфлікті, то він вирішується за допомогою пріоритету, заданого на множині переходів. Запуск переходу tj змінює маркірування M мережі Петрі N на нове маркірування M* в такий спосіб:

M*(pi) = M(pi) - W(a1) + W(a2), (1)

де a1I(tj) O(pi), a2O(tj) I(pi) та V(a1)=”+”.

Транспортна дуга aI(tj) O(pi) називається конвеєрною, якщо W(a) = 0. Вхідна конвеєрна дуга завжди дозволяє перехід tj. Перехід може мати тільки одну вхідну конвеєрну дугу. При запуску переходу tj вхідна конвеєрна дуга а видаляє M(pi) міток із позиції pi. Якщо перехід tj має вихідну конвеєрну дугу, то у нього повинна бути вхідна конвеєрна дуга. При запуску переходу tj вихідна конвеєрна дуга a добавляє в позицію pi стільки міток, скільки видалила з відповідної позиції вхідна конвеєрна дуга переходу tj.

Структура мережі Петрі другого рівня визначається трійкою: NC = (AC, AC /C, AC /C), де АС - множина дуг мережі Петрі, С и С - відношення еквівалентності на множині AС, AC /C та AC /C - множини позицій і переходів. Нехай - множина міток мережі Петрі NC. Розподіл міток по позиціях задається початковою функцією маркірування . Кожній мітці mi за допомогою бієктивного відображення f1 зіставляється множина позицій першого рівня: f1 : MC PS, де . Потім кожній мітці mi за допомогою бієктивного відображення f2 зіставляється множина мереж Петрі першого рівня зі спільною множиною позицій першого рівня: f2 : MC NS, де . Після цього кожній мітці mi за допомогою бієктивного відображення f3 зіставляється початкова мережа Петрі з множини відповідних мереж Петрі першого рівня: f3 : MC NS0, де . Нарешті, кожній мітці mi за допомогою бієктивного відображення f4 зіставляється початкове маркірування множини позицій першого рівня: f4 : MC MS, де .

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

Множина АС дуг мережі Петрі другого рівня розбивається на підмножину вхідних дуг і підмножину вихідних дуг. Кожній вхідній дузі а мережі Петрі другого рівня за допомогою відображення f5 зіставляється деяка макромітка mi із множини МС міток мережі Петрі другого рівня: . Потім, якщо вхідній дузі а мережі Петрі другого рівня зіставлена макромітка mi із множини МС міток мережі Петрі другого рівня, то цій дузі а за допомогою відображення f6 зіставляється деяке маркірування множини позицій першого рівня, зіставлених макромітці mi: .

Вхідна дуга aI(tj) O(pk) мережі Петрі другого рівня дозволяє перехід tj, якщо в позиції pk знаходиться макромітка mi, що відповідає дузі а, і маркірування позицій першого рівня, що відповідають макромітці mi, зіставлено дузі а: f1(mi) = pk, f5(a) = mi, , . Перехід другого рівня дозволений, якщо усі вхідні дуги переходу tj дозволяють його.

Кожній вихідній дузі а мережі Петрі другого рівня за допомогою відображення f7 зіставляється деяка макромітка mi із множини МС міток мережі Петрі другого рівня: . Потім, якщо вихідній дузі а мережі Петрі другого рівня зіставлена макромітка mi із множини МС міток мережі Петрі другого рівня, то цій дузі а за допомогою відображення f8 зіставляється деяка мережа Петрі з множини , зіставленої макромітці mi: .

Якщо в перехід входить дуга а, якій відповідає макромітка mi, то з переходу повинна виходити дуга b, котрій також відповідає макромітка mi. Якщо з переходу виходить дуга b, якій відповідає макромітка mi, то в перехід повинна входити дуга а, котрій також відповідає макромітка mi. У перехід не може входити дві дуги, яким зіставлена одна макромітка. Аналогічно, із переходу не можуть виходити дві дуги, яким зіставлена одна макромітка.

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

Приклад 2-мережі Петрі приведений на рис.1.

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

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

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

У третьому розділі здійснюється дослідження L-мереж Петрі.

У мережах Петрі першого рівня використовуються аналітичні дуги, що являються узагальненням інгібіторних (стримуючих, блокуючих) дуг: інгібіторна дуга є аналітичною дугою a, такою що V(a) = “<” та W(a) = 1. Відомо, що мережа Петрі з інгібіторними дугами еквівалентна машині Тюрінга.

Досліджено еквівалентність аналітичних дуг різноманітних типів. Для цього вводяться такі позначення: через позначена аналітична дуга a, така, що W(a) = x та V(a) = “y” (наприклад, позначає аналітичну дугу a, таку, що W(a) = 5 та V(a) = “”); якщо мережа Петрі має аналітичні дуги, то їхні типи вказуються в скобках після позначення мережі Петрі (наприклад, N(>,=) означає, що мережа Петрі N має аналітичні дуги типу ">" та "="; означає, що мережа Петрі N має аналітичні дуги ).

Доведено такі властивості мереж Петрі з аналітичними дугами.

Твердження 1. N(<,>,,=,,) ~ N*(<,>,,=,). Це твердження показує, що дуга еквівалентна дузі : дугу можна замінити дугою , і навпаки.

Твердження 2. N(<,>,,=,) ~ N*(<,>,,=). Це твердження показує, що дуга еквівалентна дузі : дугу можна замінити дугою , і навпаки.

Твердження 3. N(<,>,,=) ~ N*(<,>,). Це твердження показує, що дуга еквівалентна дугам та : дугу можна замінити парою дуг та , і навпаки.

Твердження 4. N(<,>,) ~ N*(<,>). Це твердження показує, що дуга еквівалентна дугам та : дугу можна замінити парою дуг та , і навпаки.

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

Лема. . Ця лема показує, що дуга еквівалентна мережі Петрі з інгібіторними дугами: дугу можна замінити мережею Петрі з інгібіторними дугами, і навпаки. Причому, чим більше значення w, тим більше розмір мережі Петрі, що може замінити дугу . Таким чином, аналітична дуга дозволяє значно зменшити розмір мережі Петрі.

З тверджень 1-5 та леми випливає теорема.

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

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

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

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

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

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

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

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

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

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

(ki1 pi1 ... kir pir ; kj1 pj1 ... kjs pjs ) q (2)

називається відповідністю позицій із номером q (q-ю відповідністю позицій) і означає, що позиції рi (=1,2,... ,r) є вхідними, а pj (=1,2,... ,s ) - вихідними позиціями для переходу tq, при цьому коефіцієнт ki (kj) показує кратність позиції рi (pj).

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

(ki1 pi1 ... kir pir : kj1 pj1 ... kjs pjs ) q (3)

називається оберненою відповідністю позицій і визначається рівністю

(ki1 pi1 ... kir pir : kj1 pj1 ... kjs pjs ) q = (kj1 pj1 ... kjs pjs ; ki1 pi1 ... kir pir) q. (4)

Вводяться операції над відповідностями позицій.

Визначення 4. Операція виносу позиції над відповідністю позицій визначається рівністю:

( ... ; kj1 pj1 ... kjs pjs ) q = ( ... ; kj1 pj1 ... kjs ) q pjs . (5)

Можна винести будь-яку позицію pj (=1,2,... ,s-1), переставивши її разом із коефіцієнтом kj на місце позиції pjs.

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

Визначення 5. Операція вкладення визначається для двох відповідностей позицій із номерами q1 і q2, що мають спільну позицію pi, рівностями

(...;...ai)q1pi (... ;...bipi...)q2 = (... ;...bi (... ;...ai)q1 pi...)q2, (6)

(...;...ai)q1pi (...cipi... ;...)q2 = (...ci (... ;...ai)q1 pi ... ;...)q2, (7)

де ai , bi та сi - коефіцієнти при pi.

Рівності (6) і (7) називаються формулами вкладення відповідностей (q1-а відповідність вкладена в q2-у відповідність).

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

Операція для двох відповідностей позицій різних типів визначається заміною в рівностях (6) і (7) відповідних знаків ";" на знаки ":". Наприклад, операція вкладення q1-ї оберненої відповідності позицій у q2-у відповідність позицій, які мають спільну позицію pi, визначається, зокрема, рівністю

(... : ...ai)q1pi (... ;...bipi...)q2 = (... ;...bi (... : ...ai)q1 pi...)q2. (8)

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

Порівнюються витрати пам'яті при завданні структури мережі Петрі у вигляді матриць і у вигляді зв'язного запису. Якщо позначити через n і m число відповідно позицій і переходів мережі Петрі, а через a і b - частку відповідно нульових і ненульових елементів у матрицях інціденцій, то для порівняння витрат пам'яті L на збереження структури у вигляді зв'язного запису з витратами пам'яті M на збереження структури у вигляді матриць отримана така формула:

. (9)

Ця формула показує, що, тому що на практиці матриці інціденції містять не менше 80% нулів, зв'язний запис дозволить заощаджувати не менше 50% пам'яті.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Якщо складна система складається з дуже великого числа підсистем, то можлива така ситуація, при якій підсистеми об'єднуються в групи, кожна з якої знаходиться під керуванням декількох керуючих процесорів Петрі і одного процесора Петрі, що узгоджує. У цьому випадку виникає необхідність узгодження роботи всіх процесорів, що узгоджують. Для цього також можна використовувати процесор Петрі. Так утворюється трьохрівнева система керування на базі 3-мережі Петрі. Аналогічно проектуються мультипроцесорні ієрархічні багаторівневі системи керування складними об'єктами на основі L-мереж Петрі.

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

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

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

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

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

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

Структура мережі Петрі записується у вигляді списку дуг. Вхідна дуга а записується у вигляді a = (a1, a2, a3, a4), де a1 - номер позиції, із якої виходить дуга, a2 - вага дуги, a3 - тип дуги, a4 - номер переходу, у який входить дуга. Вихідна дуга b записується у вигляді b = (b1, b2, b3), де b1 - номер переходу, із якого виходить дуга, b2 - вага дуги, b3 - номер позиції, у яку входить дуга.

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

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

За матеріалами дослідження подана заявка на винахід "Процесор Петрі". Науково-дослідним центром патентної експертизи Держпатенту України 27.10.99 р. прийнято рішення про видачу патенту.

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

ВИСНОВКИ

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

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

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

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

Удосконалено методику аналізу мереж Петрі шляхом синтезу двох основних методів аналізу мереж Петрі: дерева досяжності і матричного рівняння. Це дозволило скоротити час аналізу мережі Петрі за рахунок обмеження дерева досяжності за допомогою вектора запуску.

Одержав подальший розвиток метод скороченого запису структури мережі Петрі. Його використання дозволяє зменшити витрати пам'яті на збереження моделі.

Розроблено інструментальний програмний засіб підтримки моделювання складних систем на основі L-мережі Петрі. Він дозволяє моделювати складні багаторівневі ієрархічні системи, які змінюють свою структуру у процесі роботи. Показано, що він може бути використаний для спільного проектування апаратних і програмних засобів (hardware-software codesign).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

АНОТАЦІЯ

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

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

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

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

Ключові слова: автоматизоване проектування, мережі Петрі, ієрархічні багаторівневі системи.

АННОТАЦИЯ

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

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

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

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

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

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

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

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

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

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

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

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

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

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

...