WWW.REFERATCENTRAL.ORG.UA - Я ТУТ НАВЧАЮСЬ

... відкритий, безкоштовний архів рефератів, курсових, дипломних робіт

ГоловнаІнформатика, Компютерні науки → Технологія розробки мереж Петрі та вирішення проблем які виникають при їх використанні - Дипломна робота

Технологія розробки мереж Петрі та вирішення проблем які виникають при їх використанні - Дипломна робота

яким не будь іншим способом множину так називаємих допустимих процесів. Множина допустимих процесів, яка виникає в наслідок дії керуючого процесу U позначимо через Proc (U), множина префіксів цих процесів - через Pref (U). В тих випадках, коли структура керування зв'язана з інтерпретацією та множина породжуємих процесів при різних І різне, для нього вводиться позначення Proc (U, I). Множина Proc (U) та Proc (U, I) зв'язані природнимспіввідношенням: . Користуючись цими позначеннями вже можна сформулювати основні проблеми для структур керування.
1. Проблема детермінованості U. Нехай на множині обчислювальних процесів задане деяке відношення еквівалентності ~, наприклад:
а) еквівалентне тоді і тільки тоді, коли = ;
б) - еквівалентність по історіям комірок;
в) - еквівалентність по інформаційному графу;
г) - еквівалентність по t-історії;
д) - еквівалентність по кінцевим станам пам'яті;
е) - функціональна еквівалентність. Потрібно перевірити виконання формул:
А. .
Б. .
2. Проблема еквівалентності структурU та U (U~U ?):
А. .
Б. .
Видно, що проблема детермінованості може розглядатися як частинний випадок проблеми еквівалентності: схема являється детермінованою, якщо вона еквівалентна сама собі.
3. Проблема обчислюваності для U та U (U >U?):
А. .
Б. .
4. Проблема максимального (найбільшого) розпаралелення. Перетворити U в U , так щоб: 1) U ~ U; 2) U - максимальна (найбільша) по відношенню > в класі всіх структур {U : U ~ U}. Якщо не мати на увазі тривіальну еквівалентність а), яка властива тільки послідовним структурам керування, то можна сказати наступне. В перших трьох проблемах присутні дві постановки А та Б, при чому друга більш "тонка" оскільки враховує інтерпретацію. Відповідне відношення називається інтерпретаційним, і не важко помітити, що виконання Б завжди тягне за собою виконання А. Проблеми в формулюванні Б стають часто нерозв'язними [12]. Четверту проблему також можна сформулювати використовуючи відношення ~, > типу А або Б. В роботі [5] показано, що в другому випадку для достатньо нетривіальних моделей вона теж нерозв'язна. Розв'язність буде мати місце або при деякому спрощені відношень ~ та >, або при переході до більш вузьким класам моделей.
Враховуючи нерозв'язність багатьох проблем в загальному випадку цікавими стають достатні умови для виконання тої чи іншої властивості. Для проблеми детермінованості найбільш загальні результати в цьому відношенні отримані в роботі [15].
Означення 11. Діаграмою назвемо трійку (Q, , ), де Q - деяка множина станів; - бінарне відношення на ньому; q q означає наявність переходу із стану q в стан q ; - деякий алфавіт, символи якого приписані переходам.
Будемо писати , якщо символ приписаний стрілці, яка веде із q в q . Позначення , де - послідовність символів із , приймемо для факту існування шляху із q в q по стрілкам з символами ; а буде означати досяжність вершини q із вершини q по будь якому шляху; позначення прийнято для скорочення формули .
Діаграма (Q, , ) має властивості:
а) (автоматна) детермінованість, якщо
;
б) комутативність, якщо
;
в) стійкості, якщо
;
г) Черча - Россера, якщо
.
Із перелічених властивостей перші три мають локальний характер і взагалом піддаються ефективній перевірці, в той час як четверте для кожної трійки станів q, q1, q2 потребує глобального аналізу діаграм.
В роботі [15] приведено використання даних властивостей і сформульована наступна теорема.
Теорема 2.1
Виконання умов а), б), та в) в сукупності тягне за собою виконання умови г). Таким чином теорема дає достатні умови локального типу для забезпечення виконання глобальної умови. Вона цікава в паралельному програмуванні в багатьох відношеннях.
1.3. А-СХЕМИ, А-ПРОГРАМИ
Розглянемо одну із найбільш представницьких моделей, яка розроблена в колишньому радянському союзі: асинхронні схеми (А-схеми), та якщо розглядати їх разом з інтерпретацією, асинхронні програми (А-програми) [1, 7, 8, 9]. Різні означення А-схеми в різних роботах мають деяке відхилення одне від одного.
Означення 12 Будемо говорити, що задана А-схема, якщо в доповнені до пам'яті M і множині F задані: - деяка множина змінних, яку називають керуюча пам'яттю; -множина предикатних символів, які називаються символами спускових функцій. З кожним зв'язано множину ; - множина символів управляючих функцій. З кожним зв'язані .
Означення 13 Інтерпретована А-схема називається А-програмою і працює наступним чином.
1. В початковий момент часу перевіряється значення всіх спускових функцій на початковому стані пам'яттю Y, M і можуть включитися ті оператори а для яких =1.
2. Любий включив шийся оператор а працює на протязі довільного проміжку часу і в момент включення змінює стан інформаційної пам'яті М в відповідності з інтерпретацією І. Після цього спрацьовує оператор керування на тому стані, яке отрималось після моменту включення оператора а. Його спрацювання займає нульове значення часу. Таким чином моменти включення а моменти включення і виключення співпадають, але потребується щоб для довільних двох актів операторів a, b не співпадали їх активні моменти. Ця умова дозволяє повністю впорядкувати всі оператори включень і виключень модулів і розглядати їх як процеси які визначені в пункті 1.
3. В довільний неактивний момент часу деякі модулі знаходяться в активному стані, деякі - в неактивному. Тоді перевіряються спускові модулі всіх неактивних модулів і любий із модулів, у якого спускова функція рівна 1, може ввімкнутися і працювати довільний скінчений проміжок часу. Ввімкнення в кожний момент часу дозволяється тільки одному модулю із-за сформульованої вище вимоги не спів падання моментів включення. Дозвіл на включення зберігається до тих пір поки не пройшло вимкнення деякого акта. На протязі цього часу стан пам'яті не змінюється, і пере обчислення спускових функцій приведе до того самого результату.
Якщо представити, що включають тільки змінні керування пам'яттю, то можна розглядати інтерпретацію лише одної керуючої структури, не привертаючи інтерпретацію пам'яті М в операторів.
Особливо складним для А-схеми являється питання детермінованості та еквівалентності. Справа в тому, що модулі працюють абсолютно автономно, асинхронно, без зв'язку з якою несуть послідовною структурою, як це було, наприклад, з допомогою автомату. Тому важко прослідкувати потенційно можливі послідовності актів та інформаційні зв'язки між ними. Але для розпізнавання властивості не детермінованості по інформаційному графу можна дати одну просту умову.
Лема 3.1
Якщо
(3.1)
то схема S не є детермінованою по інформаційному графу.
Доведення: достатньо очевидно: в
Loading...

 
 

Цікаве