Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
28
мІнІстерство оСВІТИ і науки украЇнИ
ХАРКІВСЬКИЙ ДЕРЖАВНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ
РАДІОЕЛЕКТРОНІКИ
ЄЛЬЧАНіНОВ ДМИТРО БОРИСОВИЧ
УДК 519.71: 681.32/34
СТРУКТУРОВАНІ МЕРЕЖІ ПЕТРі У СИСТЕМАХ ПРОЕКТУВАННЯ СПЕЦІАЛІЗОВАНИХ ПРОЦЕСОРІВ
05.13.12 –системи автоматизації проектувальних робіт
Автореферат
Дисертацією є рукопис.
Робота виконана у Харківському державному технічному університеті радіоелектроніки, Міністерство освіти і науки України.
|
Науковий керівник |
кандидат технічних наук Лобода Віталій Гаврилович, Харківський державний технічний університет радіоелектроніки, професор кафедри автоматизації проектування обчислювальної техніки. |
|
Офіційні опоненти: |
доктор технічних наук, професор Філіппенко Ігор Григорович, Харківська державна академія залізничного транспорту, завідувач кафедри обчислювальної техніки та систем керування; доктор технічних наук, професор Вайнер Володимир Герасимович, Науково-технічний центр електрофізичної обробки НАН України, завідувач відділом. |
|
Провідна установа |
Харківський державний політехнічний університет (кафедра обчислювальної техніки та програмування), Міністерство освіти і науки України, м. Харків. |
Захист відбудеться " 26 " грудня 2000 року о 13 годині на засіданні спеціалізованої вченої ради Д 64.052.02 у Харківському державному технічному університеті радіоелектроніки за адресою: 61166, м. Харків, пр. Леніна, 14.
З дисертацією можна ознайомитись у бібліотеці Харківського державного технічного університету радіоелектроніки за адресою: 61166, м. Харків, пр. Леніна, 14.
Автореферат розісланий " 24 " листопада 2000 року.
|
Вчений секретар спеціалізованої вченої ради |
Безкоровайний В.В. |
ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ
Актуальність теми. Виникнення нової інформаційної технології є закономірним етапом удосконалювання процесів людино-машинного спілкування, у ході розвитку яких були вироблені певні вимоги до цієї технології. Нова сучасна інформаційна технологія повинна бути пристосована до користувача, який не є програмістом за фахом. Користувач за рахунок нової технології одержить можливість самостійної роботи із системою понять предметної галузі, можливість виділення в предметній галузі об'єктів і зв'язків, суттєвих для вирішення задачі. Це вимагає нового рівня “інтелектуальності”ЕОМ і, зокрема, здатності ЕОМ спілкуватися з користувачем на зрозумілій йому мові.
Орієнтація сучасних САПР на проектування складних обчислювальних систем призвела до виникнення нових мов проектування (наприклад, VHDL і Verilog), що описують не структуру проектованого об'єкта, а правила його функціонування. При цьому складність таких мов проектування порівняна зі складністю сучасних мов програмування. Для спрощення процесу проектування в сучасні САПР почали вводити модулі, що дозволяють описувати функціонування об'єкта проектування на більш простій і зрозумілій проектувальнику мові (електронних схем, таблиць істинності, блок-схем, кінцевих автоматів).
Мережі Петрі є зручним засобом опису й аналізу рівнобіжних процесів. Можливість модифікації мережі Петрі дозволяє адаптувати її для моделювання практично будь-яких об'єктів і процесів. Збільшення складності об'єктів, що моделюються, призводить до зростання розмірності мережі Петрі. Щоб спростити процес побудови моделі і підвищити її наочність, почали використовувати структуровані мережі Петрі. Для цього в моделі застосовують структуровані позиції, переходи, дуги і мітки.
Проте аналіз існуючих структурованих мереж Петрі показує, що вони орієнтовані на моделювання систем у певних вузьких предметних галузях і не можуть бути використані для моделювання складних систем у довільній предметній галузі. Щоб застосування структурованої мережі Петрі не обмежувалося предметною галуззю, необхідно створити структуровану мережу Петрі в рамках загальної теорії, що описує складні системи довільної предметної галузі. Однієї з таких теорій є теорія систем. Тому актуальною для моделювання складних обчислювальних систем є розробка структурованої мережі Петрі, що задовольняє основним положенням сучасного системного підходу –системології.
Зв'язок роботи з науковими програмами, планами, темами. Дисертаційна робота виконана згідно з планом науково-технічних робіт Харківського державного технічного університету радіоелектроніки в рамках держбюджетної теми "Розробка математичного забезпечення та програмно-апаратних засобів систем контролю і управління виробничими і технологічними процесами", що є частиною програми 40 Міністерства освіти і науки України "Методи побудови та створення комп'ютеризованих систем і технологій".
Мета роботи: розробка структурованої мережі Петрі для моделювання складних ієрархічних багаторівневих обчислювальних систем на основі сучасного системного підходу –системології.
Задачі дослідження. Згідно з поставленою метою задачами дослідження в дисертаційній роботі є:
Наукова новизна одержаних результатів:
Практичне значення одержаних результатів. Практична цінність отриманих результатів полягає в тому, що:
Результати роботи впроваджені в АТ "Науково-дослідний інститут радіовимірювань" у вигляді математичних моделей і інструментального програмного засобу при розробці системи збору, оперативної обробки та аналізу інформації про стан засобів наземного автоматизованого комплексу управління космічними апаратами. Наукові положення і висновки, приведені в дисертації, використані при підготовці курсу "Спеціалізовані архітектури ЕОМ" на кафедрі автоматизації проектування обчислювальної техніки Харківського державного технічного університету радіоелектроніки.
Особистий внесок. Основні результати дисертації одержані особисто автором. У друкованих працях, опублікованих у співавторстві, автору належить розробка 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(P), M(P),…, M(Pn)) всіх її підсистем, а на виході системи S з'являється вектор , де –мережа Петрі, що визначає алгоритм поведінки підсистеми Si у стані (M(P), M(P),…, M(Pn)).
Отже, система S реалізує деяку функцію f(M(P), M(P),…, 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. Розбивка класів еквівалентностей повинна задовольняти таким умовам:
Нехай 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 за допомогою бієктивного відображення f зіставляється множина позицій першого рівня: f1 : MC PS, де . Потім кожній мітці mi за допомогою бієктивного відображення f зіставляється множина мереж Петрі першого рівня зі спільною множиною позицій першого рівня: f2 : MC NS, де . Після цього кожній мітці mi за допомогою бієктивного відображення f зіставляється початкова мережа Петрі з множини відповідних мереж Петрі першого рівня: f3 : MC NS0, де . Нарешті, кожній мітці mi за допомогою бієктивного відображення f зіставляється початкове маркірування множини позицій першого рівня: f4 : MC MS, де .
Таким чином, мітці мережі Петрі другого рівня зіставляється мережа Петрі першого рівня. Така мітка називається макроміткою.
Множина АС дуг мережі Петрі другого рівня розбивається на підмножину вхідних дуг і підмножину вихідних дуг. Кожній вхідній дузі а мережі Петрі другого рівня за допомогою відображення f зіставляється деяка макромітка mi із множини МС міток мережі Петрі другого рівня: . Потім, якщо вхідній дузі а мережі Петрі другого рівня зіставлена макромітка mi із множини МС міток мережі Петрі другого рівня, то цій дузі а за допомогою відображення f зіставляється деяке маркірування множини позицій першого рівня, зіставлених макромітці mi: .
Вхідна дуга aI(tj) O(pk) мережі Петрі другого рівня дозволяє перехід tj, якщо в позиції pk знаходиться макромітка mi, що відповідає дузі а, і маркірування позицій першого рівня, що відповідають макромітці mi, зіставлено дузі а: f(mi) = pk, f(a) = mi, , . Перехід другого рівня дозволений, якщо усі вхідні дуги переходу tj дозволяють його.
Кожній вихідній дузі а мережі Петрі другого рівня за допомогою відображення f зіставляється деяка макромітка mi із множини МС міток мережі Петрі другого рівня: . Потім, якщо вихідній дузі а мережі Петрі другого рівня зіставлена макромітка mi із множини МС міток мережі Петрі другого рівня, то цій дузі а за допомогою відображення f зіставляється деяка мережа Петрі з множини , зіставленої макромітці mi: .
Якщо в перехід входить дуга а, якій відповідає макромітка mi, то з переходу повинна виходити дуга b, котрій також відповідає макромітка mi. Якщо з переходу виходить дуга b, якій відповідає макромітка mi, то в перехід повинна входити дуга а, котрій також відповідає макромітка mi. У перехід не може входити дві дуги, яким зіставлена одна макромітка. Аналогічно, із переходу не можуть виходити дві дуги, яким зіставлена одна макромітка.
Якщо перехід дозволений, то він може бути запущений. При запуску переходу tj макромітка переміщається з вхідної позиції по відповідній вхідній дузі, проходить через перехід tj і по відповідній вихідній дузі поміщається у вихідну позицію переходу tj. При цьому мережа Петрі, що відповідала макромітці до запуску переходу, заміняється мережею Петрі, зіставленої вихідній дузі, по якій макромітка потрапила у вихідну позицію переходу.
Приклад 2-мережі Петрі приведений на рис.1.
Показано, що 2-мережі Петрі задовольняють основним положенням сучасного системного підходу –системології. З їхньою допомогою можна моделювати три основні види структурних схем дворівневих ієрархічних систем з урахуванням основних принципів координації роботи підсистем.
Якщо макромітці 2-мережі Петрі у свою чергу зіставити 2-мережі Петрі, то утвориться 3-мережа Петрі. Мережі Петрі першого рівня відповідають макроміткам 2-мереж Петрі, мережі Петрі другого рівня - макроміткам 3-мережі Петрі, на третьому рівні знаходяться макромітки 3-мережі Петрі.
L-мережа Петрі будується шляхом зіставлення макроміткам 2-мережі Петрі (L –)-мереж Петрі.
У третьому розділі здійснюється дослідження 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. Запис
(kipi... kirpir ; kjpj... kjspjs ) q
|
(2) |
називається відповідністю позицій із номером q (q-ю відповідністю позицій) і означає, що позиції рi(=1,2,... ,r) є вхідними, а pj(=1,2,... ,s ) - вихідними позиціями для переходу tq, при цьому коефіцієнт ki (kj) показує кратність позиції рi(pj).
Визначення 3. Запис
(kipi... kirpir : kjpj... kjspjs ) q
|
(3) |
називається оберненою відповідністю позицій і визначається рівністю
(kipi... kirpir : kjpj... kjspjs ) q = (kjpj... kjspjs ; kipi... kirpir) q.
|
(4) |
Вводяться операції над відповідностями позицій.
Визначення 4. Операція виносу позиції над відповідністю позицій визначається рівністю:
|
( ... ; kj1pj1... kjspjs ) q = ( ... ; kj1pj1... kjs) q pjs. |
(5) |
Можна винести будь-яку позицію pj(=1,2,... ,s-1), переставивши її разом із коефіцієнтом kjна місце позиціїpjs.
Операція виносу за дужку над оберненою відповідністю позицій визначається аналогічно, заміною в рівності (5) знаків ";" на знаки ":".
Визначення 5. Операція вкладення визначається для двох відповідностей позицій із номерами q і q, що мають спільну позицію pi, рівностями
|
(...;...ai)qpi (... ;...bipi...)q=(... ;...bi(... ;...ai)qpi...)q, |
(6) |
|
(...;...ai)qpi (...cipi... ;...)q= (...ci(... ;...ai)qpi... ;...)q, |
(7) |
де ai, bi та сi- коефіцієнти при pi.
Рівності (6) і (7) називаються формулами вкладення відповідностей (q-а відповідність вкладена в q-у відповідність).
Операція для двох обернених відповідностей позицій визначається аналогічно, заміною у формулах (6) і (7) знаків ";" на знаки ":".
Операція для двох відповідностей позицій різних типів визначається заміною в рівностях (6) і (7) відповідних знаків ";" на знаки ":". Наприклад, операція вкладення q-ї оберненої відповідності позицій у q-у відповідність позицій, які мають спільну позицію pi, визначається, зокрема, рівністю
|
(... : ...ai)qpi (... ;...bipi...)q=(... ;...bi(... : ...ai)qpi...)q. |
(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-мереж Петрі.
Проведено аналіз структури й алгоритму роботи процесора Петрі. У результаті виявлені такі суттєві недоліки:
Запропоновано нову структуру й алгоритм роботи процесора Петрі. Основні зміни полягають в наступному:
За матеріалами дослідження подана заявка на винахід "Процесор Петрі". Науково-дослідним центром патентної експертизи Держпатенту України 27.10.99 р. прийнято рішення про видачу патенту.
Додатки містять приклад мережі Петрі, яка еквівалентна аналітичній дузі та схеми блоків модифікованого процесора Петрі.
У дисертації вирішена актуальна наукова задача розробки структурованої мережі Петрі для моделювання складних ієрархічних багаторівневих обчислювальних систем на основі сучасного системного підходу –системології:
СПИСОК ОПУБЛІКОВАНИХ ПРАЦЬ ЗА ТЕМОЮ ДИСЕРТАЦІЇ
АНОТАЦІЯ
Єльчанінов Д. Б. Структуровані мережі Петрі в системах проектування спеціалізованих процесорів. –Рукопис.
Дисертація на здобуття наукового ступеня кандидата технічних наук за спеціальністю 05.13.12 - системи автоматизації проектувальних робіт. –Харківський державний технічний університет радіоелектроніки, Харків, 1999.
Дисертація присвячена розробці структурованої мережі Петрі для моделювання складних ієрархічних багаторівневих обчислювальних систем на основі сучасного системного підходу –системології.
Розроблено структуровану мережу Петрі - L-мережа Петрі, - основною особливістю якої є макромітка - мітка, що є мережею Петрі. Доведено еквівалентність різноманітних типів аналітичних дуг мережі Петрі. Доведено еквівалентність мереж Петрі з аналітичними дугами машинам Тюрінга. Розроблено методику синтезу двох основних методів аналізу мереж Петрі: дерева досяжності і матричного рівняння. Розроблено метод скороченого запису структури мережі Петрі. Розроблено інструментальний програмний засіб підтримки моделювання складних систем на основі L-мережі Петрі. Розроблено нову структуру процесора Петрі - спеціалізованого процесора, основною особливістю якого є програма у вигляді мережі Петрі. На основі процесора Петрі розроблено метод проектування спеціалізованої мікропроцесорної системи, що програмується L-мережею Петрі.
Ключові слова: автоматизоване проектування, мережі Петрі, ієрархічні багаторівневі системи.
Аннотация
Ельчанинов Д. Б. Структурированные сети Петри в системах проектирования специализированных процессоров. –Рукопись.
Диссертация на соискание ученой степени кандидата технических наук по специальности 05.13.12 –системы автоматизации проектных работ. –Харьковский государственный технический университет радиоэлектроники, Харьков, 1999.
Диссертация посвящена разработке структурированной сети Петри для моделирования сложных иерархических многоуровневых вычислительных систем на основе современного системного подхода –системологии.
В первом разделе проводится анализ структурированных сетей Петри, инструментальных программных средств на их основе, специализированных микропроцессорных устройств моделирования сетей Петри и специализированных процессоров, программируемых сетями Петри. Определяется цель работы, и формулируются основные задачи исследования.
Во втором разделе разработана новая модификация сети Петри –L-сеть Петри –, предназначенная для моделирования сложных иерархических многоуровневых вычислительных систем с изменяющейся в процессе работы структурой. Основной особенностью L-сети Петри является макрометка –метка, являющаяся сетью Петри.
Показано, что L-сети Петри удовлетворяют основным положениям современного системного подхода –системологии. С их помощью можно моделировать три основных вида структурных схем двухуровневых иерархических систем с учетом основных принципов координации работы подсистем.
В третьем разделе проводится исследование L-сетей Петри. Доказана эквивалентность различных типов аналитических дуг сети Петри. Показано, что использование аналитических дуг существенно сокращает размеры сети Петри. Доказана эквивалентность сетей Петри с аналитическими дугами машинам Тьюринга.
Разработана методика синтеза двух основных методов анализа сетей Петри: дерева достижимости и матричного уравнения. Показано, что в случае, когда матричное уравнение имеет конечное множество решений в целых неотрицательных числах, для решения задачи достижимости можно использовать вектор запуска как средство ограничения дерева достижимости.
Разработан метод сокращенной записи структуры сети Петри. Его использование позволяет уменьшить затраты памяти на хранение модели.
Любой уровень L-сети Петри является средой, в которой синтезируется некоторая сеть Петри, удовлетворяющая всем необходимым топологическим характеристикам. Установление требуемых связей между позициями и переходами можно осуществлять с помощью коммутационных структур (КС).
Исследован вопрос синтеза сетей Петри на базе инструментальных средств телетрафика. Определены ограничения, которые накладывает на КС задача синтеза сетей Петри: КС должна быть смешанной, реализовывать неординарные связи и обладать возможностью быстрого перестроения соединений. Существует много КС, удовлетворяющих этим ограничениям. Возникает задача выбора КС, оптимальной по некоторому параметру. Рассмотрен пример, в котором в качестве параметра, определяющего выбор КС, берется число точек коммутации КС: оптимальной является КС с меньшим числом точек коммутации.
В четвертом разделе рассмотрены вопросы практического применения L-сетей Петри. Разработано инструментальное программное средство поддержки моделирования сложных систем на основе L-сети Петри. Программная разработка реализует следующие функции: поддержка многоуровневых сетей (с практически неограниченным количеством подсетей); поддержка множественных атрибутов (цветов) сетей первого уровня; просмотр состояния сетей любого уровня в процессе моделирования; возможность внесения изменений в сеть во время моделирования; шаговое моделирование с детализацией; отображение информации о модели при визуализации; сохранение моделей в файлах со структурой поддерживающей дальнейшее развитие системы; визуальное отображение иерархии сетей.
Приведен пример использования программы для эмуляции модели MISC-процессора. Модель построена с применением принципа двухуровневого программирования настройки на примере вычисления функции с использованием 2-сети Петри. Алгоритм вычисления функции представлен в виде сети Петри верхнего уровня. Чтобы показать процесс вычисления функции, макрометке сети Петри верхнего уровня сопоставлены сети Петри нижнего уровня, позиции которых моделируют ячейки памяти для хранения промежуточных результатов вычисления функции, а переходы –необходимые операции для вычисления этой функции.
Предложенная модель отражает концепцию совместного проектирования аппаратных и программных средств (hardware-software codesign). При таком подходе модель программы и модель выполняющего ее процессора объединяются в единую модель, представленную в виде 2-сети Петри. Таким образом можно проследить за изменением архитектуры MISC-процессора во время выполнения программы, что позволяет оптимальным образом адаптировать их друг к другу, с целью одновременной реализации как высокой скорости работы, так и высокой точности вычислений.
Рассмотрен вопрос использования L-сетей Петри для проектирования многоуровневых иерархических систем управления на основе процессора Петри, отличительной особенностью которого является программа работы в виде сети Петри.
Разработана новая структура и алгоритм работы процессора Петри. Исправлены ошибки функционирования процессора и увеличено его быстродействие. На основе процессора Петри разработан метод проектирования специализированной микропроцессорной системы, программируемой L-сетью Петри. Применение этого метода значительно упрощает разработку иерархических систем управления.
Ключевые слова: автоматизированное проектирование, сети Петри, иерархические многоуровневые системы.
abstract
Elchaninov D. B. The structured Petri nets in systems of designing of specialized processors. - Manuscript.
Thesis for a candidate’s degree by speciality 05.13.12 –Computer-Aided Design. – Kharkiv State Technical University of Radioelectronics, Kharkiv, 1999.
The thesis is devoted to development of the structured Petri net for simulation of composite hierarchical multilevel computing systems on the basis of modern system approach –systemology.
The structured Petri net –L-net –is developed. The main feature of L-net is macrotoken - the token being a Petri net. The equivalence of different types of analytical arcs of a Petri net is proved. The equivalence of Petri nets with analytical arcs to Turing machines is demonstrated. The technique of synthesis of two main methods of the analysis of Petri nets (the reachability tree and the matrix equation) is developed. The method of the abbreviated record of a Petri net structure is proposed. The tool software of support of simulation of composite systems is developed on the basis of L-net. The new structure of the Petri processor is designed. The main feature of the Petri processor is the program as a Petri net. On the basis of the Petri processor the design technique of the specialized microprocessor system programmed by L-net is proposed.
Keywords: computer-aided design, Petri nets, hierarchical multilevel systems.
Єльчанінов Дмитро Борисович
СТРУКТУРОВАНІ МЕРЕЖІ ПЕТРі У СИСТЕМАХ ПРОЕКТУВАННЯ СПЕЦІАЛІЗОВАНИХ ПРОЦЕСОРІВ
Спеціальність: 05.13.12 –системи автоматизації
проектувальних робіт
Автореферат
дисертації на здобуття
наукового ступеня кандидата технічних наук
Відповідальний за випуск Кривуля Г.Ф.
Підписано до друку 02.06.2000р. Формат 60х84 1/16. Умов. друк арк. 1,0. Облік.-вид. арк. 0,9. Тираж 100 прим. Зам. № 2-420. Ціна договірна.
Надруковано в учбово-виробничному видавнично-поліграфічному центрі ХТУРЕ, 61166 Україна, Харків, пр. Леніна, 14