Укрупнення

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

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

Загальні вимоги:

- зниження затрат на комунікації;

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

- результуючі задачі повинні мати приблизно однакову трудоємність;

- збереження масштабованості;

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

- зменшення вартості і трудоємності розробки.

Планування обчислень

На цьому етапі визначається де і на якому процесорі виконується підзадача. Основним критерієм ефективності є мінімізація часу виконання програми. Проблема планування обчислень легко вирішується при використанні систем з розділеною пам’яттю.

В алгоритмах основаних на функціональній декомпозиції, часто створюється множина дрібних “короткоживучих” підзадач. В цьому випадку застосовується алгоритми планування виконання задач (tasks scheduling), які розподіляють підзадачі по незагружених роботою процесорах.

Планування виконання задач полягає в організації їх доступу до ресурсів. Порядок представлення доступу визначається алгоритмом. Наприклад:

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

- метод збалансованого завантаження – оснований на обміну біжучого завантаження процесорів;

- планування виконання задач.

Структури, що виконують такі задачі діляться на ієрархічні і децентралізовані; в децентралізованих – головна задача відсутня.

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

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

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

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

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

Є різні алгоритми збалансованого завантаження в методах декомпозиції даних, наприклад:

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

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

- рекурсивна дихотомія графа. Використовується для нерегулярних сіток (мінімізується кількість ребер);

- ймовірнісні методи. Задачі розміщаються на випадково вибраних процесорах.

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