Page 28 - 4868

Ошибка! Стиль не определен. 26

2) розподіл за даними – розбиття набору даних на окремі частини, які
можна опрацьовувати паралельно.
Розподіл за задачами ділить алгоритм на функціонально незалежні
частини, але бувають випадки, коли одні задачі залежать від інших задач,
наприклад, якщо вхідні (початкові) дані задачі В залежать від вихідних
(кінцевих) даних задачі А, то задача В залежить від задачі А;
Для опису зв’язків між задачами використовуються відповідні графи
залежностей (рис.1.7, а, б).

Рисунок 1.7 – Приклади графів залежностей по задачах

Для більш наочного прикладу розробимо граф залежності по задачах для
випічки печива (рис.1.8).

Розігрів печі Купівля продуктів

Змішування інгредієнтів

Випікання

Рисунок 1.8 – Граф залежності по задачах для випічки печива

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

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