10.3.1 Варіанти декомпозиції

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

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

Існує три основні варіанти декомпозиції: проста декомпозиція (trival), функціональна (functional) і декомпозиція даних. Питання про використання того чи іншого типу декомпозиції при написанні паралельної програми вирішується виходячи зі структури самого завдання. Причому, в залежності від умов, можна використовувати відразу декілька типів.

 

10.3.2 Тривіальна декомпозиція

Як випливає з назви, тривіальна декомпозиція найбільш простий тип декомпозиції. Застосовується вона в тому випадку, коли різні копії лінійного коду можуть виконуватися незалежно один від одного і не залежать від результатів, отриманих в процесі обрахунку інших копій коду. Проілюструвати подібний варіант можна на прикладі розв'язання задачі методом перебору або Монте-Карло. У цьому випадку одна й та ж програма, отримавши різні початкові параметри, може бути запущена на різних процесорах кластеру. Як легко помітити, програмування таких паралельних процесів нічим не відрізняється від звичайного програмування на послідовному комп'ютері, за винятком маленької ділянки коду, що відповідає за запуск копій програми на процесорах кластеру та потім очікування закінчення рахунку запущених програм.

Рисунок 10.4 – Приклад тривіальної декомпозиції

 

10.3.3 Функціональна декомпозиція

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

Припустимо наше завдання зводиться до застосування якогось функціонального оператора до великого масиву даних: S [i] = F (a [i]). Припустимо також, що виконання функції F над одним елементом масиву займає досить великий час і нам хотілося б цей час скоротити. У цьому випадку ми можемо спробувати уявити вихідну функцію як композицію декількох фунуцій: S (a [i]) = I (H (R (a [i]). Зробивши декомпозицію ми отримаємо систему послідовних завдань:

x = r (a [i]);

y = h (x);

b [i] = i (y);

Кожна з цих задач може бути виконана на окремому вузлі кластеру. Як можна помітити загальний час обробки одного елемента массиву a[i] в результаті не змінюється, а швидше трохи збільшується за рахунок міжпроцесорного пересилання. Однак загальний час обробки всього массиву помітно знижується за рахунок того, що в нашому прикладі одночасно йде обробка відразу трьох елементів массиву.

 

 

Рисунок 10.5 – Приклад функціональної декомпозиції

 

У цього методу декомпозиції є пара особливостей, про які треба пам'ятати. Перша особливість полягає в тому, що вихід кластеру на максимальну ефективність відбувається не відразу після запуску завдання, а поступово, у міру того, як відбувається часткова обробка першого елемента масиву. Другий і третій процесори в нашому прикладі, які відповідають за виконання функцій g(x) і f(y), будуть простоювати до тих пір, поки не закінчиться виконання функції h(a[1]) на першому процесорі. Третій процесор буде простоювати до закінчення виконання функції g(a[1]). За аналогічним сценарієм, тільки в дзеркальному відображенні, відбувається закінчення роботи.

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

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