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

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

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

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

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

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

Пример

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

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

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

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

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

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

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

В середине 1960-х годов Кеннет Бэтчер работал в , где занимался проектированием параллельных процессоров с тысячами обрабатывающих элементов. Работая над решением задачи сортировки данных он пришел к выводу, что последовательные алгоритмы сортировки слишком медленные и необходимо изучить возможность создания параллельных алгоритмов сортировки. Он рассмотрел хорошо известную сортировку слиянием и обнаружил, что её первые шаги легко распараллеливаются, но более поздние слияния работают последовательно и требуют много времени. В результате он открыл два алгоритма, основанных на слиянии — битонную сортировку и . Бэтчер представил эти алгоритмы в своей статье «Sorting networks and their applications» на конференции в 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 // . — Springer , 2012. — С. -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 : .
• Owens J. D. et al. GPU Computing (англ.) // Proceedings of the IEEE. — 2008. — May (vol. 96 , no. 5). — P. 879 - 899 . — doi : .