Курсова робота з Інші. Робота № 525095

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

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

ВУЗ:

Інші

Інститут:

Не вказано

Факультет:

Не вказано

Кафедра:

Не вказано

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

Рік:

2024

Тип роботи:

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

Предмет:

Інші

Завантажити

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

Міністерство освіти і науки, молоді та спорту України Національний університет „ Львівська політехніка ” ІКТАМ Кафедра ЕОМ Курсова робота з предмету: “ Паралельні та розподілені обчислення ” на тему: “ Паралельне виконання операцій множення матриць ” Завдання Розробити структуру та описати процедуру перемноження матриці А (розмірністю N1 * N2) на матрицю В (розмірністю N2 * N3). Для вибраної структури визначити час виконання алгоритму, відсоток послідовної частини алгоритму та ефективність алгоритму для значень, які наведені нижче. Визначення вхідних даних: n1 = 120 n2=56 n3=67 5b-12b-6b-11b-8b-1b-3b-13b , де «nb»- номер букви П.І.Б. РАОПНЗДВ=> 93,27,250,219,134,67,13,203 9310 = 5D16 2710 = 1B16 25010 = FA16 21910 = DB16 13410 = 8616 6710 = 4316 132 = D16 20310 = CD16 Матриця зв’язків орієнтованого графу: №проц. 1 2 3 4 5 6 7 8 1 0 1 0 1 1 1 0 1 2 0 0 1 1 1 0 1 1 3 1 1 0 1 1 0 1 0 4 1 1 0 0 1 0 1 1 5 1 0 0 0 0 1 1 0 6 0 1 0 0 0 0 1 1 7 0 0 0 0 1 1 0 1 8 1 1 0 0 1 0 1 0 Визначення початкового завантаження: Номер – 0909624 – спільна пам’ять. Співвідношення часових параметрів: , де Zi – відповідна цифра номера залікової книжки, k – кількість цифр в номері залікової книжки. tU – час виконання однієї операції множення; tS – час виконання однієї операції сумування; tP – час виконання однієї операції пересилання даних між процесорами; tZ – час виконання операції завантаження одних даних; tW – час виконання операції вивантаження одних даних. Анотація Дана курсова робота представляє собою розробку алгоритму паралельного перемноження двох матриць розміром A(120*56) та В(56*67) на восьми процесорах використовуючи кільцеву структуру зі спільною пам’яттю. У звіті наведені функціональна схема, блок-схема виконання алгоритму, проведений розрахунок часових характеристик алгоритму, відповідно до яких визначено ефективність його виконання відносно послідовного. Програма написана засобами мови C++ з використанням бібліотеки MPI. Зміст Вступ 6 1. Теоретичний розділ 7 2. Розробка блок-схеми виконання алгоритму 9 3. Розробка функціональної схеми 10 4. Розрахунковий розділ 12 5. Розробка програми 14 Висновки 16 Список літератури 17 Додаток А. Лістинг програми 18 Вступ Паралельні обчислювальні системи - комп'ютерні системи, що реалізовують тим або іншим способом паралельну обробку даних на багатьох обчислювальних вузлах для підвищення загальної швидкості розрахунку. Ідея розпаралелення обчислень базується на тому, що більшість завдань можуть бути розділені на набір менших завдань, які можуть бути вирішені одночасно. Зазвичай паралельні обчислення вимагають координації дій. Паралельні алгоритми досить важливі з огляду на постійне вдосконалення багатопроцесорних систем і збільшення числа ядер у сучасних процесорах. Зазвичай простіше сконструювати комп'ютер з одним швидким процесором, ніж з багатьма повільними з тією ж продуктивністю. Однак збільшення продуктивності за рахунок вдосконалення одного процесора має фізичні обмеження, такі як досягнення максимальної щільності елементів та тепловиділення. Зазначені обмеження можна подолати лише шляхом переходу до багатопроцесорної архітектури, що виявляється ефективним навіть у малих обчислювальних системах. Складність послідовних алгоритмів виявляється в обсязі використаної пам'яті та часу (число тактів процесора), необхідних для виконання алгоритму. Розподілені обчислення - спосіб розв'язання трудомістких обчислювальних завдань з використанням двох і більше комп'ютерів, об'єднаних в мережу. Розподілені обчислення є окремим випадком паралельних обчислень, тобто одночасного розв'язання різних частин одного обчислювального завдання декількома процесорами одного або кількох комп'ютерів. Тому необхідно, щоб завдання, що розв'язується було сегментоване — розділене на підзадачі, що можуть обчислюватися паралельно. При цьому для розподілених обчислень доводиться також враховувати можливу відмінність в обчислювальних ресурсах, які будуть доступні для розрахунку різних підзадач. Проте, не кожне завдання можна «розпаралелити» і прискорити його розв'язання за допомогою розподілених обчислень. Теоретичний розділ Матриці та матричні операції широко використовуються при математичному моделюванні різноманітних процесів, явищ та систем. Матричні обчислення є основою великої кількості наукових та інженерних розрахунків серед прикладних областей це військова промисловість, медицина, обчислювальна математика, фізика, економіка та ін. В даному випадку в нас є 8 процесорів. Для вирішення поставленої задачі вхідні матриці розбиваємо на 8 горизонтальних смуг (матриця А) та8 вертикальних (матриця В) рис. 1. рис. 1. Розбиття вхідних матриць Кожний процесор зчитує з пам’яті відповідну підматрицю Аi та підматрицю Вi. Після того як процесор помножив під матрицю Аi на підматрицю Вi, він обмінюється з іншим процесором підматрицею Вi. Підматриця Аi завжди знаходиться у відповідному процесорі, а підматриці В рухаються по всіх процесорах. Отже кожен процесор повинен помножити відповідну підматрицю Аi на всі підматриці Вi. В результаті всіх множень у пам’яті буде результуюча матриця. Обмін підматрицями Вi між процесорами відбувається не в довільному порядку. Схема обміну відображена у графі (рис. 2). рис. 2. Граф-схема зв’язків між процесорами та пам’яттю. Із даної схеми можна отримати кільцеву структуру (рис. 3) Рис.3 – з’єднання між процесорами на кільцевій структурі. 2. Розробка блок-схеми виконання алгоритму рис. 4. Граф-схема алгоритму множення матриць Збір результатів виконання множення ( під матриць Сі ) відбувається в першому процесорі і відповідно вивантаження результуючої матриці С також відбувається з першого процесору. 3. Розробка функціональної схеми Процесор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-P2,отрим.В8 з P8 Перес.В2-P3,отрим.В1 З P1 Перес.В3-P4,отрим.В2 З P2 Перес.В4-P5,отрим.В3 З P3 Перес.В5-P6,отрим.В4 З P4 Перес.В6-P7,отрим.В5 З P5 Перес.В7-P8,отрим.В6 З P6 Перес.В8-P1,отрим.В7 З P7 Множення А1хВ8 Множення А2хВ1 Множення А3хВ2 Множення А4хВ3 Множення А5хВ4 Множення А6хВ5 Множення А7хВ6 Множення А8хВ7 Перес.В8-P2,отрим.В7 з P8 Перес.В1-P3,отрим.В8 З P1 Перес.В2-P4,отрим.В1 З P2 Перес.В3-P5,отрим.В2 З P3 Перес.В4-P6,отрим.В3 З P4 Перес.В5-P7,отрим.В4 З P5 Перес.В6-P8,отрим.В5 З P6 Перес.В7-P1,отрим.В6 З P7 Множення А1хВ7 Множення А2хВ8 Множення А3хВ1 Множення А4хВ2 Множення А5хВ3 Множення А6хВ4 Множення А7хВ5 Множення А8хВ6 Перес.В7-P2,отрим.В6 з P8 Перес.В8-P3,отрим.В7 З P1 Перес.В1-P4,отрим.В8 З P2 Перес.В2-P5,отрим.В1 З P3 Перес.В3-P6,отрим.В2 З P4 Перес.В4-P7,отрим.В3 З P5 Перес.В5-P8,отрим.В4 З P6 Перес.В6-P1,отрим.В5 З P7 Множення А1хВ6 Множення А2хВ7 Множення А3хВ8 Множення А4хВ1 Множення А5хВ2 Множення А6хВ3 Множення А7хВ4 Множення А8хВ5 Перес.В6-P2,отрим.В5 з P8 Перес.В7-P3,отрим.В6 З P1 Перес.В8-P4,отрим.В7 З P2 Перес.В1-P5,отрим.В8 З P3 Перес.В2-P6,отрим.В1 З P4 Перес.В3-P7,отрим.В2 З P5 Перес.В4-P8,отрим.В3 З P6 Перес.В5-P1,отрим.В4 З P7 Множення А1хВ5 Множення А2хВ6 Множення А3хВ7 Множення А4хВ8 Множення А5хВ1 Множення А6хВ2 Множення А7хВ3 Множення А8хВ4 Перес.В5-P2,отрим.В4 з P8 Перес.В6-P3,отрим.В5 З P1 Перес.В7-P4,отрим.В6 З P2 Перес.В8-P5,отрим.В7 З P3 Перес.В1-P6,отрим.В8 З P4 Перес.В2-P7,отрим.В1 З P5 Перес.В3-P8,отрим.В2 З P6 Перес.В4-P1,отрим.В3 З P7 Множення А1хВ4 Множення А2хВ5 Множення А3хВ6 Множення А4хВ7 Множення А5хВ8 Множення А6хВ1 Множення А7хВ2 Множення А8хВ3 Перес.В4-P2,отрим.В3 з P8 Перес.В5-P3,отрим.В4 З P1 Перес.В6-P4,отрим.В5 З P2 Перес.В7-P5,отрим.В6 З P3 Перес.В8-P6,отрим.В7 З P4 Перес.В1-P7,отрим.В8 З P5 Перес.В2-P8,отрим.В1 З P6 Перес.В3-P1,отрим.В2 З P7 Множення А1хВ3 Множення А2хВ4 Множення А3хВ5 Множення А4хВ6 Множення А5хВ7 Множення А6хВ8 Множення А7хВ1 Множення А8хВ2 Перес.В3-P2,отрим.В2 з P8 Перес.В4-P3,отрим.В3 З P1 Перес.В5-P4,отрим.В4 З P2 Перес.В6-P5,отрим.В5 З P3 Перес.В7-P6,отрим.В6 З P4 Перес.В8-P7,отрим.В7 З P5 Перес.В1-P8,отрим.В8 З P6 Перес.В2-P1,отрим.В1 З P7 Множення А1хВ2 Множення А2хВ3 Множення А3хВ4 Множення А4хВ5 Множення А5хВ6 Множення А6хВ7 Множення А7хВ8 Множення А8хВ1 Вив. С1 Перес. С2- Р3 Перес. С3- Р4 Перес. С4- Р5 Перес. С5- Р6 Перес. С6- Р7 Перес. С7- Р8 Перес. С8- Р1 Вив. С8 Перес. С2- Р4 Перес. С3- Р5 Перес. С4- Р6 Перес. С5- Р7 Перес. С6- Р8 Перес. С7- Р1 Вив. С7 Перес. С2- Р5 Перес. С3- Р6 Перес. С4- Р7 Перес. С5- Р8 Перес. С6- Р1 Вив. С6 Перес. С2- Р6 Перес. С3- Р7 Перес. С4- Р8 Перес. С5- Р1 Вив. С5 Перес. С2- Р7 Перес. С3- Р8 Перес. С4- Р1 Вив. С4 Перес. С2- Р8 Перес. С3- Р1 Вив. С3 Перес. С2- Р1 Вив. С1 рис. 5. Функціональна схема 4. Розрахунковий розділ Розміри матриць : A[120 * 56] та В[56 * 67] Розміри підматриць: A1 – A8 : [15 * 56] B1 – B 5 : [56 * 8]; B6 – В8 : [56 * 9] позначимо N1M = max(15, 15) = 15; N3M = max(8, 9) = 9. Виразимо часові параметри : ts – час виконання однієї операції сумування; – час виконання однієї операції множення; – час виконання однієї операції пересилання даних між процесорами; – час виконання операції завантаження одних даних; – час виконання операції вивантаження одних даних. Час виконання виразу буде рівний Оскільки за умовами в нас є спільна пам'ять, то звернення кожного процесору до пам'яті і завантаження даних буде виконуватися послідовно, тобто загальний час буде Оскільки розміри під матриць Аі не є однаковими, так само як розміри під матриць Ві, тому час множення буде не однаковий і виникатимуть затримки під час обміну під матрицями Ві між процесорами. Тому при підрахунку загального часу виконання операцій множення та додавання будемо використовувати найбільші значення розмірів під матиць Аі та Ві. Аналогічно максимальне значення другого виміру матриці Ві будемо використовувати для обчислення загального часу обміну даними між процесорами в тому числі і збору результату в першому процесорі. Оскільки одночасно процесор може пересилати або приймати дані, тому час обміну даними між процесорами буде проводитися в два етапи. Про те, чому саме коефіцієнт 13 використаний в даній формулі, розписано в розділі 1. Обчислюємо загальний час виконання множення матриць на даному паралельному алгоритмі: Для обчислення ефективності даного алгоритму, потрібно визначити час виконання множення даних матриць на одному процесорі. В цьому випадку, час завантаження та вивантаження даних не зміниться, пересилання і збір проводити не потрібно, тому даний час не враховується. Час виконання операцій множення та сумування обчислюється відповідно N1 * N2 * N3 * tU та N1 * (N2-1) * N3 * tS. Ефективність визначається як відношення часу виконання алгоритму на однопроцесорній системі, до часу потрібного для виконання на багатопроцесорної системі, помноженого на кількість процесорів в ній. 5. Розробка програми Програма, що реалізує поставлену в курсовій роботі задачу, написана на мові програмування С++ із використанням технології MPI. Базується на алгоритмі, блок-схема якого наведена на рис. 6. Рис. 4.2. Загальна граф-схема програми Для обміну інформацією між процесами використовуються функції бібліотеки MPI 2.0 MPI_Send() та MPI_Recv(). Це парні функції, які призначені відповідно для відправки та прийому повідомлень. Висновки Під час виконання курсової роботи я розробив паралельний алгоритм перемноження двох матриць на структурі з восьми процесорів та його програмну реалізацію. Також провів обчислення, і отримав часові характеристики даного паралельного алгоритму. Після чого порівняв його із звичайним послідовним алгоритмом, який у висновку виконується на 6,80 раз довше, ніж паралельний. Ефективність розпаралелення алгоритму виявилась рівною Е ≈ 0,85, що є досить непоганим показником, враховуючи особливість вивантаження даних у цьому алгоритмі. Програмна реалізація є повністю робочою, і може без вагань бути запущена на виконання у справжній восьмипроцесорній системі. Список літератури Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. – СПб: БХВ-Петербург, 2002. Корнеев В.В. Параллельные вычислительные системы. М.: Нолидж, 1999 http://www.parallel.ru – Інформаційно-аналітичний центр з паралельних обчислень. Додаток А. Лістинг програми #include "stdio.h" #include "stdlib.h" #include "time.h" #include "math.h" #include "mpi.h" #define AROW 120 #define ACOL 56 #define BCOL 67 #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 МБ) або завантажуй кожен файл окремо. Внесок у спільноту – це легкий спосіб допомогти іншим та отримати додаткові можливості на сайті. Твої старі роботи можуть приносити тобі нові нагороди!

поділитись

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

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

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

Коментарі

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

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

Admin

Вхід на сайт

Поскаржитися на роботу