Міністерство освіти та науки України
Національний університет „Львівська Політехніка”
Кафедра ЕОМ
Розрахункова робота
з предмету
"Паралельні та розподілені обчислення"
на тему
"Мережі Петрі"
м Львів – 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". Оскільк...
