Размещено на http://www.allbest.ru/

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

• Вступ
• Великі та надвеликі задачі - це такі задачі, розв`язок яких за допомогою комп'ютера неможливо знайти або він буде не актуальним на момент вирішення задачі. Приклад: створення кліматичної моделі землі; розробка ядерної зброї; задачі аеродинаміки; розшифровка геному людини. Паралельний описує процеси дійні факти і стани, які відбуваються одночасно і не залежить один від одного.
• Паралельні обчислення - сукупність питань, що відноситься до ресурсів паралелізму в процесі вирішення цих задач та управлінню реалізації паралелізму з метою досягнення найбільшої ефективності використання комп'ютерної техніки.
• Головний вектор розвитку комп'ютерних систем - це підвищення її ефективності, яка вимірюється у MIPS (мільйон операцій з плаваючою крапкою за одну секунду). Сумарну продуктивність арифметико логічних пристроїв ОС називається пікових ресурсів ОС, це теоретичне поняття не враховує тимчасових витрат. Реальна продуктивність - це продуктивність якої сягає ОС під час виконання конкретної операції. Реальна продуктивність не може перевищувати пікову, її наближення до пікового говорить про ефективність роботи ОС(відношення реальної до пікової).
• Класи паралельно обчислювальних систем в залежності від архітектури:
• 1. комп'ютери із загальною пам'яттю або мультипроцесорні системи. Комп'ютер працює з одним єдиним адресним простором
• Размещено на http://www.allbest.ru/
• 2. комп'ютери з розподіленою пам'яттю або мультикомп'ютерні системи. Кожен обчислювальний вузол є повноцінним комп'ютером з своїм процесором, пам'яттю, системою вводу виводу та операційною системою.
• Размещено на http://www.allbest.ru/
• Два класи паралельно, обчислювальних систем відображають 2 основні задачі паралельних обчислень: 1 - побудова обчислювальних систем - це легко дозволяють зробити паралельно розподілені системи; 2 - пошук методів розробки ефективного програмного забезпечення для паралельно обчислювальних систем. Дана задача легко розв'язується в системах із загальною пам'яттю, за рахунок того, що обмін інформацією через загальну пам'ять швидше, і програмувати легше. Недолік - обмеження з технологічних причин.
• Структури зв`язку між процесорами
• Процесори та модулі пам`яті системи мають бути зв'язані через комунікаційні системи, мають відповідати наступним критеріям:
• 1. забезпечувати високу колективність, гарантувати зв'язок між будь-якими елементами ОС без потреби переходу через проміжні пункти комутації; має забезпечуватись найбільша кількість одночасних зв'язків. Проте існують різноманітні обмеження на реалізацію цих критерій: кількість ліній зв`язку на один процесор не може збільшуватись безмежно, ширина частотного пропускання каналу теж обмежена. Витрати на виготовлення системи ліній зв'язків на один елемент та витрати під час експлуатації (дистанція між процесорних елементів). Отже дистанція між двома ПМ має бути якомога меншою а структура зв`язку має бути масштабованою.
• Структури зв'язку поділяються на 3 класи.
• Найпростіший спосіб «сітка» зв'язку, який базується на використання загальної шини, до якого під'єднаний, як процесорні елементи так і модулі пам'яті. Використовується спеціальна схема арбітражу, яка допомагає виключити помилки з'єднання.
• Размещено на http://www.allbest.ru/
• Недолік: шина стає вузьким місцем, тому перейшли до 2 способу зв'язку: сітки з комутаторами.
• Размещено на http://www.allbest.ru/
• Кожний процесорний елемент має н-1 пункт комутації, оскільки діагональні елементи не потребують з'єднань. Загалом дана сітка має н*(н-1) пунктів комутації і дає можливість встановити будь-яку кількість з'єднань, тобто можливий повність паралельний обмін даних. Суттєвим недоліком є витрати на його побудову, тобто число н процесорів з'єднувати таким способом обмежено.
• Дельта сітки. Щоб зменшити сітки порядку (н квадрат), які виникли під час побудови сітки з звичайними комутаторами, використовуються дельта мережі, які базуються на використанні дельта-перемикача.
• Размещено на http://www.allbest.ru/
• За допомогою таких перемикачів можна побудувати більш об'ємні мережі, при цьому потреби у комутаторах зменшуються і будуть дорівнювати (n*logn)/2.
• Структури, які забезпечують прямі зв'язки між процесорними елементами. Розглянемо статичні структури, при цьому n - кількість процесорів, V- кількість ліній зв'язку на кожен процесор, A - максимальна відстань між процесорами.
• Топологія кільце:
• Топологія граф:
• Топологія решітки:
• Тор - це замкнений варіант решітки.
• Гіпер-куб нульової вимірності - це єдиний елемент; вимірності і+1 виникає з двох гіперкубів вимірності і, причому всі елементи об'єктів, що взаємодіють з'єднані між собою.
• V=log2(N);
• А= log2(N);
• В порівнянні топології з'єднань можливо тільки на основі показників В і А. В залежності від умов застосування одна топологія може бути краща за іншу. Бажано щоб системи дозволяли динамічно змінювати топологію мереж.

Комп'ютери із NUMA архітектурою

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

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

Вартість - час реалізації операції, а вартість роботи - сума всіх вартості операції.

Завантаженістю пристрою на даному відрізку часу назвемо відношення вартості виконаної роботи до максимально можливої вартості. 0<=p<=1.

Має місце твердження 1. максимальна вартість роботи, яку можна виконати за час Т, для простого функціонального пристрою дорівнює Т, а для конвеєрного пристрою з довжиною м, то максимальна вартість буде м*Т.

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

Твердження 2. нехай система складається з s пристроїв, які працюють з піковими продуктивностями від і1 до іs, тоді реальна продуктивність системи буде дорівнювати

П=сума(р_і*П_і).

Прискорення - нехай алгоритм реалізується за час Т на обчислювальної системи з s пристроями, які мають пікові продуктивності від І₁ до І_s, і зв'язані наступними співвідношення: P= прискорення реалізації алгоритму на даній обчислювальній системі,

R=Ппар/Ппосл.

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

Твердження 3. нехай система складається з S пристроїв з піковими продуктивностями від П1..ПS, то максимальна продуктивність системи визначається формулою: Смах= SПмін.

Rmax=S?тип

Тобто продуктивність системи визначається найнепродуктивнішим елементом

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

З певних причин н операцій ми вимушені виконувати послідовно. Одна з основних причин послідовного виконання операцій - це в'язанні за даними. Введемо поняття b=n/N - частка послідовних обчислень.

2-й закон Амдала. Нехай система складається з S універсальних пристроїв. Припустимо, що при виконанні паралельного алгоритму всі пристрої завантажені повністю, тоді

R=S/(bS+(1_b)).

Позначимо через p - пікову продуктивність. Якщо система складається з S пристроїв однакової продуктивністю, то прискорення системи буде рівна сумі всіх завантажених пристроїв. Якщо виконуються всі N операцій, то bN - кількість послідовних операцій виконуються на першому пристрою. Загальна кількість паралельних операцій (1-b)N/S. R=sum(p_i). Всього алгоритм реалізується за час T₁=(bN+(1-b)*N/S)/p. На паралельній частині алгоритму працює як перший так і решта алгоритмів, витрачаючи час

T₁=((1-b)*N/S)/p.

P₁=1

P_i=((1-b)*N/S)/(b*N+(1-b)*N/S).

R=sum(p_i)=1+sum( ((1-b)*N/S)/(b*N+(1-b)*N/S) )=…=S/(bS+(1-b)).

Якщо система складається з однакових універсальних пристроїв то при будь-яких режимах роботи максимальне прискорення не може перевищувати b.

Принципи побудови паралельних алгоритмів

декомпозиція алгоритм комп'ютер

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

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

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

3. розподілити вхідні, вихідні і проміжні дані асоційовані з програмою

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

5. синхронізувати роботу процесів на всіх етапах.

Процес розподілу обчислень можуть бути …. декомпозиції

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

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

Обробка запиту до бази даних.

Select * from T1 where

Model = “Civic” and Year=2001

And (Color=”Green” or Color=”White”)

Результат декомпозиції запитом зображений на рис.3. один із шляхів розв'язку задач:

Размещено на http://www.allbest.ru/

Число задач, на які розбите вхідне завдання визначає ступінь деталізації декомпозиції. Декомпозицію на велику кількість задач називають мілко модульною, і на невелику кількість об'ємних задач - крупно модульною. Ту ж саму задачу можна деком позувати по різному. Якщо об'єднувати в одне завдання кілька модулів, то отримаємо крупно модульною декомпозицією. Поняття пов'язане з ступенем декомпозиції - це ступінь паралелізму та мах число задач, які можуть бути виконані паралельною програмою одночасно, відомою як максимальною ступенем паралелізму. Більш корисний - це середній ступінь паралелізму, ступінь залежить від форми графа залежності задач. І той самий ступінь декомпозиції не гарантує ту ж саму ступінь декомпозиції паралелізму.

Sp=w/t; Q=Sp/p;

w - кількість операцій; t - висота; р - процесори

Найдовший направлений шлях між початкової пари та кінцевого вузлів називається критичним шляхом. Модель взаємодії задач фіксується графом взаємодії задач. Його вершини - це задачі, а ребра зв'язують лише ті задачі, які взаємодіють. Вершини і ребра можуть бути пропорційно до кількості пропозицій і … ребра зазвичай не орієнтовані, вони можуть бути одно направлення, коли існує один напрямок задачі. Масив ребер є над множиною масиву ребер ГЗЗ. Для прикладу №1 граф взаємодії задач ідентичний графу залежності задач.

Приклад розрідженого векторно-матричного множення

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

0 1 2 3 4 5 6 7 8 9 10 11

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

Методи декомпозиції

Декомпозиція - один із фундаментальних кроків розпалалелювання задач.

Існують наступні методи декомпозиції:

1. рекурсивний

2. декомпозиція даних

3. дослідницька декомпозиція

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

Перші 2 методи призначені для розв'язку широкого розв'язку задач і є універсальними. Спекулятивна і дослідницька декомпозиція є спеціалізоване і вузько напрямлене.

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

Це метод для виявлення паралелізму в задач, які можуть бути розв'язані за допомогою методу «розподіляйте та володарюйте». При використанні цієї методики на першому етапі завдання розподіляються на набір незалежних задач. На кожному наступному етапі відбувається подальша деталізація задач за цим самим принципом. Саме за такою схемою декомпозуються більше задач сортування. Приклад: знаходження мінімального елементу з масиву чисел. {7,3,10,6,8,1,2,9}. Розіб'ємо масив на пару елементів:

7 3 10 6 8 1 2 9

3 6 1 2

3 1

1

Декомпозиція за даними