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

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

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

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

При використаннi iнших пiдходiв, зокрема завдяки додатковим цiлям оптимiзацiї сумарного та максимального обсягу використаної у вузлах пам’ятi, її використання в середньому зменшилось на 1 - 2%. Iстотну частину з яких складають буфери, що були тимчасово видiленi для зберiгання даних перед балансуванням навантаження або для iнших, даних якi через причини, невiдомi статично без запуску програми, не були використанi в тому вузлi, в якому зберiгалися.

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

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

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

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

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

Топологічна організація компютерної системи

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

При умові, що завдання, які вирішуються сильнозв’язні, при підвищенні розмірності завдання може наступити момент, коли завантаженість каналів зв’язку обчислювальної системи буде близька до максимально можливої і реальна продуктивність буде обмежена не наявністю вільних ресурсів процессора, а швидкістю системи зв’язків використаної ЕОМ. [121,122]

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

Таким чином, необхідно знайти компроміс між вартістю і зв’язністю системи.

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

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

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

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

Оскільки завдання синтезу оптимальної топології, визначення пропускної здатності каналів і маршрутизації інформаційних потоків (TCFA – Topology, Capacity and Flow Assignment) є NP-повною і не представляється можливою для рішення в загальному вигляді, то в сфері високопродуктивних обчислень існує необхідність в допоміжному програмному забезпеченні, як дозволяло б генерувати такі топологічні організації в автоматизованому режимі для конкретних завдань. [124-126]