Принципи розробки паралельних методів

Було запропоновано об'єднати цю статтю або розділ з Паралельні обчислення, але, можливо, це варто додатково обговорити. Пропозиція з грудня 2016.

Моделювання паралельних програм[ред. | ред. код]

Для визначення ефективних способів організації паралельних обчислень необхідно:

• виконати аналіз наявних обчислювальних схем та здійснити їх розподіл (декомпозицію) на частини (підзадачі), які можуть бути реалізовані незалежно одна від одної;

• виділити для набору підзадач інформаційні взаємодії;

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

Об’єм обчислень для кожного процесору повинен бути приблизно однаковий – це дозволить забезпечити рівномірне обчислювальне навантаження (балансування) процесорів (процесів).

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

Загальна схема розробки паралельних алгоритмів представлена на рисунку 1.1

Після виконання всіх етапів проектування необхідно оцінити ефективність паралельних методів, що розробляються.

За результатами проведеного аналізу може виявитися необхідність повторення деяких (або всіх) етапів розробки:

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

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

На стадії проектування паралельний метод може бути представлений у вигляді графу «підзадачі-повідомлення» (агреговане представлення графу «операції-операнди»).

Модель «підзадачі-повідомлення» дозволяє:

• Визначити підзадачі однакової обчислювальної складності.

• Забезпечити низький рівень інформаційної залежності між підзадачами.

На стадії виконання для опису паралельної програми може бути використана модель у вигляді графу «процеси-канали» (рисунок 2.1), в якій замість підзадач використовується поняття процесів , а замість інформаційних залежностей – канали передачі повідомлень.

Модель «процеси-канали» дозволяє:

• Здійснити оптимальний розподіл підзадач по процесорам (процесам).

• Виконати аналіз ефективності розробленого паралельного методу.

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

Процес – виконувана на процесорі програма, використовує для своєї роботи частину локальної пам’яті процесору та містить ряд операцій прийому/передачі даних для організації інформаційної взаємодії між виконуваними процесами паралельної програми.[1]

Канал передачі даних – черга повідомлень, в яку один чи декілька процесів можуть відправляти дані, що пересилаються, і з яких процес-адресат може витягувати повідомлення:

• канали виникають динамічно в момент виконання першої операції прийому/передачі з каналом;

• канал може відповідати одній чи декільком командам прийому/передачі даних різних процесів;

• ємність каналу необмежена;

• операції прийому повідомлень можуть призводити до блокувань (дані, що запитуються ще не були відправлені процесами-джерелами).^[1]

Методика розробки паралельних алгоритмів[ред. | ред. код]

Для розробки паралельних алгоритмів необхідно виконати:

• виділення підзадач;

• визначення інформаційних залежностей;

• масштабування;

• розподіл підзадач по процесорам (процесам) обчислювальної системи.

Розподіл обчислень на незалежні частини[ред. | ред. код]

Типовими обчислювальними схемами для виділення підзадач є:

— виконання однотипної обробки великого набору даних – паралелізм за даними. В цьому випадку виділення підзадач зводиться до розподілу наявних даних.

— виконання різних операцій над одним і тим же набором даних – функціональний паралелізм.

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

Наприклад, знаходження максимального елементу матриці (рисунок 4.2). Вихідна (початкова) матриця А може бути розділена на окремі рядки (або послідовність рядків) – стрічкова схема розподілу даних (варіант а); прямокутні набори елементів – блочна схема розподілу даних (варіант б).

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

• Формування максимально можливої кількості підзадач:

— Забезпечує використання гранично допустимого паралелізму;

— Затрудняє аналіз паралельних обчислень.

• Використання достатньо крупних підзадач:

— Призводить до зрозумілої схеми паралельних обчислень;

— Затрудняє ефективне використання великої кількості процесорів (процесів).

• Проміжний рівень – використання як елементів декомпозиції тільки тих підзадач, для яких методи паралельних обчислень відомі. Обрані підзадачі за такого підходу будемо називати базовими, які можуть бути елементарними (не допускають подальшого розподілу) або складовими.[2]

Виділення інформаційних залежностей[ред. | ред. код]

Поняття, що використовуються:

• Локальні та глобальні схеми передачі даних:

— для локальних схем в кожен момент передачі даних виконуються тільки між невеликим числом підзадач (що містяться, як правило на сусідніх процесорах (процесах));

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

• Структурні та довільні способи взаємодії:

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

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

• Статичні або динамічні схеми передачі даних:

— для статичних схем моменти та учасники інформаційної взаємодії фіксуються на етапах проектування та розробки паралельних програм;

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

• Синхронні та асинхронні способи взаємодії:

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

— при асинхронному виконанні операцій учасники взаємодії можуть не чекати повного завершення дій з передачі даних.

Звернімося знову до прикладу знаходження максимального елементу матриці:

• Достатній рівень декомпозиції може полягати в розділенні матриці А на множину окремих рядків та отриманні на цій основі набору підзадач пошуку максимальних значень в окремих рядках;

• Структура інформаційних зв'язків має вигляд:

Масштабування набору підзадач[ред. | ред. код]

Масштабування проводиться у випадку, якщо кількість наявних підзадач не дорівнює кількості доступних процесорів (апаратно незалежних процесів).

Для скорочення кількості підзадач необхідно виконати укрупнення (агрегацію) обчислень:

— підзадачі повинні мати однакову обчислювальну складність, а об'єм та інтенсивність інформаційних взаємодій між підзадачами повинні бути мінімально можливими;

— першими претендентами на об'єднання є підзадачі з високим степенем інформаційної взаємодії.

При недостатній кількості підзадач для завантаження всіх доступних для використання процесорів (апаратно незалежних процесів) необхідно виконати декомпозицію обчислень.^[2]

Розподіл підзадач між процесорами (процесами)[ред. | ред. код]

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

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

Ефективність використання процесорів (ядер) – відносна частка часу, протягом якого процесори (ядра) використовувалися для обчислень, пов'язаних з вирішенням початкової задачі.

Шляхи досягнення хороших показників ефективності:

— рівномірний розподіл обчислювального навантаження між процесами (ядрами);

— мінімальна кількість повідомлень, що передаються між процесорами (ядрами, апаратно незалежними процесами).

Оптимальне рішення проблеми розподілу підзадач між процесорами (ядрами) базується на аналізі інформаційного зв'язку графу «підзадачі-повідомлення».

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

Одна зі схем, що часто використовуються – схема «менеджер-виконавець» (manager-worker scheme):

— для керування розподілом навантаження в системі виділяється окремий процесор-менеджер, якому доступна інформація про всі наявні підзадачі;

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

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

— завершення обчислень відбувається в момент, коли процесори-виконавці завершили рішення всіх переданих їм підзадач, а процесор-менеджер не має ніяких обчислювальних робіт для виконання.^[3]

Див. також[ред. | ред. код]

• Модель паралельних обчислень

Примітки[ред. | ред. код]

Література[ред. | ред. код]

На цю статтю не посилаються інші статті Вікіпедії. Будь ласка розставте посилання відповідно до прийнятих рекомендацій.