Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Паралельне виконання операцій множення матриць
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
КН
Кафедра:
Кафедра ЕОМ
Інформація про роботу
Рік:
2011
Тип роботи:
Курсова робота
Предмет:
Паралельні та розподілені обчислення
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ І НАУКИ, МОЛОДІ ТА СПОРТУ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ „ЛЬВІВСЬКА ПОЛІТЕХНІКА”
Кафедра ЕОМ
Курсова робота
з дисципліни: “ Паралельні та розподілені обчислення”
на тему:
«Паралельне виконання операцій множення матриць»
1.Задаються дві матриці А (розмірністю n1*n2) та В (розмірністю n2*n3) :
n1=5Б , n2=3П, n3=2І – КІ-44
де nП, nБ та nІ номер букви в прізвищі, імені та по-батькові відповідно.
Артим Віталій Ігорович КІ-44:
декодування вибраних літер для 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
Згідно з таблицею отримаємо такі значення n1,n2,n3:
n1=5Б – О = 240 n2=3П – Т = 288 n3=2І – I = 181
Отже маємо матрицю А(240*288) та матрицю В(288*181)
2. Розробити та описати алгоритм множення матриць А*В на структурі, яка задається виразом:
3b-6b-2b-5b-10b-13b-14b-11b – КІ-44, де «nb»- номер букви П.І.Б студента.
Артим Віталій Ігорович КІ-44:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
А
Р
Т
И
М
В
І
Т
А
Л
І
Й
І
Г
О
Р
О
В
И
Ч
3
1
4
2
5
8
6
7
Отримаємо – ТВРМЛІГЙ
Для ТВРМЛІГЙ отримаємо 198,203,93,43,212,223,74,146. Даний набір чисел записуємо у стовпець і переводимо в двійкове 8-ми розрядне число. В отриманій двійковій матриці одиниці що розташовані на головній діагоналі замінюємо на 0:
192 – 11000110
203 - 11001011
093 - 01011101
043 - 00101011
212 - 11010100
223 - 11011111
074 - 01001010
146 – 10010010
=>
01000110
10001011
01011101
00101011
11010100
11011011
01001000
10010010
Отримана матриця розміру 8*8 є матрицею зв’язків орієнтованого графу, вершини якого це процесори, а напрямлені дуги це напрямлені лінії зв’язку між процесорами.
3.Для цієї структури визначити час виконання алгоритму, відсоток послідовної частини алгоритму та ефективність алгоритму для значень, співвідношення часових параметрів та тип початкового завантаження визначаються за правилами:
3.1. Тип початкового завантаження даних type:
, де Zi цифри номера залікової книжки, n=1..k, де k – кількість цифр номера залікової книжки.
КІ-41 … КІ-46: type=1(спільна пам’ять),type=2(через один процесор), type=3(розподілена пам’ять).
0909622
type=(0+9+0+9+6+2+2)=28 mod 3 + 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 - кількість цифр в номері залікової книжки.
tU=10tS=7tP=3tZ=3tW
Розміри матриць
Кількість процесорів (Р)
Тип початкового завантаження даних
Співвідношення часових параметрів
n1
n2
n3
240
288
181
8
через один з процесорів
Tu=10Ts=7Tp=3Tz=3Tw
Анотація
В даній курсовій роботі було розроблено програму для множення двох матриць розміром 240*288 та 288*181 на восьми процесорах, з заданою структурою зв’язків. Завантаження даних в процесори відбувається через один із них. Збір даних відбувається у тому ж процесорі з якого відбувалося завантаження. Також було визначено основні характеристики розробленого паралельного алгоритму.
Програма в даній курсовій роботі написана на мові С++ з використанням бібліотек MPI та має консольний інтерфейс.
Annotation
In this course paper was created the program, which multiples 2 matrix with 240*288 and 288*181 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 program in this course paper is written in C++ language with the usage of MPI libraries and has console interface.
ЗМІСТ
Вступ 6
1. Теоретичний розділ 7
2. Розробка граф-схеми виконання заданої функції 12
3. Розрахунковий розділ 15
4. Розробка функціональної схеми 20
5. Розробка програми 21
Висновок 23
Список літератури 24
Додатки 25
Лістинг програми 25
ВСТУП
Ідея розпаралелювання обчислень базується на тому, що більшість задач може бути розділена на набір менших завдань, які можуть бути вирішені одночасно. Паралельні обчислення використовувалися багато років в основному в найпродуктивніших обчисленнях, але останнім часом до них зріс інтерес внаслідок існування фізичних обмежень на зростання тактової частоти процесорів.
Поява в останні роки великої кількості порівняно дешевих кластерних паралельних обчислювальних систем призвело до швидкого розвитку паралельних обчислювальних технологій, у тому числі і в області високопродуктивних обчислень. Останнім часом ситуація в галузі паралельних обчислювальних технологій почала кардинально змінюватися в зв'язку з тим, що більшість основних виробників мікропроцесорів стали переходити на багатоядерні архітектури. Зміна апаратної бази змушує змінювати і підхід до побудови паралельних алгоритмів. Для реалізації обчислювальних можливостей багатоядерних архітектур потрібна розробка нових паралельних алгоритмів. Ефективність використання обчислювальних ресурсів, яку будуть мати кластери нового покоління, напряму залежатиме від якості власне паралельних програм, так і спеціалізованих бібліотек чисельних алгоритмів, орієнтованих на багатоядерні архітектури.
ТЕОРЕТИЧНИЙ РОЗДІЛ
Основна ідея розпаралелювання обчислень – мінімізація часу виконання задачі за рахунок розподілу навантаження між декількома обчислювальними пристроями. Цими «обчислювальними пристроями» можуть бути як процесори одного суперкомп'ютера, так і кілька комп'ютерів, обєднаних за допомогою комунікаційної мережі в єдину обчислювальну структуру – кластер.
Паралельна модель програмування сильно відрізняється від звичайної – послідовної. Існують дві моделі паралельного програмування: модель паралелізму даних і модель паралелізму задач. Модель паралелізму даних має на увазі незалежну обробку даних кожним процесом (наприклад, векторні операції з масивами). Модель паралелізаму задач передбачає розбиття основної задачі на самостійні підзадачі, кожна з яких виконується окремо й обмінюється даними з іншими. Це більш трудомісткий, у порівнянні з паралелізмом даних, підхід. Перевагою є велика гнучкість і велика воля, надана програмісту в розробці програми, що ефективно використовує ресурси паралельної системи. При цьому можуть застосовуватися спеціалізовані бібліотеки, що беруть на себе всі «організаційні» задачі. Приклади таких бібліотек: MPI (Message Passing Interface) і PVM (Parallel Virtual Machine).
При розробці паралельних програм виникають специфічні для даної моделі обчислень проблеми сугубо технічного характеру: забезпечення комунікацій між підзадачами, забезпечення надійності й ефективності цих комунікацій. Для рішення цих проблем можна реалізувати власні методи, а можна використовувати вже готові стандарти/специфікації/бібліотеки. MPI – «Інтерфейс передачі повідомлень» - це специфікація, що була розроблена в 1993-1994 роках групою MPI Forum (http://www.mpi-forum.org),і забезпечує реалізацію моделі обміну повідомленнями між процесами. Остання версія даної специфікації MPI-2. У моделі програмування MPI програма породжує кілька процесів, взаємодіючих між собою за допомогою звертання до підпрограм прийому і передачі повідомлень.
Звичайно, при ініціалізації MPI-програми створюється фіксований набір процесів, причому (що, утім, необов'язково) кожний з них виконується на своєму процесорі. У цих процесах можуть виконуватися різні програми, тому MPI-модель іноді називають MPMD-моделлю (Multiple Program, Multiple Data), на відміну від SPMD (Single Program…)моделі, де на кожному процесорі виконуються тільки однакові задачі. MPI підтримує двохточкові і глобальні, синхронні й асинхронні типи комунікацій. Спеціальний механізм – комунікатор – ховає від програміста внутрішні комунікаційні структури.
Організація процесу обчислення
Множення матриці A розміру mxn і матриці B розміру nxl призводить до отримання матриці С розміру mxl, кожен елемент якої визначається відповідно до виразу: / (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) де / є час виконання однієї елементарної скалярной операції.
Множення матриць при стрічковій схемі розділення даних
З визначення операції матричного множення випливає, що обчислення усіх елементів матриці С може бути виконано незалежно один від одного. Як результат, можливий підхід для організації паралельних обчислень полягає у використанні в якості базової підзадачі процедури визначення одного елемента результуючої матриці С. Для проведення всіх необхідних обчислень кожна підзадача повинна містити по одному рядку матриці А і одному стовпцю матриці В. Загальна кількість одержуваних при такому підході підзадач виявляється рівним n2 (по числу елементів матриці С).
Розглянувши запропонований підхід, можна зазначити, що досягнутий рівень паралелізму є в більшості випадків надмірним. Зазвичай при проведенні практичних розрахунків таку кількість сформованих підзадач перевищує число наявних процесорів і робить неминучим етап укрупнення базових завдань. У цьому плані може виявитися корисною агрегація обчислень вже на кроці виділення базових підзадач. Можливе рішення може полягати в об'єднанні в рамках однієї підзадачі всіх обчислень, пов'язаних не з одним, а з декількома елементами результуючої матриці С. Для подальшого розгляду визначимо базове завдання як процедуру обчислення всіх елементів однієї з рядків матриці С. Такий підхід призводить до зниження загальної кількості підзадач до величини n.
Для виконання всіх необхідних обчислень базової підзадачі повинні бути доступні один з рядків матриці A і всі стовпці матриці B. Просте вирішення цієї проблеми - дублювання матриці B у всіх підзадача - є, як правило, неприйнятним в силу великих витрат пам'яті для зберігання даних. Тому організація обчислень повинна бути побудована таким чином, щоб в кожний поточний момент часу підзадачі містили лише частину даних, необхідних для проведення розрахунків, а доступ до решти даних забезпечувався б за допомогою передачі даних між процесорами.
Виділення інформаційних залежностей
Для обчислення одного рядка матриці С необхідно, щоб у кожній підзадачі містилася рядок матриці А і був забезпечений доступ до всіх стовпцях матриці B. Можливі способи організації паралельних обчислень полягають у наступному. Алгоритм являє собою ітераційну процедуру, кількість ітерацій якої збігається з числом підзадач. На кожній ітерації алгоритму кожна підзадача містить по одному рядку матриці А і одному стовпцю матриці В. При виконанні ітерації проводиться скалярне множення, що призводить до отримання відповідних елементів результуючої матриці С. Після завершення обчислень в кінці кожної ітерації стовпці матриці В повинні бути передані між підзадачами з тим, щоб у кожній підзадачі виявилися нові стовпці матриці В і могли бути обчислені нові елементи матриці C. При цьому дана передача стовпців між підзадачами повинна бути організована таким чином, щоб після завершення ітерацій алгоритму в кожній підзадачі послідовно опинилися всі стовпці матриці В. Можлива проста схема організації необхідної послідовності передач стовпців матриці В між підзадачами полягає в представленні топології інформаційних зв'язків підзадач у вигляді кільцевої структури. У цьому випадку на кожній ітерації підзадача i, 0 <= i <n, буде передавати свій стовпець матриці В підзадачі з номером i +1 (відповідно до кільцевої структури підзадача n-1 передає свої дані підзадачі з номером 0) -Рис. 1.2. Після виконання всіх ітерацій алгоритму необхідна умова буде забезпечена в кожній підзадачі почерзі опиняться всі стовпці матриці В.
На рис. 1.2 представлені ітерації алгоритму матричного множення для випадку, коли матриці складаються з чотирьох рядків і чотирьох стовпців (n = 4). На початку обчислень в кожній підзадачі i, 0 <= i <n, розташовуються i-й рядок матриці A і i-й стовпець матриці B. В результаті їх перемножування підзадача отримує елемент Сіi результуючої матриці С. Далі підзадачі здійснюють обмін стовпцями, в ході якого кожна підзадача передає свій стовпець матриці B наступної підзадачі відповідно до кільцевої структури інформаційної взаємодії. Далі виконання описаних дій повторюється до завершення всіх ітерацій паралельного алгоритму.
/ Рис. 1.2. Загальна схема передачі даних для паралельного алгоритму матричного множення при стрічковій схемі розділення даних.
2.РОЗРОБКА ГРАФ СХЕМИ ВИКОНАННЯ ЗАДАНОЇ ФУНКЦІЇ
Комунікаційна мережа між процесорами представлена на Рис 2.1. В якості процесора який має доступ до пам’яті було вибрано процесор №5.
Рис. 2.1. граф-схема зв’язків між процесорами
Граф-схема початкового завантаження даних у процесори показана на Рис 2.2.
Перший крок: Процесор 5 передає на процесори 4,6 почасткову інформацію, на процесор 3 передається інформація для процесорів 2 та 3.
Другий крок: Процесор 5 передає на процесори 0,1,7 відповідну й
рис. 2.2. граф-схема завантаження даних
рис. 2.3. граф-схема вивантаження даних
На рис. 2. 2 наведена граф-схема виконання алгоритму множення двох матриць на кільцевій структурі з завантаженням через один з процесорів.
Рис. 2.2. Граф-схема виконання алгоритму множення двох матриць на кільцевій структурі з завантаженням через один з процесорів
3. РОЗРАХУНКОВИЙ РОЗДІЛ
Для процесорних елементів визначимо такі розміри підматриць:
Розбиття матриці А на під матриці для кожного процесора
240*288
№
Рядків
Стовбців
0
30
288
1
30
288
2
30
288
3
30
288
4
30
288
5
30
288
6
30
288
7
30
288
Розбиття матриці В на під матриці для кожного процесора
288*181
№
Рядків
Стовбців
0
288
23
1
288
23
2
288
23
3
288
23
4
288
23
5
288
22
6
288
22
7
288
22
, ,
Згідно завдання:
Tu=10Ts=7Tp=3Tz=3Tw
Виразимо інші операції через найменший час :
, , , .
Оскільки в нашому випадку всі елементи завантажуються через 1 процесор то кількість результуючих послідовних операцій завантаження буде рівна числу всіх звертань процесорів до пам’яті.
Отже в даному випадку кількість операцій завантаження та загальний час завантаження:
Nzav = (n1*n2+n2*n3) = (69120+52128) =121248
Тzav = (n1*n2+n2*n3)*Tz = 121248 Tz=( 404160 Ts)
Після операції завантаження початкових даних необхідно переслати початкові дані процесорам з функціональної схеми визначаємо час який необхідний для передачі початкових даних на всі процесори.
Кількість операцій пересилання для передачі пібматриць:
NpA =30*288=8640
NpB =288*23=6624
Тпп = (3*NpA’+ 3*NpB’)Tp = (25920+19872)Tp = 45792Tp= (65417 Ts)
Після операції початкового пересилання даних в процесори запускається цикл обробки даних, який має 8 ітерацій, які включають в себе як множення підматриць, так і пересилання даних між процесорами (підматриці ).
Для послідовного алгоритму загальна кількість операцій множення та додавання та час на їх виконання:
Загальна кількість операцій множення та додавання на кільцевій структурі при кожній ітерації рівна рівна:
,
.
Час виконання:
(*хоча кількість операцій на кожному з процесорів буде різна через різний розмір підматриці В але через необхідність пересилки даних процесори будуть вимушень очікувати завершення обчислень на процесорах які мають під матриці з більшим розміром)
Сумарна кількість операцій множення та додавання при опрацюванні даних на кільцевій структурі:
, .
, .
Час їх виконання:
Кожний процесор може в один момент часу або тільки приймати або тільки передавати інформацію. Тому передача інформації буде відбуватися за два такти.
Тобто, кількість операцій обміну на кожній ітерації рівна подвійній кількості елементів найбільшої з підматриць :
.
Тоді загальна кількість операцій обміну буде рівна кількості таких операцій на семи ітераціях:
.
Після виконання семи ітерацій отримуємо результуючі часткові підматриці , які необхідно зібрати в результуючу матрицю С.
Tzb = 5*N1*N3/8*Tp=5*240*181/8=27150Tp=38786Ts
(З функціональної схеми визначаємо)
Вивантаження даних відбувається послідовно кількість даних рівна величині результуючої матриці.
.
Для визначення точних характеристик системи врахуємо співвідношення часових параметрів (згідно з завданням). Насамперед, зведемо час виконання різних операцій до спільного знаменника, тобто визначимо базову операцію для знаходження часу виконання інших операцій.
Для визначення повного часу необхідно визначити час всіх його складових, де операції виконуються послідовно (завантаження, вивантаження) та паралельно (обчислення, обмін даними).
Тоді загальна кількість операцій при виконанні паралельного алгоритму на кільцевій структурі:
,
.
Для порівняння обчислимо умовний час виконання послідовного алгоритму:
Порівнюючи остаточні результати бачимо, що перемноження матриць на одному процесорі приблизно в 7,561 рази повільніше за множення на восьми процесорній системі на основі кільцевої топології.
Для характеристики алгоритму визначимо коефіцієнт К, який рівний відношенню часу виконання загального алгоритму до часу виконання паралельних операцій.
,
.
Ефективність визначається як відношення часу виконання операцій на однопроцесорній системі, до часу потрібного на виконання для багатопроцесорної на кількість процесорів в ній.
4. РОЗРОБКА ФУНКЦІОНАЛЬНОЇ СХЕМИ
рис 2.3 Функціональна схема обчислення.
5. РОЗРОБКА ПРОГРАМИ
Лістинг програми наведений у додатку. Дана програма написана на мові C++ в середовищі розробки Visual Studio2008. Програма має консольний інтерфейс.
На рис. 5.1 представлено вікно з результатами виконання програми
/
Рис. 5.1. Вікно консолі з розробленої програми
Граф-схема програми наведена на рис 5.2.
Рис. 5.2. Загальна граф-схема програми
Для обміну інформацією між процесами використовуються функції бібліотеки MPI 2.0 MPI_Send() та Розповсюдження вхідних даних виконується не напряму, а із врахуванням структури системи (з врахуванням фізичних зв’язків між вузлами системи).
ВИСНОВКИ
Після успішного виконання курсового проекту я своєчасно оволодів технологією побудови багатопроцесорних системи на основі кільцевої структури. Розробив восьми процесорну систему множення двох матриць, при чому дані зчитуються з пам’яті одним процесором. Також було проведено деякі обчислення, які дають уявлення про характеристики даного паралельного алгоритму, та порівняно його з послідовним. В результаті проведеної роботи можна зробити такі висновки: для восьми процесорної системи та матриць з розмірами 240х288 288х181 умовний час виконання програми в інтервалах виконання операції виявився рівним , а для послідовної структури Tpos = Ts що приблизно в 7,561 рази довше. Ефективність при цьому рівна E = 94,5% , що є досить хорошим показником, але не ідеальним.
СПИСОК ЛІТЕРАТУРИ
Корнеев В.В. Параллельные вычислительные системы. М.: Нолидж, 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 – Високопродуктивні обчислення.
ДОДАТКИ
Лістинг програми
06.03.2013 23:03-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора