Bit sort

The algorithm is based on sorting bit sequences. Such a sequence is called a sequence that at first does not decrease monotonously and then does not increase monotonically, or is reduced to this form as a result of a cyclic shift ^{[3] [4] [2]} .

Any sequence included in a bitonic sequence, any sequence consisting of one or two elements, and also any monotonic sequence is also a bitonic sequence. For example, the sequences {3,5,10,4,1}, {1,5}, {10,14,5, -1, -4} are bitonic, and {4,6,1,9,2} are not is an. Each set of unsorted elements can be considered as a set of bitone sequences consisting of two elements ^{[3] [4] [5] [2]} .

The bitwise merge process converts a bitonic sequence into a fully sorted sequence. The biton sorting algorithm consists of applying biton transforms until the set is completely sorted ^{[5] [2]} .

Example

The figure shows a biton sorting network for 16 elements, which sorts the set in ascending order. The arrows depict comparators that compare two numbers and, if necessary, swap them so that the direction of the arrow indicates a larger number.

The red rectangles are combined into green and blue rectangles. In the blue rectangles, the arrows of the comparators are directed downward (create ascending sequences), in the green rectangles upward (create descending sequences). Each of these rectangles has the same structure: a red rectangle is applied to the entire sequence, then to each half of the results, and so on. If a bitone sequence is supplied to the inputs of such a rectangle, then at the output it is converted to a fully sorted one. The combined results of the blue and green rectangle is a bitwise sequence.

Each column of blue and green rectangles takes N sorted sequences (in the very first step, 16 sorted sequences consisting of 1 element) and converts them into N / 2 sorted sequences.

Alternate View

There is an alternative and more common representation of Biton sort, which differs from the original version of Butcher. In order to get rid of comparators moving data in different directions, the connections between them were changed, based on the property that from any two sorted sequences (ie, monotonic) you can get a bitone sequence by changing the order in one of them to the opposite ^{[4 ]} .

Thus, all the blue rectangles in the figure perform the same operations. The brown rectangles are modified red blocks, the inputs and outputs of the lower part of which are connected in the reverse order.

In the mid-1960s, Kenneth Batcher worked at , where he designed parallel processors with thousands of processing elements. While working on the solution of the data sorting problem, he came to the conclusion that sequential sorting algorithms are too slow and it is necessary to study the possibility of creating parallel sorting algorithms. He looked at the well-known merge sort and found that its first steps are easy to parallelize, but later merges work sequentially and take a lot of time. As a result, he discovered two merge-based algorithms - bitwise sorting and even-odd merge sorting . Batcher introduced these algorithms in his article “Sorting networks and their applications” at the 1968 ^[3] .

Batcher himself later admitted that the name is illiterate, as it combines the Latin prefix and the Greek root. A more correct name would be “ditonic” ^{[3] [5]} .

Bit sorting is one of the first parallel sorting algorithms. The publication of this algorithm, along with the even-even odd merge sorting algorithm proposed by Batcher, stimulated the development of the design and analysis of parallel algorithms in general and parallel sorting in particular ^[2] .

Due to its high parallelism, bitone sorters are widely used in devices aimed at massive parallel computing, such as GPUs ^[6] and FPGAs ^[7] , but are rarely used in modern supercomputers ^[1] .

In early GPUs, due to the limited API and inaccessibility of the scatter operation, bitwise sorting was the dominant algorithm. The “GNUTeraSort” algorithm was developed specifically for graphics processors, based on bit-by- bit and bitwise sorting , and then GPU-ABiSort, using adaptive biton-sorting. With the advent of the CUDA hardware-software architecture, efficient versions of other parallel sorting algorithms were introduced and bitwise sorting is currently dominating the GPU ^[1] .

• Laxmikant V. Kalé, Edgar Solomonik. Sorting (Eng.) // Encyclopedia of Parallel Computing: Encyclopedia. - Springer , 2011 .-- P. 1855-1861 . - ISBN 978-0-387-09765-7 .
• Selim G. Akl. Bitonic Sort (Eng.) // Encyclopedia of Parallel Computing: Encyclopedia. - 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 .-- S. 2-5. - 148 p. - ISBN 978-1461418504 .
• Donald E. Knuth . Bitonic sorting // The art of computer programming . - 2. - Addison-Wesley , 1998.- T. 3. - S. 230-232. - 780 s. - ISBN 9780201896855 .
• Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest , Clifford Stein . Bitonic sorting // Introduction to algorithms . - 2. - MIT Press , 2001 .-- S. 608-611. - 984 p. - 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 JD et al. GPU Computing (English) // Proceedings of the IEEE. - 2008 .-- May ( vol. 96 , no. 5 ). - P. 879-899 . - DOI : 10.1109 / JPROC.2008.917757 .