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

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

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

ВУЗ:

Інші

Інститут:

Не вказано

Факультет:

Не вказано

Кафедра:

Не вказано

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

Рік:

2024

Тип роботи:

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

Предмет:

Інші

Завантажити

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

Міністерство освіти і науки, молоді та спорту України Національний університет „ Львівська політехніка ” ІКТАМ Кафедра ЕОМ Курсова робота з предмету: “ Паралельні та розподілені обчислення ” на тему: “ Паралельне виконання операцій множення матриць ” Завдання Розробити структуру та описати процедуру перемноження матриці А (розмірністю N1 * N2) на матрицю В (розмірністю N2 * N3). Для вибраної структури визначити час виконання алгоритму, відсоток послідовної частини алгоритму та ефективність алгоритму для значень, які наведені нижче. Визначення вхідних даних: n1=2П = Е = 60 n2=3І = Д =104 n3=5Б =О = 333 5b-12b-6b-11b-8b-1b-3b-13b , де «nb»- номер букви П.І.Б. ЕРНДОЧКІ=> 171,93,134,13,250,49,47,223 17110 = АВ16 9310 = 5D16 13410 = 8616 1310 = D16 25010 = FA16 4910 = 3116 472 = 2F16 22310 = DF16 Матриця зв’язків орієнтованого графу: №проц. 1 2 3 4 5 6 7 8 1 0 0 1 0 1 0 1 1 2 0 0 0 1 1 1 0 1 3 1 0 0 0 0 1 1 0 4 0 0 0 0 1 1 0 1 5 1 1 1 1 0 0 1 0 6 0 0 1 1 0 0 0 1 7 0 0 1 0 1 1 0 1 8 1 1 0 1 1 1 1 0 Визначення початкового завантаження: Номер залікової – 0909402 – спільна пам’ять. Співвідношення часових параметрів: , де Zi – відповідна цифра номера залікової книжки, k – кількість цифр в номері залікової книжки. tU – час виконання однієї операції множення; tS – час виконання однієї операції сумування; tP – час виконання однієї операції пересилання даних між процесорами; tZ – час виконання операції завантаження одних даних; tW – час виконання операції вивантаження одних даних. Анотація Дана курсова робота представляє собою розробку алгоритму паралельного перемноження двох матриць розміром A(60*104) та В(104*333) на восьми процесорах використовуючи кільцеву структуру зі спільною пам’яттю. У звіті наведені функціональна схема, блок-схема виконання алгоритму, проведений розрахунок часових характеристик алгоритму, відповідно до яких визначено ефективність його виконання відносно послідовного. Програма написана засобами мови C++ з використанням бібліотеки MPI. Зміст Завдання 2 Анотація 3 Вступ 5 1. Теоретичний розділ 6 2. Розробка блок-схеми виконання алгоритму 9 3. Розробка функціональної схеми 10 4. Розрахунковий розділ 11 5. Розробка програми 13 Висновки 15 Список літератури 16 Додаток А. Лістинг програми 17 Вступ З розвитком комп’ютерної техніки все більше постає питання оптимального вирішення складних задач. Паралельні обчислення – один із методів, який дозволяє ефективно вирішувати певного виду задачі на багатопроцесорних системах, таких як прогноз погоди, задачі гідно- і газодинаміки, квантової хімії, біології і медицина, астрономії і багато інших. Множення матриць – також одна із таких задач. Існує багато технологій реалізації паралельних обчислень, ефективність яких залежить переважно від параметрів системи: продуктивності комп’ютерів, розмірів і структури пам’яті, пропускної здатності каналів, використаних мов програмування, компіляторів, операційних систем та інших. Такий широкий обсяг параметрів вимагає проведення досліджень на різних рівнях: на рівні розпаралелення алгоритмів, створення спеціальних мов програмування, компіляторів, багатопроцесорних систем, неоднорідних систем, кластерів і систем, що розподілені на великих територіях. Паралельні алгоритми досить важливі з огляду на постійне вдосконалення багатопроцесорних систем і збільшення числа ядер у сучасних процесорах. У організації паралельних обчислень виникає низка проблем із синхронізацією роботи процесорів, рівномірним навантаженням системи, плануванням обчислень. В даній курсовій роботі буде проведено розробку алгоритму для вирішення задачі перемноженні двох матриць на кільцевій структурі. Теоретичний розділ Матриці та матричні операції широко використовуються при математичному моделюванні різноманітних процесів, явищ та систем. Матричні обчислення є основою великої кількості наукових та інженерних розрахунків серед прикладних областей це військова промисловість, медицина, обчислювальна математика, фізика, економіка та ін. В даному випадку в нас є 8 процесорів. Для вирішення поставленої задачі вхідні матриці розбиваємо на 8 горизонтальних смуг (матриця А) та8 вертикальних (матриця В) рис. 1. рис. 1. Розбиття вхідних матриць Кожний процесор зчитує з пам’яті відповідну підматрицю Аi та підматрицю Вi. Після того як процесор помножив під матрицю Аi на підматрицю Вi, він обмінюється з іншим процесором підматрицею Вi. Підматриця Аi завжди знаходиться у відповідному процесорі, а підматриці В рухаються по всіх процесорах. Отже кожен процесор повинен помножити відповідну підматрицю Аi на всі підматриці Вi. В результаті всіх множень у пам’яті буде результуюча матриця. Обмін підматрицями Вi між процесорами відбувається не в довільному порядку. Схема обміну відображена у графі (рис. 2). рис. 2. Граф-схема зв’язків між процесорами та пам’яттю. Із даної схеми можна отримати кільцеву структуру (рис. 3) Збір даних буде проводитися також по кільцю за такою схемою (з умовою, що процесор в одночасно може або отримувати дані або пересилати) : Р1(C1) => P8; P6(C6) => P3; P5(C5) => P7; P2(C2) => P4; P3(C3, C6) => P1; P7(C5, C7) => P6; P4(C2, C4) => P5; P1(C3, C6) => P8; P6(C5, C7) => P3; P5(C2, C4) => P7; P3(C5, C7) => P1; P7(C2, C4) => P6; P1(C5, C7) => P8; P6(C2, C4) => P3; P3(C2, C4) => P1; P1(C2, C4) => P8; У першому такті пересилається одна підматриця Ві, у всіх решта – дві. 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-P8,отрим.В3 з P3 Перес.В2-P4,отрим.В8 З P8 Перес.В3-P1,отрим.В6 З P6 Перес.В4-P5,отрим.В2 З P2 Перес.В5-P7,отрим.В4 З P4 Перес.В6-P3,отрим.В7 З P7 Перес.В7-P6,отрим.В5 З P5 Перес.В8-P2отрим.В1 З P1 Множення А1хВ3 Множення А2хВ8 Множення А3хВ6 Множення А4хВ2 Множення А5хВ4 Множення А6хВ7 Множення А7хВ5 Множення А8хВ1 Перес.В3-P8,отрим.В6 з P3 Перес.В8-P4,отрим.В1 з P8 Перес.В6-P1,отрим.В7 з P6 Перес.В2-P5,отрим.В8 з P2 Перес.В4-P7,отрим.В2 з P4 Перес.В7-P3,отрим.В5 з P7 Перес.В5-P6,отрим.В4 з P5 Перес.В1-P2,отрим.В3 з P1 Множення А1хВ6 Множення А2хВ1 Множення А3хВ7 Множення А4хВ8 Множення А5хВ2 Множення А6хВ5 Множення А7хВ4 Множення А8хВ3 Перес.В6-P8,отрим.В7 з P3 Перес.В1-P4,отрим.В3 з P8 Перес.В7-P1,отрим.В5 з P6 Перес.В8-P5,отрим.В1 з P2 Перес.В2-P7,отрим.В8 з P4 Перес.В5-P3,отрим.В4 з P7 Перес.В4-P6,отрим.В2 з P5 Перес.В3-P2,отрим.В6 з P1 Множення А1хВ7 Множення А2хВ3 Множення А3хВ5 Множення А4хВ1 Множення А5хВ8 Множення А6хВ4 Множення А7хВ2 Множення А8хВ6 Перес.В7-P8,отрим.В5 з P3 Перес.В3-P4,отрим.В6 з P8 Перес.В5-P1,отрим.В4 з P6 Перес.В1-P5,отрим.В3 з P2 Перес.В8-P7,отрим.В1 з P4 Перес.В4-P3,отрим.В2 з P7 Перес.В2-P6,отрим.В8 з P5 Перес.В6-P2,отрим.В7 з P1 Множення А1хВ5 Множення А2хВ6 Множення А3хВ4 Множення А4хВ3 Множення А5хВ1 Множення А6хВ2 Множення А7хВ8 Множення А8хВ7 Перес.В5-P8,отрим.В4 з P3 Перес.В6-P4,отрим.В7 з P8 Перес.В4-P1,отрим.В2 з P6 Перес.В3-P5,отрим.В6 з P2 Перес.В1-P7,отрим.В3 з P4 Перес.В2-P3,отрим.В8 з P7 Перес.В8-P6,отрим.В1 з P5 Перес.В7-P2,отрим.В5 з P1 Множення А1хВ4 Множення А2хВ7 Множення А3хВ2 Множення А4хВ6 Множення А5хВ3 Множення А6хВ8 Множення А7хВ1 Множення А8хВ5 Перес.В4-P8,отрим.В2 з P3 Перес.В7-P4,отрим.В5 з P8 Перес.В2-P1,отрим.В8 з P6 Перес.В6-P5,отрим.В7 з P2 Перес.В3-P7,отрим.В6 з P4 Перес.В8-P3,отрим.В1 з P7 Перес.В1-P6,отрим.В3 з P5 Перес.В5-P2,отрим.В4 з P1 Множення А1хВ2 Множення А2хВ5 Множення А3хВ8 Множення А4хВ7 Множення А5хВ6 Множення А6хВ1 Множення А7хВ3 Множення А8хВ4 Перес.В2-P8,отрим.В8 з P3 Перес.В5-P4,отрим.В4 з P8 Перес.В8-P1,отрим.В1 з P6 Перес.В7-P5,отрим.В5 з P2 Перес.В6-P7,отрим.В7 з P4 Перес.В1-P3,отрим.В3 з P7 Перес.В3-P6,отрим.В6 з P5 Перес.В4-P2,отрим.В2 з P1 Множення А1хВ8 Множення А2хВ4 Множення А3хВ1 Множення А4хВ5 Множення А5хВ7 Множення А6хВ3 Множення А7хВ6 Множення А8хВ2 Пер.C1 – P8 Пер.C2 – P4 Отр.С6 з P6 Отр.С2 з P2 Пер.C5 – P7 Пер.C6 – P3 Отр.С7 з P5 Отр.С1 з P1 Отр. C3, С6 з P3 Пер.C3, С6 – P1 Пер.C2, С4 – P5 Отр. C2, С4 З P4 Отр. C5, С7 з P7 Пер.C5, С7 – P6 Пер.C3, С6 – P8 Отр. C7, С5 З P6 Пер.C2, С4 – P7 Пер.C5, С7 – P3 Отр. C2, С4 З P5 Отр. C3, С6 З P1 Отр. C5, С7 З P3 Пер.C5, С7 – P1 Отр. C2, С4 З P7 Пер.C2, С4 – P6 Пер.C5, С7 – P8 Отр. C2, С4 З P6 Пер.C2, С4 – P3 Отр. C5, С7 З P1 Отр. C2, С4 З P3 Пер.C2, С4 – P1 Пер.C2, С4 – P8 Отр. C2, С4 З P1 Вивантаження С рис. 5. Функціональна схема 4. Розрахунковий розділ Розміри матриць : A[60 * 104] та В[104 * 333] Розміри підматриць: A1 – A4 : [8 * 104]; A5 – A8 : [7 * 104] B1 – B 5 : [104 * 42]; B6 – В8 : [104 * 41] позначимо N1M = max(8, 7) = 8; N3M = max(42, 41) = 42. Виразимо часові параметри : ts – час виконання однієї операції сумування; – час виконання однієї операції множення; – час виконання однієї операції пересилання даних між процесорами; – час виконання операції завантаження одних даних; – час виконання операції вивантаження одних даних. Час виконання виразу буде рівний Оскільки за умовами в нас є спільна пам'ять, то звернення кожного процесору до пам'яті і завантаження даних буде виконуватися послідовно, тобто загальний час буде Оскільки розміри під матриць Аі не є однаковими, так само як розміри під матриць Ві, тому час множення буде не однаковий і виникатимуть затримки під час обміну під матрицями Ві між процесорами. Тому при підрахунку загального часу виконання операцій множення та додавання будемо використовувати найбільші значення розмірів під матиць Аі та Ві. Аналогічно максимальне значення другого виміру матриці Ві будемо використовувати для обчислення загального часу обміну даними між процесорами в тому числі і збору результату в першому процесорі. Оскільки одночасно процесор може пересилати або приймати дані, тому час обміну даними між процесорами буде проводитися в два етапи. Про те, чому саме коефіцієнт 13 використаний в даній формулі, розписано в розділі 1. Обчислюємо загальний час виконання множення матриць на даному паралельному алгоритмі: Для обчислення ефективності даного алгоритму, потрібно визначити час виконання множення даних матриць на одному процесорі. В цьому випадку, час завантаження та вивантаження даних не зміниться, пересилання і збір проводити не потрібно, тому даний час не враховується. Час виконання операцій множення та сумування обчислюється відповідно N1 * N2 * N3 * tU та N1 * (N2-1) * N3 * tS. Ефективність визначається як відношення часу виконання алгоритму на однопроцесорній системі, до часу потрібного для виконання на багатопроцесорної системі, помноженого на кількість процесорів в ній. 5. Розробка програми Програма, що реалізує поставлену в курсовій роботі задачу, написана на мові програмування С++ із використанням технології MPI. Базується на алгоритмі, блок-схема якого наведена на рис. 6. Рис. 4.2. Загальна граф-схема програми Для обміну інформацією між процесами використовуються функції бібліотеки MPI 2.0 MPI_Send() та MPI_Recv(). Це парні функції, які призначені відповідно для відправки та прийому повідомлень. Висновки Під час виконання курсової роботи я розробив паралельний алгоритм перемноження двох матриць на структурі з восьми процесорів та його програмну реалізацію. Також провів обчислення, і отримав часові характеристики даного паралельного алгоритму. Після чого порівняв його із звичайним послідовним алгоритмом, який у висновку виконується на 8,36 раз довше, ніж паралельний. Ефективність розпаралелення алгоритму виявилась рівною Е ≈ 0,92, що є досить непоганим показником, враховуючи особливість вивантаження даних у цьому алгоритмі. Програмна реалізація є повністю робочою, і може без вагань бути запущена на виконання у справжній восьмипроцесорній системі. Список літератури Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. – СПб: БХВ-Петербург, 2002. Корнеев В.В. Параллельные вычислительные системы. М.: Нолидж, 1999 http://www.parallel.ru – Інформаційно-аналітичний центр з паралельних обчислень. Додаток А. Лістинг програми #include "stdio.h" #include "stdlib.h" #include "time.h" #include "math.h" #include "mpi.h" #define AROW 60 #define ACOL 104 #define BCOL 333 #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

Вхід на сайт

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