Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Паралельне виконання операцій множення матриць
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Інститут комп’ютерних технологій, автоматики та метрології
Факультет:
КН
Кафедра:
Електронні обчислювальні машини
Інформація про роботу
Рік:
2014
Тип роботи:
Курсова робота
Предмет:
Паралельні та розподілені обчислення
Група:
КI
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти і науки України
Національний університет „Львівська політехніка”
Кафедра ЕОМ
Курсова робота
з дисципліни «Паралельні та розподілені обчислення»
на тему:
«Паралельне виконання операцій множення матриць»
Львів – 2014
Завдання
Задаються дві матриці А (розмірністю n1*n2) та В (розмірністю n2*n3) :
n1=2Б , n2=4П, n3=2І – КІ-44
де nП, nБ та nІ номер букви в прізвищі, імені та по-батькові відповідно.
Бенько Тарас Іванович
n1=2Б – В
n2=4П – Ь
n3=2І – А
декодування вибраних літер для n1,n2,n3 відбувається на основі таблиці 2.1.
Таблиця 2.1 Декодування літер розмірностей для n1,n2,n3
n1
n2
n3
А-120
Б-110
В-100
Г-90
Ґ-80
Д-70
Е-60
А-64
Б-72
В-56
Г-88
Ґ-96
Д-104
Е-112
А-117
Б-95
В-73
Г-195
Ґ-301
Д-247
Е-149
Є-140
Ж-130
З-150
И-160
І-170
Ї-180
Й-190
Є-128
Ж-146
З-154
И-168
І-176
Ї-184
Й-192
Є-93
Ж-111
З-127
И-349
І-181
Ї-163
Й-217
К-200
Л-210
М-220
Н-230
О-240
П-250
Р-260
К-208
Л-216
М-224
Н-232
О-248
П-256
Р-264
К-307
Л-325
М-251
Н-67
О-333
П-241
Р-159
С-270
Т-280
У-50
Ф-40
Х-290
Ц-300
Ч-310
С-272
Т-288
У-296
Ф-304
Х-312
Ц-328
Ч-336
С-234
Т-91
У-181
Ф-143
Х-37
Ц-45
Ч-129
Ш-320
Щ-330
Ь-340
Ю-350
Я-360
Ш-344
Щ-352
Ь-48
Ю-368
Я-376
Ш-225
Щ-71
Ь-167
Ю-349
Я-118
Згідно з таблицею 2.1 отримаємо такі значення n1,n2,n3:
n1=2Б – В = 100
n2=4П – Ь = 48
n3=2І – А = 117
Отже маємо матрицю А(100*48) та матрицю В(48*117)
Розробити та описати алгоритм множення матриць А*В на структурі яка задається виразом:
3b-6b-2b-5b-10b-13b-14b-11b – КІ-44, де «nb»- номер букви П.І.Б студента.
Романів Петро Іванович 3b-6b-2b-5b-10b-13b-14b-11b:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
Б
Е
Н
Ь
К
О
Т
А
Р
А
С
І
В
А
Н
О
В
И
Ч
3
1
4
2
5
8
6
→
→
→
→
7
*якщо кількість букв недостатньо то вираз застосовується до послідовності ПІБПІБПІБ.
Отримаємо – НОЕКАВИС**
**якщо присутнє дублювання букв то береться буква яка іде наступною в ПІБ після необхідної.
На основі декодування отриманого набору букв на основі таблиці 2.2 формуємо варіант-стовпець
Таблиця 2.2 Кодування букв
А -27 Б -35 В -203 Г -74 Ґ -95 Д - 13 Е - 171
Є- 34 Ж-12 З -67 И -91 І -223 Ї -161 Й -146
К -47 Л -212 М -43 Н -134 О- 250 П -219 Р – 93
С -82 Т - 198 У -164 Ф -233 Х- 127 Ц -201
Ч -49 Ш -157 Щ -19 Ь -28 Ю – 63 Я- 155
Для НОЕКАВИС отримаємо 134,250,171,47,27,203,91,82. Даний набір чисел записуємо у стовпець і переводимо і двійкове 8-ми розрядне число:
134 - 10000110
250 - 11111010
171 - 10101011
47 - 00101111
27 - 00011011
203 - 11001011
91 - 01011011
82 - 01010010
В отриманій двійковій матриці одиниці що розташовані на головній діагоналі замінюємо на 0.
10000110 00000110
11111010 10111010
10101011 10001011
00101111 00101111
00011011 => 00010011
11001011 11001011
01011011 01011001
01010010 01010010
Отримана матриця розміру 8*8 є матрицею зв’язків орієнтованого графу, вершини якого це процесори а напрямлені дуги це напрямлені лінії зв’язку між процесорами. На основі цієї матриці будується відповідний їй граф що характеризує конкретну 8-ми процесорну систему (структуру) із направленими зв’язками між вершинами.
Для цієї структури визначити час виконання алгоритму, відсоток послідовної частини алгоритму та ефективність алгоритму для значень, співвідношення часових параметрів та тип початкового завантаження визначаються за правилами:
3.1. Тип початкового завантаження даних type:
, де Zi цифри номера залікової книжки, n=1..k, де k – кількість цифр номера залікової книжки.
Номер залікової книжки: № 1209940
type = (1+2+0+9+9+4+0) mod3 + 1 = 25mod3 +1 = 2 (через один процесор).
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 = 7-кількість цифр в номері залікової книжки.
Номер залікової книжки: № 1209940
tU=10tS=10tP=5tZ=1tW
Розміри матриць
Кількість
процесорів (Р)
Тип початкового завантаження даних
Співвідношення часових параметрів
N1
N2
N3
100
48
117
8
2
tU, = 10tS = 10tP =5tZ = 1tW.
Анотація
В даній курсовій роботі було розроблено програму для множення двох матриць розміром 100*48 та 48*117 на восьми процесорах, з заданою структурою зв’язків. Завантаження даних в процесори відбувається через один із них. Збір даних відбувається у тому ж процесорі з якого відбувалося завантаження. Також було визначено основні характеристики розробленого паралельного алгоритму.
Робота поділяється на такі етапи:
проектування граф-схеми виконання алгоритму (побудова зв’язків між процесорами, кільця для обміну даними, граф-схема виконання алгоритму множення двох матриць);
розробка функціональної схеми;
розрахункова частина (розрахунок ефективності, часу виконання алгоритму, відсотка послідовної частини алгоритму тощо);
програмна реалізація, яка включає в себе алгоритм роботи програми, його граф-схему та код програми.
Програма написана на мові С# з використанням технології MPI .NET, оскільки вона найкраще підходить для вирішення даної задачі, і має графічний інтерфейс.
Annotation
In this course paper was created the program, which multiples 2 matrix with 100*48 and 48*117 size on eight processors with given structure of connections. Data dividing is from one of the processors. Data replication is in the same processor, from which the downloading was. Main characteristics of elaborated parallel algorithm were also distinguished.
The work is divided into the following stages:
designing graph-scheme of algorithm execution (construction bonds between processors, rings for data exchange, graph-scheme of execution the algorithm of multiplying two matrices);
development of functional scheme;
calculation part (calculation of efficiency, time of execution the algorithm, the percentage of sequential algorithm, etc);
software implementation, which includes the algorithm of the program, it’s graph-schema and application code.
The program is written in C# using the technology of MPI .NET, because it’s best suited to solve this problem, and has graphic interface.
ЗМІСТ
Вступ 8
1. Теоретичний розділ 9
2. Розробка граф-схеми виконання заданої функції 15
3. Розрахунковий розділ 18
4. Розробка функціональної схеми 22
5. Розробка програми 26
Висновок 31
Список літератури 32
Додатки 33
Лістинг програми 33
Вступ
Паралельні обчислювальні системи - комп'ютерні системи, що реалізовують тим або іншим способом паралельну обробку даних на багатьох обчислювальних вузлах для підвищення загальної швидкості розрахунку. Ідея розпаралелення обчислень базується на тому, що більшість завдань можуть бути розділені на набір менших завдань, які можуть бути вирішені одночасно. Зазвичай паралельні обчислення вимагають координації дій.
Паралельні алгоритми досить важливі з огляду на постійне вдосконалення багатопроцесорних систем і збільшення числа ядер у сучасних процесорах. Зазвичай простіше сконструювати комп'ютер з одним швидким процесором, ніж з багатьма повільними з тією ж продуктивністю. Однак збільшення продуктивності за рахунок вдосконалення одного процесора має фізичні обмеження, такі як досягнення максимальної щільності елементів та тепловиділення. Зазначені обмеження можна подолати лише шляхом переходу до багатопроцесорної архітектури, що виявляється ефективним навіть у малих обчислювальних системах. Складність послідовних алгоритмів виявляється в обсязі використаної пам'яті та часу (число тактів процесора), необхідних для виконання алгоритму.
Розподілені обчислення - спосіб розв'язання трудомістких обчислювальних завдань з використанням двох і більше комп'ютерів, об'єднаних в мережу. Розподілені обчислення є окремим випадком паралельних обчислень, тобто одночасного розв'язання різних частин одного обчислювального завдання декількома процесорами одного або кількох комп'ютерів. Тому необхідно, щоб завдання, що розв'язується було сегментоване — розділене на підзадачі, що можуть обчислюватися паралельно. При цьому для розподілених обчислень доводиться також враховувати можливу відмінність в обчислювальних ресурсах, які будуть доступні для розрахунку різних підзадач. Проте, не кожне завдання можна «розпаралелити» і прискорити його розв'язання за допомогою розподілених обчислень.
ТЕОРЕТИЧНИЙ РОЗДІЛ
Основна ідея розпаралелювання обчислень – мінімізація часу виконання задачі за рахунок розподілу навантаження між декількома обчислювальними пристроями. Цими «обчислювальними пристроями» можуть бути як процесори одного суперкомп'ютера, так і кілька комп'ютерів, обєднаних за допомогою комунікаційної мережі в єдину обчислювальну структуру – кластер.
Паралельна модель програмування сильно відрізняється від звичайної – послідовної. Існують дві моделі паралельного програмування: модель паралелізму даних і модель паралелізму задач. Модель паралелізму даних має на увазі незалежну обробку даних кожним процесом (наприклад, векторні операції з масивами). Модель паралелізаму задач передбачає розбиття основної задачі на самостійні підзадачі, кожна з яких виконується окремо й обмінюється даними з іншими. Це більш трудомісткий, у порівнянні з паралелізмом даних, підхід. Перевагою є велика гнучкість і велика воля, надана програмісту в розробці програми, що ефективно використовує ресурси паралельної системи. При цьому можуть застосовуватися спеціалізовані бібліотеки, що беруть на себе всі «організаційні» задачі. Приклади таких бібліотек: MPI (Message Passing Interface) і PVM (Parallel Virtual Machine).
Звичайно, при ініціалізації MPI-програми створюється фіксований набір процесів, причому (що, утім, необов'язково) кожний з них виконується на своєму процесорі. У цих процесах можуть виконуватися різні програми, тому MPI-модель іноді називають MPMD-моделлю (Multiple Program, Multiple Data), на відміну від SPMD (Single Program…)моделі, де на кожному процесорі виконуються тільки однакові задачі. MPI підтримує двохточкові і глобальні, синхронні й асинхронні типи комунікацій. Спеціальний механізм – комунікатор – ховає від програміста внутрішні комунікаційні структури.
Організація процесу обчислення
Множення матриці A розміру n1xn2 і матриці B розміру n2xn3 призводить до отримання матриці С розміру n1xn3, кожен елемент якої визначається відповідно до виразу:
/ (1)
Як випливає з (1), кожен елемент результуючої матриці С є скалярний добуток відповідних рядка матриці A та стовпця матриці B: Цей алгоритм передбачає виконання mxnxl операцій множення і стільки ж операцій додавання елементів вихідних матриць. При множенні квадратних матриць розміру nxn кількість виконаних операцій має порядок O (n3). Відомі послідовні алгоритми множення матриць, що мають меншу обчислювальної складністю (наприклад, алгоритм Страса (Strassen's algorithm)), але ці алгоритми вимагають великих зусиль для їх освоєння. Далі будемо припускати, що всі матриці є квадратними і мають розмір nxn.
Послідовний алгоритм Послідовний алгоритм множення матриць видається трьома вкладеними циклами: Алгоритм 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) де / є час виконання однієї елементарної скалярної операції.
Алгоритм перемноження матриці на матрицю на кільцевій структурі
Задано дві вихідні матриці A і B. Обчислюється добуток , де А - матриця , B - матриця . Матриця результатів C має розмір . Вихідні матриці попередньо розрізані на смуги, смуги записані в пам'ять. Матриця результатів повертається в нульовий процес.
Реалізація алгоритму виконується на кільці з процесорів. Матриці розрізані як наведено на рис. 1.2: матриця А розрізана на горизонтальних смуг, матриця B розрізана на вертикальних смуг, і матриця результату C розрізана на смуги. Передбачається, що в пам'ять кожного процесора завантажується і може зберігатися тільки одна смуга матриці А і одна смуга матриці B.
/
Рис. 1.2. Схема розбиття матриць на смуги.
Оскільки за умовою в процесорах знаходиться по одній смузі матриць, то смуги матриці B (або смуги матриці A) необхідно "прокрутити" по кільцю процесорів повз смуги матриці A (матриці B). Кожний зсув смуг уздовж кільця і відповідна операція множення наведена на рис. 1.3 у виді окремого кроку. На кожному з таких кроків обчислюється тільки частина смуги. Процес i обчислює на j-м кроці добуток i-й горизонтальної смуги матриці A j-ї вертикальної смуги матриці B, добуток отримується у підматриці (i,j) матриці C.
Обчислення відбувається в такій послідовності:
Головний процесор (processor 0) отримує дані (матриці А та В) з пам’яті, після чого відбувається обчислення щодо розподілу рядків матриці А та стовпців матриці В між процесорами.
На наступному етапі головний процесор починає послідовно (по кільцю) надсилати решті процесорів необхідні їм для обчислення дані. По закінченню етапу завантаження даних кожен з процесорів буде містити смугу матриці А і смугу матриці В.
Обчислювальний крок 1. Кожен процес обчислює одну підматрицю добутку. Вертикальні смуги матриці B зсуваються уздовж кільця процесорів.
Обчислювальний крок 2. Кожен процес обчислює одну підматрицю добутку. Вертикальні смуги матриці B зсуваються уздовж кільця процесорів і т.д.
Обчислювальний крок . Кожен процес обчислює одну підматрицю добутку. Вертикальні смуги матриці B зсуваються уздовж кільця процесорів.
Обчислювальний крок . Кожен процес обчислює одну підматрицю добутку. Вертикальні смуги матриці B зсуваються уздовж кільця процесорів.
Після виконання останнього обчислювального кроку відбувається вивантаження часткових результатів (підматриць ) до нульового процесора.
Якщо "прокручувати" вертикальні смуги матриці B, то матриця С буде розподілена горизонтальними смугами, а якщо "прокручувати" горизонтальні смуги матриці A, то матриця С буде розподілена вертикальними смугами.
Час на завантаження/вивантаження матриць через один процесор залежить від алгоритму завантаження вивантаження, в загальному випадку якого можна обчислити за формулою:
Z = (A+B)+(p-1)(A+B)+(p-2)(A+B)…
Алгоритм характерний тим, що після кожного кроку обчислень здійснюється обмін даними. Нехай , , і час операцій, відповідно, множення, додавання і пересилання одного числа між сусідніми процесорами. Тоді загальний час виконання операцій множень дорівнює:
,
загальний час виконання операцій додавань:
,
загальний час виконання операцій пересилань даних по всіх процесорах:
.
Загальний час обчислень визначимо як:
.
Якщо час передачі даних великий в порівнянні з часом обчислень, або канали передачі повільні, то ефективність алгоритму буде не висока. Тут не враховується час початкового завантаження і вивантаження даних у пам'ять системи. У смугах матриць може бути різна кількість рядків, а різниця в кількості рядків між смугами - 1. При великих матрицях цим можна знехтувати.
/ Рис. 1.3. Загальна схема передачі даних для паралельного алгоритму матричного множення при стрічковій схемі розділення даних.
РОЗРОБКА ГРАФ-СХЕМИ ВИКОНАННЯ ЗАДАНОЇ ФУНКЦІЇ
Алгоритм перемноження матриць на багатопроцесорній структурі складається з декількох етапів:
визначення зв’язків між процесорами, на яких будуть перемножуватись матриці;
розбиття матриць на частини і розсилання кожному процесору його підматриці;
обчислення результату;
збереження результату.
На рис. 2.1. наведена граф-схема зв’язків між процесорами заданої структури. Дана граф-схема дозволяє визначити комунікації між процесорами. При розробці алгоритму множення матриць комунікації відіграють важливу роль. Від зв’язків між процесорами залежить алгоритм розсилання даних, збору і обміну підматрицею Ві при перемноженні матриць.
/
Рис. 2.1 Граф-схема зв’язків між процесорами.
Завантаження і вивантаження даних відбувається через 1 процесор. Вибраний процесор №7 – через нього буде здійснюватися доступ до пам’яті.
Всі інші процесори можуть одночасно приймати від одного процесора дані і передавати іншому. Ці процесори мають власну пам'ять достатню для розміщення підматриць Аi і Вi, які вони будуть перемножувати і місце для результату множення. Початкове завантаження даних відбувається за схемою рис 2.2:
Рис.2.2. Завантаження даних
За даною схемою завантаження матриці в процесори відбувається за 4 кроки:
Крок 1. В процесор 7 завантажуються з пам’яті підматриці A3 B3,А1В1
Крок 2. Процесор 7 передає підматриці A3B3,А1В1 процесорам 8,4 і завантажує підматриці A6B6, А2В2.
Крок 3. Процесори 8,4 передають процесорам 2,6 підматрицю A3 B3.
Процесор 7 передає процесорам 8,4 підматрицю A6 B6,А2В2 .
Процесор 7 завантажує з пам’яті підматриці A 8B8, А5В5,А4В4,А7В7 .
Крок 4. Процесори 2,6 передають процесорам 3,1 підматрицю A3 B3, А1В1.
Процесори 8,4 передають процесорам 2,6 підматрицю A2 B2, A6 B6.
Процесор 7 передає процесорам 8,5,4 підматриці A8 B8. А5В5,А4В4.
Всі дані завантажені.
На кожному з ярусів для обчислення часу завантаження вибирається операція, яка буде виконуватись найдовше. Збір даних і збереження в пам'ять відбувається за схемою рис. 2.3:
Рис.2.3. Вивантаження даних
Згідно з рис. 2.3 збереження даних в пам'ять відбувається за 1 крок:
Крок 1: Процесори 2,8,4,6,5,3,1 передають свій результат процесору 7.
Крок 2: Процесор 7 зберігає свій результат в пам'ять.
В даній структурі зв’язків між процесорами можна виділити кільце, тому обмін підматрицею Ві при перемноженні матриць буде виконуватись по вибраному кільцю, яке зображене на рис.2.4:
Рис.2.4 Вибраний кільцевий маршрут передачі підматриць B при множенні
РОЗРАХУНКОВИЙ РОЗДІЛ
Наступним кроком є спосіб розбиття даних між процесорами. Від даного кроку залежить рівномірність навантаження кожного процесора і час простою при різному навантажені.
Розбиття матриці А на під матриці для кожного процесора:
100*48
№
Рядків
Стовбців
1
13
48
2
13
48
3
13
48
4
13
48
5
12
48
6
12
48
7
12
48
8
12
48
Розбиття матриці В на під матриці для кожного процесора:
48*117
№
Рядків
Стовбців
1
48
15
2
48
15
3
48
15
4
48
15
5
48
15
6
48
14
7
48
14
8
48
14
Рис.3.1. Розбиття матриці між процесорами.
Згідно завдання:
Tu=10Ts=10Tp=5Tz=1Tw
Виразимо інші операції через час Tp:
TU=10 Tp; TS= Tp; Tw=10 Tp; Tz=2 Tp
Загальний час виконання операцій завантаження рівний найдовшій операції на кожному кроці.
Крок 1:
Процесор завантажує частину даних.
TZ1=((n1*n2)+(n2*n3))tZ = ((13*48)+(48*15))tZ = (624+720)tZ = 1344tZ = 1344*2tP = 2688tP
Крок 2:
Так як час завантаження є набагато менший, ніж час пересилання, хоч і об’єм завантаження є більший, найдовшою операцією є час пересилання.
TZ2 = ((n1*n2)+(n2*n3))tP = ((13*48)+(48*15))tP = (624+720)tP = 1344tP
Крок 3:
Найбільший час на даному кроці – час пересилання підматриці для процесора.
TZ3 = ((n1*n2)+(n2*n3))tP = ((13*48)+(48*15))tP = 1344tP
Крок 4:
Найбільший час на даному кроці – час пересилання підматриці для процесора.
TZ4 = ((n1*n2)+(n2*n3))tP = ((13*48)+(48*15))tP = 1344tP
TZ = TZ1 + TZ2 + TZ3 + TZ4 = (2688 + 1344 + 1344 + 1344)tP = 6720 tP
Після операції завантаження початкових даних в процесори запускається цикл обробки даних, який має 8 ітерацій, які включають в себе як множення підматриць, так і пересилання даних між процесорами (підматриці Ві).
Для послідовного алгоритму загальна кількість операцій множення та додавання:
U = (n1*n3*n2) = 100 * 117 * 48 = 561600
S = (n1*n3*(n2-1)) = 100 * 117 * 47 = 549900
Загальна кількість операцій множення та додавання на кільцевій структурі рівна:
I ітерація
II ітерація
III ітерація
IV ітерація
V ітерація
VI ітерація
VII ітерація
VIII ітерація
Сумарна кількість операцій множення та додавання при опрацюванні даних на кільцевій структурі:
, 748800 tp
, TSS = 73320 tp
На семи із восьми ітераціях відбувається процес обміну підматрицями Ві між процесорами.
Кількість операцій обміну на кожній ітерації рівна кількості елементів найбільшої з підматриць Ві:
Тоді загальна кількість операцій обміну буде рівна сумі таких операцій на семи ітераціях:
Після виконання восьми ітерацій в пам’яті кожного з процесорів отримуємо результуючу часткову підматрицю Сі. Отже необхідно зібрати всі підмасиви Сі з кожного процесора в загальну пам'ять результуючої матриці С.
Загальний час виконання операцій вивантаження дорівнює сумі найдовших операцій на кожному кроці.
Крок 1:На даному кроці найдовшою буде операція пересилання підматриці Сі.
TW1 = (n1*n3)*tp = (13*15)*tp =195tp
Крок 2:Вивантаження даних з процесора в пам’ять.
TW2 = (n1*n3)*tW = (100*117)*tW =11700tW =117000 tp
Загальний час вивантаження – W = Tw1 + Tw2 = 195tP+117000tp + 1= 117196 tp
Загальний час виконання множення матриць:
T = TZ + TU + TS + TP + TW = 6720 + 748800 + 73320 + 5040 + 117196 = 951076tP
Для характеристики алгоритму визначимо коефіцієнт К, який характеризує відсоток послідовних обчислень. В нашому випадку він буде рівний:
K = (Z+W) / T = (6720 + 117196) / 951076≈ 0,130 = 13%.
Також порахуємо ефективність паралельного алгоритму. Ефективність визначається, як відношення часу виконання алгоритму на одно процесорній системі, до часу потрібного для виконання на багатопроцесорної системі, помноженого на кількість процесорів в ній.
=8/(1+0.144*7)=3.98
E = S(N)/N = 3.98/8 ≈ 0,4975
Tk- тривалість виконання програм з максимальним показником розпаралелення на системі з k процесорами;
- N - кількість процесорів у паралельній системі;
- f – відсоток послідовних операцій програми (не можуть бути виконані паралельно на N процесорах).
РОЗРОБКА ФУНКЦІОНАЛЬНОЇ СХЕМИ
/Рис. 4.1.Частина функціональної схеми, яка відповідає за завантаження даних.
Згідно з схемою рис. 4.1 дані поступово завантажуються і передаються через один процесор, в даному випадку це процесор №7. В схемі зображені блоки завантаження і пересилання даних. Весь процес завантаження розділений на чотири рівні, кожен рівень синхронізується до операції, яка найдовше виконується.
/
/Рис. 4.2.Частина функціональної схеми, яка відповідає за перемноження матриць.
Відповідно до схеми рис. 4.2 відбувається перемноження матриці А на матрицю В на структурі з 8-ми процесорів. Процес перемноження складається з 8-ми рівнів перемноження і з 7-ми рівнів пересилання даних. Дана схема складається з блоків множення і блоків пересилання даних.
/Рис. 4.3.Частина функціональної схеми, яка відповідає за вивантаження результатів.
За схемою рис. 4.3 процес вивантаження складається з двох рівнів. На кожному рівні синхронізація відбувається згідно блоку, який виконується найдовше. В даній схемі присутні блоки двох типів: пересилання результату і вивантаження в пам'ять.
РОЗРОБКА ПРОГРАМИ
Першим кроком розробки програми для виконання заданої функції є розробка блок схеми алгоритму.
/
Рис. 5.1.Блок-схема виконання множення і пересилання підматриць
/
Рис. 5.2.Блок-схема виконання завантаження даних
/
Рис. 5.3.Блок-схема виконання вивантаження результату
Згідно з блок-схемою програма повинна завантажувати дані через один процесор і розсилати їх на всі процесори згідно з вибраним алгоритмом. Після розсилання даних відбувається 8 циклів перемноження матриці. Після того як на кожному процесорі сформується результуючі підматриці всі дані збираються на одному процесорі.
Для реалізації даної програми використовується бібліотека MPI .NET. Програма виконується згідно з розробленого алгоритму. Процес завантаження даних відповідає рис. 5.2.
Для обміну інформацією між процесами використовуються функції бібліотеки MPI .NET Send() та Receive(). Це парні функції, які призначені відповідно для відправки та прийому повідомлень.
void Communicator.Send<T>(T[]values, int dest, int tag)
values – дані повідомлення, що відправляються;
dest – ранг процесу, якому відправляється повідомлення;
tag – значення-тег, що використовується для ідентифікації повідомлення;
void Communicator.Receive<T>(int source, int tag, out T value)
source – ранг процесу, від якого повинен бути виконаний прийом повідомлення;
tag – тег повідомлення, яке повинне бути прийняте для процесу;
value – буфер пам’яті для прийому повідомлення.
Процес множення і пересилання даних між процесами зображений на рис.5.1. Вивантаження даних відбувається згідно схеми наведеної на рис.5.3.
Дана програма написана на мові C# в середовищі MS Visual Studio 2013 і має графічний інтерфейс.
Результат роботи програми:
/
Рис.5.4 Ініціалізація вхідних даних
/
Рис.5.5 Результат роботи програми
Для тестування достовірності результатів паралельної програми, я розробив ще й послідовну програму, де множаться ці матриці.
/
Рис.5.6 Перевірка коректності роботи програми
ВИСНОВОК
В процесі виконання курсової роботи, було виконане множення двох заданих матриць, причому множення відбувалось за певною схемою і алгоритмом. Крім цього було оцінено часові параметри роботи паралельної і послідовної програм, порівняно їх часові характеристики, які показують, що при вказаних даних матрицях А та В, паралельно множення буде виконуватись швидше ніж при послідовному. Хоча для інших задач та інших випадків можливі ситуації коли розпаралелювання результату не дасть.
Згідно розрахунків, отримано наступні результати:
Загальний час виконання всіх операцій - T = 951076tP
Коефіцієнт послідовної частини - K = 13%.
Ефективність E = 0,4975
Також для наглядного зображення працездатності структури була розроблена програма з допомогою бібліотеки MPI .NET. Дана програма реалізує множення двох матриць на розробленій восьми процесорній структурі.
Список літератури
Корнеев В.В. Параллельные вычислительные системы. М.: Нолидж, 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 – Високопродуктивні обчислення.
Додаток А
using System;
using System.Collections.Generic;
using System.Windows.Forms;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Windows;
using MPI;
using System.IO;
using System.Diagnostics;
namespace MPI_Test
{
class Program
{
public static int[,] MatrixA;
public static int[,] MatrixB;
private static int[][,] SubMatrixA;
private static int[][,] SubMatrixB;
public static int N1, N2, N3;
public static int[,] MatrixAB = new int[N1, N3];
public static bool flag = true;
static void Main(string[] args)
{
using (new MPI.Environment(ref args))
{
MatrixIO Print = new MatrixIO();
Intracommunicator comm = Communicator.world;
Application.SetCompatibleTextRenderingDefault(false);
int rank = comm.Rank; // ранк(номер) процеса
int size = comm.Size; // кiльiсть процесiв
int[][][,] fMatrix = new int[size][][,];
again:
#region rank 0
if (rank == 0)
{
comm.Barrier();
int[,] SubA = comm.Receive<int[,]>(5, 0);
Console.WriteLine("Процесор {0} приймає пiдматрицю А1 розмiром [ {1} x {2} ]вiд процесора №6", comm.Rank + 1, SubA.GetLength(0), SubA.GetLength(1));
int[,] SubB = comm.Receive<int[,]>(5, 1);
Console.WriteLine("Процесор {0} приймає пiдматрицю B1 розмiром [ {1} x {2} ]вiд процесора №6", comm.Rank + 1, SubB.GetLength(0), SubB.GetLength(1));
comm.Barrier();
comm.Barrier();
comm.Barrier();
//--
Console.WriteLine("• {0} - Виконує множення", comm.Rank + 1);
int[][,] SubAB = new int[8][,];
SubAB[0] = MatrixMult(SubA, SubB);
Console.WriteLine("* {0} - Виконує пересилання матрицi B до процесора №7", comm.Rank + 1);
comm.Send<int[,]>(SubB, 6, 0);
Console.WriteLine("* {0} - Отримує матрицю B вiд процесора №6", comm.Rank + 1);
SubB = comm.Receive<int[,]>(5, 0);
//Друга ітерація
Console.WriteLine("******* Друга iтерацiя *******");
Console.WriteLine("• {0} - Виконує множення", comm.Rank + 1);
SubAB[5] = MatrixMult(SubA, SubB);
Console.WriteLine("* {0} - Виконує пересилання матрицi B до процесора №7", comm.Rank + 1);
comm.Send<int[,]>(SubB, 6, 0);
Console.WriteLine("* {0} - Отримує матрицю B вiд процесора №6", comm.Rank + 1);
SubB = comm.Receive<int[,]>(5, 0);
//Третя ітерація
Console.WriteLine("******* Третя iтерацiя *******");
Console.WriteLine("• {0} - Виконує множення", comm.Rank + 1);
SubAB[3] = MatrixMult(SubA, SubB);
Console.WriteLine("* {0} - Виконує пересилання матрицi B до процесора №7", comm.Rank + 1);
comm.Send<int[,]>(SubB, 6, 0);
Console.WriteLine("* {0} - Отримує матрицю B вiд процесора №6", comm.Rank + 1);
SubB = comm.Receive<int[,]>(5, 0);
17.03.2015 00:03-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора