Biton sortering

biton sortering
Bitonsorteringsnetværk til otte indgange
Forfatter	Kenneth Edward Batcher
formål	Sorteringsalgoritme
værste tid
Bedste tid
Gennemsnitlig tid

Bitonisk sortering er en parallel  algoritme til sortering af data, en metode til at skabe et sorteringsnetværk . Udviklet af den amerikanske datalog Kenneth Batcher i 1968. Algoritmen er baseret på begrebet "bitonsekvens". Navnet blev valgt i analogi med den monotone sekvens [1] .

Bitonisk sortering er en af ​​de ældste parallelle sorteringsalgoritmer [2] . Sammen med lige-ulige flettesortering er det en af ​​de første metoder til at konstruere et sorteringsnetværk for et vilkårligt antal input [3] .

Beskrivelse af algoritmen

Algoritmen er baseret på sortering af bitoniske sekvenser. En sådan sekvens er en sekvens, der først ikke aftager monotont, og derefter ikke øges monotont, eller som er reduceret til en sådan form som følge af et cyklisk skift [3] [4] [2] .

Enhver sekvens inkluderet i en bitonisk sekvens, enhver sekvens bestående af et eller to elementer, og også enhver monoton sekvens er også bitonisk. For eksempel er sekvenserne {3,5,10,4,1}, {1,5}, {10,14,5,-1,-4} bitoniske, men {4,6,1,9,2 } er ikke er. Hvert sæt usorterede elementer kan betragtes som et sæt bitoniske sekvenser bestående af to elementer [3] [4] [5] [2] .

Den bitoniske fusionsproces konverterer en bitonisk sekvens til en fuldt sorteret sekvens. Den bitoniske sorteringsalgoritme består i at anvende bitoniske transformationer, indtil sættet er fuldstændig sorteret [5] [2] .

Eksempel

Figuren viser et bitonisk sorteringsnetværk for 16 elementer, som sorterer sættet i stigende rækkefølge. Pilene repræsenterer komparatorer , som sammenligner to tal og om nødvendigt bytter dem om, så pilens retning peger på det største tal.

De røde rektangler kombineres til grønne og blå rektangler. I de blå rektangler peger komparatorernes pile ned (skaber stigende sekvenser), i grønne rektangler peger de op (skaber faldende sekvenser). Hvert af disse rektangler har den samme struktur: det røde rektangel påføres hele sekvensen, derefter på hver halvdel af resultaterne, og så videre. Hvis en bitonisk sekvens føres til indgangene til et sådant rektangel, konverteres den ved udgangen til en fuldstændig sorteret. De kombinerede resultater af de blå og grønne felter er en bitonisk sekvens.

Hver kolonne med blå og grønne rektangler tager N sorterede sekvenser (i det allerførste trin, 16 sorterede sekvenser med 1 element) og transformerer dem til N/2 sorterede sekvenser.

Alternativ repræsentation

Der er en alternativ og mere almindelig repræsentation af Biton-sorten, der adskiller sig fra Butchers originale version. For at slippe af med komparatorer, der flytter data i forskellige retninger, blev forbindelserne mellem dem ændret, baseret på den egenskab, at du fra to sorterede sekvenser (dvs. monotone) kan få en bitonisk sekvens ved at ændre rækkefølgen i en af ​​dem til den modsatte [ 4] .

Således udfører alle de blå rektangler i figuren de samme operationer. De brune rektangler er modificerede røde blokke, hvis ind- og udgange er forbundet i omvendt rækkefølge i bunden.

Opdagelseshistorie

I midten af ​​1960'erne arbejdede Kenneth Batcher hos Goodyear Aerospace , hvor han var engageret i design af parallelle processorer med tusindvis af behandlingselementer. I arbejdet med at løse problemet med at sortere data kom han til den konklusion, at sekventielle sorteringsalgoritmer er for langsomme, og det er nødvendigt at undersøge muligheden for at skabe parallelle sorteringsalgoritmer. Han gennemgik den velkendte fusionssort og fandt ud af, at dens første trin let kan paralleliseres, men senere fusioner er sekventielle og tidskrævende. Som et resultat opdagede han to flette-baserede algoritmer, bitonisk sortering og lige-ulige fletningssortering . Batcher introducerede disse algoritmer i sit papir "Sortering af netværk og deres applikationer" på Joint Computer Conference i 1968 [3] .

Batcher selv indrømmede senere, at navnet er analfabet, da det kombinerer et latinsk præfiks og en græsk rod. Et mere korrekt navn ville være "ditonisk" [3] [5] .

Indflydelse og anvendelse

Bitonisk sortering er en af ​​de første parallelle sorteringsalgoritmer. Offentliggørelsen af ​​denne algoritme, sammen med den lige-ulige flettesorteringsalgoritme også foreslået af Batcher , stimulerede udviklingen af ​​design og analyse af parallelle algoritmer generelt og parallelsortering i særdeleshed [2] .

På grund af deres høje parallelitet, er bitonsortere i vid udstrækning brugt i enheder rettet mod massiv parallel computing, såsom GPU'er [6] og FPGA'er [7] , men bruges sjældent i moderne supercomputere [1] .

I de tidlige GPU'er, på grund af den begrænsede API og utilgængeligheden af ​​scatter-operationen, var bitonisk sortering den dominerende algoritme. Specielt for GPU'er blev "GNUTeraSort"-algoritmen udviklet, baseret på bitonisk og bitonisk sortering , og derefter GPU-ABiSort, ved hjælp af adaptiv bitonisk sortering. Med fremkomsten af ​​CUDA hardware- og softwarearkitekturen er effektive versioner af andre parallelle sorteringsalgoritmer blevet introduceret, og bitvis sortering dominerer i øjeblikket på GPU'en [1] .

Noter

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 et al., 2001 .
5. ↑ 1 2 3 Knuth, 1998 .
6. ↑ Owens JD et al., 2008 .
7. ↑ Mueller, Teubner, Alonso, 2009 .

Litteratur

• Laxmikant V. Kale, Edgar Solomonik. Sortering  (engelsk)  // Encyclopedia of Parallel Computing : encyclopedia. - Springer , 2011. - P. 1855-1861 . - ISBN 978-0-387-09765-7 .
• Selim G. Akl. Bitonic Sort  (engelsk)  // Encyclopedia of Parallel Computing: encyklopædi. - Springer , 2011. - S. 139-146 . - ISBN 978-0-387-09765-7 .
• Sherenaz W. Al-Haj Baddar, Kenneth E. Batcher. Bitonic sammensmeltning // Designing Sorting Networks: A New Paradigm . - Springer , 2012. - S.  2-5 . — 148 s. — ISBN 978-1461418504 .
• Donald E. Knuth . Bitonisk sortering // Computerprogrammerings kunst . - 2. - Addison-Wesley , 1998. - T. 3. - S. 230-232. - 780 s. — ISBN 9780201896855 .
• Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest , Clifford Stein . Bitonisk sortering // Introduktion til algoritmer . - 2. - MIT Press , 2001. - S. 608-611. — 984 s. — ISBN 9780070131514 .
• Mueller R., Teubner J., Alonso G. Databehandling på FPGA'er  //  Proceedings of the VLDB Endowment. - 2009. - August. — S. 910-921 . - doi : 10.14778/1687627.1687730 .
• Owens JD et al. GPU Computing  //  Proceedings of the IEEE. - 2008. - Maj ( bd. 96 , nr. 5 ). - S. 879 - 899 . - doi : 10.1109/JPROC.2008.917757 .