Паралельні і розподілені обчислення (стр. 2 из 3)

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

Припустимо, що з яких-небудь причин n операцій з N ми вимушені виконувати послідовно. Причини можуть бути різними. Наприклад, операції можуть бути послідовно зв'язані інформаційно. І тоді без зміни алгоритму їх не можна реалізувати інакше. Відношення b = n/N назвемо часткою послідовних обчислень.

НАСЛІДОК (2-Й ЗАКОН АМДАЛА)

Хай система складається з s однакових простих універсальних пристроїв. Припустимо, що при виконанні паралельної частини алгоритму всі s пристроїв завантажені повністю. Тоді максимально можливе прискорення рівне

Позначимо через p пікову продуктивність окремого ФП. Оскільки якщо система складається з s пристроїв однакової пікової продуктивності, то прискорення системи дорівнює сумі завантаженості всіх пристроїв:

Якщо всього виконується N операцій, то серед них bNоперацій виконується послідовно і (1 - b)N паралельно на s пристроях по (1 - b)N/sоперацій на кожному. Можна вважати, що всі послідовні операції виконуються на першому ФП. Всього алгоритм реалізується за час

На паралельній частині алгоритму працюють як перший, так і вся решта пристроїв, витрачаючи на це час:

для 2 ≤ і ≤ n. Тому p₁ = 1 і

Отже

НАСЛІДОК (3-Й ЗАКОН АМДАЛА)

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

Потоки– це об'єкти, які отримують час процесора. Час звичайно виділяється квантами. Квант часу – це інтервал, що є у розпорядженні потоку до тих пір, поки час не буде у нього відібрано і передано в розпорядження іншого потоку. Потрібно мати на увазі, що кванти виділяються не програмам або процесам, а породженим ними потокам. Як мінімум, кожен процес має хоча б один потік, але Windows 95 і Windows NT дозволяють запустити в рамках процесу скільки завгодно потоків.

Два головні типи потоків — асиметричні і симетричні. Частіше всього на персональних комп'ютерах використовують асиметричні потоки. Асиметричні потоки (Asymmetric threads) — це потоки, що вирішують різні задачі і, як правило, не розділяють ресурси. Один з таких потоків відповідає за друк; інший обробляє повідомлення від клавіатури і миші; третій завідує автоматичним збереженням документа користувача. Симетричні потоки (Symmetric threads) виконують одну і ту ж роботу, розділяють одні ресурси і виконують один код.

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

- Реального часу (Real time)

- Високий (High)

- Нормальний (Normal)

- Фоновий (Idle)

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

Процес – це виконання програми. Компоненти процесу – це програма , що виконується, її дані , її ресурси(пам’ять), стан виконання. Процес володіє своїм адресним простором, і його стан характеризується наступною інформацією: таблиці сторінок, дескриптори файлів, замовлення на ввід/вивід інформації, регістри.

Процеси або нитки можуть взаємодіяти:

1. Через розподілення пам’яті (ОП, зовн.)

2. Завдяки передачі повідомлень

При взаємодії процесів через спільну пам'ять необхідна синхронізація їх виконання.

Розрізняють 2 види синхронізації:

1. Взаємне виключення критичних інтервалів

2. Координація процесів

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

Термін безпека потоків означає підтримку об’єктів в дійсному стані при одночасному звертанні до них декількох потоків. Стандартний засіб уникнення непередбачених ситуацій – це синхронізація. Синхронізація дозволяє задавати критичні секції. Критичні секції коду – в кожен окремий момент часу може входити 1 потік, гарантуючи, що будь-які тимчасові недійсні стани об’єкту будуть невидимі його клієнтам.

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

1. Гонки (Race conditions)

2. Тупіки(Deadlocks).

Правила використання потоків

Потоки необхідно використовувати:

1. Для досягнення підвищеного паралелізму.

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

2. З метою спрощення конструкції.

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

3. Для ефективного використання процесорного часу.

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

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

Застосовується до даних, які оперують великими масивами чисел. Проводиться в два етапи:

1) розділення даних

2) використання для розподілу основного завдання на окремі задачі цього розділення

Секціонування здійснюється різними способами, буває різних типів:

1. секціонування за вихідними даними

2. секціонування за вхідними даними

3. секціонування за вхідними і вихідними даними

4. секціонування за проміжними даними

Правило власника обчислень – кожне секціонування має виконувати обчислення над всіма даними, якими володіє.

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

Приклад: визначення мінімуму або максимуму з набору чисел

2. Декомпозиція послідовних програм за вихідними даними

Застосовується до даних, які оперують великими масивами чисел. Проводиться в два етапи:

1) розділення даних

2) використання для розподілу основного завдання на окремі задачі цього розділення

Секціонування здійснюється різними способами, буває різних типів:

1. секціонування за вихідними даними

2. секціонування за вхідними даними

3. секціонування за вхідними і вихідними даними

4. секціонування за проміжними даними

Секціонування за вихідними даними – такий тип секціонування можливий, коли вихідні дані не залежать один від одного і кожен вихідний елемент є лише функцією входу

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

3. Дослідницька декомпозиція послідовних програм

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

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

Приклад: пятнашка

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

Застосовується до даних, які оперують великими масивами чисел. Проводиться в два етапи:

3) розділення даних

4) використання для розподілу основного завдання на окремі задачі цього розділення

Секціонування здійснюється різними способами, буває різних типів: