47 - Distribuované a paralelní algoritmy - algoritmy nad seznamy, stromy a grafy Flashcards
Algoritmy nad seznamy
Algoritmy pracují s vázaným seznamem.
- Každý prvek má hodnotu v_i a ukazatel na následníka Succ[i]
Můžou být asi i různě provázané? ((každý prvek má následníka nebo předchůdce i následníka). Každý prvek tak má hodnotu a případné ukazatele)
Seznamy -
Predecessor computing
Výpočet předchůdce v seznamu. Má konstantní čas.
for i = 1 to n do in parallel:
Pred[Succ[i]] = i
aneb jsem předchůdce mého následníka!
Vlastnosti
• t(n)=O(c)
• p(n)=n
• c(n)=O(n)
Seznamy - List ranking a parallel suffix sum
LIST RANKING (sekvenčně; v paralelním prostředí - path doubling)
princip – nalezení pořadí (rank) prvků seznamu (vzdálenost od konce seznamu);
• topologie – lineární pole n procesorů;
• algoritmus – používá se technika postupného zdvojování cesty;
hodnota poslední prvku nastavena na 0 (smyčka)
Princip algoritmu
1. V prvním kroku se dá všem (kromě posledního prvku) rank=1. 2. Poté se v logn krocích udělá, že rank každého prvku je vlastní rank+rank následníka - A také se změní pole následníků. Jelikož se sčítají ranky, tak současný následník je změněn na následník následníka.
Vlastnosti
• t(n)=O(logn )
• p(n)=n
• c(n)=O(n∗logn), což NENÍ optimální
PARALLEL SUFFIX SUM - to samé jako LIST RANKING avšak vzdálenost je ohodnocená, né 1
Vypočítává součet suffixů (podobně jako suma prefixů) seznamu.
• Suffix – podseznam mezi prvkem a koncem seznamu
• Vstupy -
○ Pole hodnot V
○ Binární asociativní operátor ⊕
Na konci musíme upravit hodnotu posledního prvku na neutrální prvek k operaci ⊕
Vlastnosti
• t(n)=O(logn )
• p(n)=n
• c(n)=O(n∗logn)
Seznamy - Vylepšení list ranking a suffix sum - Random Mating a Optimal List Ranking - OPTIMÁLNÍ
Random mating -> Optimalizovaný algoritmus list ranking.
Princip algoritmu
• Každý procesor si hodí korunou a přiřadí si pohlaví (male/female).
○ Hází se v každé iteraci.
Pokud je procesor female a jeho následník je male, pak se prvek přeskočí (jump over) a procesor se uvolní.
Optimal list ranking
- Je to simulace Random Mating a řeší to, že u RM se část procesorů fláká, což způsobuje neefektivitu.
Princip algoritmu
• Požadavek: pevný počet stále pracujících procesorů
• Simulace algoritmu Random Mate pomocí n/logn procesorů, každý procesor vykonává práci logn procesorů
○ Každý procesor má zásobník prvků o velikosti logn právě proto, aby mohl vykonávat simulaci Rand. mating
• Každý procesor se pokouší přeskočit (jump over) následníka prvku na vrcholu zásobníku
• Pokud je vrchol zásobníku přeskočen, procesor se zabývá dalším prvkem na zásobníku
Vlastnosti
• t(n)=O(logn )
• p(n)=n/logn
• c(n)=O(n), je optimální
Algoritmy nad stromy, binární strom a eulerova cesta
Binární strom je abstraktní datová struktura, kde mezi sebou existují vazby
- otce (index i)
- levého syna (2i)
- pravého (2i+1) syna
Speciálním případem průchodu binárním stromem je preorder (root, left, right), inorder (left, root, right) a postorder (left, right, root)
Eulerovský tah = průchod stromem ve kterém se každá hrana projde právě jednou (jednou tam a jednou zpátky)
Eulerovský graf
- Strom (tree) je obecně orientovaný graf, který tvoří uspořádaná dvojice uzlů (vertices) a hran (edges) 𝑇 = 𝑉, 𝐸 .
- Eulerovský graf je takový, který vznikne z normálního nahrazením neorientovaných hran vždy dvojící hran orientovaných.
Eulerova cesta
- Eulerova cesta je obecný případ průchodu stromem, kdy jím procestuje eulerovskou kružnicí.
- Kořen stromu je uzel stromu, ze kterého se rozhodneme eulerovskou kružnicí procházet - místo, kde přerušujeme eulerovskou cestu.
Seznam sousednosti (adjacency list)
- slouží k reprezentaci stromu v podobě grafu pro eulerovský cyklus
- pro každý uzel je přiřazen lineárně vázaný seznam, každý prvek seznamu je dvojice hrana/opačná hrana (e, eR, NÁSLEDNÍK)
v1: (e1,e3,nil) => Etour(e3)=e1
v2: (e2,e4,nil) => Etour(e4)=e2
v3: (e3,e1, -)->(e4,e2, -)->(e5,e6,nil) => Etour(e1)=e4, Etour(e2)=e5, Etour(e6)=e3
v4: (e6,e5,nil) => Etour(e5)=e6
- Algoritmus pro každou hranu e najde položku (,e,) v seznamu sousednosti. Pokud má tato položka následníka (en,,), jeho dopředná hrana en bude následnickou hranou v eulerově cyklu (Etour(e)=en)
Kořen stromu = vznikne tak, že se v jednom bodě (kořeni) Eulerovský cyklus přeruší.
Pozice hran
- vezmeme graf v podobě seznamu souslednosti
-> převedeme na Eulerovský cyklus
-> provedeme List ranking na cyklus (rank = opačné pořadí hran v cyklu)
-> Pořadí získáme paralelním vypočtením 2n-2-rank (n je počet vrcholů)
t(n) = O(log n) (nejhorší závislost má suma suffixů, ostatní jsou konstantní)
Eulerův cyklus prochází každou (neorientovanou) hranou stromu dvakrát - poprvé při zanořování po hraně do podstromu a podruhé při návratu z tohoto podstromu. Porovnáním indexů orientovaných hran v eulerově cyklu tak jde zjistit která z hran (odpovídajících jediné hraně stromu) je dopředná (směřuje dolů - má nižší index) a která zpětná (směřuje nahoru - má vyšší index).
Dopředná hrana (od rodiče k potomkovi - má nižší index než jí opačná) - position(e) < position (eR)
Zpětná hrana (od potomka k rodiči - má vyšší index než jí opačná) - position(e) > position (eR)
Počet následníků vrcholu - Počet dopředných hran v segmentu Eulerovského tahu, počínajícím i končícím ve vrcholu
Úroveň vrcholu - rozdíl dopředných a zpětných hran na cestě z kořene k vrcholu
Seznamy - List coloring a ruling set
List coloring = je obarvení seznamu tak, aby sousedé neměli stejnou barvu. k-obarvení může použít k různých barev.
2log(n) coloring
- využívá index procesoru k určení barvy.
- Hodnota k je index nejnižšího bitu indexu, ve kterém se sousedé liší, barva je pak C = 2k + ID[k]
Ruling set
k-ruling set = množina nesousedících vrcholů, mezera mezi nimiž je široká maximálně k
2k-ruling set z k-coloring = vybere prvek do ruling set tehdy, když jeho barva je nižší než barva předchůdce a následníka (hledáme lokální minima)
Tree Contraction
!!! Některé operace nad stromem se nedají provést efektivně pouze pomocí Eulerovy cesty !!!
Každý list obsahuje operand a nelistový operátor
Tree contraction strom se postupně zmenšuje až do jediného uzlu, tedy výsledku
(obecně: • Technika tree contraction je systematický způsob jak (pomocí operací RAKE a COMPRESS) zmenšovat strom až do velikosti jednoho vrcholu.
!!! Například paralelní vyhodnocení aritmetického výrazu uloženého v binárním stromu.)
Algoritmus tree contraction
- opakovaně aplikujeme RAKE a tím zmenšujeme strom
- snažíme se aplikovat pro co nejvíce listů paralelně
- nelze aplikovat operaci RAKE na vrcholy jež ve stromu sousedí (mají spol rodiče)
- Jak určit uzly na které lze aplikovat?
jinak:
- Při Tree contraction se řeší paralelní vyhodnocení aritmetického výrazu uloženého ve formě stromu, kde každý list obsahuje operand a každý uzel operátor
- Tato technika opakovaně zmenšuje strom, až do velikosti jednoho vrcholu, a to tím, že spojuje listy do rodičovského uzlu.
- Používá se právě operace RAKE v co největší míře (musí se ohlídat, aby nebyla RAKE aplikována současně na vrcholy, jejichž rodiče ve stromě sousedí).
RAKE OPERACE
- Operace redukuje počet listů v BINÁRNÍM stromě v jednom kroku na polovinu (Rake step joins every left leaf (L) of binary (B) nodes to the parent (U is unary node))
1. Odstraní u a parent(u) ze stromu T.
2. Připojí soused(u) k parent(parent(u))
1) Označíme listy zleva doprava;
2) Krajní se vyřadí (zůstanou jako poslední, až bude strom redukován na 2 listy a kořen);
3) Nejprve se volá RAKE na liché a pak na sudé listy takto upraveného seznamu vrcholů;
4) Redukce stromu za t(n) = O(log n).
Algoritmus Tree search
Poslání hodnoty do všech uzlů, pokud nalezeno vrací 1, jinak 0
Vyhledávání v neseřazené posloupnosti
Stromová architektura s 2n-1 procesory
Algoritmus
1. Kořen načte hledanou hodnotu x a předá ji synům … až se dostane ke všem listům
2. Listy obsahují seznam prvků, ve kterých se vyhledává (každý list jeden). Všechny listy paralelně porovnávají x a xi, výsledek je 0 nebo 1.
3. Hodnoty všech listů se předají kořenu - každý ne list spočte logické or svých synů a výsledek zašle otci.
Kořen dostane 0 - nenalezeno, 1- nalezeno
Analýza
Krok (1) má složitost O(log n), krok (2) má konstantní složitost, krok (3) má O(log n).
t(n) = O(log n)
p(n) = 2.n-1
c(n) = t(n).p(n) = O(n.log n) → což není optimální
