В ходе лабораторной работы необходимо: 1. Выполнить реализацию алгоритма параллельной сортировки слиянием 2. Выполнить реализацию алгоритма последовательной сортировки слиянием 3. Рассчитать теоретическое ускорение и эффективность 4. Провести эксперименты и сравнить ускорение параллельной и последовательной версии.

Описание алгоритма

1. Получение размера сортируемого массива

2. Заполнение массива

3. Вызов рекурсивной процедуры сортировки.

Реализация

Функция, задающая рекурсию:

Реализация параллельной сортировки слиянием была выполнена с помощью MPI.

Описание алгоритма
1. Получение размера сортируемого массива
2. Заполнение массива
3. Распределение массива по всем процессорам
4. Сортировка блока на каждом процессоре
5. Слияние блоков происходит в виде дерева

Реализация алгоритма

Распределение данных:

if(processorId == 0)
{
data = new int[sizeOfData];

for(int i=0; i data[i] = rand();

localData = new int[sizeOfLocalData];

for(int i=0; i localData[i] = data[i];

for(int i=1; i MPI_Send(&data[i*sizeOfLocalData], sizeOfLocalData, MPI_INT, i, 0, MPI_COMM_WORLD);

StartCounter();
}
else
{
localData = new int[sizeOfLocalData];

MPI_Recv(localData, sizeOfLocalData, MPI_INT, 0, 0, MPI_COMM_WORLD, &status);
}

MPI_Barrier(MPI_COMM_WORLD);

Слияние блоков:

n = log2(numOfProcessors) + 1;
int step = 1;

for(int i=0; i {
if((processorId % step) == 0)
{
if(and(processorId, simpleMask(i)) == 0)
{
int *tempData = new int[sizeOfLocalData];
int *commonTempData = new int[2*sizeOfLocalData];

MPI_Recv(tempData, sizeOfLocalData, MPI_INT, MPI_ANY_SOURCE, 0, MPI_COMM_WORLD, &status);

int l=0;
int r=0;

while((l {
if(localData[l] < tempData[r])
{
commonTempData[l+r] = localData[l];
l++;
}
else
{
commonTempData[l+r] = tempData[r];
r++;
}
}

while(l {
commonTempData[l+r] = localData[l];
l++;
}

while(r {
commonTempData[l+r] = tempData[r];
r++;
}

delete[] localData;
delete[] tempData;

sizeOfLocalData = sizeOfLocalData * 2;

localData = new int[sizeOfLocalData];

for(int j=0; j localData[j] = commonTempData[j]
;
delete[] commonTempData;
}
else
{
int dist = processorId - simpleMask(i);

MPI_Send(localData, sizeOfLocalData, MPI_INT, dist, 0, MPI_COMM_WORLD);
}

step = step * 2;
}

MPI_Barrier(MPI_COMM_WORLD);
}

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

p – количество процессоров, n – количество элементов в исходном массиве.
Сортировка каждого блока:
T1(n) = C1 * (n/p) * log2(n/p)
Слияние блоков:
T2(n) = C2 * p * (2n/p) = C2 * 2 * n
В сумме получаем:
T(n) = T1(n) + T2(n) = (n/p) * (C1 * log2(n/p) + C2 * 2log2p – 1)
Ускорение:
Sтеор = n * log2n / (C1 * (n/p) * log2(n/p) + C2 * 2 * n)

Эксперименты проводились на машине со следующими характеристиками: Intel Core i5, 3 Гб ОП, Windows 7. Время измеряется в милисекундах.

Работу выполнил студент группы 8303 Коклюев Сергей