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

Разработка параллельной программы, которая выполняет умножение матриц на вектор. Вычисление времени выполнения алгоритма. Создание параллельного алгоритма матричного умножения. Реализация последовательного алгоритма Гаусса. Выполнение сортировки данных.

Рубрика Физика и энергетика
Вид лабораторная работа
Язык русский
Дата добавления 23.12.2014
Размер файла 1,4 M

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.

Размещено на http://www.allbest.ru/

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

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

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

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

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

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

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

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

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

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

Киров 2014

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

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

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

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

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

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

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

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

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

Таблица 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

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

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

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

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

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

Таблица 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

Вывод:

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

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

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

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

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

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

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

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

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

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

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

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

Таблица 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 - Определение ранга процесса

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

Таблица 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

Вывод:

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

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

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

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

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

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

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

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

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

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

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

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

Таблица 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

Вывод:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Таблица 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" - ускорение, взятое в сравнении со временем работы последовательного алгоритма при использовании в нем стандартных библиотек.

Вывод:

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; }

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

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

Размещено на Allbest.ru


Подобные документы

  • Изучение и анализ алгоритма работы специализированного вычислителя. Выбор перечня и объема регистрируемой информации. Разработка функциональной схемы системы. Расчет затрат на комплектующие системы и полуфабрикаты (покупные). Расчет заработной платы.

    дипломная работа [1,2 M], добавлен 15.07.2010

  • Исследование последовательного и параллельного колебательного контура. Получение амплитудно-частотных и фазово-частотнх характеристик. Определение резонансной частоты. Добротности последовательного и параллельного контура, различия между их значениями.

    лабораторная работа [277,5 K], добавлен 16.04.2009

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

    курсовая работа [361,7 K], добавлен 30.01.2016

  • Рассмотрение алгоритма решения задач о равновесии плоской и пространственной систем сил. Нахождение уравнения траектории точки для заданного момента времени; определение ее скорости, касательного и нормального ускорения, а также радиуса кривизны.

    контрольная работа [303,8 K], добавлен 26.04.2012

  • Разработка структурной схемы и алгоритма работы многофункционального бытового устройства. Выбор электрической принципиальной схемы. Разработка чертежа печатной платы. Экономическое обоснование проекта и анализ вредных и опасных факторов при производстве.

    дипломная работа [1,7 M], добавлен 11.07.2014

  • Разработка алгоритма и программы, реализующей расчет нагрузочных потерь активной мощности и электроэнергии. Использование среднеквадратического тока линии. Учет параметров П-образной схемы замещения. Определение суммарных годовых потерь электроэнергии.

    курсовая работа [3,4 M], добавлен 28.08.2013

  • Разработка алгоритма управления режимом реактивной мощности при асимметрии системы электроснабжения промышленного предприятия. Источники реактивной мощности. Адаптивное нечеткое управление синхронного компенсатора с применением нейронной технологии.

    дипломная работа [1,6 M], добавлен 20.05.2017

  • Силовые линии электростатического поля. Поток вектора напряженности. Дифференциальная форма теоремы Остроградского-Гаусса. Вычисление электростатических полей с помощью теоремы Остроградского-Гаусса. Поле бесконечной равномерно заряженной плоскости.

    презентация [2,3 M], добавлен 13.02.2016

  • Биполярный транзистор с резистором в эмиттерной цепи, выбор и обоснование структурной схемы. Разработка принципиальной схемы, её описание и расчёт элементов, расчёт дифференциального усилителя и делителя напряжения. Разработка алгоритма и его описание.

    курсовая работа [1,3 M], добавлен 09.03.2012

  • Разработка структурно-функциональной схемы объекта диагностирования - ручного пылесоса "Спутник ПР-280". Принцип работы устройства. Функциональные модели наиболее встречающихся неисправностей, разработка алгоритма их поиска методом половинного разбиения.

    реферат [1,1 M], добавлен 18.05.2015

Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д.
PPT, PPTX и PDF-файлы представлены только в архивах.
Рекомендуем скачать работу.