Параллельные вычисления
МИНИСТЕРСТВО
ОБРАЗОВАНИЯ И НАУКИ
РОССИЙСКОЙ
ФЕДЕРАЦИИ
ФЕДЕРАЛЬНОЕ
ГОСУДАРСТВЕННОЕ
БЮДЖЕТНОЕ
ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ
ВЫСШЕГО
ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ
"ВЯТСКИЙ
ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ"
Факультет
прикладной математики и телекоммуникаций
Кафедра
радиоэлектронных средств
Лабораторные
работы № 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; }
|
Результат работы программы:
Вывод: В ходе проделанной работы был разработан
алгоритм для сортировки данных. Посчитали сумму элементов строк, а затем
отсортировали матрицу по убыванию этой суммы элементов.