Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Інформація про навчальний заклад
ВУЗ:
Інші
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Не вказано
Інформація про роботу
Рік:
2024
Тип роботи:
Курсова робота
Предмет:
Інші
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти і науки, молоді та спорту України
Національний університет „ Львівська політехніка ”
ІКТАМ
Кафедра ЕОМ
Курсова робота
з предмету:
“ Паралельні та розподілені обчислення ”
на тему:
“ Паралельне виконання операцій множення матриць ”
Завдання.
Розробити структуру та описати процедуру перемноження матриці А (розмірністю N1 * N2) на матрицю В (розмірністю N2 * N3). Для вибраної структури визначити час виконання алгоритму, відсоток послідовної частини алгоритму та ефективність алгоритму для значень, які наведені нижче.
Визначення вхідних даних:
n1=1П = Е = 60
n2=7Б = 4Б = А = 64
n3=3І = П = 241
14b-8b-1b-3b-9b-2b-11b-5b
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
Е
М
У
Н
Г
А
Б
А
П
Е
Л
Е
А
Л
Ь
Ф
А
3
8
4
5
7
1
2
6
Таблиця 2. Кодування букв
П
Е
У
А
Б
Л
Ь
Н
219
171
164
27
35
212
28
134
DB
AB
A4
1B
23
D4
1C
86
Матриця зв’язків орієнтованого графу:
№проц.
1
2
3
4
5
6
7
8
1
0
1
0
1
1
0
1
1
2
1
0
1
0
1
0
1
1
3
1
0
0
0
0
1
0
0
4
0
0
0
0
1
0
1
1
5
0
0
1
0
0
0
1
1
6
1
1
0
1
0
0
0
0
7
0
0
0
1
1
1
0
0
8
1
0
0
0
0
1
1
0
Визначення початкового завантаження:
Номер залікової –0909952
– спільна пам’ять.
Співвідношення часових параметрів:
, де Zi – відповідна цифра номера залікової книжки, k – кількість цифр в номері залікової книжки.
tU – час виконання однієї операції множення;
tS – час виконання однієї операції сумування;
tP – час виконання однієї операції пересилання даних між процесорами;
tZ – час виконання операції завантаження одних даних;
tW – час виконання операції вивантаження одних даних.
Анотація
Дана курсова робота представляє собою розробку алгоритму паралельного перемноження двох матриць розміром A(60*64) та В(64*241) на восьми процесорах використовуючи кільцеву структуру зі спільною пам’яттю.
У звіті наведені функціональна схема, блок-схема виконання алгоритму, проведений розрахунок часових характеристик алгоритму, відповідно до яких визначено ефективність його виконання відносно послідовного.
Програма написана засобами мови C++ з використанням бібліотеки MPI.
Зміст
Вступ 6
1.Теоретичний розділ 7
2. Розробка блок-схеми виконання алгоритму 9
3. Розробка функціональної схеми 10
4. Розрахунковий розділ 12
5. Розробка програми 14
Висновки 15
СПИСОК ЛІТЕРАТУРИ. 16
Додаток. 17
Лістинг програми. 17
Вступ
З розвитком комп’ютерної техніки все більше постає питання оптимального вирішення складних задач. Паралельні обчислення – один із методів, який дозволяє ефективно вирішувати певного виду задачі на багатопроцесорних системах, таких як прогноз погоди, задачі гідро- і газодинаміки, квантової хімії, біології і медицина, астрономії і багато інших. Множення матриць – також одна із таких задач.
Існує багато технологій реалізації паралельних обчислень, ефективність яких залежить переважно від параметрів системи: продуктивності комп’ютерів, розмірів і структури пам’яті, пропускної здатності каналів, використаних мов програмування, компіляторів, операційних систем та інших. Такий широкий обсяг параметрів вимагає проведення досліджень на різних рівнях: на рівні розпаралелення алгоритмів, створення спеціальних мов програмування, компіляторів, багатопроцесорних систем, неоднорідних систем, кластерів і систем, що розподілені на великих територіях.
Паралельні алгоритми досить важливі з огляду на постійне вдосконалення багатопроцесорних систем і збільшення числа ядер у сучасних процесорах.
У організації паралельних обчислень виникає низка проблем із синхронізацією роботи процесорів, рівномірним навантаженням системи, плануванням обчислень. В даній курсовій роботі буде проведено розробку алгоритму для вирішення задачі перемноженні двох матриць на кільцевій структурі.
1.Теоретичний розділ
Матриці та матричні операції широко використовуються при математичному моделюванні різноманітних процесів, явищ та систем. Матричні обчислення є основою великої кількості наукових та інженерних розрахунків серед прикладних областей це військова промисловість, медицина, обчислювальна математика, фізика, економіка та ін.
В даному випадку в нас є 8 процесорів. Для вирішення поставленої задачі вхідні матриці розбиваємо на 8 горизонтальних смуг (матриця А) та8 вертикальних (матриця В) рис. 1.1
рис. 1.1 Розбиття вхідних матриць
Кожний процесор зчитує з пам’яті відповідну підматрицю Аi та підматрицю Вi. Після того як процесор помножив під матрицю Аi на підматрицю Вi, він обмінюється з іншим процесором підматрицею Вi. Підматриця Аi завжди знаходиться у відповідному процесорі, а підматриці В рухаються по всіх процесорах. Отже кожен процесор повинен помножити відповідну підматрицю Аi на всі підматриці Вi. В результаті всіх множень у пам’яті буде результуюча матриця. Обмін підматрицями Вi між процесорами відбувається не в довільному порядку. Схема обміну відображена у графі (рис. 1.2).
рис. 1.2 Граф-схема зв’язків між процесорами та пам’яттю.
Із даної схеми можна отримати кільцеву структуру (рис. 1.3)
Рис. 1.3. Граф пересилання даних між процесорами на кільцевій структурі.
2. Розробка блок-схеми виконання алгоритму
рис. 2.1 Граф-схема алгоритму множення матриць
Оскільки згідно із завданням маємо структуру зі спільною пам’ятю, то завантаження початкових даних буде проводитися послідовно. Збір результатів виконання множення ( під матриць Сі ) відбувається в першому процесорі і відповідно вивантаження результуючої матриці С також відбувається з першого процесору.
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-P6,отрим.В2
З P2
Перес.В4-P7,отрим.В6
З P6
Перес.В5-P8,отрим.В7
З P7
Перес.В6-P4,отрим.В3
З P3
Перес.В7-P5,отрим.В4
З P4
Перес.В8-P1,отрим.В5
З P5
Множення
А1хВ8
Множення
А2хВ1
Множення
А3хВ2
Множення
А4хВ6
Множення
А5хВ7
Множення
А6хВ3
Множення
А7хВ4
Множення
А8хВ5
Перес.В8-P2,отрим.В5
з P8
Перес.В1-P3,отрим.В8
З P1
Перес.В2-P6,отрим.В1
З P2
Перес.В6-P7,отрим.В3
З P6
Перес.В7-P8,отрим.В4
З P7
Перес.В3-P4,отрим.В2
З P3
Перес.В4-P5,отрим.В6
З P4
Перес.В5-P1,отрим.В7
З P5
Множення
А1хВ5
Множення
А2хВ8
Множення
А3хВ1
Множення
А4хВ3
Множення
А5хВ4
Множення
А6хВ2
Множення
А7хВ6
Множення
А8хВ7
Перес.В5-P2,отрим.В7
з P8
Перес.В8-P3,отрим.В4
З P1
Перес.В1-P6,отрим.В8
З P2
Перес.В3-P7,отрим.В2
З P6
Перес.В4-P8,отрим.В6
З P7
Перес.В2-P4,отрим.В1
З P3
Перес.В6-P5,отрим.В3
З P4
Перес.В7-P1,отрим.В4
З P5
Множення
А1хВ7
Множення
А2хВ5
Множення
А3хВ8
Множення
А4хВ2
Множення
А5хВ6
Множення
А6хВ1
Множення
А7хВ3
Множення
А8хВ4
Перес.В7-P2,отрим.В4
з P8
Перес.В5-P3,отрим.В7
З P1
Перес.В8-P6,отрим.В5
З P2
Перес.В2-P7,отрим.В1
З P6
Перес.В6-P8,отрим.В3
З P7
Перес.В1-P4,отрим.В8
З P3
Перес.В3-P5,отрим.В2
З P4
Перес.В4-P1,отрим.В6
З P5
Множення
А1хВ4
Множення
А2хВ7
Множення
А3хВ5
Множення
А4хВ1
Множення
А5хВ3
Множення
А6хВ8
Множення
А7хВ2
Множення
А8хВ6
Перес.В4-P2,отрим.В6
з P8
Перес.В7-P3,отрим.В4
З P1
Перес.В5-P6,отрим.В7
З P2
Перес.В1-P7,отрим.В8
З P6
Перес.В3-P8,отрим.В2
З P7
Перес.В8-P4,отрим.В5
З P3
Перес.В2-P5,отрим.В1
З P4
Перес.В6-P1,отрим.В3
З P5
Множення
А1хВ6
Множення
А2хВ4
Множення
А3хВ7
Множення
А4хВ8
Множення
А5хВ2
Множення
А6хВ5
Множення
А7хВ1
Множення
А8хВ3
Перес.В6-P2,отрим.В3
з P8
Перес.В4-P3,отрим.В6
З P1
Перес.В7-P6,отрим.В4
З P2
Перес.В8-P7,отрим.В5
З P6
Перес.В2-P8,отрим.В1
З P7
Перес.В5-P4,отрим.В7
З P3
Перес.В1-P5,отрим.В8
З P4
Перес.В3-P1,отрим.В2
З P5
Множення
А1хВ3
Множення
А2хВ6
Множення
А3хВ4
Множення
А4хВ5
Множення
А5хВ1
Множення
А6хВ7
Множення
А7хВ8
Множення
А8хВ2
Перес.В3-P2,отрим.В2
з P8
Перес.В6-P3,отрим.В3
З P1
Перес.В4-P6,отрим.В6
З P2
Перес.В5-P7,отрим.В7
З P6
Перес.В1-P8,отрим.В8
З P7
Перес.В7-P4,отрим.В4
З P3
Перес.В8-P5,отрим.В5
З P4
Перес.В2-P1,отрим.В1
З P5
Множення
А1хВ2
Множення
А2хВ3
Множення
А3хВ6
Множення
А4хВ7
Множення
А5хВ8
Множення
А6хВ4
Множення
А7хВ5
Множення
А8хВ1
Вив.С1
Перес. С2- Р3
Перес. С3- Р6
Перес. С4- Р7
Перес. С5- Р8
Перес. С6- Р4
Перес. С7- Р5
Перес. С8- Р1
Вив.С8
Перес. С2- Р6
Перес. С6- Р7
Перес. С7- Р8
Перес. С3- Р4
Перес. С4- Р5
Перес. С5- Р1
Вив.С5
Перес. С3- Р7
Перес. С4- Р8
Перес. С2- Р4
Перес. С6- Р5
Перес. С7- Р1
Вив.С7
Перес. С2- Р7
Перес. С6- Р8
Перес. С3- Р5
Перес. С4- Р1
Вив.С4
Перес. С3- Р8
Перес. С2- Р5
Перес. С6- Р1
Вив.С6
Перес. С2- Р8
Перес. С3- Р1
Вив.С3
Перес. С2- Р1
Вив.С2
рис. 3.1 Функціональна схема
4. Розрахунковий розділ
Розміри матриць : A[60 * 64] та В[64 * 241]
Розміри підматриць:
A1 – A4 : [7 * 64]; A5 – A8 : [8 * 64];
B1 – B7 : [64 * 30]; В8 : [64 * 31]
позначимо N1M = max(7, 8) = 8; N3M = max(30, 31) = 31.
Виразимо часові параметри :
ts – час виконання однієї операції сумування;
– час виконання однієї операції множення;
– час виконання однієї операції пересилання даних між процесорами;
– час виконання операції завантаження одних даних;
– час виконання операції вивантаження одних даних.
Час виконання виразу буде рівний
Оскільки за умовами в нас є спільна пам'ять, то звернення кожного процесору до пам'яті і завантаження даних буде виконуватися послідовно, тобто загальний час буде
Оскільки розміри під матриць Аі не є однаковими, так само як розміри під матриць Ві, тому час множення буде не однаковий і виникатимуть затримки під час обміну під матрицями Ві між процесорами. Тому при підрахунку загального часу виконання операцій множення та додавання будемо використовувати найбільші значення розмірів під матиць Аі та Ві.
Аналогічно максимальне значення другого виміру матриці Ві будемо використовувати для обчислення загального часу обміну даними між процесорами в тому числі і збору результату в першому процесорі.
Оскільки одночасно процесор може пересилати або приймати дані, тому час обміну даними між процесорами буде проводитися в два етапи.
Обчислюємо загальний час виконання множення матриць на даному паралельному алгоритмі:
Для обчислення ефективності даного алгоритму, потрібно визначити час виконання множення даних матриць на одному процесорі. В цьому випадку, час завантаження та вивантаження даних не зміниться, пересилання і збір проводити не потрібно, тому даний час не враховується. Час виконання операцій множення та сумування обчислюється відповідно N1 * N2 * N3 * tU та N1 * (N2-1) * N3 * tS.
Ефективність визначається як відношення часу виконання алгоритму на однопроцесорній системі, до часу потрібного для виконання на багатопроцесорної системі, помноженого на кількість процесорів в ній.
5. Розробка програми
Програма, що реалізує поставлену в курсовій роботі задачу, написана на мові програмування С++ із використанням технології MPI. Базується на алгоритмі, блок-схема якого наведена на рис. 5.1
Рис. 5.1 Загальна граф-схема програми
Висновки
Під час виконання курсової роботи я розробив паралельний алгоритм перемноження двох матриць на структурі з восьми процесорів та його програмну реалізацію. Також провів обчислення, і отримав часові характеристики даного паралельного алгоритму. Після чого порівняв його із звичайним послідовним алгоритмом, який у висновку виконується на 6,7 раз довше, ніж паралельний. Ефективність розпаралелення алгоритму виявилась рівною Е ≈ 0,84.
СПИСОК ЛІТЕРАТУРИ.
Корнеев В.В. Параллельные вычислительные системы. М.: Нолидж, 1999
Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. – СПб: БХВ-Петербург, 2002.
Ортега Дж. Введение в параллельные и векторные методы решения линейных систем. М.:Мир, 1991.
Программирование на параллельных вычислительных системах: Пер с англ./Под ред. Р.Бэбба.М.:Мир, 1991.
Бройнль Т. Паралельне програмування: Початковий курс: Навчальний посібник. – К.:Вища школа.,1997.
Воеводин В.В. Математические основы параллельных вычислений.- М.: Изд-во МГУ, 1991.
Векторизация программ: теория, методы, реализация: Пер. с англ. и нем. /Под ред. Г.Д.Чинина. - М:. Мир, 1991.
Організація паралельних обчислень : Навчальний посібник з дисципліни “Паралельні та розподілені обчислення” для студентів базового напрямку 6.0915 "Комп'ютерна інженерія" / Укладачі: Є. Ваврук, О. Лашко – Львів: Національний університет “Львівська політехніка”, 2007, 70 с.
http://www.parallel.ru – Інформаційно-аналітичний центр з паралельних обчислень.
http://www.csa.ru – Інститут високопродуктивних обчислень і баз даних.
http://www.hpc.nw.ru – Високопродуктивні обчислення.
Додаток.
Лістинг програми.
#include "stdio.h"
#include "stdlib.h"
#include "time.h"
#include "math.h"
#include "mpi.h"
#define AROW 60
#define ACOL 64
#define BCOL 241
#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;
}
19.11.2013 20:11-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора