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

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

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

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

Перший із них - послідовний (рис 1.), а другий паралельний (рис 2.).
рис. 2. Приклад паралельної програми
Всі виконанняоператора а можна впорядкувати в часі по моментам ввімкнення, і тому далі будемо говорити про перший другий і т.д. актах оператора а або входження їх в обчислювальний процес . На них переносяться визначення входів і виходів, тобто можна говорити про входи і виходи обчислювального процесу . Наприклад, процес має два акта оператора b кожен із яких має входом х а виходами y, z. Перший акт реалізується між 4-им та 5-им тактом, а другий акт між 7-им та 8-им. Якщо аксіома відсутності авто паралельності 4, то вважається, що акти виключаються в порядку їх включення. Так процес має два акта оператора а: 1-й між 1-им та 5-им, 2-й між 3-ім та 7-им тактами.
Означення 4: Інформаційним графом процесу називається орієнтований граф (можливо нескінчений), з вершинами якого являються входи та виходи актів процесу , а стрілки проводяться в відповідності до наступних правил:
1. Стрілка може вести тільки з деякого виходу в деякий вхід.
2. Якщо послідовність , і при цьому для деяких j, k Outj(a)=Ink(b) і між та нема ні одного акта виключення с, такого, що , то стрілка веде із Outj(a) в Ink(b). Інших стрілок нема.
Означення 5: Інформаційні графи та ізоморфні якщо існує взаємо однозначне відображення між їх вершинами, при якому входам і виходам співставляється входи і виходи актів одно іменних операторів і які узгоджені з стрілками інформаційної залежності. Далі будемо говорити про рівність інформаційних графів з точністю до ізоморфізму.
Інформаційний граф процесу вказує шляхи передачі інформації при реалізації процесу над загальною пам'яттю. Інформація для деякого входу береться завжди з останнього виробляючого відповідну змінну акту. Для прикладу інформаційні графи процесів та показані на рис 3.
рис. 3. Інформаційні графи
Означення 6: Визначимо поняття терма над множиною .
1. Якщо , то х являється термом.
2. Нехай , - терми, має вигляд , при чому або . Тоді являється термом.
Множина всіх термів над позначимо через .
Означення 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)
Символ показує обмеження діяльності оператора на комірці х. Таким чином, початковий стан пам'яті утворюється з допомогою інтерпретованих операторів. Якщо наступний символ процесу - включення, то стан змінюється наступним чином. На входи відповідного акта із відповідних комірок береться інформація, яка вироблена до моменту включення цього акта, а в кожну комірку х, яка належить виходу, засилається обчислювальній функції результат
Loading...

 
 

Цікаве