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

Так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потеза 4 пiдтверджена.

• Для задачi В всi способи подiлу показують схожi результати. Рiзниця в коефiцiєнтах прискорення на 10..15 процесорах пояснюється особливостями вхiдних даних та не проявляється при iнших вхiдних даних. Необхiдно вiдмiтити, що при збiльшеннi кiлькостi процесорiв коефiцiєнт прискорення не зростає бiльше 6,8.

• Под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потеза 1 пiдтверджена частково. Дiйсно, подiл на пiдзадачi найбiльшого розмiру мiнiмiзує загальний час пересилок даних, але це не призводить до пiдвищення значень коефiцiєнту ефективностi, через те, що час очiкування в кiнцi обчислень twin збiльшується через незбалансованiсть навантаження та неодночасний запуск обчислень пiдзадач. Цей ефект проiлюстровано на рис. 4.8: пересилок дiйсно виконується мiнiмальна кiлькiсть: по однiй на початку та по однiй в кiнцi (не всi пересилки в кiнцi обчислень достатньо довгi, тому не всi є видимими на рисунку), але в кiнцi обчислень виконується досить довге очiкування завершення обчислень, яке за часом значно перевищує час пересилок.

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

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

Результати тестування розв’язання задач представленi на рис. 4.9 – 4.14 . Для порiвняння, на кожному графiку суцiльною лiнiєю вiдображено результати базового варiанту без балансування навантаження.

Рис. 4.8: Незбалансованiсть обчислень в кiнцi одного з крокiв розв’язання задачi А

В результатi аналiзу отриманих даних виявлено наступне:

• Для задачi A максимальне значення коефiцiєнту прискорення склало 14,4 на 28 процесорах, при чому використовувався подiл на пiдзадачi рiзного порядку. Для порiвняння, без балансування навантаження KП = 14 на 31 процесорі, що дає підвищення ефективності KЕ на 6%.

• Для задачi Б найкращi результати показало балансування навантаження, за умови використання подiлу на пiдзадачi середнього розмiру. Мiж базовим варiантом та варiантом з балансуванням навантаження практично вiдсутня рiзниця при застосуваннi 8..26 процесорiв. Але при застосуваннi бiльше 26 процесорiв балансування навантаження має перевагу: пiдвищення коефiцiєнту прискорення вiд 17,1 до 18,6, що дає пiдвищення ефективностi KЕ на 4,7%.

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

• У всiх випадках пiдхiд, який включав балансування навантаження, показав результати принаймнi не гiршi, нiж пiдхiд без балансування навантаження, i тому гiпотеза 5 пiдтверджена.

В середньому, пiдвищення коефiцiєнта ефективностi склало 4,8%.

Рис. 4.9. Залежнiсть KЕ від кількості процесорів при балансуванні навантаження з перерозподілом від одного процесу для задачі А.

Рис. 4.10. Залежнiсть KП від кількості процесорів при балансуванні навантаження з перерозподілом від одного процесу для задачі А.

Рис. 4.11. Залежнiсть KЕ від кількості процесорів при балансуванні навантаження з перерозподілом від одного процесу для задачі Б.

Рис. 4.12. Залежнiсть KП від кількості процесорів при балансуванні навантаження з перерозподілом від одного процесу для задачі Б.

Рис. 4.13. Залежнiсть KЕ від кількості процесорів при балансуванні навантаження з перерозподілом від одного процесу для задачі В.

Рис. 4.14. Залежнiсть KП від кількості процесорів при балансуванні навантаження з перерозподілом від одного процесу для задачі В.

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

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

Результати тестування розв’язання задач представленi на рис. 4.15 – 4.17 . Для порiвняння, на кожному графiку суцiльною лiнiєю вiдображено результати базового варiанту без балансування навантаження, а також найкращий з результатiв балансування навантаження без додаткового подiлу.

В результатi аналiзу отриманих даних виявлено наступне:

• Для задачi А додатковий подiл не привiв до збiльшення коефiцiєнту прискорення. Це очiкуваний результат (вiдповiдно до гiпотези 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єнту прискорення.

Рис. 4.15. Залежнiсть KП від кулькості процесорів при балансуванні навантаження з перерозподілом від одного процесу та додатковим поділом для задачі А.

Рис. 4.16. Залежнiсть KП від кулькості процесорів при балансуванні навантаження з перерозподілом від одного процесу та додатковим поділом для задачі Б.

Рис. 4.17. Залежнiсть KП від кулькості процесорів при балансуванні навантаження з перерозподілом від одного процесу та додатковим поділом для задачі В.

• Для задачi В додатковий подiл дає невеликий позитивний ефект (≈ 1% пiдвищення ефективностi) тiльки при великiй кiлькостi процесорiв (> 30), але цей ефект не проявляється в рiзнiй мiрi при рiзних вхiдних даних. Для меншої кiлькостi процесорiв навпаки, спостерiгаємо зниження ефективностi.

• Вiдсутнiсть будь-якого ефекту або зниження ефективностi у порiвняннi з балансуванням навантаження з перерозподiлом вiд одного процесу можна пояснити збiльшенням часу twin очiкування пiдзадачами вхiдних даних. Дiйсно, канали зв'язку, що обслуговують ядро 0 майже повнiстю завантаженi, та додатковий подiл призводить тiльки до збiльшення кiлькостi повiдомлень в мережi. Отже, гiпотеза 3 спростована, так як початкова розсилка забезпечує зниження навантаження каналiв зв'язку пiд час основного циклу обчислень

• В загальному випадку виконувати балансування навантаження з перерозподiлом вiд одного процесу та додатковим подiлом не доцiльно, через те що канали зв’язку першого вузла стають вузьким мiсцем для даного пiдходу.

4.7. Балансування навантаження з перерозпод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ншого ядра j. Ядро j у вiдповiдь пересилає половину пiдзадачi найменшого порядку. Пiсля цього виконуються обчислення, а додатковi пiдзадачi запитуються так само.

Результати тестування розв’язання задач представленi на рис. 4.18 – 4.23. Для порiвняння, на кожному графiку суцiльною лiнiєю вiдображено результати базового варiанту без балансування навантаження, а також найкращий з результатiв балансування навантаження без додаткового подiлу.