Ще одна ключова стаття за темою магістерської роботи - «Девіртуалізація віртуальних паралельних моделей складних динамічних систем за критеріями балансування завантаження» [
]. У цій статті запропоновано реалізація окремих компонентів моделі завантаження розподіленого паралельного моделюючого середовища, що забезпечують оптимальне виконання моделей складних динамічних систем за критеріями балансування завантаження. Також вводиться поняття девіртуалізації віртуальної паралельної моделі і критерії девіртуалізації стосовно паралельної моделі складної динамічної системи. Також розглянуто шляхи оптимізації віртуальної паралельної моделі і власне паралельної MPI-програми, що реалізує цю модель.
Серед робіт, що виходять за рамки ДонНТУ, варто відзначити роботи професора
Якобовського Михаїла Володимировича
([
11], [
12], [
13]). У даних роботах проведені дослідження статичного та динамічного балансування завантаження стосовно різних задач (зокрема стосовно задач інтегрування, задач горіння і т.д.). Також розглянуто критерії декомпозиції графів і сіткових моделей.
Основні результати, наявні до моменту написання автореферату.
В теперішній час моделювання широко використовується в багатьох галузях науки і техніки. Згідно з визначенням в вікіпедії, моделювання - дослідження об'єктів пізнання на їх моделях; побудова і вивчення моделей реально існуючих об'єктів, процесів або явищ з метою отримання пояснень цих явищ, а також для передбачення явищ, які цікавлять дослідника. Одним з найпопулярніших став метод комп'ютерного моделювання, який передбачає в якості моделі комп'ютерну програму. Методика створення комп'ютерних моделей надана в роботі [
4].
Більшості об'єктів, що моделюються, внутрішньо властива складність, яка переноситься на комп'ютерну модель у вигляді обчислювальної складності моделюючої програми. У зв'язку з великою обчислювальною складністю час виконання моделюючої програми може перевищити всі допустимі межі. Для зменшення часу виконання моделюючої програми комп'ютерні моделі повинні бути розпаралелені для паралельного виконання на паралельній обчислювальній машині. Таким чином, паралельна комп'ютерна модель (далі паралельна програма) складається з деякої множини логічних процесів, які паралельно виконуються на деякій множині процесорів паралельної обчислювальної машини, взаємодіють один з одним за допомогою обмінних (комунікаційних) операцій та в сукупності рішають задачу моделювання.
Збалансоване завантаження обчислювальних вузлів (процесорів) припускає рівномірну завантаженість процесорів арифметичними операціями. Однак при збалансованій завантаженості процесорів арифметичними операціями може виникнути дисбаланс навантаження на мережу (комунікаційне середовище), яке з'єднує процесори паралельної обчислювальної машини між собою і забезпечує обмін даними між логічними процесами. Таким чином, через перевантаження деяких ліній комунікаційної мережі деякі логічні процеси можуть простоювати більшу частину свого часу в очікуванні даних від інших процесів, без яких вони не можуть продовжувати свою роботу.
Незбалансованість завантаження неминуча з кількох причин, серед яких можна виділити неоднорідність структури моделі (різні логічні процеси вимагають різних обчислювальних потужностей) і неоднорідність структури паралельної обчислювальної машини (різні обчислювальні вузли можуть мати різну обчислювальну потужність; між різними вузлами може бути різна пропускна здатність комунікаційної мережі; в процесі роботи паралельної програми можуть звільнитися раніше зайняті вузли, які можуть бути використані для розвантаження найбільш завантажених вузлів або навпаки більш привілейований користувач може запросити частину вузлів для негайного звільнення від поточної задачі з метою їх використання у своїй задачі; деякі вузли можуть використовуватися одночасно для вирішення кількох задач у режимі поділу часу, при цьому доля процесорного часу, яка виділяється даним вузлом на рішення конкретної задачі, також може мінятися в ту або іншу сторону; деякі обчислювальні вузли або комунікаційні лінії зв'язку можуть вийти з ладу).
Таким чином, основною метою підсистеми балансування завантаження є мінімізація загального часу рішення задачі (часу моделювання). При появі нових завдань підсистема балансування завантаження повинна прийняти рішення про те, де (на якому обчислювальному вузлі) слід виконувати обчислення, пов'язані з цим новим завданням. Крім того, балансування передбачає перенесення (міграцію) частини обчислень з найбільш завантажених обчислювальних вузлів на менш завантажені вузли.
Балансування завантаження застосовується на двох етапах: на етапі декомпозиції задачі на підзадачі (процеси) і на етапі відображення цих процесів на обчислювальне середовище. Декомпозиція задачі є етапом процесу створення паралельної програми і призначена для поділу задачі на підзадачі. У результаті декомпозиції розподіленої програми з'являється набір підзадач, які паралельно вирішують задачу. Ці підзадачі можуть бути незалежними або пов'язаними одна з одною за допомогою обміну даними. Відображення підзадач на обчислювальне середовище є окремим етапом, що дозволяє розподілити підзадачі, отримані на етапі декомпозиції, між процесорами.
Слід розрізняти статичне та динамічне балансування. Статичне балансування виконується до початку виконання розподіленої програми. При розподілі логічних процесів за процесорами повинен використовуватися досвід попередніх виконань. Однак попереднє розміщення логічних процесів за процесорами без будь-яких втручань під час виконання не завжди дає необхідний ефект за причинами неоднорідності паралельної обчислювальної машини і самої паралельної програми, які описані вище. У такому разі доцільно застосовувати динамічне балансування завантаження. Динамічне балансування передбачає перерозподіл обчислювального навантаження між вузлами під час виконання програми. Програмне забезпечення, що реалізовує динамічне балансування завантаження, під час своєї роботи має обчислювати завантаження обчислювальних вузлів, пропускну здатність ліній зв'язку, частоту обмінів повідомленнями між логічними процесами розподіленої програми і т.д. На підставі зібраних даних (як щодо розподіленої програми, так і щодо обчислювального середовища) приймається рішення щодо перенесення логічних процесів з одного вузла на інший. Зазвичай рішення задачі балансування завантаження складається з чотирьох кроків: оцінка завантаження обчислювальних вузлів, ініціація балансування завантаження, прийняття рішення щодо балансування та переміщення об'єктів.
На етапі оцінки завантаження обчислювальних вузлів для визначення дисбалансу завантаження необхідні дані щодо роботи процесора, які включають завантаження процесора, час простою процесора, швидкість передачі інформації за лініями зв'язку і т.д., а також дані щодо роботи розподіленої програми, які включають час виконання окремої задачі, час простою, інтенсивність обміну інформацією та ін. Дуже важливо володіти такою інформацією як комунікаційна модель. Комунікаційна модель містить важливу інформацію щодо прийняття рішень про переміщення задач при балансуванні завантаження. При необхідності перемістити об'єкт з перевантаженого процесору A на недовантажений процесор B, доцільно вибрати для переміщення той об'єкт, який найбільш інтенсивно здійснює обмін повідомленнями з задачами, вже розташованими на B.
Оцінка завантаження процесора і об'єкта може бути здійснена кількома способами. Один із способів (аналітичний), часто використовується при статичному балансуванні завантаження, полягає у приблизній оцінці завантаження кожного об'єкту на основі знань щодо програми. Цей метод дозволяє передбачити майбутнє зміну завантаження і відреагувати на нього. Недолік цього методу полягає в тому, що він може бути досить неточним у випадку, якщо модель для оцінки швидкості виконання програм не є точною. Інший спосіб збору даних щодо завантаження полягає у вимірюванні завантаження процесорів. Більшість сучасних обчислювальних машин забезпечено лічильниками часу (з точністю до мікросекунд), які можуть бути використані для вимірювання часу роботи задачі і часу простою. Наведені два методи збору даних про завантаження можна поєднувати, доповнюючи метод, заснований на вимірюванні продуктивності здатністю прогнозу аналітичного методу оцінки.
Занадто часте виконання балансування завантаження може призвести до того, що рішення задачі тільки сповільниться. Витрати на саме балансування можуть перевершити можливу вигоду від її проведення. Отже, для продуктивності балансування необхідно якимось чином визначати момент її ініціалізації. Це може бути момент виникнення дисбалансу завантаження, визначений на підставі виміряних значень завантаження процесорів або ліній зв'язку, або передбачений аналітично на підставі знань щодо структури паралельної програми. Далі слід визначити ступінь необхідності балансування шляхом порівняння можливої користі від її проведення та витрат на неї. При цьому дисбаланс завантаження може визначатися синхронно та асинхронно. При синхронному визначенні дисбалансу всі процесори переривають роботу в певні моменти синхронізації і визначають дисбаланс завантаження шляхом порівняння завантаження окремого процесора з загальним середнім завантаженням. При асинхронному визначенні дисбалансу кожен процесор зберігає історію свого завантаження. У цьому випадку момент синхронізації для визначення ступеня дисбалансу відсутній. Обчисленням обсягу дисбалансу займається фоновий процес, що працює паралельно з програмою. Таким чином, можна виділити централізовану та децентралізовану стратегії балансування. При централізованій стратегії спеціальний керуючий процес збирає глобальну інформацію щодо стану всієї обчислювальної системи і приймає рішення про переміщення задач для кожного з процесорів. При децентралізованій стратегії на кожному процесорі виконується фоновий процес, який займається балансуванням завантаження і обмінюється інформацією щодо стану завантаження з іншими процесорами.
Висновок
Для проведення балансування завантаження під час вирішення цільової задачі необхідно розробити спеціальне програмне забезпечення, яке включає до себе програмні засоби, що забезпечують оцінку стану обчислювального середовища, керуючу програму, що приймає рішення про момент проведення балансування, і про те, які логічні процеси слід перемістити з одного процесора на інший, а також програмні засоби, що реалізують переміщення процесу з одного процесора на інший (міграції). У даний момент ведеться пошук та аналіз можливостей різних бібліотек для здійснення міграції процесів з урахуванням архітектури та програмних засобів кластеру ДонНТУ.
Важливе зауваження: Під час написання даного автореферату магістерська робота ще не закінчена. Остаточне завершення: 15 грудня 2011. Повний текст роботи та матеріали за темою можуть бути отримані у мене або у мого наукового керівника після зазначеної дати.
Література
-
Абрамов Ф.А., Фельдман Л.П., Святный В.А. Моделирование динамических процессов рудничной аэрологии. Киев, Наукова думка, 1981, 291 с.
-
Святний В.А. Паралельне моделювання складних динамічних систем // Моделирование – 2006: Международная конференция. Киев, 2006 г. – Киев, 2006. – С. 83–90.
-
Миков А.И., Замятина Е.Б., Козлов А.А. Оптимизация параллельных вычислений с применением мультиагентной балансировки. // Труды конференции ПАВТ-2009, с. 599-604, Нижний Новгород, Россия, 2009.
-
Фельдман Л.П., Святный В.А., Рэш М., Цайтц М. Научная область: параллельное моделирование. / Научные работы Донецкого национального технического университета. Серия: Проблемы моделирования и автоматизации проектирования [Электронный ресурс]. — Режим доступа: http://www.nbuv.gov.ua/portal/natural/Npdntu/Pm/2008/08flpfps.pdf
-
Надеев Д.В. Девиртуализация виртуальных параллельных моделей сложных динамических систем по критериям балансирования загрузки. / Научные работы Донецкого национального технического университета. Серия: Проблемы моделирования и автоматизации проектирования [Электронный ресурс]. — Режим доступа: http://www.nbuv.gov.ua/portal/natural/Npdntu_pm/2008/08ndvolb.pdf
-
Cвятний В.А., Надєєв Д.В. Підсистема балансування завантаження ресурсів розподіленого паралельного моделюючого середовища. / Наукові праці Донецького національного технічного університету. Серія: Інформатика, кібернетика та обчислювальна техніка. (ИКВТ-02) випуск 39. – Донецьк, ДонНТУ. – 2002. – С. 264-270.
-
Голуб С.В. Динамическая балансировка загрузки процессоров в многопроцессорных системах [Электронный ресурс] / Портал магистров ДонНТУ. — Режим доступа: http://masters.donntu.ru/2002/fvti/golub/magwork/index.html
-
Xiao Qin, Hong Jiangy, Adam Manzanaresz, Xiaojun Ruan, Shu Yinyy Communication-Aware Load Balancing for Parallel Applications on Clusters [Электронный ресурс]. — Режим доступа: http://digitalcommons.unl.edu/cgi/viewcontent.cgi?article=1051&context=csearticles&sei-redir=1
-
Техническая документация по установке и использованию менеджера распределённых ресурсов для вычислительных кластеров torque [Электронный ресурс]. — Режим доступа: http://www.adaptivecomputing.com/resources/docs/torque/pdf/TORQUE_Administrator's_Guide.pdf
-
Техническая документация по установке и использованию планировщика задач для вычислительных кластеров maui [Электронный ресурс]. — Режим доступа: http://www.adaptivecomputing.com/resources/docs/maui/pdf/mauiadmin.pdf
-
Корнилина М.А., Якобовский М.В. Динамическая балансировка загрузки процессоров при моделировании задач горения. // Материалы конференции "Высокопроизводительные вычисления и их приложения", 30 октября - 2 ноября 2000 года, Черноголовка.
-
Якобовский М.В. Балансировка загрузки процессоров [Электронный ресурс]. — Режим доступа: http://www.software.unn.ac.ru/ccam/files/ipa_f_2_01.pdf
-
Якобовский М.В. Динамическая балансировка загрузки [Электронный ресурс]. — Режим доступа: http://lira.imamod.ru/lit/msu2009/MSU_5i.ppt
