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

ж) Вибрану топологію позначити Tі перейти на крок 2.

Маршрутизація інформаційних потоків виконується по наступному алгоритму:

а) Для кожного інформаційного потоку повторити:

1) Видалити з топології всі зв’язки і вузли, які не можуть бути частиною маршруту із-за обмежень на завантаженість.

2) Вибрати найкоротший маршрут.

3) Збільшити завантаженість зв’язків і вузлів, які входять у вибраний шлях.

4) Повернути видалені зв’язки і вузли на початкове місце.

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

Введення додаткової перевірки на етапі вибору топологічної організації для розгляду на наступній ітерації. Ця перевірка збільшує обчислювальну складність алгоритму, проте дозволяє формувати тільки такі топології, в яких між будь-якою парою вершин існує декілька альтернативних маршрутів. [131-133]

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

Алгоритм синтезу відмово стійкої топології відрізняється нявністю перевірки виконання вимоги відмово стійкості для кожної топології Ti.

Перевірка вимоги відмовостійкості:

а) Для кожного інформаційного потоку повторити:

1) Видалити з топології всі зв’язки і вузли, які є частиною основного маршруту.

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

3) Повернути видалені зв’язки и вузли на початкове місце.

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

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

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

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

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

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

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

Реалізація для кластерних систем

Найбільш поширеним на сьогоднішній день типом розподілених систем є кластерні системи. Кластерна розподілена система являє собою мультикомп’ютер з мультипроцесорів, комбінуючи при цьому особливості програмування того й іншого. Як правило, вузлом кластера є мультипроцесорна система із загальною пам'яттю, програмування для якої використовує широко відому методологію розробки паралельних програм із взаємодією через загальні дані. Вузли об'єднані між собою високопродуктивною комунікаційною мережею таким чином, що один вузол не може напряму звернутися до пам'яті іншого вузла, що вимагає використання механізму передачі повідомлень для організації взаємодії між процесами. [130, 134]

Класичний низькорівневий підхід до програмування такої системи полягає в реалізації кількох процесів, взаємодіючих між собою шляхом передачі повідомлень по мережі через доступну в операційній системі концепцію об'єкта для мережевих підключень (як правило, таким об'єктом є сокет). Кожен з процесів при цьому є багатопотоковим, причому взаємодія між потоками всередині процесу ґрунтується на механізмі використання загальних змінних в пам'яті. Такий підхід дає найкращі показники прискорення та ефективності при розпаралелюванні, проте його реалізація досить складна. [135-139] Для спрощення програмування можна допустити роботу декількох процесів в рамках одного вузла, але крім додаткових накладних витрат на запуск і керування процесами такий підхід тягне додаткові витрати на взаємодію між ними, яке відбуватиметься з використанням сокетів через стек мережевих протоколів навіть якщо процеси запущені на одному вузлі.

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

6.5. Інтерфейс передачі повідомлень MPI

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

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

MPI передбачає написання однієї програми незалежно від кількості обчислювальних вузлів. Паралельне виконання MPI програми досягається одночасним запуском програми на декількох обчислювальних вузлах. Утиліта запуску MPI (mpiexec) запускає програму на зазначених обчислювальних вузлах з локальною пам'яттю і виконує настройку передачі даних між запущеними копіями програми. Кожну запущену копію MPI програми називають завданням.

Група – упорядкована множина завдань. Кожній задачі в групі присвоюється порядковий номер, починаючи з 0. Цей номер називається рангом (або ідентифікатором) завдання.

Комунікатор — об'єкт MPI, який дозволяє завданням відправляти і отримувати повідомлення.

Інтра-комунікатор — комунікатор, пов'язаний з деякою групою завдань. Дозволяє завданням взаємодіяти в межах цієї групи.

Інтер-комунікатор — комунікатор, призначений для відправки повідомлень між двома або більшою кількістю груп завдань.

Після ініціалізації MPI для програми доступний комунікатор MPI_COMM_WORLD. Цей комунікатор пов'язаний з групою, яка включає всі запущені завдання.

Для роботи з MPI в програмі необхідно підключити заголовний файл mpi. h.

Кожне повідомлення в MPI складається з конверта і буфера даних. До конверту відносяться:

• ранг завдання-відправника;

• ранг завдання-одержувача;

• тег повідомлення;

• комунікатор, в рамках якого відбувається взаємодія зазначених завдань.

Функції відправлення та прийому повідомлень MPI оперують масивами однотипних елементів - так званими буферами. Розмір буферів вказується не в байтах, а в елементах.

Кожна функція MPI, яка працює з буферами, має аргумент, в якому вказується тип елементів буфера. Для кожного базового типу мови С передбачена константа MPI (табл. 6.1). Користувач може реєструвати в MPI свої власні типи даних, після чого MPI зможе їх обробляти нарівні з базовими.

Таблиця 6.1.

Відповідність констант опису типів MPI стандартним типам змінних мови С

Тип языка Си Тип мови С	Константа MPI
int	MPI_INT
short int	MPI_SHORT
char	MPI_CHAR
long int	MPI_LONG
unsigned int	MPI_UNSIGNED
unsigned short int	MPI_UNSIGNED_SHORT
unsigned char	MPI_UNSIGNED_CHAR
unsigned long int	MPI_UNSIGNED_LONG
float	MPI_FLOAT
double	MPI_DOUBLE
long double	MPI_LONG_DOUBLE

З кожним повідомленням, яке передається в режимі точка-точка, пов'язаний деякий тег. Тег – ціле число, яке програміст вибирає, виходячи зі своїх міркувань. Діапазон допустимих значень тегів – від 0 до як мінімум 32767 включно (реалізаціям MPI дозволено вибирати максимальне значення тегу). Зазвичай теги використовуються в програмах для того, щоб відрізняти різні види повідомлень. Завдання-відправник повідомлення встановлює його тег, а завдання-одержувач може вибрати такий режим прийому, в якому будуть отримані тільки повідомлення із заданим тегом.