Теоретичні Аспекти на Границі Продуктивності і Толерантність Дефекту в Паралельних обчисленнях.

1. Вступ........................................................................................................................................................... 3

1.1 Дослідницькі Питання........................................................................................................................................ 5

1.2 Дослідницька Методологія................................................................................................................................ 6

1.3 Дослідницький Вклад......................................................................................................................................... 6

2. Планування Мільтипроцессора (Частина I)........................................................................................... 8

2.1 Класифікація планування задач......................................................................................................................... 8

2.2 Межі і Складність на Плануванні Мультипроцессора...................................................................................10

3. Завантаження Балансування і Толерантність Дефекту (ДРУГА Частина)..................................... 12

3.1 Модель Дефекту................................................................................................................................................ 12

3.2 Надійність проти Придатності......................................................................................................................... 13

4. Підведення підсумків Статті.................................................................................................................. 15

4.1 Частина 1............................................................................................................................................................ 15

4.2 Частина 2............................................................................................................................................................ 17

5. Майбутня Робота..................................................................................................................................... 21

6. Посилання.................................................................................................................................................. 22

Додатки

Стаття1. Порівняння Оптимального Виконання Паралельної Архітектури..................................29

Стаття2. Максимальна Вигода Збільшення Числа Вивантажень у мультипроцессорному плануванні............................................................................................................................................... 67

Стаття 3. Користування Правилами Голомбо для Оптимальних Схем відновлення

толерантності помилок в рорзподіленгому обчисленні............................................................... 87

Стаття4. Користування Правилами Модуло для Оптимальних Схем відновлення в

в рорзподіленгому обчисленні.......................................................................................................... 105

Стаття5. Розширенні правила Голомбо в нових схемах відновлення в

Розподіленому залежному обчисленні............................................................................................. 125

Стаття 6. Оптимальні схеми відновлення при можливій толерантності помилки в

розподіленому обчисленні............................................................................................................... 143

Теоретичні Аспекти на Межі Продуктивності і

Толерантність Дефекту в Паралельному Обчисленні

Вступ

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

 

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

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

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

і час завершення. Час завершення виконання має назву «робочий інтервал.»

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

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

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

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

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

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

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

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

 

У Статті 2 ми представляємо щільну верхню межу при максимальній вигоді збільшення числа пріоритетних переривань для будь-якої паралельної програми.

У паралельних системах, що мають можливість обробки толерантності помилок, є можливість отримання техніки відмовостійкості. У найпростішому випадку, маючи два комп'ютери, один є активним, а один - для резервування. Якщо первинні комп'ютерні збої проявляються, то помічник просто приймає роботу. Для того, щоб отримати вищу придатність, треба використовувати більш ніж тільки два комп'ютери. Проте, це може бути найдорожча для формування велика кластерна система з багатьма резервними комп'ютерами. Це часто привабливіше, ніж терпіти невдачу з комп'ютерами, які вже активні в системі, але це важко для вирішення на якому з терплячих невдачу комп'ютерів треба виконувати. Це є особливо важко, якщо це рішення доведеться зробити статично до програмних запусків виконання. Мета тут - знайти схему повторного поширення, яка підтримує високу продуктивність навіть тоді, коли один або більше комп'ютерів ламаються. У статтях 3-4 ми відобразили чотири схеми різного повторного поширення. Доклад представлений у вигляді 2х частин: перша у вигляді статтяі, що відповідає першій частині і частині другій роботи, а також їх перетині перетин стандартних концепцій.

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

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

 

Сценарій два: коли графік пріоритетний, ми використовуємо різне число пріоритетних переривань.

У другій частині ми обговорюємо проблему повторного поширення завантаження серед працюючих комп'ютерів в паралельній системі, якщо один абл більше більше комп'ютерів в системі ламаються. Тут ми представляємо чотири алгоритми (Статтяи III, IV, V і VI) різного повторного поширення.

У Секції 3 класифікація дефектів має відношення до роботи в системі толерантності дефекту представленя.

Дослідницькі Питання

У цій дисертації три основні питання знаходяться в центрі.