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

Процес, що виконується на ядрі i (i ≠ 0), перевіряє, кількість підзадач в черзі Рі. Якщо в черзі одна чи нуль підзадач (|Рі| ≤ 1), процес відправляє запит підзадачі до ядра 0. У відповідь процес, що виконується на ядрі 0, пересилає одну підзадачу з черги Р0 до черги Рі. Якщо в черзі Рі була хоча б одна під задача, передача даних суміщається з обчисленнями.

Гiпотеза, що призвела до формулювання такого способу балансування, наступна.

Гіпотеза 5. Перерозподіл вiд одного процесу (на противагу початковій розсилці та подальшим перерозподiлом мiж усіма процесами) виключає можливість транзитних пересилок даних мiж ядрами (рис. 2.10), що гарантує виконання не більше однієї пересилки вхідних даних мiж вузлами. Тому виконується мiнiмiзацiя загального часу пересилок даних , відповідно до умов оптимізації (2.6), що призведе до підвищення значень коефиціенту ефективності.

Приклади типових графiв пiдзадач, якi формуються в результаті обчислень, показані на рис. 2.11, 2.12.

Рис. 2.10. Зайві (транзитні) пересилки через наявність початкової розсилки

Рис. 2.11. Приклад виконання задачi з попереднiм подiлом на пiдзадачi однакового порядку

Рис. 2.12. Приклад виконання задачi з попереднiм подiлом на пiдзадачi
рiзного порядку

2.12.4. Балансування навантаження з перерозподiлом вiд одного процесу та додатковим подiлом

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

Такий пiдхiд призводить до обробки, з часом, все менших та менших пiдзадач. В результаті незбалансованiсть навантаження буде визначатись розмiром задач, які обробляються останніми. Останніми будуть оброблятись неподiльнi задачі, тому що неподiльнi задачi врештi-решт будуть отримані в результатi подiлу.

2.12.5. Балансування навантаження з перерозподiлом мiж усiма процесами та додатковим подiлом

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

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

Процес, що виконується на ядрi i (i≠0), перевiряє, кiлькiсть пiдзадач в черзi . Якщо в черзi одна чи нуль під задач , процес вiдправляє запит пiдзадачi до ядра j. У вiдповiдь процес, що виконується на ядрi j, пересилає одну пiдзадачу з черги до черги Якщо в черзi була хоча б одна пiд задача, передача даних сумiщається з обчисленнями. Номер j обирається довiльним чином.

2.12.6. Балансування навантаження з перерозподiлом мiж усiма процесами, додатковим подiлом та врахуванням топологiї

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

Перевага даного пiдходу над попереднім в тому, що він забезпечить менший час передачi . Недолік даного підходу в необхідності надавати інформацію про топологію системи.

2.13. Допустимi комбiнацiї способiв органiзацiї окремих етапiв балансування навантаження

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

Але не всi комбiнацiї способів з табл. 2.1 доцільно використовувати. Так, якщо застосовувати початкову розсилку, то виконувати балансування навантаження з перерозподiлом тiльки вiд одного процесу недоцiльно, тому що в цiй комбiнацiї не всi пiдзадачi можуть бути перерозподiленi. На основi таких мiркувань було видiлено комбiнацiї способiв, якi доцiльно використовувати. Цi комбiнацiї наведено в табл. 2.2 .

Таблиця 2.1:

Допустимi комбiнацiї способiв органiзацiї окремих етапiв балансування навантаження

Спосiб подiлу	Спосiб початкової розсилки	Спосiб органiзацiї основного циклу обчислень
Подiл на пiдзадачi найбiльшого розмiру	Без початкової розсилки	Способи з перерозподiлом пiдзадач
Початкова розсилка пiдзадач однакового порядку	Всi способи
Подiл на пiдзадачi середнього розмiру	Без початкової розсилки	Способи з перерозподiлом пiдзадач
Початкова розсилка пiдзадач однакового порядку	Всi способи
Подiл на пiдзадачi рiзного порядку	Без початкової розсилки	Способи з перерозподiлом пiдзадач
Початкова розсилка пiдзадач рiзного порядку	Всi способи

Таблиця 2.2:

Доцiльнi комбiнацiї способiв органiзацiї окремих етапiв балансування навантаження

Спосiб подiлу	Спосiб початкової розсилки	Спосiб органiзацiї основного циклу обчислень
Подiл на пiдзадачi найбiльшого розмiру	Початкова розсилка пiдзадач однакового порядку	Без балансування навантаження
Без початкової розсилки	Способи з перерозподiлом пiдзадач вiд одного процесу
Початкова розсилка пiдзадач однакового порядку	Способи з перерозподiлом пiдзадач мiж усiма процесами
Подiл на пiдзадачi середнього розмiру	Початкова розсилка пiдзадач однакового порядку	Без балансування навантаження
Без початкової розсилки	Способи з перерозподiлом пiдзадач вiд одного процесу
Початкова розсилка пiдзадач однакового порядку	Способи з перерозподiлом пiдзадач мiж усiма процесами
Подiл на пiдзадачi рiзного порядку	Початкова розсилка пiдзадач рiзного порядку	Без балансування навантаження
Без початкової розсилки	Способи з перерозподiлом пiдзадач вiд одного процесу
Початкова розсилка пiдзадач рiзного порядку	Способи з перерозподiлом пiдзадач мiж усiма процесами

Висновки до другого розділу

В даному роздiлi на теоретичному рiвнi розробляються питання пiдвищення ефективностi розв’язання задач за допомогою динамiчного балансування навантаження. В першу чергу були сформульованi критерiї, якi дозволяють оцiнити ефективнiсть розв’язання задачi та збалансованiсть навантаження: коефiцiєнт ефективностi KЕ та коефіцієнт прискорення КП. Було встановлено якi саме часовi характеристики виконання паралельної програми, та характер цього випливу (рис. 2.1). На основi проведеного аналiзу сформульовано умови оптимiзацiї (2.6), якi слiд ставити в основу пiд час розробки пiдходiв розв'язання поставленої задачi. Для виконання цiєї оптимiзацiї запропоновано застосувати динамiчне балансування навантаження мiж ресурсами, що видiленi для задачi.

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