Участница:Полина Кривуля/Сеть битонной сортировки

Автор: Полина Кривуля

1 Свойства и структура алгоритмов

1.1 Общее описание алгоритма

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

Битонной последовательностью называют последовательность, которая монотонно не убывает, а затем монотонно не возрастает, либо приводится к такому виду в результате циклического сдвига. Пример такой последовательности – {8, 10, 16, 12, 4, -2, -8} . Любая последовательность, входящая в битонную, любая последовательность состоящая из одного или двух элементов, а также любая монотонная последовательность также является битонной. Например, последовательности {3,5,10,4,1}, {1,5}, {10,14,5,-1,-4} являются битонными, а {4,6,1,9,2} не является. Каждое множество неотсортированных элементов можно считать множеством битонных последовательностей, состоящих из двух элементов. Процесс битонного слияния преобразует битонную последовательность в полностью отсортированную последовательность. Алгоритм битонной сортировки состоит из применения битонных преобразований до тех пор, пока множество не будет полностью отсортировано .

Время работы алгоритма составляет [math] O(log^2(n))[/math] (в случае использования параллелизма).

1.2 Математическое описание алгоритма

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

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

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

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

1.3 Вычислительное ядро алгоритма

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

1. Разбиение исходного массива на битонные последовательности.

2. Сортировка каждой битонной последовательности в порядке возрастания.

3. Объединение отсортированных битонных последовательностей.

1.4 Макроструктура алгоритма

В начале программы генерируется массив случайных чисел, но время генерации массива не засекается.

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

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

1.5 Схема реализации последовательного алгоритма

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

Сложность такой реализации [math] O(nlog^2n)[/math] поскольку при построении битонной последовательности мы использовали сортировку, работающую за [math] O(nlogn)[/math], а всего уровней было [math] logn[/math].

1.6 Последовательная сложность алгоритма

Сложность алгоритма битонной сортировки зависит от количества элементов в массиве. Обозначим эту величину как [math]n[/math].

В каждом шаге рекурсивной сортировки, массив разбивается на две части, и каждая из этих частей сортируется отдельно. Таким образом, каждый шаг рекурсии занимает [math]O(nlog(n))[/math] времени. Всего шагов рекурсии [math]log(n)[/math], так как на каждом шаге размер массива уменьшается вдвое.

Таким образом, общая сложность последовательного алгоритма битонной сортировки составляет [math]O(n log^2(n))[/math].

1.7 Информационный граф

рис.1: Информационный граф битонной сортировки

На рисунке 1 изображена работа битонной сортировки. Красные элементы соответствуют возрастающей последовательности, зеленые – убывающей. Операции min и max соответствуют операциям сравнения двух чисел и, при необходимости, обмену местами двух чисел. Можно заметить, что работу алгоритма можно представить в виде выполнения двух шагов: создание битонных последовательностей и их слияние.

рис.2: Битонная сортировка для 16 элементов

На рисунке 2 изображена битонная сортировочная сеть для 16 элементов, которая сортирует множество по возрастанию. Красные прямоугольники скомбинированы в зеленые и голубые прямоугольники. В синих прямоугольниках стрелки компараторов направлены вниз (создают возрастающие последовательности), в зеленых — вверх (создают убывающие последовательности). Каждый из таких прямоугольников имеет одинаковую структуру: красный прямоугольник применяется ко всей последовательности, затем к каждой половине полученных результатов и так далее. Если на входы такого прямоугольника подается битонная последовательность, то на выходе она преобразуется в полностью отсортированную. Объединенные результаты синего и зеленого прямоугольника является битонной последовательностью. Каждый столбец синих и зеленых прямоугольников принимает N отсортированных последовательностей (на самом первом шаге 16 отсортированных последовательностей, состоящих из 1 элемента) и преобразует их в N/2 отсортированных последовательностей. .

1.8 Ресурс параллелизма алгоритма

Алгоритм дает большой выигрыш при использовании параллелизма. В общем случае можно распараллелить данный алгоритм на любое число процессов являющееся степенью числа 2. Однако следует учитывать накладные расходы на создание MPI процессов и обмен сообщениями между ними. Если их будет достаточно много для сравнительно небольшой длины массива, то выигрыш в производительности будет очень маленьким, либо может отсутствовать вовсе.

рис.3: Битонная сортировочная сеть

На рисунке 3 каждый рабочий поток нарисован в виде вертикальной линии, начальная и конечная точки обозначают индексы текущей пары сортируемых элементов. Все цветные блоки, находящиеся в одном столбце, образуют шаг, который можно выполнять параллельно. Из диаграммы видно, что количество потоков на шаг постоянно и всегда равно [math] n/2[/math], где [math] n[/math] — количество сортируемых элементов .

При последовательной реализации каждый шаг рекурсии занимает [math]O(nlog(n))[/math] времени, а всего шагов рекурсии [math]log(n)[/math].

В параллельной реализации временная сложность алгоритма гораздо меньше - [math]O(log^2n)[/math].

1.9 Входные и выходные данные алгоритма

Исходные данные: одномерный массив [math]A[/math], содержащий [math]n[/math] элементов, [math]|A|=n[/math].

Выходные данные: упорядоченный массив [math]B=sort(A)[/math].

1.10 Свойства алгоритма

Временная сложность алгоритма:

• При последовательной реализации [math]O(nlog^2(n))[/math]
• При параллельной реализации [math]O(log^2(n))[/math]

Использование памяти:

• Для последовательной реализации в худшем случае [math]O(nlog^2(n))[/math]
• В случае использования параллелизма количество памяти зависит от реализации

Преимущества:

• Не очень сложно реализуется для случая использования параллелизма
• Более эффективен, чем алгоритм быстрой сортировки

Недостатки:

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

2 Программная реализация алгоритма

2.4 Масштабируемость алгоритма и его реализации

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

На графике приведена зависимость времени работы алгоритма от числа процессов и длины сортируемого массива. Видно, что при увеличении длины массива время выполнения растет, но чем больше процессов используется, тем медленнее растет время выполнения.

Реализованный алгоритм запускался на суперкомпьютере Ломоносов 2.

Зависимость времени работы алгоритма от длины массива и количества MPI процессов

2.7 Существующие реализации алгоритма

Наиболее используемый "классический" вариант битонной сортировки предложен GeeksforGeeks. Здесь его реализации предложены на языках C++, Java, Python3, C#, Javascript. Время работы составляет [math] O(log^2n) [/math], объем занимаемой памяти [math] O(nlogn) [/math]. Авторы отмечают, что у алгоритма число сравнений больше, чем у других сортировок.

Также реализация битонной сортировки предложена на сайте Parallel Computing. Здесь данная сортировка реализована в трех вариантах с использованием технологий MPI, OpenMP и Cuda.

В статье K-Way Bitonic Sort предложена модификация битонной сортировки, позволяющая более эффективно сортировать последовательности произвольной размерности.

На сайте Sort Visualizer предложена визуализация работы алгоритма.