34 - Distribuované a paralelní algoritmy - algoritmy řazení, select
pátek 1. dubna 2016
11:02
[link]
[link]
[link]
Analýza algoritmů
Počet procesorů 𝑝 - závisí na velikosti dat 𝑛
Čas řešení úlohy 𝑡𝑛
Cena paralelního řešení - cn=pn∗tn
Zrychlení a efektivnost
Zrychlení - tseqn𝑡(𝑛)
Efektivnost - 𝑡𝑠𝑒𝑞(𝑛)𝑐(𝑛)
<1 neoptiomální (přidá se režie)
+−1 optimální
>1 :-) 
Řazení
Optimální sekvenční algoritmus
𝑝𝑛=1, máme jen 1 procesor
𝑡𝑛=𝑂𝑛∗log𝑛, toto je rychlost quick-sortu
𝑐𝑛=𝑂𝑛∗log𝑛, čas*počet procesorů je stejný jako rychlost
Jo ještě tu je podmínka, že u řazení nejsou žádné dva prvky rovny.
Enumeration sort
Žádný paralelní algoritmus pro rozumný výpočetní model není rychlejší, bez ohledu na počet procesorů.
Kvantové počítače by to ale zvládly rychleji.
Princip algoritmu
Výsledná pozice prvku je dána počtem prvků, které jsou menší. Každý prvek se porovná se všemi ostatními prvky a pro každý prvek, který je menší si ke svému rank přičte 1.
Každý procesor může:
Uložit dva prvky do svých registrů A a B.
Porovnat obsah registrů A a B a výsledek uložit do registru RANK.
K registru RANK se mohou přičítat čísla.
Pomocí stromového propojení předat obsah kteréhokoli registru do jiného procesoru.
krok - distribuce hodnot na procesory (v řádcích i sloupcích). Složitost kroku 𝑂(𝑙𝑜𝑔 𝑛)
krok - porovnání hodnot a sčítání ve stromové struktuře. Složitost 𝑂log𝑛
Správná pozice prvku je 𝑅𝐴𝑁𝐾(𝑥𝑖) = 1 + 𝑝𝑜č𝑒𝑡 𝑚𝑒𝑛ší𝑐ℎ 𝑝𝑟𝑣𝑘ů
krok - předání hodnot na správné pozice (procesory)
Topologie
n2 procesorů v mřížce n×n.
Procesory v každém řádku jsou propojeny do binárního stromu.
To stejné platí pro řádky.
Vlastnosti
Počet procesorů - pn=On2
Časová složitost - tn=Ologn
Cena - cn=O(n2∗log⁡(n)), není to ideální cena
Odd-even transposition sort (paralelní Bubble sort)
Nejrychlejší algoritmus pro seřazení již seřazené posloupnosti. 
Princip algoritmu
Paralelní bubble-sort, porovnávají se jen sousedé a mohou se přehodit.
V prvním kroku se každý lichý procesor 𝑝𝑖 spojí se svým sousedem 𝑝𝑖+1  a porovnají své hodnoty je-li y i >y i+1, pak vymění své hodnoty.
V druhém kroku se každý sudý procesor ...totéž...
Po 𝒏 krocích (maximálně) jsou hodnoty seřazeny.
Topologie
Lineární pole 𝑛 procesorů.
Vlastnosti
Počet procesorů - pn=On
Časová složitost - tn=On
Cena - cn=O(n2), není to ideální cena
Odd-even merge sort
Princip algoritmu
Řadí se speciální sítí procesorů (každý procesor má dva vstupní a dva výstupní kanály).
Každý procesor umí porovnat hodnoty na svých vstupech, menší dá na výstup L(low), a větší dá výstup H (high).
Topologie
Sítě procesorů 1×1, 2×2, 4×4, 8×8, ... (procesory propojeny tak, aby složením jednotlivých porovnání byla seřazená posloupnost)
Seřazené posloupnosti {a1, a2}, {b1, b2} jsou spojeny do seřazené posloupnosti {c1, c2, c3, c4}
Vlastnosti
Počet procesorů - pn=On∗log2𝑛
Časová složitost - tn=Olog2𝑛
Cena - cn=On∗log4𝑛, není to ideální cena
Merge-splitting sort
Princip algoritmu
Varianta odd-even sortu, každý procesor řadí krátkou posloupnost.
Místo porovnání sousedů se provede spojení posloupností (𝑂(𝑛)) a pak rozdělení na půl.
Každý procesor obsahuje 𝑛/𝑝 čísel.
Po p/2 iteracích je posloupnost seřazena.
Topologie
Lineární pole procesorů 𝑝(𝑛) < 𝑛
Vlastnosti
Počet procesorů - pn<n
Časová složitost - tn=O𝑛∗log𝑛/𝑝+On
Cena - 𝑐(𝑛)=𝑂(𝑛∗𝑙𝑜𝑔(𝑛)) + 𝑂(𝑛∗𝑝), je optimální pro p≤log𝑛
Pipeline Merge sort
Princip algoritmu
[link]
Rozděleno na několik kroků, první spojuje posloupnosti délky 1, pak 2, 4, 8 atd.
Data nejsou uložena v procesorech, ale postupně do nich vstupují.
Každý procesor spojuje dvě seřazené posloupnosti délky 2𝑖−2
S0 reads the input stream, creates "sorted" sub-sequences of size one and sendsthese intermidently to one of its two output streams. Si repeatedly reads two sorted sub-sequences, one from each input stream, merges them, and writes the double sized sorted sub-sequences intermidently two one of its output streams. Sm reads two sorted sub-sequences, one from each input stream, merges these and produces the resultng output sequence. 
Topologie
Lineární pole procesorů.
Vlastnosti
Počet procesorů - pn=log(𝑛)+1
Časová složitost - tn=On
Cena - 𝑐(𝑛)=𝑂(𝑛∗𝑙𝑜𝑔(𝑛)), je optimální
Enumeration sort
Princip algoritmu
Legenda:
Xi - prvek xi
Yi - postupně prvky x1…xn
Ci - počet prvků menších než xi (tj. kolikát bylo Yi≤Xi)
Zi - seřazený prvek Yi
Všechny registry C se nastaví na hodnotu 1.
Následující činnosti se opakují 2n krát 1≤k≤2n
Pokud vstup není vyčerpán, vstupní prvek 𝒙𝒊 se vloží do 𝑿𝒊 (sběrnicí) a do 𝒀𝟏 (lineárním spojením) a obsah všech registrů 𝑌 se posune doprava.
Každý procesor s neprázdnými registry 𝑋 a 𝑌 je porovná, a je-li 𝑿 > 𝒀 inkrementuje 𝑪.
Je-li 𝑘 > 𝑛 (t.j. po vyčerpání vstupu) procesor 𝑷𝒌−𝒏 pošle sběrnicí obsah svého registru 𝑿 procesoru P𝐶𝑘−𝑛, který jej uloží do svého registru 𝑍.
V následujících 𝑛 cyklech procesory posouvají obsah svých registrů 𝑍 doprava a procesor Pn produkuje seřazenou posloupnost.
Topologie
Lineární pole procesorů a sběrnice, která muže přenést jednu hodnotu v každém kroku
Vlastnosti
Počet procesorů - pn=n
Časová složitost - tn=On
Cena - 𝑐(𝑛)=𝑂(𝑛2), není optimální
Minimum Extraction sort
Princip algoritmu
Stromem se odebírá vždy nejmenší prvek.
Každý listový procesor obsahuje jeden řazený prvek.
Každý nelistový procesor umí porovnat dva prvky.
Topologie
Strom
Vlastnosti
Počet procesorů - pn=2n−1
Časová složitost - tn=On
První prvek to sice zmákne v logaritmickém čase, ale potom musíme po jednom dobrat ten zbytek n−1
Cena - 𝑐(𝑛)=𝑂(𝑛2), není optimální
Bucket sort
Princip algoritmu
Stromem spojené procesory, které řadí menší posloupnosti a pak spojení.
Každý listový procesor obsahuje 𝒏/𝒎 řazených prvků a umí je seřadit optimálním sekvenčním algoritmem (např. heapsort).
Každý nelistový procesor umí spojit dvě seřazené posloupnosti optimálním sekvenčním algoritmem.
Topologie
Strom
Vlastnosti
Počet procesorů - pn=2∗log𝑛−1
Časová složitost - tn=On
Cena - 𝑐(𝑛)=𝑂(𝑛∗log𝑛), optimální
Využití
[link]
Bucket sort se dá využít pro řazení obrovských dat, která by nemohl načíst klasický 𝑶(𝒏∗𝐥𝐨𝐠𝒏) algoritmus najednou. Algoritmus rozdělí vstupní data do dostatečně malých přihrádek a tyto postupně řadí v paměti, zatímco neaktivní přihrádky nechává uložené ve vnější paměti (např. pevný disk). Dalším scénářem využití bucket sortu je distribuované řazení, při kterém je každá přihrádka řazena v jiném vlákně, připadně dokonce na jiném stroji.
Median Finding and Splitting (paralel Quick sort)
Princip algoritmu
Dělí posloupnost mediánem až na dvojice, které porovná.
Každý list umí optimální sekvenční sort.
Každý nelistový procesor umí nalézt medián v optimálním čase (např. algoritmus Select s 𝑂(𝑛) složitostí).
Ekvivalent Quick Sortu - liší se tím, že se jednotlivé stupně provádí paralelně.
Topologie
Strom
Vlastnosti
Počet procesorů - pn=log𝑛
Časová složitost - tn=On
To platí ale pouze pro paralelní nalezeni medianu. 
Therefore, if the partitioning step is performed in time Q(1), using Q(n) processes, it is possible to obtain an overall parallel run time of Q(log n), which leads to a cost-optimal formulation. However, without parallelizing the partitioning step, the best we can do (while maintaining cost-optimality) is to use only Q(log n) processes to sort n elements in time Q(n) (Problem 9.14). Hence, parallelizing the partitioning step has the potential to yield a significantly faster parallel formulation.
Cena - 𝑐(𝑛)=𝑂(𝑛∗log𝑛), optimální
Má problémy, pokud jsou tam některé řazené prvky stejné.
Fundamental problem with all tree constructions – initial division done by a single processor, which will seriously limit speed.
Select (median)
Sequential select
Princip algoritmu
Hledá k-tý nejmenší prvek v posloupnosti S.
Je-li k=|S|/2, jde o medián.
Rozdělíme vstupní posloupnost na několik pod posloupností, ty seřadíme, najdeme v každé medián a ten vrátíme.
Dostaneme posloupnost mediánu, tu seřadíme a najdeme v ní medián.
Původní vstupní posloupnost rozdělíme na tři části podle nalezeného "mediánu mediánů" (L - mensi, E - rovno, G - vetší)
(k je délka vstupní posloupnosti dělena 2)
Pokud |L| > k - medián musí být v L - Zavolej algoritmus znovu tentokrát pro posloupnost L
Pokud |L| + |E| > k - medián musí být v E - Vrať nalezený medián
Jinak - medián musí být v G - Zavolej algoritmus znovu tentokrát pro posloupnost G
Vlastnosti
Časová složitost - tn=On
Parallel select
Princip algoritmu
k-tý nejmenší prvek v posloupnosti S; EREW PRAM s N procesory P1..Pn; používá sdílené pole M o N prvcích.
Vlastnosti
Počet procesorů - pn=N
Časová složitost - tn=On/N pro 𝑛>4 && 𝑁<𝑛/log𝑛 
Cena - c(n)=O(n), optimální
Problém, který degraduje složitost algoritmus je, že při zpracování posloupností L, E, G nevíme, kam uložit číslo do paměti, dokud tam neuložíme všechny předchozí. Toto řeší následující algoritmus Parallel splitting.
Parallel splitting
Parallel splitting je krok 4 algoritmu Parallel select.
Princip algoritmu
Je dána posloupnost S a číslo m; Mají se vytvořit tři posloupnosti:
L = {si ε S: si < m}
E = {si ε S: si = m}
G = {si ε S: si > m}
Po tom co se vytvoří se vypočítá, kam mají procesory ukládat své výsledné posloupnosti (suma prefixů), aby mohly ukládat současně a nemuseli čekat, než budou uloženy všechny předchozí hodnoty.
Vlastnosti
Složitost sekvenčního algoritmu je O(n)
Paralelní řešení - máme N procesorů, které si sekvenci S rozdělí na podposloupnosti Si o délce n/N
Počet procesorů - pn=2∗log𝑛−1
Časová složitost - tn=On/N, pro dostatečně malé N.
Cena - 𝑐(𝑛)=𝑂(𝑛), optimální
Notes*
2. Otazka (okruh): Distributivni a pralelni algoritmy - razeni
Kdo me primarne zkousel: Hanáček
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli:
Zacal sem ze mam mnozinu s prvkama X a pak chci dostat Y, kde je to serazeny a zacal sem mluvit o Enumeration sortu a on me prerusil, ze chce nejakej sekvencni algoritmus, jeho slozitost a jak funguje, tam sem vedel jen slozitost a pak sem se snazil vysvetlit quicksort (bubble nechtel), ale nejak sem se zamotal i u te slozitosti. Nakonec se zeptal jak je ten Quick delanej paralelne tusil sem ze je to Merge Splitting sort, ale moc sem ho neovladal. Skoda ze nechtel ty co jsem se ucil.
From <[link]> 
Kdo me primarne zkousel: Orság
Měl jsem se zaměřit na Enumeration sort. Nejdříve jsem popisoval obecné vlastnosti paralelních algoritmů. Do toho jsem se ale zamotal a Orság se začal ptát na doplňující otázky. Bohužel jsem často nechápal co po mně chce slyšet. Poté jsem stručně popsal Enumeration sort. 
From <[link]> 