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

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

ВУЗ:
Національний університет Львівська політехніка
Інститут:
Інститут комп’ютерних технологій, автоматики та метрології
Факультет:
КН
Кафедра:
Електронні обчислювальні машини

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

Рік:
2014
Тип роботи:
Курсова робота
Предмет:
Паралельні та розподілені обчислення
Група:
КI

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

Міністерство освіти і науки України Національний університет „Львівська політехніка” Кафедра ЕОМ Курсова робота з дисципліни «Паралельні та розподілені обчислення» на тему: «Паралельне виконання операцій множення матриць» Номер залікової книжки: № 1009130 Завдання Розробити схему та описати процедуру перемноження матриці А (розмірністю N1*N2) на матрицю В (розмірністю N2*N3) на структурі з восьми процесорів. Для цієї структури визначити час виконання алгоритму, відсоток послідовної частини алгоритму та ефективність алгоритму. Веремей Юрій Олегович n1=240 , n2=264, n3=е-149 – КІ-44 Таблиця 1. Часові параметри Співвідношення часових параметрів Пояснення  tu = 10* ts час виконання однієї операції множення  ts час виконання однієї операції сумування  tp = (10/4) ts час виконання однієї операції пересилання даних між процесорами  tz = (10/3) ts час виконання операції завантаження одних даних  tW= (10/4) ts час виконання операції вивантаження одних даних  3b-6b-2b-5b-10b-13b-14b-11b – КІ-44 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22  В Е Р Е М Е Й Ю Р І Й О Л Е Г О В И Ч В Е Р   3 1  4 2    5 8  6 7           РЕЕМІЛЕЙ Буква Е дублюється тому беремо наступну вільну після неї Ю Буква Е знову дублюється тому беремо наступну після неї Г РЕЮМІЛГЙ Р = 93 = 01011101 Е = 171 = 10101011 Ю = 63 = 00111111 М = 43 = 00101011 І = 223 = 11011111 Л = 212 = 11010100 Г = 74 = 01001010 Й = 146 = 10010010 Таблиця 2. Матриця зв’язків між процесорами 1 2 3 4 5 6 7 8  1 0 1 0 1 1 1 0 1  2 1 0 1 0 1 0 1 1  3 0 0 0 1 1 1 1 1  4 0 0 1 0 1 0 1 1  5 1 1 0 1 0 1 1 1  6 1 1 0 1 0 0 0 0  7 0 1 0 0 1 0 0 0  8 1 0 0 1 0 0 1 0   Type = (i)mod3 + 1 z = 1009130 (номер залікової книжки) Type=(1+0+0+9+1+3+0)mod3+1=3 Type = 3 розподілена пам’ять. tU = (Zk-3 +1)*tS = (Zk-2 +1)*tP = (Zk-1 +1)*tZ = (Zk+1)*tW, де Zi відповідна цифра номера залікової книжки, k -кількість цифр в номері залікової книжки. Номер залікової книжки = 1009130 k=7 Tu=10*ts=2tp=4tz=1tw Анотація В даній курсовій роботі розроблено алгоритм паралельного множення двох матриць з розмірами 240х264 і 264х149. Початкові завантаження проводяться через розподілену пам’ять, тобто кожен з восьми процесорів має свою власну пам’ять і починає роботу з вже наперед поміщеними у неї підматрицями. Робота поділяється на такі етапи: проектування граф-схеми виконання алгоритму (побудова зв’язків між процесорами, кільця для обміну даними, граф-схема виконання алгоритму множення двох матриць з розподіленою пам'яттю); розробка функціональної схеми; розрахункова частина (розрахунок ефективності, часу виконання алгоритму, відсотка послідовної частини алгоритму тощо); програмна реалізація, яка включає в себе алгоритм роботи програми, його граф-схему та код програми. Програма написана на мові С++ з використанням технології MPI, оскільки вона найкраще підходить для вирішення даної задачі, і має консольний інтерфейс. Annotation In this course work was elaborated the algorithm of parallel multiplying tow matrices with dimensions 240х264 and 264х149. The initial load carried through distributed memory, that is, each of the eight processors has it’s own memory and starts with the already pre-placed in it’s submatrices. The work is divided into the following stages: designing graph-scheme of algorithm execution (construction bonds between processors, rings for data exchange, graph-scheme of execution the algorithm of multiplying two matrices with distributed memory); development of functional scheme; calculation part (calculation of efficiency, time of execution the algorithm, the percentage of sequential algorithm, etc); software implementation, which includes the algorithm of the program, it’s graph-schema and application code. The program is written in C++ using the technology of MPI, because it’s best suited to solve this problem, and a console interface. Зміст Вступ 1. Теоретичний розділ 2. Проектування граф-схеми виконання алгоритму 2.1. Зв’язки між процесорами 2.2. Пересилання даних по кільцю 2.3. Граф-схема виконання алгоритму 2.3.1 Розбиття матриці на підматриці 3. Розробка функціональної схеми 4. Розрахунковий розділ 5. Розробка програми 6. Результат виконання програми Висновки Список використаної літератури Додаток А.  7 8 12 12 12 13 14 16 18 23 25 26 27 28   Вступ Паралельні обчислювальні системи - комп'ютерні системи, що реалізовують тим або іншим способом паралельну обробку даних на багатьох обчислювальних вузлах для підвищення загальної швидкості розрахунку. Ідея розпаралелення обчислень базується на тому, що більшість завдань можуть бути розділені на набір менших завдань, які можуть бути вирішені одночасно. Зазвичай паралельні обчислення вимагають координації дій. Паралельні алгоритми досить важливі з огляду на постійне вдосконалення багатопроцесорних систем і збільшення числа ядер у сучасних процесорах. Зазвичай простіше сконструювати комп'ютер з одним швидким процесором, ніж з багатьма повільними з тією ж продуктивністю. Однак збільшення продуктивності за рахунок вдосконалення одного процесора має фізичні обмеження, такі як досягнення максимальної щільності елементів та тепловиділення. Зазначені обмеження можна подолати лише шляхом переходу до багатопроцесорної архітектури, що виявляється ефективним навіть у малих обчислювальних системах. Складність послідовних алгоритмів виявляється в обсязі використаної пам'яті та часу (число тактів процесора), необхідних для виконання алгоритму. Розподілені обчислення - спосіб розв'язання трудомістких обчислювальних завдань з використанням двох і більше комп'ютерів, об'єднаних в мережу.Розподілені обчислення є окремим випадком паралельних обчислень, тобто одночасного розв'язання різних частин одного обчислювального завдання декількома процесорами одного або кількох комп'ютерів. Тому необхідно, щоб завдання, що розв'язується було сегментоване — розділене на підзадачі, що можуть обчислюватися паралельно. При цьому для розподілених обчислень доводиться також враховувати можливу відмінність в обчислювальних ресурсах, які будуть доступні для розрахунку різних підзадач. Проте, не кожне завдання можна «розпаралелити» і прискорити його розв'язання за допомогою розподілених обчислень. Теоретичний розділ Паралельна система складається з певної кількості процесорів та модулів пам’яті. В даному випадку це структура з 8 процесорів та спільна пам’ять. Множення матриці на матрицю або матриці на вектор є базовими мікроопераціями різних задач. Для їх реалізації використовують різні алгоритми та різні структури. Для вирішення цієї задачі використовується алгоритм, при якому матриця А розбивається на 8 горизонтальних смуг, а матриця В – на 8 вертикальних, в такому разі матриця результату буде складатись з 8 горизонтальних смуг. Кожний процесор зчитує з пам’яті відповідну підматрицю А та підматрицю В. Після того як процесор помножив під матрицю А на підматрицю В, він обмінюється з іншим процесором підматрицею В. Підматриця А завжди знаходиться у відповідному процесорі, а підматриці В рухаються по всіх процесорах. Отже кожен процесор повинен помножити відповідну підматрицю А на всі підматриці В. В результаті всіх множень у пам’яті буде результуюча матриця. Однак обмін підматрицями В між процесорами відбувається не в довільному порядку. Алгоритм перемноження матриці на матрицю на кільцевій структурі: Задано дві вихідні матриці A і B. Обчислюється добуток C = А х B, де А - матриця n1 х n2, B - матриця n2 х n3. Матриця результатів C має розмір n1 х n3. Вихідні матриці попередньо розрізані на смуги, смуги записані в пам'ять. Матриця результатів повертається в нульовий процес. Реалізація алгоритму виконується на кільці з p1 процесорів. Матриці розрізані як наведено на рис. 1.1.: матриця А розрізана на p1 горизонтальних смуг, матриця B розрізана на p1 вертикальних смуг, і матриця результату C розрізана на p1 смуги. Передбачається, що в пам'ять кожного процесора завантажується і може зберігатися тільки одна смуга матриці А і одна смуга матриці B[1].    Рис. 1.1.  Схема розрізування даних для виконання паралельного алгоритму добутку двох матриць при обчисленні на кільці процесорів. Виділені смуги розміщені в пам'яті одного процесора. Оскільки за умовою в процесорах знаходиться по одній смузі матриць, то смуги матриці B (або смуги матриці A) необхідно "прокрутити" по кільцю процесорів повз смуги матриці A (матриці B). Кожний зсув смуг уздовж кільця і відповідна операція множення наведена на рис.1.2. у виді окремого кроку. На кожному з таких кроків обчислюється тільки частина смуги. Процес i обчислює на j-м кроці добуток i-й горизонтальної смуги матриці A j-ї вертикальної смуги матриці B, добуток отримується у підматриці(i,j) матриці C[1]. Обчислення відбувається в такій послідовності. 1. Кожен процесор зчитує з пам’яті відповідну йому смугу матриці А. Нульова смуга повинна зчитуватися нульовим процесором, перша смуга - першим і т.д. На рис. 1.2. смуги матриці А і B пронумеровані. 2. Кожен процесор зчитує з пам’яті відповідну йому смугу матриці B. Нульова смуга повинна зчитуватися нульовим процесором, перша смуга - першим і т.д. 3. Обчислювальний крок 1. Кожен процес обчислює одну підматрицю добутку. Вертикальні смуги матриці B зсуваються уздовж кільця процесорів. 4. Обчислювальний крок 2. Кожен процес обчислює одну підматрицю добутку. Вертикальні смуги матриці B зсуваються уздовж кільця процесорів. І т.д. 5. Обчислювальний крок p1-1. Кожен процес обчислює одну підматрицю добутку. Вертикальні смуги матриці B зсуваються уздовж кільця процесорів. 6. Обчислювальний крок p1. Кожен процес обчислює одну підматрицю добутку. Вертикальні смуги матриці B зсуваються уздовж кільця процесорів. 7. Матриця C збирається в нульовому процесорі.  1. Scatter A     2. Scatter B  7. Збір результатів у С Рис. 1.2. Стадії обчислень добутку матриць на кільцевій структурі Якщо "прокручувати" вертикальні смуги матриці B, то матриця С буде розподілена горизонтальними смугами, а якщо "прокручувати" горизонтальні смуги матриці A, то матриця С буде розподілена вертикальними смугами. Алгоритм характерний тим, що після кожного кроку обчислень здійснюється обмін даними. Нехай tu, ts, і tp час операцій, відповідно, множення, додавання і пересилання одного числа між сусідніми процесорами. Тоді загальний час виконання операцій множення: U = (n1*n2)*(n3*n2)*tu, загальний час виконання операцій додавань: S = (n1*n2)*(n3*(n2-1))*ts, загальний час виконання операцій пересилань даних по всіх процесорах: P = (n3*n2)*(p1-1)*tp. Загальний час обчислень визначимо як T = (U+S+P)/p1. Відношення часу "обчислень без обмінів" до загального часу обчислень: K = (U+S)/(U+S+P). Якщо час передачі даних великий в порівнянні з часом обчислень, або канали передачі повільні, то ефективність алгоритму буде не висока. Тут не враховується час початкового завантаження і вивантаження даних у пам'ять системи. У смугах матриць може бути різна кількість рядків, а різниця в кількості рядків між смугами - 1. В даному випадку використовуємо стрічкове розбиття. При стрічковому (block-striped) розбитті кожному процесору виділяється певна підмножина рядків (rowwise або горизонтальне розбиття) або стовпців (columnwise або вертикальне розбиття) матриці. При такому підході для горизонтального розбиття по рядках, наприклад, матриця A представляється у вигляді (1) [2] , де (1) ai = (ai1,ai2,...,ain), 0 <= i < m i-й рядок матриці A (передбачається, що кількість рядків m кратна кількості процесорів p, тобто m = k·p). Проектування граф-схеми виконання алгоритму 2.1. Зв’язки між процесорами Для ефективної роботи паралельної системи було побудовано схему пересилань даних та граф зв’язків між процесорами, їх опис, який наведений на рис. 2.1.  Рис. 2.1. Граф зв’язків між процесорами Пересилання даних по кільцю Оскільки стоїть задача розпаралелити виконання перемноження матриць, то доцільно використовувати обмін даними по кільцевій структурі, що забезпечує роботу з мінімальними затримками. Граф пересилання даних між процесорами на кільцевій структурі зображений на рис. 2.2. Пересилання між процесорами виконується у такому порядку: P3 →P8→P5→P2→P7→P4→P6→P1  Рис. 2.2. Граф пересилання даних між процесорами на кільцевій структурі Граф-схема виконання алгоритму На початку роботи алгоритму кожен процесорний елемент зчитує початкові дані, тобто підматриці А та В, які були завантажені з спільної пам’яті. Відбувається множення підматриць. Після закінчення цієї операції відбувається обмін даними підматриці В між процесорами по кільцевій структурі, яка вже була наведена на рис. 2.2. Так відбувається доти, доки підматриця В не буде перемножена на всі підматриці А. Далі відбувається поетапне виведення часткових результатів, тобто підматриць C і збір загального результату, тобто виведення матриці С у повному вигляді. На рис. 2.3. наведена граф-схема виконання алгоритму множення двох матриць з спільною пам’яттю в загальному випадку.  Рис. 2.3. Граф-схема виконання алгоритму множення двох матриць з спільною пам’яттю. 2.3.1 Розбиття матриці на підматриці Для матриць А[N1,N2] та B[N2,N3] і Р процесорів розміри підматриць Аі та Ві визначаються так. Для А та для В обчислюємо    , де С1А та С1В – ціла частина від ділення, С2А та С2В - залишки. Перші (Р - С2А) підматриці матриці А матимуть кількість рядків С1А, решту – (С1А + 1) рядків. Для матриці В, відповідно, (Р - С2В), С1В, (С1В + 1) стовпців. Визначимо розміри підматриць Аі та Ві для кожного з процесорів. , A(n1,n2) = A(240,264) B(n2,n3) = B(264,149) Розбиття матриць на підматриці: A1=(30x264) B1=(264x18) A2=(30x264) B2=(264x18) A3=(30x264) B3=(264x18) A4=(30x264) B4=(264x19) A5=(30x264) B5=(264x19) A6=(30x264) B6=(264x19) A7=(30x264) B7=(264x19) A8=(30x264) B8=(264x19) 3.Розробка функціональної схеми Результати розробки функціональної схеми наведені на рис. 3.1 Спочатку розподілені підматриці Аі та Ві записуються до розподіленої області пам’яті кожного окремого процесора, після чого система запускається на виконання. Відразу після запуску кожен з процесорів паралельно з іншими зчитує початкові дані із своєї окремої пам'яті. Загальна кількість операцій завантаження рівна сумі кількостей елементів матриць А та В: . Операція обміну підматрицями Ві.буде відбуватися паралельно. Також паралельно буде виконуватися операція звертання до памяті(оскільки в нас розподілена пам’ять) і операція множення. Відповідно до цього по заверщенні множень на кожному з процесорів буде підматриця Сі = А*Ві. Дана схема максимально показує розпаралелення виконання процесу множення матриць на 8-ми процесорах. Кожен процесор виконує моження підматриць і зберігає проміжні дані, а також обмінюється підматрицею В з сусідім процесором по кільцевій структурі. Пересилання підматриці відбувається по колу між сусідніми процесорами, причому операція відсилання і прийому даних буде виконуватись паралельно. Процесори в цьому випадку завантажені найбільш рівномірно. Процесор1 Процесор2 Процесор3 Процесор4 Процесор5 Процесор6 Процесор7 Процесор 8  Завантажен А1,B1. Завантажен А3,В3. Завантажен А4,В4. Завантажен А5,В5. Завантажен А7,В7. Завантажен А2,В2. Завантажен А6,В6. Завантажен А8,В8.  Множення А1хВ1 Множення А3ХB3 Множення А4хВ4 Множення А5хВ5 Множення А7хВ7 Множення А2хВ2 Множення А6хВ6 Множення А8хВ8  Перес.В1-P8,отрим.В8 з P8 Перес.В3-P3,отрим.В2 З P6 Перес.В4-P4,отрим.В3 З P2 Перес.В5-P7,отрим.В4 З P3 Перес.В7-P8,отрим.В6 З P8 Перес.В2-P2,отрим.В1 З P2 Перес.В6-P5,отрим.В5 З P4 Перес.В8-P1,отрим.В7 З P5  Множення А1хВ8 Множення А2хВ2 Множення А3хВ3 Множення А4хВ4 Множення А5хВ6 Множення А6хВ1 Множення А7хВ5 Множення А8хВ7  Перес.В8-P6,отрим.В7 P8 Перес.В2-P3,отрим.В1 З P6 Перес.В3-P4,отрим.В2 З P2 Перес.В4-P7,отрим.В3 З P3 Перес.В6-P8,отрим.В5 З P7 Перес.В1-P2,отрим.В8 З P1 Перес.В5-P5,отрим.В4 З P4 Перес.B7-P1,отрим.В6 З P5  Множення А1хВ7 Множення А2хВ1 Множення А3хВ2 Множення А4хВ3 Множення А5хВ5 Множення А6хВ8 Множення А7хВ4 Множення А8хВ6  Перес.В7-P6,отрим.В6 з P8 Перес.В1-P3,отрим.В8 З P6 Перес.В2-P4,отрим.В1 З P2 Перес.В3-P7,отрим.В2 З P3 Перес.В5-P8,отрим.В4 З P7 Перес.В8-P2,отрим.В7 З P1 Перес.В4-P5,отрим.В3 З P4 Перес.В6-P1,отрим.В5 З P5  Множення А1хВ6 Множення А2хВ8 Множення А3хВ1 Множення А4хВ2 Множення А5хВ4 Множення А6хВ7 Множення А7хВ3 Множення А8хВ5  Перес.В6-P6,отрим.В5 з P8 Перес.В8-P3,отрим.В7 З P6 Перес.В1-P4,отрим.В8 З P2 Перес.В2-P7,отрим.В1 З P3 Перес.В4-P8,отрим.В3 З P7 Перес.В7-P2,отрим.В6 З P1 Перес.В3-P5,отрим.В2 3 P4 Перес.В5-P1,отрим.В4 З P5  Множення А1хВ5 Множення А2хВ7 Множення А3хВ8 Множення А4хВ1 Множення А5хВ3 Множення А6хВ6 Множення А7хВ2 Множення А8хВ4  Перес.В5-P6,отрим.В4 з P8 Перес.В7-P3,отрим.В6 З P6 Перес.В8-P4,отрим.В7 З P2 Перес.В1-P7,отрим.В8 З P3 Перес.В3-P8,отрим.В2 З P7 Перес.В6-P2,отрим.В5 З P1 Перес.В2-P5,отрим.В1 З P4 Перес.В4-P1,отрим.В3 З P5  Множення А1хВ4 Множення А2хВ6 Множення А3хВ7 Множення А4хВ8 Множення А5хВ2 Множення А6хВ5 Множення А7хВ1 Множення А8хВ3  Перес.В4-P6,отрим.В3 з P8 Перес.В6-P3,отрим.В5 З P6 Перес.В7-P4,отрим.В6 З P2 Перес.В8-P7,отрим.В7 З P3 Перес.В2-P8,отрим.В1 З P7 Перес.В5-P2,отрим.В4 З P1 Перес.В8-P5,отрим.В8З P4 Перес.В3-P1,отрим.В2 З P5  Множення А1хВ3 Множення А2хВ5 Множення А3хВ6 Множення А4хВ7 Множення А5хВ1 Множення А6хВ4 Множення А7хВ8 Множення А8хВ2  Перес.В3-P6,отрим.В2 з P8 Перес.В5-P3,отрим.В4 З P6 Перес.В6-P4,отрим.В5 З P2 Перес.В7-P7,отрим.В6 З P3 Перес.В1-P8,отрим.В8 З P7 Перес.В4-P2,отрим.В3 З P1 Перес.В8-P5,отрим.В7 З P4 Перес.В2-P1,отрим.В1 З P5  Множення А1хВ2 Множення А2хВ4 Множення А3хВ5 Множення А4хВ6 Множення А5хВ8 Множення А6хВ3 Множення А7хВ7 Множення А8хВ1  Вив. С1 Перес. С2- Р1 Отрим. С7 Перес. С3- Р6 Перес. С4- Р8 Перес. С5-Р1 Перес. С6- Р1 Отрим.С3 Перес. С7- Р2 Перес. С8-Р1 Отрим.С4  Вив.(С2,С5,С6,С8) Перес. С7- Р1    Перес. С3- Р1  Перес. С4- Р1  Вив.(С3,С4,С7)         Рис 3.1 Схема планування обчислень. Розрахунковий розділ. Для процесорних елементів визначимо такі розміри підматриць: А1-8(30х264), B1-3(264х18), B4-8(264х19). Оскільки кожен процесор завантажує дані паралельно, то кількість результуючих послідовних операцій завантаження буде рівна найбільшій кількості таких операцій виконаних певним процесором. Очевидно, що найдовше завантажуватиме саме 4,7,5,6, чи 8-мий процесор, оскільки розміри їх вхідних підматриць найбільші. Отже в даному випадку кількість операцій завантаження: - для кожного процесора. Після операції завантаження початкових даних в процесори запускається цикл обробки даних, який має 8 ітерацій, які включають в себе як множення підматриць, так і пересилання даних між процесорами (підматриці Ві). Для послідовного алгоритму загальна кількість операцій множення та додавання:   Загальна кількість операцій множення та додавання на кільцевій структурі рівна: I ітерація  II ітерація   III ітерація   IV ітерація   V ітерація   VI ітерація   VII ітерація   VIII ітерація   Сумарна кількість операцій множення та додавання при опрацюванні даних на кільцевій структурі: , 1203840 ,  На семи із восьми ітераціях відбувається процес обміну підматрицями Ві між процесорами. Тут необхідні додаткові роз’яснення щодо архітектури та методів передачі приймання даних через інтерфейси обміну між процесорами. Кожен із процесорів має два інтерфейси для зв’язку з іншими процесорами, які працюють паралельно. Оскільки процесорам потрібно передати та прийняти майже однакову кількість даних, і кожен з них має вузол пам’яті однакового розміру, то процес прийому/передачі відбувається так: 1. По передньому фронту першого синхросигналу обміну в буфер інтерфейсу передачі передається значення першого елементу даних, які по спадному фронту зчитаються попереднім процесором на місце відповідного першого свого елемента. 2. По задньому фронту на місце вищезазначеного першого елемента даних через інтерфейс приймання буде записано нове значення, яке знаходиться в буфері передачі наступного процесора. 3. Пункти 1 і 2 повторяються доти доки не передадуться найбільші підматриці, при чому в останніх тактах обміну процесори які вже прийняли необхідний об’єм даних з наступного процесорного елемента не записують в свою пам'ять зайві елементи, а просто ігнорують їх. Тобто, кількість операцій обміну на кожній ітерації рівна кількості елементів найбільшої з підматриць Ві:. Тоді загальна кількість операцій обміну буде рівна сумі таких операцій на шести ітераціях:  Після виконання восьми ітерацій в пам’яті кожного з процесорів отримуємо результуючу часткову підматрицю Сі. Отже необхідно зібрати всі підмасиви Сі з кожного процесора в загальну пам'ять результуючої матриці С. Вивантаження даних відбувається в паралельному режимі. Тобто оскільки всі процесори системи під’єднані до цієї спільної пам'яті результатів через її контролер, який допускає запис в один момент тільки з одного процесора, то передача результатів відбувається почергово (вивантажує перший процесор, всі інші чекають, потім другий – всі наступні чекають, і так до сьомого). Звідси - кількість операцій вивантаження буде рівна кількості елементів результуючої матриці С розділеної на кількість процесорів р:  Для визначення точних характеристик системи врахуємо співвідношення часових параметрів (згідно з завданням). Насамперед, зведемо часи виконання різних операцій до спільного знаменника, тобто визначимо базову операцію для знаходження часів виконання інших операцій. Згідно завдання: Tu=10*ts=2tp=4tz=1tw Виразимо інші операції через найменший час Ts: , , ,  Для визначення повного часу необхідно визначити час всіх його складових, де операції виконуються послідовно (пересилання) та паралельно (завантаження, обчислення, вивантаження). При паралельному завантаженні виконується  операцій, що еквівалентно кількості операцій додавання:  Кількість операцій множення 1203840, що еквівалентно: . Кількість операцій додавань  та кількість операцій пересилань даних , що еквівалентно:  Кількість операцій вивантаження , що є еквівалентно:  Тоді загальна кількість операцій   Для порівняння обчислимо умовний час виконання послідовного алгоритму. Послідовне завантаження =(10/4)(240*264+264*149)=256740 Послідовне вивантаження =10*(240*149)= 357600  104425620 / 13631520=7,66 Порівнюючи останні результати бачимо, що перемноження однакових матриць на одному процесорі приблизно в 7,66 рази повільніше за множення на восьми процесорній системі на основі кільцевої топології. Для характеристики алгоритму визначимо коефіцієнт К, який рівний відношенню часу виконання загального алгоритму до часу виконання паралельних операцій.   Ефективність визначається як відношення часу виконання задачі на однопроцесорній системі, до часу потрібного на виконання для багатопроцесорної на кількість процесорів в ній.  5. Розробка програми Граф-схема програми наведена на рис. 5.1  Рис. 5.1. Граф-схема алгоритму перемноження матриць на заданій структурі. Завдяки тому, що при написанні коду програми були використані засоби технології MPI, дана програма не просто імітує роботу паралельноїсистеми, а дійсно є цілком працездатною і може бути запущеною на паралельній системі, яка досліджується у цій курсовій роботі. Для тестування достовірності результатів паралельної програми, я розробив ще й послідовну, де множаться ці ж матриці. Для обміну інформацією між процесами використовуються функції бібліотеки MPI 2.0 MPI_Send() та MPI_Recv(). Це парні функції, які призначені відповідно для відправки та прийому повідомлень. int MPI_Send(void *buf, int count, MPI_Datatype type, int dest, int tag, MPI_Commcomm) 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 - вказівник на структуру даних з інформацією про результат виконання операції прийому даних. Результат виконання програми Результат виконання програми наведений на рис.6.  Рис.6.1. Результат виконання програми Висновки В ході виконання курсової роботи, було виконане множення двох заданих матриць, причому множення відбувалось за певною схемою і алгоритмом. Крім цього було оцінено часові параметри роботи паралельної і послідовної програм, порівняно їх часові характеристики, які показують, що при вказаних даних матрицях А та В, паралельно множення буде виконуватись швидше ніж при послідовному. Хоча для інших задач та інших випадків можливі ситуації коли розпаралелювання результату не дасть. Для восьмипроцесорної системи та матриць з розмірами 240х264 та 264х149 умовний час виконання програми в інтервалах виконання операції додавання виявився рівним , а для послідовної машини, приблизно в 7,66 рази довше. А ефективність виявилась рівною , що є досить хорошим показником, але не ідеальним. Література Методичні вказівки до курсової роботи з дисципліни “Моделювання паралельних обчислювальних процесів” для студентів базового напрямку 6.050102 "Комп'ютерна інженерія" / Укладачі: Є. Ваврук, І. Грицик – Львів: Національний університет “Львівська політехніка”, 2012, 13 с. http://archive.nbuv.gov.ua/portal/natural/Pit/2010_1/01_006.htm - Ефективність паралельних алгоритмів обчислення матричного добутку. http://ru.wikipedia.org/wiki/Message_Passing_Interface - MPI http://www.mpiforum.org – Повний варіант описів стандартів МРІ. http://www.parallel.ru – Інформаційно-аналітичний центр з паралельних обчислень. Додаток А #include<stdio.h> #include<iostream> #include<stdlib.h> #include<iostream> #include"mpi.h" #include<Windows.h> #include<conio.h> #include<fstream> usingnamespace std; constint route=0; constint circle[] = {1,6,2,3,4,7,5,8}; constint procNumber=8; constint N1=240; constint N2=264; constint N3=149; int procRank; constint root=0; MPI_Status Status; struct A{ int row; int n1; int n2; double arr[N1/8+N1][N2]; }; struct B{ int col; int n2; int n3; double arr[N2][N3/8+N3]; }; struct R{ int n1; int n3; double arr[N1/8+N1][N3]; }; double matrixA[N1][N2]={0}; double matrixB[N2][N3]={0}; double Res[N1][N3]={0}; A subA[procNumber]; B subB[procNumber]; A procA; B procB; B procBtmp; R procRes; R result[procNumber]; int NextProc; int PrevProc; int procSize; //Збір void DataReplication(){ if(procRank==7||procRank==5||procRank==1||procRank==4){ MPI_Send(&procRes,sizeof(procRes),MPI_BYTE,root,0,MPI_COMM_WORLD); if(procRank==1){ MPI_Recv(&procRes,sizeof(procRes),MPI_BYTE,6,0,MPI_COMM_WORLD,&Status); MPI_Send(&procRes,sizeof(procRes),MPI_BYTE,root,0,MPI_COMM_WORLD); } if(procRank==7){ MPI_Recv(&procRes,sizeof(procRes),MPI_BYTE,3,0,MPI_COMM_WORLD,&Status); MPI_Send(&procRes,sizeof(procRes),MPI_BYTE,root,0,MPI_COMM_WORLD); } if(procRank==5){ MPI_Recv(&procRes,sizeof(procRes),MPI_BYTE,2,0,MPI_COMM_WORLD,&Status); MPI_Send(&procRes,sizeof(procRes),MPI_BYTE,root,0,MPI_COMM_WORLD); } }
Антиботан аватар за замовчуванням

17.03.2015 00:03-

Коментарі

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

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

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

Оголошення від адміністратора

Антиботан аватар за замовчуванням

Подякувати Студентському архіву довільною сумою

Admin

26.02.2023 12:38

Дякуємо, що користуєтесь нашим архівом!