Методи та засоби ефективної обробки паралельних задач в комп’ютерних кластерних системах (стр. 23 )

Розглянемо два варіанти:

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

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

(2.22)

де – кількість підзадач, які мало виконати кожне ядро, якщо ділиться на N без остачі. На кожне ядро відправляється а задач, а інші задачі (остача) розподіляються по одній на перші ядра.

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

де – математичне очікування, – дисперсія випадкової величини.

Досить простою евристикою буде вважати, що кожна підзадача має найбільш імовірну кількість операцій, що дорівнює . В такому випадку задача зведена до умов попередньої та розбиття множини M слід виконати за правилом (2.22).

Після виконання поділу множини M на множини P1, P2,...,PN виконується безпосередньо розсилка: на ядро з номером i передаються всі під задачі з множини Pi.

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

2.11.3. Розсилка підзадач різного порядку

Вхідними даними для даного етапу є множина підзадач:

де m – порядок підзадач (відрізняється для різ них підзадач), – відповідні шляхи поділу, q – потужність множини результатів оператору gsplit.

Необхідно розбити множину M на множини P0, P1,… PN-1, де N – кількість ядер, які доступні задачі в паралельній обчислювальній системі, так, щоб за можливістю мінімізувати незбалансованість початкового розподілу підзадач.

Нехай в множину M входять підзадачі порядків m1, m2,... , mr, причому m1 < m2 < … < mr. Відповідно до способу попереднього поділу на під задачі різного порядку, в множину M входить N підзадач всіх порядків, окрім найбільшого (тобто, порядків m1,...,mr-1). Тому для збалансованого розподілу навантаження підзадачі порядків m1,...,mr-1 слід розподілити по одній на кожне ядро. Підзадачі порядку mr мають найменші проміжки даних, і становлять незбалансоване навантаження. Ці підзадачі слід розподілити по одній на довільні ядра (на всі ядра цих підзадач не вистачить). Формально ці правила записуються так:

.

Після виконання поділу множини M на множині P0, P1,… PN-1 виконується безпосередньо розсилка: на ядро з номером i передаються всі під задачі з множини .

2.12. Способи організації основного циклу обчислень

2.12.1. Загальні зауваження

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

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

2.12.2. Без балансування навантаження

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

Це досягається за рахунок виконання наступних дій:

– Процес, що виконується на ядрі i, перевіряє, чи його черга задач Рі порожня. Якщо вона не порожня , то із черги видобувається перша підзадача та до неї застосовується оператор compute. Результат розміщується в черзі часткових результатів :

– Якщо черга порожня (|Рі| = 0), процес перевіряє, чи є в його черзі часткових результатів Qi такі, які можна об’єднати. Ці результати відповідають умовам:

де – порядок підзадач, – відповідні шляхи поділу, – потужність множини результатів оператору gsplit. Об’єднаний результат – 1-го порядку розміщується в черзі часткових результатів :

Якщо , то отримано результат для вихідної задачі, і цикл обчислень завершується.

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

Після чого результати об’єднуються за допомогою оператора merge, і об’єднаний результат m – 1-го порядку розміщується в черзі Ql.

Якщо m – 1 = 0, то отримано результат для вихідної задачі, і цикл обчислень завершується.

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

2.12.3. Балансування навантаження з перерозподілом від одного процесу

Нехай підзадачі, розподілені в результаті початкової розсилки, знаходяться в чергах , де i – номер ядра, впорядковані за зростанням за лексико-графічним порядком шляху поділу. Кожне ядро також має чергу часткових результатів , впорядковану за аналогічним правилом.

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