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

Предположим дана последовательность чисел (A1, A2, ..., An). Необходимо произвести сортировку элементов данной последовательности по возрастанию, т.е. упорядочить элементы таким образом, что для любых i, j = 1..n (i < j) выполняется соотношение Аi < = Аj.

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

При общем рассмотрении алгоритма быстрой сортировки, предложенной Хоаром (Hoare C.A.R.), прежде всего следует отметить, что этот метод основывается на последовательном разделении сортируемого набора данных на блоки меньшего размера таким образом, что между значениями разных блоков обеспечивается отношение упорядоченности (для любой пары блоков все значения одного из этих блоков не превышают значений другого блока). На первой итерации метода осуществляется деление исходного набора данных на первые две части – для организации такого деления выбирается некоторый ведущий элемент и все значения набора, меньшие ведущего элемента, переносятся в первый формируемый блок, все остальные значения образуют второй блок набора. На второй итерации сортировки описанные правила применяются рекурсивно для обоих сформированных блоков и т.д. При надлежащем выборе ведущих элементов после выполнения log2n итераций исходный массив данных оказывается упорядоченным.

Эффективность быстрой сортировки в значительной степени определяется правильностью выбора ведущих элементов при формировании блоков. В худшем случае трудоемкость метода имеет тот же порядок сложности, что и пузырьковая сортировка (т.е. T1~n2). При оптимальном выборе ведущих элементов, когда разделение каждого блока происходит на равные по размеру части, трудоемкость алгоритма совпадает с быстродействием наиболее эффективных способов сортировки (T1~nlog2n). В среднем случае количество операций, выполняемых алгоритмом быстрой сортировки, определяется выражением:

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

void SerialQuickSort(double *data, int l, int r) {
	if (l < r) {
		double pivot=data[l];
		int p = l;
		for (int i=l+1; i < r; i++)
			if (data[i] < pivot) {
				p++;
				swap(data[i],data[p]);
			}
		swap(data[l],data[p]);

		SerialQuickSort(data,l,p);
		SerialQuickSort(data,p+1,r);
	}
}

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

1) выбрать каким-либо образом ведущий элемент и разослать его по всем процессорам системы (например, в качестве ведущего элемента можно взять среднее арифметическое элементов, расположенных на выбранном ведущем процессоре);

2) разделить на каждом процессоре имеющийся блок данных на две части с использованием полученного ведущего элемента;

3) образовать пары процессоров, для которых битовое представление номеров отличается только в позиции N, и осуществить взаимообмен данными между этими процессорами; в результате таких пересылок данных на процессорах, для которых в битовом представлении номера бит позиции N равен 0, должны оказаться части блоков со значениями, меньшими ведущего элемента; процессоры с номерами, в которых бит N равен 1, должны собрать, соответственно, все значения данных, превышающие значение ведущего элемента.

В результате выполнения такой итерации сортировки исходный набор оказывается разделенным на две части, одна из которых (со значениями меньшими, чем значение ведущего элемента) располагается на процессорах, в битовом представлении номеров которых бит N равен 0. Таких процессоров всего p/2 и, таким образом, исходный N -мерный гиперкуб также оказывается разделенным на два гиперкуба размерности N-1. К этим подгиперкубам, в свою очередь, может быть параллельно применена описанная выше процедура. После N -кратного повторения подобных итераций для завершения сортировки достаточно упорядочить блоки данных, получившиеся на каждом отдельном процессоре вычислительной системы.

Для пояснения на рисунке представлен пример упорядочивания данных при n=16, p=4 (т.е. блок каждого процессора содержит 4 элемента). На этом рисунке процессоры изображены в виде прямоугольников, внутри которых показано содержимое упорядочиваемых блоков данных; значения блоков приводятся в начале и при завершении каждой итерации сортировки. Взаимодействующие пары процессоров соединены двунаправленными стрелками. Для разделения данных выбирались наилучшие значения ведущих элементов: на первой итерации для всех процессоров использовалось значение 0, на второй итерации для пары процессоров 0, 1 ведущий элемент равен -5, для пары процессоров 2, 3 это значение было принято равным 4.

void HyperQuickSort (double *Data, int Count) {
	
	localSort(Data,0,Count);

	int HypercubeDim = (int)ceil(log((double)ProcNum)/log(2.0));
	int Mask = ProcNum;
	for (int i=HypercubeDim; i>0; i--) {
		double Pivot = Data[Count/2];
		PivotDistribution(Data,Count,HypercubeDim, Mask, i, &Pivot);

		int pos = 0; while ((pos> (i-1) ) == 0 ) { // старший бит = 0  
			send = & Data[pos+1]; 
			scount = Count - pos - 1; 
			if ( scount < 0 ) scount = 0; 
			CommProcRank = ProcRank + Mask;
			local = & Data[0]; 
			lcount = pos + 1;  
		} else { // старший бит = 1 
			send = & Data[0]; 
			scount = pos + 1; 
			if ( scount > Count ) scount = pos; 
			CommProcRank = ProcRank - Mask; 
			local = & Data[pos+1]; 
			lcount = Count - pos - 1;  
			if ( lcount < 0 ) lcount = 0; 
		}

		MPI_Status state;
		MPI_Sendrecv(&scount, 1, MPI_INT,CommProcRank,0,
					 &rcount, 1, MPI_INT, CommProcRank,0,
					 MPI_COMM_WORLD, &state);

		recv = new double[rcount];
		MPI_Sendrecv(send,scount,MPI_DOUBLE,CommProcRank,0,
					 recv,rcount,MPI_DOUBLE,CommProcRank,0,
					 MPI_COMM_WORLD, &state);

		double *merged = Merge(local, lcount, recv, rcount);
		delete[] local;
		delete[] recv;
		Data = merged;
		Count = lcount+rcount;
	}
}

Оценим трудоемкость рассмотренного параллельного метода. Пусть у нас имеется N - мерный гиперкуб состоящий из p=2^N процессоров, где p < n.

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

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

При завершении вычислений процессоры выполняет сортировку своих блоков, что может быть выполнено при использовании быстрых алгоритмов за (n/p)log₂(n/p) операций.

Таким образом, общее время вычислений параллельного алгоритма быстрой сортировки составляет:

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

Рассмотрим теперь сложность выполняемых коммуникационных операций. Общее количество межпроцессорных обменов для рассылки ведущего элемента на N-мерном гиперкубе может быть ограничено оценкой:

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

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

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

Процессор AMD Phenom II X4 955 3.2 GHz

Число ядер 4

Объем кэша L1 128 Кб

Объем кэша L2 2048 Кб

Объем кэша L3 6144 КБ

RAM 4Gb, DDR3 4096 Mb, 1333 MHz

Windows 7 x32

MS Visual Studio 2010