Охарактеризуйте хвильовий алгоритмголосування

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

Суть алгоритму. Ініціаторвідправляє по одному маркері кожному сусідньому сайту (по термінологіїтеоріїграфів - кожнійсуміжнійвершині).Кожний сайт, що одержав маркер, відправляєйого назад (якщо в ньогонемає причин цього не робити).Ініціаторпідраховуєотримані назад маркери і порівнюєїхкількістьізвідомоюйомукількістюсусідніхсайтів.Коли ці числа зрівняються (одностайнерішення), ініціаторвиконує процедуру return(OK).

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

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

107.Скільки способів використовується при Оцінюванні завантаження обчислювальних вузлів в процесі розв’язання задачі балансування навантаження?

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

- функціявідрозміруобсягуданих, щовідображаєскладністьалгоритму;

- моделькомунікаційміжзавданнями.

Перевагою аналітичногометодує можливість точноїоцінкитрудомісткостізадачізчастозмінюючимзавантаженням.

Недоліки методу:

- вимагаєвеличезнихзусильізбокупрограміста, щознаєалгоритми;

- можебутидоситьнеточнимувипадку, якщомодельдляоцінкишвидкостівиконаннядодатківнеточна.

2. Метод вимірюваннязавантаженняпроцесорівізадач. У більшості сучасних ЕОМ є лічильники часу (з точністю до мікросекунд), які можуть бути використані для вимірювання часу виконання кожної задачі.

Перевага методу: він є точним і не вимагає більших зусиль програміста.

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

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

MPI, DVI, OpenMP

109.Опишіть тип відмови Зупинка

Джерелом даної відмови є вузол.Вузол зупиняється і не перезапускається.Інші вузли можуть виявити такий стан.

110. Охарактеризуйте Керуюче програмне забезпечення МРО

SPEEDES - це об’єктно-орієнтоване програмне забезпечення, що реалізує дискретне моделювання, кероване подіями.Оскільки дана система була розроблена для розподіленого моделювання, воно реалізує три стратегії синхронізації (TIME WARP, BreathingTimeBuckets і BreathingTimeWarp).Стратегії синхронізації можуть бути обрані користувачем при виконанні імітаційного прогону.

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

111.Охарактеризуйте етап прийняття рішень у процесі балансування

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

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

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

112.Охарактеризуйте хвильовий фазовий алгоритм

Для вибраного Вами прикладу опишіть процедуру перенесення навантаження

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

Хвильовийалгоритм - церозподіленийалгоритм, щозадовольняє таким вимогам:

- кінечність. Кожне обчислення містить кінцеве число подій;

- успішнезавершення. Кожне обчислення містить хоча б одну подію return(OK);

- залежність.

У кожному обчисленні кожній події виклику процедури return(OK) передує (у змісті причинно-наслідкового зв'язку) яка-небудь подія на кожному сайті.Виконання хвильового алгоритму називається хвилею.Крім того, у виконанні алгоритму розрізняються сайти ініціатори і сайти не-ініціатори.

110 .Охарактеризуйте етап прийняття рішень у процесі балансування

Прийняття рішень у процесі балансування

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

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

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

111. Охарактеризуйте хвильовий фазовий алгоритм

Хвильовий алгоритм - це розподілений алгоритм, що задовольняє таким вимогам:

- кінечність. Кожне обчислення містить кінцеве число подій;

- успішне завершення. Кожне обчислення містить хоча б одну подію return(OK);

- залежність.

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

У фазовому алгоритмі кожний процес посилає рівно d повідомлень кожному сусідові по виходу. Тільки після того, як k повідомлень було отримано від кожного сусіда по входу, (k + 1) - повідомлення посилає кожному сусідові по виходу.

112. Для вибраного Вами прикладу опишіть процедуру перенесення навантаження

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

Стратегія динамічного перенесення навантаження RCL була розроблена для SPEEDES з метою підвищення її продуктивності.

У результаті досліджень було виявлено, що процедуру Migrate() варто виконувати наприкінці циклу GVT (GlobalVirtualTime). Дійсно, події вилучаються із системи під час обчислення GVT. Тому немає небезпеки, що виникне необхідність у відкоті, що торкнеться тільки що перенесене навантаження. Більше того, необхідно перенести тільки події і змінні мігруючих об'єктів, а дані, пов'язані з відкотом, не треба переносити, оскільки черга відкотів очищається наприкінці циклу GVT.

Результати тестування алгоритмів показали:

- для всіх трьох стратегій час виконання скорочується, якщо інтервал між процедурами Migrate() невеликий;

- частота виконання процедури Migrate() впливає на час моделювання істотно;

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

Дата добавления: 2015-11-14