Балансування навантаження (англ. load balancing) — це процес розподілення множини задач на множині ресурсів (обчислювальних одиниць), з метою зробити загальний час їхнього опрацювання більш дієвим. Балансування навантаження може оптимізувати час відповіді і запобігти нерівномірному навантаженню на окремі обчислювальні вузли тоді як інші обчислювальні вузли бездіють.

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

Алгоритм балансування навантаження завжди намагається відповідати певній задачі. Серед іншого, природа задач, алгоритмічна складність, архітектура заліза, на якому алгоритм виконуватиметься, а також вимоги до помилкостійкості^[en] повинні бути взяті до уваги. Отже, доводиться йти на різні поступки, щоб якнайліпше відповідати потребам певного застосування.

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

Повне знання про час виконання кожної задачі дозволяє досягти найліпшого розподілення навантаження (див. дуже простий алгоритм приросткових сум^[en], що дає хороше наближення).^[1] На жаль, таких повних знань зазвичай немає.

З цієї причини існує декілька підходів, щоб отримати якесь уявлення про різні потрібні часи виконання. По-перше, у щасливому випадку, коли ми маємо відносно однорідний розмір, можливо припустити, що кожна задача має потребує середнього часу виконання. Інакше, якщо час виконання дуже нерівний, потрібні мудрованіші підходи. Один з них це додати певні метадані до кожної задачі. Покладачаючись на статистику часу виконання задач з подібними метаданими, можна зробити висновки для майбутніх задач.^[2]

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

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

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

Алгоритм балансування навантаження статичний, якщо для розподілу задач він не бере до уваги стан системи. Стан системи включає міри як-от рівень навантаження^[en] (а іноді й перенавантаження) деяких процесорів. Натомість, припущення про усю систему робляться заздалегідь, наприклад, про час прибуття задач і ресурсні вимоги прибулих задач. Також алгоритм має глибшу інформацію про систему, як-от кількість процесорів, їхні потужності і швидкість зв'язків. Отже, статичне балансування навантаження намагається призначити відому множину задач доступним процесорам з метою унайменшити певну функцію швидкодії.

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

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

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

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

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

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

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

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

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

З точки зору ієрархії апаратних структур існує дві головні категорії алгоритмів балансування навантаження. З одного боку це такі, де завдання призначаються «розпорядником» і виконуються «робітниками», які доповідають розпорядникові про поступ у своїй роботі, а розпорядник бере відповідальність з призначення і перепризначення завдань у разі динамічного алгоритму. Література покликається до такого розкладу як до архітектури «Розпорядник-працівник». З іншого боку, керування може бути розподілене між різними вузлами. Тоді алгоритм балансування навантаження виконується на кожному з них і відповідальність за призначення завдань (як і за перепризначення і за потреби розбиття) спільна. Друга категорія має на увазі динамічні алгоритми.

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

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

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

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

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

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

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

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

Статичне балансування навантаження завжди можливе навіть геть без знання часу виконання.

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

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

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

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

Також існують інші методи призначення завдань:

• Геш: розподіляти запити згідно з геш-таблицею.
• Сила подвійного вибору: вибрати два сервери й обрати вдаліший з них.