Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Мережі Петрі
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
КН
Кафедра:
Кафедра ЕОМ
Інформація про роботу
Рік:
2005
Тип роботи:
Розрахункова робота
Предмет:
Паралельні та розподілені обчислення
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти та науки України
Національний університет „Львівська Політехніка”
Кафедра ЕОМ
Розрахункова робота
з предмету
"Паралельні та розподілені обчислення"
на тему
"Мережі Петрі"
м Львів – 2005
Завдання: Побудувати розширену мережу Петрі, яка оптимально, тобто з мінімальною кількістю вузлів та переходів реалізовує обчислення, задані варіантом.
1. Завдання
2
Задано цілі додатні числа n та m. Знайти найбільший спільний дільник (НСД) цих чисел, використовуючи алгоритм Евкліда.
Опис алгоритму Евкліда:
Для двох цілих додатних чисел N та M найбільший спільний дільник методом Евкліда буде знайдено наступним чином:
N=max (n, m); M=min(n, m);
Шукається остача від ділення N на М.
Якщо остача рівна "0", то за найменший спільний дільник приймається М; Інакше N=M, M= N mod M (п.2) і переходимо в пункт 2.
Приклад знаходження НСД для чисел 11 і 29:
N=29; M=11;
29 / 11 = 2 (7). 7<>0;
11 / 7 = 1 (4); 4<>0;
7 / 4 = 1 (3); 3<>0;
4 / 3 = 1 (1); 1<>0;
3 / 1 = 3 (0); 0=0 ( НСД=1;
Аналіз завдання:
Оскільки ми не знаємо кількість необхідних ітерацій для знаходження НСД для пари чисел, необхідно використати лише один блок для ділення (для знаходження остачі). Кожен раз блок для знаходження остачі від ділення двох чисел повинен ініціалізуватись заново (тобто переходити в початковий стан), інакше обчислення НСД не буде вірним (Мережа буде функціонувати невірно). Для визначення моменту знаходження НСД необхідна вершина "фініш".
2. Загальна структура мережі Петрі:
На малюнку, що зображено вище, подано загальну структуру мережі Петрі, що реалізує пошук НСД методом Евкліда. На схемі зображено лише один функціональний блок, який ділить два цілі числа (знаходить цілу частину і остачу від ділення). Інші вершини є допоміжними і не має необхідності виносити їх в окремі блоки. Опишемо алгоритм роботи побудованої мережі. Мітка старт призначена для початку роботи мережі. У вершинах А і В знаходяться числа, для яких ми шукаємо НСД (А>=B!). Після того, як ми "запустили" мережу відбувається копіювання вхідних даних у вхідні вершини блоку для ділення. Оскільки А завжди має бути більшим за В, то подати мітку "старт" на пристрій ділення можна після того, як у нас число В повністю переміститься в пристрій ділення (Оскільки А менше, то воно переміститься раніше). Паралельно з переносом числа В у пристрій для ділення, ми копіюємо його у вершину m2, оскільки існує така можливість, що число В відразу виявиться НСД (наприклад для 10 і 5). Після того, як ми поділили два числа на вихідній вершині "Finnish" блоку для ділення з’являється ознака фінішу. При появі цієї ознаки ми копіюємо результати ділення (цілу і дробову частину) у вершини m1 та m3. Якщо в m3 будуть відсутні марки, то це означає, що числа поділились без остачі, а це в свою чергу відповідає тому, що ми знайшли НСД. Як наслідок встановиться мітка у вершині m5. НСД буде міститись у вершині m2. Якщо результат ділення не 0, то це означає. що пошук НСД треба знову повторити. Тепер замість діленого використовується число, яке було дільником на попередньому проході, воно зчитується з вершини m2 (Ця вершина містить всі проміжні можливі НСД). Дільником у нас має бути остача від ділення, тому вона копіюється у відповідну вхідну вершину блоку для ділення і паралельно до вершини m2, оскільки це теж можливий НСД (ця операція слідує після того, як перемістили вміст m2 у блок ділення в якості діленого). Після цього операція повторюється. Алгоритм не характеризується великим ступнем паралельності, оскільки у нас обробляється одна пара чисел, і, до того ж, на одному блоці ділення.
3. Мережа Петрі, що реалізовує ділення двох чисел.
Робота цього пристрою базується на відніманні. Від діленого ми віднімаємо дільник. Якщо в вершині. що містить дільник ще залишились марки, то в вершину "div" ми закидаємо ще одну марку. Продовжуємо до тих пір поки ми не зможемо відняти від залишку діленого дільник. Це і буде остача від ділення. Після завершення ділення у нас з’являється марка в "Finnish". Оскільки наш пристрій для ділення використовується багато разів, його необхідно щоразу заново ініціалізувати після завершення ділення. Ініціалізація полягає в очищенні всіх вершин, які можуть містити марки після виконання операції ділення. Ініціалізація стартує автоматично після того, як у вихідних вершинах Div і Mod у нас не залишиться жодної марки (тобто після того, як ми скопіювали результати). Ініціалізація – це гасіння всіх марок у кожній вершині. Після того, як всі вершини не будуть містити марок з’явиться марка у вершині "Ready". Наш пристрій знову готовий для ділення (нормального () чисел.
Оптимізація:
Помічаємо, що обнулення при ініціалізації поділювача потребують не всі вершини. Їх обнулення робити не будемо. Крім того в алгоритмі відсутнє будь-яке застосування цілої частини від ділення. Відкинемо її як з поділювана так і з головної схеми. Тепер ініціалізація поділювана буде починатись після того, як з’явиться мітка "finnish", а вершина, що містить залишок від ділення, не буде містити марок.
Оптимізована загальна структура мережі Петрі:
Оптимізований поділювач:
Мережа
К-сть дуг
К-сть вершин
К-сть переходів
Бенчмарк для чисел 10 і 15
кроки
час виконання
неоптимізована
114
23
29
20321
0,375 (сек)
оптимізована
99
17
25
20242
0,329
Порівняння мереж:
Оптимізація даної мережі ускладнюється тим, що даний алгоритм важко розпаралелити, оскільки тут присутня залежність за даними і використовується один блок для ділення чисел.
Висновок: У ході виконання практичної роботи побудували розширену мережу Петрі, яка оптимально, тобто з мінімальною кількістю вузлів та переходів реалізовує обчислення найбільшого спільного дільника двох цілих додатних чисел. Мережа Петрі допомагає більш детально дослідити алгоритм, виявити ті його частини, які можна розпаралелити (тобто виконувати їх одночасно, бо відсутня залежність за даними).
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора