Постановка задачи

Одной из типовых проблем обработки данных является сортировка. Под этим названием подразумевают задачу размещения элементов неупорядоченного набора значений

в порядке монотонного возрастания (или убывания)

Для решения данной проблемы разработано достаточно большое количество алгоритмов сортировки. Такое разнообразие алгоритмов объясняется высокой трудоёмкостью решаемой задачи с одной стороны и большими объёмами входных данных с другой стороны. В итоге возникает необходимость максимально эффективно решать данную проблему обработки данных.

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

В данной работе будут рассмотрены последовательный и параллельный алгоритмы быстрой сортировки, предложенный Хоара (C.A.R. Hoare).

Метод решения

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

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

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

Параллельная схема

Параллельный алгоритм

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

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

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

Обобщенный алгоритм быстрой сортировки

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

Все остальные действия в новом рассматриваемом алгоритме выполняются в соответствии с обычным методом быстрой сортировки.

Реализуемый алгоритм быстрой сортировки

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

1. Распределяем исходный набор данных между процессорами блоками одинакового размера (в случае, если количество элементов в исходном наборе не кратно числу процессоров вычислительной системы размеры блоков различны, но отличаются не более чем на 1);
2. Выполняем сортировку полученных блоков на каждом процессоре при помощи последовательного варианта алгоритма быстрой сортировки;
3. В цикле по i от N до 1 делать:
1. Выбираем ведущие элементы. Разбиваем исходный N – мерный гиперкуб (множество процессоров) на 2^i подгиперкубов. В каждом из образовавшихся подгиперкубов, в рамках процессора с наименьшим номером, выбираем ведущий (средний) элемент и рассылаем его значение всем остальным процессорам подгиперкуба; Заметим, что на i-ой итерации, каждый из подгиперкубов будут образовывать процессоры, в битовых представлениях номеров которых различаются i-ые позиции;
2. На каждом процессоре разделяем имеющийся блок данных на две части с использованием полученного ведущего элемента;
3. Образуем пары процессоров, для которых битовое представление их номеров отличается только в позиции (i+1), и осуществляем взаимообмен данными между этими процессорами; в результате таких пересылок данных, на процессорах, для которых в битовом представлении номера бит позиции (i+1) равен 0, должны оказаться части блоков со значениями, не превышающими значения ведущего элемента; процессоры с номерами, в которых бит (i+1) равен 1, должны собрать, соответственно, все значения данных, превышающие значение ведущего элемента;
4. Пересылаем все блоки массива с каждого процессора на один процессор и собираем там массив из блоков согласно номерам процессоров, от которых эти блоки пришли.

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

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

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

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

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

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

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

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

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

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

Демонстрация

Рассмотрим по шагам работу алгоритма при n = 24 и p = 4.

Результаты вычислительных экспериментов

Конфигурация системы

Процессор - Intel Core 2 Duo E8500 3.16 GHz
Оперативная память - 4 GB
Операционная система - MS Windows 7 x32
Компилятор - MS Visual Studio 2010

Латентность - 12 мкс
Скорость обмена между процессами - 9103879553 байт/c
Время выполнения базовой операции перестановки – 5,6 нс
Размер элемента набора - 8 байт (double)

По результатам вычислительных экспериментов можно сделать вывод о том, что параллельный алгоритм быстрой сортировки позволяет получить ускорение при решении задачи упорядочивания данных.

Об авторе

Работу выполнил студент группы 83-03 Изутов Е.О.