Постановка задачи
Сортировка является одной из типовых проблем обработки данных на ЭВМ и обычно понимается как задача размещения элементов неупорядоченного набора значений S={a1, a2, …, an} в порядке монотонного возрастания или убывания S ~ S’ = { (a′1, a′2, …., a′n): a′1≤ a′2≤ ….≤ a′n }. Сортировка является одним из наиболее часто встречаемых алгоритмов при решении разного рода задач. Но при большом объёме входных данных сортировка может выполняться за достаточно долгое время. Одним из способов уменьшения времени выполнения данной задачи является использование параллельных вычислений. Для этого необходимо модифицировать уже имеющийся последовательный алгоритм сортировки или разработать новые параллельные методы, учитывающие особенности параллельных вычислений.
Основной проблемой при решении данной задачи является то, что большинство известных оптимальных алгоритмов являются последовательными и плохо поддаются распараллеливанию. Поэтому модификация алгоритма сортировки для параллельного вычисления требует серьёзных изменений алгоритма, или отказ от использования от алгоритма в чистом виде в пользу специальной модификации, зачастую имеющей существенные отличия. Одним из таких алгоритмов является и алгоритм пузырьковой сортировки в классическом представлении, поэтому в данной работе рассмотрен его чётно-нечётный вариант.
В данной лабораторной работе требуется реализовать как алгоритм сортировки пузырьком в чётно-нечётном варианте. Алгоритм необходимо реализовать как для однопроцессорных, так и для многопроцессорных вычислительных систем, с использованием библиотеки MPI.
В отчёте изложены методы решения поставленных задач, представлены оценка эффективности, результаты тестовых запусков сортировок и демонстрация работы алгоритма.
Метод решения
Последовательный алгоритм сортировки пузырьком:
Основной идеей последовательного алгоритма пузырьковой сортировки состоит в сравнении и обмене соседних элементов входной последовательности. На каждом шаге алгоритм выполняет операции сравнения-обмена для последовательных пар элементов, в результате чего самый большой элемент последовательности перемещается в конец («всплывает» до нужной позиции как пузырёк в воде, отсюда и название алгоритма). После этого последний элемент в преобразованной последовательности может быть исключен из рассмотрения, и мы переходим к следующему шагу. Проходы по массиву повторяются до тех пор, пока на очередном проходе не окажется, что обмены больше не нужны, что означает — массив отсортирован. Этот алгоритм, очевидно, характеризуется квадратичной зависимостью сложности от объёма входной последовательности, и поэтому редко применяется в практических целях, однако его базовая идея сортировки обменами используется во многих более совершенных алгоритмах, таких как быстрая сортировка или сортировка Шелла.
void BubbleSort(int array_size)
{
int tmp_item;
for(int i = 0; i < array_size; i++)
{
for(int j = 0 ; j < array_size -1-i; j++)
{
if( data_array[j] > data_array [j+1] )
{
tmp_item = data_array [j];
data_array [j] = data_array [j+1];
data_array [j+1] = tmp_item;
}
}
}
}
Последовательный алгоритм чет - нечетной перестановки:
Алгоритм пузырьковой сортировки в прямом виде достаточно сложен для распараллеливания, так как сравнение пар значений массива данных происходит последовательно. В связи с этим для параллельного применения используется не сам этот алгоритм, а его модификация, известная как метод чет-нечетной перестановки. Суть модифицированного алгоритма состоит в разбиении алгоритма на две фазы: чётную и нечётную. На первой – нечетной фазе происходит сравнение элементов с нечетными индексами с их правыми соседями и при необходимости производится перестановка. Аналогично проходит и вторая фаза – четная. Отличие состоит в том, что в данной фазе сравниваются элементы с четными индексами и их правые соседи.
Параллельная схема
Параллельный алгоритм чет-нечетной перестановки:
Основным отличием параллельного алгоритма является то, что для каждой итерации алгоритма операции сравнения-обмена для всех пар элементов являются независимыми и выполняются одновременно. Рассмотрим случай, когда число процессоров p равно числу элементов массива n. Пусть также элементы Si S={a1, a2, …, an}, первоначально располагаются на процессорах Pi. В течение нечетной итерации каждый процессор, имеющий нечетный номер, производит сравнение-обмен своего элемента с элементом, находящимся на процессоре-соседе справа. Аналогично, в течение четной итерации каждый процессор с четным номером производит сравнение-обмен своего элемента с элементом правого соседа. Допустим число процессоров равно p, а число элементов в массиве равно n, где p != n. Теперь разделим исходный набор данных между всеми процессорами. После этого на каждый из них будет приходиться по n/p элементов исходного массива. Далее каждый процессор осуществляет внутреннюю сортировку массива, за время O((n/p)*log(n/p)), при использовании оптимального алгоритма внутренней сортировки, или O((n/p)2) , при использовании последовательной пузырьковой сортировки. Затем процессоры осуществляют p/2 нечетных и p/2 четных итераций, в каждой из которых происходит следующее: смежные процессоры обмениваются своими элементами друг с другом, в результате чего каждый процессор сортирует потом не только свои элементы, но и элементы соседнего процессора. После того, как каждый процессор произвел внутреннюю сортировку (на каждой паре процессоров получаем одинаковые массивы), удвоенный массив делится на 2 части: левый процессор обрабатывает далее только левую часть (с меньшими значениями данных), а правый - только правую (с большими значениями данных). Далее осуществляется очередная итерация. После осуществления последней итерации, происходит сбор данных, в результате, чего имеем отсортированный массив.
Пример программного кода параллельной сортировки пузырьком:
//odd-even phase
for (int i = 1; i < size; i++)
{
if (i%2 == 0)
{
if (process_rank%2 == 1)
{
if (process_rank != (size-1))
{
MPI_Send(&temp_buffer,processor_data_len[process_rank], MPI_INT, process_rank+1, SEND, MPI_COMM_WORLD);
for (int j = 0; j < processor_data_len[process_rank+1]; j++)
{
temp_buffer[j+processor_data_len[process_rank+1]] = temp_buffer[j];
}
MPI_Recv(&temp_buffer, processor_data_len[process_rank+1], MPI_INT, process_rank+1, SEND, MPI_COMM_WORLD,&status);
BubbleSort(processor_data_len[process_rank]+processor_data_len[process_rank+1]);
}
}
if (process_rank%2 == 0)
{
if (process_rank != 0)
{
MPI_Send(&temp_buffer,processor_data_len[process_rank], MPI_INT, process_rank-1, SEND, MPI_COMM_WORLD);
for (int j = 0; j < processor_data_len[process_rank-1]; j++)
{
temp_buffer[j+processor_data_len[process_rank-1]] = temp_buffer[j];
}
MPI_Recv(&temp_buffer, processor_data_len[process_rank-1], MPI_INT, process_rank-1, SEND, MPI_COMM_WORLD,&status);
BubbleSort(processor_data_len[process_rank]+processor_data_len[process_rank-1]);
for (int j = 0; j < processor_data_len[process_rank-1]; j++)
{
temp_buffer[j] = temp_buffer[j+processor_data_len[process_rank-1]];
}
}
}
}
if (i%2 == 1)
{
if (process_rank%2 == 1)
{
MPI_Send(&temp_buffer,processor_data_len[process_rank], MPI_INT, process_rank-1, SEND, MPI_COMM_WORLD);
for (int j = 0; j < processor_data_len[process_rank-1]; j++)
{
temp_buffer[j+processor_data_len[process_rank-1]] = temp_buffer[j];
}
MPI_Recv(&temp_buffer, processor_data_len[process_rank-1], MPI_INT, process_rank-1, SEND, MPI_COMM_WORLD,&status);
BubbleSort(processor_data_len[process_rank]+processor_data_len[process_rank-1]);
for (int j = 0; j < processor_data_len[process_rank-1]; j++)
{
temp_buffer[j] = temp_buffer[j+processor_data_len[process_rank-1]];
}
}
if ( process_rank%2 == 0 )
{
MPI_Send(&temp_buffer,processor_data_len[process_rank], MPI_INT, process_rank+1, SEND, MPI_COMM_WORLD);
for (int j = 0; j < processor_data_len[process_rank+1]; j++)
{
temp_buffer[j+processor_data_len[process_rank+1]] = temp_buffer[j];
}
MPI_Recv(&temp_buffer, processor_data_len[process_rank+1], MPI_INT, process_rank+1, SEND, MPI_COMM_WORLD,&status);
BubbleSort(processor_data_len[process_rank]+processor_data_len[process_rank+1]);
}
}
}
Пример сортировки:
Шаг 0. Разделение массива между процессами
Процесс №1 Процесс №2 Процесс №3 Процесс №4
3 5 9 1 0 1 6 3
Шаг 1. После внутренней сортировки qsort’ом
Процесс №1 Процесс №2 Процесс №3 Процесс №4
3 5 1 9 0 1 3 6
Шаг 1.1. Нечётная перестановка. Обмен данными
Процесс №1 Процесс №2 Процесс №3 Процесс №4
3 5 1 9 0 1 3 6
Шаг 1.2. Нечётная перестановка. После обмена данными
Процесс №1 Процесс №2 Процесс №3 Процесс №4
1 9 3 5 3 5 1 9 3 6 0 1 0 1 3 6
Шаг 1.3. Нечётная перестановка. После внутренней сортировки qsort’ом
Процесс №1 Процесс №2 Процесс №3 Процесс №4
1 3 | 5 9 1 3 | 5 9 0 1 | 3 6 0 1 | 3 6
Шаг 1.4. Нечётная перестановка. После разбиения
Процесс №1 Процесс №2 Процесс №3 Процесс №4
1 3 5 9 0 1 3 6
Шаг 2.1. Чётная перестановка. Обмен данными
Процесс №1 Процесс №2 Процесс №3 Процесс №4
1 3 5 9 0 1 3 6
Шаг 2.2. Чётная перестановка. После обмена данными
Процесс №1 Процесс №2 Процесс №3 Процесс №4
1 3 0 1 5 9 5 9 0 1 3 6
Шаг 2.3. Чётная перестановка. После внутренней сортировки qsort’ом
Процесс №1 Процесс №2 Процесс №3 Процесс №4
1 3 0 1 | 5 9 0 1 | 5 9 3 6
Шаг 2.4. Чётная перестановка. После разбиения
Процесс №1 Процесс №2 Процесс №3 Процесс №4
1 3 0 1 5 9 3 6
Шаг 3.1. Нечётная перестановка. Обмен данными
Процесс №1 Процесс №2 Процесс №3 Процесс №4
1 3 0 1 5 9 3 6
Шаг 3.2. Нечётная перестановка. После обмена данными
Процесс №1 Процесс №2 Процесс №3 Процесс №4
0 1 1 3 1 3 0 1 3 6 5 9 3 6 5 9
Шаг 3.3. Нечётная перестановка. После внутренней сортировки qsort’ом
Процесс №1 Процесс №2 Процесс №3 Процесс №4
0 1 | 1 3 0 1 | 1 3 3 5 | 6 9 3 5 | 6 9
Шаг 3.4. Нечётная перестановка. После разбиения
Процесс №1 Процесс №2 Процесс №3 Процесс №4
0 1 1 3 3 5 6 9
Массив отсортирован!
Процесс №1 Процесс №2 Процесс №3 Процесс №4
0 1 1 3 3 5 6 9
Результаты
Анализ эффективности алгоритма сортировки пузырьком:
При анализе эффективности вначале проведем общую оценку сложности рассмотренного параллельного алгоритма сортировки, а затем дополним полученные соотношения показателями трудоемкости выполняемых коммуникационных операций.
Определим первоначально трудоемкость последовательных вычислений. При рассмотрении данного вопроса алгоритм пузырьковой сортировки позволяет продемонстрировать следующий важный момент. Как уже отмечалось в начале данного раздела, использованный для распараллеливания последовательный метод упорядочивания данных характеризуется квадратичной зависимостью сложности от числа упорядочиваемых данных T1 ~ n2 .
Однако, применение в данной реализации быстрой сортировки в качестве внутренней, означает, что сравнивать производительность параллельного метода следует с оценкой T1 = n log2 n.
Определим сложность параллельного алгоритма упорядочивания данных. Как отмечалось ранее, на начальной стадии работы метода каждый процессор проводит упорядочивание своих блоков данных (размер блоков при равномерном распределении данных является равным n/p). Предположим, что данная начальная сортировка может быть выполнена при помощи быстродействующих алгоритмов упорядочивания данных, тогда трудоемкость начальной стадии вычислений можно определить выражением вида:T1p = (n/p) logp (n/p).
На каждой выполняемой итерации параллельной сортировки взаимодействующие пары процессоров осуществляют передачу блоков между собой, после чего получаемые на каждом процессоре пары блоков объединяются при помощи процедуры слияния. Общее количество итераций не превышает величины p, и, как результат, общее количество операций этой части параллельных вычислений оказывается равным:
T2p = 2p(n/p) = 2n
Рассчитаем показатели эффективности и ускорения параллельного метода сортировки:
Sp = ( n log2 n)/( (n/p) log2 (n/p) + 2n ) = ( p log2 n)/ (log2 (n/p) + 2p) ;
Ep = (n log2 n)/( p( (n/p)log 2(n/p) + 2n) ) = log2 n /( log2 (n/p) + 2p )
Учтем длительность выполняемых вычислительных операций и оценим трудоемкость операции передачи блоков между процессорами. При использовании модели Хокни общее время всех выполняемых в ходе сортировки операций передачи блоков можно оценить при помощи соотношения вида:
Tp (comm) = p(α +w(n/p)/ β)
где α – латентность, β – пропускная способность сети передачи данных, а w есть размер элемента упорядочиваемых данных в байтах. С учетом трудоемкости коммуникационных действий общее время выполнения параллельного алгоритма сортировки определяется следующим выражением:
Tp = ((n/p) log2 (n/p) + 2n) τ + p(α +w(n/p)/ β)
где τ есть время выполнения базовой операции сортировки.
Результаты вычислительных экспериментов
Тестирование реализованных последовательной и параллельной версий алгоритма проводилось на ЭВМ со следующей конфигурацией:
Intel(R) Atom(TM) N570 (1.66 GHz)
Оперативная память – 2,00 GB
Операционная система - MS Windows 7 x32
Компилятор - MS Visual Studio 2008
Скорость обмена между процессами - 682027126 байт/c
Время выполнения базовой операции перестановки - 0.00000005982с
Размер элемента набора - 4 байт (int)
Результаты вычислительных экспериментов по исследованию параллельного алгоритма сортировки пузырьком и сравнение его с последовательным алгоритмом:
размерность Время последовательного Время на 2 Ускорение на 2 Время на 4 Ускорение на 4
алгоритма процессах процессах процессах процессах
10000 0.770529 0.771048 0.982501 0.665714 1.157447
20000 3.204029 2.908284 1.016905 2.795324 1.146210
30000 6.974123 6.879525 1.013575 6.513118 1.070078
40000 12.381598 12.056348 0.898507 11.385702 1.142237
50000 22.194008 21.866282 1.014882 20.513570 1.081918
Оптимальные результаты выполнения алгоритмов были получены на четырёх процессах. Однако в любых случаях ускорение алгоритма близко к единице, в то время как ускорение этого алгоритма на двух процессорах и малом наборе данных и вовсе может оказаться меньше единицы. Это может быть связано с тем, что объём передаваемых данных является достаточно большим, и сильно увеличивает накладные расходы, в то время как прирост скорости распараллеленных вычислений не даёт ожидаемого выигрыша.
Об авторе
Работу выполнил студент группы 8410 Исаев В.Д. |
