Зміст
Вступ…………………………………………………………………………………..3
1. Дослідження структури
алгоритму множення матриць…………………….5
1.1. Проектування
блок-схеми виконання алгоритму………………………...7
1.2. Блок-схема
виконання алгоритму…………………………………………..8
2. Розрахунковий
розділ…………………………………………………………...11
2.1. Послідовне
виконання………………………………………………………11
2.2. Паралельне
виконання……………………………………………………...12
3. Реалізація заданого
алгоритму………………………………………………...16
3.1. Блок-схема
роботи програми……………………………………………….16
3.2. Вибір середовища…………………………………………………………….17
3.3. Опис роботи
програми……………………………………………………….17
3.4. Результат
виконання програми…………………………………………….20
4. Розробка кластерної
системи…………………………………………………..22
4.1. Базова інфраструктура………………………………………………………22
4.2. Проектування
архітектури кластерної системи………………………….24
4.3. Вибір системного
ПЗ…………………………………………………………26
Висновки…………………………………………………………………………….30
Список використаної
літератури………………………………………………..31
Вступ
Паралельні обчислення — це
форма обчислень, в яких кілька дій проводяться
одночасно. Грунтуються на тому, що великі
задачі можна розділити на кілька менших,
кожну з яких можна розв'язати незалежно
від інших. Паралельні обчислення застосовуються
вже протягом багатьох років, в основному
в високопродуктивних обчисленнях, але
зацікавлення ним зросло тільки недавно,
через фізичні обмеження зростання частоти.
Оскільки споживана потужність (і відповідно
виділення тепла) комп'ютерами стало проблемою
в останні роки, паралельне програмування
стає домінуючою парадигмою в комп'ютерній
архітектурі, основному в формі багатоядерних
процесорів.
Паралельні комп'ютери можуть
бути класифіковані згідно рівня, на якому
апаратне забезпечення підтримує паралелізм:
багатоядерність, багатопроцесорність
— комп'ютери, що мають багато обчислювальних
елементів в межах одної машини, а також
кластери, MPP, та ґрід — системи що використовують
багато комп'ютерів для роботи над одним
завданням. Спеціалізовані паралельні
архітектури іноді використовуються поряд
з традиційними процесорами, для прискорення
особливих задач.
Програми для паралельних комп'ютерів
писати значно складніше, ніж для послідовних,
бо паралелізм додає кілька нових класів
потенційних помилок, серед яких є найпоширеніною
стан гонитви. Комунікація, та синхронізація
процесів зазвичай одна з найбільших перешкод
для досягнення хорошої продуктивності
паралельних програм. Максимальний можливий
приріст продуктивності паралельної програми
визначається законом Амдала. Матриці
і матричні операції широко використовуються
в математичному моделюванні різних процесів,
явиш чи систем. Матричні обчислення є
великою частиною багатьох інженерних
розрахунків. Серед прикладних областей
може бути військова промисловість, медицина,
економіка та ін.
Оскільки, операція множення
матриць є базовою для широкого кола алгоритмів
обробки сигналів і зображень, то з цієї
точки зору матричні обчислювальні пристрої,
що реалізують дану операцію являють особливий
інтерес. Причому, ефективність виконання
таких операцій обробки залежить як від
продуктивності комп'ютерів, так і від
розмірів і структури пам'яті, пропускної
здатності каналів зв'язку, використаних
мов програмування, компіляторів, операційних
систем, чисельних методів та інших математичних
досліджень. Такий широкий обсяг параметрів
вимагає проведення досліджень на різних
рівнях: на рівні розпаралелення алгоритмів,
створення спеціальних мов програмування,
компіляторів, багатопроцесорних систем,
неоднорідних систем, кластерів.
Будучи обчислювально трудомісткими,
матричні обчислення є класичною областю
застосування паралельних обчислень.
З одного боку, використання високопродуктивних
багатопроцесорних систем дозволяє істотно
підвищити складність завдань, які розв'язуються.
З іншого боку, через своє достатньо просте
формулювання матричні операції надають
прекрасну можливість для демонстрації
багатьох прийомів і методів паралельного
програмування.
1. Дослідження структури
алгоритму множення матриць
Завдання №1.
Нехай задано дві вихідні матриці
A і B. Обчислюється добуток C = А х B, де А - матриця n1 х n2, і B - матриця n2 х n3. Матриця результатів C має розмір n1 х n3. Вихідні матриці
попередньо розрізані на смуги, смуги
записані на дискову пам'ять окремими
файлами зі своїми іменами і доступні
всім комп'ютерам. Матриця результатів
повертається в нульовий процес.
Реалізація алгоритму виконується
на кільці з p1 комп'ютерів. Матриці розрізані
як показане на рис. 1: матриця А розрізана на p1 горизонтальних смуг, матриця B розрізана на p1 вертикальних смуг, і матриця
результату C розрізана на p1 смуги. Тут передбачається,
що в пам'ять кожного комп'ютера завантажується
і може знаходитися тільки одна смуга
матриці А і одна смуга матриці B.
Рис. 1.Розрізування даних для паралельного
алгоритму добутку двох матриць при обчисленні
на кільці комп'ютерів. Виділені смуги
розташовані в одному комп'ютері.
Оскільки за умовою в комп'ютерах
знаходиться по одній смузі матриць, то
смуги матриці B (або смуги матриці A) необхідно "прокрутити"
по кільцю комп'ютерів повз смуги матриці A (матриці B). Кожний зсув смуг уздовж кільця
і відповідна операція множення наведена
на рис.1.2 у виді окремого кроку. На кожному
з таких кроків обчислюється тільки частина
смуги. Процес i обчислює на j-м кроці добуток
i-й горизонтальної смуги матриці A j-ї вертикальної смуги матриці B, добуток отриманий у підматриці(i,j)
матриці C.
Обчислення відбувається в
такій послідовності. 1. Кожен комп'ютер
зчитує з дискової пам'яті відповідну
йому смугу матриці А. Нульова смуга повинна
зчитуватися нульовим комп'ютером, перша
смуга - першим комп'ютером і т.д., остання
смуга - зчитується останнім комп'ютером.
Смуги матриці А і B пронумеровані. 2. Кожен комп'ютер
зчитує з дискової пам'яті відповідну
йому смугу матриці B. У даному випадку нульова смуга
повинна зчитуватися нульовим комп'ютером,
перша смуга - першим комп'ютером і т.д.,
остання смуга - зчитується останнім комп'ютером.
3. Обчислювальний крок 1. Кожен процес
обчислює одну підматрицю добутку. Вертикальні
смуги матриці B зсуваються уздовж кільця комп'ютерів.
4. Обчислювальний крок 2. Кожен процес
обчислює одну підматрицю добутку. Вертикальні
смуги матриці B зсуваються уздовж кільця комп'ютерів.
І т.д. 5. Обчислювальний крок p1-1. Кожен
процес обчислює одну підматрицю добутку.
Вертикальні смуги матриці B зсуваються уздовж кільця комп'ютерів.
6. Обчислювальний крок p1. Кожен процес
обчислює одну підматрицю добутку. Вертикальні
смуги матриці B зсуваються уздовж кільця комп'ютерів.
7. Матриця C збирається в нульовому комп'ютері.
Якщо "прокручувати" вертикальні
смуги матриці B, то матриця С буде розподілена горизонтальними
смугами, а якщо "прокручувати" горизонтальні
смуги матриціA, то матриця С буде розподілена вертикальними
смугами. Якщо час передачі даних великий
в порівнянні з часом обчислень, або канали
передачі повільні, то ефективність алгоритму
буде не висока. Тут не враховується час
початкового завантаження і вивантаження
даних у пам'ять системи. У смугах матриць
може бути різна кількість рядків, а різниця
в кількості рядків між смугами - 1. При великих
матрицях цим можна знехтувати. При достатніх
ресурсах пам'яті в системі краще використовувати
алгоритм, у якому мінімізовані обміни
між комп'ютерами в процесі обчислень.
Це досягається за рахунок дублювання
деяких даних у пам'яті комп'ютерів.
1.1. Проектування блок-схеми
виконання алгоритму
Зв'язки між процесорами
Для ефективної роботи паралельної
системи було побудовано схему пересилань
даних та граф зв'язків між процесорами,
їх опис, який наведений на рис. 2.
Рис. 2. Граф зв'язків між процесорами
Пересилання даних
по кільцю
Оскільки стоїть задача розпаралелити
виконання перемноження матриць, то доцільно
використовувати обмін даними по кільцевій
структурі, що забезпечує роботу з мінімальними
затримками. Граф пересилання даних між
процесорами на кільцевій структурі зображений
на рис. 3.
Пересилання між
процесорами виконується у такому порядку:
P1 →P3→P6→P7→P2→P5→P4→P8
Рис. 3. Граф пересилання даних
між процесорами на кільцевій структурі
1.2. Блок-схема виконання
алгоритму
На початку роботи алгоритму
кожен процесорний елемент зчитує початкові
дані, тобто підматриці А та В, які були
завантажені з розподіленої пам'яті. Відбувається
множення підматриць. Після закінчення
цієї операції відбувається обмін даними
підматриці В між процесорами по кільцевій
структурі, яка вже була наведена на рис.
3. Так відбувається доти, доки підматриця
В не буде перемножена на всі підматриці
А.
Далі відбувається поетапне
виведення часткових результатів, тобто
підматриць C і збір загального результату,
тобто виведення матриці С у повному вигляді.
На рис. 4. наведена граф-схема
виконання алгоритму множення двох матриць
з розподіленою пам'яттю в загальному
випадку.
Рис. 4. Граф-схема виконання
алгоритму множення двох матриць з розподіленою
пам'яттю.
Для матриць А[N1,N2] та B[N2,N3] і Р процесорів
розміри підматриць Аі та Ві визначаються
так.
Для А та для В обчислюємо
,
де С1А та С1В – ціла частина
від ділення, С2А та С2В - залишки.
Перші (Р - С2А) підматриці
матриці А матимуть кількість
рядків С1А, решту – (С1А + 1) рядків.
Для матриці В, відповідно,
(Р - С2В), С1В, (С1В + 1) стовпців.
Визначимо розміри підматриць Аі та Ві для кожного
з процесорів.
,
,
Розбиття матриці А на горизонтальні
стрічки і матриці B на вертикальні стрічки
наведено на рис. 5.
A B
72 67
A1 26 |
A2 26 |
A3 26 |
A4 26 |
A5 26 |
A6 26 |
A7 27 |
A8 27 |
B1
8 |
B2
8 |
B3
8 |
B4
8 |
B5
8 |
B6
9 |
B7
9 |
B8
9 |
210 72
Рис. 5. Розбиття матриць A і B
на підматриці.
Спочатку розподілені підматриці Аі та Ві записуються
до розподіленої області пам'яті кожного окремого
процесора, після чого система запускається
на виконання. Відразу після запуску кожен
з процесорів паралельно з іншими зчитує
початкові дані із своєї окремої пам'яті.
Потім кожен процесор перемножує відповідно
завантажені підматриці. Відбувається
пересилання даних по кільцю на інші процесори,
що включає в себе і посилання даних і
прийом даних процесором. Такі операції
відбувається в циклі з кількістю ітерацій
- 8. Після останньої паралельної ітерації
множення перший процесор вивантажує
частковий результат, тобто підматрицю
С1. На цьому ж етапі отримано решту часткових
результатів. Ці дані пересилаються по
кільцю процесорів. Цикл буде повторюватись
доти, доки не буде виведено останній частковий
результат. Після цього проводиться збір
результатів, виводиться загальний результат,
система завершує свою роботу.
2. Розрахунковий розділ
Для процесорних елементів
визначимо такі розміри підматриць:
А1-6[26, 72], А7-8[27, 72], B1-5[72, 8], B6-8[72,
9].