37 - Distribuované a paralelní algoritmy - algoritmy nad seznamy, stromy a grafy
pátek 1. dubna 2016
10:56
[link]
[link]
Práce se seznamy
Algoritmy pracují s vázaným seznamem.
Každý prvek má hodnotu 𝑣𝑖 a ukazatel na následníka 𝑆𝑢𝑐𝑐[𝑖].
Úloha: Predecessor computing
Výpočet předchůdce v seznamu. Má konstantní čas.
Princip algoritmu
Vlastnosti
tn=Oc
pn=n
cn=O(n)
Úloha: List ranking
Nalezni pořadí (rank) prvků seznamu (vzdálenost od konce seznamu).
Sekvenční algoritmus má složitost 𝑂(𝑛).
[link]
Nicméně na Wiki píšou, že se nepočítá vzdálenost od konce seznamu, ale od začátku.
Použitá technika je zdvojování cesty (path doubling).
Princip algoritmu
V prvním kroku se dá všem (kromě posledního prvku) 𝒓𝒂𝒏𝒌=𝟏.
Poté se v 𝐥𝐨𝐠𝒏 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
tn=Olog𝑛
pn=n
cn=O(n∗log𝑛), což není optimální
Úloha: Parallel suffix sum
Vypočítává součet suffixů (podobně jako suma prefixů) seznamu.
Suffix – podseznam mezi prvkem a koncem seznamu
Vstupy - 
Pole hodnot 𝑉
Binární asociativní operátor ⊕
Princip algoritmu
Na konci musíme upravit hodnotu posledního prvku.
Poslední prvek - pokud některý z procesorů už doskákal na konec, tak už nic nemusí číst, ostatní procesory ale ještě hodnotu požadují ⇒ hodnota posledního prvku by se přičítala několikrát ⇒ inicializujeme na 0 (neutrální prvek) a ten se přičítá.
Vlastnosti
tn=Olog𝑛
pn=n
Random mating
[link]
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í.
Vlastnosti
tn=Olog𝑛
pn=n
cn=O(n∗log𝑛), není optimální
množství práce− cn=n+34n+342𝑛+…=𝑂(𝑛), což je optimální… 
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í 𝒏/𝐥𝐨𝐠𝒏 procesorů, každý procesor vykonává práci log𝑛 procesorů
Každý procesor má zásobník prvků o velikosti 𝐥𝐨𝐠𝒏 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
Může se stát, že zásobníky procesorů budou nevyvážené, protože procesory nedeaktivují svoje prvky, ale deaktivují prvky jiných procesorů.
Řešení: 
operace jump over (přeskočení) se nahradí operací splice out (vypletení). 
Místo zneaktivnění následníka procesor zneaktivní svůj (aktuální) prvek. Předchůdce deaktivovaného procesoru se propojí s následníkem.
Prvek je vypleten pokud je M a předchůdce je F
Vlastnosti
tn=Olog𝑛
pn=n/log𝑛
cn=On, je optimální
Práce se stromy
Euler tour traversal
[link]
Obecný průchod binárním stromem
Její speciální případy jsou průchody preorder, postorder a inorder.
Euler tour
T=(V,E), kde V=verticies, E=edges je daný strom
T′ je také Eulerovský graf, tedy můžeme jím celým projít tak, že bude každá hrana použita právě jednou.
Listová reprezentace Eulerovy cesty může být spočítaná v čase 𝐎(𝟏) a hloubka v čase 𝐎(𝐥𝐨𝐠𝒏)
[link]
Princip algoritmu
Příklad Eulera
Paralelním algoritmem vytvořte Eulerovu cestu pro graf: 
T = (V,E), V = {V1,V2,V3,V4,V5}
E={e1,e2,e3,e4,e5,e6,e7,e8}, e1=(v1,v2), e2=(v2,v1), e3=(v3,v1), e4=(v1,v3), e5=(v3,v4), e6=(v4,v3), e7=(v3,v5), e8=(v5,v3). 
Postupujte tak, ze nejprve vytvorite seznam sousednosti, a s jeho pomoci zkonstruujete pole E-tour. 
Super, tak jsme spočítali Eulerův průchod stromem v čase 𝐎(𝐜)… a k čemu nám to to je?
No prakticky jsme tak vytvořili Linked List (tedy první tu cyklickou cestu musíme v kořeni přeseknout) a nad tím dokážeme počítat například sumu prefixů atd.
Vlastnosti
tn=Olog𝑛
pn=n/log𝑛
cn=On
Je to stejné jako Optimal List Ranking. 
Obecný výpočet ve stromu
Pro mnoho algoritmů nad stromem T je postup:
Vytvoříme Eulerovu cestu - O(c)
Vytvoříme pole hodnot - 𝑂(𝑐)
Spočteme nad ním sumu suffixů - 𝑂(log𝑛)
Provedeme korekci - Oc
Tedy 𝑡(𝑛) = 𝑂(log𝑛)
Můžeme tak např. spočíst:
Pořadí postorder vrcholu
Pořadí preorder vrcholu
Pořadí inorder vrcholu
Počet následníků vrcholu
Úroveň vrcholu
Tree Contraction
[link]
Některé operace nad stromem se nedají provést efektivně pouze pomocí Eulerovy cesty.
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.
Každý list obsahuje operand a každý nelist obsahuje operátor, jako je například +, *.
Cílem je spočíst hodnotu výrazu v kořeni.
Opakovaně aplikujeme (dokud nemáme jen jeden node):
Spojení listu s jeho rodičem && Spojení vrcholu stupně 2 s jeho rodičem
Toť jest na slidech… v reálu se aplikují operace RAKE a COMPRESS.
Tree Contraction jsme schopni udělat v čase 𝐎(𝐥𝐨𝐠𝒏), jelikož operace RAKE nám v každém kroku zlikviduje polovinu uzlů ve stromě.
RAKE operation
Operace redukuje počet listů ve stromě v jednom kroku na polovinu.
𝑻 = (𝑽, 𝑬) je binární strom a pro každý vrchol 𝑣 je 𝑝(𝑣) jeho rodič.
𝑠𝑖𝑏(𝑣) je synem 𝑝(𝑣).
Bereme v úvahu pouze binární stromy.
Operace RAKE pro listový vrchol 𝑢 takový, že pokud 𝑝𝑢≠𝑟 provede následující:
Odstraní 𝑢 a 𝑝(𝑢) ze stromu 𝑇.
Připojí podstrom 𝑠𝑖𝑏(𝑢) to 𝑝(𝑝(𝑢)).
RAKE trochu rozepsaný
Rake step joins every left leaf (L) of binary (B) nodes to the parent (U is unary node). By join, we mean that it undergoes a functional process which achieves the operation we want to make. This will be discussed formally later. Here is an example of the rake step.
COMPRESS operation
Compress step is actually a sequence of several events.
Find an independent set of unary nodes. (Independence here is defined such that no two are neighbors meaning no parent to child relation)
Join each node in independent set with its child (Note that independent set is not unique)
Here is an example of compress step continuing from the above rake step:
Práce s grafy
List coloring, Ruling set …. Nevím co k tomu napsat.
Notes*
2. Otazka (předmět) (okruh): PRL 46 - Distribuované algoritmy nad stromy a grafy
Kdo me primarne zkousel: Zbořil ml.
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli: 
Po předchozím výstupu jsem byl dost vyklepaný a nevěděl jsem o čem začít. Zbořil se tedy ujal slova a řekl, že chce slyšet algoritmus pro nalezeni eulerovy cesty. Naštěstí mi to naskočilo a na příkladu jsem to vysvětlil. "Nó, tak to tedy umíte", pochvaloval si. Pak se zeptal jakým způsobem bychom mohli použít na stromy algoritmy pro seznamy, například sumu suffixů. Tak sem řekl že musíme vybrat kořen, pak nám to eulerova cesta linearizuje, dostaneme lineární seznam a nad ním pak můžeme provádět paralel alg nad seznamy, např tu sumu suffixů. Spokojeně řekl, že mu to stačí a šel jsem ven. Za A.
Celkova znamka ze statni zaverecne zkousky: otázky D a A, diplomka B, celkem B
From <[link]> 