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

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

Методи дослідження

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

Наукова новизна одержаних результатів

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

Основні наукові результати, отримані особисто автором:

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

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

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

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

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

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

–  вперше розроблено теоретичні засади та створено засоби оперативного моніторингу процесу обробки задач в кластерних комп’ютерних системах, відмiннiстю яких є вико­ристання низькорівневого системного відстежування стану процесів та ресурсів комп’ютерних систем, що дозволяє забезпечити отримання даних для ефективного динамічного управління роботою таких систем;

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

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

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

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

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

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

Практичне значення одержаних результатів

Розроблені нові методи і засоби організації обчислювальних процесів дозволяють підвищити ефективність паралельних кластерних систем.

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

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

Отримані результати дозволяють:

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

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

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

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

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

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

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

–  у Інституті кібернетики ім. Національної Академії наук України (м. Київ) для підвищення ефективності роботи обчислювального кластеру, що підтримує роботу національного ресурсного центру НАН України;

–  у підрозділі R&D компанії "Intel" в межах проектів академічної спільноти зони розробників паралельного програмного забезпечення;

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

–  у Інституті проблем моделювання в енергетиці ім. Г. Є. Пухова Національної Академії наук України (м. Київ) для підтримки роботи програмного забезпечення національної ГРІД інфраструктури;

–  у ДП "Центр громадської безпеки 112" Міністерства надзвичайних ситуацій України;

–  на Центрі суперкомп’ютерних обчислень Національного технічного університету України "Київський політехнічний інститут" для удосконалення процесу технічної підтримки системного програмного забезпечення кластера;