Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Використання мереж Петрі при моделюванні паралельних обчислень.
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Інститут комп’ютерних технологій, автоматики та метрології
Факультет:
Не вказано
Кафедра:
Не вказано
Інформація про роботу
Рік:
2008
Тип роботи:
Курсова робота
Предмет:
Моделювання паралельних обчислювальних процесів
Група:
КІ-41
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ ТА НАУКИ УКРАЇНИ
Національний університет “Львівська політехніка”
ІКТА
Курсова робота
з курсу
«Моделювання паралельних обчислень»
Тема « Використання мереж Петрі при моделюванні паралельних обчислень»
ЛЬВІВ 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 с., ил.
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора