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

Реферат

Паралельні і розподілені обчислення

Вступ

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

Направлений на збільшення ефективності роботи комп’ютерної системи.

Удосконалення комп’ютерів призводить до збільшення їх продуктивності, тобто до збільшення можливості виконання більшої кількості операцій за 1 часу. Продуктивність вимірюється у MIPS (мільйон ітерацій з плаваючою комою за секунду).

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

Пікова продуктивність – сумарна продуктивність АЛП.

Ефективність системи – відношення реальної продуктивності до пікової. Якщо продуктивність системи <0.5 , то система працює незадовільно.

Способи паралельної обробки:

1. Чистий паралелізм .

2. Конвеєризація.

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

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

Якщо конвеєр кроків містить nкроків і кожен з них спрацьовує за 1 часу, то час обробки nнезалежних операцій складе <L + n – 1.

Всі операції бувають двох типів: векторні і скалярні.

Якщо хоча б один елемент команди є вектором, то команда називається векторною. Тоді кількість операцій визначається: L+n-1+s, де s - час ініціалізації вектора. Векторні операції ефективні тоді, коли n>>s, в протилежному випадку вектори перетворюються в скаляри, тобто, оскільки ні s, ні L не залежать від n, то із збільшенням довжини вхідних векторів, ефективність конвеєрної обробки зростає.

Формула ефективності:

E = n/t = n /(s + L + n - 1)t = 1 /((st/n) + (Lt/n) + t - (t/n)) = 1 /t + ((s + L – 1)/n)t

При n ®¥ E ®1/t

Для формування паралельного алгоритму необхідно:

1. ідентифікувати частини роботи, які можуть бути виконані одночасно

2. відобразити зазначені частини на множину одночасно застосовуваних процесорів

3. розподілити вхідні, вихідні і проміжні дані між процесами відповідно до поставленої задачі

4. керувати доступом до спільно використовуваних даних

5. синхронізувати процеси на різних стадіях виконання програми

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

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

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

Число і розмір задач визначає ступінь деталізації паралельного алгоритму. Декомпозицію на велику кількість малих задач називають мілкомодульною, а на велику кількість крупних задач - крупномодульною. Поняття, пов’язане із ступенем деталізації – ступінь паралелізму. Максимальне число задач, які в паралельній програмі можуть бути виконані одночасно, носять назву максимальний ступінь паралелізму.

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

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

Ступінь паралелізму також залежить від форми ГЗЗ. Одна і та сама ступінь деталізації не визначає один і той самий ступінь паралелізму.Число і розмір задач визначає ступінь деталізації паралельного алгоритму. Декомпозицію на велику кількість малих задач називають мілкомодульною, а на велику кількість крупних задач - крупномодульною. Поняття, пов’язане із ступенем деталізації – ступінь паралелізму. Максимальне число задач, які в паралельній програмі можуть бути виконані одночасно, носять назву максимальний ступінь паралелізму.

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

Будь-яка ОС є сукупністю функціональних пристроїв (ФП), що працюють в часі. Оцінимо якість роботи ОС за допомогою спеціальних характеристик. Для цього введемо ряд понять:

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

Назвемо вартістю операції час її реалізації, а вартістю роботи — суму вартостей всіх виконаних операцій. Тобто, вартість роботи — це час послідовної реалізації всіх даних операцій на простих ФП з аналогічними періодами спрацьовувань. Завантаженістю пристрою на даному відрізку часу називатимемо відношення вартості реально виконаної роботи до максимально можливої вартості. Ясно, що завантаженість р завжди задовольняє умовам 0 ≤ р ≤ 1. Має місце також очевидне

ТВЕРДЖЕННЯ 1

Максимальна вартість роботи, яку можна виконати за час Т, рівна Т для простого ФП і nТ для конвейєрного ФП довжини n.

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

ТВЕРДЖЕННЯ 2

Хай система складається з s пристроїв, в загальному випадку простих або конвеєрних. Якщо пристрої мають пікові продуктивності π₁,...π_s і працюють із завантаженостями р₁,...,р_s_, то реальна продуктивність системи виражається формулою

Введемо поняття "прискорення":

Хай алгоритм реалізується за час Т на обчислювальній системі з s пристроїв, що мають пікові продуктивності p₁,....,p_s, які зв’язані співвідношенням p_1≤p_2≤...._≤p_s. Прискоренням реалізації алгоритму на даній ОС або просто прискоренням R будемо називати відношення R=r/p_s. Беручи до уваги (1), маємо

Розглянемо систему з s пристроїв. Оскільки будь-який конвеєрний ФП завжди можна представити як лінійний ланцюжок простих пристроїв, то вважатимемо всі пристрої простими. Допустимо, що між пристроями встановлені направлені зв'язки, і вони не міняються в процесі функціонування системи. Побудуємо орієнтований мультиграф, в якому вершини символізують пристрої, а дуги — зв'язки між ними. Назвемо цей мультиграфграфом системи.

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

ТВЕРДЖЕННЯ 3

Хай система складається з sпростих пристроїв з піковими продуктивностями p₁,....,p_s. Якщо граф системи зв'язний, то максимальна продуктивність r_max системи виражається формулою

Майже дослівне повторенням твердження 3 носить назву:

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

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

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

1. Другий та третій закони Амдала