Biton sort

biton sort
Rețea de sortare Biton pentru opt intrări
Autor	Kenneth Edward Batcher
scop	Algoritm de sortare
cel mai rău moment
Cel mai bun timp
Timp mediu

Sortarea bitonic este un algoritm paralel  pentru sortarea datelor, o metodă pentru crearea unei rețele de sortare . Dezvoltat de informaticianul american Kenneth Batcher în 1968. Algoritmul se bazează pe conceptul de „secvență de bitoni”. Numele a fost ales prin analogie cu succesiunea monotonă [1] .

Sortarea bitonică este unul dintre cei mai vechi algoritmi de sortare paralelă [2] . Alături de sortarea de îmbinare par-impar , este una dintre primele metode de construire a unei rețele de sortare pentru orice număr de intrări [3] .

Descrierea algoritmului

Algoritmul se bazează pe sortarea secvențelor bitonice. O astfel de secvență este o secvență care mai întâi nu scade monoton și apoi nu crește monoton, sau este redusă la o astfel de formă ca urmare a unei deplasări ciclice [3] [4] [2] .

Orice secvență inclusă într-o secvență bitonică, orice secvență constând din unul sau două elemente și, de asemenea, orice secvență monotonă este, de asemenea, bitonică. De exemplu, secvențele {3,5,10,4,1}, {1,5}, {10,14,5,-1,-4} sunt bitonice, dar {4,6,1,9,2 } nu sunt este. Fiecare set de elemente nesortate poate fi considerat un set de secvențe bitonice constând din două elemente [3] [4] [5] [2] .

Procesul de îmbinare bitonică transformă o secvență bitonică într-o secvență complet sortată. Algoritmul de sortare bitonic constă în aplicarea transformărilor bitonice până când mulțimea este complet sortată [5] [2] .

Exemplu

Figura prezintă o rețea de sortare bitonică pentru 16 elemente, care sortează setul în ordine crescătoare. Săgețile reprezintă comparatori , care compară două numere și, dacă este necesar, le schimbă astfel încât direcția săgeții să indice numărul mai mare.

Dreptunghiurile roșii sunt combinate în dreptunghiuri verzi și albastre. În dreptunghiurile albastre, săgețile comparatoarelor indică în jos (creează secvențe crescătoare), în dreptunghiuri verzi indică în sus (creează secvențe descrescătoare). Fiecare dintre aceste dreptunghiuri are aceeași structură: dreptunghiul roșu este aplicat întregii secvențe, apoi fiecărei jumătăți a rezultatelor și așa mai departe. Dacă o secvență bitonică este alimentată la intrările unui astfel de dreptunghi, atunci la ieșire este convertită într-una complet sortată. Rezultatele combinate ale casetelor albastre și verzi sunt o secvență bitonică.

Fiecare coloană de dreptunghiuri albastre și verzi ia N secvențe sortate (în primul pas, 16 secvențe sortate cu 1 element) și le transformă în N/2 secvențe sortate.

Reprezentare alternativă

Există o reprezentare alternativă și mai comună a tipului Biton care diferă de versiunea originală a lui Butcher. Pentru a scăpa de comparatori care mută date în direcții diferite, conexiunile dintre ele au fost modificate, pe baza proprietății că din oricare două secvențe sortate (adică monotonă) puteți obține o secvență bitonică schimbând ordinea într-una dintre ele la opus . 4 ] .

Astfel, toate dreptunghiurile albastre din figură efectuează aceleași operații. Dreptunghiurile maro sunt blocuri roșii modificate, ale căror intrări și ieșiri sunt conectate în ordine inversă în partea de jos.

Istoricul descoperirilor

La mijlocul anilor 1960, Kenneth Batcher a lucrat la Goodyear Aerospace , unde a fost angajat în proiectarea de procesoare paralele cu mii de elemente de procesare. Lucrând la rezolvarea problemei sortării datelor, a ajuns la concluzia că algoritmii de sortare secvenţială sunt prea lenţi şi este necesar să se studieze posibilitatea creării algoritmilor de sortare paralelă. El a revizuit binecunoscutul mergesort și a descoperit că primii pași ai acestuia sunt ușor de paralelizat, dar îmbinările ulterioare sunt secvențiale și consumatoare de timp. Ca rezultat, el a descoperit doi algoritmi bazați pe îmbinări, sortarea bitonic și sortarea îmbinării par-impar . Batcher a introdus acești algoritmi în lucrarea sa „Sorting networks and their applications” la Joint Computer Conference în 1968 [3] .

Batcher însuși a recunoscut mai târziu că numele este analfabet, deoarece combină un prefix latin și o rădăcină greacă. Un nume mai corect ar fi „ditonic” [3] [5] .

Influență și aplicare

Sortarea bitonică este unul dintre primii algoritmi de sortare paralelă. Publicarea acestui algoritm, împreună cu algoritmul de sortare de îmbinare par-impar propus tot de Batcher , a stimulat dezvoltarea proiectării și analizei algoritmilor paraleli în general și sortării paralele în special [2] .

Datorită paralelismului lor ridicat, sortatoarele de bitoni sunt utilizate pe scară largă în dispozitivele care vizează calculul masiv paralel, cum ar fi GPU -urile [6] și FPGA -urile [7] , dar sunt rareori utilizate în supercalculatoarele moderne [1] .

În GPU-urile timpurii, din cauza API -ului limitat și a indisponibilității operațiunii de împrăștiere, sortarea bitonică a fost algoritmul dominant. În special pentru GPU-uri, a fost dezvoltat algoritmul „GNUTeraSort”, bazat pe sortarea bitonică și bitonică, apoi GPU-ABiSort, folosind sortarea bitonică adaptivă. Odată cu apariția arhitecturii hardware și software CUDA , au fost introduse versiuni eficiente ale altor algoritmi de sortare paralelă, iar sortarea pe biți domină în prezent pe GPU [1] .

Note

1. ↑ 1 2 3 Kalé, Solomonik, 2011 .
2. ↑ 1 2 3 4 5 Akl, 2011 .
3. ↑ 1 2 3 4 5 Baddar, Batcher, 2012 .
4. ↑ 1 2 3 Cormen și colab., 2001 .
5. ↑ 1 2 3 Knuth, 1998 .
6. ↑ Owens JD și colab., 2008 .
7. ↑ Mueller, Teubner, Alonso, 2009 .

Literatură

• Laxmikant V. Kale, Edgar Solomonik. Sortare  (engleză)  // Encyclopedia of Parallel Computing : enciclopedie. - Springer , 2011. - P. 1855-1861 . - ISBN 978-0-387-09765-7 .
• Selim G. Akl. Sortare Bitonic  (engleză)  // Encyclopedia of Parallel Computing : enciclopedie. - Springer , 2011. - P. 139-146 . - ISBN 978-0-387-09765-7 .
• Sherenaz W. Al-Haj Baddar, Kenneth E. Batcher. Fuziune Bitonică // Proiectarea rețelelor de sortare: o nouă paradigmă . - Springer , 2012. - S.  2-5 . — 148 p. — ISBN 978-1461418504 .
• Donald E. Knuth . Sortare bitonică // Arta programării computerelor . - 2. - Addison-Wesley , 1998. - T. 3. - S. 230-232. — 780 s. — ISBN 9780201896855 .
• Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest , Clifford Stein . Sortare bitonică // Introducere în algoritmi . - 2. - MIT Press , 2001. - S. 608-611. — 984 p. — ISBN 9780070131514 .
• Mueller R., Teubner J., Alonso G. Procesarea datelor pe FPGA-uri  //  Proceedings of the VLDB Endowment. - 2009. - August. — P. 910-921 . - doi : 10.14778/1687627.1687730 .
• Owens JD și colab. GPU Computing  //  Proceedings of the IEEE. - 2008. - Mai ( vol. 96 , nr. 5 ). - P. 879 - 899 . - doi : 10.1109/JPROC.2008.917757 .