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

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

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

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

ситуації яку опису формула (3.1), префікс може бути продовжений двома способами та , при цьому, так як aта b конкурують над пам'яттю, зв'язки які будуть сформовані будуть різними, що потягне за собою різницю в інформаційних графах.
Для перевірки властивості обчислюваності можна дати наступну достатню умову.
Лема 3.2
Якщо схеми S та S відрізняються лише спусковими функціями та і виконується умова , то S >S, де відношення розуміється в інтерпретаційному смислі.
Стандартні схеми можуть моделювати широкий клас програм, але більш всьоговони пристосовані для представлення алголоподібних конструкцій. Нехай, наприклад задана наступна програма, яка обчислює вираз sin(x)/y2 і виводить повідомлення про нерозв'язність при y=0:
i: введення (x, y);
a: x=sin(x);
b: y=y 2;
c: якщо y=0 то на m1, інакше на m2;
m1: вивід ("результат невизначений, так як y=0");
d: на о;
m2: y=x/y;
o: вивід(y);
Блок схема цієї програми показана на рис. 4, а відповідна стандартна схема на рис. 5 остання відмінна від блок-схеми тим, що всі її оператори не інтепритовані, показані тільки вхідні і вихідні змінні і передача керування.
рис. 4. Блок-схема програми
рис. 5. Стандартна схема
рис. 6. Схема передачі керуввання
Ця інформація використовується при алгоритмі перетворення стандартних схем в А-схеми, який вирішує четверту задачу - задачу розпаралелюваня, яка сформульована в другому пункті. При цьому в якості відношення еквівалентності використовується еквівалентність по інформаційному графу.
1.4. ПАРАЛЕЛЬНІ ОПЕРАТОРНІ СХЕМИ
Паралельні операторні схеми являються мабуть самою розгалуженою і найбільш дослідженою моделлю паралельних програм. В одній із перших робіт [13], в якій вони були запропоновані, розглядаються питання, зв'язані з детермінованістю та еквівалентністю. В роботі [14], вивчається проблема обчислювальності, а в [4, 6, 10]- проблема максимального розпаралелення. Результати щодо нерозв'язних проблем отримані в [3, 5, 12].
Нехай задано інформаційний базис (M, F) в тій модифікації, в якій він був визначений в другому пункті, тобто, що кожному операторному символу а співставлений не один а ціла множина символів виключення а. Будемо говорити, що над базисом (M, F) задана операторна схема S, якщо заданий автомат так, як він був визначений в пункті другому. Приклад операторної схеми зображено на рис. 7. Для цієї схеми
При заданій інтерпретації схема S породжує множину обчислюючи процесів Comp(S, I), кожний із яких перетворює поточний стан пам'яті в відповідністю з функціями . Множина префіксів цих процесів в відповідністю з пунктом другим позначимо як Pref(S, I).
рис. 7. Приклад операторної схеми
Більш точно, в довільний момент часу робота схеми характеризується вектор-станом, який має три компоненти: стан пам'яті , стан управляючого автомата q та сукупність наборів аргументів які обробляються для кожного оператора та (а) позначає чергу оператора а.
В початковий момент вектор-стан представляє собою набір , де співставляє кожному оператору порожню послідовність. Формуючий процес, або правильніше кажучи префікс процесу, являється порожньою множиною символів включення і виключення ?.
Означення 14 Нехай задана схема S=(M, F, A).
Послідовність назвемо шляхом в схемі S якщо існує послідовність станів , нескінчена або закінчується кінцевим станом, така, що
Означення 15 Схема називається вільною (free), якщо для довільного шляху існує інтерпретація І, така, що .
Таким чином схема вільна, якщо довільна послідовність переходів структури керування може бути реалізована при деякій інтерпретації. Далі клас всіх вільних схем будемо позначати через F.
Будемо говорити, що схема S буде належати до класу RF, якщо для любої інтерпретації І любий процес володіє властивістю RF.
Лема 4.1
. Таким чином, єдиною причиною відсутності свободи в схемі являється порушення сформульованої вище властивості.
Не важко помітити, що в найбільш типових випадках істинне і обернене включення, а саме: якщо і схема вільна, то вона належить класу RF.
Теорема 4.1
Існує алгоритм розпізнавання належності довільної лічильникової схеми класуRF.
Доведення: зводиться до проблеми досяжності для систем векторного додавання, апарат який буде використовуватися нами при находженні алгоритму розпізнавання обмеженості мереж Петрі (пункт 6). Будемо говорити, що схема S належить класу або задовольняє властивості LL, якщо базис (M, F) належить цьому класу.
Теорема 4.2
Для детермінованих схем класу RF , які задають реалізаціюз скінченим числом станів, дозволена властивість "бути максимально паралельним".
В роботі [14] вивчається також питання про ефективність побудови по заданій схемі еквівалентній їй максимально паралельною. Виявляється, що зазвичай процедура розпаралелювання виводить за межі класу схем, для яких вона визначена. Наприклад, для схеми яка задається кінцевою реалізацією (рис. 8), не існує еквівалентної максимально паралельної схеми з кінцевою реалізацією, але для неї існує реалізація в вигляді лічильної схеми.
рис. 8. Схема для якої не існує еквівалентної максимально паралельної схеми з кінцевою реалізацією
Означення 16 Обчислювальний процес визначається як послідовність актів операторів , де акт це трійка . Тут , де - змінна х з індексом k; . Акт виражає ввімкнення оператора а, який спрацював на входах із комірок , який заслав результат обчислень в комірки і видавшого альтернативу . Моменти включення операторів в обчислювальному процесі не відображені.
Означення 18 Процес називається правильним якщо, , тобто засилання проходить в доволі зазначеним історією комірки з індексом , де - номер терма при деякій однозначності ефективній нумерації. Таким чином кожен обчислений результат засилається в свої індивідуальні комірки.
Теорема 4.3
Існує алгоритм, який співставляє кожній детермінованій схемі S деякого класу Ф детерміновану не збиткову схему S еквівалентну S і максимально паралельну в класі тоді і тільки тоді коли функція Lah - ефективна. При цьому алгоритм розпаралелення визначається по функції Lah конструктивно.
Із теореми 4.3 отримується ряд наслідків два із яких сформульовані нище.
Наслідок 1. Для класу стандартних схем не існує алгоритму максимального розпаралелення.
Наслідок 2. для класу кінцевих вільних схем. Келлера існує алгоритм максимального розпаралелення.
1.5. МОДЕЛІ ПОТОКІВ ДАНИХ
Концепція потоків даних основана на тому, що послідовність обчислень визначається наступними даними: оператор може виконуватись, як тільки обчислені потрібні для нього операнди, тобто допускається експліцитна залежність між операторами по даних. Оскільки доступність обчислених операндів дозволяє одночасне

 
 

Цікаве

Загрузка...