Підсистема балансування завантаження ресурсів розподіленого паралельного моделюючого середовища

Авторы: Святний В.А., Надєєв Д.В.
Источник: Наукові праці Донецького національного технічного університету. Серія: Інформатика, кібернетика та обчислювальна техніка. (ИКВТ-02) випуск 39. – Донецьк, ДонНТУ. – 2002. – С. 264-270.

Abstract

Svjatnyj V.A., Nadeev D.V, Subsystem of load balancing for resources (SLBR) of distributed parallel simulation environment (DPSE). It is proposed to distinguish a load balancing subsystem as a part of the distributed parallel simulation environment , which is a new form of the system program organization of simulation facilities for complex dynamic systems. For the implementation of the subsystem, it is necessary to develop a structure, formalize functions, define the algorithm of model devirtualization and allocation in the target simulation environment, ground the methods of resource load balancing, investigate experimentally the subsystem facilities using a representative group of test models.

Вступ

Розподілене паралельне моделююче середовище (РПМС) – це нова форма системної організації сучасних та перспективних засобів моделювання складних динамічних систем (СДС) з безперервним, дискретним та безперервно-дискретним характером фізичних процесів га їх параметрів [1]. До апаратних ресурсів РПМС належать паралельні SIMD- та MIMD-сервери, численні територіально рознесені робочі місця, MIMD-кластери паралельно працюючих персональних ЕОМ, канали зв’язку, апаратура обчислювально-інформаційних мереж, файл-сервери доступу до паралельних систем, різноманітне периферійне обладнання, що орієнтоване на задачі моделювання і наближене до концентрованих груп користувачів. Програмні ресурси РПМС поділяються на системні та прикладні, останні в свою чергу мають важливу складову частину, що відноситься до моделюючого програмного забезпечення (Simulations software). Ефективність використання апаратно-програмних ресурсів РГІМС суттєво залежить від збалансованого їх завантаження. Розглянемо один із підходів до вирішення проблеми балансування завантаження ресурсів РПМС.

1. Джерела та види завантаження ресурсів в РПМС

Структура територіально розподіленого паралельного моделюючого середовища показана на рис. 1. Саме ця структура реалізована кафедрою ЕОМ ДонНТУ та інститутом паралельних і розподілених надпотужних обчислювальних систем (IPVR) Шгутгартського університету [І]. За структурою, характером взаємодії ресурсів та умовами роботи певного кола користувачів РПМС повністю відповідає визначенню розподіленої гетерогенної обчислювальної системи [2]. Джерелами завантаження ресурсів РПМС є робочі місця користувачів (розробників моделей СДС). На кожному місці розробляється паралельна програма (модель СДС), та формується замовлення на її виконання. Потік замовлень зосереджується в файл-серверах середовища теледоступу до SISD-, SIMD- та MIMD-комgонент РПМС.

Визначення 1. Замовлення на ресурси в РПМС – це протокол доступу зареєстрованого користувача та специфікація паралельної моделі (СПМ) СДС з множиною релевантних даних і планом модельних експериментів. Специфікація СДС-моделі може бути виконана її розробником в таких формах:

• на мові опису моделі СДС в термінах предметної області; така специфікація має бути складовою частиною об’єктно-орієнтованої паралельної мови СДС- моделювання [3] (СПМ-1);
• у формі блок-схеми, притаманної блочно-орієнтованій мові моделювання СДС (СПМ-2);
• у формі специфікації рівняння-орієнтованої мови моделювання, близької до мов програмування високого рівня та звичайної математичної форми запису алгебро-диференціальних рівнянь та формул (СПМ-3);
• у вигляді паралельних програм на мовах програмування SIMD- та MIMD- орієнтації (СПМ-4).

Визначення 2. Завантаження РПМС – це сукупність всіх замовлень у формах СПМ-1 – СПМ-4, що передані на виконання і зосереджені у файл-серверах доступу до ресурсів.

Характер робіт, що повинні виконуватись ресурсами РПМС, зумовлюється видом формального опису складної динамічної системи і типом СПМ. З огляду на тісний взаємозв’язок між формальним описом СДС і специфікаціями паралельних моделей розглянемо їх детальніше під кутом зору формування визначених вище замовлень. Складні динамічні системи (рис. 2) мають місце в усіх галузях техніки і технологій, які ми будемо об'єднувати поняттям предметної області (ПО) і структурою формального опису СДС. Незалежно від фізичної природи процесів в формальному описі СДС можна виділити опис топології та математичний опис динаміки процесів.

Аналіз показує, що топологія СДС може бути зведена до трьох видів – топологічні схеми (ТС), структури. систем автоматизації (ССА), мережні динамічні об’єкти (МДО), що відображаються графами. Засобами опису цих топологій є графічні зображення елементів ТС, ССА, МДО, за стандартами предметних областей, матриці зв'язків між входами та виходами елементів, топологічні матриці графів.

Суттєвим з точки зору математичного опису динаміки процесів є поділ динамічних систем на системи з зосередженими (СДСЗП) і розподіленими (СДСРП) параметрами. В технічних і технологічних СДСЗП безперервні процеси описуються системами алгебро-диференціальних рівнянь. При побудові керованих дискретними регуляторами та цифровими ІЮМ СДС до їх опису добавляються логічні функції та рівняння, що оперують з дискретними величинами. Системи з розподіленими параметрами описуються диференціальними рівняннями у часткових похідних. При побудові автоматизованих СДСРП до цих рівнянь приєднуються засоби опису СДСЗП. На рис. 2 показано двосторонній зв’язок між топологічним та математичним описами СДС. Саме аспект складності динамічних систем спонукає до пошуку методів топологічного аналізу їх структур з метою автоматичного генерування модельних рівнянь у формі, придатній до чисельного вирішення.

Характер робіт та види завантажень ресурсів РПМС містяться в замовленнях (СПМ1 – СІІМ4) і визначаються етапами комп’ютерно-підтримуваної розробки паралельних моделей СДС, їх відлагодження та дослідження (проведення модельних експериментів) [3]:

• побудова структури СДС як об’єкта моделювання; цей етап виконується на робочому місці засобами підсистеми діалогу РПМС і має за мету мінімізувати об’єм ручної праці та вірогідність внесення помилок при визначенні структури і параметрів СДС;
• топологічний аналіз структури СДС, формування в результаті аналізу векторів і матриць параметрів формального опису СДС; топологічні аналізатори можуть імплементуватись на робочих місцях, в SISD-, SIMD- та MIMD-серверах;
• генерування систем рівнянь паралельних моделей СДСЗП, СДСРП у вигляді, що потребують чисельні методи; генератори рівнянь використовують дані топологічного аналізу і можуть імплементуватись на робочих місцях, в SISD-, SIMD- та MIMD- серверах;
• чисельне рішення рівнянь паралельних моделей СДС; паралельні вирішувані рівнянь реалізуються на SIMD- та MIMD-системах; існують СДС з розподіленими параметрами, для яких доцільно будувати вирішувані рівнянь комбінованого SIMD/MIMD-типу, в тому числі за SPMD-алгоритмами;
• відлагодження паралельних моделей СДС; цей вид завантаження ресурсів РПМС має змінний характер – від опробування фрагментів моделей на робочому місці з використанням емуляторів SIMD- та MIMD-систем до комплексної перевірки правильності функціонування моделей на реальних цільових паралельних машинах; особливістю цього виду завантажень є активне використання діалогового режиму спілкування розробника моделей з ресурсами РПМС;
• проведення модельних експериментів за відповідною програмою та відповідними варіантами параметрів та структур СДС;
• візуалізація результатів моделювання;
• вирішення задач моделювання в реальному темпі часу: анімація, сумісне функціонування паралельних моделей СДС з реальною апаратурою, використання паралельних моделей СДС в тренажерах; цей вид завантаження ресурсів РПМС г найбільш інтенсивним:
• тестування ресурсів РГ1МС; з огляду на складність та гетерогенність ресурсів планомірне тестування є запорукою надійної експлуатації РПМС широким колом користувачів, запобіганню помилок в моделюванні, зумовлених апаратно- ироірамними причинами.

2. Проблема розміщення замовлень та балансування завантаження ресурсів РПМС

Сучасна концепція мов паралельного моделювання [3], [4] передбачає надання розробнику СДС-моделі віртуальних паралельних SIMD- та MIMD-ресурсів. Специфікація СІІМ-1 характеризує віртуальні моделі СДС. Замовлення ресурсів реальної РПМС потребує виконання підготовчих робіт, які складають процес девіртуалізації і виконуються як підготовчий стан формування дієздатної паралельної моделі, що реалізується на фізично наявних ресурсах. Девіртуалізація складається з таких операцій:

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

Кінцевою метою девіртуалізації є рівномірне завантаження ресурсів РПМС, залучених до реалізації моделей. Згідно з визначенням 2 загальне завантаження PПМС зумовлюється сукупністю віртуальних моделей. Задача девіртуалізації вирішується на основі моделі завантаження РПМС.

Визначення 3. Модель завантаження РПМС – це формально-вербальний опис девіртуалізаційних властивостей віртуальних програм паралельного моделювання СДС. Девіртуалізаційні властивості віртуальних моделей СДС мають два рінні:

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

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

3. Стан та перспективи вирішення проблеми балансування завантаження ресурсів обчислювальних систем

Проблема розподілу та балансування завантаження (БЗ) ресурсів обчислювальних систем досліджується понад двадцять років, їй присвячена дуже широка бібліографія [5,6]. Аналіз показує, що на сьогодні визначились такі основні класифікаційні ознаки методів та засобів БЗ:

1. Статичне та динамічне балансування;
2. Централізоване та децентралізоване балансування;
3. Балансування, ініційоване парами вузлів обчислювальної системи відправником та приймачем;
4. Кооперативне та автономне балансування;
5. Адаптивне та не адаптивне балансування;
6. Оптимальне та субоптимальне балансування.

Дослідження цих методів та засобів дало певні практичні результати: всі серійні паралельні обчислювальні системи MIMD-архітектури мають програмно-апаратні засоби розподілу га балансування завантаження процесорних вузлів, в стадії розробки знаходяться засоби для MIMD-кластерів та проблемно-орієнтованих систем (банки даних , мережі робочих місць, комп’ютерні системи та ін.) [5,6]. Перспективними напрямками досліджень залишаються побудова методів та засобів динамічного балансування з організацією міграції процесів, адаптації систем керування завантаженням до актуального стану виконання потоків замовлень, пошук оптимальних рішень з урахуванням специфіки вирішуваних задач [5,6].

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

4. Підсистема балансування завантаження ресурсів РПМС: визначення, функції

Визначення 4. Підсистемою балансування завантаження (ПБЗ) ресурсів РПМС будемо називати сукупність апаратних, алгоритмічних, програмних, мовних, інформаційних та організаційних засобів, що забезпечують рівномірне завантаження паралельно працюючих ресурсів на всіх стадіях розробки, відлагодження та використання паралельних моделей складних динамічних систем з метою досягнення оптимальних показників функціонування середовища.

Згідно з цим визначенням ПБЗ повинна виконувати такі функції:

1. Побудова моделей завантаження (M3) на основі специфікації СІІМ-1 та віртуальної імплементації паралельної СДС-моделі.
2. Оцінка ефективності віртуальної паралельної моделі СДС за критеріями якості функціонування MIMD-систем та гетерогенних розподілених обчислювальних систем [2,3,4,5].
3. Девіртуалізація СДС-моделі на задану цільову структуру РПМС (рис. 2).
4. Статичне балансування паралельної імплементації топологічного аналізатора, генераторів рівнянь, вирішувачів рівнянь.
5. Оцінка ефекту від балансування шляхом безпосередніх замірів під час комплексного відлагодження девіртуалізованої паралельної СДС-моделі.
6. Порівняння ефективності за п.п. 2, 5, виявлення «вузьких місць».
7. Реєстрація замовлень з робочих місць користувачів (розробників моделі), формування черги на виконання замовлень з урахуванням даних за п.п. 1-6.
8. Оцінка завантаження РІІМС на верхньому (програмному) рівні.
9. Корегування розподілу ресурсів РПМС з позиції загального об’єму завантаження.

5. Основні вимоги до підсистеми

Розробка підсистеми балансування завантаження ресурсів належить до головних задач побудови РПМС. З урахуванням досягнутого рівня техніки паралельних ЕОМ, рівня системного та модельного програмного забезпечення РПМС, перспектив їх розвитку, наявного досвіду паралельного моделювання складних динамічних систем [1,3] поставимо такі вимоги до підсистеми:

• дружність до розробників паралельних моделей СДС;
• виконання функцій 1-6 на кожному робочому місці, а функцій 7-9 – в файл-сервері доступу до паралельних машин та кластерів; це означає поєднання децентралізованого та централізованого підходів до балансування;
• можливість зміни критеріїв оптимальності балансування завантаження в залежності від вирішуваних задач моделювання;
• наявність засобів статичного та динамічного балансування з адаптацією до потоків замовлень на моделювання та дослідження моделей СДС змінної структури;
• інтеграція з підсистемами діалогу та обміну інформацією, з мовами паралельного моделювання.

6. Висновки

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

Література

1. Розподілене паралельне моделююче середовище /Надєєв Д., Ротермель К., Святний В.А., Солонін О.М., Степанов І.С., Цайтц М. /.Збірник наукових праць ДонНТУ «Проблеми моделювання га автоматизованого проектування динамічних систем», вип. 29, 2001, с.
2. Rothermel К.: Grundlagen der verteilten Systeme. – IPVR der Universitat Stuttgart, 1998.
3. Святний В.А. Проблеми паралельного моделювання складних динамічних систем. Наукові праці ДонНТУ, серія ІКОТ, вип.. 6, 1999, с. 6-14.
4. Paralelle Simulationstechnik /V.A. Svjatnyi, L.P. Feldman, V.V. Lapko, E.-D. Gilles, M. Zeitz, A. Reuter, K. Rothermel/. Збірник наукових праць ДонНТУ «Проблеми моделювання та автоматизованого проектування динамічних систем», вип. 10, 1999, с. 9-19.  
5. Becker W.: Dynamische adaptive Lastbalancierung fur große, heterogen konkurrierende Anwendungen. IPVR der Universitat Stuttgart, Dissertation, 1995.
6. Poliak R.: Auswirkungen verschiedener Informationsebenen auf die Effizienz der dynamischen Lastbalansierung. IPVR der Universitat Stuttgart, Dissertation, 1999.