Битонная сортировка

Битонная сортировка
Битонная сортировочная сеть для восьми входов
Предназначение	Алгоритм сортировки
Худшее время	[math]\displaystyle{ O(\log^2(n)) }[/math]
Лучшее время	[math]\displaystyle{ O(\log^2(n)) }[/math]
Среднее время	[math]\displaystyle{ O(\log^2(n)) }[/math]

Битонная сортировка (англ. Bitonic sorter) — параллельный алгоритм сортировки данных, метод для создания сортировочной сети. Разработан американским информатиком Кеннетом Бэтчером в 1968 году. В основе алгоритма лежит понятие «битонной последовательности». Название было выбрано по аналогии с монотонной последовательностью.

Битонная сортировка — один из старейших параллельных алгоритмов сортировки. Наряду с четно-нечетной сортировки слиянием, является одним из первых методов построения сортировочной сети для любого количества входов.

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

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

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

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

Пример

Diagram of the bitonic sorting network with 16 inputs and arrows

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

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

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

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

Diagram of the bitonic sorting network with 16 inputs

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

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

История открытия

В середине 1960-х годов Кеннет Бэтчер работал в Goodyear Aerospace, где занимался проектированием параллельных процессоров с тысячами обрабатывающих элементов. Работая над решением задачи сортировки данных он пришел к выводу, что последовательные алгоритмы сортировки слишком медленные и необходимо изучить возможность создания параллельных алгоритмов сортировки. Он рассмотрел хорошо известную сортировку слиянием и обнаружил, что её первые шаги легко распараллеливаются, но более поздние слияния работают последовательно и требуют много времени. В результате он открыл два алгоритма, основанных на слиянии — битонную сортировку и четно-нечетную сортировку слиянием. Бэтчер представил эти алгоритмы в своей статье «Sorting networks and their applications» на конференции Joint Computer Conference в 1968 году.

Сам Бэтчер позднее признал, что название является неграмотным, так как комбинирует латинскую приставку и греческий корень. Более правильным названием было бы «дитонная» (ditonic).

Влияние и применение

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

Благодаря высокой параллельности, битонные сортировщики широко применяются в устройствах, нацеленных на массивные параллельные вычисления, таких как графические процессоры и ПЛИС, но редко используется в современных суперкомпьютерах.

В ранних графических процессорах, в связи с ограниченным API и недоступностью операции рассеяния, битонная сортировка была доминирующим алгоритмом. Специально для графических процессоров был разработан алгоритм «GNUTeraSort», основанный на битонной и поразрядной сортировке, а затем GPU-ABiSort, использующий адаптивную битонную сортировку. С появлением программно-аппаратной архитектуры CUDA были представлены эффективные версии других параллельных алгоритмов сортировки и в настоящее время на GPU доминирует поразрядная сортировка.

Литература

• Laxmikant V. Kalé, Edgar Solomonik. Sorting (англ.) // Encyclopedia of Parallel Computing : энциклопедия. — Springer, 2011. — P. 1855-1861. — ISBN 978-0-387-09765-7.
• Selim G. Akl. Bitonic Sort (англ.) // Encyclopedia of Parallel Computing : энциклопедия. — Springer, 2011. — P. 139-146. — ISBN 978-0-387-09765-7.
• Sherenaz W. Al-Haj Baddar, Kenneth E. Batcher. Bitonic merging // Designing Sorting Networks: A New Paradigm. — Springer, 2012. — С. 2-5. — 148 с. — ISBN 978-1461418504.
• Donald E. Knuth. Bitonic sorting // The art of computer programming. — 2. — Addison-Wesley, 1998. — Т. 3. — С. 230-232. — 780 с. — ISBN 9780201896855.
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Bitonic sorting // Introduction to algorithms. — 2. — MIT Press, 2001. — С. 608-611. — 984 с. — ISBN 9780070131514.
• Mueller R., Teubner J., Alonso G. Data processing on FPGAs (англ.) // Proceedings of the VLDB Endowment. — 2009. — August. — P. 910-921. — doi:10.14778/1687627.1687730.
• Owens J. D. et al. GPU Computing (англ.) // Proceedings of the IEEE. — 2008. — May (vol. 96, no. 5). — P. 879 - 899. — doi:10.1109/JPROC.2008.917757.