Сортировка Бэтчэра (Ясенков) (Лабораторная работа 2)

Московский Энергетический Институт

(Технический Университет)

Кафедра Прикладной Математики

Отчет по лабораторной работе 2

«MPI »

Выполнил: Ясенков Е.М.

Группа: А-13-03

Москва 2008

Задание

Реализовать параллельный алгоритм сортировки Бэтчэра. Элементами массива являются структуры, для которых определены отношения «> » и «<». Предполагается, что необъодимо сортировать большой массив данных.

Алгоритм

Данная задача крайне не эффективно решается в системах с разделенной памятью, потому что требуется очень большое количество обменов сообщениями. (3*log(n)). Работает это следующим образом: в начале каждого прохода по вектору главный процесс рассылает всем матрицу, потом в каждом процессе объявляется структура, в которой мы передаем количество элементов, требующих перестановку и номера этих элементов. При проходе по циклу (своей части) эта структура заполняется, и потом отсылается главному процессу. Там непосредственно меняются элементы, указанные в структуре.

Реализация

#include

#include "stdlib.h"

#include

#include "iostream"

#include "mpi.h"

#ifdef SEEK_SET

#undef SEEK_SET

#endif

#ifdef SEEK_CUR

#undef SEEK_CUR

#endif

#ifdef SEEK_END

#undef SEEK_END

#endif

struct elem

{

elem () { x = 0; };

elem(double arg) { x = arg; };

double x;

bool operator > (elem el2) { return x > el2.x; }

};

void swap(elem& p1, elem& p2)

{

elem temp = p1;

p1 = p2;

p2 = temp;

};

int main(int argc, char** argv)

{

if(argc < 2)

{

std::cout<<"Wrong number of arguments"<

return 0;

}

// Готовим матрицу для сортировки

int n = atoi(argv[1]);

elem* pA = new elem[n];

for(int i=0; i

int nCurrRank; // ранг текущего процесса

int nProcCount; // Количество процессов

MPI_Status status;

MPI_Init(&argc, &argv);

MPI_Comm_rank(MPI_COMM_WORLD, &nCurrRank);

MPI_Comm_size(MPI_COMM_WORLD, &nProcCount);

double start_time = 0;

if (!nCurrRank) start_time=MPI_Wtime();

// отправим всем процессам вектор для сортировки

int nResult = MPI_Bcast(pA, n*sizeof(elem), MPI_BYTE, 0, MPI_COMM_WORLD);

if(nResult != MPI_SUCCESS) std::cout<

// Устанавливаем начальные значения

int t = log((double)n)/log(2.0);

int p = pow(2.0, (double)(t-1));

int nCurrSize = (n - p)/nProcCount;

while(p > 0)

{

int q = pow(2.0, (double)(t-1));

int r = 0;

int d = p;

while(q >= p)

{

nCurrSize = (n - d)/nProcCount;

for(int i=nCurrRank*nCurrSize; i<(nCurrRank+1)*nCurrSize; i++)

if((i&p) == r) if(pA[i] > pA[d + i]) swap(pA[i], pA[d + i]);

nResult = MPI_Bcast(&pA[nCurrRank*nCurrSize], nCurrSize*sizeof(elem), MPI_BYTE, nCurrRank, MPI_COMM_WORLD);

nResult = MPI_Bcast(&pA[nCurrRank*nCurrSize + d], nCurrSize*sizeof(elem), MPI_BYTE, nCurrRank, MPI_COMM_WORLD);

d = q-p;

q = q/2;

r=p;

}

p = p/2;

}

if(!nCurrRank) std::cout<

MPI_Finalize();

return 0;

}

Тестирование

Зависимость времени вычислений от количества процессов

Зависимость ускорения вычислений от количества процессов

Вывод

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

4