Міністерство освіти і науки України
Відкритий міжнародний університет розвитку людини “Україна”
Івано-Франківська філія
Кафедра КНІВМЕ
Дипломна робота
на тему:
«Технологія розробки программного забезпечення мереж Петрі та вирішення проблем які виникають при їх використанні»
ЗМІСТ
ВСТУП 4
Розділ 1 6
1.1. ОБЧИСЛЮВАЛЬНІ ПРОЦЕСИ НАД ПАМЯТТЮ 6
1.2. СТРУКТУРИ КЕРУВАННЯ 14
1.3. А–СХЕМИ, А–ПРОГРАМИ 19
1.4. ПАРАЛЕЛЬНІ ОПЕРАТОРНІ СХЕМИ 24
1.5. МОДЕЛІ ПОТОКІВ ДАНИХ 28
Розділ 2 33
МЕРЕЖІ ПЕТРІ 33
2.1 ЗАГАЛЬНІ ВІДОМОСТІ ПРО МЕРЕЖІ ПЕТРІ 33
2.2 ПРИНЦИП ФУНКЦІОНУВАННЯ МЕРЕЖІ ПЕТРІ 34
2.3 ПРОБЛЕМИ РОЗВ’ЯЗНОСТІ МЕРЕЖ ПЕТРІ 38
2.4 РОЗШИРЕНІ МЕРЕЖІ ПЕТРІ 41
Розділ 3 44
3.1. ПЕРЕВІРКА МЕРЕЖІ ПЕТРІ НА ІСНУВАННЯ ТУПИКОВОЇ РОЗМІТКИ (ДЕДЛОКУ) 44
3.2. КОРИСТУВАННЯ ПРОГРАМОЮ 52
ВИСНОВКИ 60
ЛІТЕРАТУРА 61
ДОДАТОК 63
ВСТУП
В наш час все більшого поширення набула проблема паралельного обчислення. Разом з нею і виникло багато інших проблем серед яких і моделювання розподілених обчислень. При моделюванні розподілених обчислень розглядаються і класичні мережі Петрі, де і є проблема виникнення тупикової розмітки (deadlock). Дослідження цієї проблеми і зумовлює актуальність обраної теми.
Класичні мережі Петрі використовуються саме для проектування розподілених обчислень і широко використовується при розробці паралельних процесів та іншого. За допомогою класичних мереж Петрі навіть моделюються операційні системи.
При розгляданні класичних мереж Петрі багато інформації наведено в таких книгах: Алгоритмы, математическое обеспечение и архитектура многопроцессорных вычислительных систем; Воеводин В.В. Математические основы параллельных вычислений; Теория параллельного программирования: Прикладные Аспекты.
При досліджені проблеми виникнення тупикової розмітки багато інформації здобуто з наступних джерел: Элементы параллельного программирования; Параллельные вычислительные системы.
Розглянуто також розширені мережі Петрі і описані вони в наступній літературі: Разрешимость функциональной эквивалентности на подклассе схем потоков данных.
Мета роботи – дослідження класичних мереж Петрі, вивчення їх недоліків та проблем які виникають при їх використані, дослідження проблеми досяжності тупикової розмітки.
Для досягнення мети в роботі потрібно вирішити такі задачі:
вивчити принцип роботи класичних мереж Петрі;
вивчити причини виникнення проблем при їх використанні мереж Петрі;
вивчити проблему досяжності тупикової розмітки в класичних мережах Петрі.
Об'єкт дослідження: технологія розробки мереж Петрі та вирішення проблем які виникають при їх використанні.
Предмет дослідження: можливості класичних мереж Петрі, виникнення тупи кокової розмітки. Дослідження мереж Петрі на виникнення тупикової розмітки.
Практична значущість: результатом дослідження є програма яка може бути використана, як в практиці так і в начальному процесі.
Робота складається з вступу, трьох розділів та висновку. В кінці роботи наведено список використаної літератури та додатки.
У вступі розкривається актуальність обраної теми, визначено об’єкт та предмет дослідження та дається характеристика кожного розділу.
В першому розділі розглянуто базові поняття та принципи роботи паралельного обчислення .
Другий розділ повністю присвячений розгляду класичних мереж Петрі.
Третій розділ присвячено опису програмного продукту, реалізація та інструкція по використанню.
У висновках звертається увага на обґрунтування результатів дослідження, узагальнюються окремі факти та ідеї, що формувалися під час дослідження.
В додатку наведено вихідні коди розробленого програмного продукту.
Розділ 1
1.1. ОБЧИСЛЮВАЛЬНІ ПРОЦЕСИ НАД ПАМЯТТЮ
Виразом інформаційних складових в наших моделях буде множина процесів, які представляють собою послідовність включення і виключення деяких операторів. В залежності від порядку включення і виключення процеси можуть бути або послідовними або паралельними.
І так нехай задана множина М={x, y, xi, . . .} комірок пам’яті або змінних, які можуть бути з індексом, та множина F={a, b, ai, . . .} символів операторів, які там, не призводять до двозначності, будемо для скорочення називати просто операторами. Для кожного оператора визначені упорядковані множини , вхідних і вихідних змінних. Символи і будуть позначати k-ту компоненту цих множин. Припускається, що виконується умова
Таким чином, ніякі два виходи не виробляють одну і ту ж змінну. Крім того, припускається, що F включає в себе два спеціальних символа: і – для оператора вводу та о – для оператора виводу інформації.
Означення 1: описана пара множин (M, F) називається інформаційним базисом.
Можливі і інші варіанти при описанні інформаційного базиса. Наприклад іноді в якості входів і виходів оператора at зручно розглядати деякі абстрактні елементи ta та at (індекс перед а означає вхід, а після а – вихід). З кожним із таких елементів з допомогою деякого відображення співставляється деяка своя змінна.
З кожним оператор ним символом а зв’язується символ ініціалізації та символ завершення . Перший вказує на початок роботи оператора а, а другий на завершення його роботи.
Означення 2: обчислювальним процесом над інформаційним базисом (M, F) називається скінчена або нескінчена послідовність де є або , або для деякого оператора а. Початковий відрізок позначимо як і назвемо його префіксом процесу. При цьому припущені від вимагається :
Для любих k та a, якщо префікс містить п символів виключення оператора а, то він містить не менше ніж п операторів включення а. Ця аксіома виражає природну вимогу про те, що виключення оператора не може бути раніше його включення.
Для любого а, якщо процес скінчений, він містить включення і виключення оператора а. Також природна вимога: після завершення „роботи” всі процеси які були включені повинні бути завершені.
Процес або нескінчений і тоді має не більше одного входження символа о, або скінчений і тоді містить єдине входження цього символа. Помітимо, що ця умова слабша, чим вимога про вихід із обчислення через оператор виводу: останнє входження в процес не обов’язково о. Не рідко додатково потрібні іще дві умови.
Для довільного відрізка виду між символами включення повинен бути символ виключення . Цю вимогу можна назвати відсутністю авто паралельності, тобто одночасного виконання оператора а з самим собою.
Вимога інформаційної забезпеченості , та Оператор а може включитися тільки тоді, коли вироблена інформація для кожного із його входів попередніми операторами.
рис. 1. Приклад послідовної програми
Означення 3: Процес називається послідовним, якщо в ньому за кожним символом безпосередньо слідує символ .
Обчислювальні процеси зручно представляти в вигляді часових діаграм. Нехай наприклад,
Тоді процесами являються ; . Перший із них – послідовний (рис 1.), а другий паралельний (рис 2.).
рис. 2. Приклад паралельної програми
Всі виконання оператора а можна впорядкувати в часі по моментам ввімкнення, і тому далі будемо говорити про перший другий і т.д. актах оператора а або входження їх в обчислювальний процес . На них переносяться визначення входів і виходів, тобто можна говорити про входи і виходи обчислювального процесу . Наприклад, процес ( має два акта оператора b кожен із яких має входом х а виходами y, z. Перший акт реалізується між 4-им та 5-им тактом, а другий акт між 7-им та 8-им. Якщо аксіома відсутності авто паралельності 4, то вважається, що акти виключаються в порядку їх включення. Так процес має два акта оператора а: 1-й між 1-им та 5-им, 2-й між 3-ім та 7-им тактами.
Означення 4: Інформаційним графом процесу називається орієнтований граф (можливо нескінчений), з вершинами якого являються входи та виходи актів процесу , а стрілки проводяться в відповідності до наступних правил:
Стрілка може вести тільки з деякого виходу в деякий вхід.
Якщо послідовність , і при цьому для деяких j, k Outj(a)=Ink(b) і між та нема ні одного акта виключення с, такого, що , то стрілка веде із Outj(a) в Ink(b). Інших стрілок нема.
Означення 5: Інформаційні графи та ізоморфні якщо існує взаємо однозначне відображення між їх вершинами, при якому входам і виходам співставляється входи і виходи актів одно іменних операторів і які узгоджені з стрілками інформаційної залежності. Далі будемо говорити про рівність інформаційних графів з точністю до ізоморфізму.
Інформаційний граф процесу вказує шляхи передачі інформації при реалізації процесу ( над загальною пам’яттю. Інформація для деякого входу береться завжди з останнього виробляючого відповідну змінну акту. Для прикладу інформаційні графи процесів ( та ( показані на рис 3.
рис. 3. Інформаційні графи
Означення 6: Визначимо поняття терма над множиною .
Якщо , то х являється термом.
Нехай , - терми, має вигляд , при чому або . Тоді являється термом.
Множина всіх термів над позначимо через .
Означення 7: Терм –історією або скорочено t-історією входження (і в (, називається терм , рівний , якщо і=1, (і=, де ; для відповідного символа включення а , якщо попередньо визначене. Цей терм називається також терм-історією відповідного акта оператора а; , якщо визначені, , при чому , де - останнє входження в перед , яке виробляють .
Далі будемо вважати, що операторна множина F, а також інформаційний базис належать до класу LL (loss – less) [13, 14], якщо . Таким чином кожне виконання акта в базисі класу LL спричиняє за собою зміну стану пам’яті. Ця властивість являється дуже важливою в теорії паралельного програмування, в чому ми ще не раз переконаємося. Має місце наступна фундаментальна лема про зв’язок різних атрибутів процесів.
Лема 1
Для довільних процесів ( та (:
А. випливає, що , але супротивне не вірне.
Б. спричиняє, що , але супротивне не вірне.
В. випливає, що рівність терм-історії операторів виводу цих процесів, але супротивне не вірне.
Г. t-історії процесів ( та ( співпадають тоді і тільки тоді, коли .
Скажемо декілька слів про значення цієї леми.
На формальних моделях розв’язуються різні за природою задачі. Так, одна із них – перевірка не детермінованості деякої програмної або апаратної моделі: чи гарантовано те, що на одних і тих же вхідних даних при любих режимах обчислення видається однаковий результат. Друга важлива проблема – перевірка еквівалентності двох моделей: чи реалізують вони одну і ту ж функцію. Третя задача – розпаралелення програм – заключається в тому, що по мірі паралельності чи навіть послідовній програмі будується максимально паралельна, еквівалентна первинній. Не дивлячись на зовнішню відмінність, у всіх трьох випадках потрібно потурбуватися про те, щоб деякий набір процесів реалізував одну і ту ж функцію. В першому випадку це набір процесів схеми, яка перевіряється на детермінованість, в другому – сукупність процесів схем, для яких перевіряється відношення еквівалентності, в третьому – множина процесів, яка розширює процеси програми яка розпаралелюється.
Розглянемо деякі перетворення процесів, які зберігають вказані інваріанти. Спочатку приведемо фундаментальну умову із теорії паралельного програмування, яке було незалежно сформульоване Берштейном, Раселлом та Наріньяні, але в літературі його частіше називають умовою Бернштейна. Припустимо, що для операторів а та b виконується умова Бернштейна, якщо
. (1.1)
Для скороченого запису цієї умови приймемо позначення а/b, а при невиконанні його – позначення ‘a/b, якщо для деяких відрізків ( та (.
, .
Лема 1.2
Якщо процес отримується із процесу з допомогою кінцевого числа перестановок актів операторів, які задовольняють умові (1.1), то .
Розглянемо відповідне відношення еквівалентності ~: процеси ( та ( знаходяться в цьому відношенні якщо один отримується з іншого з допомогою вказаних перестановок. Виявляється, воно близьке до відношення еквівалентності по рівності історій комірок. Перед тим як показати це, введемо одне дуже важливе поняття.
Означення 8: Будемо говорити, що процес ( належить класу RF або володіє властивістю RF (repetition-free), якщо для довільного його відрізка виду між входженнями а є таке входження , де b може бути рівним а, що . Таким чином, кожне включення оператора відбувається на поновлених даних. Звідси, випливає, що довільний оператор без входів зустрічається не більше одного разу. Очевидна наступна лема.
Лема 1.3
Процес тоді і тільки тоді, коли не містить двох актів з однаковою t-історією.
Спів відношення між еквівалентностями по історіям комірок та ~ встановлює наступну лему.
Лема 1.4
А) ;
Б) .
Означення 9: Інтерпретацією І інформаційного базису (M,F) називається трійка , де ( деяка множина , яке будимо називати далі множиною значень; (0 – відображення із М в (, тобто деякий початковий стан пам’яті; - відображення, яке перетворює оператор ний символ а в перетворювач над пам’яттю. Під т розуміємо число входів, а під п число виходів оператора а.
Визначимо проміжковий стан пам’яті після виконання префікса деякого процесу . Якщо то ; а якщо і визначене, то
(1.2)
Символ показує обмеження діяльності оператора на комірці х. Таким чином, початковий стан пам’яті утворюється з допомогою інтерпретованих операторів. Якщо наступний символ процесу – включення, то стан змінюється наступним чином. На входи відповідного акта із відповідних комірок береться інформація, яка вироблена до моменту включення цього акта, а в кожну комірку х, яка належить виходу, засилається обчислювальній функції результат відповідної позиції. Стан комірки х після виконання послідовності актів при інтерпретації І позначимо через , а стан всієї пам’яті – .
Означення 10: Інтерпретація І0 називається вільною, якщо , тобто множиною значень є множина термів; , тобто при початковому стані пам’яті в комірці х міститься терм х,
,тобто використання -того оператора а до термів дає вектор із п екземплярів термів якщо останній є термом, і не визначений в супротивному випадку.
В даному випадку для інформаційного базису існує всього одна вільна інтерпретація. В випадку інших моделей, як показано нижче, існує їх може бути скінчена кількість. Вільна інтерпретація цікава тим, що її засобами встановлюється прямий зв’язок між синтаксисом та семантикою процесів, тобто правдива наступна лема.
Лема 1.5
. Доведення випливає із розгляду t-історії комірки і вмісту комірки при вільній інтерпретації.
Наслідок: . В повній мірі значимість цього наслідку буде видна при розгляді наступних моделей. Зараз же вона нам стане в нагоді доведення основного твердження цього розділу.
Теорема 1.1
.
Доведення: Твердження теореми і правда очевидне, так як вільна інтерпретація є частинним випадком М інтерпретації. Доведемо теорему в ліву сторону. Нехай при І0 в комірку х як процесу (, так і процесу ( засилають один терм t. Ясно, що на одних і тих же початкових даних суперпозиція інтерпретованих операцій t при любій інтерпретації вийде один і той же результат. Із розгляду означення стану пам’яті, видно , що при фіксованому процесі при любій інтерпретації інформація для любого акта береться із одних і тих же виходів. Виходячи з цього при любій інтерпретації формується режим переробки інформації, який задається термом t звідки випливає рівність вмісту комірок із лівої частини теореми.
Щойно доведена теорема носить назву теорема про вільну інтерпретацію. Вона показує, що в деякому смислі вільна інтерпретація являється представником всіх інтерпретацій даного інформаційного базису. Багато подальших тверджень будемо формулювати з квантом все загальності І. Це звичайний прийом теорії моделей програм і обчислень. І для того щоб їх перевірити нема необхідності перебирати всі інтерпретації. Більш того, це неможливо. Достатньо перевірити твердження по всіх вільних інтерпретаціях. В випадку „некерованих” обчислювальних процесів вона одна, в випадку інших моделей вільних інтерпретацій може бути довільне число; головне, щоб всі вони будуть описуватись досить осяйно для перевірки потрібних тверджень. Теорема 1.1 буде при цьому модифікуватися і прийматиме специфічні відтінки, але в цілому її смисл залишиться. Вона дозволяє позбутися або різко скоротити область дії квантора все загальності для інтерпретацій.
1.2. СТРУКТУРИ КЕРУВАННЯ
Вище розглянуті процеси – послідовність деяких дій, які перетворюються при задані інтерпретації в досить конкретні акти. Означення процесу не було зв’язане з яким не будь способом генерації актів або обмеженнями на їх появу в процесі. Можна вважати, що процес являється протоколом спрацювання актів після того як на деяких початкових даних відпрацювала деяка обчислювальна система, яка виконувала який не будь контроль при обчислюванні, але цей контроль ніяк не відображений в протоколі. В даному пункті буде розглянуто ця друга складова обчислення – контроль – в „чистому” вигляді, без відношення до інформаційного складу актів, керування якими буде вестись.
Най простішою структурою контролю являється орієнтований граф, в конкретних моделях зазвичай називають управляючим графом. Якщо G=(W,A), де W – множина вершин, А – множина стрілок, то в W виділяються вхідна і вихідна вершини, а кожній стрілці співставляється символ включення або виключення деякого оператора. Таким чином любому шляху із вхідної вершини в вихідну або нескінченому співставляється послідовність включень і виключень. Множину всіх послідовностей які з’являються позначимо через Pass(a). Якщо люба така послідовність являється процесом, то граф G називається правильним.
Перше питання яке виникає – це чи існує алгоритм перевірки правильності графа. Оказується, що в випадку моделі яку ми розглядаємо множина процесів які породжуються є регулярною, і відповідь проста. Такий алгоритм є і оснований на тому, що якщо граф породжує деяку послідовність (, на якій порушується люба аксіома процесу, то він породжує деякий процес ((, яка не являється процесом, обмеженої довжини. В якості границі для перевірки завжди можна взяти 2k|W|, де k – число простих циклів в графі G. Доведення цього твердження основане на скорочені ( виключенням з нього зайвих циклів.
Формування обчислювального процесу по графу G походить так, що при русі із деяких вершин ми можемо піти в довільному але тільки одному напрямку. Таким чином, контроль, який задається управляючим графом, являється не детермінованим, але не паралельним. Паралелізм досягається в наслідок розділення актів включення і виключення, і тільки. Інша більш складна модель керування отримується якщо, допустити одночасний рух по деяким стрілкам. Моделі такого типу отримали назву графових моделей паралельних програм і вивчалися найбільш інтенсивно.
Мабуть, самий популярний механізм керування – кінцевий автомат. Він відрізняється від звичайного управляючого графа тим, що при переході від вершини до вершини проходить вибір наступної вершини на основі інформації про спрацювання попереднього акта. Для вказання вибору наступної вершини приходиться вводити деяку додаткову градацію для результатів спрацювання, яка має формальний тип. Як правило, така градація задається співставленням кожному символу оператора а не одного символа оператора виключення а, а деяку множину альтернатив . При такій модифікації залишаться в силі всі поняття і результати попереднього пункту, якщо в означені процесу замінити всі слова „символ виключення а” на „деякий символ виключення аі”, а в означені інтерпретації добавити ще одну складову – множина функцій, які вибирають на основі поточного стану пам’яті деяку альтернативу. Управляючий автомат над множиною символів включення і виключення
визначається як п’ятірка , де Q – деяке, зазвичай скінчена, множина станів; q0 – початковий стан; Q( - множина кінцевих станів; ( - частинна функція переходів, . Якщо функція - визначена, то і для довільного j функція визначена. Як завжди робота автомата полягає в переході із одного стану в інший в відповідності з „вказівками” функції (. Рух починається з початкового стану і закінчується в першому кінцевому стані який зустрінеться. По скінченим автоматам є великий вибір книг.
Всі моделі які розглядатимуться нижче можна представляти і порівнювати в рамках деякої мета моделі [9]. Загальним для них є те, що вони в сукупності з інформаційним базисом (M, F) вони породжують, генерують або визначають яким не будь іншим способом множину так називаємих допустимих процесів. Множина допустимих процесів, яка виникає в наслідок дії керуючого процесу 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 Інтерпретована А-схема називається А-програмою і працює наступним чином.
В початковий момент часу перевіряється значення всіх спускових функцій на початковому стані пам’яттю Y, M і можуть включитися ті оператори а для яких =1.
Любий включив шийся оператор а працює на протязі довільного проміжку часу і в момент включення змінює стан інформаційної пам’яті М в відповідності з інтерпретацією І. Після цього спрацьовує оператор керування на тому стані, яке отрималось після моменту включення оператора а. Його спрацювання займає нульове значення часу. Таким чином моменти включення а моменти включення і виключення співпадають, але потребується щоб для довільних двох актів операторів a, b не співпадали їх активні моменти. Ця умова дозволяє повністю впорядкувати всі оператори включень і виключень модулів і розглядати їх як процеси які визначені в пункті 1.
В довільний неактивний момент часу деякі модулі знаходяться в активному стані, деякі – в неактивному. Тоді перевіряються спускові модулі всіх неактивних модулів і любий із модулів, у якого спускова функція рівна 1, може ввімкнутися і працювати довільний скінчений проміжок часу. Ввімкнення в кожний момент часу дозволяється тільки одному модулю із-за сформульованої вище вимоги не спів падання моментів включення. Дозвіл на включення зберігається до тих пір поки не пройшло вимкнення деякого акта. На протязі цього часу стан пам’яті не змінюється, і пере обчислення спускових функцій приведе до того самого результату.
Якщо представити, що включають тільки змінні керування пам’яттю, то можна розглядати інтерпретацію лише одної керуючої структури, не привертаючи інтерпретацію пам’яті М в операторів.
Особливо складним для А-схеми являється питання детермінованості та еквівалентності. Справа в тому, що модулі працюють абсолютно автономно, асинхронно, без зв’язку з якою несуть послідовною структурою, як це було, наприклад, з допомогою автомату. Тому важко прослідкувати потенційно можливі послідовності актів та інформаційні зв’язки між ними. Але для розпізнавання властивості не детермінованості по інформаційному графу можна дати одну просту умову.
Лема 3.1
Якщо
(3.1)
то схема S не є детермінованою по інформаційному графу.
Доведення: достатньо очевидно: в ситуації яку опису формула (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. МОДЕЛІ ПОТОКІВ ДАНИХ
Концепція потоків даних основана на тому, що послідовність обчислень визначається наступними даними: оператор може виконуватись, як тільки обчислені потрібні для нього операнди, тобто допускається експліцитна залежність між операторами по даних. Оскільки доступність обчислених операндів дозволяє одночасне виконання кількох операторів, паралельність дій являється внутрішньою властивістю схем потоків даних.
Одна із перших моделей, яка неявно використовувала принцип потоку даних , - це модель Карпа та Міллера [13]. дещо пізніше Родрігес ввів поняття „програмних графів” [11] які лягли в основу потоків даних Деніса-Фоссіна [11]. З останнім тісно пов’язані моделв Берса та Косинського; дещо відмінна модель представлена Адамсом [17] який істотно використовував поняття черги FIFO.
На схемах Карпа – Міллера були досліджені такі властивості паралельних обчислень, як комутативність, стійкість, результативність, безповоротність, однозначність та детермінованість. Основні результати можна звести в наступні теореми.
Для схем Карпа – Міллера розв’язно:
Чи являється безповоротною схема з скінченим числом керуючих станів.
Чи являється обмеженою без повторна схема з кінцевим управлінням.
Чи виконується довільний оператор в без повторній схемі з кінцевим управлінням скінчене число разів при любому обчислені.
Стійка, комутативна, без повторна, і результуюча схема з кінцевим керуванням є