Вправи і завдання до теми №3

1. Яка різниця між простими і розширеними мережами Петрі?

2. Запропонуйте просту мережу Петрі для синхронізації трьох паралельних процесів.

3. Побудуйте розширену мережу Петрі, котра виконує таке обчислення:

4. Побудуйте розширену мережу Петрі, котра виконує операції "розділити":

.

Вершини для X, Y та Z містять невід’ємні числа i можуть з'являтися лише один раз. У розширеній мережі Петрі мають бути помічені вершини "старт", "готово", "помилка". В разі спроби "розділити на нуль" повинні маркуватись вершини "готово" та "помилка".

5. Побудуйте розширену мережу Петрі, котра виконує такі обчислення:

Вершини дляX, Y, Z містять невід’ємні числа i можуть з'явитися лише один раз. У мережі мають бути помічені вершини "старт", "готово" та "помилка". У випадку, якщо Y=0, мають маркуватися вершини "готово", "помилка".

6. Побудуйте розширену мережу Петрі для віднімання цілих чисел. Знак числа має встановлюватися за допомогою додаткової вершини.

 

Тема 4: Розробка паралельного алгоритму

Питання:

Паралелізм даних

Паралелізм задач

Етапи розробки паралельного алгоритму

Вправи і завдання до теми №4

Найрозповсюдженішим підходом до розпаралелення обчислень і обробки даних є підхід, що базується на моделях паралелізму даних і паралелізму задач. В основі кожного підходу лежить розповсюдження обчислювальної роботи між доступними користувачу процесорами паралельного комп’ютера. Причому виникають проблеми забезпечення рівномірного завантаження процесорів і ефективної організації обміну інформації між ними.

 

Паралелізм даних

Паралелізм даних базується на застосуванні однієї операції до кількох елементів масиву даних і може використовуватися при векторній і паралельній обробці.

Основними ознаками підходу є:

- обробкою даних керує одна програма;

- простір є глобальним (для програміста є одна єдина пам’ять, а деталі структури даних доступні до пам’яті і міжпроцесорного обміну для програміста скриті);

- слабка синхронізація обчислень на паралельних процесорах (кожен процесор виконує один той же фрагмент програми, але нема гарантії, що в даний момент часу на всіх процесорах виконується одна і таж машинна програма);

- паралельні операції над елементами масиву виконується на всіх допустимих даній програмі процесорах.

Базовими операціями для даної моделі паралелізму є: операції керування даними, операції над масивами та їх фрагментами, умовні операції, операції приведення, зсуву, сканування, пересилання даних.

Для програмування в моделі паралелізму даних використовуються спеціалізовані мови програмування, здебільшого різновидності мови FORTRAN. А сам програміст – слабо впливає на процес і результати роботи

Паралелізм задач

Метод передбачає розбиття задачі на кілька відносно самостійних підзадач. Найефективніше дана модель реалізовується на MIMD структурі, де кожен процесор виконує свою програму (FORTRAN чи С). Оскільки в даному випадку програмісту самому необхідно контролювати як розподіл даних між процесорами і різними під задачами так і організацію обміну даними між ними, то підхід є більш трудоємкісним від попереднього.

При паралелізмі задач виникають певні проблеми:

- підвищена трудоємність розробки і відлагодження програм;

- на програміста покладається вся відповідальність за збалансоване завантаження програм;

- програмісту необхідно мінімізувати обмін даними між процесорами.

- підвищена небезпека виникнення тупикових ситуацій.

Проте забезпечується висока гнучкість і свобода програмісту у виборі напрямку і особливостей організації паралельної роботи. Крім того, для даної моделі є розроблений великий клас спеціалізованих бібліотек: MPI (Message Passing Interface), PVM (Parallel Virtual Machines).