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

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

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

Для проведення вимiрiв на реальнiй кластернiй системi були застосованi вбудованi засоби MPI, високоточн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зних класiв задач, що були обранi для експериментiв, що перш за все пояснюється рiзницею мiж характеристиками самих задач з точки зору обчислювальної складностi та об’ємiв даних, що передаються.

Для задачi А (паралельна реалiзацiя з регулярним паралелiзмом) найкращi результати показало балансування навантаження з перерозподiлом вiд одного процесу, при чому використовувався подiл на пiдзадачi рiзного порядку. Пiдвищення ефективностi KЕ в порiвняннi з базовим пiдходом без балансування навантаження склало 6,0%.

П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Е на 4,7% для 26 процесорiв i бiльше. Подальше пiдвищення ефективностi досягнуто за рахунок використання пiдходу з перерозподiлом мiж усiма процесами та додатковим подiлом, який дозволив додатково пiдвищити ефективнiсть в середньому на 3,2% на 16 процесорах i бiльше.

Для задачi В (паралельна реалiзацiя з нерегулярним паралелiзмом) всi пiдходи без балансування навантаження (рiзне зерно паралелiзму) показують схожi результати: для 16 процесорiв i бiльше коефiцiєнт прискорення не перевищує 6,8. Використання балансування навантаження з перерозподiлом вiд одного процесу пiдвищило ефективнiсть в середньому на 4,8% для 18 процесорiв i бiльше. При цьому виявлено, що найкраще використовувати подiл на пiдзадачi середнього розмiру (P2 пiдзадач).

Подальше пiдвищення ефективностi виконання задачi В було досягнуто за рахунок використання пiдходу з перерозподiлом мiж усiма процесами та додатковим подiлом. Це пiдвищило коефiцiєнт ефективностi ще на 6,3% в порiвняннi з пiдходом без додаткового подiлу.

Iнформацiя про досягнуте пiдвищення ефективностi для рiзних задач зведена у табл. 4.1 .

В процесi аналiзу результатiв також виконувалась емпiрична перевiрка ряду гiпотез. Результати емпiричної перевiрки гiпотез зведенi в табл. 4.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льшенням часу twin витраченого на взаємодiю, та часу tw, inочiкування пiдзадачами вхiдних даних. Додатковий подiл призводить до збiльшення кiлькостi повiдомлень в мережi, але всi повiдомлення обслуговуються одним i тим же вузлом, i тому канали зв'язку першого вузла стають вузьким мiсцем для даного пiдходу.

Таблиця 4.1.

Середнє пiдвищення коефiцiєнту ефективностi KЕ розв'язання задач, що були обранi для проведення експериментiв

Задача	Балансування навантаження з перерозподiлом вiд одного процесу, у порiвняннi з базовим пiдходом без балансування навантаження	Балансування навантаження з перерозподiлом мiж усiма процесами та додатковим подiлом, у порiвняннi з перерозподiлом вiд одного процесу
Задача А	+6,0%	Без змiн
Задача Б	+4,7%	+3,2%
Задача В	+4,8%	+6,3%

Таблиця 4.2.

Результати емпiричної перевiрки гiпотез щодо пiдходiв до балансування навантаження

Гiпотеза	Результат перевiрки
гiпотеза 1	пiдтверджена частково
гiпотеза 2	пiдтверджена
гiпотеза 4	пiдтверджена
гiпотеза 5	пiдтверджена
гiпотеза 3	спростована

Пiдхiд до балансування навантаження з перерозподiлом вiд одного процесу та додатковим подiлом не показав пiдвищення ефективностi у порiвняннi з аналогiчним пiдходом без додаткового подiлу. Це можна пояснити збiльшенням часу twin витраченого на взаємодiю, та часу tw, inоч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 на 16 i бiльше ядрах.

Тестування пiдходу до балансування навантаження з врахуванням топологiї призвело до тривiальних результатiв (повне спiвпадiння з показниками ефективностi пiдходiв без врахування топологiї) через те, що мережа InfiniBand кластерної системi Центру суперкомп’ютерних обчислень НТУУ «КПI» має топологiю «зірка», в якiй вiдстанi мiж будь-якими двома вузлами є однаковими, i тому врахування топологiї не мало переваг.

На основi отриманих результатiв в табл. 4.3 сформульованi рекомендацiї щодо вибору пiдходу динамiчного балансування навантаження в залежностi вiд задачi та системи.

Таблиця 4.3.

Рекомендац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зняються

РОЗДІЛ 5

РЕАЛІЗАЦІЇ ДЛЯ КЛАСТЕРНИХ СИСТЕМ ТА АНАЛІЗ РЕЗУЛЬТАТІВ ЕКСПЕРІМЕНТІВ

5.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в, з’єднаних високопродуктивною мережею, наприклад Infiniband. [106] Переважна бiльшiсть iснуючих кластерних систем надає доступ до низькорiвневого iнтерфейсу передачi повiдомлень MPI як до iнтерфейсу програмування обчислювальної системи. Структура цього iнтерфейсу дозволяє абстрагувати апаратнi особливостi тiєї чи iншої системи, зокрема систему зв’язкiв та нестрогу неоднорiднiсть обчислювальних вузлiв, дозволяючи виконувати обчислення на будь-якому з них та органiзовувати передачу даних мiж будь-якою парою вузлiв. Таким чином, MPI є фактично iнтерфейсом до бiльшостi кластерних систем, вiдповiдно доцiльним є використовувати його для безпосередньої передачi даних, тобто ввести додатковий рiвень абстракцiї над MPI (рис. 5.1). Змiнення поведiнки безпосередньо iнтерфейсу MPI небажана, оскiльки може вплинути на вже iснуючi програми з його використанням, якi розраховують на вiдому поведiнку.