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

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

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

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

6.7.5. Діаграма пропускних спроможностей процесів

Діаграма пропускних спроможностей процесів - це останній з основних елементів інтерфейсу розробленого програмного забезпечення.

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

Віджет складається з 4 частин:

Гістограма інтенсивностей обміну. В лівій частині віджета розташована діаграма інтенсивностей обміну.

Гістограма може показувати інтенсивність входять передач, інтенсивність вихідних передач і сумарну інтенсивність передач процесу

Рис. 6.1. Діаграма пропускних спроможностей процесів

Шкала інтенсивності обміну. Над гистограммой інтенсивностей обміну розташована шкала інтенсивностей обміну, яка дозволяє встановити абсолютне значення інтенсивностей обміну на гістограмі.

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

Sent – включає відображення інтенсивностей вхідних передач на гістограмі.

Received – включає відображення інтенсивностей вихідних передач на гістограмі.

Total – включає відображення сумарних інтенсивностей передач на гістограмі.

Легенда колірного кодування. Легенда розташована в правій частині віджета і має такий вигляд:

Червоний – використовується для позначення інтенсивностей вихідного обміну.

Зелений – використовується для позначення інтенсивностей вхідного обміну.

Синій – використовується для позначення інтенсивностей сумарного обміну.

6.8. Синтез топології з коментарями

Нехай задані наступні інформаційні потоки між 5 вузлами:

На цьому прикладі розглянемо роботу алгоритму крок за кроком. Нехай параметри алгоритму задані як α = 5, β = 5, Dmax = 2, Ne = 1. На першому кроці поточною топологією є повний граф (рис. 6.2). На малюнках в якості ваги ребер вказано сумарний інформаційний потік fijL, що передається через відповідний канал зв'язку. Далі на кроках 2 - 5 з цього графа видаляються (рис. 6.3 – 6.6) найменш завантажені зв'язки (в даному простому прикладі вони мають нульову завантаженість). Так як дані кроки тривіальні, немає сенсу розглядати їх детально.

На п'ятому кроці розглядається один (так як Ne = 1) найменш завантажений зв'язок: це зв'язок між вузлами 0 і 2. Даний зв'язок видаляється і будується нова топологія T1 (рис. 6.7). Для нової топології вирішується завдання маршрутизації і розраховується завантаження каналів зв'язку. У новій топології обмеження на діаметр і завантаженість вузлів і зв'язків виконуються. Однак вартість нової топології (C1 = DNS = 2 ⋅ 5 ⋅ 2 = 20) більше вартості поточної топології (рис. 6.6, C1 = DNS = 1 ⋅ 5 ⋅ 3 = 15), тому топологія T1 далі не розглядається. Так як інші ребра для видалення не розглядаються (так як Ne = 1), то алгоритм завершує роботу. Результат на рис. 6.6.

Рис. 6.2. Синтез, крок 1

Рис. 6.3. Синтез, крок 1

Рис. 6.4. Синтез, крок 1

Рис. 6.5. Синтез, крок 1

Рис. 6.6. Синтез, крок 1

Рис. 6.7. Синтез, крок 5, розглянута топологія T1

6.9. Синтез складної топології

Нехай задані наступні інформаційні потоки між 16 вузлами:

Результатом синтезу за допомогою запропонованого алгоритму (α = 7, β = 24, Dmax = 3, Ne = 5) є топологічна організація, представлена на рис. 6.8. На малюнку в якості ваги ребер вказаний сумарний інформаційний потік fijL, що передається через відповідний канал зв'язку.

Рис. 6.8. Синтезована топологічна організація

6.9.1. Чисельне інтегрування

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

У представленому прикладі в програмі проводиться чисельне інтегрування функції на проміжку [0; π]. Природа підінтегральної функції така, що при значеннях аргументу, близьких до 0 інтеграл сходиться швидко, а при значеннях, близьких до π – інтеграл сходиться дуже повільно.

У початковому варіанті програми проміжок інтегрування був розділений на стільки рівних частин, скільки було обчислювальних вузлів. Відповідна часова діаграма представлена на рис. 6.9. Як видно з малюнка, це призвело до дуже нерівномірного розподілу обчислювальної роботи між завданнями. Перше завдання, яке інтегрувало функцію на проміжку [0; ], завершило роботу дуже швидко і після цього ніяких обчислень більш не виконувало. Останнє завдання обчислювало інтеграл на проміжку [; π] і це зайняло значний час, а саме, останнє завдання виконувало розрахунки довше за всіх. Як наслідок, коефіцієнт прискорення не перевищував 3 при запуску програми на 16 вузлах.

Рис. 6.9. Часова діаграма показує нерівномірний розподіл
обчислювального завантаження

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

Рис. 6.10. Часова діаграма поліпшеного варіанту програми

6.9.2. Множення матриць

Фрагмент програми, що аналізується виконує множення щільних матриць.

Для початкового варіанту програми коефіцієнт прискорення був приблизно рівним половині від очікуваного (тобто, на 16 вузлах коефіцієнт прискорення ≈ 7,5). Відповідна часова діаграма представлена на рис. 6.11. З малюнка видно, що завдання з ідентифікатором 0 виконує розсилку початкових даних, прийом результатів і тільки після цього рахунок. Очевидна помилка в коді нульового завдання: оператори рахунку та пересилок поміняні місцями. Тим не менш, дана помилка не призводить до отримання неправильних результатів, оскільки завдання 0 записує результат до себе в локальний масив і їй не потрібно пересилок для відправки свого часткового результату.

Спосіб виправлення цієї помилки очевидний: поміняти місцями проблемні оператори. Часова діаграма роботи виправленої програми представлена на рис. 6.12.

Рис. 6.11. Часова діаграма показує неправильний порядок дій у завданні 0

Рис. 6.12. Часова діаграма виправленого варіанту програми

6.9.3. Введення даних

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

Рис. 6.13. Структура розподіленої обчислювальної системи

В початковому варіанті програми введення даних займало занадто великий час (рис. 6.14). Аналіз статистики повідомлень (рис. 6.15) показує, що розсилку вхідних даних (тобто і введення) виконує завдання з ідентифікатором 0. Проте, завдання з ідентифікатором 0 за замовчуванням розміщується на першому вузлі, тоді як сховище даних сполучене з четвертим вузлом. Таким чином, виконувати читання з першого вузла є неефективним.

Для того, щоб поліпшити ситуацію, немає необхідності вносити зміни в програму. Досить відредагувати скрипт запуску програми так, щоб завдання з ідентифікатором 0 розміщувалося на 4-му вузлі. Після виконання цих дій тривалість введення значно зменшилася (рис. 6.16).