Материал: Параллельные вычисления
Параллельные вычисления
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ
РОССИЙСКОЙ ФЕДЕРАЦИИ
ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ
БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ
ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ
"ВЯТСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ"
Факультет прикладной математики и телекоммуникаций
Кафедра
радиоэлектронных средств
Лабораторные работы № 1 - 4
Параллельные
вычисления
Киров
2014
Лабораторная работа №1
Параллельные алгоритмы матрично-векторного умножения
Цель работы: разработка параллельной программы, которая выполняет умножение матриц на вектор.
. Реализация последовательного алгоритма
умножения матрицы на вектор.
Рисунок 1.1 - Задание размера матрицы
Рисунок 1.2 - Ввод данных простым способом
Рисунок 1.3 - Результат выполнения
матрично-векторного умножения
. Проведение вычислительных экспериментов
Вычисление времени выполнения алгоритма:
Таблица 1.1 - Сравнительная таблица работы
последовательного алгоритма
Размер
матрицы
Экспериментальное
время, с
Теоретическое
время, с
10
0,000091
0,00038
100
0,000177
0,0398
1000
0,006624
3,998
2000
0,018156
15,996
3000
0,039233
35,994
4000
0,064005
63,992
5000
0,102
99,99
6000
0,139
143,988
7000
0,236
195,986
8000
0,258
255,984
9000
0,309
323,982
10000
0,393
399,98
. Разработка параллельного алгоритма
умножения матрицы на вектор
Рисунок 1.4 - Печать количества и ранга
процессов
Рисунок 1.5 - Распределение данных
Рисунок 1.6 - Результат проверки умножения
матрицы на вектор
. Проведение вычислительных экспериментов
Таблица 1.2 - Сравнение времени работы
последовательного и параллельного алгоритмов
Размер
объектов
Последовательный
алгоритм, с
Параллельный
алгоритм
2
процесса
4
процесса
8
процессов
Время,
с
ускорение
Время,
с
ускорение
Время,
с
ускорение
10
0,000002
0,000003
0,67
0,000004
0,5
0,000003
0,67
100
0,000045
0,000022
2,045
0,000013
3,46
0,000008
5,625
1000
0,003988
0,00278
1,4345
0,001134
3,52
0,000545
7,32
2000
0,016664
0,008298
2,008
0,004478
3,72
0,002116
7,875
3000
0,033735
0,017384
1,94
0,010314
3,27
0,004806
7,019
4000
0,059323
0,03352
1,77
0,018750
3,16
0,011837
5,012
5000
0,094667
0,051625
1,834
0,029602
3,198
0,015779
5,99
6000
0,137
0,1001
1,369
0,040165
3,41
0,023406
5,85
7000
0,192
0,1007
1,91
0,055858
3,44
0,027571
6,96
8000
0,247
0,13
1,9
0,074295
3,33
0,035478
6,96
9000
0,318
0,161
1,975
0,093128
3,415
0,05137
6,19
10000
0,384
0,206
1,864
0,114
3,37
0,062096
6,184
Вывод:
. В ходе лабораторной работы были
разработаны 2 алгоритма вычисления произведения матрицы на вектор.
. Выявлено, что последовательный алгоритм
выполняется быстрее, чем последовательный, и с увеличением числа процессов,
время вычисления уменьшается.
Лабораторная работа №2
Параллельные алгоритмы матричного умножения
Цель работы: разработка параллельной программы,
которая выполняет умножение двух матриц.
. Реализация последовательного алгоритма
матричного умножения
Рисунок 2.1 - Задание размера объекта
Рисунок 2.2 - Ввод данных простым способом
Рисунок 2.3 - Результат выполнения
матрично-векторного умножения
Рисунок 2.4 - Задание данных с помощью
случайного генератора
. Проведение вычислительных экспериментов
Вычисление времени выполнения алгоритма:
Таблица 2.1 - Сравнительная таблица работы
последовательного алгоритма
Размер
матрицы
Экспериментальное
время, с
Теоретическое
время, с
10
0,000009
0,0000065
100
0,004949
0,0068
500
0,853
0,853
1000
13,438
6,827
1500
54,374
23,0464
2000
129,97
54,632985
2500
277,843
106,71
3000
483,046
184,40169
3. Разработка параллельного алгоритма
матричного умножения
Рисунок 2.5 - Определение ранга процесса
. Проведение вычислительных экспериментов
Таблица 2.2 - Сравнение работы последовательного
и параллельного алгоритмов
Размер
объектов
Последовательный
алгоритм, с
Параллельный
алгоритм
4
процесса
9
процессов
Время,
с
ускорение
Время,
с
ускорение
10
0,000009
0,00005
0,18
0,007362
0,001
100
0,004949
0,003443
1,437
0,023
0,215
500
0,853
0,255
3,345
0,375
2,275
1000
13,438
3,039
4,42
1,872
7,178
1500
54,374
17,057
3,19
5,811397
9,356
2000
129,97
33,23
3,91
21,47895
6,051
2500
277,843
85,074
3,266
40,23121
6,91
3000
483,046
130,373
3,705
56,60254
8,534
Вывод:
. В ходе лабораторной работы были
реализованы 2 алгоритма вычисление произведения матриц.
. Результаты работы последовательного и
параллельного алгоритма совпадают.
. Ускорение параллельного алгоритма,
относительно последовательного, пропорционально числу выполняемых процессов.
Лабораторная работа №3
Параллельные методы решения систем линейных
уравнений
Цель работы: разработка параллельной программы,
которая выполняет решение системы линейных уравнений методом Гаусса.
. Реализация последовательного алгоритма
Гаусса
Рисунок 3.1 - Результат работы последовательного
алгоритма
Рисунок 3.2 - Работа программы со случайными
числами
Рисунок 3.3 - Прямой ход, выбор ведущих строк
. Проведение вычислительных экспериментов
Вычисление времени выполнения алгоритма:
Таблица 3.1 - Сравнительная таблица работы
последовательного алгоритма
Размер
матрицы
Экспериментальное
время, с
Теоретическое
время, с
10
0,000015
0,000018
100
0,001978
0,001611
500
0,199
0,199
1000
1,647
1,589619
1500
5,89896
5,362286
2000
13,158849
12,70743
2500
26,066889
24,815479
3000
46,434393
42,876861
3. Разработка параллельного алгоритма
Гаусса
Рисунок 3.4 - Определение ранга процесса
Рисунок 3.5 - Результат выполнения прямого хода
метода Гаусса
4. Проведение вычислительных экспериментов
Таблица 3.2 - Сравнение работы последовательного
и параллельного алгоритмов
Размер
объектов
Последовательный
алгоритм, с
Параллельный
алгоритм
2
процесса
4
процесса
8
процессов ускорение
Время,
с
ускорение
Время,
с
ускорение
10
0,000015
0,000136
0,110294
0,000625
0,024
0,064815
0,000231
100
0,001978
0,002086
0,948226
0,003529
0,560499
0,442513
0,00447
500
0,199
0,112197
1,773666
0,088939
2,237489
3,381095
0,058857
1000
1,647
0,879686
1,872259
0,618633
2,662322
9,32891
0,176548
1500
5,89896
2,98725
1,974713
3,04487
1,937344
15,725795
0,375114
2000
13,158849
7,025873
1,872913
5,009367
2,626849
24,13871
0,545135
2500
26,066889
14,022705
1,858906
10,231977
2,547591
34,096514
0,764503
3000
46,434393
24,198062
1,91893
15,636958
2,969529
45,749477
1,014971
Вывод:
. В ходе лабораторной работы были
разработаны две программы для решения систем линейных уравнений методом Гаусса.
. Результаты работы программ совпадают.
. Параллельный алгоритм выполняется
быстрее последовательного.
Лабораторная работа №4
матрица вектор алгоритм
сортировка
Параллельные методы сортировки данных
Цель работы: разработка параллельной программы,
которая выполняет сортировку данных.
. Реализация последовательного алгоритма
сортировки данных
Рисунок 4.1 - Задание размера объекта
Рисунок 4.2 - Результат сортировки массива
. Проведение вычислительных экспериментов
Вычисление времени выполнения алгоритма:
Таблица 4.1 - Сравнительная таблица работы
последовательного алгоритма
Размер
матрицы
Экспериментальное
время, с
Теоретическое
время, с
При
использовании стандартных библиотек, с
10
0,000003
0,0000003
0,000007
100
0,000035
0,0000349
0,000018
10000
0,325979
0,35249672
0,001528
20000
1,454637
1,410057387
0,002973
30000
3,172682
3,172682
0,004271
40000
5,589694
5,64037056
0,0061
50000
8,924028
8,813123066
0,008473
. Разработка параллельного алгоритма
сортировки
Рисунок 4.3 - Результат работы параллельной
программы
. Проведение вычислительных экспериментов
Таблица 4.2 - Сравнение работы последовательного
и параллельного алгоритмов
Размер
объектов
Последовательный
алгоритм, с
При
использовании стандартных библиотек, с
Параллельный
алгоритм
2
процесса
Время,
с
Ускорение
1
Ускорение
2
10
0,000003
0,000007
0,000028
0,107143
0,25
100
0,000035
0,000018
0,000038
0,921053
0,473684
10000
0,325979
0,001528
0,1112
2,931466
0,013741
20000
1,454637
0,002973
0,302582
4,807414
0,009825
30000
3,172682
0,004271
0,690155
4,597057
0,006188
40000
5,589694
0,0061
1,219006
4,585452
0,005004
50000
8,924028
0,008473
2,002792
4,455794
0,004231
Параллельный
алгоритм
4
процесса
8
процессов
Время,
с
Ускорение
1
Ускорение
2
Время,
с
Ускорение
1
Ускорение
2
0,000054
0,055556
0,12963
0,018494
0,000162
0,000379
0,000061
0,57377
0,295082
0,036119
0,000969
0,000498
0,086117
3,785304
0,017743
0,033827
9,636651
0,045171
0,090653
16,04621
0,032795
0,092735
15,68595
0,032059
0,201978
15,70806
0,021146
0,167749
18,91327
0,025461
0,355119
15,74034
0,017177
0,228482
24,46448
0,026698
0,541799
16,4711
0,015639
0,285105
31,30085
0,029719
В таблице 4.2 "Ускорение 1"
соответствует значению ускорения времени выполнения параллельного алгоритма
относительно практически полученного времени выполнения последовательного
алгоритма, а "Ускорение 2" - ускорение, взятое в сравнении со
временем работы последовательного алгоритма при использовании в нем стандартных
библиотек.
Вывод:
. В ходе лабораторной работы были
разработаны последовательный и параллельный алгоритмы для сортировки данных.
. При использовании стандартных библиотек
время вычисления алгоритма значительно сокращается.
Индивидуальное задание.
Формулировка:
Дана матрица случайных чисел (равномерно
распределенных на интервале [0,r] , где r - параметр, передаваемый в функцию),
размера N*N
. Отсортировать строки матрицы в порядке убывания суммы элементов строк.
Код программы:
#include <stdio.h> #include
<stdlib.h> #include <time.h> #include <math.h> #include
<mpi.h> #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<N; 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; }
Результат работы программы:
Вывод: В ходе проделанной работы был разработан
алгоритм для сортировки данных. Посчитали сумму элементов строк, а затем
отсортировали матрицу по убыванию этой суммы элементов.
