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

1

Вступ. 2

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

Класифікація паралельних комп’ютерів і систем. 5

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

Закони Амдала 7

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

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

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

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

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

Спекулятивна декомпозиція. (або пан або пропав). 11

Гібридна декомпозиція – об‘єднання всіх. 11

Концепція машин потоків даних 11

Принцип МПД. 12

Обчислення в МПД 12

Синхронна та асинхронна паралельність. 13

Асинхронна паралельність 13

Синхронна паралельність 14

Вступ.

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

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

Головний вектор розвитку комп’ютерних систем – це підвищення її ефективності, яка вимірюється у MIPS (мільйон операцій з плаваючою крапкою за одну секунду). Сумарну продуктивність арифметико логічних пристроїв ОС називається пікових ресурсів ОС, це теоретичне поняття не враховує тимчасових витрат. Реальна продуктивність – це продуктивність якої сягає ОС під час виконання конкретної операції. Реальна продуктивність не може перевищувати пікову, її наближення до пікового говорить про ефективність роботи ОС(відношення реальної до пікової).

Класи паралельно обчислювальних систем в залежності від архітектури:

1. комп’ютери із загальною пам’яттю або мультипроцесорні системи. Комп’ютер працює з одним єдиним адресним простором

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

Два класи паралельно, обчислювальних систем відображають 2 основні задачі паралельних обчислень: 1 – побудова обчислювальних систем – це легко дозволяють зробити паралельно розподілені системи; 2 – пошук методів розробки ефективного програмного забезпечення для паралельно обчислювальних систем. Дана задача легко розв’язується в системах із загальною пам’яттю, за рахунок того, що обмін інформацією через загальну пам'ять швидше, і програмувати легше. Недолік – обмеження з технологічних причин.

Структури зв‘язку між процесорами

Процесори та модулі пам‘яті системи мають бути зв’язані через комунікаційні системи, мають відповідати наступним критеріям:

1. забезпечувати високу колективність, гарантувати зв'язок між будь-якими елементами ОС без потреби переходу через проміжні пункти комутації; має забезпечуватись найбільша кількість одночасних зв’язків. Проте існують різноманітні обмеження на реалізацію цих критерій: кількість ліній зв‘язку на один процесор не може збільшуватись безмежно, ширина частотного пропускання каналу теж обмежена. Витрати на виготовлення системи ліній зв’язків на один елемент та витрати під час експлуатації (дистанція між процесорних елементів). Отже дистанція між двома ПМ має бути як умога меншою а структура зв‘язку має бути маштабованою.

Структури зв’язку поділяються на 3 класи.

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

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

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

Д

0 1

ельта сітки. Щоб зменшити сітки порядку (н квадрат), які виникли під час побудови сітки з звичайними комутаторами, використовуються дельта мережі, які базуються на використанні дельта-перемикача.

За допомогою таких перемикачів можна побудувати більш об’ємні мережі, при цьому потреби у комутаторах зменшуються і будуть дорівнювати (n*logn)/2.

Структури, які забезпечують прямі зв’язки між процесорними елементами. Розглянемо статичні структури, при цьому n – кількість процесорів, V- кількість ліній зв’язку на кожен процесор, A – максимальна відстань між процесорами.

Топологія кільце:

Топологія граф:

Топологія решітки:

Тор – це замкнений варіант решітки.

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

V=log2(N);

А= log2(N);

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

Комп’ютери із numa архітектурою.

Будова, особливості, зразки.

Класифікація паралельних комп’ютерів і систем.

Класифікація Флінина: (1966) – базується на поняття потоку, під яким розуміється послідовність команд. На основі числа потоків команд даних флін виділяє 4 класи архітектури:

1. STS (single Instruction Stream) – до цього класу відносяться машини фоннеймінського типу, в яких дані обробляються послідовно один за одним.

УУПК ПРПЄ ПДП

2. SIMD – у архітектурі подібного класу зберігається один потік команд (векторні операції), що дозволяють виконувати одні і ті самі операції над багатьма даними. Частіш за все – це матриці процесорів, які отримають результат від пристроїв керування і виконують операції.

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

Незважаючи на різноманітність форм проявлення паралелізму способів паралельної обробки існують лише 2:

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

2. конвеєрна обробка

Чистий паралелізм. Приклад: нехай нам потрібно знайти суму двох двох-розрядних векторів. Є пристрій додавання, який виконує одну операцію за 5 тактів.

C=A+B.

1

1

1

1

1

1

1

1

1 С1

1

Чистий паралелізм полягає у прямому збільшенні об’єктів. В загальному випадку тривалість роботи, це l*n, де l – довжина вхідних векторів, а n – кількість тактів, за яких виконується операція. Система з N векторів виконає цю саму роботу на час t_n=l*n/N.

Конвеєрна обробка. Приклад:

Кожна частина конвеєрного пристроя називається кроком конвеєра, а загальна частина кроків – довжиною конвеєра. Якщо конвеєрний пристрій містить Л кроків, а кожен крок спрацьовує за час Т, то час обробки Н незалежних операцій буде дорівнювати Л+Н-1. якщо цей пристрій використовувати в монопольному режимі як послідовний, то цей час складе Л*Н. якщо знайти співвідношення, то при Нбезмежності =Л. команда у якої всі операнди є скалярні величини називається скалярною. Якщо хоча б один операнд вектор, то така команда називається векторною. При використання векторних команд у формулі з‘являється ще один операнд сігма – це час ініціалізації векторної команди. Оскільки ні сігма ні Л не залежить від довжини вектора, то із збільшенням довжини вхідних векторів, ефективність конвеєрної обробки зростає. Під ефективністю розуміємо реальну ефективність, яка дорівнює відношенню загальної кількості операції до сумарного часу виконання. Можна отримати такі результати:

Пар = n/t=n/((l-n+б-1)/tt)=1/(l*tt/n-tt+б*tt/n-tt/n), де tt – це тривалість роботи системи.

E=1/(tt+tt/n*(l+5-1))1/tt;

?????

Закони Амдала

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

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