Автор работы: Пользователь скрыл имя, 17 Января 2014 в 17:38, курсовая работа
Завдання: Розробити схему та описати процедуру перемноження матриці А (розмірністю N1*N2) на матрицю В (розмірністю N2*N3) на структурі з восьми процесорів. Для цієї структури визначити час виконання алгоритму, відсоток послідовної частини алгоритму та ефективність алгоритму.
В даній курсовій роботі проведено розробку програмної реалізації восьми процесорної паралельної системи зі розподіленою пам’яттю, яка виконує множення двох матриць розмірами А(190*88) та В(88*149).
На рис. 1.2 представлені ітерації алгоритму матричного множення для випадку, коли матриці складаються з чотирьох рядків і чотирьох стовпців. На початку обчислень в кожній підзадачі i, 0 <= i <n, розташовуються i-й рядок матриці A і i-й стовпець матриці B. В результаті їх перемножування підзадача отримує елемент Сіi результуючої матриці С. Далі підзадачі здійснюють обмін стовпцями, в ході якого кожна підзадача передає свій стовпець матриці B наступної підзадачі відповідно до кільцевої структури інформаційної взаємодії. Далі виконання описаних дій повторюється до завершення всіх ітерацій паралельного алгоритму.
Згідно з заданим варіантом будуємо структуру зв’язків між процесорами. Зв'язок між процесорами ми зобразили у вигляді графа з 8-ма вершинами.
Рис. 2.1 Граф обміну даними між процесорами
Оскільки в нас розподілена пам'ять то завантаження вхідних та вивантаження вихідних даних буде виконуватись паралельно.
Зробивши аналіз графа я прийшов до висновку що дане завдання можна розв’язати організувавши кільцеву структуру звязків між процесорами. Граф-схема кільцевої структури наведена на Рис.2.2.
Рис.2.2 Граф-схема кільцевого зв’язку між процесорами
Завантаження даних в процесори відбуваються через розподілену пам’ять. Визначемо розмірності підматриць А та В для кожного з процесорів. Для цього ми ділимо кількість рядків матриці А на кількість процесорів(в даному випадку 8) та кількість стовпців матриці В на кількість процесорів. Якщо під час виконання розподілу, не вдається отримати однакову розмірність підматриць, то розділяємо їх таким чином, щоб різниця між ними не була більша за 1.
Рис. 2.3 Розбиття матриць
Кожен процесор має свою пам'ять. На початку роботи туди буде завантажено для кожного і-го процесора під матриці Аі та Ві. Після перемноження під матриць відбудеться обмін Ві під матрицями по кільці, структура якого була показана вище. Після обміну знову відбудеться перемноження підматриць. Обмін відбуватиметься доти, доки кожен і-тий процесор не виконає множення Аі*В. Після виконання перемножень буде відбуватись збір результату в 1-ий процесор.
На рис. 2.4. наведена граф-схема виконання алгоритму множення двох матриць з розподіленою пам’яттю в загальному випадку.
Рис. 2.4. Граф-схема виконання алгоритму множення двох матриць з розподіленою пам’яттю.
Процесор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-P5,отрим.В6 з P6 |
Перес.В2-P4,отрим.В7 З P7 |
Перес.В3-P6,отрим.В8 З P8 |
Перес.В4-P8,отрим.В2 З P2 |
Перес.В5-P7,отрим.В1 З P1 |
Перес.В6-P1,отрим.В3 З P3 |
Перес.В7-P2,отрим.В5 З P5 |
Перес.В8-P3,отрим.В4 З P4 |
Множення А1хВ6 |
Множення А2хВ7 |
Множення А3хВ8 |
Множення А4хВ2 |
Множення А5хВ1 |
Множення А6хВ3 |
Множення А7хВ5 |
Множення А8хВ4 |
Перес.В6-P5,отрим.В3 P6 |
Перес.В7-P4,отрим.В5 З P5 |
Перес.В8-P6,отрим.В4 З P8 |
Перес.В2-P8,отрим.В7 З P2 |
Перес.В1-P7,отрим.В6 З P1 |
Перес.В3-P1,отрим.В8 З P3 |
Перес.В5-P2,отрим.В1 З P5 |
Перес.B4-P3,отрим.В2 З P4 |
Множення А1хВ3 |
Множення А2хВ5 |
Множення А3хВ4 |
Множення А4хВ7 |
Множення А5хВ6 |
Множення А6хВ8 |
Множення А7хВ1 |
Множення А8хВ2 |
Перес.В3-P5,отрим.В8 з P6 |
Перес.В5-P4,отрим.В1 З P7 |
Перес.В4-P6,отрим.В2 З P8 |
Перес.В7-P8,отрим.В5 З P2 |
Перес.В6-P7,отрим.В3 З P1 |
Перес.В8-P1,отрим.В4 З P3 |
Перес.В1-P2,отрим.В6 З P5 |
Перес.В2-P3,отрим.В7 З P4 |
Множення А1хВ8 |
Множення А2хВ1 |
Множення А3хВ2 |
Множення А4хВ5 |
Множення А5хВ3 |
Множення А6хВ4 |
Множення А7хВ6 |
Множення А8хВ7 |
Перес.В8-P5,отрим.В4 з P6 |
Перес.В1-P4,отрим.В1 З P7 |
Перес.В2-P6,отрим.В7 З P8 |
Перес.В5-P8,отрим.В1 З P2 |
Перес.В3-P7,отрим.В8 З P1 |
Перес.В4-P1,отрим.В2 З P3 |
Перес.В6-P2,отрим.В3 З P5 |
Перес.В7-P3,отрим.В5 З P4 |
Множення А1хВ4 |
Множення А2хВ6 |
Множення А3хВ7 |
Множення А4хВ1 |
Множення А5хВ8 |
Множення А6хВ2 |
Множення А7хВ3 |
Множення А8хВ5 |
Перес.В4-P5,отрим.В2 з P6 |
Перес.В6-P4,отрим.В3 З P7 |
Перес.В7-P6,отрим.В5 З P8 |
Перес.В1-P8,отрим.В6 З P2 |
Перес.В8-P7,отрим.В4 З P1 |
Перес.В2-P1,отрим.В7 З P3 |
Перес.В3-P2,отрим.В8 З P5 |
Перес.В5-P3,отрим.В1 З P4 |
Множення А1хВ2 |
Множення А2хВ3 |
Множення А3хВ5 |
Множення А4хВ6 |
Множення А5хВ4 |
Множення А6хВ7 |
Множення А7хВ8 |
Множення А8хВ1 |
Перес.В2-P5,отрим.В7 з P6 |
Перес.В3-P4,отрим.В8 З P7 |
Перес.В5-P6,отрим.В1 З P8 |
Перес.В6-P8,отрим.В3 З P2 |
Перес.В4-P7,отрим.В2 З P1 |
Перес.В7-P1,отрим.В5 З P3 |
Перес.В8-P2,отрим.В4 З P5 |
Перес.В1-P3,отрим.В6 З P4 |
Множення А1хВ7 |
Множення А2хВ8 |
Множення А3хВ1 |
Множення А4хВ3 |
Множення А5хВ2 |
Множення А6хВ5 |
Множення А7хВ4 |
Множення А8хВ6 |
Перес.В7-P5,отрим.В5 з P6 |
Перес.В8-P4,отрим.В4 З P7 |
Перес.В1-P6,отрим.В6 З P8 |
Перес.В3-P8,отрим.В8 З P2 |
Перес.В5-P7,отрим.В7 З P1 |
Перес.В5-P1,отрим.В1 З P3 |
Перес.В4-P2,отрим.В2 З P5 |
Перес.В6-P3,отрим.В3 З P4 |
Множення А1хВ5 |
Множення А2хВ4 |
Множення А3хВ6 |
Множення А4хВ8 |
Множення А5хВ7 |
Множення А6хВ1 |
Множення А7хВ2 |
Множення А8хВ3 |
Вив. С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 Схема планування обчислень.
Операція обміну підматрицями Ві.буде відбуватися паралельно. Також паралельно буде виконуватися операція звертання до памяті(оскільки в нас розподілена пам’ять) і операція множення.
Відповідно до цього по заверщенні множень на кожному з процесорів буде підматриця Сі = А*Ві. Дана схема максимально показує розпаралелення виконання процесу множення матриць на 8-ми процесорах.
Кожен процесор виконує моження підматриць і зберігає проміжні дані, а також обмінюється підматрицею В з сусідім процесором по кільцевій структурі. Пересилання підматриці відбувається по колу між сусідніми процесорами, причому операція відсилання і прийому даних буде виконуватись паралельно. Процесори в цьому випадку завантажені найбільш рівномірно.
4.Розрахунковий розділ
Для процесорних елементів визначимо такі розміри підматриць:
А1-A5[24,88], А6-A8[23,88], B1-B5[88, 19], B6-B8[88, 18].
Для визначення точних характеристик системи врахуємо співвідношення часових параметрів (згідно з завданням). Насамперед, зведемо часи виконання різних операцій до спільного знаменника, тобто визначимо базову операцію для знаходження часів виконання інших операцій.
Виразимо інші операції через час Tz:
TW=1/5TZ , TP =1/3TZ, TS=1/5TZ, Tu=2Tz.
Оскільки пам’ять розподілена, то це означає що завантаження буде відбуватися паралельно, а отже за час завантаження ми беремо час завантаження процесора, який виконує завантаження підматриць з більшим розміром:
TZ = (24 * 88 + 88 * 19) * tZ = 3784* tZ
Операція пересилання також буде виконуватися паралельно, а отже, обраховуємо пересилку найбільшої підматриці Ві також враховуємо, що пересилка буде відбуватися в 7 тактів:
TP = 7 * 88 * 19 * tP =11704 * tP = 3902 * tZ
Операція множення також буде виконуватися паралельно на процесорах і займе 8 тактів:
TU = TU1 +TU2 +TU3 +TU4 +TU5 +TU6 +TU7 +TU8 = 619696*tz
1 такт:
TU1= 24 * 88 * 19 * tU = 40128 * tU = 80256 * tZ
2 такт:
TU2= 24 * 88 * 19 * tU = 40128 * tU = 80256 * tZ
3 такт:
TU3= 24 * 88 * 19 * tU = 40128 * tU = 80256 * tZ
4 такт:
TU4= 24 * 88 * 19 * tU = 40128 * tU = 80256 * tZ
5 такт:
TU5= 24 * 88 * 18 * tU = 38016 * tU = 76032 * tZ
6 такт:
TU6= 23 * 88 * 19 * tU = 38456 * tU = 76912 * tZ
7 такт:
TU7= 23 * 88 * 18 * tU = 36432 * tU = 72864 * tZ
8 такт:
TU8= 23 * 88 * 18 * tU = 36432 * tU = 72864 * tZ
Час додавання також виконується паралельно:
TS = TS1 +TS2 +TS3 +TS4 +TS5 +TS6 +TS7 +TS8 = 61265,4 * tZ
1 такт:
TS = 24 * (88 - 1) * 19 * tS = 39672 * tS = 7934,4 * tZ
2 такт:
TS = 24 * (88 - 1) * 19 * tS = 39672 * tS = 7934,4 * tZ
3 такт:
TS = 24 * (88 - 1) * 19 * tS = 39672 * tS = 7934,4 * tZ
4 такт:
TS = 24 * (88 - 1) * 19 * tS = 39672 * tS = 7934,4 * tZ
5 такт:
TS = 24 * (88 - 1) * 18 * tS = 37584 * tS = 7516,8 * tZ
6 такт:
TS = 23 * (88 - 1) * 19 * tS = 38019 * tS = 7603,8 * tZ
7 такт:
TS = 23 * (88 - 1) * 18 * tS = 36018 * tS = 7203,6 * tZ
8 такт:
TS = 23 * (88 - 1) * 18 * tS = 36018 * tS = 7203,6 * tZ
Збір результату, на кожному етапі операції, що показані нище на графі де зображено вивантаження та пересилання виконуються паралельно:
Рис 4.1. Граф вивантаження та пересилання між процесорами
1-ий етап:
Вивантажуємо С1, а також пересилаємо С2, С5, С6, С8:
TW = 24 * 149 * tw = 3576 * tw = 715,2 * tZ
TP= 88 * 19 * 4 * tP = 6688* tP = 2230* tZ
2-ий етап:
Вивантажуємо С2, С5, С6, С8 та пересилаємо С3, С4, С7:
TW = 24 * 149 * 4 =14208 tw = 2841,6 * tz
TP = 88 * 19 * 3 * tP = 5016 * tP = 1672 * tZ
3-ій етап:
Вивантажуємо тільки С3, С4, С7:
TW = 24 * 149 * 3 * tw = 2145,6 * tZ
TW = 2230 + 2841,6 +2145,6 = 7212,2 * tZ
Загальний час:
Tпар= 3784 + 3902 + 619696 +61265,4 +7212,2 = 695859,6 * Z
Для порівняння обчислимо
умовний час виконання
TZпос = n1 * n2 + n2 * n3 = 29832* tZ
Пересилань не буде, тому TPпос =0.
TUпос 2491280*tu = 4982560 * tZ
TSпос = 2462970 * tS = 492594 * tZ
TWпос = 190 * 149 * tW = 28310 * tZ
TПОС = TZпос + TSпос + TWпос = 29832 +4982560 +492594 +28310 =5533296 * tZ
Ефективність: E= TПОС / (8Tпар)= 5533296 / (8 * 695859,6) = 0,99
Граф-схема програми наведена на рис. 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.1. Результат виконання множення
Під час виконання курсового проекту я оволодів технологією написання програм для багатопроцесорних систем. Розробив восьми процесорну систему з розподіленою пам’яттю множення двох матриць. Також було проведено деякі обчислення, які дають уявлення про характеристики даного паралельного алгоритму, та порівняно його з послідовним. В результаті проведеної роботи можна зробити такі висновки: для восьми процесорної системи та матриць з розмірами 190х88 88х149 умовний час виконання програми в інтервалах виконання операції виявився рівним 695859,6 tZ, а для послідовної структури 5533296 tZ . Ефективність при цьому рівна E = 99% , що є досить хорошим показником.
Информация о работе Паралельне виконання операцій множення матриць