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

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ

РОССИЙСКОЙ ФЕДЕРАЦИИ

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ

БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

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

Факультет прикладной математики и телекоммуникаций

Кафедра радиоэлектронных средств


Лабораторные работы № 1 - 4

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


Киров 2014


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


Параллельные алгоритмы матрично-векторного умножения

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

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


Рисунок 1.1 - Задание размера матрицы


Рисунок 1.2 - Ввод данных простым способом


Рисунок 1.3 - Результат выполнения матрично-векторного умножения


.Проведение вычислительных экспериментов

Вычисление времени выполнения алгоритма:


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

Размер матрицыЭкспериментальное время, сТеоретическое время, с100,0000910,000381000,0001770,039810000,0066243,99820000,01815615,99630000,03923335,99440000,06400563,99250000,10299,9960000,139143,98870000,236195,98680000,258255,98490000,309323,982100000,393399,98

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


Рисунок 1.4 - Печать количества и ранга процессов


Рисунок 1.5 - Распределение данных


Рисунок 1.6 - Результат проверки умножения матрицы на вектор


.Проведение вычислительных экспериментов


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

Размер объектовПоследовательный алгоритм, сПараллельный алгоритм2 процесса4 процесса8 процессовВремя, сускорениеВремя, сускорениеВремя, сускорение100,0000020,0000030,670,0000040,50,0000030,671000,0000450,0000222,0450,0000133,460,0000085,62510000,0039880,002781,43450,0011343,520,0005457,3220000,0166640,0082982,0080,0044783,720,0021167,87530000,0337350,0173841,940,0103143,270,0048067,01940000,0593230,033521,770,0187503,160,0118375,01250000,0946670,0516251,8340,0296023,1980,0157795,9960000,1370,10011,3690,0401653,410,0234065,8570000,1920,10071,910,0558583,440,0275716,9680000,2470,131,90,0742953,330,0354786,9690000,3180,1611,9750,0931283,4150,051376,19100000,3840,2061,8640,1143,370,0620966,184

Вывод:

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

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


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


Параллельные алгоритмы матричного умножения

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

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


Рисунок 2.1 - Задание размера объекта


Рисунок 2.2 - Ввод данных простым способом


Рисунок 2.3 - Результат выполнения матрично-векторного умножения


Рисунок 2.4 - Задание данных с помощью случайного генератора


.Проведение вычислительных экспериментов

Вычисление времени выполнения алгоритма:


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

Размер матрицыЭкспериментальное время, сТеоретическое время, с100,0000090,00000651000,0049490,00685000,8530,853100013,4386,827150054,37423,04642000129,9754,6329852500277,843106,713000483,046184,40169

3.Разработка параллельного алгоритма матричного умножения


Рисунок 2.5 - Определение ранга процесса


.Проведение вычислительных экспериментов


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

Размер объектовПоследовательный алгоритм, сПараллельный алгоритм4 процесса9 процессовВремя, сускорениеВремя, сускорение100,0000090,000050,180,0073620,0011000,0049490,0034431,4370,0230,2155000,8530,2553,3450,3752,275100013,4383,0394,421,8727,178150054,37417,0573,195,8113979,3562000129,9733,233,9121,478956,0512500277,84385,0743,26640,231216,913000483,046130,3733,70556,602548,534

Вывод:

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

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

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


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


Параллельные методы решения систем линейных уравнений

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

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


Рисунок 3.1 - Результат работы последовательного алгоритма


Рисунок 3.2 - Работа программы со случайными числами


Рисунок 3.3 - Прямой ход, выбор ведущих строк


.Проведение вычислительных экспериментов

Вычисление времени выполнения алгоритма:


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

Размер матрицыЭкспериментальное время, сТеоретическое время, с100,0000150,0000181000,0019780,0016115000,1990,19910001,6471,58961915005,898965,362286200013,15884912,70743250026,06688924,815479300046,43439342,876861

3.Разработка параллельного алгоритма Гаусса


Рисунок 3.4 - Определение ранга процесса


Рисунок 3.5 - Результат выполнения прямого хода метода Гаусса


4.Проведение вычислительных экспериментов


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

Размер объектовПоследовательный алгоритм, сПараллельный алгоритм2 процесса4 процесса8 процессовВремя, сускорениеВремя, сускорениеВремя, сускорение100,0000150,0001360,1102940,0006250,0240,0648150,0002311000,0019780,0020860,9482260,0035290,5604990,4425130,004475000,1990,1121971,7736660,0889392,2374893,3810950,05885710001,6470,8796861,8722590,6186332,6623229,328910,17654815005,898962,987251,9747133,044871,93734415,7257950,375114200013,1588497,0258731,8729135,0093672,62684924,138710,545135250026,06688914,0227051,85890610,2319772,54759134,0965140,764503300046,43439324,1980621,9189315,6369582,96952945,7494771,014971

Вывод:

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

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

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


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

матрица вектор алгоритм сортировка

Параллельные методы сортировки данных

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

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


Рисунок 4.1 - Задание размера объекта


Рисунок 4.2 - Результат сортировки массива


.Проведение вычислительных экспериментов

Вычисление времени выполнения алгоритма:



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

Размер матрицыЭкспериментальное время, сТеоретическое время, сПри использовании стандартных библиотек, с100,0000030,00000030,0000071000,0000350,00003490,000018100000,3259790,352496720,001528200001,4546371,4100573870,002973300003,1726823,1726820,004271400005,5896945,640370560,0061500008,9240288,8131230660,008473

.Разработка параллельного алгоритма сортировки


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


.Проведение вычислительных экспериментов


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

Размер объектовПоследовательный алгоритм, сПри использовании стандартных библиотек, сПараллельный алгоритм2 процессаВремя, сУскорение 1Ускорение 2100,0000030,0000070,0000280,1071430,251000,0000350,0000180,0000380,9210530,473684100000,3259790,0015280,11122,9314660,013741200001,4546370,0029730,3025824,8074140,009825300003,1726820,0042710,6901554,5970570,006188400005,5896940,00611,2190064,5854520,005004500008,9240280,0084732,0027924,4557940,004231Параллельный алгоритм4 процесса8 процессовВремя, сУскорение 1Ускорение 2Время, сУскорение 1Ускорение 20,0000540,0555560,129630,0184940,0001620,0003790,0000610,573770,2950820,0361190,0009690,0004980,0861173,7853040,0177430,0338279,6366510,0451710,09065316,046210,0327950,09273515,685950,0320590,20197815,708060,0211460,16774918,913270,0254610,35511915,740340,0171770,22848224,464480,0266980,54179916,47110,0156390,28510531,300850,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; }


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



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


Теги: Параллельные вычисления  Практическое задание  Физика
Просмотров: 22751
Найти в Wikkipedia статьи с фразой: Параллельные вычисления
Назад