Сортировка является одной из типовых проблем обработки данных и обычно понимается как задача размещения элементов неупорядоченного набора значений в порядке монотонного возрастания или убывания. В данной работе необходимо реализовать алгоритм сортировки «пузырьком». Его последовательную версию для однопроцессорных систем, и параллельную – для многопроцессорных систем, используя стандарт MPI и OpenMP. А также, вычислить время его работы для обоих случаев, протестировать и сравнить ускорение параллельного и последовательного алгоритма.

Алгоритм пузырьковой сортировки в прямом виде достаточно сложен для распараллеливания – сравнение пар значений упорядочиваемого набора данных происходит строго последовательно. В связи с этим для параллельного применения используется не сам этот алгоритм, а его модификация, известная в литературе как метод чет-нечетной перестановки ( the odd-even transposition method). Суть модификации состоит в том, что в алгоритм сортировки вводятся два разных правила выполнения итераций метода: в зависимости от четности или нечетности номера итерации сортировки для обработки выбираются элементы с четными или нечетными индексами соответственно, сравнение выделяемых значений всегда осуществляется с их правыми соседними элементами. Таким образом, на всех нечетных итерациях сравниваются пары

(a1, a2), (a3, a4), ..., (an-1,an) (при четном n),

а на четных итерациях обрабатываются элементы

(a2, a3), (a4, a5), ..., (an-2,an-1).

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

void SerialBubbleSort(int* ar, int size)
{
	for (int i = 0; i < size; i++)
	{
		if (i % 2 == 0)
		{
			for (int j = 0; j < size; j += 2)
				if (j < size - 1)
					if(ar[j] > ar[j+1])
					{
						int v = ar[j];
						ar[j] = ar[j+1];
						ar[j+1] = v;
					}
		}
		else
		{
			for (int j = 1; j < size; j += 2)
				if (j < size - 1)
					if(ar[j] > ar[j+1])
					{
						int v = ar[j];
						ar[j] = ar[j+1];
						ar[j+1] = v;
					}
		}
	}
}
        

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

OpenMP

void ParallelBubbleSort(int* ar, int size)
{
	for (int i = 0; i < size; i++)
		{
			int v = 0;
			if (i % 2 == 0)
			{
				#pragma omp parallel for private(v)
				for (int j = 0; j < size; j += 2)
					if (j < size - 1)
						if(ar[j] > ar[j+1])
						{
							v = ar[j];
							ar[j] = ar[j+1];
							ar[j+1] = v;
						}
			}
			else
			{
				#pragma omp parallel for private(v)
				for (int j = 1; j < size; j += 2)
					if (j < size - 1)
						if(ar[j] > ar[j+1])
						{
							v = ar[j];
							ar[j] = ar[j+1];
							ar[j+1] = v;
						}
			}	
		}
}        
        

MPI

#define N кол-во элементов

int n = N;
int id, p;
int s;

MPI_Init(&argc, &argv);
MPI_Comm_rank(MPI_COMM_WORLD, &id);
MPI_Comm_size(MPI_COMM_WORLD, &p);

if (id == 0)
{
    s = n / p;

    MPI_Bcast(&s, 1, MPI_INT, 0, MPI_COMM_WORLD);
    chunk = (int *)malloc(s * sizeof(int));
    MPI_Scatter(data, s, MPI_INT, chunk, s, MPI_INT, 0, MPI_COMM_WORLD);

    sort(chunk,s);
}
else
{
    MPI_Bcast(&s, 1, MPI_INT, 0, MPI_COMM_WORLD);
    chunk = (int *)malloc(s * sizeof(int));
    MPI_Scatter(data, s, MPI_INT, chunk, s, MPI_INT, 0, MPI_COMM_WORLD);

    sort(chunk, s);
}

step = 1;
 
while (step < p)
{
    if (id % (2 * step) == 0)
    {
        if (id + step < p)
        {
            MPI_Recv(&m, 1, MPI_INT, id + step, 0, MPI_COMM_WORLD, &status);
            other = (int *)malloc(m * sizeof(int));
            MPI_Recv(other, m, MPI_INT, id+step, 0, MPI_COMM_WORLD, &status);
            chunk = merge(chunk, s, other, m);
            s = s + m;
        }
    }
    else
    {
        int near = id - step;
        MPI_Send(&s, 1, MPI_INT, near, 0, MPI_COMM_WORLD);
        MPI_Send(chunk, s, MPI_INT, near, 0, MPI_COMM_WORLD);
        break;
    }
    step = step * 2;
}
        

Трудоемкость последовательной версии пузырьковой сортировки O(n^2).

Параллельный алгоритм состоит из 2-х этапов. На первом каждый узел сортирует свою часть данных. Трудоемкость этой операции O((n / p)^2). На втором этапе происходят обмены между процессорами. При этом части сортируемых данных сливаются в единый массив за время O(2 * n / p). Таких итераций не более p. В итоге имеем оценку времени параллельной версии O((n / p)^2 + 2 * n)

Ускорение и эффективность:

S = (n * p^2) / (n + 2 * p^2)

E = (n * p) / (n + 2 * p^2)

Тестовая конфигурация (MPI):
Core 2 Duo E8300 @2.8 Ghz
4 Gb RAM DDR2 800Mhz

Тестовая конфигурация (OpenMP):
Intel Core i7 Q740 @1,73GHz
8 Gb RAM DDR3 1333Mhz

Выполнили студенты группы 83-03: Минеев Александр и Вихирев Алексей