Паралельне виконання операцій множення матриць
Міністерство освіти і науки України
Національний університет “Львівська політехніка”
Кафедра ЕОМ
КУРСОВА РОБОТА
з дисципліни:
«Паралельні та розподілені обчислення»
на тему:
«Паралельне виконання операцій множення матриць»
Залікова книжка № 1009546
Виконав: ст.гр.КІ-42
Кухар Б.І.
Перевірив: Грос В.В.
Львів
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™.........................
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), кожен
елемент результуючої матриці С
є скалярний добуток
Цей алгоритм передбачає виконання 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 забезпечує переносимість
програм на рівні вихідних кодів.
Підтримується робота на гетерогенних
кластерах і симетричних
Важливою властивістю
1.3 Сучасні методи
та інструменти для
Багатоядерне програмування
для x86 процесорів складне, і часто
максимальний результат приросту продуктивності
досягається при переході від 1 ядра
до 4 ядер, та від 4 до 16 ядер. Однак, при
використанні 4 ядер, пропускна здатність
пам'яті стає вузьким місцем для
подальшого зростання продуктивності.
Щоб використати переваги паралельних
обчислень графічних
Універсальні обчислення
на графічних процесорах (GPGPU) є методика
використання GPU, які зазвичай мають
справу з обчисленнями тільки для
комп'ютерної графіки, виконувати обчислення
в додатках, що традиційно обробляються
центральними процесорами. Це стало
можливим завдяки включенню
CUDA (англ. Compute Unified Device Architecture)
- програмно-апаратна
Напрямок обчислень
1.3.1 Технологія NVIDIA® CUDA™
Єдине середовище розробки
на C, яка дозволяє програмістам і
розробникам писати програмне забезпечення
для вирішення складних обчислювальних
завдань за менший час завдяки
багатоядерній обчислювальній потужності
графічних процесорів. У світі
вже встановлені мільйони GPU з
підтримкою CUDA, і тисячі програмістів
безкоштовно користуються інструментами
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 разів. В результаті кожен процесор перемножить свою підматрицю А на кожну підматрицю В і отримає частковий результат.
Після виконання множення
і отримання часткових
Цей процес зображено на функціональній схемі паралельного множення двох матриць із завантаження даних через один процесор (рис.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+
= 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
Обрахуємо ефективність алгоритму. Ефективність визначається як відношення часу виконання алгоритму на одно процесорній системі, до часу потрібного для виконання на багатопроцесорної системі, помноженого на кількість процесорів в ній.