МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ національний університет “Львівська політехніКА” КАФЕДРА ЕЛЕКТРОННИХ ОБЧИСЛЮВАЛЬНИХ МАШИН Розрахункова робота з курсу “Паралельні та розподілені обчислення” на тему: “Побудова розширеної мережі Петрі” Львів-2005 Постановка та аналіз завдання: побудувати розширену мережу Петрі, яка оптимально, тобто з мінімальною кількістю вузлів та переходів реалізовує обчислення, задані варіантом. Вершини вхідних даних містять цілі невід’ємні числа i можуть з'явитися лише один раз. У мережі мають бути помічені вершини “старт”, “фініш” та “помилка”. Знак результату має встановлюватися за допомогою додаткової вершини. При необхідності, результат може знаходитися у декількох вершинах (наприклад ціла і дробові частини). Загальна мережа Петрі:
Рис.1 Загальнамережа Петрі. В Загальному випадку формула для знаходження факторіалу має вигляд: n!=n(n-1)(n-2)…1. Виходячи з цього, мережа Петрі, яка реалізовує даний вираз повинна мати 2 функціональні блоки, які будуть виконувати операції множення та відімання одиниці. Блок A-1 призначений для віднімання одиниці від вхідного операнда. Вершина Start призначена для початку виконня операції віднімання. У вершині Rezult знаходиться результат виконання операції. До вершини Input подається вхідний операнд. Вершина Finish вказує на ознаку закінчення виконання операції віднімання. Блок A mul B (my) призначений для виконання операції множення двох чисел. Вершини А та В – це вхідні дані, над якими буде виконуватись операція множення. Вершина Start вказує на початок виконання множення. Вершина Rezult буде містити результат виконання. Вершина Finish – це ознака закінчення виконання множення. Крім перелічених блоків реалізована мною мережа Петрі містить також такі вершини: START – ознака початку виконання дій. N – вхідний операнд. REZULT – містить результат роботи мережі. FINISH – ознака закінчення роботи. Progress1 – призначена для перекачування вхідного операнда у блок множення та віднімання, а також для задання старту для цих блоків. Progress2 – вершина, яка призначена для задання старту для блоку множення. TMP – зберігає тимчасовий результат блоку віднімання одиниці. Опис окремих блоків:
Рис.2 Блок множення A mul B (my) Блок множення A mul B (my) виконує операцію множення двох опернадів. Містить такі вершини: Variable A, Variable B – вхідні дані, над якими виконується операція. Start – стартує мережу до виконання. Finish – ознака закінчення множення. Process, m2, m3 – забезпечують пстійну роботу мережі. m1 – призначена для відкачування проміжних результатів для можливості наступної коректної роботи мережі.
Рис. 3 Блок виконання операції віднімання одиниці А-1 Цей блок містить такі вузли: Start – задає початок виконання мережі. InputA – вхідний операнд, від якого буде відніматись одиниця. Temp – містить проміжний результат виконання. Rezult – містить вхідний операнд – 1. Finish – ознака закінчення роботи мережі. Висновки: при виконанні розрахункової роботи я ознайомився з основними правилами роботи мереж Петрі. Мною була розроблена мережа, яка обчислює факторіл вхідного операнду. Також я побачив що мережі Петрі є ефективними для ознайомлення з принципами побудови паралельних алгоритмів. Мережі Петрі дають наочне уявлення про паралельні обчислення, проте беручи до уваги невисоку швидкодію їх роботи вони не можуть служити ефективним засобом для розробки алгоритмів з високою часовою складністю.