График зависимости ускорения и эффективности от количества элементов векторов

Задание

1. Создать пустой проект консольного Windows – приложения в среде Visual С++.

2. Написать последовательную программу, вычисляющую суммы элементов двух векторов Ci=Ai+Bi, где 0<=i<=n.

3. Написать параллельную программу на основе технологии MPI, в которой элементы векторов А и В распределяются по процессам и суммируются, при этом n=10, а число процессов равно двум.

4. Модифицировать программу, написанную в Задании 3 так, чтобы она корректно работала с произвольным количеством элементов (n вводится пользователем с клавиатуры) и процессов.

5. Построить графики зависимости времени выполнения последовательного и параллельного алгоритмов от количества элементов вектора и числа процессов. Проанализировать эффективность параллельного алгоритма.

 

Блок-схема

Начало

i, n, a[], b[], c[]

i = 0, n

a[i] = i, b[i] = i;

c[i] = a[i] + b[i];

i = 0, n

Конец

 

 

 

Текст программы

#include <mpi.h>

#include "stdio.h"

#include <conio.h>

#include "iostream"

#include <time.h>

 

using namespace std;

 

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

{

int nom = 0, kol = 0, n;

MPI_Init(&argc, &argv);

MPI_Comm_rank(MPI_COMM_WORLD, &nom); //функция определения ранга процесса

MPI_Comm_size(MPI_COMM_WORLD, &kol); //ф-ия опред-ия количества процессов

MPI_Status Status;

 

if (nom == 0)

{

printf("Vvedite razmernost:\n");

scanf("%d", &n);

}

 

//всем процессам рассылается величина n

MPI_Bcast(&n,1,MPI_INT,0,MPI_COMM_WORLD);

double *a, *b, *c, *c1, t1, t2, td;

double start, finish, duration, duration1;

a = new double[n];

b = new double[n];

c = new double[n];

c1 = new double[n];

 

int ost = n % kol;

 

if (nom == 0)

{

for ( int i = 0; i < n; i++)

{

a[i] = i;

b[i] = i;

c[i] = 0;

c1[i] = 0;

}

 

for ( int i = 0; i < n; i++)

{

// printf("%.1f ", a[i]);

}

printf("\n");

for ( int i = 0; i < n; i++)

{

//printf("%.1f ", b[i]);

}

printf("\n");

printf("%d\n", ost);

printf("%d\n", n);

}

// рассылка содержимого векторов всем процессам

MPI_Bcast(a,n,MPI_DOUBLE,0,MPI_COMM_WORLD);

MPI_Bcast(b,n,MPI_DOUBLE,0,MPI_COMM_WORLD);

MPI_Bcast(c,n,MPI_DOUBLE,0,MPI_COMM_WORLD);

start = MPI_Wtime(); //функция измерения времени в параллельном алгоритме

 

for (int i = nom*(n/kol); i < (nom + 1)*(n/kol); i++)

{

c[i] = a[i] + b[i];

}

 

for (int i = 0; i < ost; i++)

{

if (nom == i)

{

c[n - ost + i] = a[n - ost + i] + b[n - ost + i];

}

}

finish = MPI_Wtime();

MPI_Reduce(c,c1,n,MPI_DOUBLE,MPI_SUM,0,MPI_COMM_WORLD);

 

if (nom == 0)

{

for (int i = 0; i < n; i++)

{

// printf("%.1f ", c1[i]);

}

duration = finish - start;

printf("Parallel=%f \n", duration);

printf("\n");

}

t1 = clock();

for (int i = 0; i < n; i++)

{

c[i] = a[i] + b[i];

}

t2 = clock();

td = (t2-t1)/double(CLOCKS_PER_SEC);

printf("Posl=%f \n", td);

MPI_Finalize();

return 0;

}

Результаты экспериментов

Таблица 1.

Кол-во элементов векторов	Кол-во процессов/ вычислительных узлов кластера	Время выполнения последовательного алгоритма (T1), сек	Время выполнения параллельного алгоритма (Tp), сек	Ускорение (Sp)	Эффективность (Ep)
		0,003	0,001144	2,62	1,31
		0,005	0,001023	4,88	1,22
		0,11	0,005948	18,49	3,082

График зависимости ускорения и эффективности от количества элементов векторов

 

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