Русский

  English

ДонНТУ   Портал магістрів

Волохова Галина Вікторівна

Факультет комп'ютерних наук та технологій

Кафедра прикладної математики і інформатики

Спеціальність Інженерія програмного забезпечення

Балансування навантаження в паралельних обчислювальних системах

Науковий керівник: к.т.н., доц. Михайлова Тетяна Василівна

Резюме Біографія Реферат

Реферат за темою магістерської роботи

Зміст

• Вступ
• 1. Особливості розподіленої системи

                1.1 Загальні відомості про балансування навантаження
                1.2 Етапи створення розподіленої програми

• 2. Методи балансування

                2.1 Статичне балансування
                2.2 Динамічне балансування

• 3. Динамічне балансування та перенесення навантаження

                3.1 Опис RCL–cтратегії перенесення навантаження
                        3.1.1 Дії першого рівня
                        3.1.2 Дії другого рівня
                        3.1.3 Випадковий алгоритм
                        3.1.4 Алгоритм, заснований на комунікаціях
                        3.1.5 Алгоритм, заснований на обчисленні навантаження
                3.2 Реалізація RCL–алгоритма

• Висновок
• Список джерел

Вступ

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

1. Особливості розподіленої системи

1.1 Загальні відомості про балансування навантаження

Балансування навантаження (Load Balancing) застосовується для оптимізації виконання паралельних обчислень за допомогою паралельної обчислювальної системи, воно припускає рівномірне навантаження процесорів багатопроцесорної ЕОМ. При появі нових завдань програмне забезпечення, що реалізує балансування, має прийняти рішення про те, на якому процесорі (обчислювальному вузлі) слід виконувати обчислення, пов'язані з цією новою задачею. балансування навантаження також передбачає перенесення частини обчислень з найбільш завантажених процесорів на менш завантажені [1].

1.2 Етапи створення розподіленої програми

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

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

Однак під час роботі паралельної програми може виникнути конфлікт між збалансованим розподілом об'єктів по процесорах і низькою швидкістю обмінів даними між цими процесорами. Деякі процесори можуть простоювати, тоді як інші будуть перевантажені, якщо комунікація між процесорами ведеться на низькій швидкості [3]. З іншого боку, витрати на комунікацію можуть бути великими для збалансованої системи. Саме тому метод балансування повинен бути підібраний таким чином, щоб обчислювальні вузли були завантажені рівномірно, а швидкість обміну даними між процесорами була оптимальною.

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

Дисбаланс навантаження може виникнути з кількох причин:

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

На сьогоднішній день універсального методу боротьби з дисбалансом навантаження не існує.

2. Методи балансування

Методи балансування поділяють на статичні та динамічні.

2.1 Статичне балансування

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

Це пояснюється тим, що:

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

2.2 Динамічне балансування

Динамічне балансування передбачає перерозподіл навантаження на обчислювальні вузли під час виконання програми. Для такого балансування використовують програмне забезпечення, яке визначає:

• завантаження процесорів;
• пропускну спроможність ліній зв'язку між вузлами;
• частоту обміну даними між логічними процесами паралельного програми та ін.

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

3 Динамічне балансування та перенесення навантаження

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

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

3.1 Опис RCL–cтратегії перенесення навантаження

Розглянемо три алгоритма динамічного перенесення навантаження:

• випадковий алгоритм (random, R);
• алгоритм, заснований на комунікаціях (communication, С);
• алгоритм, заснований на обчисленні навантаження (load, L).

Будемо надалі називати ці алгоритми балансування RCL–стратегією.

Алгоритм перенесення об'єкта або процесу з одного обчислювального вузла досить складний. Однак введення деяких припущень може знизити складність цього алгоритму. Нехай:

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

RCL стратегія використовує дворівневий процес прийняття рішень (централізований і децентралізований підходи), який передбачає:

• центральний процес–координатор приймає рішення про перенесення навантаження;
• кожен відсилає повідомлення процес вибирає навантаження, яке слід перенести [10].

3.1.1 Дії першого рівня

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

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

Якщо в перенесенні навантаження немає необхідності, процесор посилає повідомлення про це іншим вузлам і кожен вузол продовжує обробляти свої завдання.

3.1.2 Дії другого рівня

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

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

3.1.3 Випадковий алгоритм

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

До переваг випадкового алгоритму можна віднести: легкість реалізації і порівняно невеликий час вибору об'єктів для перенесення.

3.1.4 Алгоритм, заснований на комунікаціях

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

3.1.5 Алгоритм, заснований на обчисленні навантаження

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

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

3.2 Реалізація RCL–алгоритма

Стратегія динамічного перерозподілу навантаження RCL була реалізована в системі SPEEDES (Synchronous Parallel Environment for Emulation and Discrete–Event Simulation — синхронна паралельна середа для емуляції і моделювання дискретних подій) з метою підвищення її продуктивності.

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

Висновок

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

Частота виконання процедури перерозподілу істотно впливає на час моделювання.

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

При написанні даного реферату магістерська робота ще не завершена. Остаточне завершення: грудень 2012 року. Повний текст роботи та матеріали по темі можуть бути отримані у автора або його керівника після зазначеної дати.

Список джерел

1. Замятина Е. Б., Ефимов А. Ю., Козлов А. А., Усынин А. С. Оптимизация времени выполнения параллельных вычислений — Пермь, 2009.
2. Немнюгин С.А., Средства программирования для многопроцессорных вычислительных систем — Санкт–Петербург, 2007.
3. Миков А.И., Замятина Е.Б., Козлов А.А. Оптимизация параллельных вычислений с применением мультиагентной балансировки — Пермь, 2007.
4. Load Balancing in Parallel Computers. Электронный ресурс. Режим доступа: http://www.inspirenignite.com/load-balancing-in-parallel-computers/
5. Бельков Д.В., Алгоритмы балансировки загрузки процессоров параллельной вычислительной системы. Электронный ресурс. Режим доступа: http://ea.donntu.ru:8080/jspui/bitstream/123456789/6282/1/belkov.pdf
6. Афраймович Л.Г. Модели и методы эффективного использования распределенных вычислительных систем — Нижний Новгород, 2012
7. Ardhendu Mandal and Subhas Chandra Pal, An Empirical Study and Analysis of the Dynamic Load Balancing Techniques Used in Parallel Computing Systems. Электронный ресурс. Режим доступа http://arxiv.org/ftp/arxiv/papers/1109/1109.1650.pdf
8. Marc H. Willebeek–LeMair, Anthony P. Reeves, Transactions on parallel and distributed systems, vol.4, # 9 — 1993, c. 979
9. Балансировка нагрузки в распределенных системах. Электронный ресурс. Режим доступа http://intuit4.intuit.ru/studies/courses/1146/238/lecture/3287?page=1
10. Принципы построения параллельных вычислительных систем. Электронный ресурс. Режим доступа http://wiki.auditory.ru/Принципы_построения_параллельных_вычислительных_систем