Битонная сортировка
Битонная сортировка (англ. Bitonic sorter) — параллельный алгоритм сортировки данных, метод для создания сортировочной сети. Разработан американским информатиком Кеннетом Бэтчером в 1968 году. В основе алгоритма лежит понятие «битонной последовательности». Название было выбрано по аналогии с монотонной последовательностью[1].
| Битонная сортировка | |
|---|---|
 Битонная сортировочная сеть для восьми входов | |
| Автор | Кеннет Эдвард Бэтчер |
| Предназначение | Алгоритм сортировки |
| Худшее время | |
| Лучшее время | |
| Среднее время | |
Битонная сортировка — один из старейших параллельных алгоритмов сортировки[2]. Наряду с четно-нечетной сортировки слиянием, является одним из первых методов построения сортировочной сети для любого количества входов[3].
Описание алгоритма
Алгоритм основан на сортировке битонных последовательностей. Такой последовательностью называется последовательность, которая сначала монотонно не убывает, а затем монотонно не возрастает, либо приводится к такому виду в результате циклического cдвига[3][4][2].
Любая последовательность, входящая в битонную, любая последовательность состоящая из одного или двух элементов, а также любая монотонная последовательность также является битонной. Например, последовательности {3,5,10,4,1}, {1,5}, {10,14,5,-1,-4} являются битонными, а {4,6,1,9,2} не является. Каждое множество неотсортированных элементов можно считать множеством битонных последовательностей, состоящих из двух элементов[3][4][5][2].
Процесс битонного слияния преобразует битонную последовательность в полностью отсортированную последовательность. Алгоритм битонной сортировки состоит из применения битонных преобразований до тех пор, пока множество не будет полностью отсортировано[5][2].
Пример
На рисунке изображена битонная сортировочная сеть для 16 элементов, которая сортирует множество по возрастанию. Стрелки изображают компараторы, которые сравнивают два числа и при необходимости меняют их местами таким образом, чтобы направление стрелки указывало на большее число.
Красные прямоугольники скомбинированы в зеленые и голубые прямоугольники. В синих прямоугольниках стрелки компараторов направлены вниз (создают возрастающие последовательности), в зеленых — вверх (создают убывающие последовательности). Каждый из таких прямоугольников имеет одинаковую структуру: красный прямоугольник применяется ко всей последовательности, затем к каждой половине полученных результатов и так далее. Если на входы такого прямоугольника подается битонная последовательность, то на выходе она преобразуется в полностью отсортированную. Объединенные результаты синего и зеленого прямоугольника является битонной последовательностью.
Каждый столбец синих и зеленых прямоугольников принимает N отсортированных последовательностей (на самом первом шаге 16 отсортированных последовательностей, состоящих из 1 элемента) и преобразует их в N/2 отсортированных последовательностей.
Альтернативное представление
Существует альтернативное и более распространенное представление Битонной сортировки, которое отличается от оригинальной версии Батчера. Чтобы избавиться от компараторов, перемещающих данные в разных направлениях, соединения между ними были изменены, основываясь на том свойстве, что из любых двух отсортированных последовательностей (т.е. монотонных) можно получить битонную последовательность, изменив порядок в одной из них на противоположный[4].
Таким образом все синие прямоугольники на рисунке выполняют одинаковые операции. Коричневые прямоугольники являются модифицированными красными блоками, входы и выходы нижней части которых подсоединены в обратном порядке.
История открытия
В середине 1960-х годов Кеннет Бэтчер работал в Goodyear Aerospace, где занимался проектированием параллельных процессоров с тысячами обрабатывающих элементов. Работая над решением задачи сортировки данных он пришел к выводу, что последовательные алгоритмы сортировки слишком медленные и необходимо изучить возможность создания параллельных алгоритмов сортировки. Он рассмотрел хорошо известную сортировку слиянием и обнаружил, что её первые шаги легко распараллеливаются, но более поздние слияния работают последовательно и требуют много времени. В результате он открыл два алгоритма, основанных на слиянии — битонную сортировку и четно-нечетную сортировку слиянием. Бэтчер представил эти алгоритмы в своей статье «Sorting networks and their applications» на конференции Joint Computer Conference в 1968 году[3].
Сам Бэтчер позднее признал, что название является неграмотным, так как комбинирует латинскую приставку и греческий корень. Более правильным названием было бы «дитонная» (ditonic)[3][5].
Влияние и применение
Битонная сортировка является одним из первых параллельных алгоритмов сортировки. Публикация этого алгоритма, наряду с также предложенным Бэтчером алгоритмом четно-нечетной сортировки слиянием, стимулировала развитие проектирования и анализа параллельных алгоритмов в общем и параллельной сортировки в частности[2].
Благодаря высокой параллельности, битонные сортировщики широко применяются в устройствах, нацеленных на массивные параллельные вычисления, таких как графические процессоры[6] и ПЛИС[7], но редко используется в современных суперкомпьютерах[1].
В ранних графических процессорах, в связи с ограниченным API и недоступностью операции рассеяния, битонная сортировка была доминирующим алгоритмом. Специально для графических процессоров был разработан алгоритм «GNUTeraSort», основанный на битонной и поразрядной сортировке, а затем GPU-ABiSort, использующий адаптивную битонную сортировку. С появлением программно-аппаратной архитектуры CUDA были представлены эффективные версии других параллельных алгоритмов сортировки и в настоящее время на GPU доминирует поразрядная сортировка[1].
Примечания
Литература
- 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.