Паралельне виконання операцій множення матриць. Курсова робота з Паралельні та розподілені обчислення . Робота № 525096

Перехід до торгівельного партнера Binance

Паралельне виконання операцій множення матриць

Інформація про навчальний заклад

ВУЗ:

Національний університет Львівська політехніка

Інститут:

Не вказано

Факультет:

Не вказано

Кафедра:

Кафедра ЕОМ

Інформація про роботу

Рік:

2013

Тип роботи:

Курсова робота

Предмет:

Паралельні та розподілені обчислення

Завантажити

Частина тексту файла (без зображень, графіків і формул):

МІНІСТЕРСТВО ОСВІТИ І НАУКИ, МОЛОДІ ТА СПОРТУ УКРАЇНИ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ „ЛЬВІВСЬКА ПОЛІТЕХНІКА” Кафедра ЕОМ Курсова робота з дисципліни: “ Паралельні та розподілені обчислення” на тему: «Паралельне виконання операцій множення матриць» Завдання Розробити структуру та описати процедуру перемноження матриці А (розмірністю n1*n2) на матрицю В (розмірністю n2*n3). Для вибраної структури визначити час виконання алгоритму, відсоток послідовної частини алгоритму та ефективність алгоритму для значень, що задані в таблиці. Розміри матриць: n1 = 200 n2 = 248 n3 = 117 Отже маємо матрицю А(250*56) та матрицю В(56*181) Вираз для структури алгоритму множення матриць: 14b-8b-1b-3b-9b-2b-11b-5b Отриманий набір букв: ЙАКПНОИЧ Декодування отриманого набору букв: Й = 14610 = 1001 0010 А = 2710 = 0001 1011 К = 4710 = 0010 1111 П = 21910 = 1101 1011 Н = 13410= 1000 0110 О = 25010= 1111 1010 И = 9110= 0101 1011 Ч = 4910= 0011 0001 Матриця зв’язків: 1 2 3 4 5 6 7 8 1 0 0 0 1 0 0 1 0 2 0 0 0 1 1 0 1 1 3 0 0 0 0 1 1 1 1 4 1 1 0 0 1 0 1 1 5 1 0 0 0 0 1 1 0 6 1 1 1 1 1 0 1 0 7 0 1 0 1 1 0 0 1 8 0 0 1 1 0 0 0 0 Табл. 1.2. Матриця зв’язків Тип початкового завантаження даних: Type = (0+9+0+9+0+4+8)mod 3 +1 = 1 (спільна пам'ять ) tU =10 tS =1 tP =5 tZ =9 tW tU - час виконання однієї операції множення; tS- час виконання однієї операції сумування; tP- час виконання однієї операції пересилання даних між процесорами; tZ - час виконання операції завантаження одних даних; tW - час виконання операції вивантаження одних даних. Анотація У даній курсовій роботі розроблено алгоритм паралельного перемноження двох матриць назаданій структурі згідно з варіантом завдання. При реалізації алгоритму програми використана технологія MPI. Визначено відсоток послідовної частини алгоритму, час його виконання. Програма написана на мові програмування С++. Зміст ВСТУП 6 1. ТЕОРЕТИЧНИЙ РОЗДІЛ 7 1.1. Масштабування і розподіл підзадач по процесорах 9 2. Аналіз (розробка) граф-схеми виконання алгоритму 11 3. Схема планування обчислень 13 4. Розрахунковий розділ 16 5. Розробка програми 18 Висновки 19 СПИСОК ЛІТЕРАТУРИ. 20 Додаток А. Лістинг програми 21 ВСТУП Паралельні обчислення — це форма обчислень, в яких кілька дій проводяться одночасно. Ґрунтуються на тому, що великі задачі можна розділити на кілька менших, кожну з яких можна розв'язати незалежно від інших. Є кілька різних рівнів паралельних обчислень: бітовий, інструкцій, даних та паралелізм задач. Паралельні обчислення застосовуються вже протягом багатьох років, в основному в високопродуктивних обчисленнях. Оскільки споживана потужність (і відповідно виділення тепла) комп'ютерами стало проблемою в останні роки, паралельне програмування стає домінуючою парадигмою в комп'ютерній архітектурі, основному в формі багатоядерних процесорів. Паралельні комп'ютери можуть бути грубо класифіковані згідно рівня, на якому апаратне забезпечення підтримує паралелізм: багатоядерність, багатопроцесорність — комп'ютери, що мають багато обчислювальних елементів в межах одної машини, а також кластери, MPP, та ґрід — системи що використовують багато комп'ютерів для роботи над одним завданням. Спеціалізовані паралельні архітектури іноді використовуються поряд з традиційними процесорами, для прискорення особливих задач. Програми для паралельних комп'ютерів писати значно складніше, ніж для послідовних, бо паралелізм додає кілька нових класів потенційних помилок, серед яких є найпоширенішоюстан гонитви. Комунікація, та синхронізація процесів зазвичай одна з найбільших перешкод для досягнення хорошої продуктивності паралельних програм. Максимальний можливий приріст продуктивності паралельної програми визначається законом Амдала. 1. ТЕОРЕТИЧНИЙ РОЗДІЛ З визначення операції матричного множення випливає, що обчислення усіх елементів матриці може бути виконано незалежно один від одного. Як результат, можливий підхід для організації паралельних обчислень полягає у використанні в якості базової підзадачі процедуру визначення одного елемента результуючої матриці. Для проведення всіх необхідних обчислень кожна підзадача повинна містити по одному рядку матриці А і одному стовпцю матриці В. Загальна кількість одержуваних при такому підході підзадач виявляється рівним n2 (по числу елементів матриці С). Для виконання всіх необхідних обчислень базової підзадачі повинні бути доступні один з рядків матриці A і всі стовпці матриці B. Просте вирішення цієї проблеми - дублювання матриці B у всіх підзадачахє, як правило, неприйнятним в силу великих витрат пам'яті для зберігання даних. Тому організація обчислень повинна бути побудована таким чином, щоб в кожний поточний момент часу підзадачі містили лише частину даних, необхідних для проведення розрахунків, а доступ до решти даних забезпечувався б за допомогою передачі даних між процесорами за певним алгоритмом. Алгоритм являє собою ітераційну процедуру, кількість ітерацій якої збігається з числом підзадач. На кожній ітерації алгоритму кожна підзадача містить по одному рядку матриці А і одному стовпцю матриці В. При виконанні ітерації проводиться скалярне множення рядків і стовпців, що призводить до отримання відповідних елементів результуючої матриці. Після завершення обчислень в кінці кожної ітерації стовпці матриці В повинні бути передані між підзадачами з тим, щоб у кожній підзадачі виявилися нові стовпці матриці В і могли бути обчислені нові елементи результуючої матриці. При цьому дана передача стовпців між підзадачами повинна бути організована таким чином, щоб після завершення ітерацій алгоритму в кожній підзадачі послідовно опинилися всі стовпці матриці В. Можлива проста схема організації необхідної послідовності передач стовпців матриці В між підзадачами. Вона полягає в представленні топології інформаційних зв'язків підзадач у вигляді кільцевої структури. У цьому випадку на кожній ітерації підзадача i, 0 <= i <n, буде передавати свій стовпець матриці В підзадачі з номером i +1 (відповідно до кільцевої структури підзадача n-1 передає свої дані підзадачі з номером 0) - див рис . 1.1. Після виконання всіх ітерацій алгоритму необхідна умова буде забезпечена - в кожній підзадачі по черзі виявляться всі стовпці матриці В. На рис. 1.1 представлені ітерації алгоритму матричного множення для випадку, коли матриці складаються з чотирьох рядків і чотирьох стовпців (n = 4). На початку обчислень в кожній підзадачі i, 0 <= i <n, розташовуються i-й рядок матриці A і i-й стовпець матриці B. В результаті їх перемножування підзадача отримує елемент cii результуючої матриці С. Далі підзадачі здійснюють обмін стовпцями, в ході якого кожна підзадача передає свій стовпець матриці B наступної підзадачі відповідно до кільцевої структури інформаційних взаємодій. Далі виконання описаних дій повторюється до завершення всіх ітерацій паралельного алгоритму. Рис. 1.1 Загальна схема передачі даних для алгоритму матричного множення при стрічковій схемі розподілення даних Процесори фізично об’єднані в топологію « кільце »(рис 1.2): Рис. 1.2 Об’єднання процесорів у топологію «кільце» 1.1. Масштабування і розподіл підзадач по процесорах Під масштабованістю розуміється здатність паралельної системи до збільшення продуктивності при збільшенні кількості процесорів. При фіксованому розмір задачі і зростанні числа процесорів – паралельна ефективність падає. При фіксованому числі процесорів і зростанні розміру задачі – паралельна ефективність зростає.Паралельний алгоритм називається масштабованим, якщо при збільшенні кількості процесорів можна збільшувати розмірність задачі так, щоб підтримати паралельну ефективність постійною. Виділені базові підзадачі характеризуються однаковою обчислювальною трудомісткістю і рівним обсягом переданих даних. Коли розмір матриць n виявляється більше, ніж число процесорів p, базові підзадачі можна укрупнити, об'єднавши в рамках однієї підзадачі кілька сусідніх рядків і стовпців перемножуваних матриць. У цьому випадку вихідна матриця A розбивається на ряд горизонтальних смуг, а матриця B представляється у вигляді набору вертикальних смуг. Розмір смуг при цьому слід вибрати рівним k = n / p (у припущенні, що n кратне p), що дозволить як і раніше забезпечити рівномірність розподілу обчислювального навантаження по процесорах, що становить багатопроцесорну обчислювальну систему. Для розподілу підзадач між процесорами може бути використаний будь-який спосіб, що забезпечує ефективне представлення кільцевої структури інформаційної взаємодії підзадач. Для цього досить, наприклад, щоб підзадачі, які є сусідніми в кільцевій топології, розташовувалися на процесорах, між якими є прямі лінії передачі даних. 2. Аналіз (розробка) граф-схеми виконання алгоритму Згідно з заданим варіантом отримуємо таку структуру зв’язків між процесорами(рис 2.1): Рис. 2.1. Граф-схема зв’язків процесорів для множення двох матриць. Структура для обміну інформацією типу кільце дозволяє систематизувати обмін між всіма процесорами і забезпечує чіткий і прозорий алгоритм обміну даними . Для спрощення обчислень на даній структурі, я виділив кільце, на основі якого буде реалізований процес обміну підматрицями В в процесі перемноження матриць А і В(рис 2.2). Рис. 2.2. Граф-схема кільцевого зв’язку між процесорами рис. 2.3. Граф-схема алгоритму множення матриць 3. Схема планування обчислень На рис. 3.1 зображена схема планування обчислень, на якій зображено такі етапи: Завантаження даних з пам’яті. Розсилка даних на процесори Ітерації обчислення зсувом частин матриці по заданій структурі. Збір результату Процесор1 Процесор2 Процесор3 Процесор4 Процесор5 Процесор6 Процесор7 Процесор 8 Завантажен А1,В1. Завантажен А2,В2. Завантажен А3,В3. Завантажен А4,В4. Завантажен А5,В5. Завантажен А6,В6. Завантажен А7,В7. Завантажен А8,В8. Множення А1хВ1 Множення А2хВ2 Множення А3хВ3 Множення А4хВ4 Множення А5хВ5 Множення А6хВ6 Множення А7хВ7 Множення А8хВ8 Перес.В1-P4,отрим.В6 з P6 Перес.В2-P8,отрим.В7 З P7 Перес.В3-P6,отрим.В8 З P8 Перес.В4-P5,отрим.В1 З P1 Перес.В5-P7,отрим.В4 З P4 Перес.В6-P1,отрим.В3 З P3 Перес.В7-P2,отрим.В5 З P5 Перес.В8-P3,отрим.В2 З P2 Множення А1хВ6 Множення А2хВ7 Множення А3хВ8 Множення А4хВ1 Множення А5хВ4 Множення А6хВ3 Множення А7хВ5 Множення А8хВ2 Перес.В6-P4,отрим.В3 з P6 Перес.В7-P8,отрим.В5 З P7 Перес.В8-P6,отрим.В2 З P8 Перес.В1-P5,отрим.В6 З P1 Перес.В4-P7,отрим.В1 З P4 Перес.В3-P1,отрим.В8 З P3 Перес.В5-P2,отрим.В4 З P5 Перес.В2-P3,отрим.В7 З P2 Множення А1хВ3 Множення А2хВ5 Множення А3хВ2 Множення А4хВ6 Множення А5хВ1 Множення А6хВ8 Множення А7хВ4 Множення А8хВ7 Перес.В3-P4,отрим.В8 з P6 Перес.В5-P8,отрим.В4 З P7 Перес.В2-P6,отрим.В7 З P8 Перес.В6-P5,отрим.В3 З P1 Перес.В1-P7,отрим.В6 З P4 Перес.В8-P1,отрим.В2 З P3 Перес.В4-P2,отрим.В1 З P5 Перес.В7-P3,отрим.В5 З P2 Множення А1хВ8 Множення А2хВ4 Множення А3хВ7 Множення А4хВ3 Множення А5хВ6 Множення А6хВ2 Множення А7хВ1 Множення А8хВ5 Перес.В8-P4,отрим.В2 з P6 Перес.В4-P8,отрим.В1 З P7 Перес.В7-P6,отрим.В5 З P8 Перес.В3-P5,отрим.В8 З P1 Перес.В6-P7,отрим.В3 З P4 Перес.В2-P1,отрим.В7 З P3 Перес.В1-P2,отрим.В6 З P5 Перес.В5-P3,отрим.В4 З P2 Множення А1хВ2 Множення А2хВ1 Множення А3хВ5 Множення А4хВ8 Множення А5хВ3 Множення А6хВ7 Множення А7хВ6 Множення А8хВ4 Перес.В2-P4,отрим.В7 з P6 Перес.В1-P8,отрим.В6 З P7 Перес.В5-P6,отрим.В4 З P8 Перес.В8-P5,отрим.В2 З P1 Перес.В3-P7,отрим.В8 З P4 Перес.В7-P1,отрим.В5 З P3 Перес.В6-P2,отрим.В3 З P5 Перес.В4-P3,отрим.В1 З P2 Множення А1хВ7 Множення А2хВ6 Множення А3хВ4 Множення А4хВ2 Множення А5хВ8 Множення А6хВ5 Множення А7хВ3 Множення А8хВ1 Перес.В7-P4,отрим.В5 з P6 Перес.В6-P8,отрим.В3 З P7 Перес.В4-P6,отрим.В1 З P8 Перес.В2-P5,отрим.В7 З P1 Перес.В8-P7,отрим.В2 З P4 Перес.В5-P1,отрим.В4 З P3 Перес.В3-P2,отрим.В8 З P5 Перес.В1-P3,отрим.В6 З P2 Множення А1хВ5 Множення А2хВ3 Множення А3хВ1 Множення А4хВ7 Множення А5хВ2 Множення А6хВ4 Множення А7хВ8 Множення А8хВ6 Перес.В5-P4,отрим.В4 з P6 Перес.В3-P8,отрим.В8 З P7 Перес.В1-P6,отрим.В6 З P8 Перес.В7-P5,отрим.В5 З P1 Перес.В2-P7,отрим.В7 З P4 Перес.В4-P1,отрим.В1 З P3 Перес.В8-P2,отрим.В2 З P5 Перес.В6-P3,отрим.В3 З P2 Множення А1хВ4 Множення А2хВ8 Множення А3хВ6 Множення А4хВ5 Множення А5хВ7 Множення А6хВ1 Множення А7хВ2 Множення А8хВ3 Пер. С1- Р4 Пер. С2- Р8 Пер. С3- Р6 Пер. С4- Р5 Пер. С5- Р7 Пер. С6- Р1 Вив.С7 Пер. С8- Р3 Пер. С6- Р4 Пер. С8- Р6 Пер. С1- Р5 Пер. С4- Р7 Пер. С3- Р1 Вив.С5 Пер. С2- Р3 Пер. С3- Р4 Пер. С2- Р6 Пер. С6- Р5 Пер. С1- Р7 Пер. С8- Р1 Вив.С4 Пер. С8- Р4 Пер. С3- Р5 Пер. С6- Р7 Пер. С2- Р1 Вив.С1 Пер. С2- Р4 Пер. С8- Р5 Пер. С3- Р7 Вив.С6 Пер. С2- Р5 Пер. С8- Р7 Вив.С3 Пер. С2- Р7 Вив.С8 Вив.С2 Рис 3.1 Схема планування обчислень. 4. Розрахунковий розділ Розміри матриць : A[200 * 248] та В[248 * 117] Розміри підматриць: A1 – A8: [25 * 248]; B1 – B 3 : [248 * 14]; B4 – В8 : [248 * 15] позначимо N1M = max(25, 25) = 25; N3M = max(14, 15) = 15. Виразимо часові параметри : ts – час виконання однієї операції сумування; – час виконання однієї операції множення; – час виконання однієї операції пересилання даних між процесорами; – час виконання операції завантаження одних даних; – час виконання операції вивантаження одних даних. Час виконання виразу буде рівний Оскільки за умовами в нас є спільна пам'ять, то звернення кожного процесору до пам'яті і завантаження даних буде виконуватися послідовно, тобто загальний час буде Оскільки розміри під матриць Аі не є однаковими, так само як розміри під матриць Ві, тому час множення буде не однаковий і виникатимуть затримки під час обміну під матрицями Ві між процесорами. Тому при підрахунку загального часу виконання операцій множення та додавання будемо використовувати найбільші значення розмірів під матиць Аі та Ві. Аналогічно максимальне значення другого виміру матриці Ві будемо використовувати для обчислення загального часу обміну даними між процесорами в тому числі і збору результату в першому процесорі. Оскільки одночасно процесор може пересилати або приймати дані, тому час обміну даними між процесорами буде проводитися в два етапи. Про те, чому саме коефіцієнт 13 використаний в даній формулі, розписано в розділі 1. Обчислюємо загальний час виконання множення матриць на даному паралельному алгоритмі: Для обчислення ефективності даного алгоритму, потрібно визначити час виконання множення даних матриць на одному процесорі. В цьому випадку, час завантаження та вивантаження даних не зміниться, пересилання і збір проводити не потрібно, тому даний час не враховується. Час виконання операцій множення та сумування обчислюється відповідно N1 * N2 * N3 * tU та N1 * (N2-1) * N3 * tS. Ефективність визначається як відношення часу виконання алгоритму на однопроцесорній системі, до часу потрібного для виконання на багатопроцесорної системі, помноженого на кількість процесорів в ній. 5. Розробка програми Програма, що реалізує поставлену в курсовій роботі задачу, написана на мові програмування С++ із використанням технології MPI. Рис.5.1 – результат виконання програми. Базується на алгоритмі, блок-схема якого наведена на рис. 5.2. Рис. 5.2. Загальна граф-схема програми Висновки Під час виконання курсової роботи я розробив паралельний алгоритм перемноження двох матриць на структурі з восьми процесорів який в 6, 83 рази швидший за послідовний. СПИСОК ЛІТЕРАТУРИ. Корнеев В.В. Параллельные вычислительные системы. М.: Нолидж, 1999 Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. – СПб: БХВ-Петербург, 2002. Ортега Дж. Введение в параллельные и векторные методы решения линейных систем. М.:Мир, 1991. Программирование на параллельных вычислительных системах: Пер с англ./Под ред. Р.Бэбба.М.:Мир, 1991. Бройнль Т. Паралельне програмування: Початковий курс: Навчальний посібник. – К.:Вища школа.,1997. Воеводин В.В. Математические основы параллельных вычислений.- М.: Изд-во МГУ, 1991. Векторизация программ: теория, методы, реализация: Пер. с англ. и нем. /Под ред. Г.Д.Чинина. - М:. Мир, 1991. Організація паралельних обчислень : Навчальний посібник з дисципліни “Паралельні та розподілені обчислення” для студентів базового напрямку 6.0915 "Комп'ютерна інженерія" / Укладачі: Є. Ваврук, О. Лашко – Львів: Національний університет “Львівська політехніка”, 2007, 70 с. http://www.parallel.ru – Інформаційно-аналітичний центр з паралельних обчислень. http://www.csa.ru – Інститут високопродуктивних обчислень і баз даних. http://www.hpc.nw.ru – Високопродуктивні обчислення. Додаток А. Лістинг програми #include "stdio.h" #include "stdlib.h" #include "time.h" #include "math.h" #include "mpi.h" #define AROW 200 #define ACOL 248 #define BCOL 117 #define MAX_VALUE 10 int proc_map(int i, int size) { size = size - 1; int r = (int) ceil( (double)AROW / (double)size); int proc = i / r; return proc + 1; } int main(int argc, char** argv) { int size, rank; MPI_Status Stat; MPI_Init(&argc, &argv); MPI_Comm_size(MPI_COMM_WORLD, &size); MPI_Comm_rank(MPI_COMM_WORLD, &rank); if (rank == 0) { int a[AROW][ACOL]; int b[ACOL][BCOL]; int c[AROW][BCOL]; /* Generating Random Values for A & B Array*/ srand(time(NULL)); for (int i=0;i<AROW;i++) { for (int j=0;j<ACOL;j++) { a[i][j] = rand() % MAX_VALUE; } } for (int i=0;i<ACOL;i++) { for (int j=0;j<BCOL;j++) { b[i][j] = rand() % MAX_VALUE; } } /* Printing the Matrix*/ printf("Matrix A :\n"); for (int i=0;i<AROW;i++) { for (int j=0;j<ACOL;j++) { printf("%3d ", a[i][j]); } printf("\n"); } printf("\nMatrix B :\n"); for (int i=0;i<ACOL;i++) { for (int j=0;j<BCOL;j++) { printf("%3d ", b[i][j]); } printf("\n"); } printf("\n"); /* (1) Sending B Values to other processes */ for (int j=1;j<size;j++) { for (int x=0;x<ACOL;x++) { MPI_Send(b[x], BCOL, MPI_INTEGER, j, 1000 + x, MPI_COMM_WORLD); } } /* (2) Sending Required A Values to specific process */ for (int i=0;i<AROW;i++) { int processor = proc_map(i, size); MPI_Send(a[i], ACOL, MPI_INTEGER, processor, (100*(i+1)), MPI_COMM_WORLD); } /* (3) Gathering the result from other processes*/ for (int i=0;i<AROW;i++) { int source_process = proc_map(i, size); MPI_Recv(c[i], BCOL, MPI_INTEGER, source_process, i, MPI_COMM_WORLD, &Stat); } /* Printing the Result */ printf("\nMatrix C :\n"); for (int i=0;i<AROW;i++) { for (int x=0;x<BCOL;x++) { printf("%3d ", c[i][x]); } printf("\n"); } } else { int b[ACOL][BCOL]; /* (1) Each process get B Values from Master */ for (int x=0;x<ACOL;x++) { MPI_Recv(b[x], BCOL, MPI_INTEGER, 0, 1000 + x, MPI_COMM_WORLD, &Stat); } /* (2) Get Required A Values from Master then Compute the result */ for (int i=0;i<AROW;i++) { int c[BCOL]; int processor = proc_map(i, size); if (rank == processor) { int buffer[ACOL]; MPI_Recv(buffer, ACOL, MPI_INTEGER, 0, (100*(i+1)), MPI_COMM_WORLD, &Stat); for (int j=0;j<BCOL;j++) { int sum = 0; for (int z=0;z<ACOL;z++) { sum = sum + (buffer[z] * b[z][j] ); } c[j] = sum; } MPI_Send(c, BCOL, MPI_INTEGER, 0, i, MPI_COMM_WORLD); } } } MPI_Finalize(); return 0; }

Курсова робота Паралельні та розподілені обчислення

woyna666

19.11.2013 20:11-

Коментарі

Ви не можете залишити коментар. Для цього, будь ласка, або зареєструйтесь.

Ділись своїми роботами та отримуй миттєві бонуси!

Маєш корисні навчальні матеріали, які припадають пилом на твоєму комп'ютері? Розрахункові, лабораторні, практичні чи контрольні роботи — завантажуй їх прямо зараз і одразу отримуй бали на свій рахунок! Заархівуй всі файли в один .zip (до 100 МБ) або завантажуй кожен файл окремо. Внесок у спільноту – це легкий спосіб допомогти іншим та отримати додаткові можливості на сайті. Твої старі роботи можуть приносити тобі нові нагороди!

поділитись