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

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

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

МІНІСТЕРСТВО ОСВІТИ ТА НАУКИ УКРАЇНИ

НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ «ЛЬВІВСЬКА ПОЛІТЕХНІКА»

Інститут Комп'ютерних Технологій, Автоматики та Метрології

Кафедра ЕОМ

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

з дисципліни

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

на тему:

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

Виконав:

ст.гр КІ-43

Закревський А.С.

Перевірив

Грос В.В.

Львів -2015



Завдання

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

Таблиця 1

Розміри матриці	К-ть процесорів	Тип початкового завантаження даних	Співвідношення часових параметрів
N1	N2	N3
120	112	117	8	через один з процесорів	tu = 10ts = 2tp = 6tz = 6tw

Примітка:

tU - час виконання однієї операції множення;

tS - час виконання однієї операції сумування;

tP - час виконання однієї операції пересилання даних між процесорами;

tZ - час виконання операції завантаження одних даних;

tW - час виконання операції вивантаження одних даних.

Таблиця 2. Матриця зв'язків

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



Анотація

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

В курсовій роботі розроблено граф-схему виконання алгоритму множення двох матриць, граф-схему загальної схеми виконання програми та граф-схему покрокового виконання алгоритму.Програмне реалізація до курсової роботи виконане у середовищі Microsoft Visual Studio 2012 на мові С++ з використанням бібліотек MPI.

.

.



Вступ

множення матриця алгоритм

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

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

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

Для вивчення паралельних алгоритмів найкращим і найпростішим способом є набуття навичок паралельної обробки матриць та векторів.

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



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

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

Паралельна модель програмування сильно відрізняється від звичайної - послідовної. Існують дві моделі паралельного програмування: модель паралелізму даних і модель паралелізму задач. Модель паралелізму даних має на увазі незалежну обробку даних кожним процесом (наприклад, векторні операції з масивами). Модель паралелізму задач передбачає розбиття основної задачі на самостійні підзадачі, кожна з яких виконується окремо й обмінюється даними з іншими. Це більш трудомісткий, у порівнянні з паралелізмом даних, підхід. Перевагою є велика гнучкість і велика воля, надана програмісту в розробці програми, що ефективно використовує ресурси паралельної системи. При цьому можуть застосовуватися спеціалізовані бібліотеки, що беруть на себе всі «організаційні» задачі. Приклади таких бібліотек: MPI і PVM.

При розробці паралельних програм виникають специфічні для даної моделі обчислень проблеми сугубо технічного характеру: забезпечення комунікацій між підзадачами, забезпечення надійності й ефективності цих комунікацій. Для рішення цих проблем можна реалізувати власні методи, а можна використовувати вже готові стандарти/специфікації/бібліотеки. MPI - «Інтерфейс передачі повідомлень» - це специфікація, що була розроблена в 1993-1994 роках групою MPI Forum і забезпечує реалізацію моделі обміну повідомленнями між процесами. Остання версія даної специфікації MPI-2. У моделі програмування MPI програма породжує кілька процесів, взаємодіючих між собою за допомогою звертання до підпрограм прийому і передачі повідомлень.

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

1.1 Організація процесу обчислення

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

(1)

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

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



1.2 Послідовний алгоритм

Послідовний алгоритм множення матриць видається трьома циклами:

Алгоритм 1.Послідовний алгоритм множення двох квадратних матриць

/ / Алгоритм 1

/ / Послідовний алгоритм множення матриць

double MatrixA [Size] [Size];

double MatrixB [Size] [Size];

double MatrixC [Size] [Size];

int i, j, k;

...

for (i = 0; i <Size; i + +) {

for (j = 0; j <Size; j + +) {

MatrixC [i] [j] = 0;

for (k = 0; k <Size; k + +) {

MatrixC [i] [j] = MatrixC [i] [j] + MatrixA [i] [k] * MatrixB [k] [j];

}

}

}

Цей алгоритм є ітеративним і орієнтований на послідовне обчислення рядків матриці С. Дійсно, при виконанні однієї ітерації зовнішнього циклу (циклу за змінною i) обчислюється один рядок результуючої матриці (див. рис. 1.1).

Рис. 1.1.

На першій ітерації циклу за змінною i використовується перший рядок матриці A і всі стовпці матриці B для того, щоб обчислити елементи першого рядка результуючої матриці С.

Оскільки кожен елемент результуючої матриці є скалярний добуток рядка та стовпця вихідних матриць, то для обчислення всіх елементів матриці з розміром nxn необхідно виконати n2 *(2n-1) скалярних операцій та затратити час

(2)

де є час виконання однієї операції.

1.3 Множення матриць при стрічковій схемі розділення даних

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

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

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

1.4 Виділення інформаційних залежностей

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

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

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

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

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



2.Розробка граф-схеми виконання заданої функції

Комунікаційна мережа між процесорами представлена на рис 2.1. В якості процесора який має доступ до пам'яті було вибрано процесор №4.

Рис. 2.1. Граф-схема зв'язків між процесорами

Використання усіх зв'язків між процесорами для вирішення даної задачі - недоцільне, і навіть може призвести до втрати продуктивності. Для реалізації алгоритму перемноження матриць, спершу необхідно вирішити, як саме матриці будуть розподілені між процесорами. Обираємо наступний тип розбиття: матриця А - стрічково-горизонтальне розбиття, матриця В - стрічково-вертикальне розбиття

Граф-схема початкового завантаження даних у процесори показана на Рис 2.2.

Перший крок: Процесор 4 передає на процесор 1 через 3 і 7 підматрицю 1. На 2 процесор передається через 5 процесор підматрицю 5. На 8 - через 6 підматрицю 6.

Другий крок: Процесор 4 завантажує і передає підматриці 5 і 6 на 5, 6 процесори і на 7 через 3 підматрицю 3

Третій крок: Дальше процесор 4 завантажує підматриці 3 і 4, і передає підматрицю 3 на 3 процесор.

Рис. 2.2. Граф-схема завантаження даних

Граф-схема вивантаження даних зпроцесорів показана на Рис 2.3.

Перший крок: Процесор 7 передає на процесор 4 через 1 і 6 підматрицю 7. На 4 процесор передається через 3 процесор підматрицю 3. З8 -через 5 підматрицю 8.

Другий крок: Процесор 1 передає підматрицю1 на 4 через 6 процесор. 2 і 5 процесори перередають підматриці 2 і 5 на 4.

Третій крок: Дальше процесор 6 вивантажує підматрицю.

Рис. 2.3. Граф-схема вивантаження даних



В даній структурі зв'язків від процесорами можна виділити кільце, тому обмін підматрицею Ві при перемноженні матриць буде виконуватись по вибраному кільцю, яке зображене на рис.2.4:

Рис.2.4. Вибраний кільцевий маршрут передачі підматриць В при множенні

Передача відбувається за 2 кроки:

Крок 1:

7 ->1, 6->8; 3->2; 4->5;

Крок 2:

1 ->6, 8->3; 2->4; 5->7;

Де 1-8 - це номери процесорів, а -> вказує від якого до якого процесора відбувається пересилання підматриць B.

На рис. 2.5 наведена граф-схема виконання алгоритму множення двох матриць на кільцевій структурі з завантаженням через один з процесорів.

Рис. 2.5. Граф-схема виконання алгоритму множення двох матриць на кільцевій структурі з завантаженням через один з процесорів

На граф-схемі (рис. 2.5) представлено N процесорних елементів (в нашому випадку - 8). Дані завантажуються першим процесором, який має доступ до пам'яті. Він у відповідності із деревом завантаження вхідних даних (рис. 2.2) розсилає дані всім іншим процесорам. Кожен процесор отримує свою частину матриці А та B. Після завершення розсилки даних розпочинається сам процес обчислення, підчас якого обмін між процесорами відбувається по структурі зв'язків за маршрутом, вказаним на рис. 2.4. Процес множення - пересилання повторюється 8 разів. Після виконання останнього перемноження, розпочинається збір результатів. В результаті чого всі процесори у відповідності із деревом вивантаження (рис. 2.3) перешлють часткові результати до першого процесора, який їх складає у повну матрицю-результат і записує у пам'ять.



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

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

Рис. 3.1.Частина функціональної схеми, яка відповідає за завантаження даних.

Згідно з схемою рис. 3.1 дані поступово завантажуються і передаються через один процесор, в даному випадку це процесор №4. Процесор 4 через процесори 3, 5 і 6 пересилає підматриці на кожен процесор.На схемі зображені блоки завантаження і пересилання даних. Кожен блок відповідно до часу потрібного для його виконання має відповідні розміри(блоки однакові, так як три завантаження виконується за такий же час, як і одна пересилка). Весь процес завантаження розділений на чотири рівні, кожен рівень синхронізується до операції, яка найдовше виконується.

Рис. 3.2.Частина функціональної схеми, яка відповідає за перемноження матриць.

Відповідно до схеми рис. 3.2 відбувається перемноження матриці А на матрицю В на структурі з 8-ми процесорів. Розмір блоків відповідає часу потрібному для виконання вказаної операції. Процес перемноження складається з 8-ми рівнів перемноження і з 7-ми рівнів пересилання даних. Дана схема складається з блоків множення та додавання і блоків пересилання даних.

Рис. 3.3.Частина функціональної схеми, яка відповідає за вивантаження результатів.

Відповідно до схеми рис. 3.3 процес вивантаження складається з чотирьох рівнів.

На кожному рівні синхронізація відбувається згідно блоку, який виконується найдовше. В даній схемі присутні блоки двох типів: пересилання результату і вивантаження в пам'ять. Розміри блоків вказані відповідно до часу який потрібний для їх виконання(блоки однакові, так як три вивантаження виконується за такий же час, як і одна пересилка)..



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

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

Множення відбувається наступним чином: процесори перемножують відповідну підматрицю матрицю А та підматрицю B.

Для процесорних елементів визначимо такі розміри підматриць:

А0-7[15, 112], B0-2[112, 14],

B2-7[112, 15].

Розбиття матриці А [120, 112] на підматриці для кожного процесора:

№	Рядків	Стовпців
0	15	112
1	15	112
2	15	112
3	15	112
4	15	112
5	15	112
6	15	112
7	15	112

Розбиття матриці В [112, 117] на підматриці для кожного процесора:

№	Рядків	Стовпців
0	112	14
1	112	14
2	112	14
3	112	15
4	112	15
5	112	15
6	112	15
7	112	15

Співвідношення часових параметрів згідно варіанту tu= 10ts=2tp=6tz=6tw

tU= 2 * tP

tS=2/10* tP

tZ= 2/6* tP

tW= 2/6* tP

Дані завантажуються через 1 процесор.

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

Час виконання операцій множення та додавання:

Час виконання операцій завантаження:

Час виконання операцій вивантаження:

Отже час виконання послідовного алгоритму:

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

Обчислення часу виконання операцій завантажень:

Операція початкового завантаження матриць A та B виконується одним процесором послідовно, тому загальний час завантаження з пам'яті буде рівний сумі елементів в матрицях.

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

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

Час множення на одній ітерації (вибираєм, ту на якій найбільше значень)та загальний:

де n1ч - найбільша частина матриці А при розбитті, n3ч - найбільша частина матриці В при розбитті.

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

Час додавання (в найгіршому випадку) на одній ітерації та загальний:

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

Час пересилання (в найгіршому випадку) на одній ітерації (отримання нового рядка та пересилання існуючого)

Загальний час пересилання під час процесу множення (в найгіршому випадку) для кількості процесорів p1 = 8:

Час вивантаження є часом вивантаження одної результуючої матриці С з процесора 4 в пам'ять:

В моєму випадку послідовно будуть виконуватись тільки завантаження матриць 1, 2, 8 і вивантаження матриці 6

, де ,,,,,-відповідно розміри матриць 1, 2, 8.

, де ,-розміри матриці 6

Загальний час виконання множення матриць на паралельному алгоритмі, використовуючи дану систему:

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

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



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

5.1 Розробка блок-схеми алгоритму

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

Рис. 5.1.Блок-схема роботи програми.

Згідно з блок-схемою програма повинна завантажувати дані через один процесор і розсилати їх на всі процесори згідно з вибраним алгоритмом. Після розсилання даних відбувається 8 циклів перемноження матриці. Після того як на кожному процесорі сформується результуючі підматриці всі дані збираються на одному процесорі.



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

Дана програма написана на мові C++. Для розробки самого паралельного алгоритму множення матриць було обрано шлях використання інтерфейсу передачі повідомлень (МРІ) між процесами, оскільки він має наступні можливості:

створення програм багатопроцесорної обробки інформації;

велика кількість функцій для обміну повідомленнями між процесами;

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

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

MPI розшифровується як "Message passing interface" ("Взаємодія через передачу повідомлень"). Кілька плутає справу той факт , що цей термін вже застосовується по відношенню до апаратної архітектурі ЕОМ. Програмний інструментарій MPI реалізований в тому числі і для ЕОМ з такою архітектурою .

MPI надає програмісту єдиний механізм взаємодії гілок всередині паралельного додатка незалежно від машинної архітектури (однопроцесорні / багатопроцесорні із загальною / роздільною пам'яттю), взаємного розташування гілок (на одному процесорі / на різних ) і API операційної системи.

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

В даний час різними колективами розробників написано кілька програмних пакетів , які відповідають специфікації MPI , зокрема: MPICH , LAM , HPVM і так далі. Вони виступають базовими при перенесенні MPI на нові архітектури ЕОМ.

Мінімально до складу MPI входять: бібліотека програмування (заголовні і бібліотечні файли для мов Сі , Сі + + і Фортран ) і завантажувач додатків.

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

В МРІ функціях використовується поняття комунікатор. - це спеціально створений службовий об'єкт, який об'єднує групу процесів і ряд додаткових параметрів (контекст), використовуваних при виконанні операцій передачі даних.

При розробці програмного коду були використані наступні функції бібліотеки МРІ:

int MPI_Init(int *argc, char ***argv), де

argc - вказівник на кількість параметрів командного рядка;

argv - параметри командного рядка.

Використовується для ініціалізації середовища виконання MPI-програми.

int MPI_Finalize(void).

Завершує виконання МРІ програми.

int MPI_Comm_size(MPI_Comm comm, int *size), де

comm - комунікатор, розмір якого визначається;

size - визначена кількість процесів в комунікаторі.

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

int MPI_Comm_Rank(MPI_Comm comm, int *rank), де

comm - комунікатор, в якому визначається ранг процесу;

rank - ранг процесу в комунікаторі.

Визначає ранг процесу.

Як правило, виклик функцій Mpi_comm_size і Mpi_comm_rank виконується відразу після Mpi_init для отримання загальної кількості процесів і рангу поточного процесу.

int MPI_Send(void *buf, int count, MPI_Datatype type, int dest, int tag, MPI_Comm comm), де

buf - адреса буфера пам'яті, в якому розташовуються дані повідомлення, що відправляється;

count - кількість елементів даних в повідомленні;

type - тип елементів даних повідомлення, що пересилається;

dest - ранг процесу, якому відправляється повідомлення;

tag - значення-тег, що використовується для ідентифікації повідомлення;

comm - комунікатор, в рамках якого виконується передача даних.

Викликається процесом-відправником для відправлення повідомлення іншому процесу.

int MPI_Recv(void *buf, int count, MPI_Datatype type, int source,int tag, MPI_Comm comm, MPI_Status *status), де

buf, count, type - буфер пам'яті для прийому повідомлення, призначення кожного окремого параметра відповідає опису в MPI_Send.

source - ранг процесу, від якого повинен бути виконаний прийом повідомлення.

tag - тег повідомлення, яке повинне бути прийняте для процесу.

comm - комунікатор, в рамках якого виконується передача даних.

status - вказівник на структуру даних з інформацією про результат виконання операції прийому даних.

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

int MPI_Sendrecv_replace(void *buf, int count, MPI_Datatype datatype, int dest, int sendtag, int source, int recvtag, MPI_Comm comm, MPI_Status *status)

buf, count, type - буфер пам'яті для прийому повідомлення, призначення кожного окремого параметра відповідає опису в MPI_Send.

dest - ранг процесу, якому відправляється повідомлення;

sendtag - значення-тег, що використовується для ідентифікації повідомлення;

source - ранг процесу, від якого повинен бути виконаний прийом повідомлення.

recvtag - тег повідомлення, яке повинне бути прийняте для процесу.

comm - комунікатор, в рамках якого виконується передача даних.

status - вказівник на структуру даних з інформацією про результат виконання операції прийому даних.

Дана функція викликається процесом для одночасного відправлення повідомлення і прийому від іншого процесу. В ході виконання вміст буфера заміщається.

int MPI_Isend(void *buf, int count, MPI_Datatype type, int dest, int tag, MPI_Comm comm, MPI_Request *request), де

buf - адреса буфера пам'яті, в якому розташовуються дані повідомлення, що відправляється;

count - кількість елементів даних в повідомленні;

type - тип елементів даних повідомлення, що пересилається;

dest - ранг процесу, якому відправляється повідомлення;

tag - значення-тег, що використовується для ідентифікації повідомлення;

comm - комунікатор, в рамках якого виконується передача даних.

request - - вказівник на ідентифікатор комунікаційної події;

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

int MPI_Wait (MPI_Request *request, MPI_Status *status), де

request - вказівник на ідентифікатор комунікаційної події;

status - вказівник на структуру даних з інформацією про результат виконання операції прийому даних.

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

int MPI_Waitall (int count, MPI_Request *array_of_requests, MPI_Status *array_of_statuses), де

count - кількість елементів в масиві ідентифікаторів;

array_of_requests - масив ідентифікаторів комунікаційних подій;

array_of_statuses - масив структур даних з інформацією про результат виконання операції прийому даних.

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

Для елементів матриць був обраний цілий тип int, а у функціях передачі повідомлень МРІ використаний наслідуваний тип MPI_INT із мови С.

Всі вхідні матриці та вихідні результуючі матриці паралельного та послідовного алгоритмів зберігаються у файлах (example.txt, input.txt, output.txt, test.txt відповідно) у вигляді лінійного представлення матриць із розподіленням 1 рядок матриці на 1 рядок файлу.

Код генератора вхідних матриць присутній на початку програми до МРІ частини коду і може бути використаний для генерації нових матриць та відповідних їм файлів.



5.4 Результат роботи програми

Рис. 5.2 Результати роботи програми.

Завантаження даних на процесори відбувається з файла. Файл був заздалегідь згенерований. Як видно з рис.5.2 програма працює коректно і видає результати множення.



Висновок

В результаті виконання курсової роботи я розробив паралельний алгоритм множення матриці на матрицю, для чого використав кільцеву структуру, яка складається з 8 процесорів з завантаженням даних через один процесор. Також було обчислено час множення, додавання, завантаження і вивантаження, які дають уявлення про характеристики даного паралельного алгоритму та порівняння його із звичайним послідовним алгоритмом. В результаті проведеної роботи можна зробити наступні висновки. Для алгоритму, реалізованого на даній структурі та матриць розмірності 120x112 і 112x117, умовний час виконання для послідовного алгоритму - Tпос = 3474256, а паралельного - = 468448, що приблизно в 7,4 разів швидше. Ефективність розпаралелення виявилась рівною Е ? 0,9336, що є високим показником, який забезпечується кількістю 8 робочих процесорів та досить великим об'ємом даних.

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

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

Размещено на Allbest.ru

...