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

В процесі динамічного балансування навантаження можна перерозподіляти між ядрами та вузлами одиниці роботи різного розміру. Розглянемо можливі варіанти одиниць роботи – зерна балансування. Можна переміщати між ядрами та вузлами тільки такі обчислення, які можна виконати паралельно з іншими. Інакше звільнене ядро буде очікувати завершення тих обчислень, які були переміщені з нього. Тому можливі наступні варіанти одиниць роботи, що можна перемістити:

– Одиниця роботи – процес. Балансування фактично є міграцією процесів або потоків між різними комп’ютерами в кластерній системі. Як описано в [11], міграція процесів в цілому між ЕОМ є складною задачею через цілу низку причин. Наприклад, виникає проблема при міграції процесів, які використовують будь-які локальні ресурсів ЕОМ (наприклад, файлів або засобів міжпроцесної взаємодії).

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

Таким чином, найбільш доцільним є балансування на рівні підзадач, що розв’язуються в потоках виконання. Схема процесу обробки задачі з балансуванням навантаження зображена на рис. 2.7.

2.5. Критерії вибору моделі програмування паралельних комп’ютерних систем

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

Підсистема динамічного балансування навантаження працює не сама по собі, а в тісній взаємодії з бібліотеками часу виконання та операційною системою, які забезпечують підтримку тої моделі програмування, яка використовується на відповідній паралельній ЕОМ. Так як в якості одиниці роботи, яка підлягає балансуванню, обрано підзадачу (обґрунтування вибору наведено в попередніх підрозділах), то модель програмування повинна містити підзадачі як абстракції.

Тому маємо наступні вимоги для моделі програмування паралельних ЕОМ, яка буде використовуватись з динамічним балансуванням навантаження:

– наявність підзадачі або еквівалентної сутності у множині абстракцій моделі;

– можливість реалізації моделі в системах з локальною пам’яттю, а саме в кластерних (мультикомп’ютерних) системах.

2.6. Недоліки моделі низькорівневої передачі повідомлень

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

Основним недоліком моделі низькорівневої передачі повідомлень є відсутність абстракцій, які характеризують об’єкти, що використовуються при реалізації прикладного програмного забезпечення. Натомість в моделі присутні абстракції і примітиви, які відображають особливості паралельних ЕОМ з локальною пам’яттю. Визначення терміну «абстракція» наведено в [47]:

Визначення 1. Абстракція виділяє сукупність суттєвих характеристик деякого об’єкту, які відрізняють його від всіх інших видів об’єктів, і, таким чином, чітко визначає концептуальні границі з точки зору спостерігача.

Так, в моделі низькорівневої передачі повідомлень присутні наступні абстракції:

– Абстракція групи взаємодіючих процесів. Відповідно до класифікації, вона відноситься до категорії абстракцій сутності (англ. entity abstraction). Суттєвими характеристиками групи процесів є:

– наявність ідентифікаторів в кожного процесу;

– унікальність ідентифікаторів процесів в межах групи;

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

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

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

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

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

Використання вищеназваних абстракцій примушує зводити операції над об’єктами з предметної області до операцій з повідомленнями, які є особливістю роботи в ЕОМ з локальною пам’яттю, а до предметної області як такої не відносяться.

Ця проблема відома як невідповідність абстракцій. В дослідженнях [48, 17] автори вбачають надмірну складність паралельних програм саме в цьому.

Проблема не є новою, існують спроби її розв’язання. Звичайно застосовують спеціалізовані рішення. Наприклад, бібліотеки А++/Р++ [49] орієнтовані на паралельну обробку багатовимірних масивів скалярних даних цілих типів та даних типів з плаваючою комою. Бібліотека OpenFOAM [50] містить набір високорівневих абстракцій для розв’язання чисельного розв’язання задач механіки суцільних середовищ, в тому числі задач опору матеріалів, динаміки рідин та газів. Бібліотека Cusp [51] орієнтована на розв’язання задач, що сформульовані в термінах графів та розріджених матриць.

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

2.7. Високорівневі абстракції для паралельних комп’ютерних систем
з локальною пам’яттю

В циклі статей [52, 53] запропоновано набір високорівневих абстракцій для розробки паралельних реалізацій алгоритмів.

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

– Абстракція часткових результатів, яка також відноситься до категорії абстракцій сутності. Частковий результат – це дані, які є результатом обчислення підзадачі. Для часткових результатів, отриманих в результаті обчислення підзадач однієї задачі, визначена операція об’єднання. Результатом об’єднання є результат вихідної задачі.

Ці абстракції мають наступні переваги перед абстракціями з моделі низькорівневої передачі повідомлень та абстракціями спеціалізованих бібліотек:

– Ці абстракції не прив’язані до певної предметної області і тому мають багато сфер застосування.

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

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

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

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

2.8. Високорівнева передача повідомлень

2.8.1. Загальні визначення

Модель високорівневої передачі повідомлень запропонована в статтях [52, 53]. Ця модель програмування орієнтована на паралельні ЕОМ з локальною пам’яттю, хоча немає перешкод реалізації цієї моделі на ЕОМ зі спільною пам’яттю.

Дана модель програмування паралельних ЕОМ надає високорівневі абстракції для опису кроків алгоритму, які можна виконати паралельно, а також необхідних для їх виконання даних. Реалізація даної моделі для паралельної ЕОМ на основі отриманого опису виконує описані кроки, відповідно до семантики, яка подається нижче.