Введение

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

Bitonic mergesort — это параллельный алгоритм сортировки. Он также используется как метод построения сортировочной сети. Алгоритм был разработан Кеном Батчером. Получающиеся сортировочные сети состоят из компараторов и имеют задержку , где — количество элементов, подлежащих сортировке. Это делает его популярным выбором для сортировки большого числа элементов на архитектуре, которая сама содержит большое количество параллельных вычислительных блоков, работающих синхронно, таких как типичный графический процессор. Отсортированная последовательность — это монотонно не убывающая (или не возрастающая) последовательность. Битоническая последовательность — это последовательность с для некоторого , или циклическая перестановка такой последовательности.

Сложность

Пусть и
Из алгоритма построения следует, что число раундов параллельных сравнений задается формулой
Отсюда следует, что число компараторов ограничено (что устанавливает точное значение для , когда является степенью 2). Хотя абсолютное число сравнений обычно выше, чем в сортировке нечет-чет Батчера, многие последовательные операции в битонической сортировке сохраняют локальность доступа к памяти, что делает реализации более удобными для кэша и, как правило, более эффективными на практике.

Альтернативное представительство

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

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