Алговики - Вклад [ru]

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

2023-12-05T08:37:24Z

Полина Кривуля: /* Информационный граф */

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

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

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

'''Битонная сортировка''' – это параллельный алгоритм сортировки, основанный на использовании понятия '''битонной последовательности'''. Алгоритм разработан американским информатиком Кеннетом Бэтчером в 1968 году и является одним из старейших параллельных алгоритмов сортировки. Наряду с четно-нечетной сортировкой слиянием, является одним из первых методов построения сортировочной сети для любого количества входов <ref> Википедия: [https://ru.wikipedia.org/wiki/Битонная_сортировка#:~:text=Битонная%20сортировка%20(англ.,лежит%20понятие%20«битонной%20последовательности». Битонная сортировка] </ref>. Публикация этого алгоритма, наряду с также предложенным Бэтчером алгоритмом [[сеть нечетно-четной перестановки]], стимулировала развитие проектирования и анализа параллельных алгоритмов в общем и параллельной сортировки в частности.

'''Битонной последовательностью''' называют последовательность, которая монотонно не убывает, а затем монотонно не возрастает, либо приводится к такому виду в результате циклического сдвига. Пример такой последовательности – {8, 10, 16, 12, 4, -2, -8} <ref> Дальневосточный Федеральный университет: [https://cc.dvfu.ru/ru/lesson-10/ Занятие 10. Программирование на CUDA. Часть 6.] </ref>.
Любая последовательность, входящая в битонную, любая последовательность состоящая из одного или двух элементов, а также любая монотонная последовательность также является битонной. Например, последовательности {3,5,10,4,1}, {1,5}, {10,14,5,-1,-4} являются битонными, а {4,6,1,9,2} не является. Каждое множество неотсортированных элементов можно считать множеством битонных последовательностей, состоящих из двух элементов. Процесс битонного слияния преобразует битонную последовательность в полностью отсортированную последовательность. Алгоритм битонной сортировки состоит из применения битонных преобразований до тех пор, пока множество не будет полностью отсортировано <ref> Selim G. Akl. Bitonic Sort (англ.) // Encyclopedia of Parallel Computing : энциклопедия. — Springer, 2011. — P. 139-146. — ISBN 978-0-387-09765-7. </ref>.

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

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

Решение задачи основано на понятии битонной последовательности. Исходный массив преобразуется в битонную последовательность. Для этого нужно разделить последовательность пополам, первую часть рекурсивно отсортировать по возрастанию, вторую часть рекурсивно отсортировать по убыванию <ref> Bimlibik: [https://bimlibik.github.io/posts/sorting-algorithm/. Алгоритмы сортировки] </ref>.

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

В данном алгоритме необходимо, чтобы размер исходного массива был равен степени двойки. В противном случае, его придется дополнять фиктивными элементами, что, однако, не влияет не асимптотику <ref> Habr: [https://habr.com/ru/articles/335920/. Описание алгоритмов сортировки и сравнение их производительности] </ref>.

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

Вычислительное ядро алгоритма битонной сортировки можно представить следующим образом <ref>Ionescu, M.F., & Schauser, K.E. (1990). Optimizing Parallel Bitonic Sort. Department of Computer Science, University of California.</ref>:

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

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

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

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

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

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

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

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

=== Последовательная сложность алгоритма ===
Сложность алгоритма битонной сортировки зависит от количества элементов в массиве. Обозначим эту величину как <math>n</math>.

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

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

=== Информационный граф ===
[[Файл:Graph bitonic.png|500px|thumb|center|рис.1: Информационный граф битонной сортировки]]

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

[[Файл:BitonicSort1.svg|700px|thumb|center|рис.2: Битонная сортировка для 16 элементов]]

На рисунке 2 изображена битонная сортировочная сеть для 16 элементов, которая сортирует множество по возрастанию. Красные прямоугольники скомбинированы в зеленые и голубые прямоугольники. В синих прямоугольниках стрелки компараторов направлены вниз (создают возрастающие последовательности), в зеленых — вверх (создают убывающие последовательности). Каждый из таких прямоугольников имеет одинаковую структуру: красный прямоугольник применяется ко всей последовательности, затем к каждой половине полученных результатов и так далее. Если на входы такого прямоугольника подается битонная последовательность, то на выходе она преобразуется в полностью отсортированную. Объединенные результаты синего и зеленого прямоугольника является битонной последовательностью.
Каждый столбец синих и зеленых прямоугольников принимает N отсортированных последовательностей (на самом первом шаге 16 отсортированных последовательностей, состоящих из 1 элемента) и преобразует их в N/2 отсортированных последовательностей. <ref> Википедия: [https://ru.wikipedia.org/wiki/Битонная_сортировка#:~:text=Битонная%20сортировка%20(англ.,лежит%20понятие%20«битонной%20последовательности». Битонная сортировка] </ref>.

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

[[Файл:Bitonic sort.svg|thumb|center|700px|рис.3: Битонная сортировочная сеть]]

На рисунке 3 каждый рабочий поток нарисован в виде вертикальной линии, начальная и конечная точки обозначают индексы текущей пары сортируемых элементов. Все цветные блоки, находящиеся в одном столбце, образуют шаг, который можно выполнять параллельно. Из диаграммы видно, что количество потоков на шаг постоянно и всегда равно <math> n/2</math>, где <math> n</math> — количество сортируемых элементов <ref> Ponies&Light: [https://poniesandlight.co.uk/reflect/bitonic_merge_sort/. Implementing Bitonic Merge Sort in Vulkan Compute] </ref>.

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

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

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

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

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

=== Свойства алгоритма ===
Временная сложность алгоритма:
* При последовательной реализации <math>O(nlog^2(n))</math>
* При параллельной реализации <math>O(log^2(n))</math>

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

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

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

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

=== Особенности реализации последовательного алгоритма ===

=== Локальность данных и вычислений ===

=== Возможные способы и особенности параллельной реализации алгоритма ===

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

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

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

[[Файл:Зависимость времени работы алгоритма от длины массива и количества процессов.png|мини|центр|Зависимость времени работы алгоритма от длины массива и количества MPI процессов]]

=== Динамические характеристики и эффективность реализации алгоритма ===

=== Выводы для классов архитектур ===

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

Также реализация битонной сортировки предложена на сайте [https://people.cs.rutgers.edu/~venugopa/parallel_summer2012/bitonic_openmp.html Parallel Computing]. Здесь данная сортировка реализована в трех вариантах с использованием технологий MPI, OpenMP и Cuda.

В статье [https://ieeexplore.ieee.org/document/16506 K-Way Bitonic Sort] предложена модификация битонной сортировки, позволяющая более эффективно сортировать последовательности произвольной размерности.

На сайте [https://www.sortvisualizer.com/bitonicsort/ Sort Visualizer] предложена визуализация работы алгоритма.

== Литература ==
<references />

[[en:Description of algorithm properties and structure]]

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

2023-12-05T08:36:54Z

Полина Кривуля: /* Ресурс параллелизма алгоритма */

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

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

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

'''Битонная сортировка''' – это параллельный алгоритм сортировки, основанный на использовании понятия '''битонной последовательности'''. Алгоритм разработан американским информатиком Кеннетом Бэтчером в 1968 году и является одним из старейших параллельных алгоритмов сортировки. Наряду с четно-нечетной сортировкой слиянием, является одним из первых методов построения сортировочной сети для любого количества входов <ref> Википедия: [https://ru.wikipedia.org/wiki/Битонная_сортировка#:~:text=Битонная%20сортировка%20(англ.,лежит%20понятие%20«битонной%20последовательности». Битонная сортировка] </ref>. Публикация этого алгоритма, наряду с также предложенным Бэтчером алгоритмом [[сеть нечетно-четной перестановки]], стимулировала развитие проектирования и анализа параллельных алгоритмов в общем и параллельной сортировки в частности.

'''Битонной последовательностью''' называют последовательность, которая монотонно не убывает, а затем монотонно не возрастает, либо приводится к такому виду в результате циклического сдвига. Пример такой последовательности – {8, 10, 16, 12, 4, -2, -8} <ref> Дальневосточный Федеральный университет: [https://cc.dvfu.ru/ru/lesson-10/ Занятие 10. Программирование на CUDA. Часть 6.] </ref>.
Любая последовательность, входящая в битонную, любая последовательность состоящая из одного или двух элементов, а также любая монотонная последовательность также является битонной. Например, последовательности {3,5,10,4,1}, {1,5}, {10,14,5,-1,-4} являются битонными, а {4,6,1,9,2} не является. Каждое множество неотсортированных элементов можно считать множеством битонных последовательностей, состоящих из двух элементов. Процесс битонного слияния преобразует битонную последовательность в полностью отсортированную последовательность. Алгоритм битонной сортировки состоит из применения битонных преобразований до тех пор, пока множество не будет полностью отсортировано <ref> Selim G. Akl. Bitonic Sort (англ.) // Encyclopedia of Parallel Computing : энциклопедия. — Springer, 2011. — P. 139-146. — ISBN 978-0-387-09765-7. </ref>.

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

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

Решение задачи основано на понятии битонной последовательности. Исходный массив преобразуется в битонную последовательность. Для этого нужно разделить последовательность пополам, первую часть рекурсивно отсортировать по возрастанию, вторую часть рекурсивно отсортировать по убыванию <ref> Bimlibik: [https://bimlibik.github.io/posts/sorting-algorithm/. Алгоритмы сортировки] </ref>.

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

В данном алгоритме необходимо, чтобы размер исходного массива был равен степени двойки. В противном случае, его придется дополнять фиктивными элементами, что, однако, не влияет не асимптотику <ref> Habr: [https://habr.com/ru/articles/335920/. Описание алгоритмов сортировки и сравнение их производительности] </ref>.

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

Вычислительное ядро алгоритма битонной сортировки можно представить следующим образом <ref>Ionescu, M.F., & Schauser, K.E. (1990). Optimizing Parallel Bitonic Sort. Department of Computer Science, University of California.</ref>:

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

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

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

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

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

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

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

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

=== Последовательная сложность алгоритма ===
Сложность алгоритма битонной сортировки зависит от количества элементов в массиве. Обозначим эту величину как <math>n</math>.

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

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

=== Информационный граф ===
[[Файл:Graph bitonic.png|500px|thumb|center|рис.1: Информационный граф битонной сортировки]]

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

[[Файл:BitonicSort1.svg|500px|thumb|center|рис.2: Битонная сортировка для 16 элементов]]

На рисунке 2 изображена битонная сортировочная сеть для 16 элементов, которая сортирует множество по возрастанию. Красные прямоугольники скомбинированы в зеленые и голубые прямоугольники. В синих прямоугольниках стрелки компараторов направлены вниз (создают возрастающие последовательности), в зеленых — вверх (создают убывающие последовательности). Каждый из таких прямоугольников имеет одинаковую структуру: красный прямоугольник применяется ко всей последовательности, затем к каждой половине полученных результатов и так далее. Если на входы такого прямоугольника подается битонная последовательность, то на выходе она преобразуется в полностью отсортированную. Объединенные результаты синего и зеленого прямоугольника является битонной последовательностью.
Каждый столбец синих и зеленых прямоугольников принимает N отсортированных последовательностей (на самом первом шаге 16 отсортированных последовательностей, состоящих из 1 элемента) и преобразует их в N/2 отсортированных последовательностей. <ref> Википедия: [https://ru.wikipedia.org/wiki/Битонная_сортировка#:~:text=Битонная%20сортировка%20(англ.,лежит%20понятие%20«битонной%20последовательности». Битонная сортировка] </ref>.

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

[[Файл:Bitonic sort.svg|thumb|center|700px|рис.3: Битонная сортировочная сеть]]

На рисунке 3 каждый рабочий поток нарисован в виде вертикальной линии, начальная и конечная точки обозначают индексы текущей пары сортируемых элементов. Все цветные блоки, находящиеся в одном столбце, образуют шаг, который можно выполнять параллельно. Из диаграммы видно, что количество потоков на шаг постоянно и всегда равно <math> n/2</math>, где <math> n</math> — количество сортируемых элементов <ref> Ponies&Light: [https://poniesandlight.co.uk/reflect/bitonic_merge_sort/. Implementing Bitonic Merge Sort in Vulkan Compute] </ref>.

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

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

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

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

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

=== Свойства алгоритма ===
Временная сложность алгоритма:
* При последовательной реализации <math>O(nlog^2(n))</math>
* При параллельной реализации <math>O(log^2(n))</math>

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

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

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

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

=== Особенности реализации последовательного алгоритма ===

=== Локальность данных и вычислений ===

=== Возможные способы и особенности параллельной реализации алгоритма ===

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

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

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

[[Файл:Зависимость времени работы алгоритма от длины массива и количества процессов.png|мини|центр|Зависимость времени работы алгоритма от длины массива и количества MPI процессов]]

=== Динамические характеристики и эффективность реализации алгоритма ===

=== Выводы для классов архитектур ===

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

Также реализация битонной сортировки предложена на сайте [https://people.cs.rutgers.edu/~venugopa/parallel_summer2012/bitonic_openmp.html Parallel Computing]. Здесь данная сортировка реализована в трех вариантах с использованием технологий MPI, OpenMP и Cuda.

В статье [https://ieeexplore.ieee.org/document/16506 K-Way Bitonic Sort] предложена модификация битонной сортировки, позволяющая более эффективно сортировать последовательности произвольной размерности.

На сайте [https://www.sortvisualizer.com/bitonicsort/ Sort Visualizer] предложена визуализация работы алгоритма.

== Литература ==
<references />

[[en:Description of algorithm properties and structure]]

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

2023-12-05T08:35:08Z

Полина Кривуля: /* Информационный граф */

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

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

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

'''Битонная сортировка''' – это параллельный алгоритм сортировки, основанный на использовании понятия '''битонной последовательности'''. Алгоритм разработан американским информатиком Кеннетом Бэтчером в 1968 году и является одним из старейших параллельных алгоритмов сортировки. Наряду с четно-нечетной сортировкой слиянием, является одним из первых методов построения сортировочной сети для любого количества входов <ref> Википедия: [https://ru.wikipedia.org/wiki/Битонная_сортировка#:~:text=Битонная%20сортировка%20(англ.,лежит%20понятие%20«битонной%20последовательности». Битонная сортировка] </ref>. Публикация этого алгоритма, наряду с также предложенным Бэтчером алгоритмом [[сеть нечетно-четной перестановки]], стимулировала развитие проектирования и анализа параллельных алгоритмов в общем и параллельной сортировки в частности.

'''Битонной последовательностью''' называют последовательность, которая монотонно не убывает, а затем монотонно не возрастает, либо приводится к такому виду в результате циклического сдвига. Пример такой последовательности – {8, 10, 16, 12, 4, -2, -8} <ref> Дальневосточный Федеральный университет: [https://cc.dvfu.ru/ru/lesson-10/ Занятие 10. Программирование на CUDA. Часть 6.] </ref>.
Любая последовательность, входящая в битонную, любая последовательность состоящая из одного или двух элементов, а также любая монотонная последовательность также является битонной. Например, последовательности {3,5,10,4,1}, {1,5}, {10,14,5,-1,-4} являются битонными, а {4,6,1,9,2} не является. Каждое множество неотсортированных элементов можно считать множеством битонных последовательностей, состоящих из двух элементов. Процесс битонного слияния преобразует битонную последовательность в полностью отсортированную последовательность. Алгоритм битонной сортировки состоит из применения битонных преобразований до тех пор, пока множество не будет полностью отсортировано <ref> Selim G. Akl. Bitonic Sort (англ.) // Encyclopedia of Parallel Computing : энциклопедия. — Springer, 2011. — P. 139-146. — ISBN 978-0-387-09765-7. </ref>.

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

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

Решение задачи основано на понятии битонной последовательности. Исходный массив преобразуется в битонную последовательность. Для этого нужно разделить последовательность пополам, первую часть рекурсивно отсортировать по возрастанию, вторую часть рекурсивно отсортировать по убыванию <ref> Bimlibik: [https://bimlibik.github.io/posts/sorting-algorithm/. Алгоритмы сортировки] </ref>.

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

В данном алгоритме необходимо, чтобы размер исходного массива был равен степени двойки. В противном случае, его придется дополнять фиктивными элементами, что, однако, не влияет не асимптотику <ref> Habr: [https://habr.com/ru/articles/335920/. Описание алгоритмов сортировки и сравнение их производительности] </ref>.

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

Вычислительное ядро алгоритма битонной сортировки можно представить следующим образом <ref>Ionescu, M.F., & Schauser, K.E. (1990). Optimizing Parallel Bitonic Sort. Department of Computer Science, University of California.</ref>:

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

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

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

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

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

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

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

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

=== Последовательная сложность алгоритма ===
Сложность алгоритма битонной сортировки зависит от количества элементов в массиве. Обозначим эту величину как <math>n</math>.

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

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

=== Информационный граф ===
[[Файл:Graph bitonic.png|500px|thumb|center|рис.1: Информационный граф битонной сортировки]]

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

[[Файл:BitonicSort1.svg|500px|thumb|center|рис.2: Битонная сортировка для 16 элементов]]

На рисунке 2 изображена битонная сортировочная сеть для 16 элементов, которая сортирует множество по возрастанию. Красные прямоугольники скомбинированы в зеленые и голубые прямоугольники. В синих прямоугольниках стрелки компараторов направлены вниз (создают возрастающие последовательности), в зеленых — вверх (создают убывающие последовательности). Каждый из таких прямоугольников имеет одинаковую структуру: красный прямоугольник применяется ко всей последовательности, затем к каждой половине полученных результатов и так далее. Если на входы такого прямоугольника подается битонная последовательность, то на выходе она преобразуется в полностью отсортированную. Объединенные результаты синего и зеленого прямоугольника является битонной последовательностью.
Каждый столбец синих и зеленых прямоугольников принимает N отсортированных последовательностей (на самом первом шаге 16 отсортированных последовательностей, состоящих из 1 элемента) и преобразует их в N/2 отсортированных последовательностей. <ref> Википедия: [https://ru.wikipedia.org/wiki/Битонная_сортировка#:~:text=Битонная%20сортировка%20(англ.,лежит%20понятие%20«битонной%20последовательности». Битонная сортировка] </ref>.

=== Ресурс параллелизма алгоритма ===
[[Файл:Bitonic sort.svg|обрамить|рис.3: Битонная сортировочная сеть]]
Алгоритм дает большой выигрыш при использовании параллелизма. В общем случае можно распараллелить данный алгоритм на любое число процессов являющееся степенью числа 2. Однако следует учитывать накладные расходы на создание MPI процессов и обмен сообщениями между ними. Если их будет достаточно много для сравнительно небольшой длины массива, то выигрыш в производительности будет очень маленьким, либо может отсутствовать вовсе.
На диаграмме 3 каждый рабочий поток нарисован в виде вертикальной линии, начальная и конечная точки обозначают индексы текущей пары сортируемых элементов. Все цветные блоки, находящиеся в одном столбце, образуют шаг, который можно выполнять параллельно. Из диаграммы видно, что количество потоков на шаг постоянно и всегда равно <math> n/2</math>, где <math> n</math> — количество сортируемых элементов <ref> Ponies&Light: [https://poniesandlight.co.uk/reflect/bitonic_merge_sort/. Implementing Bitonic Merge Sort in Vulkan Compute] </ref>.

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

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

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

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

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

=== Свойства алгоритма ===
Временная сложность алгоритма:
* При последовательной реализации <math>O(nlog^2(n))</math>
* При параллельной реализации <math>O(log^2(n))</math>

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

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

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

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

=== Особенности реализации последовательного алгоритма ===

=== Локальность данных и вычислений ===

=== Возможные способы и особенности параллельной реализации алгоритма ===

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

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

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

[[Файл:Зависимость времени работы алгоритма от длины массива и количества процессов.png|мини|центр|Зависимость времени работы алгоритма от длины массива и количества MPI процессов]]

=== Динамические характеристики и эффективность реализации алгоритма ===

=== Выводы для классов архитектур ===

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

Также реализация битонной сортировки предложена на сайте [https://people.cs.rutgers.edu/~venugopa/parallel_summer2012/bitonic_openmp.html Parallel Computing]. Здесь данная сортировка реализована в трех вариантах с использованием технологий MPI, OpenMP и Cuda.

В статье [https://ieeexplore.ieee.org/document/16506 K-Way Bitonic Sort] предложена модификация битонной сортировки, позволяющая более эффективно сортировать последовательности произвольной размерности.

На сайте [https://www.sortvisualizer.com/bitonicsort/ Sort Visualizer] предложена визуализация работы алгоритма.

== Литература ==
<references />

[[en:Description of algorithm properties and structure]]

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

2023-12-04T18:31:58Z

Полина Кривуля: /* Информационный граф */

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

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

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

'''Битонная сортировка''' – это параллельный алгоритм сортировки, основанный на использовании понятия '''битонной последовательности'''. Алгоритм разработан американским информатиком Кеннетом Бэтчером в 1968 году и является одним из старейших параллельных алгоритмов сортировки. Наряду с четно-нечетной сортировкой слиянием, является одним из первых методов построения сортировочной сети для любого количества входов <ref> Википедия: [https://ru.wikipedia.org/wiki/Битонная_сортировка#:~:text=Битонная%20сортировка%20(англ.,лежит%20понятие%20«битонной%20последовательности». Битонная сортировка] </ref>. Публикация этого алгоритма, наряду с также предложенным Бэтчером алгоритмом [[сеть нечетно-четной перестановки]], стимулировала развитие проектирования и анализа параллельных алгоритмов в общем и параллельной сортировки в частности.

'''Битонной последовательностью''' называют последовательность, которая монотонно не убывает, а затем монотонно не возрастает, либо приводится к такому виду в результате циклического сдвига. Пример такой последовательности – {8, 10, 16, 12, 4, -2, -8} <ref> Дальневосточный Федеральный университет: [https://cc.dvfu.ru/ru/lesson-10/ Занятие 10. Программирование на CUDA. Часть 6.] </ref>.
Любая последовательность, входящая в битонную, любая последовательность состоящая из одного или двух элементов, а также любая монотонная последовательность также является битонной. Например, последовательности {3,5,10,4,1}, {1,5}, {10,14,5,-1,-4} являются битонными, а {4,6,1,9,2} не является. Каждое множество неотсортированных элементов можно считать множеством битонных последовательностей, состоящих из двух элементов. Процесс битонного слияния преобразует битонную последовательность в полностью отсортированную последовательность. Алгоритм битонной сортировки состоит из применения битонных преобразований до тех пор, пока множество не будет полностью отсортировано <ref> Selim G. Akl. Bitonic Sort (англ.) // Encyclopedia of Parallel Computing : энциклопедия. — Springer, 2011. — P. 139-146. — ISBN 978-0-387-09765-7. </ref>.

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

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

Решение задачи основано на понятии битонной последовательности. Исходный массив преобразуется в битонную последовательность. Для этого нужно разделить последовательность пополам, первую часть рекурсивно отсортировать по возрастанию, вторую часть рекурсивно отсортировать по убыванию <ref> Bimlibik: [https://bimlibik.github.io/posts/sorting-algorithm/. Алгоритмы сортировки] </ref>.

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

В данном алгоритме необходимо, чтобы размер исходного массива был равен степени двойки. В противном случае, его придется дополнять фиктивными элементами, что, однако, не влияет не асимптотику <ref> Habr: [https://habr.com/ru/articles/335920/. Описание алгоритмов сортировки и сравнение их производительности] </ref>.

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

Вычислительное ядро алгоритма битонной сортировки можно представить следующим образом <ref>Ionescu, M.F., & Schauser, K.E. (1990). Optimizing Parallel Bitonic Sort. Department of Computer Science, University of California.</ref>:

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

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

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

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

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

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

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

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

=== Последовательная сложность алгоритма ===
Сложность алгоритма битонной сортировки зависит от количества элементов в массиве. Обозначим эту величину как <math>n</math>.

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

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

=== Информационный граф ===
[[Файл:Graph bitonic.png|мини|рис.1: Информационный граф битонной сортировки]]

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

[[Файл:BitonicSort1.svg|без|рис.2: Битонная сортировка для 16 элементов]]

На рисунке 2 изображена битонная сортировочная сеть для 16 элементов, которая сортирует множество по возрастанию. Красные прямоугольники скомбинированы в зеленые и голубые прямоугольники. В синих прямоугольниках стрелки компараторов направлены вниз (создают возрастающие последовательности), в зеленых — вверх (создают убывающие последовательности). Каждый из таких прямоугольников имеет одинаковую структуру: красный прямоугольник применяется ко всей последовательности, затем к каждой половине полученных результатов и так далее. Если на входы такого прямоугольника подается битонная последовательность, то на выходе она преобразуется в полностью отсортированную. Объединенные результаты синего и зеленого прямоугольника является битонной последовательностью.
Каждый столбец синих и зеленых прямоугольников принимает N отсортированных последовательностей (на самом первом шаге 16 отсортированных последовательностей, состоящих из 1 элемента) и преобразует их в N/2 отсортированных последовательностей. <ref> Википедия: [https://ru.wikipedia.org/wiki/Битонная_сортировка#:~:text=Битонная%20сортировка%20(англ.,лежит%20понятие%20«битонной%20последовательности». Битонная сортировка] </ref>.

=== Ресурс параллелизма алгоритма ===
[[Файл:Bitonic sort.svg|обрамить|рис.3: Битонная сортировочная сеть]]
Алгоритм дает большой выигрыш при использовании параллелизма. В общем случае можно распараллелить данный алгоритм на любое число процессов являющееся степенью числа 2. Однако следует учитывать накладные расходы на создание MPI процессов и обмен сообщениями между ними. Если их будет достаточно много для сравнительно небольшой длины массива, то выигрыш в производительности будет очень маленьким, либо может отсутствовать вовсе.
На диаграмме 3 каждый рабочий поток нарисован в виде вертикальной линии, начальная и конечная точки обозначают индексы текущей пары сортируемых элементов. Все цветные блоки, находящиеся в одном столбце, образуют шаг, который можно выполнять параллельно. Из диаграммы видно, что количество потоков на шаг постоянно и всегда равно <math> n/2</math>, где <math> n</math> — количество сортируемых элементов <ref> Ponies&Light: [https://poniesandlight.co.uk/reflect/bitonic_merge_sort/. Implementing Bitonic Merge Sort in Vulkan Compute] </ref>.

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

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

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

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

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

=== Свойства алгоритма ===
Временная сложность алгоритма:
* При последовательной реализации <math>O(nlog^2(n))</math>
* При параллельной реализации <math>O(log^2(n))</math>

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

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

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

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

=== Особенности реализации последовательного алгоритма ===

=== Локальность данных и вычислений ===

=== Возможные способы и особенности параллельной реализации алгоритма ===

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

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

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

[[Файл:Зависимость времени работы алгоритма от длины массива и количества процессов.png|мини|центр|Зависимость времени работы алгоритма от длины массива и количества MPI процессов]]

=== Динамические характеристики и эффективность реализации алгоритма ===

=== Выводы для классов архитектур ===

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

Также реализация битонной сортировки предложена на сайте [https://people.cs.rutgers.edu/~venugopa/parallel_summer2012/bitonic_openmp.html Parallel Computing]. Здесь данная сортировка реализована в трех вариантах с использованием технологий MPI, OpenMP и Cuda.

В статье [https://ieeexplore.ieee.org/document/16506 K-Way Bitonic Sort] предложена модификация битонной сортировки, позволяющая более эффективно сортировать последовательности произвольной размерности.

На сайте [https://www.sortvisualizer.com/bitonicsort/ Sort Visualizer] предложена визуализация работы алгоритма.

== Литература ==
<references />

[[en:Description of algorithm properties and structure]]

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

2023-12-04T18:30:27Z

Полина Кривуля: /* Ресурс параллелизма алгоритма */

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

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

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

'''Битонная сортировка''' – это параллельный алгоритм сортировки, основанный на использовании понятия '''битонной последовательности'''. Алгоритм разработан американским информатиком Кеннетом Бэтчером в 1968 году и является одним из старейших параллельных алгоритмов сортировки. Наряду с четно-нечетной сортировкой слиянием, является одним из первых методов построения сортировочной сети для любого количества входов <ref> Википедия: [https://ru.wikipedia.org/wiki/Битонная_сортировка#:~:text=Битонная%20сортировка%20(англ.,лежит%20понятие%20«битонной%20последовательности». Битонная сортировка] </ref>. Публикация этого алгоритма, наряду с также предложенным Бэтчером алгоритмом [[сеть нечетно-четной перестановки]], стимулировала развитие проектирования и анализа параллельных алгоритмов в общем и параллельной сортировки в частности.

'''Битонной последовательностью''' называют последовательность, которая монотонно не убывает, а затем монотонно не возрастает, либо приводится к такому виду в результате циклического сдвига. Пример такой последовательности – {8, 10, 16, 12, 4, -2, -8} <ref> Дальневосточный Федеральный университет: [https://cc.dvfu.ru/ru/lesson-10/ Занятие 10. Программирование на CUDA. Часть 6.] </ref>.
Любая последовательность, входящая в битонную, любая последовательность состоящая из одного или двух элементов, а также любая монотонная последовательность также является битонной. Например, последовательности {3,5,10,4,1}, {1,5}, {10,14,5,-1,-4} являются битонными, а {4,6,1,9,2} не является. Каждое множество неотсортированных элементов можно считать множеством битонных последовательностей, состоящих из двух элементов. Процесс битонного слияния преобразует битонную последовательность в полностью отсортированную последовательность. Алгоритм битонной сортировки состоит из применения битонных преобразований до тех пор, пока множество не будет полностью отсортировано <ref> Selim G. Akl. Bitonic Sort (англ.) // Encyclopedia of Parallel Computing : энциклопедия. — Springer, 2011. — P. 139-146. — ISBN 978-0-387-09765-7. </ref>.

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

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

Решение задачи основано на понятии битонной последовательности. Исходный массив преобразуется в битонную последовательность. Для этого нужно разделить последовательность пополам, первую часть рекурсивно отсортировать по возрастанию, вторую часть рекурсивно отсортировать по убыванию <ref> Bimlibik: [https://bimlibik.github.io/posts/sorting-algorithm/. Алгоритмы сортировки] </ref>.

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

В данном алгоритме необходимо, чтобы размер исходного массива был равен степени двойки. В противном случае, его придется дополнять фиктивными элементами, что, однако, не влияет не асимптотику <ref> Habr: [https://habr.com/ru/articles/335920/. Описание алгоритмов сортировки и сравнение их производительности] </ref>.

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

Вычислительное ядро алгоритма битонной сортировки можно представить следующим образом <ref>Ionescu, M.F., & Schauser, K.E. (1990). Optimizing Parallel Bitonic Sort. Department of Computer Science, University of California.</ref>:

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

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

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

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

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

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

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

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

=== Последовательная сложность алгоритма ===
Сложность алгоритма битонной сортировки зависит от количества элементов в массиве. Обозначим эту величину как <math>n</math>.

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

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

=== Информационный граф ===
[[Файл:Graph bitonic.png|мини|рис.1: Информационный граф битонной сортировки]]

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

[[Файл:BitonicSort1.svg|мини|рис.2: Битонная сортировка для 16 элементов]]

На рисунке 2 изображена битонная сортировочная сеть для 16 элементов, которая сортирует множество по возрастанию. Красные прямоугольники скомбинированы в зеленые и голубые прямоугольники. В синих прямоугольниках стрелки компараторов направлены вниз (создают возрастающие последовательности), в зеленых — вверх (создают убывающие последовательности). Каждый из таких прямоугольников имеет одинаковую структуру: красный прямоугольник применяется ко всей последовательности, затем к каждой половине полученных результатов и так далее. Если на входы такого прямоугольника подается битонная последовательность, то на выходе она преобразуется в полностью отсортированную. Объединенные результаты синего и зеленого прямоугольника является битонной последовательностью.
Каждый столбец синих и зеленых прямоугольников принимает N отсортированных последовательностей (на самом первом шаге 16 отсортированных последовательностей, состоящих из 1 элемента) и преобразует их в N/2 отсортированных последовательностей. <ref> Википедия: [https://ru.wikipedia.org/wiki/Битонная_сортировка#:~:text=Битонная%20сортировка%20(англ.,лежит%20понятие%20«битонной%20последовательности». Битонная сортировка] </ref>.

=== Ресурс параллелизма алгоритма ===
[[Файл:Bitonic sort.svg|обрамить|рис.3: Битонная сортировочная сеть]]
Алгоритм дает большой выигрыш при использовании параллелизма. В общем случае можно распараллелить данный алгоритм на любое число процессов являющееся степенью числа 2. Однако следует учитывать накладные расходы на создание MPI процессов и обмен сообщениями между ними. Если их будет достаточно много для сравнительно небольшой длины массива, то выигрыш в производительности будет очень маленьким, либо может отсутствовать вовсе.
На диаграмме 3 каждый рабочий поток нарисован в виде вертикальной линии, начальная и конечная точки обозначают индексы текущей пары сортируемых элементов. Все цветные блоки, находящиеся в одном столбце, образуют шаг, который можно выполнять параллельно. Из диаграммы видно, что количество потоков на шаг постоянно и всегда равно <math> n/2</math>, где <math> n</math> — количество сортируемых элементов <ref> Ponies&Light: [https://poniesandlight.co.uk/reflect/bitonic_merge_sort/. Implementing Bitonic Merge Sort in Vulkan Compute] </ref>.

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

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

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

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

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

=== Свойства алгоритма ===
Временная сложность алгоритма:
* При последовательной реализации <math>O(nlog^2(n))</math>
* При параллельной реализации <math>O(log^2(n))</math>

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

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

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

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

=== Особенности реализации последовательного алгоритма ===

=== Локальность данных и вычислений ===

=== Возможные способы и особенности параллельной реализации алгоритма ===

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

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

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

[[Файл:Зависимость времени работы алгоритма от длины массива и количества процессов.png|мини|центр|Зависимость времени работы алгоритма от длины массива и количества MPI процессов]]

=== Динамические характеристики и эффективность реализации алгоритма ===

=== Выводы для классов архитектур ===

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

Также реализация битонной сортировки предложена на сайте [https://people.cs.rutgers.edu/~venugopa/parallel_summer2012/bitonic_openmp.html Parallel Computing]. Здесь данная сортировка реализована в трех вариантах с использованием технологий MPI, OpenMP и Cuda.

В статье [https://ieeexplore.ieee.org/document/16506 K-Way Bitonic Sort] предложена модификация битонной сортировки, позволяющая более эффективно сортировать последовательности произвольной размерности.

На сайте [https://www.sortvisualizer.com/bitonicsort/ Sort Visualizer] предложена визуализация работы алгоритма.

== Литература ==
<references />

[[en:Description of algorithm properties and structure]]

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

2023-12-04T18:29:50Z

Полина Кривуля: /* Информационный граф */

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

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

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

'''Битонная сортировка''' – это параллельный алгоритм сортировки, основанный на использовании понятия '''битонной последовательности'''. Алгоритм разработан американским информатиком Кеннетом Бэтчером в 1968 году и является одним из старейших параллельных алгоритмов сортировки. Наряду с четно-нечетной сортировкой слиянием, является одним из первых методов построения сортировочной сети для любого количества входов <ref> Википедия: [https://ru.wikipedia.org/wiki/Битонная_сортировка#:~:text=Битонная%20сортировка%20(англ.,лежит%20понятие%20«битонной%20последовательности». Битонная сортировка] </ref>. Публикация этого алгоритма, наряду с также предложенным Бэтчером алгоритмом [[сеть нечетно-четной перестановки]], стимулировала развитие проектирования и анализа параллельных алгоритмов в общем и параллельной сортировки в частности.

'''Битонной последовательностью''' называют последовательность, которая монотонно не убывает, а затем монотонно не возрастает, либо приводится к такому виду в результате циклического сдвига. Пример такой последовательности – {8, 10, 16, 12, 4, -2, -8} <ref> Дальневосточный Федеральный университет: [https://cc.dvfu.ru/ru/lesson-10/ Занятие 10. Программирование на CUDA. Часть 6.] </ref>.
Любая последовательность, входящая в битонную, любая последовательность состоящая из одного или двух элементов, а также любая монотонная последовательность также является битонной. Например, последовательности {3,5,10,4,1}, {1,5}, {10,14,5,-1,-4} являются битонными, а {4,6,1,9,2} не является. Каждое множество неотсортированных элементов можно считать множеством битонных последовательностей, состоящих из двух элементов. Процесс битонного слияния преобразует битонную последовательность в полностью отсортированную последовательность. Алгоритм битонной сортировки состоит из применения битонных преобразований до тех пор, пока множество не будет полностью отсортировано <ref> Selim G. Akl. Bitonic Sort (англ.) // Encyclopedia of Parallel Computing : энциклопедия. — Springer, 2011. — P. 139-146. — ISBN 978-0-387-09765-7. </ref>.

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

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

Решение задачи основано на понятии битонной последовательности. Исходный массив преобразуется в битонную последовательность. Для этого нужно разделить последовательность пополам, первую часть рекурсивно отсортировать по возрастанию, вторую часть рекурсивно отсортировать по убыванию <ref> Bimlibik: [https://bimlibik.github.io/posts/sorting-algorithm/. Алгоритмы сортировки] </ref>.

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

В данном алгоритме необходимо, чтобы размер исходного массива был равен степени двойки. В противном случае, его придется дополнять фиктивными элементами, что, однако, не влияет не асимптотику <ref> Habr: [https://habr.com/ru/articles/335920/. Описание алгоритмов сортировки и сравнение их производительности] </ref>.

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

Вычислительное ядро алгоритма битонной сортировки можно представить следующим образом <ref>Ionescu, M.F., & Schauser, K.E. (1990). Optimizing Parallel Bitonic Sort. Department of Computer Science, University of California.</ref>:

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

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

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

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

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

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

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

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

=== Последовательная сложность алгоритма ===
Сложность алгоритма битонной сортировки зависит от количества элементов в массиве. Обозначим эту величину как <math>n</math>.

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

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

=== Информационный граф ===
[[Файл:Graph bitonic.png|мини|рис.1: Информационный граф битонной сортировки]]

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

[[Файл:BitonicSort1.svg|мини|рис.2: Битонная сортировка для 16 элементов]]

На рисунке 2 изображена битонная сортировочная сеть для 16 элементов, которая сортирует множество по возрастанию. Красные прямоугольники скомбинированы в зеленые и голубые прямоугольники. В синих прямоугольниках стрелки компараторов направлены вниз (создают возрастающие последовательности), в зеленых — вверх (создают убывающие последовательности). Каждый из таких прямоугольников имеет одинаковую структуру: красный прямоугольник применяется ко всей последовательности, затем к каждой половине полученных результатов и так далее. Если на входы такого прямоугольника подается битонная последовательность, то на выходе она преобразуется в полностью отсортированную. Объединенные результаты синего и зеленого прямоугольника является битонной последовательностью.
Каждый столбец синих и зеленых прямоугольников принимает N отсортированных последовательностей (на самом первом шаге 16 отсортированных последовательностей, состоящих из 1 элемента) и преобразует их в N/2 отсортированных последовательностей. <ref> Википедия: [https://ru.wikipedia.org/wiki/Битонная_сортировка#:~:text=Битонная%20сортировка%20(англ.,лежит%20понятие%20«битонной%20последовательности». Битонная сортировка] </ref>.

=== Ресурс параллелизма алгоритма ===
[[Файл:Bitonic sort.svg|обрамить|Битонная сортировочная сеть]]
Алгоритм дает большой выигрыш при использовании параллелизма. В общем случае можно распараллелить данный алгоритм на любое число процессов являющееся степенью числа 2. Однако следует учитывать накладные расходы на создание MPI процессов и обмен сообщениями между ними. Если их будет достаточно много для сравнительно небольшой длины массива, то выигрыш в производительности будет очень маленьким, либо может отсутствовать вовсе.
На диаграмме каждый рабочий поток нарисован в виде вертикальной линии, начальная и конечная точки обозначают индексы текущей пары сортируемых элементов. Все цветные блоки, находящиеся в одном столбце, образуют шаг, который можно выполнять параллельно. Из диаграммы видно, что количество потоков на шаг постоянно и всегда равно <math> n/2</math>, где <math> n</math> — количество сортируемых элементов <ref> Ponies&Light: [https://poniesandlight.co.uk/reflect/bitonic_merge_sort/. Implementing Bitonic Merge Sort in Vulkan Compute] </ref>.

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

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

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

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

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

=== Свойства алгоритма ===
Временная сложность алгоритма:
* При последовательной реализации <math>O(nlog^2(n))</math>
* При параллельной реализации <math>O(log^2(n))</math>

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

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

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

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

=== Особенности реализации последовательного алгоритма ===

=== Локальность данных и вычислений ===

=== Возможные способы и особенности параллельной реализации алгоритма ===

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

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

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

[[Файл:Зависимость времени работы алгоритма от длины массива и количества процессов.png|мини|центр|Зависимость времени работы алгоритма от длины массива и количества MPI процессов]]

=== Динамические характеристики и эффективность реализации алгоритма ===

=== Выводы для классов архитектур ===

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

Также реализация битонной сортировки предложена на сайте [https://people.cs.rutgers.edu/~venugopa/parallel_summer2012/bitonic_openmp.html Parallel Computing]. Здесь данная сортировка реализована в трех вариантах с использованием технологий MPI, OpenMP и Cuda.

В статье [https://ieeexplore.ieee.org/document/16506 K-Way Bitonic Sort] предложена модификация битонной сортировки, позволяющая более эффективно сортировать последовательности произвольной размерности.

На сайте [https://www.sortvisualizer.com/bitonicsort/ Sort Visualizer] предложена визуализация работы алгоритма.

== Литература ==
<references />

[[en:Description of algorithm properties and structure]]

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

2023-12-04T18:20:51Z

Полина Кривуля: /* Свойства и структура алгоритмов */

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

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

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

'''Битонная сортировка''' – это параллельный алгоритм сортировки, основанный на использовании понятия '''битонной последовательности'''. Алгоритм разработан американским информатиком Кеннетом Бэтчером в 1968 году и является одним из старейших параллельных алгоритмов сортировки. Наряду с четно-нечетной сортировкой слиянием, является одним из первых методов построения сортировочной сети для любого количества входов <ref> Википедия: [https://ru.wikipedia.org/wiki/Битонная_сортировка#:~:text=Битонная%20сортировка%20(англ.,лежит%20понятие%20«битонной%20последовательности». Битонная сортировка] </ref>. Публикация этого алгоритма, наряду с также предложенным Бэтчером алгоритмом [[сеть нечетно-четной перестановки]], стимулировала развитие проектирования и анализа параллельных алгоритмов в общем и параллельной сортировки в частности.

'''Битонной последовательностью''' называют последовательность, которая монотонно не убывает, а затем монотонно не возрастает, либо приводится к такому виду в результате циклического сдвига. Пример такой последовательности – {8, 10, 16, 12, 4, -2, -8} <ref> Дальневосточный Федеральный университет: [https://cc.dvfu.ru/ru/lesson-10/ Занятие 10. Программирование на CUDA. Часть 6.] </ref>.
Любая последовательность, входящая в битонную, любая последовательность состоящая из одного или двух элементов, а также любая монотонная последовательность также является битонной. Например, последовательности {3,5,10,4,1}, {1,5}, {10,14,5,-1,-4} являются битонными, а {4,6,1,9,2} не является. Каждое множество неотсортированных элементов можно считать множеством битонных последовательностей, состоящих из двух элементов. Процесс битонного слияния преобразует битонную последовательность в полностью отсортированную последовательность. Алгоритм битонной сортировки состоит из применения битонных преобразований до тех пор, пока множество не будет полностью отсортировано <ref> Selim G. Akl. Bitonic Sort (англ.) // Encyclopedia of Parallel Computing : энциклопедия. — Springer, 2011. — P. 139-146. — ISBN 978-0-387-09765-7. </ref>.

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

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

Решение задачи основано на понятии битонной последовательности. Исходный массив преобразуется в битонную последовательность. Для этого нужно разделить последовательность пополам, первую часть рекурсивно отсортировать по возрастанию, вторую часть рекурсивно отсортировать по убыванию <ref> Bimlibik: [https://bimlibik.github.io/posts/sorting-algorithm/. Алгоритмы сортировки] </ref>.

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

В данном алгоритме необходимо, чтобы размер исходного массива был равен степени двойки. В противном случае, его придется дополнять фиктивными элементами, что, однако, не влияет не асимптотику <ref> Habr: [https://habr.com/ru/articles/335920/. Описание алгоритмов сортировки и сравнение их производительности] </ref>.

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

Вычислительное ядро алгоритма битонной сортировки можно представить следующим образом <ref>Ionescu, M.F., & Schauser, K.E. (1990). Optimizing Parallel Bitonic Sort. Department of Computer Science, University of California.</ref>:

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

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

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

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

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

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

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

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

=== Последовательная сложность алгоритма ===
Сложность алгоритма битонной сортировки зависит от количества элементов в массиве. Обозначим эту величину как <math>n</math>.

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

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

=== Информационный граф ===
[[Файл:Graph bitonic.png|мини|Информационный граф битонной сортировки]]

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

=== Ресурс параллелизма алгоритма ===
[[Файл:Bitonic sort.svg|обрамить|Битонная сортировочная сеть]]
Алгоритм дает большой выигрыш при использовании параллелизма. В общем случае можно распараллелить данный алгоритм на любое число процессов являющееся степенью числа 2. Однако следует учитывать накладные расходы на создание MPI процессов и обмен сообщениями между ними. Если их будет достаточно много для сравнительно небольшой длины массива, то выигрыш в производительности будет очень маленьким, либо может отсутствовать вовсе.
На диаграмме каждый рабочий поток нарисован в виде вертикальной линии, начальная и конечная точки обозначают индексы текущей пары сортируемых элементов. Все цветные блоки, находящиеся в одном столбце, образуют шаг, который можно выполнять параллельно. Из диаграммы видно, что количество потоков на шаг постоянно и всегда равно <math> n/2</math>, где <math> n</math> — количество сортируемых элементов <ref> Ponies&Light: [https://poniesandlight.co.uk/reflect/bitonic_merge_sort/. Implementing Bitonic Merge Sort in Vulkan Compute] </ref>.

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

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

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

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

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

=== Свойства алгоритма ===
Временная сложность алгоритма:
* При последовательной реализации <math>O(nlog^2(n))</math>
* При параллельной реализации <math>O(log^2(n))</math>

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

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

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

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

=== Особенности реализации последовательного алгоритма ===

=== Локальность данных и вычислений ===

=== Возможные способы и особенности параллельной реализации алгоритма ===

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

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

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

[[Файл:Зависимость времени работы алгоритма от длины массива и количества процессов.png|мини|центр|Зависимость времени работы алгоритма от длины массива и количества MPI процессов]]

=== Динамические характеристики и эффективность реализации алгоритма ===

=== Выводы для классов архитектур ===

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

Также реализация битонной сортировки предложена на сайте [https://people.cs.rutgers.edu/~venugopa/parallel_summer2012/bitonic_openmp.html Parallel Computing]. Здесь данная сортировка реализована в трех вариантах с использованием технологий MPI, OpenMP и Cuda.

В статье [https://ieeexplore.ieee.org/document/16506 K-Way Bitonic Sort] предложена модификация битонной сортировки, позволяющая более эффективно сортировать последовательности произвольной размерности.

На сайте [https://www.sortvisualizer.com/bitonicsort/ Sort Visualizer] предложена визуализация работы алгоритма.

== Литература ==
<references />

[[en:Description of algorithm properties and structure]]

Файл:Graph bitonic.png

2023-12-04T18:16:58Z

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

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

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

2023-12-04T17:06:12Z

Полина Кривуля: /* Свойства и структура алгоритмов */

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

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

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

'''Битонная сортировка''' – это параллельный алгоритм сортировки, основанный на использовании понятия '''битонной последовательности'''. Алгоритм разработан американским информатиком Кеннетом Бэтчером в 1968 году и является одним из старейших параллельных алгоритмов сортировки. Наряду с четно-нечетной сортировкой слиянием, является одним из первых методов построения сортировочной сети для любого количества входов <ref> Википедия: [https://ru.wikipedia.org/wiki/Битонная_сортировка#:~:text=Битонная%20сортировка%20(англ.,лежит%20понятие%20«битонной%20последовательности». Битонная сортировка] </ref>. Публикация этого алгоритма, наряду с также предложенным Бэтчером алгоритмом [[сеть нечетно-четной перестановки]], стимулировала развитие проектирования и анализа параллельных алгоритмов в общем и параллельной сортировки в частности.

'''Битонной последовательностью''' называют последовательность, которая монотонно не убывает, а затем монотонно не возрастает, либо приводится к такому виду в результате циклического сдвига. Пример такой последовательности – {8, 10, 16, 12, 4, -2, -8} <ref> Дальневосточный Федеральный университет: [https://cc.dvfu.ru/ru/lesson-10/ Занятие 10. Программирование на CUDA. Часть 6.] </ref>.
Любая последовательность, входящая в битонную, любая последовательность состоящая из одного или двух элементов, а также любая монотонная последовательность также является битонной. Например, последовательности {3,5,10,4,1}, {1,5}, {10,14,5,-1,-4} являются битонными, а {4,6,1,9,2} не является. Каждое множество неотсортированных элементов можно считать множеством битонных последовательностей, состоящих из двух элементов. Процесс битонного слияния преобразует битонную последовательность в полностью отсортированную последовательность. Алгоритм битонной сортировки состоит из применения битонных преобразований до тех пор, пока множество не будет полностью отсортировано <ref> Selim G. Akl. Bitonic Sort (англ.) // Encyclopedia of Parallel Computing : энциклопедия. — Springer, 2011. — P. 139-146. — ISBN 978-0-387-09765-7. </ref>.

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

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

Решение задачи основано на понятии битонной последовательности. Исходный массив преобразуется в битонную последовательность. Для этого нужно разделить последовательность пополам, первую часть рекурсивно отсортировать по возрастанию, вторую часть рекурсивно отсортировать по убыванию <ref> Bimlibik: [https://bimlibik.github.io/posts/sorting-algorithm/. Алгоритмы сортировки] </ref>.

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

В данном алгоритме необходимо, чтобы размер исходного массива был равен степени двойки. В противном случае, его придется дополнять фиктивными элементами, что, однако, не влияет не асимптотику <ref> Habr: [https://habr.com/ru/articles/335920/. Описание алгоритмов сортировки и сравнение их производительности] </ref>.

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

Вычислительное ядро алгоритма битонной сортировки можно представить следующим образом <ref>Ionescu, M.F., & Schauser, K.E. (1990). Optimizing Parallel Bitonic Sort. Department of Computer Science, University of California.</ref>:

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

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

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

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

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

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

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

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

=== Последовательная сложность алгоритма ===
Сложность алгоритма битонной сортировки зависит от количества элементов в массиве. Обозначим эту величину как <math>n</math>.

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

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

=== Информационный граф ===
[[Файл:Bitonic sort.svg|обрамить|Информационный граф битонной сортировки]]

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

На диаграмме каждый рабочий поток нарисован в виде вертикальной линии, начальная и конечная точки обозначают индексы текущей пары сортируемых элементов. Все цветные блоки, находящиеся в одном столбце, образуют шаг, который можно выполнять параллельно. Из диаграммы видно, что количество потоков на шаг постоянно и всегда равно <math> n/2</math>, где <math> n</math> — количество сортируемых элементов <ref> Ponies&Light: [https://poniesandlight.co.uk/reflect/bitonic_merge_sort/. Implementing Bitonic Merge Sort in Vulkan Compute] </ref>.

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

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

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

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

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

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

=== Свойства алгоритма ===
Временная сложность алгоритма:
* При последовательной реализации <math>O(nlog^2(n))</math>
* При параллельной реализации <math>O(log^2(n))</math>

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

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

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

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

=== Особенности реализации последовательного алгоритма ===

=== Локальность данных и вычислений ===

=== Возможные способы и особенности параллельной реализации алгоритма ===

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

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

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

[[Файл:Зависимость времени работы алгоритма от длины массива и количества процессов.png|мини|центр|Зависимость времени работы алгоритма от длины массива и количества MPI процессов]]

=== Динамические характеристики и эффективность реализации алгоритма ===

=== Выводы для классов архитектур ===

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

Также реализация битонной сортировки предложена на сайте [https://people.cs.rutgers.edu/~venugopa/parallel_summer2012/bitonic_openmp.html Parallel Computing]. Здесь данная сортировка реализована в трех вариантах с использованием технологий MPI, OpenMP и Cuda.

В статье [https://ieeexplore.ieee.org/document/16506 K-Way Bitonic Sort] предложена модификация битонной сортировки, позволяющая более эффективно сортировать последовательности произвольной размерности.

На сайте [https://www.sortvisualizer.com/bitonicsort/ Sort Visualizer] предложена визуализация работы алгоритма.

== Литература ==
<references />

[[en:Description of algorithm properties and structure]]

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

2023-12-03T15:51:07Z

Полина Кривуля: /* Существующие реализации алгоритма */

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

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

'''Битонная сортировка''' – это параллельный алгоритм сортировки, основанный на использовании понятия '''битонной последовательности'''. Алгоритм разработан американским информатиком Кеннетом Бэтчером в 1968 году и является одним из старейших параллельных алгоритмов сортировки. Наряду с четно-нечетной сортировкой слиянием, является одним из первых методов построения сортировочной сети для любого количества входов <ref> Википедия: [https://ru.wikipedia.org/wiki/Битонная_сортировка#:~:text=Битонная%20сортировка%20(англ.,лежит%20понятие%20«битонной%20последовательности». Битонная сортировка] </ref>. Публикация этого алгоритма, наряду с также предложенным Бэтчером алгоритмом [[сеть нечетно-четной перестановки]], стимулировала развитие проектирования и анализа параллельных алгоритмов в общем и параллельной сортировки в частности.

'''Битонной последовательностью''' называют последовательность, которая монотонно не убывает, а затем монотонно не возрастает, либо приводится к такому виду в результате циклического сдвига. Пример такой последовательности – {8, 10, 16, 12, 4, -2, -8} <ref> Дальневосточный Федеральный университет: [https://cc.dvfu.ru/ru/lesson-10/ Занятие 10. Программирование на CUDA. Часть 6.] </ref>.
Любая последовательность, входящая в битонную, любая последовательность состоящая из одного или двух элементов, а также любая монотонная последовательность также является битонной. Например, последовательности {3,5,10,4,1}, {1,5}, {10,14,5,-1,-4} являются битонными, а {4,6,1,9,2} не является. Каждое множество неотсортированных элементов можно считать множеством битонных последовательностей, состоящих из двух элементов. Процесс битонного слияния преобразует битонную последовательность в полностью отсортированную последовательность. Алгоритм битонной сортировки состоит из применения битонных преобразований до тех пор, пока множество не будет полностью отсортировано <ref> Selim G. Akl. Bitonic Sort (англ.) // Encyclopedia of Parallel Computing : энциклопедия. — Springer, 2011. — P. 139-146. — ISBN 978-0-387-09765-7. </ref>.

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

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

Решение задачи основано на понятии битонной последовательности. Исходный массив преобразуется в битонную последовательность. Для этого нужно разделить последовательность пополам, первую часть рекурсивно отсортировать по возрастанию, вторую часть рекурсивно отсортировать по убыванию <ref> Bimlibik: [https://bimlibik.github.io/posts/sorting-algorithm/. Алгоритмы сортировки] </ref>.

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

В данном алгоритме необходимо, чтобы размер исходного массива был равен степени двойки. В противном случае, его придется дополнять фиктивными элементами, что, однако, не влияет не асимптотику <ref> Habr: [https://habr.com/ru/articles/335920/. Описание алгоритмов сортировки и сравнение их производительности] </ref>.

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

Вычислительное ядро алгоритма битонной сортировки можно представить следующим образом <ref>Ionescu, M.F., & Schauser, K.E. (1990). Optimizing Parallel Bitonic Sort. Department of Computer Science, University of California.</ref>:

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

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

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

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

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

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

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

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

=== Последовательная сложность алгоритма ===
Сложность алгоритма битонной сортировки зависит от количества элементов в массиве. Обозначим эту величину как <math>n</math>.

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

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

=== Информационный граф ===
[[Файл:Bitonic sort.svg|обрамить|Информационный граф битонной сортировки]]

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

На диаграмме каждый рабочий поток нарисован в виде вертикальной линии, начальная и конечная точки обозначают индексы текущей пары сортируемых элементов. Все цветные блоки, находящиеся в одном столбце, образуют шаг, который можно выполнять параллельно. Из диаграммы видно, что количество потоков на шаг постоянно и всегда равно <math> n/2</math>, где <math> n</math> — количество сортируемых элементов <ref> Ponies&Light: [https://poniesandlight.co.uk/reflect/bitonic_merge_sort/. Implementing Bitonic Merge Sort in Vulkan Compute] </ref>.

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

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

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

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

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

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

=== Свойства алгоритма ===
Временная сложность алгоритма:
* При последовательной реализации <math>O(nlog^2(n))</math>
* При параллельной реализации <math>O(log^2(n))</math>

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

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

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

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

=== Особенности реализации последовательного алгоритма ===

=== Локальность данных и вычислений ===

=== Возможные способы и особенности параллельной реализации алгоритма ===

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

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

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

[[Файл:Зависимость времени работы алгоритма от длины массива и количества процессов.png|мини|центр|Зависимость времени работы алгоритма от длины массива и количества MPI процессов]]

=== Динамические характеристики и эффективность реализации алгоритма ===

=== Выводы для классов архитектур ===

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

Также реализация битонной сортировки предложена на сайте [https://people.cs.rutgers.edu/~venugopa/parallel_summer2012/bitonic_openmp.html Parallel Computing]. Здесь данная сортировка реализована в трех вариантах с использованием технологий MPI, OpenMP и Cuda.

В статье [https://ieeexplore.ieee.org/document/16506 K-Way Bitonic Sort] предложена модификация битонной сортировки, позволяющая более эффективно сортировать последовательности произвольной размерности.

На сайте [https://www.sortvisualizer.com/bitonicsort/ Sort Visualizer] предложена визуализация работы алгоритма.

== Литература ==
<references />

[[en:Description of algorithm properties and structure]]

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

2023-12-03T12:22:54Z

Полина Кривуля: /* Свойства алгоритма */

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

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

'''Битонная сортировка''' – это параллельный алгоритм сортировки, основанный на использовании понятия '''битонной последовательности'''. Алгоритм разработан американским информатиком Кеннетом Бэтчером в 1968 году и является одним из старейших параллельных алгоритмов сортировки. Наряду с четно-нечетной сортировкой слиянием, является одним из первых методов построения сортировочной сети для любого количества входов <ref> Википедия: [https://ru.wikipedia.org/wiki/Битонная_сортировка#:~:text=Битонная%20сортировка%20(англ.,лежит%20понятие%20«битонной%20последовательности». Битонная сортировка] </ref>. Публикация этого алгоритма, наряду с также предложенным Бэтчером алгоритмом [[сеть нечетно-четной перестановки]], стимулировала развитие проектирования и анализа параллельных алгоритмов в общем и параллельной сортировки в частности.

'''Битонной последовательностью''' называют последовательность, которая монотонно не убывает, а затем монотонно не возрастает, либо приводится к такому виду в результате циклического сдвига. Пример такой последовательности – {8, 10, 16, 12, 4, -2, -8} <ref> Дальневосточный Федеральный университет: [https://cc.dvfu.ru/ru/lesson-10/ Занятие 10. Программирование на CUDA. Часть 6.] </ref>.
Любая последовательность, входящая в битонную, любая последовательность состоящая из одного или двух элементов, а также любая монотонная последовательность также является битонной. Например, последовательности {3,5,10,4,1}, {1,5}, {10,14,5,-1,-4} являются битонными, а {4,6,1,9,2} не является. Каждое множество неотсортированных элементов можно считать множеством битонных последовательностей, состоящих из двух элементов. Процесс битонного слияния преобразует битонную последовательность в полностью отсортированную последовательность. Алгоритм битонной сортировки состоит из применения битонных преобразований до тех пор, пока множество не будет полностью отсортировано <ref> Selim G. Akl. Bitonic Sort (англ.) // Encyclopedia of Parallel Computing : энциклопедия. — Springer, 2011. — P. 139-146. — ISBN 978-0-387-09765-7. </ref>.

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

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

Решение задачи основано на понятии битонной последовательности. Исходный массив преобразуется в битонную последовательность. Для этого нужно разделить последовательность пополам, первую часть рекурсивно отсортировать по возрастанию, вторую часть рекурсивно отсортировать по убыванию <ref> Bimlibik: [https://bimlibik.github.io/posts/sorting-algorithm/. Алгоритмы сортировки] </ref>.

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

В данном алгоритме необходимо, чтобы размер исходного массива был равен степени двойки. В противном случае, его придется дополнять фиктивными элементами, что, однако, не влияет не асимптотику <ref> Habr: [https://habr.com/ru/articles/335920/. Описание алгоритмов сортировки и сравнение их производительности] </ref>.

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

Вычислительное ядро алгоритма битонной сортировки можно представить следующим образом <ref>Ionescu, M.F., & Schauser, K.E. (1990). Optimizing Parallel Bitonic Sort. Department of Computer Science, University of California.</ref>:

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

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

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

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

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

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

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

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

=== Последовательная сложность алгоритма ===
Сложность алгоритма битонной сортировки зависит от количества элементов в массиве. Обозначим эту величину как <math>n</math>.

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

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

=== Информационный граф ===
[[Файл:Bitonic sort.svg|обрамить|Информационный граф битонной сортировки]]

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

На диаграмме каждый рабочий поток нарисован в виде вертикальной линии, начальная и конечная точки обозначают индексы текущей пары сортируемых элементов. Все цветные блоки, находящиеся в одном столбце, образуют шаг, который можно выполнять параллельно. Из диаграммы видно, что количество потоков на шаг постоянно и всегда равно <math> n/2</math>, где <math> n</math> — количество сортируемых элементов <ref> Ponies&Light: [https://poniesandlight.co.uk/reflect/bitonic_merge_sort/. Implementing Bitonic Merge Sort in Vulkan Compute] </ref>.

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

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

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

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

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

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

=== Свойства алгоритма ===
Временная сложность алгоритма:
* При последовательной реализации <math>O(nlog^2(n))</math>
* При параллельной реализации <math>O(log^2(n))</math>

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

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

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

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

=== Особенности реализации последовательного алгоритма ===

=== Локальность данных и вычислений ===

=== Возможные способы и особенности параллельной реализации алгоритма ===

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

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

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

[[Файл:Зависимость времени работы алгоритма от длины массива и количества процессов.png|мини|центр|Зависимость времени работы алгоритма от длины массива и количества MPI процессов]]

=== Динамические характеристики и эффективность реализации алгоритма ===

=== Выводы для классов архитектур ===

=== Существующие реализации алгоритма ===
[https://www.geeksforgeeks.org/bitonic-sort/ Реализация битонной сортировки от GeeksforGeeks]

[https://people.cs.rutgers.edu/~venugopa/parallel_summer2012/bitonic_openmp.html Реализация битонной сортировки, найденная на сайте Parallel Computing]

[https://www.sortvisualizer.com/bitonicsort/ Реализация битонной сортировки с красивым интерфейсом сайта, где можно наглядно увидеть как работает последовательный алгоритм сортировки]

== Литература ==
<references />

[[en:Description of algorithm properties and structure]]

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

2023-12-02T14:48:54Z

Полина Кривуля: /* Существующие реализации алгоритма */

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

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

'''Битонная сортировка''' – это параллельный алгоритм сортировки, основанный на использовании понятия '''битонной последовательности'''. Алгоритм разработан американским информатиком Кеннетом Бэтчером в 1968 году и является одним из старейших параллельных алгоритмов сортировки. Наряду с четно-нечетной сортировкой слиянием, является одним из первых методов построения сортировочной сети для любого количества входов <ref> Википедия: [https://ru.wikipedia.org/wiki/Битонная_сортировка#:~:text=Битонная%20сортировка%20(англ.,лежит%20понятие%20«битонной%20последовательности». Битонная сортировка] </ref>. Публикация этого алгоритма, наряду с также предложенным Бэтчером алгоритмом [[сеть нечетно-четной перестановки]], стимулировала развитие проектирования и анализа параллельных алгоритмов в общем и параллельной сортировки в частности.

'''Битонной последовательностью''' называют последовательность, которая монотонно не убывает, а затем монотонно не возрастает, либо приводится к такому виду в результате циклического сдвига. Пример такой последовательности – {8, 10, 16, 12, 4, -2, -8} <ref> Дальневосточный Федеральный университет: [https://cc.dvfu.ru/ru/lesson-10/ Занятие 10. Программирование на CUDA. Часть 6.] </ref>.
Любая последовательность, входящая в битонную, любая последовательность состоящая из одного или двух элементов, а также любая монотонная последовательность также является битонной. Например, последовательности {3,5,10,4,1}, {1,5}, {10,14,5,-1,-4} являются битонными, а {4,6,1,9,2} не является. Каждое множество неотсортированных элементов можно считать множеством битонных последовательностей, состоящих из двух элементов. Процесс битонного слияния преобразует битонную последовательность в полностью отсортированную последовательность. Алгоритм битонной сортировки состоит из применения битонных преобразований до тех пор, пока множество не будет полностью отсортировано <ref> Selim G. Akl. Bitonic Sort (англ.) // Encyclopedia of Parallel Computing : энциклопедия. — Springer, 2011. — P. 139-146. — ISBN 978-0-387-09765-7. </ref>.

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

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

Решение задачи основано на понятии битонной последовательности. Исходный массив преобразуется в битонную последовательность. Для этого нужно разделить последовательность пополам, первую часть рекурсивно отсортировать по возрастанию, вторую часть рекурсивно отсортировать по убыванию <ref> Bimlibik: [https://bimlibik.github.io/posts/sorting-algorithm/. Алгоритмы сортировки] </ref>.

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

В данном алгоритме необходимо, чтобы размер исходного массива был равен степени двойки. В противном случае, его придется дополнять фиктивными элементами, что, однако, не влияет не асимптотику <ref> Habr: [https://habr.com/ru/articles/335920/. Описание алгоритмов сортировки и сравнение их производительности] </ref>.

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

Вычислительное ядро алгоритма битонной сортировки можно представить следующим образом <ref>Ionescu, M.F., & Schauser, K.E. (1990). Optimizing Parallel Bitonic Sort. Department of Computer Science, University of California.</ref>:

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

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

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

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

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

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

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

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

=== Последовательная сложность алгоритма ===
Сложность алгоритма битонной сортировки зависит от количества элементов в массиве. Обозначим эту величину как <math>n</math>.

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

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

=== Информационный граф ===
[[Файл:Bitonic sort.svg|обрамить|Информационный граф битонной сортировки]]

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

На диаграмме каждый рабочий поток нарисован в виде вертикальной линии, начальная и конечная точки обозначают индексы текущей пары сортируемых элементов. Все цветные блоки, находящиеся в одном столбце, образуют шаг, который можно выполнять параллельно. Из диаграммы видно, что количество потоков на шаг постоянно и всегда равно <math> n/2</math>, где <math> n</math> — количество сортируемых элементов <ref> Ponies&Light: [https://poniesandlight.co.uk/reflect/bitonic_merge_sort/. Implementing Bitonic Merge Sort in Vulkan Compute] </ref>.

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

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

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

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

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

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

=== Свойства алгоритма ===
Временная сложность алгоритма:
* При последовательной реализации <math>O(nlog^2(n))</math>
* При параллельной реализации <math>O(log^2(n))</math>

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

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

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

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

=== Особенности реализации последовательного алгоритма ===

=== Локальность данных и вычислений ===

=== Возможные способы и особенности параллельной реализации алгоритма ===

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

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

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

[[Файл:Зависимость времени работы алгоритма от длины массива и количества процессов.png|мини|центр|Зависимость времени работы алгоритма от длины массива и количества MPI процессов]]

=== Динамические характеристики и эффективность реализации алгоритма ===

=== Выводы для классов архитектур ===

=== Существующие реализации алгоритма ===
[https://www.geeksforgeeks.org/bitonic-sort/ Реализация битонной сортировки от GeeksforGeeks]

[https://people.cs.rutgers.edu/~venugopa/parallel_summer2012/bitonic_openmp.html Реализация битонной сортировки, найденная на сайте Parallel Computing]

[https://www.sortvisualizer.com/bitonicsort/ Реализация битонной сортировки с красивым интерфейсом сайта, где можно наглядно увидеть как работает последовательный алгоритм сортировки]

== Литература ==
<references />

[[en:Description of algorithm properties and structure]]

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

2023-12-02T14:26:19Z

Полина Кривуля: /* Масштабируемость алгоритма и его реализации */

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

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

'''Битонная сортировка''' – это параллельный алгоритм сортировки, основанный на использовании понятия '''битонной последовательности'''. Алгоритм разработан американским информатиком Кеннетом Бэтчером в 1968 году и является одним из старейших параллельных алгоритмов сортировки. Наряду с четно-нечетной сортировкой слиянием, является одним из первых методов построения сортировочной сети для любого количества входов <ref> Википедия: [https://ru.wikipedia.org/wiki/Битонная_сортировка#:~:text=Битонная%20сортировка%20(англ.,лежит%20понятие%20«битонной%20последовательности». Битонная сортировка] </ref>. Публикация этого алгоритма, наряду с также предложенным Бэтчером алгоритмом [[сеть нечетно-четной перестановки]], стимулировала развитие проектирования и анализа параллельных алгоритмов в общем и параллельной сортировки в частности.

'''Битонной последовательностью''' называют последовательность, которая монотонно не убывает, а затем монотонно не возрастает, либо приводится к такому виду в результате циклического сдвига. Пример такой последовательности – {8, 10, 16, 12, 4, -2, -8} <ref> Дальневосточный Федеральный университет: [https://cc.dvfu.ru/ru/lesson-10/ Занятие 10. Программирование на CUDA. Часть 6.] </ref>.
Любая последовательность, входящая в битонную, любая последовательность состоящая из одного или двух элементов, а также любая монотонная последовательность также является битонной. Например, последовательности {3,5,10,4,1}, {1,5}, {10,14,5,-1,-4} являются битонными, а {4,6,1,9,2} не является. Каждое множество неотсортированных элементов можно считать множеством битонных последовательностей, состоящих из двух элементов. Процесс битонного слияния преобразует битонную последовательность в полностью отсортированную последовательность. Алгоритм битонной сортировки состоит из применения битонных преобразований до тех пор, пока множество не будет полностью отсортировано <ref> Selim G. Akl. Bitonic Sort (англ.) // Encyclopedia of Parallel Computing : энциклопедия. — Springer, 2011. — P. 139-146. — ISBN 978-0-387-09765-7. </ref>.

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

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

Решение задачи основано на понятии битонной последовательности. Исходный массив преобразуется в битонную последовательность. Для этого нужно разделить последовательность пополам, первую часть рекурсивно отсортировать по возрастанию, вторую часть рекурсивно отсортировать по убыванию <ref> Bimlibik: [https://bimlibik.github.io/posts/sorting-algorithm/. Алгоритмы сортировки] </ref>.

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

В данном алгоритме необходимо, чтобы размер исходного массива был равен степени двойки. В противном случае, его придется дополнять фиктивными элементами, что, однако, не влияет не асимптотику <ref> Habr: [https://habr.com/ru/articles/335920/. Описание алгоритмов сортировки и сравнение их производительности] </ref>.

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

Вычислительное ядро алгоритма битонной сортировки можно представить следующим образом <ref>Ionescu, M.F., & Schauser, K.E. (1990). Optimizing Parallel Bitonic Sort. Department of Computer Science, University of California.</ref>:

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

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

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

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

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

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

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

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

=== Последовательная сложность алгоритма ===
Сложность алгоритма битонной сортировки зависит от количества элементов в массиве. Обозначим эту величину как <math>n</math>.

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

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

=== Информационный граф ===
[[Файл:Bitonic sort.svg|обрамить|Информационный граф битонной сортировки]]

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

На диаграмме каждый рабочий поток нарисован в виде вертикальной линии, начальная и конечная точки обозначают индексы текущей пары сортируемых элементов. Все цветные блоки, находящиеся в одном столбце, образуют шаг, который можно выполнять параллельно. Из диаграммы видно, что количество потоков на шаг постоянно и всегда равно <math> n/2</math>, где <math> n</math> — количество сортируемых элементов <ref> Ponies&Light: [https://poniesandlight.co.uk/reflect/bitonic_merge_sort/. Implementing Bitonic Merge Sort in Vulkan Compute] </ref>.

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

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

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

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

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

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

=== Свойства алгоритма ===
Временная сложность алгоритма:
* При последовательной реализации <math>O(nlog^2(n))</math>
* При параллельной реализации <math>O(log^2(n))</math>

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

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

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

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

=== Особенности реализации последовательного алгоритма ===

=== Локальность данных и вычислений ===

=== Возможные способы и особенности параллельной реализации алгоритма ===

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

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

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

[[Файл:Зависимость времени работы алгоритма от длины массива и количества процессов.png|мини|центр|Зависимость времени работы алгоритма от длины массива и количества MPI процессов]]

=== Динамические характеристики и эффективность реализации алгоритма ===

=== Выводы для классов архитектур ===

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

== Литература ==
<references />

[[en:Description of algorithm properties and structure]]

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

2023-12-02T14:20:17Z

Полина Кривуля: /* Ресурс параллелизма алгоритма */

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

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

'''Битонная сортировка''' – это параллельный алгоритм сортировки, основанный на использовании понятия '''битонной последовательности'''. Алгоритм разработан американским информатиком Кеннетом Бэтчером в 1968 году и является одним из старейших параллельных алгоритмов сортировки. Наряду с четно-нечетной сортировкой слиянием, является одним из первых методов построения сортировочной сети для любого количества входов <ref> Википедия: [https://ru.wikipedia.org/wiki/Битонная_сортировка#:~:text=Битонная%20сортировка%20(англ.,лежит%20понятие%20«битонной%20последовательности». Битонная сортировка] </ref>. Публикация этого алгоритма, наряду с также предложенным Бэтчером алгоритмом [[сеть нечетно-четной перестановки]], стимулировала развитие проектирования и анализа параллельных алгоритмов в общем и параллельной сортировки в частности.

'''Битонной последовательностью''' называют последовательность, которая монотонно не убывает, а затем монотонно не возрастает, либо приводится к такому виду в результате циклического сдвига. Пример такой последовательности – {8, 10, 16, 12, 4, -2, -8} <ref> Дальневосточный Федеральный университет: [https://cc.dvfu.ru/ru/lesson-10/ Занятие 10. Программирование на CUDA. Часть 6.] </ref>.
Любая последовательность, входящая в битонную, любая последовательность состоящая из одного или двух элементов, а также любая монотонная последовательность также является битонной. Например, последовательности {3,5,10,4,1}, {1,5}, {10,14,5,-1,-4} являются битонными, а {4,6,1,9,2} не является. Каждое множество неотсортированных элементов можно считать множеством битонных последовательностей, состоящих из двух элементов. Процесс битонного слияния преобразует битонную последовательность в полностью отсортированную последовательность. Алгоритм битонной сортировки состоит из применения битонных преобразований до тех пор, пока множество не будет полностью отсортировано <ref> Selim G. Akl. Bitonic Sort (англ.) // Encyclopedia of Parallel Computing : энциклопедия. — Springer, 2011. — P. 139-146. — ISBN 978-0-387-09765-7. </ref>.

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

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

Решение задачи основано на понятии битонной последовательности. Исходный массив преобразуется в битонную последовательность. Для этого нужно разделить последовательность пополам, первую часть рекурсивно отсортировать по возрастанию, вторую часть рекурсивно отсортировать по убыванию <ref> Bimlibik: [https://bimlibik.github.io/posts/sorting-algorithm/. Алгоритмы сортировки] </ref>.

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

В данном алгоритме необходимо, чтобы размер исходного массива был равен степени двойки. В противном случае, его придется дополнять фиктивными элементами, что, однако, не влияет не асимптотику <ref> Habr: [https://habr.com/ru/articles/335920/. Описание алгоритмов сортировки и сравнение их производительности] </ref>.

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

Вычислительное ядро алгоритма битонной сортировки можно представить следующим образом <ref>Ionescu, M.F., & Schauser, K.E. (1990). Optimizing Parallel Bitonic Sort. Department of Computer Science, University of California.</ref>:

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

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

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

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

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

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

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

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

=== Последовательная сложность алгоритма ===
Сложность алгоритма битонной сортировки зависит от количества элементов в массиве. Обозначим эту величину как <math>n</math>.

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

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

=== Информационный граф ===
[[Файл:Bitonic sort.svg|обрамить|Информационный граф битонной сортировки]]

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

На диаграмме каждый рабочий поток нарисован в виде вертикальной линии, начальная и конечная точки обозначают индексы текущей пары сортируемых элементов. Все цветные блоки, находящиеся в одном столбце, образуют шаг, который можно выполнять параллельно. Из диаграммы видно, что количество потоков на шаг постоянно и всегда равно <math> n/2</math>, где <math> n</math> — количество сортируемых элементов <ref> Ponies&Light: [https://poniesandlight.co.uk/reflect/bitonic_merge_sort/. Implementing Bitonic Merge Sort in Vulkan Compute] </ref>.

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

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

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

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

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

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

=== Свойства алгоритма ===
Временная сложность алгоритма:
* При последовательной реализации <math>O(nlog^2(n))</math>
* При параллельной реализации <math>O(log^2(n))</math>

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

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

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

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

=== Особенности реализации последовательного алгоритма ===

=== Локальность данных и вычислений ===

=== Возможные способы и особенности параллельной реализации алгоритма ===

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

=== Динамические характеристики и эффективность реализации алгоритма ===

=== Выводы для классов архитектур ===

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

== Литература ==
<references />

[[en:Description of algorithm properties and structure]]

Файл:Зависимость времени работы алгоритма от длины массива и количества процессов.png

2023-12-02T14:16:21Z

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

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

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

2023-12-02T14:12:12Z

Полина Кривуля: /* Свойства алгоритма */

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

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

'''Битонная сортировка''' – это параллельный алгоритм сортировки, основанный на использовании понятия '''битонной последовательности'''. Алгоритм разработан американским информатиком Кеннетом Бэтчером в 1968 году и является одним из старейших параллельных алгоритмов сортировки. Наряду с четно-нечетной сортировкой слиянием, является одним из первых методов построения сортировочной сети для любого количества входов <ref> Википедия: [https://ru.wikipedia.org/wiki/Битонная_сортировка#:~:text=Битонная%20сортировка%20(англ.,лежит%20понятие%20«битонной%20последовательности». Битонная сортировка] </ref>. Публикация этого алгоритма, наряду с также предложенным Бэтчером алгоритмом [[сеть нечетно-четной перестановки]], стимулировала развитие проектирования и анализа параллельных алгоритмов в общем и параллельной сортировки в частности.

'''Битонной последовательностью''' называют последовательность, которая монотонно не убывает, а затем монотонно не возрастает, либо приводится к такому виду в результате циклического сдвига. Пример такой последовательности – {8, 10, 16, 12, 4, -2, -8} <ref> Дальневосточный Федеральный университет: [https://cc.dvfu.ru/ru/lesson-10/ Занятие 10. Программирование на CUDA. Часть 6.] </ref>.
Любая последовательность, входящая в битонную, любая последовательность состоящая из одного или двух элементов, а также любая монотонная последовательность также является битонной. Например, последовательности {3,5,10,4,1}, {1,5}, {10,14,5,-1,-4} являются битонными, а {4,6,1,9,2} не является. Каждое множество неотсортированных элементов можно считать множеством битонных последовательностей, состоящих из двух элементов. Процесс битонного слияния преобразует битонную последовательность в полностью отсортированную последовательность. Алгоритм битонной сортировки состоит из применения битонных преобразований до тех пор, пока множество не будет полностью отсортировано <ref> Selim G. Akl. Bitonic Sort (англ.) // Encyclopedia of Parallel Computing : энциклопедия. — Springer, 2011. — P. 139-146. — ISBN 978-0-387-09765-7. </ref>.

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

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

Решение задачи основано на понятии битонной последовательности. Исходный массив преобразуется в битонную последовательность. Для этого нужно разделить последовательность пополам, первую часть рекурсивно отсортировать по возрастанию, вторую часть рекурсивно отсортировать по убыванию <ref> Bimlibik: [https://bimlibik.github.io/posts/sorting-algorithm/. Алгоритмы сортировки] </ref>.

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

В данном алгоритме необходимо, чтобы размер исходного массива был равен степени двойки. В противном случае, его придется дополнять фиктивными элементами, что, однако, не влияет не асимптотику <ref> Habr: [https://habr.com/ru/articles/335920/. Описание алгоритмов сортировки и сравнение их производительности] </ref>.

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

Вычислительное ядро алгоритма битонной сортировки можно представить следующим образом <ref>Ionescu, M.F., & Schauser, K.E. (1990). Optimizing Parallel Bitonic Sort. Department of Computer Science, University of California.</ref>:

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

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

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

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

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

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

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

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

=== Последовательная сложность алгоритма ===
Сложность алгоритма битонной сортировки зависит от количества элементов в массиве. Обозначим эту величину как <math>n</math>.

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

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

=== Информационный граф ===
[[Файл:Bitonic sort.svg|обрамить|Информационный граф битонной сортировки]]

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

На диаграмме каждый рабочий поток нарисован в виде вертикальной линии, начальная и конечная точки обозначают индексы текущей пары сортируемых элементов. Все цветные блоки, находящиеся в одном столбце, образуют шаг, который можно выполнять параллельно. Из диаграммы видно, что количество потоков на шаг постоянно и всегда равно <math> n/2</math>, где <math> n</math> — количество сортируемых элементов <ref> Ponies&Light: [https://poniesandlight.co.uk/reflect/bitonic_merge_sort/. Implementing Bitonic Merge Sort in Vulkan Compute] </ref>.

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

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

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

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

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

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

=== Свойства алгоритма ===
Временная сложность алгоритма:
* При последовательной реализации <math>O(nlog^2(n))</math>
* При параллельной реализации <math>O(log^2(n))</math>

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

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

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

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

=== Особенности реализации последовательного алгоритма ===

=== Локальность данных и вычислений ===

=== Возможные способы и особенности параллельной реализации алгоритма ===

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

=== Динамические характеристики и эффективность реализации алгоритма ===

=== Выводы для классов архитектур ===

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

== Литература ==
<references />

[[en:Description of algorithm properties and structure]]

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

2023-12-02T14:02:20Z

Полина Кривуля: /* Ресурс параллелизма алгоритма */

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

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

'''Битонная сортировка''' – это параллельный алгоритм сортировки, основанный на использовании понятия '''битонной последовательности'''. Алгоритм разработан американским информатиком Кеннетом Бэтчером в 1968 году и является одним из старейших параллельных алгоритмов сортировки. Наряду с четно-нечетной сортировкой слиянием, является одним из первых методов построения сортировочной сети для любого количества входов <ref> Википедия: [https://ru.wikipedia.org/wiki/Битонная_сортировка#:~:text=Битонная%20сортировка%20(англ.,лежит%20понятие%20«битонной%20последовательности». Битонная сортировка] </ref>. Публикация этого алгоритма, наряду с также предложенным Бэтчером алгоритмом [[сеть нечетно-четной перестановки]], стимулировала развитие проектирования и анализа параллельных алгоритмов в общем и параллельной сортировки в частности.

'''Битонной последовательностью''' называют последовательность, которая монотонно не убывает, а затем монотонно не возрастает, либо приводится к такому виду в результате циклического сдвига. Пример такой последовательности – {8, 10, 16, 12, 4, -2, -8} <ref> Дальневосточный Федеральный университет: [https://cc.dvfu.ru/ru/lesson-10/ Занятие 10. Программирование на CUDA. Часть 6.] </ref>.
Любая последовательность, входящая в битонную, любая последовательность состоящая из одного или двух элементов, а также любая монотонная последовательность также является битонной. Например, последовательности {3,5,10,4,1}, {1,5}, {10,14,5,-1,-4} являются битонными, а {4,6,1,9,2} не является. Каждое множество неотсортированных элементов можно считать множеством битонных последовательностей, состоящих из двух элементов. Процесс битонного слияния преобразует битонную последовательность в полностью отсортированную последовательность. Алгоритм битонной сортировки состоит из применения битонных преобразований до тех пор, пока множество не будет полностью отсортировано <ref> Selim G. Akl. Bitonic Sort (англ.) // Encyclopedia of Parallel Computing : энциклопедия. — Springer, 2011. — P. 139-146. — ISBN 978-0-387-09765-7. </ref>.

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

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

Решение задачи основано на понятии битонной последовательности. Исходный массив преобразуется в битонную последовательность. Для этого нужно разделить последовательность пополам, первую часть рекурсивно отсортировать по возрастанию, вторую часть рекурсивно отсортировать по убыванию <ref> Bimlibik: [https://bimlibik.github.io/posts/sorting-algorithm/. Алгоритмы сортировки] </ref>.

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

В данном алгоритме необходимо, чтобы размер исходного массива был равен степени двойки. В противном случае, его придется дополнять фиктивными элементами, что, однако, не влияет не асимптотику <ref> Habr: [https://habr.com/ru/articles/335920/. Описание алгоритмов сортировки и сравнение их производительности] </ref>.

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

Вычислительное ядро алгоритма битонной сортировки можно представить следующим образом <ref>Ionescu, M.F., & Schauser, K.E. (1990). Optimizing Parallel Bitonic Sort. Department of Computer Science, University of California.</ref>:

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

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

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

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

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

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

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

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

=== Последовательная сложность алгоритма ===
Сложность алгоритма битонной сортировки зависит от количества элементов в массиве. Обозначим эту величину как <math>n</math>.

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

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

=== Информационный граф ===
[[Файл:Bitonic sort.svg|обрамить|Информационный граф битонной сортировки]]

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

На диаграмме каждый рабочий поток нарисован в виде вертикальной линии, начальная и конечная точки обозначают индексы текущей пары сортируемых элементов. Все цветные блоки, находящиеся в одном столбце, образуют шаг, который можно выполнять параллельно. Из диаграммы видно, что количество потоков на шаг постоянно и всегда равно <math> n/2</math>, где <math> n</math> — количество сортируемых элементов <ref> Ponies&Light: [https://poniesandlight.co.uk/reflect/bitonic_merge_sort/. Implementing Bitonic Merge Sort in Vulkan Compute] </ref>.

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

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

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

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

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

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

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

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

=== Особенности реализации последовательного алгоритма ===

=== Локальность данных и вычислений ===

=== Возможные способы и особенности параллельной реализации алгоритма ===

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

=== Динамические характеристики и эффективность реализации алгоритма ===

=== Выводы для классов архитектур ===

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

== Литература ==
<references />

[[en:Description of algorithm properties and structure]]

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

2023-12-02T13:59:25Z

Полина Кривуля: /* Ресурс параллелизма алгоритма */

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

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

'''Битонная сортировка''' – это параллельный алгоритм сортировки, основанный на использовании понятия '''битонной последовательности'''. Алгоритм разработан американским информатиком Кеннетом Бэтчером в 1968 году и является одним из старейших параллельных алгоритмов сортировки. Наряду с четно-нечетной сортировкой слиянием, является одним из первых методов построения сортировочной сети для любого количества входов <ref> Википедия: [https://ru.wikipedia.org/wiki/Битонная_сортировка#:~:text=Битонная%20сортировка%20(англ.,лежит%20понятие%20«битонной%20последовательности». Битонная сортировка] </ref>. Публикация этого алгоритма, наряду с также предложенным Бэтчером алгоритмом [[сеть нечетно-четной перестановки]], стимулировала развитие проектирования и анализа параллельных алгоритмов в общем и параллельной сортировки в частности.

'''Битонной последовательностью''' называют последовательность, которая монотонно не убывает, а затем монотонно не возрастает, либо приводится к такому виду в результате циклического сдвига. Пример такой последовательности – {8, 10, 16, 12, 4, -2, -8} <ref> Дальневосточный Федеральный университет: [https://cc.dvfu.ru/ru/lesson-10/ Занятие 10. Программирование на CUDA. Часть 6.] </ref>.
Любая последовательность, входящая в битонную, любая последовательность состоящая из одного или двух элементов, а также любая монотонная последовательность также является битонной. Например, последовательности {3,5,10,4,1}, {1,5}, {10,14,5,-1,-4} являются битонными, а {4,6,1,9,2} не является. Каждое множество неотсортированных элементов можно считать множеством битонных последовательностей, состоящих из двух элементов. Процесс битонного слияния преобразует битонную последовательность в полностью отсортированную последовательность. Алгоритм битонной сортировки состоит из применения битонных преобразований до тех пор, пока множество не будет полностью отсортировано <ref> Selim G. Akl. Bitonic Sort (англ.) // Encyclopedia of Parallel Computing : энциклопедия. — Springer, 2011. — P. 139-146. — ISBN 978-0-387-09765-7. </ref>.

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

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

Решение задачи основано на понятии битонной последовательности. Исходный массив преобразуется в битонную последовательность. Для этого нужно разделить последовательность пополам, первую часть рекурсивно отсортировать по возрастанию, вторую часть рекурсивно отсортировать по убыванию <ref> Bimlibik: [https://bimlibik.github.io/posts/sorting-algorithm/. Алгоритмы сортировки] </ref>.

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

В данном алгоритме необходимо, чтобы размер исходного массива был равен степени двойки. В противном случае, его придется дополнять фиктивными элементами, что, однако, не влияет не асимптотику <ref> Habr: [https://habr.com/ru/articles/335920/. Описание алгоритмов сортировки и сравнение их производительности] </ref>.

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

Вычислительное ядро алгоритма битонной сортировки можно представить следующим образом <ref>Ionescu, M.F., & Schauser, K.E. (1990). Optimizing Parallel Bitonic Sort. Department of Computer Science, University of California.</ref>:

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

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

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

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

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

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

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

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

=== Последовательная сложность алгоритма ===
Сложность алгоритма битонной сортировки зависит от количества элементов в массиве. Обозначим эту величину как <math>n</math>.

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

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

=== Информационный граф ===
[[Файл:Bitonic sort.svg|обрамить|Информационный граф битонной сортировки]]

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

На диаграмме каждый рабочий поток нарисован в виде вертикальной линии, начальная и конечная точки обозначают индексы текущей пары сортируемых элементов. Все цветные блоки, находящиеся в одном столбце, образуют шаг, который можно выполнять параллельно. Из диаграммы видно, что количество потоков на шаг постоянно и всегда равно <math> n/2</math>, где <math> n</math> — количество сортируемых элементов <ref> Ponies&Light: [https://poniesandlight.co.uk/reflect/bitonic_merge_sort/. Implementing Bitonic Merge Sort in Vulkan Compute] </ref>.

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

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

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

[[Файл:Зависимость времени выполнения от размера массива и количества процессов.png|обрамить|Зависимость времени выполнения от размера массива и количества процессов]]

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

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

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

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

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

=== Особенности реализации последовательного алгоритма ===

=== Локальность данных и вычислений ===

=== Возможные способы и особенности параллельной реализации алгоритма ===

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

=== Динамические характеристики и эффективность реализации алгоритма ===

=== Выводы для классов архитектур ===

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

== Литература ==
<references />

[[en:Description of algorithm properties and structure]]

Файл:Зависимость времени выполнения от размера массива и количества процессов.png

2023-12-02T13:58:22Z

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

Зависимость времени выполнения от размера массива и количества процессов

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

2023-12-02T13:39:04Z

Полина Кривуля: /* Информационный граф */

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

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

'''Битонная сортировка''' – это параллельный алгоритм сортировки, основанный на использовании понятия '''битонной последовательности'''. Алгоритм разработан американским информатиком Кеннетом Бэтчером в 1968 году и является одним из старейших параллельных алгоритмов сортировки. Наряду с четно-нечетной сортировкой слиянием, является одним из первых методов построения сортировочной сети для любого количества входов <ref> Википедия: [https://ru.wikipedia.org/wiki/Битонная_сортировка#:~:text=Битонная%20сортировка%20(англ.,лежит%20понятие%20«битонной%20последовательности». Битонная сортировка] </ref>. Публикация этого алгоритма, наряду с также предложенным Бэтчером алгоритмом [[сеть нечетно-четной перестановки]], стимулировала развитие проектирования и анализа параллельных алгоритмов в общем и параллельной сортировки в частности.

'''Битонной последовательностью''' называют последовательность, которая монотонно не убывает, а затем монотонно не возрастает, либо приводится к такому виду в результате циклического сдвига. Пример такой последовательности – {8, 10, 16, 12, 4, -2, -8} <ref> Дальневосточный Федеральный университет: [https://cc.dvfu.ru/ru/lesson-10/ Занятие 10. Программирование на CUDA. Часть 6.] </ref>.
Любая последовательность, входящая в битонную, любая последовательность состоящая из одного или двух элементов, а также любая монотонная последовательность также является битонной. Например, последовательности {3,5,10,4,1}, {1,5}, {10,14,5,-1,-4} являются битонными, а {4,6,1,9,2} не является. Каждое множество неотсортированных элементов можно считать множеством битонных последовательностей, состоящих из двух элементов. Процесс битонного слияния преобразует битонную последовательность в полностью отсортированную последовательность. Алгоритм битонной сортировки состоит из применения битонных преобразований до тех пор, пока множество не будет полностью отсортировано <ref> Selim G. Akl. Bitonic Sort (англ.) // Encyclopedia of Parallel Computing : энциклопедия. — Springer, 2011. — P. 139-146. — ISBN 978-0-387-09765-7. </ref>.

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

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

Решение задачи основано на понятии битонной последовательности. Исходный массив преобразуется в битонную последовательность. Для этого нужно разделить последовательность пополам, первую часть рекурсивно отсортировать по возрастанию, вторую часть рекурсивно отсортировать по убыванию <ref> Bimlibik: [https://bimlibik.github.io/posts/sorting-algorithm/. Алгоритмы сортировки] </ref>.

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

В данном алгоритме необходимо, чтобы размер исходного массива был равен степени двойки. В противном случае, его придется дополнять фиктивными элементами, что, однако, не влияет не асимптотику <ref> Habr: [https://habr.com/ru/articles/335920/. Описание алгоритмов сортировки и сравнение их производительности] </ref>.

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

Вычислительное ядро алгоритма битонной сортировки можно представить следующим образом <ref>Ionescu, M.F., & Schauser, K.E. (1990). Optimizing Parallel Bitonic Sort. Department of Computer Science, University of California.</ref>:

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

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

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

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

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

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

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

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

=== Последовательная сложность алгоритма ===
Сложность алгоритма битонной сортировки зависит от количества элементов в массиве. Обозначим эту величину как <math>n</math>.

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

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

=== Информационный граф ===
[[Файл:Bitonic sort.svg|обрамить|Информационный граф битонной сортировки]]

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

На диаграмме каждый рабочий поток нарисован в виде вертикальной линии, начальная и конечная точки обозначают индексы текущей пары сортируемых элементов. Все цветные блоки, находящиеся в одном столбце, образуют шаг, который можно выполнять параллельно. Из диаграммы видно, что количество потоков на шаг постоянно и всегда равно <math> n/2</math>, где <math> n</math> — количество сортируемых элементов <ref> Ponies&Light: [https://poniesandlight.co.uk/reflect/bitonic_merge_sort/. Implementing Bitonic Merge Sort in Vulkan Compute] </ref>.

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

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

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

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

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

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

=== Особенности реализации последовательного алгоритма ===

=== Локальность данных и вычислений ===

=== Возможные способы и особенности параллельной реализации алгоритма ===

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

=== Динамические характеристики и эффективность реализации алгоритма ===

=== Выводы для классов архитектур ===

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

== Литература ==
<references />

[[en:Description of algorithm properties and structure]]

Файл:Bitonic sort.svg

2023-12-02T13:32:32Z

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

Bitonic sort

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

2023-12-02T13:29:13Z

Полина Кривуля: /* Схема реализации последовательного алгоритма */

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

2023-12-02T13:19:27Z

Полина Кривуля: /* Макроструктура алгоритма */

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

2023-11-07T11:07:09Z

Полина Кривуля: /* Вычислительное ядро алгоритма */

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

2023-11-07T11:06:28Z

Полина Кривуля: /* Свойства и структура алгоритмов */

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

2023-11-07T10:41:56Z

Полина Кривуля: /* Программная реализация алгоритма */

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

2023-11-07T10:38:46Z

Полина Кривуля: /* Последовательная сложность алгоритма */

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

2023-11-07T10:37:54Z

Полина Кривуля: /* Математическое описание алгоритма */

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

2023-10-30T17:47:22Z

Полина Кривуля: /* Математическое описание алгоритма */

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

2023-10-30T17:42:39Z

Полина Кривуля: /* Входные и выходные данные алгоритма */

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

2023-10-24T11:40:58Z

Полина Кривуля: /* Последовательная сложность алгоритма */

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

2023-10-24T11:36:52Z

Полина Кривуля: /* Общее описание алгоритма */

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

2023-10-24T11:27:18Z

Полина Кривуля: /* Математическое описание алгоритма */

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

2023-10-24T11:02:46Z

Полина Кривуля: Математическое описание алгоритма

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

2023-10-23T18:55:35Z

Полина Кривуля: Предварительное общее описание алгоритма

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

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

'''Битонная сортировка''' – это параллельный алгоритм сортировки, основанный на '''битонной последовательности'''. Алгоритм разработан американским информатиком Кеннетом Бэтчером в 1968 году и является одним из старейших параллельных алгоритмов сортировки. Наряду с четно-нечетной сортировкой слиянием, является одним из первых методов построения сортировочной сети для любого количества входов <ref> Википедия: [https://ru.wikipedia.org/wiki/Битонная_сортировка#:~:text=Битонная%20сортировка%20(англ.,лежит%20понятие%20«битонной%20последовательности». Битонная сортировка] </ref>. Публикация этого алгоритма, наряду с также предложенным Бэтчером алгоритмом [[сеть нечетно-четной перестановки]], стимулировала развитие проектирования и анализа параллельных алгоритмов в общем и параллельной сортировки в частности.

'''Битонной последовательностью''' называют последовательность, которая монотонно не убывает, а затем монотонно не возрастает, либо приводится к такому виду в результате циклического сдвига. Пример такой последовательности – {8, 10, 16, 12, 4, -2, -8} <ref> Дальневосточный Федеральный университет: [https://cc.dvfu.ru/ru/lesson-10/ Занятие 10. Программирование на CUDA. Часть 6.] </ref>.
Любая последовательность, входящая в битонную, любая последовательность состоящая из одного или двух элементов, а также любая монотонная последовательность также является битонной. Например, последовательности {3,5,10,4,1}, {1,5}, {10,14,5,-1,-4} являются битонными, а {4,6,1,9,2} не является. Каждое множество неотсортированных элементов можно считать множеством битонных последовательностей, состоящих из двух элементов. Процесс битонного слияния преобразует битонную последовательность в полностью отсортированную последовательность. Алгоритм битонной сортировки состоит из применения битонных преобразований до тех пор, пока множество не будет полностью отсортировано <ref> Selim G. Akl. Bitonic Sort (англ.) // Encyclopedia of Parallel Computing : энциклопедия. — Springer, 2011. — P. 139-146. — ISBN 978-0-387-09765-7. </ref>.

Время работы алгоритма составляет <math> O(log^2(n))</math>.

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

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

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

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

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

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

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

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

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

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

=== Особенности реализации последовательного алгоритма ===

=== Локальность данных и вычислений ===

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

=== Динамические характеристики и эффективность реализации алгоритма ===

=== Выводы для классов архитектур ===

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

== Литература ==
<references />

[[en:Description of algorithm properties and structure]]