1.2.1. Стратегія «розділяй та володарюй» та приклади застосування.
«Розділя́й та володарю́й» (англ. divide and conquer) в інформатиці — важлива парадигма розробки алгоритмів, що полягає в рекурсивному розбитті розв'язуваної задачі на дві або більше підзадачі того ж типу, але меншого розміру, і комбінуванні їх розв'язків для отримання відповіді до вихідного завдання. Розбиття виконуються доти, поки всі підзавдання не стануть елементарними.
Типовий приклад — алгоритм сортування злиттям. Щоб відсортувати масив чисел за зростанням, його розбивають на дві рівні частини; кожну сортують, потім відсортовані частини зливають в одну. Ця процедура застосовується до кожної з частин доти, поки сортовані частини масиву містять хоча б два елементи (щоб можна було її розбити на дві частини).
Час роботи цього алгоритму складає O(n log n) операцій, тоді як простіші алгоритми вимагають O(n2) часу, де n — розмір вихідного масиву.
Інші приклади важливих алгоритмів, в яких застосовується парадигма «розділяй та володарюй»:
Двійковий пошук
Метод бісекції
Швидке сортування
Швидке перетворення Фур'є
Множення Карацуби та інші ефективні алгоритми для множення великих чисел.
Розкладання завдання в послідовність різнорідних підзадач. Цей метод називають іноді методом "розділяй і володарюй".
У цьому методі зазвичай виділяється відносно невелике число підзадач. Наприклад: завдання - виконати програму на ЕОМ; підзадачі - ввести початковий текст програми; транслювати програму в машинні команди; приєднати до машинного коду стандартні процедури з бібліотеки; завантажити програму в оперативну пам'ять; запустити процес виконання; завершити процес виконання програми.
Результати рішення першої підзадачі стають початковими даними для другої підзадачі і т. д. Таким чином, тут використаний другий підхід в чистому вигляді - декомпозиція функції, завдання її суперпозицією простіших. Помітимо також, що така суперпозиція може бути задана послідовним з'єднанням машин Т'юринга.
На алгоритмічній мові цей метод може бути виражений записом процедур, що послідовно викликаються.
Найчастіше підхід "розділяй і володарюй" використовують через те, що він забезпечує швидші рішення, ніж ітераційні алгоритми. Основним недоліком алгоритмів типу "розділяй і володарюй" являється те, що ділять завдання на незалежні підзадачі. Коли підзадачі незалежні, це часто призводить до неприпустимо великих витрат часу, оскільки одні і ті ж підзадачі починають вирішуватися багато разів.
1.2.2. Стратегія балансування та приклади застосування.
Балансування навантаження (англ. load balancing) — це процес розподілення множини задач на множині ресурсів (обчислювальних одиниць), з метою зробити загальний час їхнього опрацювання більш дієвим. Балансування навантаження може оптимізувати час відповідь і запобігти нерівномірному навантаженню на окремі обчислювальні вузли тоді як інші обчислювальні вузли бездіють.
Балансування навантаження це предмет досліджень у галузі паралельних обчислень. Головні два підходи — статичні алгоритми, які не беруть до уваги стан різних машин, динамічні алгоритми, які зазвичай загальніші і дієвіші, але вимагають обміну інформацією між різними обчислювальними одиницями, що створює ризик падіння дієвості.
Інша властивість задач критична для дизайну алгоритму балансування навантаження це їхня здатність під час виконання бути розбитими на підзадачі. Модель деревоподібних обчислень використовує цю властивість. Наприклад, в алгоритмі видпакового опитування незадіяна одиниця виконання випадковим чином опитує інших виконавців допоки не знайде зайнятий і просить його поділити його задачу між ними.
На відміну від алгоритмів статичного розподілу навантаження, динамічні алгоритми беруть до уваги поточне навантаження кожної обчислювальної одиниці (також відомої як вузол) системи. Зі цим підходом, задачі можуть пути перерозподілені з перенавантаженого вузла на вільніший вузол, щоб пришвидшити опрацювання. Хоча ці алгоритми і набагато складніші спроєктувати, вони можуть дати чудові показники, зокрема, коли час виконання задач сильно різниться.
Динамічне балансування навантаження може бути модульнішим, бо необов'язково мати окремий вузол присвячений розподіленню роботи. Очевидно, що, якщо для ухвалення рішення алгоритм балансування навантаження вимагає занадто багато повідомлень між вузлами, то виникає ризик сповільнення розв'язання головної задачі.
Інфрасткуртура паралельних обчислень часть утворена з машин з різними характеристиками, які треба брати до уваги під час розподілення навантаження. Наприклад, малопотужні машини можуть отримувати запити, які вимагають меншого об'єму обчислень, або, у випадку однорідних запитів чи запитів з невідомою необхідною кількістю обчислень, отримувати менше запитів ніж потужніші машини.
При проектуванні деяких алгоритмів доводитися йти на раз-особисті компроміси, тобто по можливості збалансувати обчислювальні витрати на використання різних частин алгоритми. Метод балансування розглядається як балансування дерев. Дерево - важлива структура даних, вживана для зберігання, обробки і представлення інформації. Дерево складається з елементів^ вершин і зв'язків між ними (дуг). Серед вершин виділяється одна, яка називається коренем. Вона є батьківською по відношенню до інших пов'язаних з нею вершин. Усі вершини, пов'язані з коренем дугами, називаються нащадками. Кожна вершина в дереві, окрім кореня, має точно одну батьківську вершину і більше нащадків. Дерево має дві властивості:
• зв’язність: з кореня треба пройти по дугах до кожної вершини;
• воно не містить циклів, тобто замкнутих послідовностей вершин і дуг.
У комп'ютерних науках часто використовуються дерева, в яких усі вершини містять обмежене число нащадків (не більше двох).
Якщо це число 2 (0,1,2), то такі дерева називаються бінарними. Якщо у вершини два нащадки, те дерево ділиться на ліве піддерево і праве. Розрізняють ідеальні і вироджені дерева.
Ідеальне дерево - дерево, в якому усі вершини розташовуються на k рівнях :корінь - на 1-му, дві вершини на 2-му, чотири - на 3-му. Нова вершина може бути поміщена тільки на k+1 рівень.
Вироджене дерево - дерево, яке є лінійним списком елементів, впорядкованих за збільшенням або зменшенням інформаційних полів.
Критерій якості дерева - це довжина найдовшої гілки. На одиницю від цього значення відрізняється кількість рівнянь дерева, тобто її висота (на одиницю менше). Дерева мінімальної висоти мають максимальну кількість вершин на одному рівні. Таким чином хороші з точки зору пошуку і вставки вершини - це дерева мінімальної висоти. Вони мають мінімальну кількість вершин на кожному рівні.
Метод балансування - метод що дозволяє не допустити занадто поганих дерев.
Суть: дерево називається збалансованим, якщо висота hl лівого піддерева і висота hr правого піддерева для кожної вершини відрізняються не більше ніж на одиницю. Кращі зі збалансованих дерев є ідеальними. При включенні нової вершини в дерево може (але не обов’язково) збільшуватися висота одного з дерев.
Можливі 3 ситуації.
1. Вершина включається в піддерево меншої висоти, його висота збільшується на одиницю, дерево ставає збалансованим (ідеальним).
2. Піддерева мають однакову висоту. При включенні нової вершини, висота однієї з них збільшується на одиницю, дерево залишається збалансованим.
3. Вершина включається в піддерево більшої висоти, різниця висот ставає рівною двом. Дерево стає незбалансованим. Варіанти рішення : треба гілці одного з піддерев підняти на одну одиницю і одночасно на одиницю опустити інше. Ця модифікація призводить до зміни форми дерева. Піднімаючи ліве піддерево, включаючи його корінь, тим самим, робиться рівень кореня лівого піддерева вищим, ніж корінь самого дерева. Отже, корінь лівого піддерева стає коренем усього дерева. В цьому випадку доведеться змінити деякі зв'язки між вершинами, оскільки якщо корені міняються ролями, то на зворотні міняються і відношення пращур-нащадок.
При реалізації алгоритмів балансування потрібно знайти баланс між затримками при розподіленні завдань і обробкою самих завдань. Оптимальне рішення залежить від характеристики додатку, типу завдання, топології мережі і вузлів, вартості розгортання рішення. Для всіх цих проблем не існує ідеального алгоритму балансування який підходив би для будь-яких умовах, кожний підходить для конкретних складових і націлений на розв’язання чітких цілей. Необхідно провести класифікацію існуючих алгоритмів для того щоб використовувати наявні алгоритми максимально доцільно. Розробка такої класифікації стимулюватиме розробку нових алгоритмів і прискорить вдосконалення існуючих.
Для продуктивного і більш раціонального використання мереж з розподіленими розрахунками необхідно реалізувати дві вимоги які часто конкурують. Перш за все це те що процесори повинні бути зайняті корисною роботою. Другий пункт накладає вимоги до міжпроцесорного зв’язку – він повинен бути мінімальним. Для більшості розподілених систем розрахунку вартість налагодження контакту зростає при збільшені кількості і об’єму завдань. Важливо мінімізувати результуючу суму з них або максимум з них. Всі алгоритми балансування навантаження можна розділити на три групи: динамічні, статичні, адаптивні.
Динамічні алгоритми розподілення навантаження застосовують інформацію про стан системи для прийняття рішення про розподілення навантаження. Статичні алгоритми не слідкують за станом системи. В даній групі алгоритмів рішення про розподілення навантаження приймається заздалегідь і не змінюється в процесі роботи. Прикладом таких алгоритмів може слугувати RR (round robin), коли відбувається присвоєння задач до розрахункових вузлів по круговому циклу. Перша задача присвоюється першому розрахунковому вузлу друга другому і так до останнього вузла, потім все починається спочатку. Найбільш розповсюджена реалізація даного алгоритму на DNS-сервері шляхом повторення IP адрес вузлів в необхідній пропорції розподілення навантаження. Також до статичних відносять Simulated Annealing or Genetic Algorithms (генетичний алгоритм) який забезпечує змішану процедуру розподілу завдань за обчислювальними ресурсами з використанням методів оптимізації. Динамічне балансування передбачає перерозподіл розрахункової потужності на вузлах в ході виконання програми і завдяки цьому можуть обігнати статичні алгоритми. Завдяки тому, що динамічні алгоритми відслідковують і аналізують такі параметри як завантаження розрахункових вузлів, пропускну здатність лінії, частоту обміну повідомленнями між логічними процесами, це призводить до збільшення накладних розрахунків на балансування в порівнянні із статичними алгоритмами.
Адаптивні ж алгоритми використовують поєднання двох вище наведених алгоритмів. В залежності від умов і поточних параметрів розрахункової системи вибирається найбільш доречний алгоритм. Наприклад Derbal[1] використовує масштабоване планування основане на ентропії розрахункової системи, а вже за допомогою ланцюгів Маркова сумує динамічні служби в мережі. Для прикладу є система[2] з підтримкою поколінь планування (the introduction of the Generational Scheduling) з реплікацією завдань. Цей алгоритм адаптується до змін в продуктивності з реструктуризацією завдань.
Відповідно до цілісності передачі завдання розділяють на витісняючи (preemptive) і невитісняючі (non-preemptive) алгоритми балансування. Не витісняючи алгоритми можуть передавати задачі які ще не почали розв’язувати. Витісняючи алгоритми здатні передавати задачі які розв’язані частково. Прикладом застосування не витісняючого алгоритму – сервер NetWare, витісняючого – ОС Windows NT, OS/2, VAX/VMS, UNIX.
Розділяють динамічні алгоритми балансування які враховують топологію і які її не враховують. По централізованості динамічні алгоритми розділяють на групи: централізовані, повністю розподілені, ієрархічні, суміщені.
Потенційно централізовані алгоритми менш надійні, ніж повністю розподілені, оскільки збій в роботі центрального компоненту призведе до збою всієї системи. Також центральний компонент потрібно забезпечити великою пропускною здатністю. Ієрархічні алгоритми частково вирішують ці проблеми, уникнути їх можна лише при повністю розподілених системах. Перевагою централізованого алгоритму є спрощення контролю і налагодження. Централізований спосіб підходить тільки тоді коли завдання може виконуватися незалежно і асинхронно відповідно до центрального процесора[3]. Необхідно мінімізувати обмін інформацією між центральним і підлеглим вузлом. Прикладом може слугувати алгоритм Least Load. Це динамічний алгоритм із зворотнім зв’язком. Завдання надсилається на той розрахунковий вузол який менш всього завантажений. Завантаженість може визначатися середнім часом відповіді.
У повністю розподіленій системі з N обчислювальними ресурсами для прийняття рішення про планування ресурс має обмінятись 2(N −1) повідомленнями[4]. Частковим прикладом для балансування такого типу може слугувати алгоритм[5] Ричарда Карпа (Richard Karp) який використовується для однорангових мереж (Р2Р). В даному алгоритмі інформація про однорангові вузли зберігається локально в каталогах кожного «едмеієнту» мережі. Таким чином значну частину проблем балансування було знято з сервера і передано на вузли.
Прикладом ієрархічної системи є мережа з проміжним забезпеченням gLite в якому система управління потоком знань(WMS) відповідає за розподіл і управління завдань. WMS контролює процес виконання завдань і відправку результатів замовнику. В gLite для балансування навантаження використовується алгоритм «максимальної/нечіткої оцінки» які проводять відбір ресурсів по відповідності до поставлених задач. В суміщеній розподіленій системі на список завдань кожний розрахунковий вузол формує список доступних ресурсів. Актуальну інформацію про стан системи можна отримати як від кожного вузла напряму так і від центральної інформаційної системи. Така модель реалізована в проміжному забезпечені ARC проекту NorduGrid.