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

6.5.1. Передача з блокуванням та без блокування

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

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

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

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

Функції без блокування приймають ті ж параметри, що і з блокуванням, і ще додатковий один параметр request типу MPI_Request.

У параметрі request передається дескриптор запиту відправлення або прийому. Цей дескриптор можна передати функціями MPI_Wait або MPI_Waitall для того, щоб дочекатися закінчення передачі.

Всі буфери, які використовуються в передачах без блокування стають недоступними користувачеві після запуску передачі або прийому повідомлення. Буфери стають знову доступними після виконання функцій MPI_Wait або MPI_Waitall для цих передач.

Вибір способу відправки повідомлень (з блокуванням/без блокування) не впливає на вибір способу прийому. Повідомлення, які були відправлені функціями з блокуванням, можуть бути прийняті без блокування, і навпаки.

6.5.2. Колективні взаємодії

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

Такі види обміну можна умовно розділити на три групи:

а) одна задача відправляє дані декільком;

б) одна задача отримує дані від декількох;

в) кілька завдань обмінюються даними між собою.

6.6. Віртуальні топології MPI

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

• кількість передач;

• загальний обсяг переданих даних;

• тип передач;

• інтенсивність передач;

• пікова і середня швидкість передачі даних між процесами;

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

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

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

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

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

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

• кільцеві топології;

• топології типу решітка;

• топології виду n-мірного тора (mesh).

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

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

6.7. Особливості реалізації аналізатора

6.7.1. Підхід до аналізу паралельних програм

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

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

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

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

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

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