44 - Distribuované a paralelní algoritmy - algoritmy řazení, select Flashcards
Analýza algoritmů (cena, efektivnost, ..)
Počet procesorů p - závisí na velikosti dat n
- p(n) = 1 - sekvenční, c - konstantní, log n, n, n log n -> v pohodě,
- n^2, n^r, n^n -> už není v pohodě
• Čas řešení úlohy t(n) • Cena paralelního řešení - c(n)=p(n)∗t(n) • Zrychlení a efektivnost ○ Zrychlení - (t_seq (n))/(t(n)) - čas ○ Efektivnost - (t_seq (n))/(c(n)) - čas vs cena § <1 neoptiomální (přidá se režie) § +−1 optimální § >1 :-)
Řazení
Optimální sekvenční algoritmus
• p(n)=1, máme jen 1 procesor
• t(n)=O(n∗logn ), toto je rychlost quick-sortu
• c(n)=O(n∗logn ), čas*počet procesorů je stejný jako rychlost
! ještě tu je podmínka, že u řazení nejsou žádné dva prvky rovny.
Řazení - Enumeration sort - mřížka
mřížka nxn, n^2 procesorů, data pošleme všude, všude porovnáme zdali je větší či menší, poté seřadíme podle počtu menších prvků
Ideální algoritmus pro paralelní zpracování (ale drahý) - Žádný paralelní algoritmus pro rozumný výpočetní model není rychlejší, bez ohledu na počet procesorů (kvantový počítač by byl rychlejší)
• Výsledná pozice prvku je dána počtem prvků, které jsou menší.
• 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.
Výpočet - data pošleme všude, všude porovnáme zdali je větší či menší, poté seřadíme podle počtu menších prvků:
- krok - distribuce hodnot na procesory (v řádcích i sloupcích). Složitost kroku O(log n)
- krok - porovnání hodnot a sčítání ve stromové struktuře. Složitost O(logn ) - Správná pozice prvku je RANK(xi) = 1 + počet menších prvků
- krok - předání hodnot na správné pozice (procesory)
Topologie
• n^2 procesorů v mřížce n×n.
• Procesory jsou v každém sloupci a řádku propojeny do binárního stromu
Vlastnosti
• Počet procesorů - p(n)=O(n^2 )
• Časová složitost - t(n)=O(log(n) )
• Cena - c(n)=O(n^2∗log(n)), není to ideální cena
Řazení - Odd-even transposition sort (paralelní Bubble sort) - lineární
Nejrychlejší algoritmus pro seřazení již seřazené posloupnosti !
Výpočet: Paralelní bubble-sort, porovnávají se jen sousedé a mohou se přehodit.
1. V prvním kroku se každý lichý procesor p_i spojí se svým sousedem p_(i+1) a porovnají své hodnoty je-li y i >y i+1, pak vymění své hodnoty. 2. V druhém kroku se každý sudý procesor ...totéž... 3. Po n krocích (maximálně) jsou hodnoty seřazeny.
Topologie
• Lineární pole n procesorů.
Vlastnosti
• Počet procesorů - p(n)=O(n)
• Časová složitost - t(n)=O(n)
• Cena - c(n)=O(n^2), není to ideální cena
Řazení - Odd-even merge sort - síť topologie
Řadí dvě seřazené posloupnosti do jedné seřazené!!!
- Ř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ů - p(n)=O(n∗log^2n )
• Časová složitost - t(n)=O(log^2n )
• Cena - c(n)=O(n∗log^4n ), není to ideální cena
Řazení - Merge-splitting sort - lineární pole - OPTIMÁLNÍ - pro správný počet procesorů
Každý procesor seřadí svou posloupnost, potom seřadí dvě, a to se opakuje, postupně lichý a sudý
- Varianta odd-even transposition sortu, každý procesor řadí krátkou posloupnost.
- Místo porovnání sousedů se provede spojení posloupností (O(n)) a pak rozdělení na půl.
- Každý procesor obsahuje n/p čísel. - Po p/2 iteracích je posloupnost seřazena.
Topologie
• Lineární pole procesorů p(n) < n
Vlastnosti
• Počet procesorů - p(n) < n
• Časová složitost - t(n)=O(n∗logn/p)+O(n)
• Cena - c(n)=O(n∗log(n)) + O(n∗p), je optimální pro p≤logn
Řazení - Pipeline Merge sort - lineární pole procesorů - OPTIMÁLNÍ
- 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^(i−2)
Topologie
• Lineární pole procesorů.
Vlastnosti
• Počet procesorů - p(n)=log〖(n〗)+1
• Časová složitost - t(n)=O(n)
• Cena - c(n)=O(n∗log(n)), je optimální
Řazení - Enumeration sort - lineární pole + sběrnice
Legenda ○ C_i - počet prvků menších než x_i (tj. kolikát bylo Y_i≤X_i) ○ X_i - prvek x_i ○ Y_i - postupně prvky x_1…x_n ○ Z_i - seřazený prvek Y_i
- Všechny registry C se nastaví na hodnotu 1.
- Pokud vstup není vyčerpán, vstupní prvek x_i se vloží do X_i (sběrnicí) a do Y_1 (lineárním spojením) a obsah všech registrů Y se posune doprava.
- Každý procesor s neprázdnými registry X a Y je porovná, a je-li X > Y inkrementuje C.
- potom to vybublá
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ů - p(n)=n
• Časová složitost - t(n)=O(n)
• Cena - c(n)=O(n^2), není optimální
Řazení - Minimum Extraction sort - strom
Stromem vždycky probublá ten nejmenší z listů nahoru do kořene
• 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ů - p(n)=2n−1 • Časová složitost - t(n)=O(n) ○ První prvek to sice zmákne v logaritmickém čase, ale potom musíme po jednom dobrat ten zbytek n−1 • Cena - c(n)=O(n^2), není optimální
Řazení - Bucket sort - strom - OPTIMÁLNÍ
data v listech, spojujeme do kořene
• Stromem spojené procesory, které řadí menší posloupnosti a pak spojení.
○ Každý listový procesor obsahuje n/m ř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ů - p(n)=〖2∗log〗〖(n)−1〗 • Časová složitost - t(n)=O(n) • Cena - c(n)=O(n∗logn), optimální
Bucket sort se dá využít pro řazení obrovských dat, která by nemohl načíst klasický O(n∗logn) 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.
Řazení - Median Finding and Splitting (paralel Quick sort) - strom - OPTIMÁLNÍ
Máme posloupnost v kořeni, postupně dělíme podle mediánu na poloviční posloupnosti, než máme v listech seřazenou posloupnost
• 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 O(n) složitostí).
• Ekvivalent Quick Sortu - liší se tím, že se jednotlivé stupně provádí paralelně.
-> QUICK SORT: vybereme medián, poté určíme pro všechny zdali je větší či menší než medián, proházíme, a to samé poté na poloviny
- - - Zvolme v zadaném poli libovolný prvek a říkejme mu pivot.
- - - Nyní můžeme pole přeházet tak, aby na jedné straně byly prvky větší než pivot, na druhé menší než pivot a pivot samotný byl umístěn přesně mezi těmito částmi.
- - - Tento postup můžeme zopakovat pro obě rozdělené části (bez pivota, ten je již umístěn na správném místě).
- - - Proceduru opakujeme tak dlouho, dokud nenarazíme na všechny triviálně řešitelné podproblémy (pole velikosti 1).
- - - V tento okamžik je celé pole seřazeno od nejvyššího prvku.
- Má problémy, pokud jsou tam některé řazené prvky stejné
Topologie • Strom Vlastnosti • Počet procesorů - p(n)=log(n) • Časová složitost - t(n)=O(n) ○ To platí ale pouze pro paralelní nalezeni medianu. • Cena - c(n)=O(n∗logn), optimální
Select - sequential select (median)
Hledáme medián - rozzdělíme na posloupnosti, v každé najdeme medián, poté najdeme medián mediánů a rozdělíme vstupní posloupnost podle tohoto mediánu
- poté hledáme dále pro menší či větší posloupnost, podle délky posloupností
• 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 - t(n)=O(n)
Select - Parallel select - OPTIMÁLNÍ
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ů - p(n)=N
• Časová složitost - t(n)=O(n/N) pro n > 4 && N < n/logn
• Cena - c(n)=O(n), optimální
Select - Parallel splitting - OPTIMÁLNÍ
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ů - p(n)=〖2∗log〗〖(n)−1〗
• Časová složitost - t(n)=O(n/N), pro dostatečně malé N.
• Cena - c(n)=O(n), optimální
