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

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

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

6.1. Автоматизація синтезу топології

Загальні відомості

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

Одним з найбільш загальних завдань є задача синтезу топології, визначення пропускної здатності каналів і маршрутизації інформаційних потоків (англ. TCFA — Topology, Capacity and Flow Assignment). Це завдання є обчислювально-складним, і для його вирішення різними авторами пропонується кілька загальних підходів. Було показано, що в найбільш узагальненому формулюванні дане завдання є NP-повним завданням на графах, тому існуючі підходи припускають знаходження рішень, близьких до оптимальних, за поліноміальний час, з використанням евристичних оцінок і наближених оптимізаційних методів.

Широко відомі два методи знаходження розв’язання даного завдання, близьких до оптимального. Обидва метода ґрунтуються на застосуванні алгоритмів з поліноміальною обчислювальною складністю, проте ступінь полінома в оцінках складності цих алгоритмів велика, що перешкоджає практичному застосуванні даних методів для завдань розмірності N > 50. При цьому топологічні організації сучасних обчислювальних комплексів представляються графами з розмінностями порядку N →∞.

Регулярність представлень графів не дозволяє спростити дані методи. Разом з тим в контексті сучасних високопродуктивних систем, особливості їх організації, що припускають максимально можливе використання гомогенності вузлів і зв’язків та побудова на основі регулярних, математично-описаних топологічних структур дозволяє обмежити узагальнену постановку завдання. У такій постановці стає можливим створення евристичного алгоритму розв’язання задачі синтезу топології, визначення пропускної здатності каналів і маршрутизації інформаційних потоків з меншою обчислювальною складністю. Оскільки існуючі алгоритми мають поліноміальну обчислювальну складність, новий алгоритм також повинен мати поліноміальну складність, проте з меншим ступенем у поліномі. [127,129]

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

6.2. Математична постановка задачи

Як було сказано вище, особливості побудови сучасних високопродуктивних систем дозволяють обмежити узагальнене завдання синтезу топології, визначення пропускної спроможності каналів і маршрутизації інформаційних потоків наступним чином. Зважаючи на те, що у більшості кластерних систем використовується лише один тип каналів зв'язку, з невеликою протяжністю (фізично вузли розташовуються, як правило, в одному приміщенні), можна відмовитися від використання узагальнених позначень різних типів каналів зв'язку, що мають різну пропускну спроможність і обмеження на довжину. Також, можна нехтувати завдовжки каналів зв'язку, вважаючи її рівною для усіх зв'язків. Дійсно, протяжність високопродуктивних мереж типу InfiniBand обмежена 40 метрами навіть при використанні активних кабелів з проміжними підсилювачами.

Вихідними даними для даного завдання є інформаційні потоки TijS відправлених і TijR прийнятих даних в одиницю часу між вузлами i та j, де i, j ≤ N. Шуканою є матриця суміжності L, елементами якої є:

(6.1)

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

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

Ступінь i-го вузла:

(6.2)

Ступінь графа — максимальна із степенів вершин:

(6.3)

Діаметр графа — максимальна довжина найкоротшої відстані між двома вузлами:

(6.4)

причому при розрахунку діаметра D враховуються тільки довжини шляхів між тими вузлами, між якими існує інформаційний потік Tij > 0.

Сумарний інформаційний потік, що передається через канал зв'язку Lij позначимо як fijL. Тоді сумарний інформаційний потік, що передається через вузол i:

(6.5)

Завантаженість канала зв'язку Lij:

(6.6)

де αij — пропускна здатність канала зв'язку.

Завантаженість вузла i:

(6.7)

де βi — пропускна здатність вузла.

Вартість топологічної організації:

(6.8)

У цьому формулюванні на вирішення задачи, щоб вона відповідала вимогам для побудови реальної топології обчислювальної системи, накладаються додаткові обмеження. Частина обмежень, такі як обмеження максимального діаметру, мотивовані обмеженнями на час поширення даних в обчислювальній системі; інша частина, зокрема, обмеження на завантаженість, фізичними властивостями системи.

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

Обмеження на діаметр

(6.9)

Обмеженення на завантаженість каналів зв’язку:

(6.10)

Обмеженення на завантаженість вузлів:

(6.11)

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

У контексті високопродуктивних систем усі канали зв'язку можна вважати гомогенними, тому:

(6.12)

Всі вузли також можна вважати гомогенними:

(6.13)

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

На основі введених визначень сформулюємо два оптимізаційні завдання.

Синтез топології, який не гарантує відмово стійкість. Синтезувати топологічну організацію у вигляді матриці суміжності L (6.1) на основі значень інформаційних потоків TijS і TijR за умови гомогенності вузлів і зв'язків (6.12), (6.13), таку що оптимізаційний критерій – вартість C (1.8) є мінімальним і виконуються обмеження на діаметр (6.9 ) і завантаженість (6.10), (6.11 ).

Синтез відмовостійкої топології. Синтезувати топологічну організацію у вигляді матриці суміжності L (6.1) на основі значень інформаційних потоків TijS і TijR за умови гомогенності вузлів і зв'язків (6.12), (6.13), таку, що оптимізаційний критерій – вартість C (6.8) є мінімальним і виконуються обмеження на діаметр (6.9) топології, завантаженість вузлів і зв'язків (6.10 ), (6.11) і забезпечується існування альтернативних маршрутів.

6.3. Алгоритми синтезу без урахування відмов

Основою запропонованих алгоритмів є процедура видалення найменш завантажених каналів зв'язку.

Алгоритм синтезу топології без відмовостійкості:

а) Прийняти як поточну топологію T повний граф.

б) В поточній топології Т прокласти маршрути для всіх інформаційних потоків з урахуванням вимог завантаженості каналів зв’язків і вузлів.

в) Відсортувати канали зв’язку по зменшенню коефіцієнта завантаженості.

г) Повторити для Ne найменш завантажених ребер ei:

1) Удалити ребро ei з Т та позначити нову топологію як Ti.

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

3) Перевірити виконання обмежень, накладених на діаметр.

4) Розрахувати вартість Ci.

д) Якщо не вдалося побудувати жодної нової топології, то поточна топологія T є результатом роботи.

е) Серед топологій Ti вибрати топологію з найменшою вартістю Ci. Якщо е декілька топологій з рівним діаметром, то слідує вибрати топологію Ti, в якої характеристики завантаженості ребер і вузлів як можна ближче до характеристик Т.