Page 32 - 6571

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

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

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

алгоритмів найкраще відповідають декомпозиції за результую-
чими даними.

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

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

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

4.2 Загальна схема розпаралелювання задач та

закон Амдала

Розглянемо алгоритми розпаралелювання типових задач не-
залежно від конкретної програмної і платформної реалізації. Роз-

паралелити задачу можна не в єдиний спосіб. Алгоритми розпа-
ралелювання зручно графічно зображати у вигляді розгалужених
дерев.

Перший етап: розбиття задачі на незалежні підзадачі.

31