Паралельне виконання операцій множення матриць

      Міністерство освіти і науки України

Національний університет “Львівська політехніка”

Кафедра ЕОМ

 

КУРСОВА РОБОТА

з дисципліни:

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

на тему:

«Паралельне виконання  операцій множення матриць»

 

Залікова книжка № 1009546

 

 

 

Виконав: ст.гр.КІ-42

Кухар Б.І.

                  Перевірив: Грос В.В.

 

 

 

 

 

 

Львів

 2014р.

Завдання

Розробити структуру та описати  процедуру перемноження матриці  А(розмірністю n₁*n₂) на матрицю В (розмірністю n₂*n₃) на заданій структурі. Для цієї структури визначити час виконання алгоритму, відсоток послідовної частини алгоритму та ефективність алгоритму для значень, що наведені в таблиці.

Для визначення завдання були виконані такі дії:

1. Визначення розмірів матриць. Для цього потрібно було провести декодування літер, які задавались згідно номеру групи:

n1=3П-"Х" , n2=2І-"O", n3=4Б-"H"     –    КІ-42

Згідно з таблицею декодування  літер розмірностей:

n1 = 240   n2 = 248 n3 = 67

А(240*248)

В(248*67)

С(240*67)

2. Структура задається виразом:

5b-12b-6b-11b-8b-1b-3b-13b –   КІ-42

де «nb»- номер букви  П.І.Б студента.

 

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

 

Таблиця 1.1. -  Порядкові номери літер прізвища, імені та по-батькові

1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19
К	У	Х	А	Р	Б	О	Г	Д	А	Н	І	В	А	Н	О	В	И	Ч
6		7		1	3		5			4	2		8

 

Порядк літер прізвища, імені та по-батькові з таблиці 1.1.: РІБНГКХА

 

Звідси формуємо таблицю декодування табл. 1.2, та матрицю зв’язків табл. 1.3.

 

Таблиця 1.2.Таблиця декодування

Р = 93	01011101
І = 223	11011111
Б = 35	00100011
Н = 134	10000110
Г = 74	01001010
К = 47	00101111
Х = 127	01111111
А = 27	00011010

 

Таблиця 1.3.Матриця зв’язків

ms	1	2	3	4	5	6	7	8
1	0	1	0	1	1	1	0	1
2	1	0	0	1	1	1	1	1
3	0	0	0	0	0	0	1	1
4	1	0	0	0	0	1	1	0
5	0	1	0	0	0	0	1	0
6	0	0	1	0	1	0	1	1
7	0	1	1	1	1	1	0	1
8	0	0	0	1	1	0	1	0

 

 

 

 

 

 

 

3. Визначення типу пам’яті:

Номер залікової книжки: 1009546

(25 mod 3) + 1 = 2 – завантаження через один процесор.

Співвідношення часових  параметрів: t_U = 10t_S  = 6t_P =5t_Z = 7t_W

 

 

 

 

 

Анотація

В даній курсовій роботі завданням було розробка алгоритму паралельного множення двох матриць розмірами 240х248 і 248х67 на розподіленій комп’ютерній системі із восьми процесорів, при чому завантаження і вивантаження відбувалось через один із них. Такий алгоритм може бути ефективним в системах з обмеженим доступом до пам’яті. Для реалізації паралельного алгоритму множення матриць було використано інтерфейс передачі повідомлень (МРІ) між процесами, оскільки він має широкі можливості. Для програмної реалізації алгоритму було обрано мову С++, з використаннямMPI. Наведені граф-схеми виконання алгоритму, схеми планування обчислень і блок-схеми програми множення матриць пояснюють реалізацію даного алгоритму більш детально.

 

Зміст

Вступ 6

1. Теоретичний  розділ 7

1.1 Матричні обчислення 7

1.2 Інтерфейс передачі повідомлень 10

1.3 Сучасні методи та  інструменти для паралельної  обробки................11

1.3.1 Технологія NVIDIA® CUDA™..................................................12

2. Розробка  граф-схеми виконання множення  матриць 13

3. Розробка  функціональної схеми 18

4. Розрахунковий  розділ 23

4.1 Визначення розмірності підматриць 23

4.2 Розрахунок часу виконання послідовного алгоритму 24

4.3 Розрахунок часу виконання паралельного алгоритму 25

4.4 Порівняння ефективності 25

5.Розробка  програми 26

5.1 Вибір середовища 26

5.2 Опис використаних функцій MPI 26

5.3 Розробка загальної блок-схеми програми 31

Висновки 32

Список використаної літератури 33

Додаток  39

 

 

Вступ

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

Домінуюче положення при  розробці паралельних програм для  паралельних систем займає стандарт MPI (англ. Message Passing Interface) та використання технології CUDA від Nvidia. Обидві технології є доволі ефективними.

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

 

 

 

1. Теоретичний розділ

1.1 Матричні обчислення

Множення матриці A розміру mxn і матриці B розміру nxl призводить до отримання матриці С розміру mxl, кожен елемент якої визначається відповідно до виразу:

(1)

Як випливає з (1), кожен  елемент результуючої матриці С  є скалярний добуток відповідних  рядка матриці A та стовпця матриці B:

Цей алгоритм передбачає виконання  mxnxl операцій множення і стільки ж операцій додавання елементів вихідних матриць. При множенні квадратних матриць розміру nxn кількість виконаних операцій має порядок O (n3). Відомі послідовні алгоритми множення матриць, що мають меншу обчислювальну складність (наприклад, алгоритм Страса (Strassen's algorithm)), але ці алгоритми вимагають великих зусиль для їх освоєння.  Далі будемо припускати, що всі матриці є квадратними і мають розмір nxn.

З визначення операції матричного множення випливає, що обчислення усіх елементів матриці С може бути виконано незалежно один від одного. Як результат, можливий підхід для організації паралельних обчислень полягає у використанні в якості базової підзадачі процедури визначення одного елемента результуючої матриці С. Для проведення всіх необхідних обчислень кожна підзадача повинна містити по одному рядку матриці А і по одному стовпцю матриці В. Загальна кількість одержуваних при такому підході підзадач виявляється рівним n2 (по числу елементів матриці С).

Розглянувши запропонований підхід, можна зазначити, що досягнутий рівень паралелізму є в більшості  випадків надмірним. Зазвичай при проведенні практичних розрахунків такої кількісті сформованих підзадач перевищує число наявних процесорів і робить неминучим етап укрупнення базових завдань. У цьому плані може виявитися корисною агрегація обчислень вже на кроці виділення базових підзадач. Можливе рішення може полягати в об'єднанні в рамках однієї підзадачі всіх обчислень, пов'язаних не з одним, а з декількома елементами результуючої матриці С. Для подальшого розгляду визначимо базове завдання як процедуру обчислення всіх елементів однієї з рядків матриці С. Такий підхід призводить до зниження загальної кількості підзадач до величини n.

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

Для обчислення одного рядка  матриці С необхідно, щоб у  кожній підзадачі містилася рядок  матриці А і був забезпечений доступ до всіх стовпців матриці B.  
Алгоритм являє собою ітераційну процедуру, кількість ітерацій якої збігається з числом підзадач. На кожній ітерації алгоритму кожна підзадача містить по одному рядку матриці А і одному стовпцю матриці В. При виконанні ітерації проводиться скалярне множення, що приводить до отримання відповідних елементів результуючої матриці С. Після завершення обчислень в кінці кожної ітерації стовпці матриці В повинні бути передані між підзадачами з тим, щоб у кожній підзадачі виявилися нові стовпці матриці В і могли бути обчислені нові елементи матриці C. При цьому дана передача стовпців між підзадачами повинна бути організована таким чином, щоб після завершення ітерацій алгоритму в кожній підзадачі послідовно опинилися всі стовпці матриці В. Можлива проста схема організації необхідної послідовності передачі стовпців матриці В між підзадачами, полягає в представленні топології інформаційних зв'язків підзадач у вигляді кільцевої структури. У цьому випадку на кожній ітерації підзадача i, де 0<=i<n, буде передавати свій стовпець матриці В підзадачі з номером i+1 (відповідно до кільцевої структури, підзадача n-1 передає свої дані підзадачі з номером 0) - Рис. 1.2. Після виконання всіх ітерацій алгоритму необхідна умова буде забезпечена в кожній підзадачі по черзі опиняться всі стовпці матриці В.

На рис.1.2 представлені ітерації алгоритму матричного множення для випадку, коли матриці складаються з чотирьох рядків і чотирьох стовпців (n=4). На початку обчислень в кожній підзадачі i, де 0<=i<n, розташовуються i-й рядок матриці A і i-й стовпець матриці B. В результаті їх перемножування підзадача отримує елемент Сіi результуючої матриці С. Далі підзадачі здійснюють обмін стовпцями, в ході якого кожна підзадача передає свій стовпець матриці B наступної підзадачі відповідно до кільцевої структури інформаційної взаємодії. Далі виконання описаних дій повторюється до завершення всіх ітерацій паралельного алгоритму.

 
Рис.1.2. Загальна схема передачі даних для паралельного алгоритму матричного множення при стрічковій схемі розділення даних.

 

1.2 Інтерфейс передачі повідомлень

MPI (англ. Message Passing Interface, Інтерфейс передачі повідомлень) — це специфікація, що була розроблена в 1993–1994 роках групою MPI Forum, і забезпечує реалізацію моделі обміну повідомленнями між процесами. У моделі програмування MPI програма породжує кілька процесів, що взаємодіють між собою за допомогою звертання до підпрограм прийому і передачі повідомлень.

Зазвичай, при ініціалізації MPI-програми створюється фіксований набір процесів, причому кожний з них виконується  на своєму процесорі. У цих процесах можуть виконуватися різні програми, тому MPI-модель іноді називають MPMD-моделлю (Multiple Program, Multiple Data), на відміну від SPMD моделі, де на кожному процесорі виконуються тільки однакові задачі. MPI підтримує двохточкові і глобальні, синхронні й асинхронні, блокуючі і неблокуючі типи комунікацій. Структура комунікацій може змінюватися протягом часу життя процесу, але кількість задач повинна залишатися постійною.

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

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