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

 

Висновки до розділу 3

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

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

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

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

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

Запропоновано ряд пiдходiв до визначення часу початку передачi даних. Серед них слiд вiдзначити два пiдходи, якi є вiдповiдно нижнiм i верхнiм обмеженням на доцiльнi значення часу початку передачi даних: передавати данi вiдразу по готовностi, тобто фактично на виконувати вiдкладення, та передавати данi за запитом, тобто вiдкладати передачу на максимально можливий термiн. Обмеження знизу є гарантiєю збереження коректностi обчислень, оскiльки данi будуть пiдготованi перед їх пересилкою для використання, а вихiд за обмеження зверху через необхiднiсть додаткового очiкування пiсля запиту на використання даних вносить у час виконання затримку, пiд час якої обчислення не виконуються, що в результатi знижує коефiцiєнт ефективностi. Запропоновано також два пiдходи до бiльш гнучкого обчислення часу початку передачi даних, один з яких базується на статистичнiй обробцi попереднiх значень часу очiкування введення та виведення та обсягiв пам’ятi пiд час розв’язання даної задачi, а iнший – на ймовiрнiснiй оцiнцi часу першого запиту даних та часу, необхiдного для передачi цих даних мiж вузлами. В рамках кожного з пiдходiв може бути запропоновано декiлька рiзних способiв визначення невiдомих величин, а саме можна змiнювати алгоритми статистичної обробки або ймовiрнiснi моделi прогнозування. Для останнiх найбiльш простою є використання моделi програмування, що базується на розбиттi на пiдзадачi, яка якiсно вiдображає задачi з великою кiлькiстю даних для обробки.

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

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

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

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

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

Роздiл 4

Проведення експериментiв та аналiз результатів

4.1. Особливостi реалiзацiї запропонованих пiдходiв в кластерних системах

Запропонованi в другому роздiлi пiдходи до динамiчного балансування навантаження в теорiї виконують оптимiзацiю (2.6), що призводить до пiдвищення коефiцiєнта ефективностi KЕ

- необхiдно, щоб тривалiсть додаткових дiй, якi пов’язанi з балансуванням навантаження, була значно менше, нiж виконання обчислень, безпосередньо пов’язаних з розв’язанням задачi;

- необхiдно, щоб обраний спосiб реалiзацiї не був специфiчним для певного апаратного забезпечення i пiдходив для великої кiлькостi кластерних систем. Основну масу високопродуктивних систем на сьогоднiшнiй день складають кластернi системи, [16] одиничним елементом яких є паралельна ЕОМ зi спiльною пам’яттю (обчислювальний вузол), що мiстить n ядер, а базовим елементом є комп’ютерна мережа. Таким чином, хоча окремi ядра i мають спiльну пам’ять, в цiлому кластерна система вiдноситься до систем з локальною пам’яттю. В якостi комп’ютерної мережi звичайно використовується спецiальна високопродуктивна мережа, наприклад, InfiniBand, яка забезпечує високi швидкостi та низькi затримки передачi даних. Переважна бiльшiсть кластерних систем має реалiзацiю iнтерфейсу передачi повiдомлень MPI в якостi основного програмного iнтерфейсу програмування обчислювальної системи. Введення унiфiкованого iнтерфейсу передачi повiдомлень дозволяє абстрагувати апаратнi особливостi рiзних паралельних систем, зокрема особливостi системи зв’язкiв та способiв її використання. MPI дозволяє виконувати обчислення на будь-якому вузлi та органiзовувати передачу даних мiж будь-якою парою вузлiв в певних режимах.

Таким чином, MPI є де-юре i де-факто стандартним iнтерфейсом до бiльшостi кластерних систем. Тому доцiльно виконувати реалiзацiю пiдсистеми динамiчного балансування навантаження як окремого рiвня абстракцiї над MPI (рис. 4.1). Змiна набору абстракцiй або поведiнки безпосередньо iнтерфейсу MPI небажана, оскiльки це радикальне рiшення буде мати вплив на вже iснуючi програми з його використанням, якi розраховують на вiдому поведiнку.

Рис. 4.1. Мiсце динамiчного балансування навантаження на рiвнi пiдзадач в стеку iснуючих технологiй

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