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

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

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

ВУЗ:

Інші

Інститут:

Не вказано

Факультет:

Не вказано

Кафедра:

Не вказано

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

Рік:

2024

Тип роботи:

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

Предмет:

Інші

Завантажити

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

Міністерство освіти і науки, молоді та спорту України Національний університет „ Львівська політехніка ” ІКТАМ Кафедра ЕОМ Курсова робота з предмету: “ Паралельні та розподілені обчислення ” на тему: “ Паралельне виконання операцій множення матриць ” Завдання Розробити структуру та описати процедуру перемноження матриці А (розмірністю N1 * N2) на матрицю В (розмірністю N2 * N3). Для вибраної структури визначити час виконання алгоритму, відсоток послідовної частини алгоритму та ефективність алгоритму для значень, які наведені нижче. Визначення вхідних даних: n1=1П= К = 200 n2=7Б = В =56 n3=3І =Г = 195 14b-8b-1b-3b-9b-2b-11b-5b , де «nb»- номер букви П.І.Б. АИКНБОГР=> 27,91,47,134,35,250,74,93 2710 = 1B16 9110 = 5B16 4710 = 2F16 13410 = 8616 3510 = 2316 25010 = FA16 742 = 4A16 9310 = 5D16 Матриця зв’язків орієнтованого графу: №проц. 1 2 3 4 5 6 7 8 1 0 0 0 1 1 0 1 1 2 0 0 0 1 1 0 1 1 3 0 0 0 0 1 1 1 1 4 1 0 0 0 0 1 1 0 5 0 0 1 0 0 0 1 1 6 1 1 1 1 1 0 1 0 7 0 1 0 0 1 0 0 0 8 0 1 0 1 1 1 0 0 Визначення початкового завантаження: Номер залікової – 0909024 – спільна пам’ять. Співвідношення часових параметрів: , де Zi – відповідна цифра номера залікової книжки, k – кількість цифр в номері залікової книжки. tU – час виконання однієї операції множення; tS – час виконання однієї операції сумування; tP – час виконання однієї операції пересилання даних між процесорами; tZ – час виконання операції завантаження одних даних; tW – час виконання операції вивантаження одних даних. Анотація Дана курсова робота представляє собою розробку алгоритму паралельного перемноження двох матриць розміром A(200*56) та В(56*195) на восьми процесорах використовуючи кільцеву структуру зі спільною пам’яттю. У звіті наведені функціональна схема, блок-схема виконання алгоритму, проведений розрахунок часових характеристик алгоритму, відповідно до яких визначено ефективність його виконання відносно послідовного. Програма написана засобами мови C++ з використанням бібліотеки MPI. Зміст Завдання 2 Анотація 4 Вступ 6 1. Теоретичний розділ 8 2. Розробка блок-схеми виконання алгоритму 11 3. Розробка функціональної схеми 12 4. Розрахунковий розділ 13 5. Розробка програми 15 Висновки 17 Список літератури 18 Додаток А. Лістинг програми 19 Вступ Під терміном паралельні обчислення розуміють сукупність питань, що відноситься до створення ресурсів паралелізму в процесах вирішення задачі з метою досягнення більшої ефективності використання обчислювальної техніки. Програми для паралельних комп'ютерів писати значно складніше, ніж для послідовних, бо паралелізм додає кілька нових класів потенційних помилок, серед яких є найпоширенішою стан «перегонів». Комунікація, та синхронізація процесів зазвичай одна з найбільших перешкод для досягнення хорошої продуктивності паралельних програм. Удосконалення комп’ютерів призводить до збільшення їх продуктивності, тобто до збільшення можливості виконання більшої кількості операцій за 1 часу. Продуктивність вимірюється у MIPS (мільйон ітерацій з плаваючою комою за секунду). Реальна продуктивність обчислювальної системи визначається як продуктивність, якої сягає обчислювальна система при виконанні конкретної задачі. Причому, ефективність паралельної обробки залежить як від продуктивності комп’ютерів так і від розмірів і структури пам’яті, пропускної здатності каналу звязку, використаних мов програмування, компіляторів операційних систем та від інших факторів. Основна ідея розпаралелювання обчислень – мінімізація часу виконання задачі за рахунок розподілу навантаження між декількома обчислювальними пристроями. Цими «обчислювальними пристроями» можуть бути як процесори одного суперкомп'ютера, так і кілька комп'ютерів рангом поменше, обєднаних за допомогою комунікаційної мережі в єдину обчислювальну структуру – кластер. Існують дві моделі паралельного програмування: модель паралелізм даних і модель паралелізму задач. Модель паралелізми даних має на увазі незалежну обробку даних кожним процесом (наприклад, векторні операції з масивами). Модель паралелізами задач передбачає розбивка основної задачі на трохи щодо самостійних підзадач, кожна з яких виконується окремо й обмінюється даними з іншими. Це більш трудомісткий, у порівнянні з паралелізмом даних, підхід. Перевагою є велика гнучкість і велика воля, надана програмісту в розробці програми, що ефективно використовує ресурси паралельної системи. При цьому можуть застосовуватися спеціалізовані бібліотеки, що беруть на себе всі «організаційні» задачі. Максимальний можливий приріст продуктивності паралельної програми визначається законом Амдаля. Для скорочення термінів розробки паралельних засобів та дослідження їх роботи використовується моделювання. Теоретичний розділ Під терміном паралельні обчислення розуміють сукупність питань, що відноситься до створення ресурсів паралелізму в процесах вирішення задачі з метою досягнення більшої ефективності використання обчислювальної техніки. Направлений на збільшення ефективності роботи комп’ютерної системи. Удосконалення комп’ютерів призводить до збільшення їх продуктивності, тобто до збільшення можливості виконання більшої кількості операцій за 1 часу. Продуктивність вимірюється у MIPS (мільйон ітерацій з плаваючою комою за секунду). Реальна продуктивність обчислювальної системи визначається як продуктивність, якої сягає обчислювальна система при виконанні конкретної задачі. Основна ідея розпаралелювання обчислень – мінімізація часу виконання задачі за рахунок розподілу навантаження між декількома обчислювальними пристроями. Цими «обчислювальними пристроями» можуть бути як процесори одного суперкомп'ютера, так і кілька комп'ютерів рангом поменше, обєднаних за допомогою комунікаційної мережі в єдину обчислювальну структуру – кластер. Паралельна модель програмування сильно відрізняється від звичайної – послідовної. Існують дві моделі паралельного програмування: модель паралелізм даних і модель паралелізму задач. Модель паралелізми даних має на увазі незалежну обробку даних кожним процесом (наприклад, векторні операції з масивами). Модель паралелізами задач передбачає розбивка основної задачі на трохи щодо самостійних підзадач, кожна з яких виконується окремо й обмінюється даними з іншими. Це більш трудомісткий, у порівнянні з паралелізмом даних, підхід. Перевагою є велика гнучкість і велика воля, надана програмісту в розробці програми, що ефективно використовує ресурси паралельної системи. При цьому можуть застосовуватися спеціалізовані бібліотеки, що беруть на себе всі«організаційні» задачі. Приклади таких бібліотек: MPI (Message Passing Interface) і PVM (Parallel Virtual Machine). Схема обміну відображена у графі (рис. 1). рис. 1. Граф-схема зв’язків між процесорами та пам’яттю. Із даної схеми можна отримати кільцеву структуру (рис. 2) Рис. 2. Граф пересилання даних між процесорами на кільцевій структурі. Збір даних буде проводитися також по кільцю за такою схемою (з умовою, що процесор в одночасно може або отримувати дані або пересилати) : Р2(C2) => P7; P1(C1) => P8; P6(C6) => P4; P5(C5) => P3; P8(C8, C1) => P2; P4(C4, C6) => P1; P3(C5, C3) => P6; P2(C8, C1) => P7; P1(C4, C6) => P8; P6(C5, C3) => P4; P4(C5, C3) => P1; P8(C4, C6) => P2; P2(C4, C6) => P7; P1(C5, C3) => P8; P8(C5, C3) => P2; P2(C5, C3) => P7; 2. Розробка блок-схеми виконання алгоритму рис. 3. Граф-схема алгоритму множення матриць Оскільки згідно із завданням маємо структуру зі спільною пам’ятю, то завантаження початкових даних буде проводитися послідовно. Збір результатів виконання множення ( під матриць Сі ) відбувається в першому процесорі і відповідно вивантаження результуючої матриці С також відбувається з першого процесору. 3. Розробка функціональної схеми Процесор1 Процесор2 Процесор3 Процесор4 Процесор5 Процесор6 Процесор7 Процесор 8 Завантажен А1,В1. Завантажен А2,В2. Завантажен А3,В3. Завантажен А3,В3. Завантажен А3,В3. Завантажен А3,В3. Завантажен А3,В3. Завантажен А3,В3. Множення А1хВ1 Множення А2хВ2 Множення А3хВ3 Множення А4хВ4 Множення А5хВ5 Множення А6хВ6 Множення А7хВ7 Множення А8хВ8 Перес.В1-P8,отрим.В4 з P4 Перес.В2-P7,отрим.В8 З P8 Перес.В3-P6,отрим.В5 З P5 Перес.В4-P1,отрим.В6 З P6 Перес.В5-P3,отрим.В7 З P7 Перес.В6-P4,отрим.В3 З P3 Перес.В7-P5,отрим.В2 З P2 Перес.В8-P2,отрим.В1 З P1 Множення А1хВ4 Множення А2хВ8 Множення А3хВ5 Множення А4хВ6 Множення А5хВ7 Множення А6хВ3 Множення А7хВ2 Множення А8хВ1 Перес.В4-P8,отрим.В6 з P4 Перес.В8-P7,отрим.В1 З P8 Перес.В5-P6,отрим.В7 З P5 Перес.В6-P1,отрим.В3 З P6 Перес.В7-P3,отрим.В2 З P7 Перес.В3-P4,отрим.В5 З P3 Перес.В2-P5,отрим.В8 З P2 Перес.В1-P2,отрим.В4 З P1 Множення А1хВ6 Множення А2хВ1 Множення А3хВ7 Множення А4хВ3 Множення А5хВ2 Множення А6хВ5 Множення А7хВ8 Множення А8хВ4 Перес.В6-P8,отрим.В3 з P4 Перес.В1-P7,отрим.В4 З P8 Перес.В7-P6,отрим.В2 З P5 Перес.В3-P1,отрим.В5 З P6 Перес.В2-P3,отрим.В8 З P7 Перес.В5-P4,отрим.В7 З P3 Перес.В8-P5,отрим.В1 З P2 Перес.В4-P2,отрим.В6 З P1 Множення А1хВ3 Множення А2хВ4 Множення А3хВ2 Множення А4хВ5 Множення А5хВ8 Множення А6хВ7 Множення А7хВ1 Множення А8хВ6 Перес.В3-P8,отрим.В5 з P4 Перес.В4-P7,отрим.В6 З P8 Перес.В2-P6,отрим.В8 З P5 Перес.В5-P1,отрим.В7 З P6 Перес.В8-P3,отрим.В1 З P7 Перес.В7-P4,отрим.В2 З P3 Перес.В1-P5,отрим.В4 З P2 Перес.В6-P2,отрим.В3 З P1 Множення А1хВ5 Множення А2хВ6 Множення А3хВ8 Множення А4хВ7 Множення А5хВ1 Множення А6хВ2 Множення А7хВ4 Множення А8хВ3 Перес.В5-P8,отрим.В7 з P4 Перес.В6-P7,отрим.В3 З P8 Перес.В8-P6,отрим.В1 З P5 Перес.В7-P1,отрим.В2 З P6 Перес.В1-P3,отрим.В4 З P7 Перес.В2-P4,отрим.В8 З P3 Перес.В4-P5,отрим.В6 З P2 Перес.В3-P2,отрим.В5 З P1 Множення А1хВ7 Множення А2хВ3 Множення А3хВ1 Множення А4хВ2 Множення А5хВ4 Множення А6хВ8 Множення А7хВ6 Множення А8хВ5 Перес.В7-P8,отрим.В2 з P4 Перес.В3-P7,отрим.В5 З P8 Перес.В1-P6,отрим.В4 З P5 Перес.В2-P1,отрим.В8 З P6 Перес.В4-P3,отрим.В6 З P7 Перес.В8-P4,отрим.В1 З P3 Перес.В6-P5,отрим.В3 З P2 Перес.В5-P2,отрим.В7 З P1 Множення А1хВ2 Множення А2хВ5 Множення А3хВ4 Множення А4хВ8 Множення А5хВ6 Множення А6хВ1 Множення А7хВ3 Множення А8хВ7 Перес.В2-P8,отрим.В8 з P4 Перес.В5-P7,отрим.В7 З P8 Перес.В4-P6,отрим.В6 З P5 Перес.В8-P1,отрим.В1 З P6 Перес.В6-P3,отрим.В3 З P7 Перес.В1-P4,отрим.В4 З P3 Перес.В3-P5,отрим.В5 З P2 Перес.В7-P2,отрим.В2 З P1 Множення А1хВ8 Множення А2хВ7 Множення А3хВ6 Множення А4хВ1 Множення А5хВ3 Множення А6хВ4 Множення А7хВ5 Множення А8хВ2 Пер.C2 – P4 Пер.C2 – P4 Отр. C5 З P5 Отр. C6 З P6 Пер.C2 – P4 Пер.C2 – P4 Отр. C2 З P2 Отр. C1 З P1 Пер.C3, С5 – P6 Пер.C4, С6 – P1 Пер.C5, С6 – P7 Отр. C2, С4 з P4 Отр. C5, С6 з P5 Пер.C8, С1 – P2 Пер.C4, С6 – P8 Пер.C8, С1 – P7 Отр. C3, С5 з P6 Пер.C5, С3 – P4 Отр. C8, С1 з P2 Отр. C4, С6 з P1 Отр. C5, С3 з P4 Отр. C4, С6 з P8 Пер.C5, С3 – P1 Пер.C4, С6 – P2 Пер.C5,С3 –P8 Пер.C4,С6 –P7 Отр. C4, С6 з P2 Отр. C5, С3 з P1 Отр. C4, С6 з P8 Пер.C5,С3 –P2 Пер.C5,С3 –P7 Отр. C5, С3 З P2 Вивантаження С рис. 4. Функціональна схема 4. Розрахунковий розділ Розміри матриць : A[200 * 56] та В[56 * 195] Розміри підматриць: A1 – A8 : [25 * 56]; B1 – B 3 : [56 * 25]; B4 – В8 : [56 * 24] позначимо N1M = max(25, 25) = 25; N3M = max(25, 24) = 25. Виразимо часові параметри : ts – час виконання однієї операції сумування; – час виконання однієї операції множення; – час виконання однієї операції пересилання даних між процесорами; – час виконання операції завантаження одних даних; – час виконання операції вивантаження одних даних. Час виконання виразу буде рівний Оскільки за умовами в нас є спільна пам'ять, то звернення кожного процесору до пам'яті і завантаження даних буде виконуватися послідовно, тобто загальний час буде Оскільки розміри під матриць Аі не є однаковими, так само як розміри під матриць Ві, тому час множення буде не однаковий і виникатимуть затримки під час обміну під матрицями Ві між процесорами. Тому при підрахунку загального часу виконання операцій множення та додавання будемо використовувати найбільші значення розмірів під матиць Аі та Ві. Аналогічно максимальне значення другого виміру матриці Ві будемо використовувати для обчислення загального часу обміну даними між процесорами в тому числі і збору результату в першому процесорі. Оскільки одночасно процесор може пересилати або приймати дані, тому час обміну даними між процесорами буде проводитися в два етапи. Про те, чому саме коефіцієнт 13 використаний в даній формулі, розписано в розділі 1. Обчислюємо загальний час виконання множення матриць на даному паралельному алгоритмі: Для обчислення ефективності даного алгоритму, потрібно визначити час виконання множення даних матриць на одному процесорі. В цьому випадку, час завантаження та вивантаження даних не зміниться, пересилання і збір проводити не потрібно, тому даний час не враховується. Час виконання операцій множення та сумування обчислюється відповідно N1 * N2 * N3 * tU та N1 * (N2-1) * N3 * tS. Ефективність визначається як відношення часу виконання алгоритму на однопроцесорній системі, до часу потрібного для виконання на багатопроцесорної системі, помноженого на кількість процесорів в ній. 5. Розробка програми Програма, що реалізує поставлену в курсовій роботі задачу, написана на мові програмування С++ із використанням технології MPI. Базується на алгоритмі, блок-схема якого наведена на рис. 5 Рис. 5. Загальна граф-схема програми Для обміну інформацією між процесами використовуються функції бібліотеки MPI 2.0 MPI_Send() та MPI_Recv(). Це парні функції, які призначені відповідно для відправки та прийому повідомлень. Висновки Під час виконання курсової роботи я розробив паралельний алгоритм перемноження двох матриць на структурі з восьми процесорів та його програмну реалізацію. Також провів обчислення, і отримав часові характеристики даного паралельного алгоритму. Ефективність розпаралелення алгоритму виявилась рівною Е ≈ 0,84, що є досить непоганим показником, враховуючи особливість вивантаження даних у цьому алгоритмі. Програмна реалізація є повністю робочою, і може без вагань бути запущена на виконання у справжній восьмипроцесорній системі. Список літератури Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. – СПб: БХВ-Петербург, 2002. Корнеев В.В. Параллельные вычислительные системы. М.: Нолидж, 1999 http://www.parallel.ru – Інформаційно-аналітичний центр з паралельних обчислень. Додаток А. Лістинг програми #include "stdio.h" #include "stdlib.h" #include "time.h" #include "math.h" #include "mpi.h" #define AROW 200 #define ACOL 56 #define BCOL 195 #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

Вхід на сайт

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