Автор работы: Пользователь скрыл имя, 13 Декабря 2013 в 13:29, лабораторная работа
Необходимо реализовать алгоритм чет-нечетной перестановки с использованием 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",
fprintf(out,"%d\t%d\t%f\t%f\t%
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. Однако применение подобной оценки сложности последовательного алгоритма приведет к искажению исходного целевого назначения критериев качества параллельных вычислений – показатели эффективности в этом случае будут характеризовать используемый способ параллельного выполнения данного конкретного метода сортировки, а не результативность использования параллелизма для задачи упорядочивания данных в целом как таковой. Различие состоит в том, что для сортировки могут быть применены более эффективные последовательные алгоритмы, трудоемкость которых имеет порядок |
( |
и чтобы сравнить, насколько
быстрее могут быть упорядочены
данные при использовании параллельных
вычислений, в обязательном порядке
должна применяться именно эта оценка
сложности. Как основной результат
приведенных рассуждений, можно
сформулировать утверждение о том,
что при определении
Определим теперь сложность
рассмотренного параллельного алгоритма упоряд |
( |
Далее, на каждой выполняемой итерации
параллельной сортировки взаимо
С учетом полученных соотношений показатели эффекти
Расширим приведенные
где – латентность, – пропускная способность сети передачи данных, а 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, оценил его время выполнения при различном числе процессов, определил зависимость ускорения от числа процессов.
Информация о работе Реализация алгоритма чет-нечетной перестановки с использованием MPI