Параллельные методы сортировки

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

Ключевые слова: сортировка, параллелизм, пузырьковая сортировка, сортировка включением, сортировка слиянием, сортировка Шелла, быстрая сортировка

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

Существует большое количество алгоритмов сортировки. Каждый из них предлагает свой подход к решению задачи;", однако это различие заключается лишь в том, как именно сравнивать элементы в процессе сортировки. Наиболее простыми методами являются, например, пузырьковая сортировка и сортировка включением. Их трудоемкость (далее в настоящей работе количество необходимых для сортировки операций будет обозначаться через латинскую букву T, а число элементов в неупорядоченном наборе данных — через букву n) измеряется квадратичной зависимостью числа операций, необходимых для проведения сортировки, от числа элементов неупорядоченного набора данных, то есть T ~ n². Для куда более эффективных и быстрых алгоритмов, таких, как сортировка слиянием, сортировка Шелла или быстрая сортировка, число операций, необходимых для проведения сортировки, уже зависит от числа элементов неупорядоченного набора данных через логарифм — T ~ n * log₂ n. Именно это выражение считается минимальной возможным числом операций сортировки (в расчет не берутся частные случаи, когда, например, для выполнения сортировки необходимо всего лишь поменять местами два элемента).

Так как преодолеть границу в n * log₂ n последовательным алгоритмом не представляется возможным, то задача по ускорению процесса сортировки ложится на плечи новых параллельных методов сортировки, которые, на самом деле, являются модифицированными последовательными методами сортировки, но с использованием нескольких, как минимум двух, вычислительных элементов.

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

Основной операцией для параллельных методов сортировки являются так называемая операция «compare-split», которая на русский язык переводится как «сравнить-разделить». Ее суть заключается в том, что сначала производится сортировки внутри выделенных блоков данных, после чего блоки делятся на пары, в рамках каждой из которых происходит слияние блоков. После этого в новом блоке производится сортировка, эффективность которой после проведенной сортировки в блоках значительно превосходит аналогичную процедуру сортировки без разделения на блоки — значение 2 * (n/p) * log₂ (n/p) + 2*(n/p) меньше значения (2n/p) * log₂ (2n/p).

Одним из самых простых методов сортировки является пузырьковая сортировка. На практике еще практически не применяют, но он крайне важен в учебных целях. Алгоритм пузырьковой сортировки заключается в следующем: происходит последовательный проход по набору значений, в ходе которого сравниваются пары смежных значений. Например, если массив необходимо упорядочить по возрастанию, то при сравнении будет восстанавливаться такой порядок, чтобы значение слева было больше значения справа. В итоге после первой итерации наименьший элемент займет последнюю позицию. После этот элемент уже не будет участвовать в сортировке. При использовании параллельного метода в данном алгоритме и использовании двух потоков время выполнения сортировки уменьшается примерно в полтора раза, а при использовании четырех потоков — почти в три раза [1].

Еще одним методом сортировки является сортировка Шелла. Данный алгоритм является очень эффективным и быстрым, и его время сортировки при использовании последовательного метода измеряется как раз выражением T ~ n * log₂ n. Суть сортировки Шелла состоит в том, что на начальном этапе сравниваются не смежные элементы, а элементы, находящиеся на значительном удалении друг от друга. Это позволяет намного быстрее перетащить, например, элементы с более высокими значениями к началу массива в задаче на возрастание. При использовании параллельного метода в данном алгоритме и использовании двух потоков время выполнения сортировки уменьшается примерно в 1,65 раза, а при использовании четырех потоков — примерно в 2,1 раза [1].

Литература:

1. Гергель, В. П. Высокопроизводительные вычисления для многопроцессорных многоядерных систем: Учебник. / В. П. Гергель. — М.: Издательство Московского университета, 2010. — 544 с., илл.