Параллельные вычисления

Лабораторная работаПомощь в написанииУзнать стоимостьмоей работы

Разработка параллельного алгоритма умножения матрицы на вектор Рисунок 1.4 — Печать количества и ранга процессов Рисунок 1.5 — Распределение данных Рисунок 1.6 — Результат проверки умножения матрицы на вектор. Реализация последовательного алгоритма Гаусса Рисунок 3.1 — Результат работы последовательного алгоритма Рисунок 3.2 — Работа программы со случайными числами Рисунок 3.3 — Прямой ход, выбор… Читать ещё >

Параллельные вычисления (реферат, курсовая, диплом, контрольная)

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

" ВЯТСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ"

Факультет прикладной математики и телекоммуникаций Кафедра радиоэлектронных средств Лабораторные работы № 1 — 4

Параллельные вычисления Киров 2014

Лабораторная работа № 1

Параллельные алгоритмы матрично-векторного умножения Цель работы: разработка параллельной программы, которая выполняет умножение матриц на вектор.

1. Реализация последовательного алгоритма умножения матрицы на вектор.

Рисунок 1.1 — Задание размера матрицы Рисунок 1.2 — Ввод данных простым способом Рисунок 1.3 — Результат выполнения матрично-векторного умножения

2. Проведение вычислительных экспериментов Вычисление времени выполнения алгоритма:

Таблица 1.1 — Сравнительная таблица работы последовательного алгоритма


Размер матрицы	Экспериментальное время, с	Теоретическое время, с
	0,91	0,38
	0,177	0,0398
	0,6 624	3,998
	0,18 156	15,996
	0,39 233	35,994
	0,64 005	63,992
	0,102	99,99
	0,139	143,988
	0,236	195,986
	0,258	255,984
	0,309	323,982
	0,393	399,98

3. Разработка параллельного алгоритма умножения матрицы на вектор Рисунок 1.4 — Печать количества и ранга процессов Рисунок 1.5 — Распределение данных Рисунок 1.6 — Результат проверки умножения матрицы на вектор

4. Проведение вычислительных экспериментов Таблица 1.2 — Сравнение времени работы последовательного и параллельного алгоритмов


Размер объектов	Последовательный алгоритм, с	Параллельный алгоритм
		2 процесса	4 процесса	8 процессов
		Время, с	ускорение	Время, с	ускорение	Время, с	ускорение
	0,2	0,3	0,67	0,4	0,5	0,3	0,67
	0,45	0,22	2,045	0,13	3,46	0,8	5,625
	0,3 988	0,278	1,4345	0,1 134	3,52	0,545	7,32
	0,16 664	0,8 298	2,008	0,4 478	3,72	0,2 116	7,875
	0,33 735	0,17 384	1,94	0,10 314	3,27	0,4 806	7,019
	0,59 323	0,3 352	1,77	0,18 750	3,16	0,11 837	5,012
	0,94 667	0,51 625	1,834	0,29 602	3,198	0,15 779	5,99
	0,137	0,1001	1,369	0,40 165	3,41	0,23 406	5,85
	0,192	0,1007	1,91	0,55 858	3,44	0,27 571	6,96
	0,247	0,13	1,9	0,74 295	3,33	0,35 478	6,96
	0,318	0,161	1,975	0,93 128	3,415	0,5 137	6,19
	0,384	0,206	1,864	0,114	3,37	0,62 096	6,184

Вывод:

1. В ходе лабораторной работы были разработаны 2 алгоритма вычисления произведения матрицы на вектор.

2. Выявлено, что последовательный алгоритм выполняется быстрее, чем последовательный, и с увеличением числа процессов, время вычисления уменьшается.

Лабораторная работа № 2

Параллельные алгоритмы матричного умножения Цель работы: разработка параллельной программы, которая выполняет умножение двух матриц.

1. Реализация последовательного алгоритма матричного умножения Рисунок 2.1 — Задание размера объекта Рисунок 2.2 — Ввод данных простым способом Рисунок 2.3 — Результат выполнения матрично-векторного умножения Рисунок 2.4 — Задание данных с помощью случайного генератора

2. Проведение вычислительных экспериментов Вычисление времени выполнения алгоритма:

Таблица 2.1 — Сравнительная таблица работы последовательного алгоритма


Размер матрицы	Экспериментальное время, с	Теоретическое время, с
	0,9	0,65
	0,4 949	0,0068
	0,853	0,853
	13,438	6,827
	54,374	23,0464
	129,97	54,632 985
	277,843	106,71
	483,046	184,40 169

3. Разработка параллельного алгоритма матричного умножения Рисунок 2.5 — Определение ранга процесса

4. Проведение вычислительных экспериментов Таблица 2.2 — Сравнение работы последовательного и параллельного алгоритмов


Размер объектов	Последовательный алгоритм, с	Параллельный алгоритм
		4 процесса	9 процессов
		Время, с	ускорение	Время, с	ускорение
	0,9	0,5	0,18	0,7 362	0,001
	0,4 949	0,3 443	1,437	0,023	0,215
	0,853	0,255	3,345	0,375	2,275
	13,438	3,039	4,42	1,872	7,178
	54,374	17,057	3,19	5,811 397	9,356
	129,97	33,23	3,91	21,47 895	6,051
	277,843	85,074	3,266	40,23 121	6,91
	483,046	130,373	3,705	56,60 254	8,534

Вывод:

1. В ходе лабораторной работы были реализованы 2 алгоритма вычисление произведения матриц.

2. Результаты работы последовательного и параллельного алгоритма совпадают.

3. Ускорение параллельного алгоритма, относительно последовательного, пропорционально числу выполняемых процессов.

Лабораторная работа № 3

Параллельные методы решения систем линейных уравнений Цель работы: разработка параллельной программы, которая выполняет решение системы линейных уравнений методом Гаусса.

1. Реализация последовательного алгоритма Гаусса Рисунок 3.1 — Результат работы последовательного алгоритма Рисунок 3.2 — Работа программы со случайными числами Рисунок 3.3 — Прямой ход, выбор ведущих строк

2. Проведение вычислительных экспериментов Вычисление времени выполнения алгоритма:

Таблица 3.1 — Сравнительная таблица работы последовательного алгоритма


Размер матрицы	Экспериментальное время, с	Теоретическое время, с
	0,15	0,18
	0,1 978	0,1 611
	0,199	0,199
	1,647	1,589 619
	5,89 896	5,362 286
	13,158 849	12,70 743
	26,66 889	24,815 479
	46,434 393	42,876 861

3. Разработка параллельного алгоритма Гаусса Рисунок 3.4 — Определение ранга процесса Рисунок 3.5 — Результат выполнения прямого хода метода Гаусса

4. Проведение вычислительных экспериментов Таблица 3.2 — Сравнение работы последовательного и параллельного алгоритмов


Размер объектов	Последовательный алгоритм, с	Параллельный алгоритм
		2 процесса	4 процесса	8 процессов
		Время, с	ускорение	Время, с	ускорение	Время, с	ускорение
	0,15	0,136	0,110 294	0,625	0,024	0,64 815	0,231
	0,1 978	0,2 086	0,948 226	0,3 529	0,560 499	0,442 513	0,447
	0,199	0,112 197	1,773 666	0,88 939	2,237 489	3,381 095	0,58 857
	1,647	0,879 686	1,872 259	0,618 633	2,662 322	9,32 891	0,176 548
	5,89 896	2,98 725	1,974 713	3,4 487	1,937 344	15,725 795	0,375 114
	13,158 849	7,25 873	1,872 913	5,9 367	2,626 849	24,13 871	0,545 135
	26,66 889	14,22 705	1,858 906	10,231 977	2,547 591	34,96 514	0,764 503
	46,434 393	24,198 062	1,91 893	15,636 958	2,969 529	45,749 477	1,14 971

Вывод:

1. В ходе лабораторной работы были разработаны две программы для решения систем линейных уравнений методом Гаусса.

2. Результаты работы программ совпадают.

3. Параллельный алгоритм выполняется быстрее последовательного.

Лабораторная работа № 4

матрица вектор алгоритм сортировка Параллельные методы сортировки данных Цель работы: разработка параллельной программы, которая выполняет сортировку данных.

1. Реализация последовательного алгоритма сортировки данных Рисунок 4.1 — Задание размера объекта Рисунок 4.2 — Результат сортировки массива

2. Проведение вычислительных экспериментов Вычисление времени выполнения алгоритма:

Таблица 4.1 — Сравнительная таблица работы последовательного алгоритма


Размер матрицы	Экспериментальное время, с	Теоретическое время, с	При использовании стандартных библиотек, с
	0,3	0,3	0,7
	0,35	0,349	0,18
	0,325 979	0,35 249 672	0,1 528
	1,454 637	1,410 057 387	0,2 973
	3,172 682	3,172 682	0,4 271
	5,589 694	5,64 037 056	0,0061
	8,924 028	8,813 123 066	0,8 473

3. Разработка параллельного алгоритма сортировки Рисунок 4.3 — Результат работы параллельной программы

4. Проведение вычислительных экспериментов Таблица 4.2 — Сравнение работы последовательного и параллельного алгоритмов


Размер объектов	Последовательный алгоритм, с	При использовании стандартных библиотек, с	Параллельный алгоритм
			2 процесса
			Время, с	Ускорение 1	Ускорение 2
	0,3	0,7	0,28	0,107 143	0,25
	0,35	0,18	0,38	0,921 053	0,473 684
	0,325 979	0,1 528	0,1112	2,931 466	0,13 741
	1,454 637	0,2 973	0,302 582	4,807 414	0,9 825
	3,172 682	0,4 271	0,690 155	4,597 057	0,6 188
	5,589 694	0,0061	1,219 006	4,585 452	0,5 004
	8,924 028	0,8 473	2,2 792	4,455 794	0,4 231
Параллельный алгоритм
4 процесса	8 процессов
Время, с	Ускорение 1	Ускорение 2	Время, с	Ускорение 1	Ускорение 2
0,54	0,55 556	0,12 963	0,18 494	0,162	0,379
0,61	0,57 377	0,295 082	0,36 119	0,969	0,498
0,86 117	3,785 304	0,17 743	0,33 827	9,636 651	0,45 171
0,90 653	16,4 621	0,32 795	0,92 735	15,68 595	0,32 059
0,201 978	15,70 806	0,21 146	0,167 749	18,91 327	0,25 461
0,355 119	15,74 034	0,17 177	0,228 482	24,46 448	0,26 698
0,541 799	16,4711	0,15 639	0,285 105	31,30 085	0,29 719

В таблице 4.2 «Ускорение 1» соответствует значению ускорения времени выполнения параллельного алгоритма относительно практически полученного времени выполнения последовательного алгоритма, а «Ускорение 2» — ускорение, взятое в сравнении со временем работы последовательного алгоритма при использовании в нем стандартных библиотек.

Вывод:

1. В ходе лабораторной работы были разработаны последовательный и параллельный алгоритмы для сортировки данных.

2. При использовании стандартных библиотек время вычисления алгоритма значительно сокращается.

Индивидуальное задание.

Формулировка:

Дана матрица случайных чисел (равномерно распределенных на интервале [0,r], где r — параметр, передаваемый в функцию), размера N*N. Отсортировать строки матрицы в порядке убывания суммы элементов строк.

Код программы:

#include

#define N 5

int A[N][N];

int B[N][N];

void fill_matrix ()

{

int i, j;

srand (time (NULL));

for (i = 0; i < N; i ++)

for (j = 0; j < N; j ++)

A[i][j]=rand ()%30;

}

void print_matrix ()

{

int i, j;

for (i = 0; i < N; i ++) {

for (j = 0; j < N; j ++)

printf («%d «, A[i][j]);

printf («n»);

} }

int main (int argc, char* argv[])

{

int r, i, j, k, temp, temp1;

int D[N];

MPI_Status st;

MPI_Datatype typ;

MPI_Init (&argc, &argv);

MPI_Comm_rank (MPI_COMM_WORLD, &r);

if (r == 0) {

fill_matrix ();

printf («n Source: n»);

print_matrix ();

printf («n»);

for (i = 0; i < N; i ++)

{

for (j = 0; j < (N); j++)

{ B[i][j]=A[i][j];

}}

MPI_Barrier (MPI_COMM_WORLD);

MPI_Send (A, N*N, MPI_INT, 1, 0, MPI_COMM_WORLD);

}

else if (r == 1)

{

MPI_Barrier (MPI_COMM_WORLD);

MPI_Recv (B, N*N, MPI_INT, 0, 0, MPI_COMM_WORLD, &st);

for (i = 0; i < N; i ++)

{

D[i]=0;

for (j = 0; j < (N); j++)

{

D[i]=D[i]+B[i][j];

} }

for (i = 0; i < N; i ++) {

printf («%d «, D[i]);

printf («n»);

}

for (i = 0; i < N- 1; i++)

{

for (k = i + 1; k < N; k++)

{

for (j=0; j

{

if (D[i] < D[k])

{

temp = D[i];

D[i] = D[k];

D[k] = temp;

temp1 = B[i][j];

B[i][j] = B[k][j];

B[k][j] = temp1;

} } } }

printf («n»);

printf («n Otsortirovannaya: n»);

for (i = 0; i < N; i ++) {

for (j = 0; j < N; j ++)

printf («%d «, B[i][j]);

printf («n»);

}}

MPI_Finalize ();

return 0; }

Результат работы программы:

Вывод: В ходе проделанной работы был разработан алгоритм для сортировки данных. Посчитали сумму элементов строк, а затем отсортировали матрицу по убыванию этой суммы элементов.

Показать весь текст

Заполнить форму текущей работой