Sortirajuća mreža

U računarskim naukama, komparativne mreže su abstraktni uredjaji sačinjeni od određenog broja „žica“, koje sadrže neke vrednosti, i komparativnih modula koji povezuju parove žica i menjaju vrednosti na njima ako se ne nalaze u željenom odnosu. Takve mreže se najčešće konstruišu da bi se izvelo sortiranje odredjenog broja vrednosti i tada se nazivaju sortirajuće mreže.

Sortirajuće mreže se razlikuju od sortiranja metodom poredjenja u tome što one nisu sposobne da rade sa proizvoljno velikim unosima i u tome što se njihova sekvenca poređenja određuje unapred, bez obzira na ishod prošlih poređenja. Ta nezavisnot od sekvence poređenja je korisna pri paralelnom izvršavanju i u hardverskoj implementaciji. Bez obzira na jednostavnost sortirajućih mreža, teorija iza njih je iznenađujuće kompleksna. Njih su prvi put proučavali Arsmstrong, Nelson i O'Konor oko 1954. godine, koji su tada i stavili patent na tu ideju.^[1]

Sortirajuće mreže se mogu implementirati preko hardvera i softvera. Donald Knut je opisao kako se poredjenja binarnih celih brojeva mogu implementirati kao jednostavni uredjaji sa tri stanja. Bečer je 1968, predložio da se sortirajuće mreže koriste za izradu prekidačkih mreža za računarski hardver, i da time zamene sve elekronske komponente i skuplje crossbar prekidače. U poslednjih 15 godina sortirajuće mreže, a naročito bitonik sort se koriste od strane GPGPU udruženja za izradu sortirajućih algoritama koji bi radili na grafičkim procesorskim jedinicama.^[2]

Uvod

Demonstracij akomparatora u sortirajućoj mreži

Sortirajuća mreža se sastoji od dva tipa elemenata: komparatori i žice. Žice su predstavljene da idu sa leva na desno, noseći vrednosti (jedna vrednost po žici) koje se kreću mrežom u svakom trenutku. Svaki komparator povezuje dve žice. Kada par vrednosti koji putuje kroz par žica naiđe na komparator, komparator menja mesta vrednostima ako i samo ako je vrednost gornje žice veća od vrednosti donje.

Po formuli, ako gornja žica prenosi x, a donja y, onda će pošto nalete na komparator žice nose x’ = min(x,y) i

y’ = max(x, y), tako da je par vrednosti sortiran. Mreža koja će sadrži odredjen broj žica i komparator koji su zajedno sposobni da sortiraju vrednosti se naziva sortirajuća mreža.

Potpuna operacija jednostavne sortirajuće mreže je prikazana ispod. Jasno se vidi zašto će ova mreža ispravno sortirati ulaze.

Dubina i efikasnost

Efikasnost sortirajuće mreže se može proceniti na osnovu njene veličine. Ona predstavlja broj komparatora ili neformalno dubinu koja je određena kao najveći broj komparatora koje jedna ulazna vrednost može da susretne svojim putem kroz mrežu. Ako uzmemo u obzir da sortirajuće mreže mogu da rade određena poređenja paralelno i ako pretpostavimo da svim poređenjima treba određena jedinica vremena, možemo reći da je dubina mreže jednaka broju koraka koji su potrebni da se izvrši.

Ubacivanje u mrežu i selekcija

Svaku mrežu možemo konstruisati rekurzivno na osnovu principa ubacivanja i selekcije. Ako pretpostavimo da imamo sortirajuću mrežu veličine n, možemo napraviti mreću veličine n+1 ubacujući dodatni broj u već sortiranu podmrežu (koristeći medote sortiranja umetanjem). Isto to možemo postići i selekcijom najniže vrednosti od ulaza i onda sortirati ostataka vrednosti rekurzivno (koristeći metode sortiranja mehurom).

Sortirajuća mreža koja je napravljena rekurzivno gde najveći element ide na dno, a onda se sortiraju ostale žice. Zasnovano na sortiranju mehurom

Sortirajuća mreža konstrisana rekurzivno tako da se prvo sortiraju n žica pa se onda dodaje preostala vrednost Zasnovano na sortiranju umetanjem

Struktura ove dve sortirajuće mreže je veoma slična. Ako spojimo ove dve metode, vidimo preko komparacija koje mogu da se izvrše istovremeno da su čak i identične.^[3]

Kad su dozvoljena paralelna poređenja, sortiranja mehurom i umetanjem su identična

Ovakve mreže imaju veliku dubinu od 2n -3, što je čini nepraktičnom.

Princip nula-jedan

Iako je lako dokazati ispravnost nekih mreža kao u gore navedenim primerima to nije uvek tako. Postoji n! Permutacija u mreži sa n žica, i testiranje svih njih traje vrlo dugo, naročito ako je n veliki broj. Taj broj može značajno da se smanji do 2n , koristeći metod koji se zove nula-jedan.

Ovaj princip kaže da ako sortirajuća mreža može da sortira 2n niza nula i jedinica, onda može da sortira i proizvoljne brojeve u istom vremenu. Ovo ne samo da smanjuje testiranje ispravnosti same mreže već je vrlo koristan pro kreiranju mnogih ovakvih konstrukcija.

Princip se može dokazati tako što se prvo primeti činjenica o komparatorima: kada se monotono rastuća funkcija f primeni na ulazne vrenosti, x i z su zamenjeni f(x) i f(y), onda komparatori prave min(f(x), f(y)) = f(min(x,y)) i max(f(x), f(y)) = f(max(x,y)). Uz pomoć indukcije rezultat se može prevesti u lemu koja kaže da ako mreža prenosi sekvencu a1, ..., an into b1, ..., bn, ona će transformirati (a1), ..., f(an) u f(b1), ..., f(bn). Dokaz dalje ide dokazivanjem suprotnog: pretpostavljamo da je neki ulaz a1, ..., an sadrži dva elementa ai < aj , i da mreža ispravno zameni mesta ovim ulazima. Onda će to takodje ispravno sortirati i f(a1), ..., f(an) za funkciju:

f(x)={\begin{cases}1\ &{\mbox{if }}x>a_{i}\\0\ &{\mbox{otherwise.}}\end{cases}}

Ova funckija je monotona, zato koristimo nula-jedan princip kao kontrapozitiv.

Konstrukcija sortirajućih mreža

Razni algoritim postoje za nastajanje jednostavnih ali efikasnih mreža dubine O(log2 n). Često se koriste u praksi. Teorijski je moguće konstruisati ove mreže sa logaritamskom dubinom, koristeći AKS mrežu. Iako je bitno teorijsko otkriće, ASK mreža ima malu ili nikakvu primenu zbog linearne konstante iza O notacije koja je veličine mnogo, mnogo hiljada. Postoji I pojednostavljena verzija AKS-a, koja naglašava da su konstante koje su dobijene za granicu dubine neodgovarajuće I da nemaju praktični značaj. Još jedna metoda konstrukcije sortirajuće mreže je otkrivena za O(n log n) ali iako ima manju konstantu od AKS-a, baš zbog O(n log n) složenosti ne može da efikasno ima paralelnu implementaciju.

Optimalne sortirajuće mreže

One mogu biti optimalno konstruisane za fiksirane unose odredjene n veličine, sa minimalnom dubinom ili minimalnom veličinom (brojem komparatora). One se mogu koristiti za povećanje performance većih sortirajućih mreža. Ova tabela prikazuje poznate rezultate optimizacije.

n	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
Dubina	0	1	3	3	5	5	6	6	7	7	8	8	9	9	9	9
Veličina, gornja granica	0	1	3	5	9	12	16	19	25	29	35	39	45	51	56	60
Veličina, donja granica, ako je različita	33	37	41	45	49	53

Prvih šesnaest dubinski- optimalnih mreža su navedene u Art of Computer Programming, koju je napisao Knut. Iako je optimalnost prvih osam dokazana još 60-ih godina, optimalnost poslednjih šest je pokazana tek 2014. godine (deveti I desti slučaj su dokazani 1991.) .

Za izradu optimalnih sortirajućih mreža su se čak koristili I genetski algoritmi. Knut kaže da su slučajevi za n=9 i n=11 zasnovani na toj metodi.

Reference

^ US 3029413, O'Connor, Daniel G. & Nelson, "Sorting system with $n$ -line sorting switch", published 10. 4. 1962
^ Owens, J. D.; Houston, M.; Luebke, D.; Green, S.; Stone, J. E.; Phillips, J. C. (2008). „GPU Computing”. Proceedings of the IEEE. 96 (5): 879. doi:10.1109/JPROC.2008.917757.
^ Knuth, D. E. (1997). The Art of Computer Programming, Volume 3: Sorting and Searching (Second изд.). Addison–Wesley. стр. 219—247. ISBN 978-0-201-89685-5.

[1] US 3029413, O'Connor, Daniel G. & Nelson, "Sorting system with $n$ -line sorting switch", published 10. 4. 1962

[2] Owens, J. D.; Houston, M.; Luebke, D.; Green, S.; Stone, J. E.; Phillips, J. C. (2008). „GPU Computing”. Proceedings of the IEEE. 96 (5): 879. doi:10.1109/JPROC.2008.917757.

[knuth-3] Knuth, D. E. (1997). The Art of Computer Programming, Volume 3: Sorting and Searching (Second изд.). Addison–Wesley. стр. 219—247. ISBN 978-0-201-89685-5.

[1]

[2]

[3]