Реализация алгоритма чет-нечетной перестановки с использованием MPI

 

Министерство образования  и науки Украины

Харьковский национальный университет имени В. Н. Каразина

Факультет компьютерных наук

 

 

 

 

 

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

по курсу: «Средства программирования многопроцессорных систем»

на тему: «Реализация алгоритма чет-нечетной перестановки с использованием MPI»

 

 

 

 

Выполнил:

студент 5 курса ФКН

группы КСУ-52

Магомедов Р. М.

 

 

 

 

 

Харьков – 2013

Задание:

Необходимо реализовать алгоритм чет-нечетной перестановки с использованием MPI. В начальный момент времени сортируемый массив находится на одном процессе, а затем распределяется поровну другим процессам, которые моделируют движение своей группы частиц. Напишите параллельную программу, оцените показатели эффективности, постройте графики зависимости времени реализации программы от числа процессов и ускорения.

Код программы:

// Process.h

class Process {

private:

int *A; // array

int id; // process id

int n; // array size

int N; // num of processes

public:

int* getA();

int getn();

Process(int A[], int n, int id);

void setN(int Num); // геттер и сеттер для числа процессов

int getN();

void compare_split_min(); // обмен и сравнение с соседним массивом

void compare_split_max();

void printArray(); // вывод массива на печать

int getId(); // геттер айди

void sort (); // пузырьковая сортировка А

void ParallelSort(); // параллельная сортировка исходного массива

};

 

// Process.cpp

#include <iostream>

#include <mpi.h>

#include "Process.h"

using namespace std;

Process::Process(int A[], int n, int id) {

this->A = new int[n];

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

this->A[i] = A[i];

}

this->n = n;

this->id = id;

}

void Process::setN(int Num) {

N = Num;

}

int Process::getN() {

return N;

} 

void Process::compare_split_min() {

MPI_Status status;

int anotherSize;

MPI_Send (&n, 1, MPI_INT, id + 1, 0, MPI_COMM_WORLD); // обмениваемся размерами массивов

MPI_Recv (&anotherSize, 1, MPI_INT, id + 1, 0, MPI_COMM_WORLD, &status);

int *temp = new int[anotherSize];

MPI_Send (A, n, MPI_INT, id + 1, 0, MPI_COMM_WORLD); // обмениваеся массивами

MPI_Recv (temp, anotherSize, MPI_INT, id + 1, 0, MPI_COMM_WORLD, &status);

int j = n - 1;

for(int i = 0; i < anotherSize && j < n; i++) {

if(temp[i] < this->A[j]) {

A[j] = temp[i];

j--;

} else if(i == 0) {

return;

} else {

break;

}

}

sort();

}

void Process::compare_split_max() {

MPI_Status status;

int anotherSize;

MPI_Recv (&anotherSize, 1, MPI_INT, id - 1, 0, MPI_COMM_WORLD, &status);

MPI_Send (&n, 1, MPI_INT, id - 1, 0, MPI_COMM_WORLD); // обмениваемся размерами массивов

int *temp = new int[anotherSize];

MPI_Recv (temp, anotherSize, MPI_INT, id - 1, 0, MPI_COMM_WORLD, &status);

MPI_Send (A, n, MPI_INT, id - 1, 0, MPI_COMM_WORLD); // обмениваеся массивами

int j = 0;

for(int i = anotherSize - 1; i >= 0 && j < n; i--) {

if(temp[i] > this->A[j]) {

A[j] = temp[i];

j++;

}  else if(i == anotherSize - 1) {

return;

} else {

break;

}

}

sort();

}

void Process::printArray() {

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

cout<<A[i]<<" ";

}

cout<<endl;

}

int Process::getId() {

return this->id;

}

void Process::sort () {

int i, j;

for (i = n - 2; i >= 0; i--) {

for (j = 0; j <= i; j++) {

if (A[j] > A[j + 1]) {

swap (A[j], A[j + 1]);

}

}

}

}

void Process::ParallelSort() {

for (int i = 0; i < N; i++) {

if (i % 2 == 1) {    // нечетная итерация

if (id % 2 == 1) {    // нечетный номер процесса

// Cравнение-обмен с процессом — соседом справа

if (id < N - 1) {

this->compare_split_min();

}

} else {

// Cравнение-обмен с процессом — соседом слева

if (id > 0) {

this->compare_split_max();

}

}

} else {    // четная итерация

if(id % 2 == 0) {    // четный номер процесса

// Cравнение-обмен с процессом — соседом справа

if (id < N - 1) {

this->compare_split_min();

}

} else {

if (id > 0) {

this->compare_split_max();

}

}

}

}

}

int* Process::getA() {

return this->A;

}

int Process::getn() {

return this->n;

}

 

 

// Source.cpp

#include "Process.h"

#include "mpi.h"

#include <iostream>

#include <ctime>

#include <fstream>

using namespace std;

void printArray(int arrSize, int *mas) {

for(int i = 0; i < arrSize; i++) {

cout<<mas[i]<<" ";

}

cout<<endl;

}

void sort (int* v, int n)

{

int i, j;

for (i = n - 2; i >= 0; i--)

for (j = 0; j <= i; j++)

if (v[j] > v[j + 1])

swap (v[j], v[j + 1]);

}

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

MPI_Init(&argc, &argv);

int myRank;

int tasks; // number of tasks

int arrSize = 5000; // array size

int MAX = 100; // top of random

double startT, stopT;

MPI_Comm_rank(MPI_COMM_WORLD, &myRank);

MPI_Comm_size(MPI_COMM_WORLD, &tasks);

if(myRank == 0) {

int *mas; // source array

mas = new int[arrSize];

cout<<"Array size: "<<arrSize;

// srand(time(NULL));

for(int i = 0; i < arrSize; i++) {

mas[i] = rand() % MAX; // filling array with random

}

//  cout<<"Initial array: "<<endl;

//  printArray(arrSize, mas); // printing source array

 

int *sendcounts = new int[tasks]; // array with sizes of arrays, sending to each process

 

for(int i = 0; i < tasks; i++) {

sendcounts[i] = arrSize / tasks;

}

 

if(tasks > 1) {

for(int i = 1; i <= arrSize % tasks; i++) {

sendcounts[i]++;

}

}

int recvcount;

MPI_Scatter(sendcounts, 1, MPI_INT, &recvcount, 1, MPI_INT, 0, MPI_COMM_WORLD);

 

int *recvbuf = new int[recvcount];

int *displs;

 

displs = new int[recvcount];

displs[0]=0;

for(int i = 1; i < tasks; i++)

displs[i] = sendcounts[i-1] + displs[i-1];

 

MPI_Scatterv(mas, sendcounts, displs, MPI_INT, recvbuf,

recvcount, MPI_INT, 0, MPI_COMM_WORLD);

 

Process* p = new Process(recvbuf, recvcount, myRank);

p->setN(tasks);

 

// printArray(arrSize, mas);

 

startT = MPI_Wtime();

p->sort();

p->ParallelSort(); // Параллельная сортировка

stopT = MPI_Wtime();

double t2 = stopT - startT;

cout<<" Parallel time: "<<t2;

startT = MPI_Wtime();

sort(mas, arrSize);

stopT = MPI_Wtime();

double t1 = stopT - startT;

cout<<" Linear time: "<<t1;

MPI_Gatherv(p->getA(), p->getn(), MPI_INT, mas, sendcounts, displs, MPI_INT, 0, MPI_COMM_WORLD);

 

// cout<<"\nResult Array: "<<endl;

// printArray(arrSize, mas);

 

cout<<" SpeedUp: "<< t1/t2 << endl;

FILE *out;

fopen_s(&out,"C:\\result.xls","at");

fprintf(out,"%d\t%d\t%f\t%f\t%f\n",tasks, arrSize, t1, t2, t1/t2);

fclose(out);

delete[] recvbuf;

} else {  

int recvcount;

MPI_Scatter(0, 0, 0, &recvcount, 1, MPI_INT, 0, MPI_COMM_WORLD);

int *recvbuf;

recvbuf=new int[recvcount];

MPI_Scatterv(0, 0, 0, 0, recvbuf, recvcount, MPI_INT, 0, MPI_COMM_WORLD);

Process* p = new Process(recvbuf, recvcount, myRank);

p->setN(tasks);

p->sort();

p->ParallelSort();

MPI_Gatherv(p->getA(), p->getn(), MPI_INT, 0, 0, 0, 0, 0, MPI_COMM_WORLD);

delete[] recvbuf;

}

MPI_Finalize();

return 0;

}

/*

#include <fstream>

using namespace std;

 

void main() {

ofstream ofs("executor.bat");

ofs<<"D:\n";

ofs<<"cd D:\\lab4_MPI\\Debug \n";

 

for(int i = 2; i < 100; i *= 2) {

ofs<<"mpiexec -n "<<i<<" lab4_MPI.exe\n";

}

ofs<<"pause\n";

ofstream res("C:\\result.xls");

res<<"Num of processes\tArraySize\tLinear time\tParal time\tSpeedUp\n";

}*/

 

Анализ  эффективности

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

Определим первоначально  трудоемкость последовательных вычислений. При рассмотрении данного вопроса  алгоритм пузырьковой сортировки позволяет продемонстрировать следующий важный момент. Использованный для распараллеливания последовательный метод упорядочивания данных характеризуется квадратичной зависимостью сложности от числа упорядочиваемых данных, т.е. T1~n2. Однако применение подобной оценки сложности последовательного алгоритма приведет к искажению исходного целевого назначения критериев качества параллельных вычислений – показатели эффективности в этом случае будут характеризовать используемый способ параллельного выполнения данного конкретного метода сортировки, а не результативность использования параллелизма для задачи упорядочивания данных в целом как таковой. Различие состоит в том, что для сортировки могут быть применены более эффективные последовательные алгоритмы, трудоемкость которых имеет порядок

(

и чтобы сравнить, насколько  быстрее могут быть упорядочены  данные при использовании параллельных вычислений, в обязательном порядке  должна применяться именно эта оценка сложности. Как основной результат  приведенных рассуждений, можно  сформулировать утверждение о том, что при определении показателей ускорения и эффективности параллельных вычислений в качестве оценки сложности последовательного способа решения рассматриваемой задачи следует использовать трудоемкость наилучших последовательных алгоритмов. Параллельные методы решения задач должны сравниваться с наиболее быстродействующими последовательными способами вычислений!

Определим теперь сложность  рассмотренного параллельного алгоритма упорядочивания данных. Как отмечалось ранее, на начальной стадии работы метода каждый процессор проводит упорядочивание своих блоков данных (размер блоков при равномерном распределении данных равен n/p ). Предположим, что данная начальная сортировка может быть выполнена при помощи быстродействующих алгоритмов упорядочивания данных, тогда трудоемкость начальной стадии вычислений можно определить выражением вида:

(

Далее, на каждой выполняемой итерации параллельной сортировки взаимодействующие пары процессоров осуществляют передачу блоков между собой, после чего получаемые на каждом процессоре пары блоков объединяются при помощи процедуры слияния. Общее количество итераций не превышает величины p, и, как результат, общее количество операций этой части параллельных вычислений оказывается равным

С учетом полученных соотношений показатели эффективности и ускорения параллельного метода сортировки имеют вид:

 

 

Расширим приведенные выражения  – учтем длительность выполняемых  вычислительных операций и оценим трудоемкость операции передачи блоков между процессорами. При использовании модели Хокни общее время всех выполняемых в ходе сортировки операций передачи блоков можно оценить при помощи соотношения вида:

 

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

С учетом трудоемкости коммуникационных действий общее время выполнения параллельного алгоритма сортировки определяется следующим выражением:

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

 

 

 

 

Результаты выполнения программы:

 

Num of processes	ArraySize	Linear time	Paral time	SpeedUp
1	5000	0.932999	0.975091	0.956833
2	5000	0.942038	0.538954	1.747903
4	5000	0.945421	0.453123	2.086458
8	5000	0.941413	0.431964	2.179377
16	5000	0.944634	0.398605	2.36985
32	5000	0.987632	0.536894	1.839528
64	5000	1.045225	1.871174	0.558593
1	10000	3.80766	3.832309	0.993568
2	10000	3.822126	2.364367	1.616554
4	10000	3.833119	1.844534	2.078097
8	10000	3.816167	1.683738	2.266485
16	10000	3.823516	1.681379	2.274036
32	10000	3.835184	1.866848	2.054363
64	10000	3.8787	2.639561	1.469449
1	19998	15.183987	15.155715	1.001865
2	19998	15.165118	8.582241	1.767035
4	19998	15.251164	7.457504	2.045076
8	19998	15.230511	6.893685	2.209342
16	19998	15.220257	6.729888	2.261591
32	19998	15.169219	6.835443	2.219201
64	19998	15.266993	8.848571	1.725363

 

Выводы:

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