Постановка задачи
Сортировка – это процесс упорядочивания информации по определенному признаку. Основное назначение сортировки – облегчить процесс поиска данных. Информационные данные сортируются в целях облегчения последующей обработки данных: поиска, добавления или исключения объектов. В настоящее время известно множество алгоритмов сортировки, свойства которых достаточно хорошо изучены. Пузырьковая сортировка сама по себе является достаточно медленным алгоритмом сортировки, однако может быть ускорена при помощи распараллеливания. В прямом виде он достаточно сложен для этого, в связи с чем для параллельного применения используется модификация этого алгоритма – метод чет-нечетной перестановки.
Метод решения
Алгоритм состоит из повторяющихся проходов по сортируемому массиву. За каждый проход элементы последовательно сравниваются попарно и, если порядок в паре неверный, выполняется обмен элементов. Проходы по массиву повторяются N-1 раз. При каждом проходе алгоритма по внутреннему циклу, очередной наибольший элемент массива ставится на своё место в конце массива рядом с предыдущим наибольшим элементом, а наименьший элемент перемещается на одну позицию к началу массива.
Суть модификации состоит в том, что в алгоритм сортировки вводятся два разных правила выполнения итераций метода – в зависимости от четности или нечетности номера итерации сортировки для обработки выбираются элементы с четными или нечетными индексами соответственно, сравнение выделяемых значений всегда осуществляется с их правыми соседними элементами. Таким образом, на всех нечетных итерациях сравниваются пары
(a1, a2), (a3, a3), ..., (an-1,an) (при четном n),
а на четных итерациях обрабатываются элементы
(a2, a3), (a4, a5), ..., (an-2,an-1).
После n- кратного повторения итераций сортировки исходный набор данных оказывается упорядоченным.
На количестве процессоров p модификация работает следующим образом: массив делится на блоки размера n/p, которые распределяются по процессорам. На этапе предобработки каждый процессор упорядочивает блок последовательной сортировкой, после чего на нечётных итерациях процессоры с нечётными номерами обмениваются блоками с соседними процессорами справа и сортируют их, после чего на процессе с меньшим номером остается n/p первых упорядоченных элементов объединенного блока, а на процессе с большим номером остается n/p последних упорядоченных элементов объединенного блока. На чётных итерациях процессоры с чётными номерами производят такой же обмен. После выполнения этих шагов последовательность оказывается отсортированной.
Анализ эффективности
Определим эффективность последовательной и параллельной версии.
Трудоемкость последовательной версии пузырьковой сортировки 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)
Результаты экспериментов
OpenMP:
MPI:
Конфигурация: Intel Core i7-2630QM CPU
@ 2.00Ghz
4 Gb RAM
Код программы
OpenMP:
void ParallelSort(double *A, int N)
{
int tid;
int exch = 1, start = 0, i;
double temp;
while(exch || start)
{
exch = 0;
#pragma omp parallel for private(temp)
for(i = start; i < N - 1; i += 2)
{
if(A[i] > A[i + 1])
{
temp = A[i];
A[i] = A[i + 1];
A[i + 1] = temp;
exch = 1;
}
}
if(start == 0)
start = 1;
else start = 0;
}
}
MPI:
void ParallelBubble(double *pProcData, int BlockSize) {
// Local sorting the process data
SerialBubbleSort(pProcData, BlockSize);
int Offset;
split_mode SplitMode;
for(int i = 0; i < ProcNum; i++) {
if((i % 2) == 1) {
if((ProcRank % 2) == 1) {
Offset = 1;
SplitMode = KeepFirstHalf;
}
else {
Offset = -1;
SplitMode = KeepSecondHalf;
}
}
else {
if((ProcRank % 2) == 1) {
Offset = -1;
SplitMode = KeepSecondHalf;
}
else {
Offset = 1;
SplitMode = KeepFirstHalf;
}
}
// Check the first and last processes
if((ProcRank == ProcNum - 1) && (Offset == 1)) continue;
if((ProcRank == 0 ) && (Offset == -1)) continue;
MPI_Status status;
int DualBlockSize;
MPI_Sendrecv(&BlockSize, 1, MPI_INT, ProcRank + Offset, 0, &DualBlockSize, 1, MPI_INT, ProcRank + Offset, 0, MPI_COMM_WORLD, &status);
double *pDualData = new double[DualBlockSize];
double *pMergedData = new double[BlockSize + DualBlockSize];
// Data exchange
ExchangeData(pProcData, BlockSize, ProcRank + Offset, pDualData, DualBlockSize);
// Data merging
merge(pProcData, pProcData + BlockSize, pDualData, pDualData + DualBlockSize, pMergedData);
// Data splitting
if(SplitMode == KeepFirstHalf)
copy(pMergedData, pMergedData + BlockSize, pProcData);
else
copy(pMergedData + BlockSize, pMergedData + BlockSize + DualBlockSize, pProcData);
delete []pDualData;
delete []pMergedData;
}
}
Об авторах
Мельников И.Д. и Никитин А.И.
группа 8410
