Мережеві моделі

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

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

У загальному випадку кожен елемент мережної моделі може мати кілька точок з'єднання, званих надалі також вершинами або контактами елемента. На рис. 1 наведено приклад представлення наступних елементів: а) позиції; б) переходу, в) не термінала і г) “оболонки” макровизначення, що становить зовнішнє середовище чи оточення. Через контакти "оболонки" здійснюється взаємодія із зовнішнім світом. Контакти на рис. 1 виділені точками.

Д

елементів
для опису ієрархічної графової структури можна скористатися схемами сполучення [2, 3]. Для цього введемо структурні метазмінні, значеннями яких є змінні наступних типів: P-позиції, Т-переходи, S - нетермінали, - оболонка. Введені метаперемінні позначимо С. Математичною моделлю елемента Сj (рис. 2), що використовується для формального опису сполучення його з іншими елементами системи та зовнішнім середовищем, є пара множин [Xi(j)]1m і [Yi(j)]1t вхідних та вихідних контактів.

С

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

Розглянемо загальніший спосіб графового представлення багаторівневої мережевої моделі. Ребра у разі служать задля представлення елементарних каналів, лише констатують факт з'єднання двох вершин. З'являється можливість за допомогою контактів представляти численні міжрівневі зв'язки. Ребра, безпосередньо якими пересуваються мітки, з'являються при “розкритті” множинних зв'язків.

Визначимо мережне макровизначення, використовуючи поняття графа, доповнюючи його структурними та описовими функціями.

Орграф - це двійка (V, E), де V - кінцеве безліч вершин, EÍ VXV - безліч ребер. Нехай N - безліч елементів мережевого макровизначення; f :V® N - сюр'єктивне відображення безлічі вершин на безліч елементів. Ядро цього відображення Ker f є розбиттям множини контактів по окремих елементах.

Проведемо наступну класифікацію елементів з множини N:

Структура мережевого макровизначення є атрибутною, тобто вершин, елементів, дуг можуть бути приписані атрибути. Розглянемо два множини атрибутів, а саме: безліч атрибутів елементівАі безліч атрибутів дугВ. Позначимо:N2A- функція, яка пов'язує безліч атрибутів елементів з кожним елементом;:Е2B- функція, що пов'язує безліч атрибутів ребер з кожним рубом. З цього випливає, що мережне макровизначення складається з суто структурної частини, заданої об'єктамиN, V, E,,та семантичної компоненти, що визначається атрибутами кожного елемента та ребра.

Для подальшої імітації багаторівневу мережну модель необхідно привести до однорівневого уявлення, яке включає тільки прямі зв'язки міжтермінальними елементами (т. е. безпосередньо контактів нетермінальних елементів). Процес переходу до однорівневого уявлення назвемо генерацією або компонуванням. Цей процес природно описується графовими граматиками (ГГ), в яких передбачається механізм для генерації безлічі графів. У термінах ГГ можна описувати еквівалентні структурні перетворення[3], зокрема перехід від багаторівневої схеми сполучення до однорівневої, визначивши при цьому відповідну ГГ. Крім цього, ГГ можуть бути засобом для специфікації систем, представлених у вигляді ієрархічно пов'язаних графів. Відомо кілька видів графових граматик. Найбільш прості їх засновані на правилах заміни вузла чи дуги графа деяким подграфом.

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

Введена ГГ має такі особливості.

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

ГГ визначимо як четвірку

 - кінцева безліч міток;

 - власне підмножина , зване термінальними мітками;

P-кінцева безліч продукцій. Кожна продукція має бути задана у формі(d,D),деd-, DG, Gозначає безліч всіх графів (вірніше графових структур, визначених вище) з вузловими мітками з ;

S- спеціальний нетермінал, званий початковим.

Шлях, у якому продукція(d,D)застосовується для трансформації графаM,наступний(графMназвемо основним).

Крок 1:Знайти появу вузла з міткоюdу графіM,т. е. повинен існувати такий вузолn,щоM(n)=d.Назвемо вузолnщо породжує. Безліч вузлів, які безпосередньо пов'язані з вузлом, що породжує (точніше з його контактами), назвемо сусідами.

Крок 2:Додати до графаMграфD,ізоморфний графуD.ГрафDбуде називатися дочірнім.

Крок 3:Використовуючи деякий фіксований алгоритм, вбудувати подграфDв основний графM.В результаті вбудовування основний графМперетворюється до графа M .Розглянемо докладніше процедуру вбудовування.

ПозначимоEMB (D,M \D)- безліч ребер між дочірнім графом і графом, тобто безліч зв'язків, що з'єднують графDз оточенням:

Індекс у дужках обмежує безліч тих елементів, які належать об'єкту - індексу. У нижній частині рис.3 схематично наведено приклад вбудовування графаDу графМ. У нижній частині малюнка представлена ​​застосована до графаMфункція. Пунктирними лініями зображені зв'язки, згенерованіпри вбудовуванні.

Крок 4:Видалити вузол, що породжуєnв основному графі (видаляючи всі пов'язані з ним ребра). Видалити "оболонку" дочірнього графа (видаляючи при цьому всі контакти з інцидентними ним ребрами). У прикладі, поданому на рис. 3, видаляються ребра(x1, z1), (x2, z1), (z2, y).

Таким чином, при заміні вузлаnосновного графаMграфомDвиходить графM:

Кінцева послідовність називається висновком довжиноюm.Мова, що генерується граматикоюG -безліч графів з термінальними мітками, які можуть бути виведені з початкового графа з міткоюS, такою, щоL (G) =G\S *M>.

моделі

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

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

З кожною продукцією пов'язуються правила обчислення атрибутів. Розглянемо лише ті атрибути, які беруть участь у правилах обчислення:pr- пріоритет синтаксичного елемента;коrr- корекція пріоритету (може бути як позитивною, так і негативною );ar -тип пріоритету (0-абсолютний. 1відносний). Ці атрибути приписуються нетермінальним елементам і деяким термінальним елементам (переходам). Наслідуючи термінологію атрибутних рядкових граматик, класифікуватимемо атрибути на синтезовані та наслідувані. Для визначеної генеруючої ГГ додатково вводимо власніатрибути для нетермінальних елементів. У кожному графі нетермінал може мати різні за значенням власні атрибути. Власні атрибути у процесі генерації не змінюються. У нашому випадкурr- успадкований атрибут, акорrрrіar -власні. Нехайрr(b) -пріоритет нетерміналуbу лівій частині продукції;рr(n) - атрибути вузлаnNSNTправої частини продукції. Правила обчислення атрибутів будуть такі:

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

Описана ГГ для генерації однорівневої моделі реалізована в комплексі програм КОМПОНОВЩИК. Компонувальник може виробляти повну або неповну генерацію. Неповністю згенеровану структуру, тобто таку, в якій не всі елементи є термінальними, можна назвати сентенційною формою. Кожен граф (вірніше, мережне макровизначення) у системі зберігається у розділі бібліотеки. Тому щодо його ідентифікації можна вказати конструкцію виду: . . Подання мережевого макровизначення в алфавіті ГГ формується транслятором з мови опису моделей. Багаторівнева модель визначається за допомогою продукції. Можливе явне та неявне їхнє завдання. Для зв'язку з КОМПОНОВИКОМ використовується наступна пропозиція директивної мови (мови опису завдання), записана у формі РБНФ:

, -відповідноDD-ім'я бібліотеки та ім'я розділу, де зберігається мережне макровизначення правої частини продукції, заданої явним чином;

- Мітка нетермінала лівої частини цієї продукції;

- ім'я мітки нетерміналу, який заборонено для заміни;

=23>—максимально допустимий рівень помилок. при якому ще продовжується генерація.

Для вивантаження згенерованої структури на зовнішню пам'ять можна скористатися командою#UNLOAD

- DD-ім'я бібліотеки, в яку вивантажується структура; - Ім'я розділу бібліотеки.

На закінчення відзначимо макрозасоби, які у інших мережевих моделях. У КОМБІ-мережах для підтримки ієрархічного проектування були введеніK-переходи таK-позиції [б]. При цьомуK-перехід “обрамлений” лише переходами, а граничними елементамиK-позиції є лише позиції, Представлене вище макрозасіб є більш загальним у тому сенсі, що граничними елементами нетерміналу можуть бути як позиції, і переходи. Макро мережі описано у роботі [7].

1.Котов Ст. Е.Мережі Петрі. - М: Наука, 1984. - 157 с.

2.Бусленко Н. П.Моделування складних систем. – М.- Наука, 1978. – 399 с.

3.Бусленко В. Н.Автоматизація імітаційного моделювання складних систем. - М: Наука, 1977. - 238 с.

4. Проектування підсистем зовнішніх пристроїв з прямим доступом на основі мережевих моделей //.П. Вашкевич, В. Н. Дубінін, С. А. Зікін, Б. М. Раков. - Питання радіоелектроніки, сер. ЕВТ, 1984, вип. 13, с.78-82.

5. D. Janssens, G. Rozenberg. Graph grammars with node-label controlled rewriting and embedding. - "Lecture Notes in Computer Seience", 1983, v. 153, pp. 186-205.