Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Паралельне виконання операцій множення матриць
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Кафедра ЕОМ
Інформація про роботу
Рік:
2011
Тип роботи:
Курсова робота
Предмет:
Паралельні та розподілені обчислення
Група:
КІ
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ І НАУКИ, МОЛОДІ ТА СПОРТУ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ „ЛЬВІВСЬКА ПОЛІТЕХНІКА”
Кафедра ЕОМ
Курсова робота
з дисципліни: “ Паралельні та розподілені обчислення”
на тему:
«Паралельне виконання операцій множення матриць»
Завдання
1.Задаються дві матриці А (розмірністю n1*n2) та В (розмірністю n2*n3) :
n1=6Б, n2=1П, n3=3І – КІ-45
де nП, nБ та nІ номер букви в прізвищі, імені та по-батькові відповідно.
Калинюк Олег Петрович КІ-45:
декодування вибраних літер для 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=6Б – В = 100 n2=1П – К = 208 n3=3І – Е = 149
Отже маємо матрицю А(100*208) та матрицю В(208*149)
2. Розробити та описати алгоритм множення матриць А*В на структурі, яка задається виразом:
9b-10b-3b-6b-7b-12b-8b-4b – КІ-45, де «nb»- номер букви П.І.Б студента.
Калинюк Олег Петрович КІ-45:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
К
а
л
и
н
ю
к
О
л
е
г
П
е
т
р
о
в
и
ч
3
8
4
5
7
1
2
6
Отримаємо – ЛЕИЮКПОН
Для ЛЕИЮКПОН отримаємо 212, 171, 91, 63, 47, 219, 250, 134. Даний набір чисел записуємо у стовпець і переводимо в двійкове 8-ми розрядне число. В отриманій двійковій матриці одиниці що розташовані на головній діагоналі замінюємо на 0:
212 - 11010100
171 - 10101011
091 - 01011011
063 - 00111111
047 - 00101111
219 - 11011011
250 - 11111010
134 – 10000110
=>
01010100
10101011
01011011
00101111
00100111
11011011
11111100
10000110
Отримана матриця розміру 8*8 є матрицею зв’язків орієнтованого графу, вершини якого це процесори, а напрямлені дуги це напрямлені лінії зв’язку між процесорами.
3.Для цієї структури визначити час виконання алгоритму, відсоток послідовної частини алгоритму та ефективність алгоритму для значень, співвідношення часових параметрів та тип початкового завантаження визначаються за правилами:
3.1. Тип початкового завантаження даних type:
, де Zi цифри номера залікової книжки, n=1..k, де k – кількість цифр номера залікової книжки.
КІ-41 … КІ-46: type=1(спільна пам’ять),type=2(через один процесор), type=3(розподілена пам’ять).
0809243
type=(0+8+0+9+2+4+3)=26 mod 3 + 1 = 3 (з розподіленої памяті)
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=3tP=5tZ=4tW
Розміри матриць
Кількість процесорів (Р)
Тип початкового завантаження даних
Співвідношення часових параметрів
n1
n2
n3
100
208
149
8
З розподіленої памяті
Tu=10Ts=3Tp=5Tz=4Tw
Анотація
В даній курсовій роботі розроблена структура перемноження матриці на матрицю на кільцевій структурі, завантаження початкових даних в процесори відбувається з розподіленої памяті. Розміри матриць згідно із варіантом. Також пораховано час виконання алгоритму, відсоток послідовної частини алгоритму та ефективність алгоритму для значень згідно з варіанту.
Курсова робота виконана у середовищі Microsoft Visual Studio 2008 на мові С++ з використанням бібліотек MPI і має консольний інтерфейс. В курсовій наведено граф-схеми виконання алгоритму множення двох матриць на кільцевій структурі .
ЗМІСТ
Вступ 6
1. Теоретичний розділ 7
2. Розробка граф-схеми виконання множення двох матриць 13
3. Розрахунковий розділ 17
4. Розробка схеми планування обчислень 20
5. Розробка програми 23
Висновок 27
Список літератури 28
Додатки 29
Лістинг програми 29
Вступ.
З недавніх пір електронно-обчислювальні машини міцно і надовго увійшли в життя кожної окремо взятої людини. Саме ці пристрої є головними помічниками людей у розв'язанні проблем у різних життєвих сферах. Застосування цього чуда техніки підвищує ефективність і якість планування та управління виробництвом, розробки складних технічних пристроїв, освіти тощо. З розвитком науки і техніки кількість завдань, які вирішуються складно невпинно зростає. Для вирішення багатьох з них можливостей звичайних комп'ютерів зазвичай недостатньо. Такі сфери науки як моделювання клімату, генна інженерія, проектування інтегральних схем, створення лікарських препаратів вимагає продуктивності обчислювальної техніки.
Довгий час вирішення цієї важливою проблеми не давало спокою науковцям з цілого світу. У підсумку, було вирішено прискорювати вирішення обчислювальних завдань за допомогою паралельних обчислень. Під паралельними обчисленнями розуміють виконання декількох обчислень в один і той же час на різних процесорах. Алгоритми, які використовуються розділяються на інформаційно-незалежні частини. Кожен з цих фрагментів виконується на окремому процесорі. В нашому випадку використання структур паралельної обробки даних, а саме, кільцева, 2D (решітка), 3D (куб), значно прискорює процес розпаралелення та розподіленого обчислення задачі між процесорами.
Теоретичний розділ
Основна ідея розпаралелювання обчислень – мінімізація часу виконання задачі за рахунок розподілу навантаження між декількома обчислювальними пристроями. Цими «обчислювальними пристроями» можуть бути як процесори одного суперкомп'ютера, так і кілька комп'ютерів, об’єднаних за допомогою комунікаційної мережі в єдину обчислювальну структуру – кластер.
Паралельна модель програмування сильно відрізняється від звичайної – послідовної. Існують дві моделі паралельного програмування: модель паралелізму даних і модель паралелізму задач. Модель паралелізму даних має на увазі незалежну обробку даних кожним процесом (наприклад, векторні операції з масивами). Модель паралелізму задач передбачає розбиття основної задачі на самостійні підзадачі, кожна з яких виконується окремо й обмінюється даними з іншими. Це більш трудомісткий, у порівнянні з паралелізмом даних, підхід. Перевагою є велика гнучкість надана програмісту в розробці програми, що дає можливість ефективно використовує ресурси паралельної системи. При цьому можуть застосовуватися спеціалізовані бібліотеки, що беруть на себе всі «організаційні» задачі. Приклади таких бібліотек: 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.1. Всі процесори в один момент часу можуть передавати або отримувати дані тільки від одного процесора.
Рис. 2.1. Граф-схема зв’язків між процесорами
Оскільки паралельне обчислення добутку матриць грунтується на паралельному множенні рядків, які рівномірно розділенні між процесорами, матриці А на матрицю В. Розподіл матриці А між процесорами має вигляд:
Матриця А
12*208 А0
12*208 А1
12*208 А2
12*208 А3
13*208 А4
13*208 А5
13*208 А6
13*208 А7
При великих розмірах матриці В недоцільно зберігати її на кожному процесорі, оскільки це приводить до значних витрат пам’яті. Щоб зменшити об’єм памяті, який необхідний для зберігання вхідних даних матриця В розбивається на стовбці, які також рівномірно розміщуються по процесорах. Для доступу до наступних стовпців матриці В відбувається процес обміну даних між процесорами. Розподіл матриці В між процесорами має вигляд:
Матриця В
208*19 В0
208*19 В1
208*19 В2
208*19 В3
208*19 В4
208*18 В5
208*18 В6
208*18 В7
Щоб отримати кінцевий результат необхідно зібрати результуючі дані з усіх процесорів. Збирати результат необхідно за такою схемою.
Матриця результату R
12*149R0
12*149 R1
12*149 R2
12*149 R3
13*149 R4
13*149 R5
13*149 R6
13*149 R7
Збір даних проводиться за сім кроків, граф-схема збору даних показана на рис 2.2.
Перший крок: Процесор 1 передає підматрицю R1 результату процесору 6:
Другий крок: Процесор 2 передає підматрицю R2 результату процесору 6
Процесор 0 передає підматрицю R0 результату процесору 1
Третій крок: Процесор 1 передає підматрицю R0 результату процесору 6
Четвертий крок: Процесор 3 передає підматрицю R3 результату процесору 6
Пятий крок: Процесор 4 передає підматрицю R4 результату процесору 6
Шостий крок: Процесор 5 передає підматрицю R5 результату процесору 6
Сьомий крок: Процесор 7 передає підматрицю R7 результату процесору 6
Рис. 2.2. Граф-схема збору даних
На рис. 2.3 наведена граф-схема виконання алгоритму множення двох матриць з пересилкою даних по кільцевій структурі з завантаженням даниз з розподіленої памяті.
Рис. 2.3. Граф-схема виконання алгоритму множення двох матриць на кільцевій структурі з завантаженням даних з розподіленої памяті.
3. Розрахунковий розділ
Для процесорних елементів визначимо такі розміри підматриць:
,, ,
Згідно завдання:
Tu=10Ts=3Tp=5Tz=4Tw
Виразимо інші операції через найменший час :
, , , .
Оскільки в нашому випадку матриці завантажуються з розподіленої памяті то кількість результуючих послідовних операцій завантаження буде рівна сумі елементів найбільших під матриць А та В.
Nzav = (n1*N2+N2*n3) = (13*208+208*19) =6656
Де n1- кількість рядків найбільшої з підматриць А, n3 – кількість стовпців найбільшої з підматриць В.
Отже в даному випадку загальний час завантаження:
Тzav = (n1*N2+N2*n3)*Tz = 6656 Tz = (13312Ts)
Для послідовного алгоритму час завантаження рівний:
Тzp = (N1*N2+N2*N3)*Tz = 51792 Tz = (103548Ts)
Після операції завантаження даних в процесори запускається цикл обробки даних, який має 8 ітерацій, які включають в себе як множення підматриць, так і пересилання даних між процесорами (підматриці ).
Для послідовного алгоритму загальна кількість операцій множення та додавання та час на їх виконання:
Загальна кількість операцій множення та додавання на кільцевій структурі при кожній ітерації рівна:
,
.
(n1- кількість рядків найбільшої з підматриць А, n3 – кількість стовбців найбільшої з під матриць В)
Час виконання:
(*хоча кількість операцій на кожному з процесорів буде різна через різний розмір підматриці В але через необхідність пересилки даних процесори будуть вимушені очікувати завершення обчислень на процесорах, які мають підматриці з більшим розміром)
Сумарна кількість операцій множення та додавання при опрацюванні даних на кільцевій структурі:
, .
, .
Час їх виконання:
Кожний процесор може в один момент часу або тільки приймати або тільки передавати інформацію. Тому передача інформації буде відбуватися за два такти.
Тобто, кількість операцій обміну на кожній ітерації рівна подвійній кількості елементів найбільшої з підматриць :
.
Тоді загальна кількість операцій обміну буде рівна кількості таких операцій на семи ітераціях:
.
Після виконання семи ітерацій отримуємо результуючі часткові підматриці , які необхідно зібрати в результуючу матрицю R. Оскільки схема вивантаження включає в себе сім послідовних передач матриць результату то загальний час збору буде рівний:
Tzb = 7*N1*N3/8*Tp=7*208*149/8 Tp =27118Tp=90393Ts
Вивантаження даних відбувається послідовно кількість даних рівна величині результуючої матриці.
.
Для визначення повного часу необхідно визначити час всіх його складових, де операції виконуються послідовно (завантаження, вивантаження) та паралельно (обчислення, обмін даними).
Тоді загальна кількість операцій при виконанні паралельного алгоритму на кільцевій структурі:
,
.
Для порівняння обчислимо умовний час виконання послідовного алгоритму, який включає в себе час на завантаження та вивантаження даних та час множення та додавання при послідовному алгоритмі :
Порівнюючи остаточні результати бачимо, що перемноження матриць на одному процесорі приблизно в рази повільніше за множення на восьми процесорній системі на основі кільцевої топології.
Ефективність визначається як відношення часу виконання операцій на однопроцесорній системі, до часу потрібного на виконання для багатопроцесорної на кількість процесорів в ній.
4. Розробка схеми планування обчислень.
Схема планування обчислення множення двох матриць зображена на рис.4.1. Вона складається з чотирьох етапів:
завантаження даних з пам’яті;
восьми ітерацій обчислення з зсувом частин матриці В по кільцю;
збором результуючої матриці;
вивантаження результату у пам'ять;
Етапи завантаження даних з пам’яті та початкової розсилки даних відбуваються поступово це зроблено для зменшення об’єму пам’яті необхідної для зберігання даних.
Рис 4.1 Схема планування обчислення множення двох матриць.
5. Розробка програми
Лістинг програми наведений у додатку. Дана програма написана на мові C++ в середовищі розробки Visual Studio2008. Програма має консольний інтерфейс.
Граф-схема програми наведена на рис 5.1.
Рис. 5.1. Загальна граф-схема програми
На рис. 5.2 представлено вікно з результатами виконання програми
/
Рис. 5.2. Вікно консолі з розробленої програми
Для обміну інформацією між процесами використовуються функції бібліотеки MPI 2.0 MPI_Send(), MPI_Resv(), MPI_Scaterv(). Розповсюдження вхідних даних виконується не напряму, а із врахуванням структури системи (з врахуванням фізичних зв’язків між вузлами системи).
Розглянема синтаксис операцій обміну повідомлень які використовувалися в даній курсовій роботі:
MPI_Send
int MPI_Send(void *buf, int count, MPI_Datatype type, int dest, int tag, MPI_Comm comm), де
buf - адреса буфера пам'яті, в якому розташовуються дані повідомлення, що відправляється;
count - кількість елементів даних в повідомленні;
type - тип елементів даних повідомлення, що пересилається;
dest - ранг процесу, якому відправляється повідомлення;
tag - значення-тег, що використовується для ідентифікації повідомлення;
comm - комунікатор, в рамках якого виконується передача даних.
MPI_Recv
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 - вказівник на структуру даних з інформацією про результат виконання операції прийому даних.
MPI_Scaterv
int MPI_Scatterv(void* sendbuf, int *sendcounts, int *displs, MPI_Datatype sendtype, void* recvbuf, int recvcount, MPI_Datatype recvtype, int root, MPI_Comm comm)
sendbuf – адрес початку буфера передачі;
sendcounts – цілочисельний масив (розмір якого рівний кількості процесорів в групі) який вміщує кількість елементів які будуть посилатися кожному процесорові
displs – цілочисельний масив (розмір якого рівний кількості процесорів в групі) визначає зміщення від початку sendbuf для даних які посилаються кожному процесорові;
sendtype – тип даних що передається
recvbuf – адрес початку прийому
recvcount – кількість елементів що приймається
recvtype – тип елементів що приймається
root – номер процесора відправника
comm – комунікатор
Висновок
Під час виконання курсового проекту я оволодів технологією написання програм для багатопроцесорних систем. Розробив восьми процесорну систему множення двох матриць в якій дані зчитуються з розподіленої памяті. Також було проведено деякі обчислення, які дають уявлення про характеристики даного паралельного алгоритму у порівняні з послідовним. В результаті проведеної роботи можна зробити такі висновки: для восьми процесорної системи та матриць з розмірами 100х208 208х149 умовний час виконання програми в інтервалах виконання операції виявився рівним , а для послідовної структури Tpos = Ts, що приблизно в 6,98 рази довше. Ефективність при цьому рівна E = 87,3% , що є досить хорошим показником, але не ідеальним.
СПИСОК ЛІТЕРАТУРИ
Корнеев В.В. Параллельные вычислительные системы. М.: Нолидж, 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 – Високопродуктивні обчислення.
Додаток
Лістинг програми
#include "stdafx.h"
#include <stdio.h>
#include <iostream>
#include <stdlib.h>
#include <iostream>
#include "mpi.h"
using namespace std;
const int route=0;
const int circle[] = {0,1,2,3,4,7,6,5};
const int procNumber=8;
const int N1=100;
const int N2=208;
const int N3=149;
int procRank;
const int root=0;
struct A{
int row;
int n1;
int n2;
double arr[N1/8+N1][N2];
};
struct B{
int col;
int n2;
int n3;
double arr[N2][N3/8+N3];
};
struct R{
int n1;
int n3;
double arr[N1/8+N1][N3];
};
double matrixA[N1][N2]={0};
double matrixB[N2][N3]={0};
double Res[N1][N3]={0};
A subA[procNumber];
B subB[procNumber];
A procA;
B procB;
R procRes;
R result[procNumber];
void DataCircleReplication(){
MPI_Status Status;
if(procRank!=root)
MPI_Send(&procRes,sizeof(procRes),MPI_BYTE,root,0,MPI_COMM_WORLD);
if(procRank==root){
for(int i=0;i<procNumber;i++)
if(i!=root)
MPI_Recv(&result[i],sizeof(procRes),MPI_BYTE,i,0,MPI_COMM_WORLD,&Status);
result[root]=procRes;
}
}
void DataCircleDistribution(){
if(procRank==root){
procA = subA[root];
procB = subB[root];
for(int i=0;i<procNumber;i++)
if(i!=root){
MPI_Send(&subA[circle[i]],sizeof(subA[circle[i]]),MPI_BYTE,circle[i],0,MPI_COMM_WORLD);
MPI_Send(&subB[circle[i]],sizeof(subB[circle[i]]),MPI_BYTE,circle[i],0,MPI_COMM_WORLD);
}
}
MPI_Status Status;
if(procRank!=root){
MPI_Recv(&procA,sizeof(procA),MPI_BYTE,root,0,MPI_COMM_WORLD,&Status);
MPI_Recv(&procB,sizeof(procB),MPI_BYTE,root,0,MPI_COMM_WORLD,&Status);
}
}
void DataSend(){
procRes.n1=procA.n1;
procRes.n3=N3;
MPI_Status Status;
for(int k=0;k<procNumber;k++){
for(int i=0;i<procNumber;i++)
if(procRank==circle[i])
MPI_Send(&procB,sizeof(B),MPI_BYTE,circle[(i+1)%8],0,MPI_COMM_WORLD);
for(int i=-1;i<procNumber-1;i++)
if(procRank==circle[i+1]){
if(i==-1)i=7;
MPI_Recv(&procB,sizeof(B),MPI_BYTE,circle[i],0,MPI_COMM_WORLD,&Status);
}
for(int i=0;i<procA.n1;i++)
for(int j=0;j<procB.n3;j++)
for(int k=0;k<procA.n2;k++)
procRes.arr[i][j+procB.col]+=procA.arr[i][k]+procB.arr[k][j];
}
}
int main(int argc, char* argv[])
{
MPI_Init(&argc, &argv);
MPI_Comm_rank(MPI_COMM_WORLD,&procRank);
if(procRank==root){
for(int i=0;i<N1;i++)
for(int j=0;j<N2;j++)
matrixA[i][j]=rand()%9+1;
for(int i=0;i<N2;i++)
for(int j=0;j<N3;j++)
matrixB[i][j]=rand()%9+1;
for(int i=0;i<N1;i++)
for(int j=0;j<N3;j++)
for(int k=0;k<N2;k++)
Res[i][j]+=matrixA[i][k]+matrixB[k][j];
int rowsSum=0;
int restRows = N1;
int restProc = procNumber;
for(int i=0;i<procNumber;i++)
{
subA[i].row=rowsSum;
subA[i].n1 = restRows/restProc;
subA[i].n2 = N2;
for (int k=0;k<subA[i].n1;k++)
for(int j=0;j<subA[i].n2;j++)
subA[i].arr[k][j] = matrixA[k+rowsSum][j];
rowsSum+=subA[i].n1;
restRows -= restRows/restProc;
restProc--;
}
rowsSum=0;
restProc = procNumber;
restRows = N3;
for(int i=0;i<procNumber;i++)
{
subB[i].col = rowsSum;
subB[i].n2 = N2;
subB[i].n3 = restRows/restProc;
for (int k= 0;k<subB[i].n2;k++)
for(int j=0;j<subB[i].n3;j++)
subB[i].arr[k][j] = matrixB[k][j+rowsSum];
rowsSum+=subB[i].n3;
restRows -= restRows/restProc;
restProc--;
}
cout<<"Matrix A"<<endl;
for(int i=0;i<N1;i++){
for(int j=0;j<N2;j++)
cout<<matrixA[i][j]<<" ";
cout<<endl;
}
cout<<endl<<"Matrix B"<<endl;
for(int i=0;i<N2;i++){
for(int j=0;j<N3;j++)
cout<<matrixB[i][j]<<" ";
cout<<endl;
}
cout<<endl<<"Result"<<endl;
for(int i=0;i<N1;i++){
for(int j=0;j<N3;j++)
cout<<Res[i][j]<<" ";
cout<<endl;
}
}
DataCircleDistribution();
DataSend();
DataCircleReplication();
if(procRank==root){
cout<<endl<<endl;
for(int k=0;k<procNumber;k++)
for(int i=0;i<result[k].n1;i++){
for(int j=0;j<result[k].n3;j++)
cout<<result[k].arr[i][j]<<" ";
cout<<endl;
}
}
MPI_Finalize();
return 0;
}
10.02.2012 12:02-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора