Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Паралельне виконання операцій множення матриць
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Кафедра ЕОМ
Інформація про роботу
Рік:
2024
Тип роботи:
Курсова робота
Предмет:
Паралельні та розподілені обчислення
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти і науки України
Національний університет “Львівська політехніка”
Кафедра ЕОМ
КУРСОВА РОБОТА
з дисципліни:
«Паралельні та розподілені обчислення»
на тему:
«Паралельне виконання операцій множення матриць»
Залікова книжка № 1009546
Львів
2014р.
Завдання
Розробити структуру та описати процедуру перемноження матриці А(розмірністю n1*n2) на матрицю В (розмірністю n2*n3) на заданій структурі. Для цієї структури визначити час виконання алгоритму, відсоток послідовної частини алгоритму та ефективність алгоритму для значень, що наведені в таблиці.
Для визначення завдання були виконані такі дії:
1. Визначення розмірів матриць. Для цього потрібно було провести декодування літер, які задавались згідно номеру групи:
n1=3П-"Х" , n2=2І-"O", n3=4Б-"H" – КІ-42
Згідно з таблицею декодування літер розмірностей:
n1 = 240 n2 = 248 n3 = 67
А(240*248)
В(248*67)
С(240*67)
2. Структура задається виразом:
5b-12b-6b-11b-8b-1b-3b-13b – КІ-42
де «nb»- номер букви П.І.Б студента.
Для того, щоб сформувати задану структуру, скористаємось таблицею 1.1., щоб отримати відповідні літери. Після цього розкодуємо їх задопомогою таблиці кодування букв.
Таблиця 1.1. - Порядкові номери літер прізвища, імені та по-батькові
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
К
У
Х
А
Р
Б
О
Г
Д
А
Н
І
В
А
Н
О
В
И
Ч
6
7
1
3
5
4
2
8
Порядк літер прізвища, імені та по-батькові з таблиці 1.1.: РІБНГКХА
Звідси формуємо таблицю декодування табл. 1.2, та матрицю зв’язків табл. 1.3.
Таблиця 1.2.Таблиця декодування
Р = 93
01011101
І = 223
11011111
Б = 35
00100011
Н = 134
10000110
Г = 74
01001010
К = 47
00101111
Х = 127
01111111
А = 27
00011010
Таблиця 1.3.Матриця зв’язків
ms
1
2
3
4
5
6
7
8
1
0
1
0
1
1
1
0
1
2
1
0
0
1
1
1
1
1
3
0
0
0
0
0
0
1
1
4
1
0
0
0
0
1
1
0
5
0
1
0
0
0
0
1
0
6
0
0
1
0
1
0
1
1
7
0
1
1
1
1
1
0
1
8
0
0
0
1
1
0
1
0
3. Визначення типу пам’яті:
Номер залікової книжки: 1009546
(25 mod 3) + 1 = 2 – завантаження через один процесор.
Співвідношення часових параметрів: tU = 10tS = 6tP =5tZ = 7tW
Анотація
В даній курсовій роботі завданням було розробка алгоритму паралельного множення двох матриць розмірами 240х248 і 248х67 на розподіленій комп’ютерній системі із восьми процесорів, при чому завантаження і вивантаження відбувалось через один із них. Такий алгоритм може бути ефективним в системах з обмеженим доступом до пам’яті. Для реалізації паралельного алгоритму множення матриць було використано інтерфейс передачі повідомлень (МРІ) між процесами, оскільки він має широкі можливості. Для програмної реалізації алгоритму було обрано мову С++, з використаннямMPI. Наведені граф-схеми виконання алгоритму, схеми планування обчислень і блок-схеми програми множення матриць пояснюють реалізацію даного алгоритму більш детально.
Зміст
Вступ 6
1. Теоретичний розділ 7
1.1 Матричні обчислення 7
1.2 Інтерфейс передачі повідомлень 10
1.3 Сучасні методи та інструменти для паралельної обробки................11
1.3.1 Технологія NVIDIA® CUDA™..................................................12
2. Розробка граф-схеми виконання множення матриць 13
3. Розробка функціональної схеми 18
4. Розрахунковий розділ 23
4.1 Визначення розмірності підматриць 23
4.2 Розрахунок часу виконання послідовного алгоритму 24
4.3 Розрахунок часу виконання паралельного алгоритму 25
4.4 Порівняння ефективності 25
5.Розробка програми 26
5.1 Вибір середовища 26
5.2 Опис використаних функцій MPI 26
5.3 Розробка загальної блок-схеми програми 31
Висновки 32
Список використаної літератури 33
Додаток 39
Вступ
Доволі значна частина математичних моделей, що розглядаються при вирішенні проблем, породжених промисловістю, наукою та технікою, зводяться до задач математичної фізики. В наші часи чи не єдиним способом їх розв’язання є чисельні методи та використання ЕОМ. Проте вимоги до їх реалізації постійно зростають: вона має бути швидшою, точнішою і здатною дати лад новим, більш складним задачам. Наразі основною матеріальною базою для проведення подібних обчислень є суперкомп’ютери та кластери зі значною кількістю потужних процесорів. Проте такий підхід є доволі дорогим як з точки зору вартості комплектуючих, так і з урахуванням вартості електроенергії, необхідної для функціонування подібного обчислювального комплексу.
Домінуюче положення при розробці паралельних програм для паралельних систем займає стандарт MPI (англ. Message Passing Interface) та використання технології CUDA від Nvidia. Обидві технології є доволі ефективними.
Програма, яка розроблена за допомогою MPI може бути представлена інформаційним графом, вершинам якого відповідають паралельні гілки програми, а ребрам комунікаційні зв'язки між ними. Це можна використовувати для диспетчеризації завдань та їх обчислювальних потоків. Враховуючи гетерогенність обчислювальних ресурсів і середовищ передачі даних у кластері, можна здійснити розподіл обчислювальних потоків (гілок) з обчислювальних вузлів так, щоб мінімізувати накладні витрати на обмін даними між потоками і вирівняти обчислювальне навантаження між вузлами.
1. Теоретичний розділ
1.1 Матричні обчислення
Множення матриці A розміру mxn і матриці B розміру nxl призводить до отримання матриці С розміру mxl, кожен елемент якої визначається відповідно до виразу:
/
(1)
Як випливає з (1), кожен елемент результуючої матриці С є скалярний добуток відповідних рядка матриці A та стовпця матриці B:
Цей алгоритм передбачає виконання mxnxl операцій множення і стільки ж операцій додавання елементів вихідних матриць. При множенні квадратних матриць розміру nxn кількість виконаних операцій має порядок O (n3). Відомі послідовні алгоритми множення матриць, що мають меншу обчислювальну складність (наприклад, алгоритм Страса (Strassen's algorithm)), але ці алгоритми вимагають великих зусиль для їх освоєння. Далі будемо припускати, що всі матриці є квадратними і мають розмір nxn.
З визначення операції матричного множення випливає, що обчислення усіх елементів матриці С може бути виконано незалежно один від одного. Як результат, можливий підхід для організації паралельних обчислень полягає у використанні в якості базової підзадачі процедури визначення одного елемента результуючої матриці С. Для проведення всіх необхідних обчислень кожна підзадача повинна містити по одному рядку матриці А і по одному стовпцю матриці В. Загальна кількість одержуваних при такому підході підзадач виявляється рівним 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. Загальна схема передачі даних для паралельного алгоритму матричного множення при стрічковій схемі розділення даних.
1.2 Інтерфейс передачі повідомлень
MPI (англ. Message Passing Interface, Інтерфейс передачі повідомлень) — це специфікація, що була розроблена в 1993–1994 роках групою MPI Forum, і забезпечує реалізацію моделі обміну повідомленнями між процесами. У моделі програмування MPI програма породжує кілька процесів, що взаємодіють між собою за допомогою звертання до підпрограм прийому і передачі повідомлень.
Зазвичай, при ініціалізації MPI-програми створюється фіксований набір процесів, причому кожний з них виконується на своєму процесорі. У цих процесах можуть виконуватися різні програми, тому MPI-модель іноді називають MPMD-моделлю (Multiple Program, Multiple Data), на відміну від SPMD моделі, де на кожному процесорі виконуються тільки однакові задачі. MPI підтримує двохточкові і глобальні, синхронні й асинхронні, блокуючі і неблокуючі типи комунікацій. Структура комунікацій може змінюватися протягом часу життя процесу, але кількість задач повинна залишатися постійною.
Специфікація MPI забезпечує переносимість програм на рівні вихідних кодів. Підтримується робота на гетерогенних кластерах і симетричних мультипроцесорних системах. Не підтримується, як уже відзначалося, запуск процесів під час виконання MPI-програми. У специфікації відсутні опис паралельного вводу-виводу і зневадження програм — ці можливості можуть бути включені до складу конкретної реалізації MPI у виді додаткових пакетів і утиліт. Сумісність різних реалізацій не гарантується.
Важливою властивістю паралельної програми є детермінізм — програма повинна завжди давати той самий результат для того самого набору вхідних даних. Модель передачі повідомлень, загалом даною властивістю не володіє, оскільки не визначений порядок одержання повідомлень від двох процесів третім. Якщо ж один процес послідовно посилає кілька повідомлень іншому, MPI гарантує, що одержувач одержить їх саме в тому порядку, у якому вони були відправлені.
1.3 Сучасні методи та інструменти для паралельної обробки
Багатоядерне програмування для x86 процесорів складне, і часто максимальний результат приросту продуктивності досягається при переході від 1 ядра до 4 ядер, та від 4 до 16 ядер. Однак, при використанні 4 ядер, пропускна здатність пам'яті стає вузьким місцем для подальшого зростання продуктивності. Щоб використати переваги паралельних обчислень графічних процесорів, програмісти можуть просто змінити вимогливі до продуктивності частини програми і скористатися сотнями паралельних ядер GPU. Решта частина додатка не змінюється, що дозволяє найбільш ефективно використовувати всі ядра в системі. Запуск функції на GPU вимагає переписати код цієї функції та реалізувати її паралелізм, потім додати нові виклики функцій, вказавши, які саме функції будуть оброблятись на GPU і які на CPU. Завдяки цим змінам, вимогливі до продуктивності частини додатку тепер можуть виконуватись значно швидше на GPU.
Універсальні обчислення на графічних процесорах (GPGPU) є методика використання GPU, які зазвичай мають справу з обчисленнями тільки для комп'ютерної графіки, виконувати обчислення в додатках, що традиційно обробляються центральними процесорами. Це стало можливим завдяки включенню програмованих шейдерних блоків та більш високої арифметичної точності конвеєрів візуалізації, що дозволило розробникам програмного забезпечення використовувати потокові процесори задля не-графічних даних.
CUDA (англ. Compute Unified Device Architecture) - програмно-апаратна архітектура, яка дозволяє робити обчислення з використанням графічних процесорів NVIDIA, що підтримують технологію GPGPU (англ. General-Purpose computing on Graphics Processing Units) - обчислення загального призначення на графічних процесорах. Це архітектура паралельних обчислень від NVIDIA, що дозволяє істотно збільшити обчислювальну продуктивність завдяки використанню GPU (графічних процесорів).
Напрямок обчислень еволюціонує від «централізованої обробки даних» на центральному процесорі до «спільної обробки» на CPU і GPU. Для реалізації нової обчислювальної парадигми компанія NVIDIA винайшла архітектуру паралельних обчислень CUDA, на даний момент представлену в графічних процесорах GeForce, ION, Quadro, Tesla і забезпечує необхідну базу розробникам ПЗ.
1.3.1 Технологія NVIDIA® CUDA™
Єдине середовище розробки на C, яка дозволяє програмістам і розробникам писати програмне забезпечення для вирішення складних обчислювальних завдань за менший час завдяки багатоядерній обчислювальній потужності графічних процесорів. У світі вже встановлені мільйони GPU з підтримкою CUDA, і тисячі програмістів безкоштовно користуються інструментами CUDA для прискорення обчислювальних додатків - від кодування відео та аудіо до пошуків нафти і газу, моделювання геному людини, виведення тривимірних томографічних зображень і ще цілого ряду обчислювальних завдань в науково-дослідницькій та прикладній сфері. CUDA SDK дозволяє програмістам реалізовувати на спеціальному спрощеному діалекті мови програмування С алгоритми, здійснимі на графічних процесорах NVIDIA, і включати спеціальні функції в текст програми на Cі. CUDA дає розробникові можливість на свій розсуд організовувати доступ до набору інструкцій графічного прискорювача і управляти його пам'яттю, організовувати на ньому складні паралельні обчислення.
2.Розробка граф-схеми виконання множення матриць
На основі даних із таблиці 1.3. будуємо граф з’єднань процесорів:
/
Рис.2.1. Граф з’єднань у структурі процесорів
Використання усіх зв’язків між процесорами для вирішення даної задачі – недоцільне, і навіть може призвести до втрати продуктивності, тому найкраще розробити граф кільця передачі даних між процесорами (рис. 2.3). Для реалізації алгоритму перемноження матриць ми вирішили, як матриці розподілені між процесорами. Вибрано наступний тип розбиття: матриця А – стрічково-горизонтальне розбиття, матриця В - стрічково-вертикальне розбиття (рис. 2.2) для зручного множення.
/
Рис.2.2. Результат розбиття матриць
Для отримання часткових результатів на кожному з процесорів, необхідно виконувати пересилання підматриць В між процесорами. Цю дію можна виконувати по певному замкнутому кільцю. Приклад такого кола наведено на Рис.2.3.
/
Рис.2.3. Кільце передачі даних між процесорами
Оскільки завантаження початкових даних здійснюється через один процесор, який може одночасно обмінюватися даними із трьома процесорами, то необхідно виділити у структурі (рис. 2.1) певні дерева зв’язків, по яких буде проводитися завантаження початкових даних у процесори (рис. 2.4) і вивантаження часткових результатів у головний процесор (рис. 2.5).
/
Рис.2.4. Дерево завантаження вхідних даних
/
Рис.2.5. Дерево вивантаження результату
Дана структура дозволяє проводити множення над окремими частинами матриць паралельно, завдяки чому ми бачимо пришвидшення нашого алгоритму.
На рис. 2.6 наведено граф-схему виконання алгоритму перемноження двох матриць з завантаженням даних через один процесор.
Рис. 2.6 Граф-схема виконання алгоритму множення двох матриць з завантаженням даних через один процесор На граф-схемі (рис. 2.6) представлено n процесорних елементів (в нашому випадку – 8). Дані завантажуються першим процесором, який має доступ до пам’яті. Він у відповідності із деревом завантаження вхідних даних (рис. 2.4) розсилає дані всім іншим процесорам. Кожен процесор отримує свою підматрицю А та B. Після завершення розсилки даних розпочинається сам процес обчислення, під час якого обмін між процесорами відбувається по структурі зв’язків за маршрутом, вказаним на рис. 2.3. Процес множення – пересилання підматриці В повторюється 8 разів і множення її на під матриці А. Після виконання останнього перемноження розпочинається збір результатів. В результаті чого всі процесори у відповідності із деревом вивантаження (рис. 2.5) перешлють часткові результати до першого процесора, який їх складає у повну матрицю-результат (матрицю С) і записує її у пам’ять.
3. Розробка функціональної схеми
Виконання всього паралельного алгоритму можна розділити на три блоки: завантаження даних, обчислення і вивантаження.
Підчас завантаження даних із пам’яттю працює лише один процесор. Спершу він завантажує підматриці А3 і В3 і надсилає їх у процесор 5. Після цього він завантажує підматриці А і В для процесорів 7, 8 і 6, а в той же час процесор 5 передає підматриці процесора 3 до процесора 7. Процесор 2 передає завантажені частини до процесорів 5, 1 і 4, а процесор 7 передає процесору 3 його підматриці. Доки процесори 5, 1 і 4 пересилають процесорам 7, 8 і 6 їхні підматриці, процесор 2 завантажує підматриці для процесорів 5, 1 і 4. Після цього він передає завантажені підматриці до процесорів, яким вони належать і звільнившись, завантажує підматриці А2 і В2. На цьому процес завантаження завершується і розпочинається процес обчислення.
Процесори перемножують елементи матриць, які були у них попередньо завантаженні і отримують частину результату. Після обчислень відбувається пересилання підматриць В по кільцю 1→2→5→7→6→3→8→4→1. Отже, підматриця В1 пересилається з процесора 2 на процесор 1; підматриця В5 пересилається з процесора 1 на процесор 8; і т.д. Після виконання таких пересилань процесори перемнужають свої підматриці А на підматриці В які їм переслали і отримують іще одну частину результату. Такі цикли множення-пересилання повторюються 8 разів. В результаті кожен процесор перемножить свою підматрицю А на кожну підматрицю В і отримає частковий результат.
Після виконання множення і отримання часткових результатів розпочинається збирання результату і його запис в пам’ять. Відповідно до дерева вивантаження, спершу передаються часткові розв’язки від процесорів 1, 5 і 7 до процесора 2, де вони складаються у матрицю С. Із процесорів 4, 6 і 3 часткові розв’язки передаються до процесорів 1, 5 і 7. Потім із процесора 8 підматриця С вивантажується у процесор 3, а процесори 1, 5 і 7 вивантажують у процесор 2 наступну групу часткових розв’язків. Частковий розв’язок процесора 8 передається із процесора 3 у процесор 7, і нарешті передається у процесор 2, у якому після цього вже буде зібрано повний розв’язок, і він розпочне вивантаження матриці С у файл.
Цей процес зображено на функціональній схемі паралельного множення двох матриць із завантаження даних через один процесор (рис.3.1) і на схемі планування обчислень паралельного множення двох матриць із завантаженням даних через один процесор (рис.3.2).
Як видно із схеми планування обчислень, операції множення і пересилання різних процесорів на етапі обчислення виконуються паралельно на кожному процесорі. Тому час виконання кожного ярусу множення буде рівним найдовшому часу виконання множення і пересилань на ярусі.
На етапі завантаження даних, операції завантаження із пам’яті і передачі від першого процесора даних до першого ярусу дерева завантаження, виконуються послідовно, а операції передачі даних між молодшими ярусами дерева завантаження, і операції читання першим процесором з пам’яті виконуються паралельно.
На етапі збирання результатів операції пересилання від процесорів молодшого яруса дерева вивантаження до процесорів старшого яруса, відбуваються паралельно, так само як вивантаження даних із процесорів першого яруса до головного процесора. Тому час виконання блоку вивантаження буде залежати від часу виконання пересилання даних по найдовшій гілці дерева збору результату (рис. 2.5).
Рис. 3.1 Функціональна схема паралельного множення двох матриць із завантаження даних через один процесор
Рис. 3.2 Схема планування обчислень при паралельному множенні двох матриць із завантаження даних через один процесор
4. Розрахунковий розділ
Для порівняння продуктивності виконання множення при використанні паралельного та послідовного алгоритму, проведемо ряд обчислень.
Множення відбувається наступним чином: процесори перемножують відповідну підматрицю матрицю А та підматрицю B.
За заданими вхідними даними співвідношення часових параметрів згідно варіанту:
tu=10ts=6tp=5tz=7tw
4.1 Визначення розмірності підматриць
Для процесорних елементів визначимо такі розміри підматриць:
A1(30,248) – кількість елементів 7440
A2(30,248) – кількість елементів 7440
A3(30,248) – кількість елементів 7440
A4(30,248) – кількість елементів 7440
A5(30,248) – кількість елементів 7440
A6(30,248) – кількість елементів 7440
A7(30,248) – кількість елементів 7440
A8(30,248) – кількість елементів 7440
B1(248,8) – кількість елементів 1984
B2(248,8) – кількість елементів 1984
B3(248,8) – кількість елементів 1984
B4(248,8) – кількість елементів 1984
B5(248,8) – кількість елементів 1984
B6(248,9) – кількість елементів 2232
B7(248,9) – кількість елементів 2232
B8(248,9) – кількість елементів 2232
4.2 Розрахунок часу виконання послідовного алгоритму
За заданими вхідними даними виразимо тривалість всіх операцій, які виконуються, через тривалість операції вивантаження даних tw. І так маємо:
Tu = 7*tw
Ts = 7/10*tw
Tp = 7/6*tw
Tz = 7/5*tw
Час виконання операцій завантаження:
Tz=(n1*n2+n2*n3)*tz=(240*248+248*67)*tz=(59520+16616)*tz=76136*tz= = 106590,4tw;
Після того, як дані були завантаженні у один процесор, відбувається «розповсюдження» даних по інших процесорах. Найдовший шлях пересилання даних має вагу 3, найкоротший – 2. Відповідно, час початкового пересилання є:
Tпер = (2 * 30 + 3 * 30 + 2 * 9 + 3 * 8) * 248 * tp = 47616 * tp = 55552 * tw
Процесори готові до роботи, оскільки вони отримали усі необхідні їм дані. Перемноження відбувається «по кільцю», тобто: кожен процесор множить свій рядок на рядок, який приходить до нього. Виконавши операцію множення, процесор пересилає отриманий раніше рядок наступному процесору, а на вхід отримує новий, який перемножує на «свій» рядок. Таким чином маємо 7 операцій пересилання і 8 операцій множення.
Час множення (в найгіршому випадку) на одній ітерації та загальний:
Тмні = N1ч * n2 * N3ч * tu= 30 * 248 * 9 * tu = 66960 * tu = 468720 * tw,
де N1ч – найбільша частина матриці А при розбитті
N3ч – найбільша частина матриці В при розбитті
Тмн = Ttu1 + Ttu2 + ... + Ttu8 = 3749760 * tw
Час додавання (в найгіршому випадку) на одній ітерації та загальний:
Тдоді = N1ч * (n2 - 1) * N3ч* ts = 30 * 247 * 9 * ts = 66690 * ts = 46683 * tw
Тдод = Tts1 + Tts2 + ... + Tts8 = 373464 * tw
Час пересилання (в найгіршому випадку) на одній ітерації (отримання нового рядка та пересилання існуючого)
Тпер.мні = 2 * N3ч * n2 * tp = 2 * 9 * 248 * tp = 4464 * tp = 5208 * tw
Загальний час пересилання під час процесу множення (в найгіршому випадку) для кількості процесорів p1 = 8:
Тпер.мн. = Tpi * (p1 – 1) * tp = 42532 * tw
Загальний час пересилання (збору) результатів в процесор 1:
Тзб.рез = (3 * 30 + 3 * 9) * 248 * tp = 29016 * tp = 33852 * tw
Загальний час вивантаження є часом вивантаження одної результуючої матриці С з процесора 2 в пам’ять:
Tвив = n1 * n3 * tw = 240 * 67 * tw= 16080 * tw
Загальний час виконання множення матриць на паралельному алгоритмі, використовуючи дану систему:
Tпар = Tзав + Tпер + Tмн + Tдод + Tпер.мн + Tзб.рез + Tвив = (106590,4 + 55552 + 3749760 + 373464 + 36456 + 33852+ 16080) * tw = 4355674,4 * tw
Обрахунок часу виконання послідовного алгоритму множення матриць:
Загальний час множення елементів матриць:
Tпосл.мн = n1 * n2 * n3 * tu = 27914880 * tw
Загальний час додавання при обчисленні:
Tпосл.дод = n1 * n3 * (n2 – 1) * ts = 2780232* tw
Tпос = Tзав + Tпосл.мн + Tпосл.дод + Tвив = 30817782,4 * tw
Для характеристики алгоритму визначимо коефіцієнт К.
K = Tпар / (Tпер + Tмн + Tдод + Tпер.мн + Tзб.рез) = 4355674,4 / (55552 + 3749760 + 373464 + 36456 + 33852) * tw = 1.025
Обрахуємо ефективність алгоритму. Ефективність визначається як відношення часу виконання алгоритму на одно процесорній системі, до часу потрібного для виконання на багатопроцесорної системі, помноженого на кількість процесорів в ній.
E = Tпос / (Tпар * P) = 6890742,4 / (4355674,4 * 8) ≈ 0,884
5. Розробка програми
5.1 Вибір середовища
Дана програма написана на мові C++. Для розробки самого паралельного алгоритму множення матриць було обрано шлях використання інтерфейсу передачі повідомлень (МРІ) між процесами, оскільки він має наступні можливості:
створення програм багатопроцесорної обробки інформації;
велика кількість функцій для обміну повідомленнями між процесами;
синхронізація роботи процесів;
МРІ (Message Passing Interface) - програмний інтерфейс (API) для передачі інформації, який дозволяє обмінюватися повідомленнями між процесами, що виконують одну задачу. Розроблений Вільямом Гроуппом, Евін Ласко та іншими. MPI є найбільш поширеним стандартом інтерфейсу обміну даними в паралельному програмуванні, існують його реалізації для великого числа комп'ютерних платформ. Використовується при розробці програм для кластерів і суперкомп'ютерів. Основним засобом комунікації міжпроцесами в MPI є передача повідомлень один одному. Стандартизацією MPI займається MPI Forum. У стандарті MPI описаний інтерфейс передачі повідомлень, який повинен підтримуватися як на платформі, так і в додатках користувача. В даний час існує велика кількість безкоштовних і комерційних реалізацій MPI. Існують реалізації для мов Фортран 77/90, С та С++.
5.2 Опис використаних функцій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 - масив структур даних з інформацією про результат виконання операції прийому даних.
Дана функція викликається процесом-передавачем при
03.06.2014 22:06-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора