Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Паралельне виконання операцій множення матриць
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Кафедра ЕОМ
Інформація про роботу
Рік:
2014
Тип роботи:
Курсова робота
Предмет:
Паралельні та розподілені обчислення
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ І НАУКИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ „ЛЬВІВСЬКА ПОЛІТЕХНІКА”
Кафедра ЕОМ
Курсова робота
з дисципліни: “ Паралельні та розподілені обчислення”
на тему:
«Паралельне виконання операцій множення матриць»
Завданння
Задаються дві матриці А (розмірністю n1*n2) та В (розмірністю n2*n3) :
n1=3П, n2=2І, n3=4Б – КІ-42, де 3П=Ц(300), 2І=А(64), 4Б=Р(159)
n1=300, n2=64, n3=159
Отже маємо матрицю А(300*64) та матрицю В(64*159)
Розробити та описати алгоритм множення матриць А*В на структурі яка задається виразом:
5b-12b-6b-11b-8b-1b-3b-13b – КІ-42, де «nb»- номер букви П.І.Б студента.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
М
А
Ц
Ю
К
Т
А
Р
А
С
І
Г
О
Р
О
В
И
Ч
6
7
1
3
5
4
2
8
Отримаємо – КГТІРМЦО
Для КГТІРМЦО отримаємо 47,74,198,223,93,43,201,250. Даний набір чисел записуємо у стовпець і переводимо у двійкове 8-ми розрядне число:
047 -
00101111
074 -
01001010
198 -
11000110
223 -
11011111
093 -
01011101
043 -
00101011
201 -
11001001
250 -
11111010
В отриманій двійковій матриці одиниці що розташовані на головній діагоналі замінюємо на 0.
0
0
1
0
1
1
1
1
=>
0
0
1
0
1
1
1
1
0
1
0
0
1
0
1
0
0
0
0
0
1
0
1
0
1
1
0
0
0
1
1
0
1
1
0
0
0
1
1
0
1
1
0
1
1
1
1
1
1
1
0
0
1
1
1
1
0
1
0
1
1
1
0
1
0
1
0
1
0
1
0
1
0
0
1
0
1
0
1
1
0
0
1
0
1
0
1
1
1
1
0
0
1
0
0
1
1
1
0
0
1
0
0
1
1
1
1
1
1
0
1
0
1
1
1
1
1
0
1
0
Отримана матриця розміру 8*8 є матрицею зв’язків орієнтованого графу, вершини якого це процесори а напрямлені дуги це напрямлені лінії зв’язку між процесорами. На основі цієї матриці будується відповідний їй граф що характеризує конкретну 8-ми процесорну систему (структуру) із напрявленими зв’язками між вершинами.
Для цієї структури визначити час виконання алгоритму, відсоток послідовної частини алгоритму та ефективність алгоритму для значень, співвідношення часових параметрів та тип початкового завантаження визначаються за правилами:
3.1. Тип початкового завантаження даних type:
, де Zi цифри номера залікової книжки, n=1..k, де k – кількість цифр номера залікової книжки.
Zi=1009587, n=7
type=1(спільна пам’ять)
3.2. Співвідношення часових параметрів tU,tS,tP,tZ,tW:
tU – час виконання однієї операції множення;
tS - час виконання однієї операції сумування;
tP - час виконання однієї операції пересилання даних між процесорами;
tZ - час виконання операції завантаження одних даних;
tW - час виконання операції вивантаження одних даних.
tU=(Zk-3 +1)tS=(Zk-2 +1)tP=(Zk-1 +1)tZ=(Zk+1)tW, де Zi відповідна цифра номера залікової книжки, k -кількість цифр в номері залікової книжки.
tU=10tS=1tP=9tZ=4tW
Анотація
В даній курсовій роботі було розроблено програму для множення двох матриць розміром 190*216 та 216*73 на восьми процесорах, з заданою структурою зв’язків. Завантаження даних в процесори відбувається через спільну пам’ять. Також було розроблено функціональну схему і визначено основні характеристики розробленого паралельного алгоритму. Для реалізації паралельного алгоритму множення матриць було використано інтерфейс передачі повідомлень (МРІ) між процесами, оскільки він має широкі можливості. Для програмної реалізації алгоритму було обрано мову С++, з використанням MPI. Наведені граф-схеми виконання алгоритму, схеми планування обчислень і блок-схеми програми множення матриць пояснюють реалізацію даного алгоритму більш детально.
Аnnotation
In this term paper has developed a program to multiply two matrices of size 300 * 64 and 64 * 159 on eight processors of a given structure relationships. Loading data into the processor takes place through shared memory. They also developed a functional diagram and the main characteristics of the developed parallel algorithm . To implement the parallel matrix multiplication algorithm used message passing interface ( MPI ) between processes, since it has great potential . For a software implementation of the algorithm was chosen language C + +, using MPI. The following graph charts the algorithm , computation and scheduling schemes flowchart program matrix multiplication implementation of this algorithm is explained in more detail.
Зміст
Вступ…………………………………………………………………………………...7
1. Теоретичний розділ 8
1.2 Інтерфейс передачі повідомлень……………………………………………......13
2. Проектування граф-схеми виконання алгоритму 155
3. Розробка функціональної схеми 2121
4. Розрахунковий розділ 233
5. Розробка програми виконання заданої функції 256
Висновок……………………………………………………………………………...30
Список використаної літератури…………………………………………………....31
Додатки…………………………………………………………………………….…32
Вступ
На сьогоднішній день найбільш перспективні дві основні технології, які мають багато спільного: паралельні та розподілені обчислення.
У паралельних обчисленнях бере участь обладнання, що знаходиться, як правило, в одному фізичному місці, вони тісно поєднані між собою і всі параметри їх роботи відомі програмісту. У розподілених обчисленнях немає тісного постійного зв'язку між вузлами, вони розподілені по деякій території і параметри роботи цієї системи динамічні і не завжди відомі.
Існують різні методи і технології паралельних і розподілених обчислень, постійне зростання використання яких в сучасній практичній діяльності можна пояснити наступними обставинами:
• надзвичайно швидке зростання складності об'єктів моделювання (перехід від простих до складних ("великим") системам);
• перехід до вирішення завдань, вирішення яких вимагає досліджень, які необхідні для проведення ретельного аналізу складної поведінки ;
• необхідність управління складними промисловими і технологічними завданнями в режимі реального часу і в умовах невизначеності;
• зростання кількості завдань, для вирішення яких необхідно обробляти гігантські обсяги інформації.
Домінуюче положення при розробці паралельних програм для паралельних систем займає стандарт MPI (англ. Message Passing Interface). Програма, розроблена в моделі передачі повідомлень, може бути представлена інформаційним графом, вершинам якого відповідають паралельні гілки програми, а ребрам комунікаційні зв'язки між ними. Це можна використовувати для диспетчеризації завдань та їх обчислювальних потоків. Враховуючи гетерогенність обчислювальних ресурсів і середовищ передачі даних у кластері, можна здійснити розподіл обчислювальних потоків (гілок) з обчислювальних вузлів так, щоб мінімізувати накладні витрати на обмін даними між потоками і вирівняти обчислювальне навантаження між вузлами.
Теоретичний розділ
Матриця — математичний об'єкт, записаний у вигляді прямокутної таблиці чисел (чи елементів кільця) і допускаючий операції (додавання, віднімання, множення та множення на скаляр). Зазвичай матриці представляються двовимірними (прямокутними) таблицями. Іноді розглядають багатовимірні матриці або матриці непрямокутної форми. В даній статті вони розглядатися не будуть.
Матриці є корисними для запису даних, що залежать від двох категорій, наприклад: для коефіцієнтів систем лінійних рівнянь та лінійних перетворень.
Горизонтальні лінії в матриці звуть рядками, вертикальні — стовпцями.
Матрицю, що складається з m рядків та n стовпців, називають матрицею m-на-n (або mn-матрицею), а m і n — її розмірністю.
Елемент матриці A, що знаходиться на перетині i-го рядка з j-им стовпчиком, називають i,j-им елементом або (i,j)-им елементом A.
Записують це як Ai,j чи A[i,j], або, в нотації мови програмування C, A[i][j].
Часто пишуть для означення матриці A розмірності n x m, де кожен елемент матриці A[i,j] позначають як aij для всіх 1 ≤ i ≤ n та 1 ≤ j ≤ m.
Приклад
Матриця є матрицею 4×3. Елемент A[2,3], або a2,3 дорівнює 7.
Множення матриці на вектор і матриці на матрицю є базовими макроопераціями для багатьох задач. Для їх реалізації використовуються різні алгоритми та різні структури. Розмаїтість варіантів алгоритмів виникає із-за розмаїтості обчислювальних систем і розмаїтості розмірів задач. Стандартний алгоритм множення матриці на матрицю наведений на Рис.1.1:
Рис.1.1 Алгоритм множення матриці на матрицю
Множення двох матриць має сенс лише тоді, коли число стовпчиків першої матриці дорівнює числу рядків другої матриці. Якщо A — матриця m-на-n (m рядків, n стовпчиків), а B — матриця n-на-p (n рядків, p стовпчиків), їх добуток AB є матрицею m-на-p (m рядків, p стовпчиків), що розраховується за формулою:
(AB)[i, j] = A[i, 1] * B[1, j] + A[i, 2] * B[2, j] + ... + A[i, n] * B[n, j] для кожної пари i та j.
Наприклад,
Це множення має такі властивості:
(AB)C = A(BC) для всіх матриць A розмірності k-на-m, B розмірності m-на-n і C розмірності n-на-p (асоціативність).
(A + B)C = AC + BC для всіх матриць A і B розмірності m-на-n і матриць C розмірності n-на-k (дистрибутивність).
C(A + B) = CA + CB для всіх матриць A і B розмірності m-на-n і матриць C розмірності k-на-m (дистрибутивність).
Зауваження: комутативність має місце не завжди: для добутку певних матриць A і B може бути AB ≠ BA.
Матриці називають антикомутативними, якщо AB = −BA. Такі матриці є дуже важливими в представленнях алгебр Лі та в представленнях алгебр Кліффорда.
Розглядаються і різні варіанти завантаження даних у систему: завантаження даних через один з процесорів, завантаження даних безпосередньо кожним процесором з розподіленої пам'яті, завантаження даних з спільної пам'яті. Якщо завантаження даних здійснюється через один з процесорів, то дані зчитуються цим процесором з пам'яті, розрізаються на частини, які розсилаються іншим процесорам. Але дані можуть бути підготовлені і заздалегідь, тобто заздалегідь розрізані вроздріб і кожна частина записана в окрему пам'ять, потім кожен процесор безпосередньо зчитує з пам'яті призначений для нього файл.
Алгоритм перемноження матриці на матрицю на кільцевій структурі
Задано дві вихідні матриці A і B. Обчислюється добуток C = А х B, де А - матриця n1 х n2, B - матриця n2 х n3. Матриця результатів C має розмір n1 х n3. Вихідні матриці попередньо розрізані на смуги, ці смуги записані в пам'ять. Матриця результатів повертається в нульовий процес. Реалізація алгоритму виконується на кільці з p1 процесорів. Матриці розрізані як наведено на рис. 1.2: матриця А розрізана на p1 горизонтальних смуг, матриця B розрізана на p1 вертикальних смуг, і матриця результату C розрізана на p1 смуги. Передбачається, що в пам'ять кожного процесора завантажується і може зберігатися тільки одна смуга матриці А і одна смуга матриці B.
Рис.1.2 Методи розрізування даних для виконання паралельного алгоритму добутку двох матриць при обчисленні на кільці процесорів. Виділені смуги розміщення в пам’яті одного процесора.
Дані можуть бути підготовлені і заздалегідь, тобто заздалегідь розрізані вроздріб і кожна частина записана на диск у виді окремого файлу зі своїм ім'ям; потім кожен комп'ютер безпосередньо зчитує з диску, призначений для нього файл. Вихідні матриці попередньо розрізані на смуги, смуги записані на дискову пам'ять окремими файлами зі своїми іменами і доступні всім комп'ютерам. Матриця результатів повертається в нульовий процес. Нижче подані схеми виконання перемноження матриць на кільцевій структурі (для обох випадків: коли пересилаються стовбці матриці А або, коли пересилаються рядки матриці В)
Рис. 1.3а. Схема множення матриць на кільцевій структурі (пересилання стовбців матриці А)
Рис. 1.3б. Схема множення матриць на кільцевій структурі (пересилання рядків матриці В)
Оскільки за умовою в процесорах знаходиться по одній смузі матриць, то смуги матриці B (або смуги матриці A) необхідно "прокрутити" по кільцю процесорів повз смуги матриці A (матриці B). Кожний зсув смуг уздовж кільця і відповідна операція множення наведена на рис.1.3 у виді окремого кроку. На кожному з таких кроків обчислюється тільки частина смуги. Процес i обчислює на j-м кроці добуток i-й горизонтальної смуги матриці A j-ї вертикальної смуги матриці B, добуток отримується у підматриці(i,j) матриці C.
Обчислення відбувається в такій послідовності:
Кожен процесор зчитує з пам’яті відповідну йому смугу матриці А. Нульова смуга повинна зчитуватися нульовим процесором, перша смуга - першим і т.д.
Кожен процесор зчитує з пам’яті відповідну йому смугу матриці B. Нульова смуга повинна зчитуватися нульовим процесором, перша смуга - першим і т.д.
Обчислювальний крок 1. Кожен процес обчислює одну підматрицю добутку. Вертикальні смуги матриці B зсуваються уздовж кільця процесорів і т.д. до обчислювального кроку p1.
Обчислювальний крок p1. Кожен процес обчислює одну підматрицю добутку. Вертикальні смуги матриці B зсуваються уздовж кільця процесорів.
Матриця C збирається в нульовому процесорі.
Якщо "прокручувати" вертикальні смуги матриці B, то матриця С буде розподілена горизонтальними смугами, а якщо "прокручувати" горизонтальні смуги матриці A, то матриця С буде розподілена вертикальними смугами.
Алгоритм характерний тим, що після кожного кроку обчислень здійснюється обмін даними
Якщо час передачі даних великий в порівнянні з часом обчислень, або канали передачі повільні, то ефективність алгоритму буде невисока.
1.2 Інтерфейс передачі повідомлень
У 1994 р. був прийнятий стандарт механізму передачі повідомлень MPI (Message Passing Interface). Він готувався з 1992 по 1994 рр.. групою Message Passing Interface Forum, до якої увійшли представники більш ніж 40 організацій з Америки і Європи. Основна мета, яку ставили перед собою розробники MPI - це забезпечення повної незалежності додатків, написаних з використанням MPI, від архітектури багатопроцесорної системи, без якої-небудь істотної втрати продуктивності. Підтвердженням того, що ця мета була досягнута, служить той факт, що в даний час цей стандарт підтримується практично всіма виробниками багатопроцесорних систем. Реалізації MPI успішно працюють не тільки на класичних MPP системах, але також на SMP системах і на мережах робочих станцій (в тому числі і неоднорідних).
MPI - це бібліотека функцій, забезпечує взаємодію паралельних процесів за допомогою механізму передачі повідомлень. Підтримуються інтерфейси для мов C і FORTRAN. Останнім часом додана підтримка мови C + +. Бібліотека включає в себе безліч функцій передачі повідомлень типу точка-точка, розвинутий набір функцій для виконання колективних операцій і управління процесами паралельного застосування. Основна відмінність MPI від попередників в тому, що явно вводяться поняття груп процесів, з якими можна оперувати як з кінцевими множинами, а також областей зв'язку та комунікаторів, що описують ці галузі зв'язку. Це надає програмісту дуже гнучкі засоби для написання ефективних паралельних програм. В даний час MPI є основною технологією програмування для багатопроцесорних систем з розподіленою пам'яттю.
Альтернативний підхід надає парадигма паралельної обробки даних, що реалізована в мові високого рівня HPF. Від програміста вимагається тільки задати розподіл даних по процесорах, а компілятор автоматично генерує виклики функцій синхронізації і передачі повідомлень (невдале розташування даних може викликати істотне збільшення накладних витрат). Для розпаралелювання циклів використовуються або спеціальні конструкції мови (оператор FORALL), або директиви компілятору, що задаються у вигляді псевдокомментаріев ($ HPF INDEPENDENT). Мова HPF реалізує ідею інкрементального розпаралелювання і модель загальної пам'яті на системах з розподіленою пам'яттю. Ці дві обставини і визначають простоту програмування і відповідно привабливість цієї технології. Одна і та ж програма, без якої-небудь модифікації, повинна ефективно працювати як на однопроцесорних системах, так і на багатопроцесорних обчислювальних системах.
Програми на мові HPF істотно коротше функціонально ідентичних програм, використовують прямі виклики функцій обміну повідомленнями. Мабуть, мови цього типу будуть активно розвиватися і поступово витіснять з широкого обігу пакети передачі повідомлень. Останнім буде відводитися роль, яка в сучасному програмуванні відводиться асемблеру: до них вдаватимуться лише для розробки мов високого рівня і при написанні бібліотечних підпрограм, від яких потрібна максимальна ефективність. У середині 90-х років, коли з'явився HPF, з ним зв'язувалися великі надії, проте труднощі з його реалізацією поки що не дозволили створити досить ефективних компіляторів. Мабуть, найбільш вдалими були проекти, в яких компіляція HPF-програм виконується в два етапи. На першому етапі HPF-програма перетворюється на стандартну Фортран-програму, доповнену викликами комунікаційних підпрограм. А на другому етапі відбувається її компіляція стандартними компіляторами. Тут слід зазначити систему компіляції Adaptor, розроблену німецьким Інститутом алгоритмів і наукових обчислень, і систему розробки паралельних програм DVM, створену в Інституті прикладної математики ім. М.В. Келдиша РАН. Система DVM підтримує не тільки мову Фортран, але і C. Наш досвід роботи з системою Adaptor показав, що в більшості випадків ефективність паралельних HPF-програм значно нижче, ніж MPI-програм. Тим не менш, в деяких простих випадках Adaptor дозволяє разпаралелить звичайну програму додаванням в неї всього кілька рядків.
Проектування граф-схеми виконання алгоритму
Алгоритм перемноження матриць на багатопроцесорній структурі складається з декількох етапів:
визначення зв’язків між процесорами, на яких будуть перемножуватись матриці;
розбиття матриць на частини і розсилання кожному процесору його підматриці;
обчислення результату;
збереження результату.
Задаються дві матриці А (розмірністю n1*n2) та В (розмірністю n2*n3) :
n1=3П, n2=2І, n3=4Б – КІ-42, де 3П=Ц(300), 2І=А(64), 4Б=Р(159)
n1=300, n2=64, n3=159
Отже маємо матрицю А(300*64) та матрицю В(64*159)
Розробити та описати алгоритм множення матриць А*В на структурі яка задається виразом:
5b-12b-6b-11b-8b-1b-3b-13b – КІ-42, де «nb»- номер букви П.І.Б студента.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
М
А
Ц
Ю
К
Т
А
Р
А
С
І
Г
О
Р
О
В
И
Ч
6
7
1
3
5
4
2
8
Отримаємо – КГТІРМЦО
Для КГТІРМЦО отримаємо 47,74,198,223,93,43,201,250. Даний набір чисел записуємо у стовпець і переводимо у двійкове 8-ми розрядне число:
047 -
00101111
074 -
01001010
198 -
11000110
223 -
11011111
093 -
01011101
043 -
00101011
201 -
11001001
250 -
11111010
В отриманій двійковій матриці одиниці що розташовані на головній діагоналі замінюємо на 0.
0
0
1
0
1
1
1
1
=>
0
0
1
0
1
1
1
1
0
1
0
0
1
0
1
0
0
0
0
0
1
0
1
0
1
1
0
0
0
1
1
0
1
1
0
0
0
1
1
0
1
1
0
1
1
1
1
1
1
1
0
0
1
1
1
1
0
1
0
1
1
1
0
1
0
1
0
1
0
1
0
1
0
0
1
0
1
0
1
1
0
0
1
0
1
0
1
1
1
1
0
0
1
0
0
1
1
1
0
0
1
0
0
1
1
1
1
1
1
0
1
0
1
1
1
1
1
0
1
0
Отримана матриця розміру 8*8 є матрицею зв’язків орієнтованого графу, вершини якого це процесори а напрямлені дуги це напрямлені лінії зв’язку між процесорами. На основі цієї матриці будується відповідний їй граф що характеризує конкретну 8-ми процесорну систему (структуру) із напрявленими зв’язками між вершинами.
Для цієї структури визначити час виконання алгоритму, відсоток послідовної частини алгоритму та ефективність алгоритму для значень, співвідношення часових параметрів та тип початкового завантаження визначаються за правилами:
3.1. Тип початкового завантаження даних type:
, де Zi цифри номера залікової книжки, n=1..k, де k – кількість цифр номера залікової книжки.
Zi=1009587, n=7
type=1(спільна пам’ять)
3.2. Співвідношення часових параметрів tU,tS,tP,tZ,tW:
tU – час виконання однієї операції множення;
tS - час виконання однієї операції сумування;
tP - час виконання однієї операції пересилання даних між процесорами;
tZ - час виконання операції завантаження одних даних;
tW - час виконання операції вивантаження одних даних.
tU=(Zk-3 +1)tS=(Zk-2 +1)tP=(Zk-1 +1)tZ=(Zk+1)tW, де Zi відповідна цифра номера залікової книжки, k -кількість цифр в номері залікової книжки.
tU=10tS=1tP=9tZ=4tW
Кожен процесор по черзі звертається до спільної пам’яті і завантажує свою частину матриць А і В. Після того, як дані завантаженні відбувається процес обчислення. Обчислення складається з 8-ми циклів множення і додавання і 7 циклів обміну під матрицями В. Як тільки на кожному процесорі сформуються результуючі підматриці розпочинається процес вивантаження підматриці в пам'ять. Кожен процесор по черзі звертається до спільної пам’яті і вивантажує свою результуючу підматрицю.
На рис. 2.1 наведена граф-схема зв’язків між процесорами заданої структури. Дана граф-схема дозволяє визначити комунікації між процесорами. При розробці алгоритму множення матриць комунікації відіграють важливу роль. Від зв’язків між процесорами залежить алгоритм розсилання даних, збору і обміну підматрицею Ві при перемноженні матриць.
Рис.2.1 Граф можливого обміну
Так як, завантаження відбувається з спільної пам’яті, то всі процесори звертаються до пам’яті послідовно і кожен завантажує для себе свої підматриці.
Вивантаження відбувається аналогічно до завантаження, кожен процесор послідовно звертається в пам'ять і зберігає свій результат.
В даній структурі зв’язків від процесорами можна виділити кільце, тому обмін підматрицею Ві при перемноженні матриць буде виконуватись по вибраному кільцю, з процесорів (0,2,5,7,1,4,3,6), яке можна виділити з графу (Рис. 2.2.).
Рис.2.2 Обмін по кільцевій структурі
Оскільки пам’ять спільна, то завантаження вхідних та вивантаження вихідних даних буде виконуватись послідовно. Тому в такому випадку граф обміну даних між процесорами та пам’яттю набуде наступного вигляду Рис. 2.3.
Рис. 2.3 Граф обміну даних між процесорами та пам’яттю
На рис. 2.4 наведено граф-схему виконання алгоритму покрокового перемноження двох матриць.
Рис. 2.4 Граф-схему виконання алгоритму покрокового перемноження двох матриць.
3.Розробка функціональної схеми
Рис. 3.1.Завантаженняданих з спільної пам’яті
Функціональна схема відображає комунікації між процесорами в ході виконання обчислень, а також покрокове виконання алгоритму.
Згідно з схемою рис. 3.1 дані кожен процесор послідовно звертається до спільної пам’яті і завантажує свої підматриці. Алгоритм є повністю послідовним і в той час як працює один процесор, на всіх інших відбувається простій.
4.Розрахунковий розділ
Для порівняння продуктивності виконання множення при використанні паралельного та послідовного алгоритму, проведемо ряд обчислень.
Множення відбувається наступним чином: процесори перемножують відповідну підматрицю матрицю А та підматрицю B.
Дані завантажуються з спільної пам’яті.
Розміри матриць: n1=300, n2=64, n3=159.
Розміри підматриць:
A0-A3: [38, 64]; A4-A7:[37, 64]
B0-B6: [64, 20]; B0: [64, 19]
Розміри для розрахунків: n1r = 38(37); n3r = 20(19).
Виразимо часові параметри через найменший :
– час виконання однієї операції множення;
– час виконання однієї операції пересилання даних між процесорами;
– час виконання операції з авантаження одних даних;
– час виконання операції вивантаження одних даних;
– час виконання однієї операції сумування.
Час виконання виразу буде рівний:
Оскільки в нас є спільна пам'ять, то звернення кожного процесору до пам'яті і завантаження даних буде виконуватися послідовно, тобто загальний час :
Оскільки одночасно процесор може пересилати або приймати дані, тому час обміну даними між процесорами буде проводитися в два етапи.
Обчислюємо загальний час виконання множення матриць на даному алгоритмі:
Для характеристики алгоритму визначимо коефіцієнт К, який характеризує відсоток послідовних обчислень.
Ефективність визначається як відношення часу виконання алгоритму на однопроцесорній системі, до часу потрібного для виконання на багатопроцесорної системі, помноженого на кількість процесорів в ній.
Також порахуємо ефективність паралельного алгоритму. Ефективність визначається, як відношення часу виконання алгоритму на одно процесорній системі, до часу потрібного для виконання на багатопроцесорної системі, помноженого на кількість процесорів в ній.
5.Розробка програми виконання заданої функції
Першим кроком розробки програми для виконання заданої функції є розробка блок схеми алгоритму.
Рис. 5.1.Блок-схема роботи програми.
Згідно з блок-схемою програма повинна завантажувати дані з спільної пам’яті. Після розсилання даних відбувається 8 циклів перемноження матриці. Після того як на кожному процесорі сформується результуючі підматриці всі дані послідовно вивантажуються в пам'ять.
Для реалізації даної програми використовується бібліотека 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 - масив структур даних з інформацією про результат виконання операції прийому даних.
Дана функція викликається процесом-передавачем при неблокуючому передаванні даних, якщо необхідно дочекатися завершення отримання даних кількома процесами-приймачами.
Висновок
Після успішного виконання курсової роботи я оволодів технологією побудови багатопроцесорних системи. Розробив восьми процесорну систему множення двох матриць, при чому дані зчитуються з спільної пам’яті. Також було проведено деякі обчислення, які дають уявлення про характеристики даного паралельного алгоритму, та порівняно його з послідовним. В результаті проведеної роботи можна зробити такі висновки: для восьми процесорної системи та матриць з розмірами 300х64 64х159 умовний час виконання програми в інтервалах виконання операції виявився рівним , а для послідовної структури що приблизно в 3 рази довше. Ефективність при цьому рівна E = 37% , що є досить хорошим показником, але не ідеальним.
Список літератури
Корнеев В.В. Параллельные вычислительные системы. М.: Нолидж, 1999
С. Немнюгин, О.Стесик Параллельное программирование для многопроцессорных вычислительных систем. – СПб: БХВ-Петербург, 2002.
Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. – СПб: БХВ-Петербург, 2002.
Ортега Дж. Введение в параллельные и векторные методы решения линейных систем. М.:Мир, 1991.
Программирование на параллельных вычислительных системах: Пер с англ./Под ред. Р.Бэбба.М.:Мир, 1991.
Бройнль Т. Паралельне програмування: Початковий курс: Навчальний посібник. – К.:Вища школа.,1997.
Воеводин В.В. Математические основы параллельных вычислений.- М.: Изд-во МГУ, 1991.
Векторизация программ: теория, методы, реализация: Пер. с англ. и нем. /Под ред. Г.Д.Чинина. - М:. Мир, 1991.
Організація паралельних обчислень : Навчальний посібник з дисципліни “Паралельні та розподілені обчислення” для студентів базового напрямку 6.0915 "Комп'ютерна інженерія" / Укладачі: Є. Ваврук, О. Лашко – Львів: Національний університет “Львівська політехніка”, 2007, 70 с.
1http://www.parallel.ru – Інформаційно-аналітичний центр з паралельних обчислень.
http://www.csa.ru – Інститут високопродуктивних обчислень і баз даних.
http://www.hpc.nw.ru – Високопродуктивні обчислення.
04.06.2014 21:06-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора