Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Паралельне виконання операцій множення матриць
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
КН
Кафедра:
Кафедра ЕОМ
Інформація про роботу
Рік:
2011
Тип роботи:
Курсова робота
Предмет:
Паралельні та розподілені обчислення
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ І НАУКИ, МОЛОДІ ТА СПОРТУ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ „ЛЬВІВСЬКА ПОЛІТЕХНІКА”
Кафедра ЕОМ
Курсова робота
з дисципліни: “ Паралельні та розподілені обчислення”
на тему:
«Паралельне виконання операцій множення матриць»
Завдання
Задаються дві матриці А (розмірністю n1*n2) та В (розмірністю n2*n3) :
n1=5Б , n2=3П, n3=2І – КІ-44
де nП, nБ та nІ номер букви в прізвищі, імені та по-батькові відповідно.
ПІБ: Новосад Олег Євгенович;
Група: КІ – 44:
n1=5Б – Н = 230
n2=3П – В = 56
n3=2І – Л = 325
Отже маємо матрицю А(230*56) та матрицю В(56*325)
Розробити та описати алгоритм множення матриць А*В на структурі, яка задається виразом:
3b – 6b – 2b – 5b – 10b – 13b – 14b – 11b
де «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
Отримаємо – ВАОСЕВГГ ( ВАОСЕГГГ ( ВАОСЕНГГ ( ВАОСЕНГЄ
Для ВАОСЕНГЄ отримаємо наступні значення, які записуємо у стовпець і переводимо у двійкове 8-ми розрядне число, а в отриманій двійковій матриці одиниці що розташовані на головній діагоналі замінюємо на 0.
В = 20310 = 110010112 11001011 01001011
А = 2710 = 000110112 00011011 00011011
О = 25010 = 111110102 11111010 11011010
С = 8210 = 010100102 01010010 01000010
Е = 17110 = 101010112 10101011 => 10100011
Н = 13410 = 100001102 10000110 10000010
Г = 7410 = 010010102 01001010 01001100
Є = 3410 = 001000102 00100010 00100010
Згідно варіанту, 6 стовбець не містив в собі ‘1’, що заважало б коректному вирішенню поставленого завдання. З викладачем було узгоджено, що в цьому стовбці на позиції 6 біта (відлік йде зверху) поставити ‘1’ (ця одиниця виділена жирним накресленням).
Отримана матриця розміру 8*8 є матрицею зв’язків орієнтованого графу, вершини якого це процесори, а напрямлені дуги це напрямлені лінії зв’язку між процесорами. На основі цієї матриці будується відповідний їй граф що характеризує певну 8-ми процесорну систему (структуру) із направленими зв’язками між вершинами.
3. Для цієї структури визначити час виконання алгоритму, відсоток послідовної частини алгоритму та ефективність алгоритму для значень, співвідношення часових параметрів та тип початкового завантаження визначаються за правилами:
3.1. Тип початкового завантаження даних type:
Номер залікової книжки: 0809083
type = (0+8+0+9+0+8+3) = 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 -кількість цифр в номері залікової книжки.
K = 7
tU=(9 +1)tS=(0 +1)tP=(8 +1)tZ=(3+1)tW
tU=4tW
tS=10/tw
tP=1/tw
tZ=9/tw
Анотація
Дана курсова робота полягає в розробці алгоритму перемноження матриць на 8 процесорах, при чому доступ до даних в пам’яті здійснюється один процесор. В курсовій наведена граф-схема виконання алгоритму множення двох матриць на кільцевій структурі, граф-схема зв’язків, графи пересилань даних, програмна реалізація алгоритму і проведені розрахунки часу виконання та ефективності.
Програмна реалізація курсової роботи виконана у середовищі Microsoft Visual Studio 2010 на мові С з використанням бібліотек MPI (Message Passing Interface) і має консольний інтерфейс.
Annotation
The matrix multiplication algorithm for 8 processors was developed in this course work. The accesses to the data in the memory may take place through the one processor. In the exchange rate is shown graph-scheme of the algorithm for multiplying two matrices in a ring structure, the graph-scheme of relations, graphs of data transfers, algorithm software implementation and calculations of time and efficiency.
Algorithm software implementation of the course work was done in a Microsoft Visual Studio 2010 environment, using C programming language and the MPI (Message Passing Interface) library. Program has a console interface. Зміст
Вступ 7
1. Теоретичний розділ 8
2. Проектування граф-схеми виконання алгоритму 13
3. Розробка функціональної схеми 17
4. Розрахунковий розділ 19
5. Розробка програми 21
Висновки 22
Література 23
Вступ
З недавніх пір електронно-обчислювальні машини міцно і надовго увійшли в життя кожної окремо взятої людини. Саме ці пристрої є головними помічниками людей у розв'язанні проблем у різних життєвих сферах. Застосування цього чуда техніки підвищує ефективність і якість планування та управління виробництвом, розробки складних технічних пристроїв, освіти тощо. З розвитком науки і техніки кількість завдань, які вирішуються складно невпинно зростає. Для вирішення багатьох з них можливостей звичайних комп'ютерів зазвичай недостатньо. Такі сфери науки як моделювання клімату, генна інженерія, проектування інтегральних схем, створення лікарських препаратів вимагає продуктивності обчислювальної техніки.
Довгий час вирішення цієї важливою проблеми не давало спокою науковцям з цілого світу. У підсумку, було вирішено прискорювати вирішення обчислювальних завдань за допомогою паралельних обчислень. Під паралельними обчисленнями розуміють виконання декількох обчислень в один і той же час на різних процесорах. Алгоритми, які використовуються, розділяються на інформаційно-незалежні частини. Кожен з цих фрагментів виконується на окремому процесорі. В нашому випадку використання структур паралельної обробки даних, а саме, кільцева, 2D (решітка), 3D (куб), значно прискорює процес розпаралелення та розподіленого обчислення задачі між процесорами.
Теоретичний розділ
Матриця — математичний об'єкт, записаний у вигляді прямокутної таблиці чисел (чи елементів кільця) і допускаючий операції (додавання, віднімання, множення та множення на скаляр). Зазвичай матриці представляються двовимірними (прямокутними) таблицями. Іноді розглядають багатовимірні матриці або матриці непрямокутної форми. В даній статті вони розглядатися не будуть.
Матриці є корисними для запису даних, що залежать від двох категорій, наприклад: для коефіцієнтів систем лінійних рівнянь та лінійних перетворень.
Горизонтальні лінії в матриці звуть рядками, вертикальні — стовпцями.
Матрицю, що складається з m рядків та n стовпців, називають матрицею m-на-n (або mn-матрицею), а m і n — її розмірністю.
Елемент матриці A, що знаходиться на перетині i-го рядка з j-им стовпчиком, називають i,j-им елементом або (i,j)-им елементом A.
Записують це як Ai,j чи A[i,j], або, в нотації мови програмування C, A[i][j].
Часто пишуть для означення матриці A розмірності n x m, де кожен елемент матриці A[i,j] позначають як aij для всіх 1 ≤ i ≤ n та 1 ≤ j ≤ m.
Приклад
Матриця є матрицею 4×3. Елемент A[2,3], або a2,3 дорівнює 7.
Множення матриці на вектор і матриці на матрицю є базовими макроопераціями для багатьох задач. Для їх реалізації використовуються різні алгоритми та різні структури. Розмаїтість варіантів алгоритмів виникає із-за розмаїтості обчислювальних систем і розмаїтості розмірів задач. Стандартний алгоритм множення матриці на матрицю:
Множення двох матриць має сенс лише тоді, коли число стовпчиків першої матриці дорівнює числу рядків другої матриці. Якщо A — матриця m-на-n (m рядків, n стовпчиків), а B — матриця n-на-p (n рядків, p стовпчиків), їх добуток AB є матрицею m-на-p (m рядків, p стовпчиків), що розраховується за формулою:
(AB)[i, j] = A[i, 1] * B[1, j] + A[i, 2] * B[2, j] + ... + A[i, n] * B[n, j] для кожної пари i та j.
Наприклад,
Це множення має такі властивості:
(AB)C = A(BC) для всіх матриць A розмірності k-на-m, B розмірності m-на-n і C розмірності n-на-p (асоціативність).
(A + B)C = AC + BC для всіх матриць A і B розмірності m-на-n і матриць C розмірності n-на-k (дистрибутивність).
C(A + B) = CA + CB для всіх матриць A і B розмірності m-на-n і матриць C розмірності k-на-m (дистрибутивність).
Зауваження: комутативність має місце не завжди: для добутку певних матриць A і B може бути AB ≠ BA.
Матриці називають антикомутативними, якщо AB = −BA. Такі матриці є дуже важливими в представленнях алгебр Лі та в представленнях алгебр Кліффорда.
Розглядаються і різні варіанти завантаження даних у систему: завантаження даних через один з процесорів, завантаження даних безпосередньо кожним процесором з розподіленої пам'яті, завантаження даних з спільної пам'яті. Якщо завантаження даних здійснюється через один з процесорів, то дані зчитуються цим процесором з пам'яті, розрізаються на частини, які розсилаються іншим процесорам. Але дані можуть бути підготовлені і заздалегідь, тобто заздалегідь розрізані вроздріб і кожна частина записана в окрему пам'ять, потім кожен процесор безпосередньо зчитує з пам'яті призначений для нього файл.
Алгоритм перемноження матриці на матрицю на кільцевій структурі
Задано дві вихідні матриці A і B. Обчислюється добуток C = А х B, де А - матриця n1 х n2, B - матриця n2 х n3. Матриця результатів C має розмір n1 х n3. Вихідні матриці попередньо розрізані на смуги, ці смуги записані в пам'ять. Матриця результатів повертається в нульовий процес. Реалізація алгоритму виконується на кільці з p1 процесорів. Матриці розрізані як наведено на рис. 1.1: матриця А розрізана на p1 горизонтальних смуг, матриця B розрізана на p1 вертикальних смуг, і матриця результату C розрізана на p1 смуги. Передбачається, що в пам'ять кожного процесора завантажується і може зберігатися тільки одна смуга матриці А і одна смуга матриці B.
Рис.1.1. Методи розрізування даних для виконання паралельного алгоритму добутку двох матриць при обчисленні на кільці процесорів. Виділені смуги розміщення в пам’яті одного процесора.
Дані можуть бути підготовлені і заздалегідь, тобто заздалегідь розрізані вроздріб і кожна частина записана на диск у виді окремого файлу зі своїм ім'ям; потім кожен комп'ютер безпосередньо зчитує з диску, призначений для нього файл. Вихідні матриці попередньо розрізані на смуги, смуги записані на дискову пам'ять окремими файлами зі своїми іменами і доступні всім комп'ютерам. Матриця результатів повертається в нульовий процес. Нижче подані схеми виконання перемноження матриць на кільцевій структурі (для обох випадків: коли пересилаються стовбці матриці А або, коли пересилаються рядки матриці В)
Рис. 1.2а. Схема множення матриць на кільцевій структурі (пересилання стовбців матриці А)
Рис. 1.2б. Схема множення матриць на кільцевій структурі (пересилання рядків матриці В)
Оскільки за умовою в процесорах знаходиться по одній смузі матриць, то смуги матриці B (або смуги матриці A) необхідно "прокрутити" по кільцю процесорів повз смуги матриці A (матриці B). Кожний зсув смуг уздовж кільця і відповідна операція множення наведена на рис.1.2 у виді окремого кроку. На кожному з таких кроків обчислюється тільки частина смуги. Процес i обчислює на j-м кроці добуток i-й горизонтальної смуги матриці A j-ї вертикальної смуги матриці B, добуток отримується у підматриці(i,j) матриці C.
Обчислення відбувається в такій послідовності:
Кожен процесор зчитує з пам’яті відповідну йому смугу матриці А. Нульова смуга повинна зчитуватися нульовим процесором, перша смуга - першим і т.д.
Кожен процесор зчитує з пам’яті відповідну йому смугу матриці B. Нульова смуга повинна зчитуватися нульовим процесором, перша смуга - першим і т.д.
Обчислювальний крок 1. Кожен процес обчислює одну підматрицю добутку. Вертикальні смуги матриці B зсуваються уздовж кільця процесорів і т.д. до обчислювального кроку p1.
Обчислювальний крок p1. Кожен процес обчислює одну підматрицю добутку. Вертикальні смуги матриці B зсуваються уздовж кільця процесорів.
Матриця C збирається в нульовому процесорі.
Якщо "прокручувати" вертикальні смуги матриці B, то матриця С буде розподілена горизонтальними смугами, а якщо "прокручувати" горизонтальні смуги матриці A, то матриця С буде розподілена вертикальними смугами.
Алгоритм характерний тим, що після кожного кроку обчислень здійснюється обмін даними
Якщо час передачі даних великий в порівнянні з часом обчислень, або канали передачі повільні, то ефективність алгоритму буде невисока.
2. Проектування граф-схеми виконання алгоритму
На рис. 2.1. наведена схема зв’язків між процесорами системи.
Рис.2.1. Граф 8-процесорної системи.
Рис.2.2. Розбиття матриці між процесорами.
Завантаження і вивантаження даних відбувається через 1 процесор. Було вибрано процесор №7, оскільки цей процесор містить найбільшу кількість входів (7), отже будь-який інший процесор зможе легко в нього переслати свої результати роботи – через нього буде здійснюватися доступ до пам’яті. Цей процесор буде проводити розподіл даних між іншими процесорами і в нього в результаті збиратимуться усі обраховані дані з різних процесорів. Процесор може завантажувати чи вивантажувати до 3 смуг матриці одночасно. Штриховою лінією позначений прямий зв’язок процесора №8 з процесором №7.
Процедура завантаження та початкового пересилання: спочатку процесор №7 завантажує по 3 смуги кожної матриці для процесорів №4, №1 та №3, передає ці смуги відповідно процесорам №2, №6 та №5. Далі, процесор №7 знову завантажує по 3 смуги кожної матриці, в цей час процесори №2, №6 та №5 передають дані адресовані процесорам №4, №1 та №3 відповідно. Наступним кроком процесор №7 передає дані для процесорів №2, №6 та №5. Потім він завантажує останні 2 смуги, по смузі з кожної матриці залишає собі і решту передає процесору №8.
Рис.2.3. Граф пересилання даних.
На кожному з ярусів вибирається операція, яка буде виконуватись найдовше, аби синхронізувати кожен етап обчислення на процесорах.
Рис.2.4. Граф збору даних.
Після кожного множення виконується зсув смуг матриці B по кільцю, яке зображене на рис.2.5.
Процедура вивантаження результуючих даних: процесори №4, №5 та №1 передають свої результати процесору №7. Далі процесор №8 передає свій результат процесору №7, а в цей час процесори №3, №2 та №6 передають обраховані дані процесорам №4, №5 та №1 відповідно. Останнім кроком процесори №4, №5 та №1 пересилають процесору №7 результати обрахунків процесорів №3, №2 та №6.
Рис.2.5. Кільцева структура заданої 8-процесорної систем (граф системи на рис. 2.2.)
// розробити граф-схему алгоритму
Розробка функціональної схеми
Розрахунковий розділ
Для процесорних елементів визначимо такі розміри підматриць:
A0- A1- 28*56 B0-B2 – 56*40
A2- A7- 29*56 B3-B7 – 56*41
Розбиття матриці А(230x56) на підматриці для кожного процессора
№
Рядків
Стовбців
0
28
56
1
28
56
2
29
56
3
29
56
4
29
56
5
29
56
6
29
56
7
29
56
Розбиття матриці В(56*325) на підматриці для кожного процесора:
№
Рядків
Стовбців
0
56
40
1
56
40
2
56
40
3
56
41
4
56
41
5
56
41
6
56
41
7
56
41
tU = 10tS = tP = 9tz = 4tw
tU = 4 * tw
tS = 4/10 * tw
tP = 4 * tw
tz = 4/9 * tw
Згідно із завданням, елементи завантажуються через один процесор (type = 2). Вибраний процесор №7. Отже, кількість послідовних операцій завантаження буде рівна числу звертань процесорів до пам’яті.
Nзав = (n1 * n2 + n2 * n3) = 230 * 56 + 56 * 325 = 12880 + 18200 = 31080 – кількість звертань до пам’яті при отриманні обидвох матриць. Для отримання часу завантаження матриць в процесор, виразимо Nзав через tw (згідно значень, поданих вище). Звідси, час завантаження матриць:
Tзав = ((n1 * n2 + n2 * n3) * tz = (230 * 56 + 56 * 325) * tz = (12880 + 18200) * tz = 31080 * tz = 13813 * tw
Після того, як дані були завантаженні у один процесор, відбувається «розповсюдження» даних по інших процесорах. Найдовший шлях пересилання даних має вагу 3, найкоротший – 2. Відповідно, час початкового пересилання є:
Tпер = (2 * 28 + 3 * 29 + 2 * 40 + 3 * 41) * 56 * tp = 19376 * tp = 77504 * tw
Процесори готові до роботи, оскільки вони отримали усі необхідні їм дані. Перемноження відбувається «по кільцю», тобто: кожен процесор множить свій рядок на рядок, який приходить до нього (включаючи отримані дані при початковому пересиланні). Виконавши операцію множення, процесор пересилає отриманий раніше рядок наступному процесору, а на вхід отримує новий, який перемножує на «свій» рядок. Таким чином маємо 7 операцій пересилання (коли на вхід процесора приходять дані, які були на початковому розповсюдженню значень, пересилка не виконується) і 8 операцій множення.
Час множення (в найгіршому випадку) на одній ітерації та загальний:
Тмні = N1ч * n2 * N3ч * tu= 29 * 56 * 41 * tu = 66584 * tu = 266336 * tw,
де N1ч – найбільша частина матриці А при розбитті
N3ч – найбільша частина матриці В при розбитті
Тмн = Ttu1 + Ttu2 + ... + Ttu8 = 2130688 * tw
Час додавання (в найгіршому випадку) на одній ітерації та загальний:
Тдоді = N1ч * (n2 - 1) * N3ч* ts = 29 * 55 * 41 * ts = 65395 * ts = 26158 * tw
Тдод = Tts1 + Tts2 + ... + Tts8 = 209264 * tw
Час пересилання (в найгіршому випадку) на одній ітерації (отримання нового рядка та пересилання існуючого)
Тпер.мні = 2 * N3ч * n2 * tp = 2 * 41 * 56 * tp = 4592 * tp = 18368 * tw
Загальний час пересилання під час процесу множення (в найгіршому випадку) для кількості процесорів p1 = 8:
Тпер.мн. = Tpi * (p1 – 1) * tp = 128576 * tw
Загальний час пересилання (збору) результатів в процесор 7:
Тзб.рез = (3 * 29 + 3 * 41) * 56 * tp = 11760 * tp = 47040 * tw
Загальний час вивантаження є часом вивантаження одної результуючої матриці С з процесора 7 в пам’ять:
Tвив = n1 * n3 * tw = 230 * 325 * tw= 74750 * tw
Загальний час виконання множення матриць на паралельному алгоритмі, використовуючи дану систему:
Tпар = Tзав + Tпер + Tмн + Tдод + Tпер.мн + Tзб.рез + Tвив = (13813 + 77504 + 2130688 + 209264 + 128576 + 47040 + 74750) * tw = 2681635 * tw
Обрахунок часу виконання послідовного алгоритму множення матриць:
Загальний час множення елементів матриць:
Tпосл.мн = n1 * n2 * n3 * tu = 16744000 * tw
Загальний час додавання при обчисленні:
Tпосл.дод = n1 * n3 * (n2 – 1) * ts = 1644500 * tw
Tпос = Tзав + Tпосл.мн + Tпосл.дод + Tвив = 18477063 * tw
Відношення часу обчислень послідовного і паралельного алгоритмів:
N = Tпос / Tпар = 6,89.
Для характеристики алгоритму визначимо коефіцієнт К, який рівний відношенню часу виконання загального алгоритму до часу виконання паралельних операцій.,
K = Tпар / (Tпер + Tмн + Tдод + Tпер.мн + Tзб.рез) = 2681635 / (77504 + 2130688 + 209264 + 128576 + 47040) * tw = 1.034
Обрахуємо ефективність алгоритму. Ефективність визначається як відношення часу виконання алгоритму на одно процесорній системі, до часу потрібного для виконання на багатопроцесорної системі, помноженого на кількість процесорів в ній.
E = Tпос / (Tпар * P) = 18477063 / (2681635 * 8) ≈ 0,86
Розробка програми
Висновки
Під час виконання цієї курсової роботи я розробив паралельний алгоритм перемноження матриці на матрицю на заданій структурі. Також було проведено деякі обчислення, які дають уявлення про характеристики даного паралельного алгоритму та порівняння його із звичайним послідовним алгоритмом. В результаті проведеної роботи можна зробити наступні висновки. Для алгоритму, реалізованого на даній структурі та матриць розмірності 230x56 і 56x325, умовний час виконання в інтервалах виконання операції завантаження виявився рівним Т = 2681635 * tw, а для послідовного алгоритму – TПОС = 18477063 * tw, що приблизно в 7 раз довше. Ефективність розпаралелення виявилась рівною Е ≈ 0,86, що є високим показником, який забезпечується кількістю 8 робочих процесорів та досить великим об’ємом даних.
Розроблений у цій курсовій роботі паралельний алгоритм є ефективним та може використовуватись, коли немає жорстких обмежень щодо ефективності використання пам’яті (наприклад, таких як недопустимість дублювання вхідних даних).
Література
http://www.intuit.ru/department/calculate/paralltp/5/9.html – Теорія і практика паралельних обчислень
Організація паралельних обчислень: Навчальний посібник з дисципліни “Паралельні та розподілені обчислення” для студентів базового напрямку 6.0915 "Комп'ютерна інженерія" / Укладачі: Є. Ваврук, О. Лашко – Львів: Національний університет “Львівська політехніка”, 2007, 70 с.
http://www.mpiforum.org – Повний варіант описів стандартів МРІ.
Бройнль Т. Паралельне програмування: Початковий курс: Навчальний посібник. – К.:Вища школа.,1997.
http://www.parallel.ru – Інформаційно-аналітичний центр з паралельних обчислень.
http://www.csa.ru – Інститут високопродуктивних обчислень і баз даних.
http://www.hpc.nw.ru – Високопродуктивні обчислення.
Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. – СПб: БХВ-Петербург, 2002.
Воеводин В.В. Математические основы параллельных вычислений.- М.: Изд-во МГУ, 1991.
06.03.2013 23:03-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора