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

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

Гiпотеза 3. Застосування пiдходу передачi даних по запитам в дослiджуванiй реалiзацiї дозволяє виконувати запити на використання даних не в тому порядку, в якому данi можуть бути пiдготованi. Таким чином, можливе перевпорядкування доступу, що зменшує час очiкування введення та виведення вiдповiдно до проаналiзованих в роздiлi 2.3 спiввiдношень у часi. Навiть за вiдсутностi балансування навантаження, перевпорядкування передач може зменшити час очiкування введення та виведення, що спростовує дану гiпотезу. Бiльш того, збiльшення коефiцiєнту ефективностi при використаннi цього способу (рис. 5.5) свiдчить на користь невiрностi гiпотези.

Гiпотеза 4. На рис. 5.7 показано змiну коефiцiєнту ефективностi, усереднену для всiх задач, для яких виконувались експерименти, у залежностi вiд вiдношення часу затримки при застосуваннi статично визначеної тривалостi вiдкладення до середньої тривалостi очiкування початку передачi даних.

Дiйсно, якщо тривалiсть вiдкладення передачi даних значно менше середньої тривалостi очiкування введення та виведення, td << w, i∕o, або ≤ 0.05, коефiцiєнт ефективностi майже незмiнний, оскiльки передача даних розпочинається з незначною затримкою. Зазначимо також, що при нульовiй затримцi коефiцiєнт ефективностi навiть знижується через необхiднiсть виконання обчислень для пiдтримки механiзму вiдкладення передачi даних.

Гiпотеза 5. Як випливає з рис. 5.7 зi збiльшенням вiдношення тривалостi вiдкладення передачi до часу очiкування передачi даних, коефiцiєнт ефективностi збiльшується i сягає максимального значення при = 0.72, пiсля чого починає зменшуватись. Якщо тривалiсть близька до середнього часу очiкування передачi даних, коефiцiєнт ефективностi залишається незмiнним, а при подальшому збiльшеннi тривалостi вiдкладення стає нижче середнього значення, що пiдтверджує дану гiпотезу.

Рис. 5.7. Залежнiсть коефiцiєнту ефективностi вiд вiдношення статичного часу затримки до середнього часу очiкування, усереднена для всiх задач

Гiпотеза 6. Для перевiрки цiєї гiпотези було виконано ряд експериментiв з рiзними обчислювальними задачами, для яких тривалiсть затримки td визначалась як певна функцiональна залежнiсть f(t) = at2 + bt + c, причому параметри a, b,c обирались таким чином, щоб задовольняти або не задовольняти квадратнiй нерiвностi

Для наборiв параметрiв, що задовольняють нерiвностi, середнє значення коефiцiєнту ефективностi склало = 80.431%, у той час як для тих, що не задовольняють нерiвностi, середнє значення склало = 85.192. Порiвняння цих значень свiдчить про вiрнiсть гiпотези. Крiм того, при використаннi параметрiв, що не задовольняють нерiвностi, тобто передбачають такий час затримки, який в середньому менше рiзницi мiж часом запиту на використання даних та часом їх готовностi, досягнуто збiльшення коефiцiєнту ефективностi в середньому на 1.056%.

Гiпотеза 7. Для перевiрки цiєї гiпотези було виконано ряд експериментальних запускiв з використанням рiзних функцiї для визначення тривалостi вiдкладення. Як видно з рис. 5.8, використання функцiй, значення яких не дорiвнює нулю в початку координат, f(0)≠0, знизило коефiцiєнт ефективностi у порiвняннi з функцiями, для яких ця умова не вiрна. Це легко пояснюється тим, що на початку роботи програми бiльшiсть даних, що передаються, необхiднi для негайних обчислень i тому вiдкладати їх передачу на тривалий час недоцiльно. На рис. 5.8 також показано вплив змiни початку вiдкладення передач даних по вiдношенню до загального часу роботи програми (який був обраний iз запуску без вiдкладення). Найбiльш доцiльним для даного перелiку обчислювальних задач є починати застосовувати вiдкладення передачi даних через 17% загального часу виконання передач.

Неважко вiдмiтити, що розпочинати вiдкладення наприкiнцi роботи програми недоцiльно, так як це призведе до зниження коефiцiєнту ефективностi. Також можна припинити вiдкладення передачi даних за певний час до очiкуваного завершення обчислень. Дана гiпотеза експериментально пiдтверджена, але для її практичного застосування необхiдно використовувати методи оцiнки часу виконання обчислень. [117-118]

Гiпотеза 8. Для обчислень з довiльними обсягами даних, що передаються мiж парами вузлiв, застосування пiдходу з оцiнкою тривалостi передачi даних та часу можливого запиту на використання цих даних може генерувати некоректнi оцiнки часу через випадковiсть обсягiв даних, якi в свою чергу можуть призвести до зниження ефективностi (рис. 5.9).

Рис. 5.8. Змiна коефiцiєнту ефективностi при початку роботи механiзму вiдкладення передачi даних через p вiдсоткiв тривалостi виконання обчислень

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

Гiпотеза 9. Як випливає з рис. 5.9, вiдкладення на частину оцiненої рiзницi мiж часом готовностi i часом запиту на використання цих даних дозволяє збiльшити коефiцiєнт ефективностi для задач з довiльним розподiлом обсягiв даних, що передаються мiж вузлами. Це зокрема пояснюється зменшенням кiлькостi випадкiв, у яких завищена оцiнка цiєї рiзницi призводила до внесення очiкування передачi даних, що компенсує додатковi затримки, якi могли статися пiсля цього моменту часу.

Рис. 5.9. Залежнiсть коефiцiєнту ефективностi вiд кiлькостi процесiв для рiзних способiв оцiнки часу вiдкладення

Висновки до роздiлу 5

Запропонованi пiдходи до вiдкладання початку передачi даних мiж вузлами обчислювальної системи на певний час з огляду на збiльшення ефективностi та оптим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зованi реалiзацiї MPI та дозволить користувачевi системи описувати спосiб передачi даних iз використанням вiдомих засобiв. При цьому також доцiльно реалiзувати одну iз абстракцiй бiльш високого рiвня над передачею повiдомлень, зокрема абстракцiю розбиття i об’єднання пiдзадач, яка дозволить у бiльш простому виглядi описувати структуру задач для подальших експериментiв.

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

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

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

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

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