МІНІСТЕРСТВО ОСВІТИ ТА НАУКИ УКРАЇНИ Національний університет “Львівська політехніка” ІКТА
Курсова робота з курсу «Моделювання паралельних обчислень» Тема « Використання мереж Петрі при моделюванні паралельних обчислень» ЛЬВІВ 2008 ЗМІСТ 1. Теоретичні відомості 3 2. Постановка та аналіз завдання 5 3. Загальна структура мережі Петрі на рівні функціональних блоків 7 4. Мережі Петрі, що реалізовують всі функціональні блоки з розгорнутим поясненням їх роботи 12 5. Результати тестування мережі 16 Висновок 17 Список використаної літератури 18 Теоретичні відомості Мережі Петрі призначені для представлення координації асинхронних подій і застосовуються для описування взаємовідносин між паралельними процесами та їх синхронізацією. Мережа Петрі – це орієнтований, дводольний граф з мітками (марками). Це визначення треба розуміти так (рис.1.1):
Кожна мережа Петрі є графом з двома різними групами вершин: вузли та переходи. Між вузлами та переходами можуть міститися орієнтовані ребра (дуги), але два вузли або два переходи не можуть з’єднуватися ребрами. Між кожною парою вузол/перехід може існувати максимально одне ребро від вузла до переходу (ребро входу) i максимально одне ребро від переходу до вузла (ребро виходу). Вузли можуть бути вільними або зайнятими міткою (маркованими); переходи не можуть бути маркованими. Вузли, що є стартовими пунктами одного ребра до одного переходу t, називаються далі вхідними вузлами переходу t. Вузли, що є кінцевими пунктами ребра від переходу t називаються вихідними вузлами переходу t. На рис.1.2 показано просту мережу Петрі, що має один перехід, три ребра i три вузли, два з яких марковані i один не маркований. Кожен вузол зв’язаний з переходом за допомогою одного ребра.

 За допомогою мереж Петрі можна моделювати такі якості як: асинхронність, конфліктнісь, паралелізм. Основні методи дослідження мереж Петрі: Дерево досягальності, Графічний, Аналітичний, За допомогою еквівалентних сумуючись. Взагалі, мережі Петрі досліджують на такі властивосі: Безпечність — досліджує виконання умови що кількість «фішок» в позиції не перевищує 1; Обмеженість — досліджує виконання умови що кількість «фішок» в позиції не перевищує заданого числа, Зберігальність — досліджує виконання умови що кількість «фішок» в мережі не змінюється, Оберненість — для довільного досяжного стану досліджується існування послідовності виконань переходів яка повертає мережу в початковий стан), Активність переходів — досліджує можливість виконання певних переходів та наявність тупиків — станів у яких переходи не дозволені та для яких неможливо досягти стану в якому ці переходи дозволені, Досяжність маркування — досліджує існування послідовності виконань переходів при якій можна досягнути задане маркування, Покриття — досліджує існування послідовності виконань переходів при якій можна досягнути маркування що покриває (є більшим) за задане маркування. 2. Постановка та аналіз завдання Побудувати мережу Петрі, яка обраховує наступний вираз: Задано цілі додатні числа
. Знайти :
якщо
– комплексне число, [a/b]– ціла частина від ділення. Вершини вхідних даних містять цілі невід’ємні числа i можуть з’явитися лише один раз. У мережі мають бути помічені вершини “старт”, “фініш” та “помилка”. Проаналізувавши вираз можна побачити, що в виразі присутні такі операції: множення двох чисел, піднесення чисел до степеня, додавання двох чисел, ділення, віднімання. Всі ці операції можна представити окремими блоками. Блоки множення двох чисел будуть також використовуватись у блоці піднесення до степеня. Проаналізувавши вираз можна визначити спрощений його варіант:
Визначимо дійсну та уявну частини: Re=
Im=
Також можна відзначити частини виразу, які можливо опрацювати паралельно: Блок CountRe обчислює
На початку роботи виконується розмноження вхідних даних U1,U2 і V на блоки U1^2, U2^2 та V^2 свою роботу ці блоки розпочинають по завершенню переносу вхідних даних і працюють паралельно. По закінченні роботи цих блоків розпочинають роботу блоки А+В_1, U2^3, 3U1*U2^2. Результати роботи блоку А+В_1 накопичуються в змінній m2. Результати роботи блоків U1^3, U2^3, 3U1*U2^2 подаються на вхід блоку А-В_3. Результати роботи блоку А-В_3 подаються на вхід блоку ділення вхід діленого, на вхід дільника цього ж блоку подається результат роботи блоку V^2, по закінченні роботи блоку XdY_1 результати, залежно від знаку на виході блоку А-В_3 додаються до змінної m3 чи m2. Значення змінної m2 подається на вхід А блоку А-В_2 і значення змінної m3 на вхід В блоку А-В_2. Блок CountIm обчислює
На початку роботи виконується розмноження вхідних даних U1,U2 і V на блоки V^2 та U1^2, свою роботу ці блоки розпочинають по завершенню переносу вхідних даних і працюють паралельно. По закінченні роботи блоку U1^2 розпочинає роботу блок AmulB_1 результати роботи якого подаються на вхід діленого блоку XdY_1, на вхід дільника цього ж блоку поступає результат роботи блоку V^2. 4. Мережі Петрі, що реалізовують всі функціональні блоки з розгорнутим поясненням їх роботи Модуль А * В
Під час кожного проходу X зменшується на одиницю і Y покроково додається до з Z. У вузлі "пам'ять" копіюється початкова величина Y, і в кінці операції через перехід u на Y робиться нова копія, щоб Y можна було використати в наступних розрахунках. Новий обчислювальний цикл починається, якщо "пам'ять" дорівнює нулю; потім перехід знову активізується через дугу заперечення. Цикли, в яких величина Y додається до Z, виконуються доти, поки X не буде дорівнювати нулю, тобто добуток X*Y буде додано до Z. Модуль А + В
Після перемикання стартового переходу s. маркується середній вузол мережі Петрі. Крок за кроком, перемикаючи перехід t, одне маркування береться з вузла Y (вхід) і одночасно вводиться у вузол Z (вихід). Середній вузол залишається при цьому маркованим, бо він містить у собі як вихідну, так і вхідну дуги (1-1+1=1). Одначе цей вузол не є зайвим, бо він дбає про те, щоб операція складання відбувалась як результуюча після розблокування стартового вузла. В кінці операції, коли Y=0, сума з'являється у вузлі Z і перехід t більше не активізується. Для завершення операції призначений перехід й, що тепер активізований; якщо він перемикається, то марка із середнього вузла виводиться і генерується марка у вузлі готовності, що сигналізує про закінчення обчислення. Модуль А - В
Токен з вершини Старт активізує перехід Т10 і перемішається у вершину Process, яка через перехід забезпечує роботу мережі. При наявності токенів у вершинах А та В активізувати перехід Т13 і працює доти, доки у якийсь з вершин (а чи В) не закінчаться токени. Якщо токени закінчились у вершині В то токени, що залишились у вершині А переносяться у вершину Absolute і роботі блоку завершується. У випадку коли ж токени закінчуються у вершині А, то токени з вершини В переносяться у вершину Absolytе і разом з тим заноситься токен у вершину Sign і робота мережі завершується. Модуль А/В
В мережі присутня вершина Start, яка ініціалізує процес обчислення. Вона пов’язана через перехід р1 з вершиною Process, яка забезпечує постійну роботу мережі. У вершинах X та Y повинні знаходитися значення відповідних змінних. Якщо у вершині Yнемає жодної марки і подано сигнал Start, то через перехід p_er з’являється ознака у вершині Error, що свідчить про спробу поділити на нуль. Лише за умови наявності марок у вершині Y спрацює перехід р1, який розпочне роботу мережі. Перехід р4 здійснює віднімання (X-Y), поки у вершині Х або Y не залишиться жодної марки. Якщо першим «вичерпався» Y, то Z1 міститиме копію Y, а вершина v3 – ознаку того, що відбулося одне повне віднімання. Далі значення з Z1 перепишеться через перехід р7 у вхідну вершину Y, після чого значення Z збільшиться на одиницю. Далі весь процес почнеться спочатку, і буде тривати, поки не вичерпається значення діленого -X. Якщо у вершині X не залишилося марок, то у вершині Z1, залишиться остача від ділення. Таким чином , вершина Z буде містити цілу частину ділення X/Y, а вершина Z1 – остачу. Ознака готовості результату –Finish, сформується коли зникнуть всі марки у вершині X. Вона також, заблокує всі подальші обчислення через перехід р2. 5. Результати тестування мережі №п/п U1 U2 V Re Sign (Re) Im Час виконання  1 0 0 0 0 0 0 Один перехід  2 1 1 1 27 1 36 1-2 хвилини  3 0 1 1 9 1 9 1-2 хвилини  4 1 0 5 2 0 9 3-4 хвилини  5 5 5 5 132 1 9 1-2години  6 35 25 15 1507 1 3686 9-10 годин  7 10 5 8 25 0 219 2-3 години   Слід зауважити, що час виконання може відрізнятися в залежності від потужності ПК на якому тестується мережа (в основному від тактової частоти процесора). Дана мережа тестувалась на ПК з процесором Intel Celeron з тактовою частотою 1,9 ГГц та об’ємом оперативної пам’яті 1ГБ. ВИСНОВОК Паралельне програмування набуває все більшого поширення і розвитку в світі з появою потужних супер ЕОМ та комп’ютерних комплексів які складаються з кількох комп’ютерів які об’єднані в мережу. З цих передумов виникає проблема моделювання розподілених обчислень, для чого можливе використання мереж Петрі. В даній курсовій роботі досліджено принципи роботи мережі Петрі, наведено приклад її застосування для моделювання паралельного обчислення математичного виразу. Для досягнення мети в роботі вирішено такі задачі: досліджено і охарактеризовано роботу мереж Петрі; розроблено та описано основні блоки арифметичних операцій; побудовано мережу Петрі для обчислення заданого виразу; досліджено часові характеристики роботи моделі. СПИСОК ВИКОРИСТАНОЇ ЛІТЕРАТУРИ 1. «Організація паралельних обчислень» Навчальний посібник з дисципліни “Паралельні та розподілені обчислення” для студентів базового напрямку 6.0915 "Комп'ютерна інженерія" / Укладачі: Є. Ваврук, О. Лашко – Львів: Національний університет “Львівська політехніка”, 2007. 2. www.wikipedia.com 3. Питерсон Дж. Теория сетей Петри і моделирования систем: Пер. с англ. -М.: Мир, 1984. -264 с., ил.