Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Паралельне виконання операцій множення матриць
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
ІКТА
Факультет:
Комп'ютерна інженерія
Кафедра:
ЕОМ
Інформація про роботу
Рік:
2014
Тип роботи:
Курсова робота
Предмет:
Паралельні та розподілені обчислення
Група:
КІ 2
Частина тексту файла (без зображень, графіків і формул):
Міністерство Освіти та Науки України
Національний Університет “Львівська Політехніка”
Кафедра ЕОМ
Курсова робота
з дисципліни: “ Паралельні та розподілені обчислення ”
на тему:
«Паралельне виконання операцій множення матриць»
Завданння
Задаються дві матриці А (розмірністю n1*n2) та В (розмірністю n2*n3) :
n1=3П, n2=2І, n3=4Б – КІ-42, де 3П=И(160), 2І=А(64), 4Б=К(307)
n1=160, n2=64, n3=307
Отже маємо матрицю А(160*64) та матрицю В(64*307)
Розробити та описати алгоритм множення матриць А*В на структурі яка задається виразом:
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
19
20
21
22
23
24
Г
Р
И
Ц
Ю
К
П
А
В
Л
О
О
Л
Е
К
С
А
Н
Д
Р
О
В
И
Ч
7
8
1
3
5
2
4
9
Отримаємо – ЮОКЛАГИЕ
Для ЮОКЛАГИЕ отримаємо 63, 250, 47, 212, 27, 74, 91, 171. Даний набір чисел записуємо у стовпець і переводимо у двійкове 8-ми розрядне число:
063 -
00111111
250 -
11111010
047 -
00101111
212 -
11010100
027 -
00011011
074 -
01001010
091 -
01011011
171 -
10101011
В отриманій двійковій матриці одиниці що розташовані на головній діагоналі замінюємо на 0.
0
0
1
1
1
1
1
1
=>
0
0
1
1
1
1
1
1
1
1
1
1
1
0
1
0
1
0
1
1
1
0
1
0
0
0
1
0
1
1
1
1
0
0
0
0
1
1
1
1
1
1
0
1
0
1
0
0
1
1
0
0
0
1
0
0
0
0
0
1
1
0
1
1
0
0
0
1
0
0
1
1
0
1
0
0
1
0
1
0
0
1
0
0
1
0
1
0
0
1
0
1
1
0
1
1
0
1
0
1
1
0
0
1
1
0
1
0
1
0
1
1
1
0
1
0
1
0
1
0
Отримана матриця розміру 8*8 є матрицею зв’язків орієнтованого графу, вершини якого це процесори а напрямлені дуги це напрямлені лінії зв’язку між процесорами. На основі цієї матриці будується відповідний їй граф що характеризує конкретну 8-ми процесорну систему (структуру) із напрявленими зв’язками між вершинами.
Для цієї структури визначити час виконання алгоритму, відсоток послідовної частини алгоритму та ефективність алгоритму для значень, співвідношення часових параметрів та тип початкового завантаження визначаються за правилами:
3.1. Тип початкового завантаження даних type:
, де Zi цифри номера залікової книжки, n=1..k, де k – кількість цифр номера залікової книжки.
Zi=1009167, 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=2tP=7tZ=8tW
Анотація
В даній курсовій роботі розроблено програмну реалізацію восьми процесорної паралельної системи зі спільною пам’яттю, яка виконує множення двох матриць розмірами 160х64 та 64х307. Також наводяться числові значення характеристик даної системи таких як ефективність, коефіцієнт відношення часу виконання паралельної частини програми і часу виконання всієї програми. Проведено також порівняння даного алгоритму з простим послідовним за такими основним ознаками, як час виконання однакової задачі на різних алгоритмах, ефективність. Алгоритм виконання множення 2-ох матриць реалізований на С++ з консольним інтерфейсом, та з використанням MPI.
Зміст
Вступ………………………………………………………………………………..…. 6
1. Теоретичний розділ………………………………………………………………... 7
1.1 Алгоритм перемноження матриці на матрицю на кільцевій структурі .....8
1.2 Інтерфейс передачі повідомлень……………………………………………10
2. Аналіз(розробка) граф-схеми алгоритму множення матриць……………...…… 12
3. Розробка функціональної схеми……………………………………………........... 16
4. Розрахунковий розділ………………………………………………………………18
5. Розробка програми виконання заданої функції ……………………………..…..21
Висновок…………………………………………………………………………….… 26
Список літератури…………………………………………………………….……..27
Додаток………………………………………………………………………………28
Вступ
Ідея розпаралелювання обчислень базується на тому, що більшість задач може бути розділена на набір менших завдань, які можуть бути вирішені одночасно. Паралельні обчислення використовувалися багато років в основному в найпродуктивніших обчисленнях, в наш час це стало дуже актуальним питанням і має досить широке застосування у багатьох сферах нашого життя, таких як медицина, автомобілебудування, математика, фізика, астрономія, будівництво тощо.
Поява в останні роки великої кількості порівняно дешевих кластерних паралельних обчислювальних систем призвело до швидкого розвитку паралельних обчислювальних технологій, у тому числі і в області високопродуктивних обчислень. Останнім часом ситуація в галузі паралельних обчислювальних технологій почала кардинально змінюватися в зв'язку з тим, що більшість основних виробників мікропроцесорів стали переходити на багатоядерні архітектури. Зміна апаратної бази змушує змінювати і підхід до побудови паралельних алгоритмів. Для реалізації обчислювальних можливостей багатоядерних архітектур потрібна розробка нових паралельних алгоритмів.
Ефективність використання обчислювальних ресурсів, яку будуть мати кластери нового покоління, напряму залежатиме від якості власне паралельних програм, так і спеціалізованих бібліотек чисельних алгоритмів, орієнтованих на багатоядерні архітектури.
1. Теоретичний розділ
Основна ідея розпаралелювання обчислень – мінімізація часу виконання задачі за рахунок розподілу навантаження між декількома обчислювальними пристроями. Цими «обчислювальними пристроями» можуть бути як процесори одного суперкомп'ютера, так і кілька комп'ютерів, обєднаних за допомогою комунікаційної мережі в єдину обчислювальну структуру – кластер. Паралельна модель програмування сильно відрізняється від звичайної – послідовної. Існують дві моделі паралельного програмування: модель паралелізму даних і модель паралелізму задач. Модель паралелізму даних має на увазі незалежну обробку даних кожним процесом (наприклад, векторні операції з масивами). Модель паралелізаму задач передбачає розбиття основної задачі на самостійні підзадачі, кожна з яких виконується окремо й обмінюється даними з іншими. Це більш трудомісткий, у порівнянні з паралелізмом даних, підхід. Перевагою є велика гнучкість і велика воля, надана програмісту в розробці програми, що ефективно використовує ресурси паралельної системи. При цьому можуть застосовуватися спеціалізовані бібліотеки, що беруть на себе всі «організаційні» задачі. Приклади таких бібліотек: MPI (Message Passing Interface) і PVM (Parallel Virtual Machine).
Множення матриці на вектор і матриці на матрицю є базовими макроопераціями для багатьох задач лінійної алгебри, наприклад ітераційних методів розв’язання систем лінійних рівнянь і т.п. Тому приведені алгоритми тут можна розглядати як фрагменти в алгоритмах цих методів. Розглянемо три алгоритми множення матриці на матрицю. Розмаїтість варіантів алгоритмів виникає із-за розмаїтості обчислювальних систем і розмаїтості розмірів задач. Розглядаються і різні варіанти завантаження даних у систему: завантаження даних через один комп'ютер; і завантаження даних безпосередньо кожним комп'ютером з дискової пам'яті. Якщо завантаження даних здійснюється через один комп'ютер, то дані зчитуються цим комп'ютером з дискової пам'яті, розрізаються на частини, які розсилаються іншим комп'ютерам. Але дані можуть бути підготовлені і заздалегідь, тобто заздалегідь розрізані вроздріб і кожна частина записана на диск у виді окремого файлу зі своїм ім'ям; потім кожен комп'ютер безпосередньо зчитує з диска, призначений для нього файл.
1.1 Алгоритм перемноження матриці на матрицю на кільцевій структурі
Задано дві вихідні матриці A і B. Обчислюється добуток C = А х B, де А - матриця n1 х n2, B - матриця n2 х n3. Матриця результатів C має розмір n1 х n3. Вихідні матриці попередньо розрізані на смуги, ці смуги записані в пам'ять. Матриця результатів повертається в нульовий процес. Реалізація алгоритму виконується на кільці з p1 процесорів. Матриці розрізані як наведено на рис. 1.2: матриця А розрізана на p1 горизонтальних смуг, матриця B розрізана на p1 вертикальних смуг, і матриця результату C розрізана на p1 смуги. Передбачається, що в пам'ять кожного процесора завантажується і може зберігатися тільки одна смуга матриці А і одна смуга матриці B.
Рис.1.1 Методи розрізування даних для виконання паралельного алгоритму. добутку двох матриць при обчисленні на кільці процесорів. Виділені смуги розміщення в пам’яті одного процесора.
Дані можуть бути підготовлені і заздалегідь, тобто заздалегідь розрізані вроздріб і кожна частина записана на диск у виді окремого файлу зі своїм ім'ям; потім кожен комп'ютер безпосередньо зчитує з диску, призначений для нього файл. Вихідні матриці попередньо розрізані на смуги, смуги записані на дискову пам'ять окремими файлами зі своїми іменами і доступні всім комп'ютерам. Матриця результатів повертається в нульовий процес. Нижче подані схеми виконання перемноження матриць на кільцевій структурі (для обох випадків: коли пересилаються стовбці матриці А або, коли пересилаються рядки матриці В)
Рис. 1.2а. Схема множення матриць на кільцевій структурі (пересилання стовбців матриці А)
Рис. 1.2б. Схема множення матриць на кільцевій структурі (пересилання рядків матриці В)
Оскільки за умовою в процесорах знаходиться по одній смузі матриць, то смуги матриці 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 Інтерфейс передачі повідомлень
При розробці паралельних програм виникають специфічні для даної моделі обчислень проблеми сугубо технічного характеру: забезпечення комунікацій між підзадачами, забезпечення надійності й ефективності цих комунікацій, дозвіл проблем зв'язаних із загальним доступом до поділюваних ресурсів та інше. Для рішення цих проблем можна реалізувати власні методи, а можна використовувати вже готові стандарти/специфікації/бібліотеки. MPI – «Інтерфейс передачі повідомлень» - це специфікація, що була розроблена в 1993-1994 роках групою MPI Forum (http://www.mpi-forum.org),і забезпечує реалізацію моделі обміну повідомленнями між процесами. Остання версія даної специфікації MPI-2. У моделі програмування MPI програма породжує кілька процесів, взаємодіючих між собою за допомогою звертання до підпрограм прийому і передачі повідомлень.
Звичайно, при ініціалізації MPI-програми створюється фіксований набір процесів, причому (що, утім, необов'язково) кожний з них виконується на своєму процесорі. У цих процесах можуть виконуватися різні програми, тому MPI-модель іноді називають MPMD-моделлю (Multiple Program, Multiple Data), на відміну від SPMD (Single Program…)моделі, де на кожному процесорі виконуються тільки однакові задачі. MPI підтримує двохточкові і глобальні, синхронні й асинхронні, блокуючі типи комунікацій, що неблокують. Спеціальний механізм – комунікатор – ховає від програміста внутрішні комунікаційні структури. Структура комунікацій може змінюватися протягом часу життя процесу, але кількість задач повинна залишатися постійним (MPI-2 уже підтримує динамічна зміна числа задач).
Специфікація MPI забезпечує переносимість програм на рівні вихідних кодів і велику функціональність. Підтримується робота на гетерогенних кластерах і симетричних мультипроцесорних системах. Не підтримується запуск процесів під час виконання MPI-програми. У специфікації відсутні опис паралельного введення-висновку і налагодження програм – ці можливості можуть бути включені до складу конкретної реалізації MPI у виді додаткових пакетів і утиліт. Сумісність різних реалізацій не гарантується.
Важливою властивістю паралельної програми є детермінізм – програма повинна завжди давати той самий результат для того самого набору вхідних даних. Модель передачі повідомлень, загалом даною властивістю не володіє, оскільки не визначений порядок одержання повідомлень від двох процесів третім. Якщо ж один процес послідовно посилає кілька повідомлень іншому процесу, MPI гарантує, що одержувач одержить їхній саме в тім порядку, у якому вони були відправлені. Відповідальність за забезпечення детермінованого виконання програми лягає на програміста.
2. Аналіз (розробка) граф-схеми виконання заданої функції
Кожен процесор по черзі звертається до спільної пам’яті і завантажує свою частину матриць А і В. Після того, як дані завантаженні відбувається процес обчислення. Обчислення складається з 8-ми циклів множення і додавання і 7 циклів обміну під матрицями В. Як тільки на кожному процесорі сформуються результуючі підматриці розпочинається процес вивантаження підматриці в пам'ять. Кожен процесор по черзі звертається до спільної пам’яті і вивантажує свою результуючу підматрицю.
На рис. 2.1 наведена граф-схема зв’язків між процесорами заданої структури. Дана граф-схема дозволяє визначити комунікації між процесорами. При розробці алгоритму множення матриць комунікації відіграють важливу роль. Від зв’язків між процесорами залежить алгоритм розсилання даних, збору і обміну підматрицею Ві при перемноженні матриць.
Рис.2.1 Граф з’єднань у структурі процесорів.
В даній структурі зв’язків від процесорами можна виділити кільце, тому обмін підматрицею Ві при перемноженні матриць буде виконуватись по вибраному кільцю, з процесорів (2,4,3,1,0,5,6,7), яке можна виділити з графу (Рис. 2.2.).
Рис.2.2 Обмін по кільцевій структурі.
Оскільки пам’ять спільна, то завантаження вхідних та вивантаження вихідних даних буде виконуватись послідовно. Тому в такому випадку граф обміну даних між процесорами та пам’яттю набуде наступного вигляду Рис. 2.3.
Рис. 2.3 Граф обміну даних між процесорами та пам’яттю.
Для розподілення матриць між процесорами обираємо наступний тип розбиття: матриця А – стрічково-горизонтальне розбиття, матриця В - стрічково-вертикальне розбиття (рис. 2.4).
Рис. 2.4 Результат розбиття матриць
На рис. 2.5 наведено граф-схему виконання алгоритму покрокового перемноження двох матриць.
На граф-схемі представлено N процесорних елементів (в нашому випадку – 8). Дані завантажуються кожним процесором по черзі із спільної пам’яті . Після завершення завантаження даних розпочинається сам процес обчислення, підчас якого обмін між процесорами відбувається по структурі зв’язків за маршрутом, вказаним на рис. 2.2. Процес множення – пересилання повторюється 8 разів. Після виконання останнього перемноження, кожен процесор вивантажує часткові результати в пам'ять по черзі, так само як при завантаженні.
Рис. 2.5 Граф-схема виконання алгоритму покрокового перемноження двох матриць.
3.Розробка функціональної схеми
Виконання всього паралельного алгоритму можна розділити на три блоки: завантаження даних, обчислення і вивантаження.
Завантаження даних, як вже описувалося в попередньому розділі, відбувається послідовно кожним процесором зі спільної пам’яті.
Процес обчислення відбувається наступним чином: процесори перемножують елементи матриць, які були у них попередньо завантаженні і отримують частину результату. Після обчислень відбувається пересилання підматриць В по кільцю рис 2.2. Після виконання таких пересилань процесори перемножають свої підматриці А на підматриці В які їм переслали і отримують іще одну частину результату. Такі цикли множення-пересилання повторюються 8 разів. В результаті кожен процесор перемножить свою підматрицю А на кожну підматрицю В і отримає частковий результат.
Вивантаження даних відбувається аналогічно до завантаження, послідовно вивантажуючи часткові результати в спільну пам'ять.
Цей процес зображено на функціональній схемі паралельного множення двох матриць із завантаженням даних з спільної пам’яті рис. 3.1.
Як видно із схеми планування обчислень, операції множення і пересилання різних процесорів на етапі обчислення виконуються паралельно на кожному процесорі. Тому час виконання кожного ярусу множення буде рівним найдовшому часу виконання множення і пересилань на ярусі. Також, як видно із схеми, значний час затрачається на завантаження і вивантаження даних, тому що використана спільна пам'ять, з якою в певний момент часу може працювати тільки один процесор.
Рис. 3.1. Функціональна схема паралельного множення двох матриць із завантаження даних з спільної пам’яті.
4.Розрахунковий розділ
Для порівняння продуктивності виконання множення при використанні паралельного та послідовного алгоритму, проведемо ряд обчислень.
Дані завантажуються з спільної пам’яті.
Розміри матриць: n1=160, n2=64, n3=307.
Розміри підматриць:
A0-A7: [20, 64];
B0-B4: [64, 38]; B5-B7: [64, 39]
Розміри для розрахунків: n1r = 20; n3r = 38(39).
Виразимо часові параметри через найменший :
tU=10tS=2tP=7tZ=8tW
– час виконання однієї операції множення;
– час виконання однієї операції пересилання даних між процесорами;
– час виконання операції з авантаження одних даних;
– час виконання операції вивантаження одних даних;
– час виконання однієї операції сумування.
Оскільки в нас є спільна пам'ять, то звернення кожного процесору до пам'яті і завантаження даних буде виконуватися послідовно, тобто загальний час :
Перемноження матриць відбувається наступним чином: кожен процесор множить свій рядок на рядок, який приходить до нього (включаючи отримані дані при початковому пересиланні). Виконавши операцію множення, процесор пересилає отриманий раніше рядок наступному процесору, а на вхід отримує новий, який перемножує на «свій» рядок. Таким чином маємо 7 операцій пересилання (коли на вхід процесора приходять дані, які були на початковому розповсюдженню значень, пересилка не виконується) і 8 операцій множення.
Тому загальним часом виконання операції на кожному такті вважаємо найбільший час:
Тоді в загальному час множення, пересилання та сумування даних буде:
Оскільки в нас спільна пам'ять, то звернення кожного процесору до пам'яті і вивантаження даних буде виконуватися послідовно, тобто загальний час :
Обчислюємо загальний час виконання множення матриць на паралельному алгоритмі:
Обчислюємо час виконання послідовного алгоритму множення матриць:
Загальний час додавання при обчисленні:
Для характеристики алгоритму визначимо коефіцієнт К, який рівний відношенню часу виконання загального алгоритму до часу виконання паралельних операцій.
Ефективність визначається як відношення часу виконання алгоритму на однопроцесорній системі, до часу потрібного для виконання на багатопроцесорної системі, помноженого на кількість процесорів в ній.
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 - масив структур даних з інформацією про результат виконання операції прийому даних.
Дана функція викликається процесом-передавачем при неблокуючому передаванні даних, якщо необхідно дочекатися завершення отримання даних кількома процесами-приймачами.
Код генератора вхідних матриць присутній на початку програми до МРІ частини коду і може бути використаний для генерації нових матриць та відповідних їм файлів.
Рис. 5.2 Результати роботи програми.
Висновок
Під час виконання курсового проекту я оволодів технологією написання програм для багатопроцесорних систем. Розробив восьми процесорну систему зі спільною пам’яттю множення двох матриць. Також було проведено деякі обчислення, які дають уявлення про характеристики даного паралельного алгоритму, та порівняно його з послідовним. В результаті проведеної роботи можна зробити такі висновки: для восьми процесорної системи та матриць з розмірами 160х64 64х307 умовний час виконання програми в інтервалах виконання операції сумування виявився рівним , а для послідовної структури
Список літератури
Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. – СПб: БХВ-Петербург, 2002.
Ортега Дж. Введение в параллельные и векторные методы решения линейных систем. М.:Мир, 1991.
Программирование на параллельных вычислительных системах: Пер с англ./Под ред. Р.Бэбба.М.:Мир, 1991.
Бройнль Т. Паралельне програмування: Початковий курс: Навчальний посібник. – К.:Вища школа.,1997.
Воеводин В.В. Математические основы параллельных вычислений.- М.: Изд-во МГУ, 1991.
Векторизация программ: теория, методы, реализация: Пер. с англ. и нем. /Под ред. Г.Д.Чинина. - М:. Мир, 1991.
Корнеев В.В. Параллельные вычислительные системы. М.: Нолидж, 1999
С. Немнюгин, О.Стесик Параллельное программирование для многопроцессорных вычислительных систем. – СПб: БХВ-Петербург, 2002.
Питерсон Дж. Теория сетей Петри і моделирования систем: Пер. с англ. -М.: Мир, 1984. -264 с., ил.
10. http://www.parallel.ru – Інформаційно-аналітичний центр з паралельних обчислень.
11. http://www.csa.ru – Інститут високопродуктивних обчислень і баз даних.
12. http://www.hpc.nw.ru – Високопродуктивні обчислення.
13. Організація паралельних обчислень : Навчальний посібник з дисципліни “Паралельні та розподілені обчислення” для студентів базового напрямку 6.0915 "Комп'ютерна інженерія" / Укладачі: Є. Ваврук, О. Лашко – Львів: Національний університет “Львівська політехніка”, 2007, 70 с.
Додаток
matrix.h
#include <cstdlib>
#include <cstdio>
#include <math.h>
#include "mpi.h"
#include <random>
#include <Windows.h>
#include <conio.h>
#include <iostream>
using namespace std;
#define PAUSE {printf("Press \"Enter\" to continue\n"); fflush(stdin); getchar(); fflush(stdin);}
// Declarations
class Matrix;
double Det(const Matrix& a);
Matrix Diag(const int n);
Matrix Diag(const Matrix& v);
Matrix Inv(const Matrix& a);
Matrix Ones(const int rows, const int cols);
int Size(const Matrix& a, const int i);
Matrix Zeros(const int rows, const int cols);
/*
* a simple exception class
* you can create an exeption by entering
* throw Exception("...Error description...");
* and get the error message from the data msg for displaying:
* err.msg
*/
class Exception
{
public:
const char* msg;
Exception(const char* arg)
: msg(arg)
{
}
};
class Matrix
{
public:
// constructor
Matrix()
{
//printf("Executing constructor Matrix() ...\n");
// create a Matrix object without content
p = NULL;
rows = 0;
cols = 0;
}
// constructor
Matrix(const int row_count, const int column_count)
{
// create a Matrix object with given number of rows and columns
p = NULL;
if (row_count > 0 && column_count > 0)
{
rows = row_count;
cols = column_count;
p = new double*[rows];
for (int r = 0; r < rows; r++)
{
p[r] = new double[cols];
// initially fill in zeros for all values in the matrix;
for (int c = 0; c < cols; c++)
{
p[r][c] = 0;
}
}
}
}
// assignment operator
Matrix(const Matrix& a)
{
rows = a.rows;
cols = a.cols;
p = new double*[a.rows];
for (int r = 0; r < a.rows; r++)
{
p[r] = new double[a.cols];
// copy the values from the matrix a
for (int c = 0; c < a.cols; c++)
{
p[r][c] = a.p[r][c];
}
}
}
// index operator. You can use this class like myMatrix(col, row)
// the indexes are one-based, not zero based.
double& operator()(const int r, const int c)
{
if (p != NULL && r > 0 && r <= rows && c > 0 && c <= cols)
{
return p[r-1][c-1];
}
else
{
throw Exception("Subscript out of range");
}
}
// index operator. You can use this class like myMatrix.get(col, row)
// the indexes are one-based, not zero based.
// use this function get if you want to read from a const Matrix
double get(const int r, const int c) const
{
if (p != NULL && r > 0 && r <= rows && c > 0 && c <= cols)
{
return p[r-1][c-1];
}
else
{
throw Exception("Subscript out of range");
}
}
// assignment operator
Matrix& operator= (const Matrix& a)
{
rows = a.rows;
cols = a.cols;
p = new double*[a.rows];
for (int r = 0; r < a.rows; r++)
{
p[r] = new double[a.cols];
// copy the values from the matrix a
for (int c = 0; c < a.cols; c++)
{
p[r][c] = a.p[r][c];
}
}
return *this;
}
// add a double value (elements wise)
Matrix& Add(const double v)
{
for (int r = 0; r < rows; r++)
{
for (int c = 0; c < cols; c++)
{
p[r][c] += v;
}
}
return *this;
}
// subtract a double value (elements wise)
Matrix& Subtract(const double v)
{
return Add(-v);
}
// multiply a double value (elements wise)
Matrix& Multiply(const double v)
{
for (int r = 0; r < rows; r++)
{
for (int c = 0; c < cols; c++)
{
p[r][c] *= v;
}
}
return *this;
}
// divide a double value (elements wise)
Matrix& Divide(const double v)
{
return Multiply(1/v);
}
// addition of Matrix with Matrix
friend Matrix operator+(const Matrix& a, const Matrix& b)
{
//
01.06.2014 14:06-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора