Základy

Sekvenční

T(n) - doba běhu algoritmu pro vstup velikosti n
SL(n) - sequential lower bound - dolní mez doby běhu sekvenčního algoritmu
SU(n) - sequential upper bound - horní mez; worst case nejlepšího známého algoritmu

Paralelní

T(n,p) - doba běhu algoritmu pro vstup velikosti n na p procesorech
S(n,p)=SU(n)/T(n,p) - zrychlení oproti sekvenčnímu řešení; lineární zrychlení je, pokud S(n,p)=\Theta(p)
L(n,p)=SL(n)/p - lower bound
C(n,p)=p T(n,p) - cena; algo je cenově optimální, pokud C(n,p)=O(SU(n))
W(n,p) - paralelní práce je u synchroních algoritmů součet počtu taktů přes všechny procesory, a u asynchroních algoritmů součet času práce vláken; algo je pracovně optimální, pokud W(n,p)=O(SU(n))
E(n,p)=SU(n)/C(n,p) - paralelní efektivita / zrychlení na procesor

Algoritmus je cenově optimální <=> má lineární zrychlení <=> má konstantní efektivitu

Isoefektivní funkce

Cenová škálovatelnost … tj. chceme aby algoritmus byl efektivní. Mějme p jader, jaký je minimální velikost vstupu, aby byl výpočet efektivní? A naopak, mějme vstup velikosti n, jaký je nejvyšší počet jader p, aby byl výpočet efektivní?

$\psi_1$(p)=n - minimální velikost vstupu, aby byl výpočet efektivní
$\psi_2$(n)=p - maximální počet jader, aby byl výpočet efektivní

Pak je

$\psi_3$(n)=p - minimální počet jader takový, aby byl čas výpočtu byl minimální možný

Amdalův zákon - mějme část programu fp, která lze paralelizovat, a část fs, která nejde paralelizovat, potom T(n,p)>=fs+fp/p, S(n,p)<=1/(fs+(1-fs)/p)

Paralelní prefixový součet (PPS)

Pro asociativní operaci + chceme prefixový součet.

In:  2  4  5  3  2  5  7  6  1  4
Out: 2  6 11 14 16 21 28 34 35 39

Lze na EREW-PRAM(n,n) pomocí sčítání ze vzdálenosti 2^i v O(log n)

T(n,p)=O(n/p+log p)
C(n,p)=O(n+log p)
E(n,p)=O(n/(n+p log p))

Použití v RadixSortu, Paralelní sčítačka.

Tridiagonální systém rovnic

Mějme systém rovnic v následujícím tvaru:

|g1 h1  0  0  0 | |x1|   |b1|
|f2 g2 h2  0  0 | |x2|   |b2|
| 0 f3 g3 h3  0 | |x3| = |b3|
| 0  0 f4 g4 h4 | |x4|   |b4|
| 0  0  0 f5 g5 | |x5|   |b5|

Upravíme rovnice do následujícího tvaru:

|x(i+1)|   |-gi/hi -fi/hi bi/hi| |  xi  |
|  xi  | = |   1      0     0  | |x(i-1)|
|   1  |   |   0      0     1  | |   1  |

zjevně pro Hi=Gi G(i-1) … G1

|x(i+1)|      |  x1  |
|  xi  | = Hi |   0  |
|   1  |      |   1  |

Použijeme PPS pro spočtení Hi O(n/p + log p) a poslední procesor vyřeší svojí rovnici o neznámých x1, xn-1 a xn O(1). Výsledek rozešle všem O(log p), ti pak dopočítají svoje proměnné O(n/p).

Celková složitost je O(n/p + log p).

Segmentový paralelní prefixový součet (SPPS)

Výpočet prefixového součtu uvnitř segmentů.

In:  |2  4  5 |3  2  5 |7  6  1  4
Out: |2  6 11 |3  5 10 |7 13 14 18

Je PPS s modifikovanou operací +’. Pozorujeme, že zůstává asociativní.

 +'    b    |b   
 a    a+b   |b
|a  |(a+b)  |b

Sken & rekurence

Rekurence řádu m je množina rovnic xi=f(x(i-1), …, x(i-m)) a výchozích hodnot x0, …, x(m-1). Sken je jednoduchá rekurence 1. řádu, tj. xi=x(i-1) (+) bi / x0=b0.

Lineární rekurence prvního řádu

Mějme předpis x0=b0; xi=(x(i-1) (x) ai) (+) bi, kde chceme, aby operace (+) byla asociativní, a (x) semi-asociativní (tedy existujea asociativní operace (.) taková, že (a (x) b) (x) c = a (x) (b (.) c) ), a (x) je distributivní vůči (+).

Úlohu přetransformujeme, a budeme pracovat s páry hodnot. Definujme y0=a0; yi=y(i-1) (.) ai; ci=[ai,bi]; si=[yi,xi]. Potom s0=[y0,x0]=[a0,b0]=c0 a si=[yi,xi]=[y(i-1) (.) ai,(x(i-1) (x) ai) (+) bi] = [y(i-1),x(i-1)] (o) [ai,bi] = s(i-1) (o) ci, kde (o) je operace definovaná jako: [a,b] (o) [c,d] = [a (.) c, (b (x) c) (+) d] a není obtížné ukázat, že je tato operace asociativní.

Nyní lze použít sken pro spočtení hodnot. Čas bude 2(T(+)+T(x)+T(.))(n/p+log p).

Podobně lze sestavit rekurence m-tého řády, kde se počítá s m-prvkovými

Polynomiální interpolace

Mějme funkci f(x) definovanou n+1 body [x,f(x)], a <= x1 <= x2 <= … <= b. Cílem je najít polynom p(xi)=f(xi). Pomocí Newtonovy metody lze takový polynom najít: Pn(x)=f0+f01(x-x0)+f02(x-x0)(x-x1)+…+f0n(x-x0)..(x-x(n-1)); funkce f(i,j) (od i pro j prvků) se definuje rekurzivně:

f(i,j) = (f(i,j-1) - f(i+1,j-1))/(x(i)-x(i+j))

idk dále …

Řazení na mřížkách

ShearSort

Mřížka s N=n^2 prvky se řadí pro i od 1 do 2 log n + 1 iteracích střídavě hadovitě v jedné dimenzi a normálně v druhé dimenzi. Důkaz správnosti si lze rozmyslet přes řazení 0/1. Logaritmus, protože se počet řádek s mixovanými 0/1 půlí v každé iteraci. Výsledek je hadovitě seřazená mřížka.

Obecná složitost paralelního řadícího algoritmu: T(N,p)=O(N/p log(N/p)) + O(t(p) N/p), kde t(p) je počet compare and exchange řazení p čísel na p procesorech. Aplikováno na ShearSort kde máme t(p)=(2 log n + 1) … idk

Dolní mez na 2D hadí řazení (str. 117)

Rozdělme mřížku M(n,n), potom libovolné datově necitlivé hadí řazení potřebuje alespoň max(2n-2,3n-2sqrt(n)-4) compare and exchange operací.

2n-2 je triviální mez, jinak se nemohl prvek dostat z levého horního rohu do pravého dolního.

druhé nerozumím

Simulace CubeBMS na 2D mřížce (bitonic merge sort?)

Peano curve – je vnoření hyperkostky do mřížky Mn=M(2^(n/2),2^(n/2)), s “nízkou” dilatací dj=2^(j/2). Simulace BMS na mřížce bude trvat n(n+1)/2 komunikačních kroků přes vzdálenost di, kde i jde po sekvenci [0,1,0,2,1,0,3,2,1,…,n-1,n-2,…,0]. Mějme N=2^n, pak součet takové řady je sum(i od 0 do n) sum(j od 0 do i) dj <= sum(i od 1 do n/2) 4 2^i <= 4 2^(n/2+1) = 8 sqrt(N). Řazení simulací BMS na mřížce tak bude trvat T(N,p)=O(N/p log(N/p)) + O(N/sqrt(p)), kde první část je za sekvenční řazení bloků a druhá za BMS v čase N/p za exchange * sqrt(N/(N/p)) za BMS.

Časově a cenově optimální řadící algoritmus na mřížkách

Mějme p=N jader, pak budeme řadit na mřížce následovně: Rozřežeme mřížku na N^(1/4) bloků o velikosti N^(3/4); blokům ve stejné řadě/sloupci říkejme v/h-slice. Provedeme osm fází řazení, [+složitost v O]:

1. seřadíme bloky snake-like [N^(3/8) log(N)]
1. permutujme sloupce tak, aby byly sloupce bloku uniformě rozdělené ve všech blocích [N^(1/2)]
1. seřadíme bloky snake-like [dtto 1]
1. seřadíme sloupce [N^(1/2) parallel bubble sort]
1. seřaďme odd-even dvojice vertikálně sousedních bloků snake-like [dtto 1]
1. seřaďme even-odd dvojice vertikálně sousedních bloků snake-like [dtto 1]
1. seřaďme řádky v globálním snake-like směru [dtto 4]
1. provedeme 2N^(3/8) kroků odd-even transpozice dle globálního snake-like pořadí [2N^(3/8)]

Toto seřadí celou mřížku snake-like v čase 3N^(1/2) + o(N^(1/2)).

Pozorujeme jak se vyvyjí stav 0/1 po každém kroku:

1. každý blok obsahuje max jednu špinavou řádku
1. počet jedniček v blocích v h-slice se liší maximálně o N^(1/8)
1. každý h-slice obsahuje maximálně 2 špinavé řádky
1. každý v-slice má maximálně N^(1/8) špinavých řádek
5+6) slije vertikálně bloky, je pouze jeden špinavý řádek na v-slice; bloky uvnitř h-slice se lyší max o N^(2/8), což je méně N^(3/8) a proto budou globálně max 2 špinavé řádky; počet jedniček se v těchto blocích může lyšit nejvýše o N^(2/8) * N^(1/8)
1. 2 špinavé řádky jsou teď nad sebou a seřazeny, horní může mít max N^(3/8) jedniček a dolní N^(3/8) nul
1. posledních 2N^(3/8) prvků je seřazeno

Díky dvoum řazení a jedné permutaci je čas T(N,N)=3N^(1/2)+o(N^(1/2)).

Batcherův Even-Odd merge sort

Síť s hloubkou log^2 n, která není datově citlivá a řadí. Trik je vytvořit část sítě, která slije dvě seřazené posloupnosti. Důkaz správnosti pomocí 0/1 lemma – rozdělení na sudé a liché do skupin nahoru a dolu zaručuje, že se počet jedniček skupin liší maximálně o jedna. Proto bude na poslední sadé komparátoru pouze jedna pozice, kde může být 0/1 špatně … ta očividně bude opravena komparátorem.

U části permutace a komparací máme

Časová složitost Tm(2) = 1, Tm(2N) = Tm(N)+1; Tm(2N) = log N + 1 = log(2N)
Cenová složitost Cm(2N) = N Tm(2N) = N log(2N)

U části dělení na poloviny máme

Časová složitost Ts(2N) = Ts(N) + Tm(2N) = Ts(N) + log(2N) = O(log^2(N))
Cenová složitost Cs(2N) = 2 Cs(N) + Cm(2N) = 2Cs(N) + N log(2N) = O(N log^2(N))

Tento algoritmus je ekvivalentní řazení na hyperkrychli po dimenzích. Tedy řadíme postupně dimenze: 1; 2, 1; 3, 2, 1; …

Batcherův Even-Even merge sort

Pak je i varianta Batcherova algo. které je trochu jednodušší, páč se nemění volba prvků u první vs druhé skupině. Komparátory o druhé části ovšem nemusí být u prvního a posledního prvku, protože víme, že jsou určitě seřazeny správně

Cenově optimální řadící algoritmus na EREW PRAM - Coleův merge sort

Myšlenka je jednoduchá – použijme rekurzivně tento algoritmus pro seřazení první a druhé poloviny pole. Potom použijeme část algoritmu znovu, pro slití sudých prvků, a pak si projdeme výsledek kde v O(N) zjistíme pozice všech prvků na lichých indexech. Itercí bude log n, protože sléváme posloupnosti velikosti 2^i. Čas na slití posloupnosti je T(2N)=T(N)+O(N), což je celkově O(N); díky dělení v rekurzi tak máme celkově Tc(2N)=2Tc(N)+O(N)=O(N log N).

Vzpomeňme si, že algoritmus sekvenčního slévání dvou seřazených posloupností udržuje pointer do obou polí, porovná prvky a menší z nich kopíruje do výsledného pole.

První pozorování je, že výsledné slité pole obsahuje nejvýše dva prvky s lichými indexy z původních polí za sebou. Součet indexů těchto pointerů při zkopírování prvku je roven pozici prvku ve výsledném poli. Také pozorujeme, že pokud je sudý prvek na pozici j v seřazeném poli sudých prvků, tak se ve výsledném poli nachází v rozmezí 2j až 2j+2 (protože před ním jsou nejvýše dva liché prvky. Pozice pointerů před jeho zkopírováním by tak musela být velice blízko p (pozice v původním poli) a 2j-p. Jediná otázka tedy zbývá … je prvek vyšší než lichý prvek z druhého pole na pozici 2j-p-1? Pokud ano, tak je ve výsledku na pozici 2j, jinak je na pozici 2j-1.

Vyřešili jsme sudé prvky, nyní k těm na lichých pozicích. Díky tomu, že jsme zjistili úplnou informaci o pozicích pointerů pro sudé prvky, tak víme jak asi mohly vypadat pointery i pro liché prvky. Pokud nějaký pointer ukazuje na náš lichý prvek, tak musel být tento prvek vyšší, než nějaký sudý prvek. Hledáme tak poslední výskyt pointeru na tento prvek, protože to je ta hranice, kdy přestal být vyšší než prvky z druhého pole, a začal být nižší. Protože je to poslední hodnota, tak tento prvek byl vyšší, než jeho protivník, ale nižší než další sudý prvek. Jediné co potřebujeme je ho tedy porovnat s lichým prvkem mezi a máme definitivní pozici pointerů při zpracování tohoto prvku na liché pozici – tedy jeho výslednou pozici.

Paralelní sken na spojových seznamech

Mějme jednosměrný spojový seznam reprezentovaný v poli, kde je na indexu I index následníka.

Plně paralelní vytvoření pole předchůdců na EREW

pro i od 0 do n
    pokud s[i]=i potom P[S[i]]=i

List ranking na CREW

Úkolem je najít vzdálenost elementu od konce spojového seznamu. Lze použít pro rychlé přelití do pole.

Použijeme pointer jumping. Řeší v paralelním čase log N, a řeší i sufixový součet. Není cenově optimální C(n,n) = O(n log n). Může být pracovně optimální pokud jádra přeskakují pouze nehotové elementy – ve chvíli kdy dojdou na vyřešený element, tak ukončí výpočet. I takováto varianta není cenově optimální, protože polovina elementů dělá pořád log n skoků.

Pokud chceme cenově optimální algo. můžeme vzít n’=n/log n jader a komprimovat spojový seznam na n’ prvků. Provedení předchozího algoritmu potom bude cenově optimální C(n’,n)=O(n), ovšem je potřeba rychle provést i kompresi a dekompresi “schovaných” elementů.

Prvky, které přeskočíme, budeme vybírat pomocí pseudonáhodného obarvení vrcholů. Zjevně, pokud obarvíme linked-list K barvami a vybereme lokální minima obarvení, tak jsme vybrali alespoň N/K-1 vrcholů. Pokud chceme obarvovat části linked listu nezávisle, tak budeme potřebovat alespoň 3 barvy; zároveň to i ve 3 barvách zvládneme. Pokud nad listem provedeme log log n (lln) 3-obarvení a odebrání maxim, dostaneme list velikosti n (3/4)^(log log n) = n/log n. Na tomto listu provedeme PPS v O(n) a list znovu nafoukneme a nastavíme rank na rank následníka + 1.

Nejdéle trvá konverze O(log n.loglog n). Cenově tedy algo. vyjde O(n loglog n). Pracovně ale algoritmus vyjde O(n), protože pointer jumping se dělá n/log n jádry na vstup velikosti n/log n v O(n) a redukce se udělá v O(n log*n).

Paralelní souvislé komponenty na CRCW

Paralelní postup bude bottom up – přes hrany budeme užívat union-find algoritmus, každá komponenta tak bude na konci mít jednoho reprezentanta v kořenu stromu všech vrcholů komponenty. Problém může nastat, pokud bychom v jednom kroku nastavili rodiče vrcholům vzájemně, tedy P[i]=j, P[j]=i, což by vytvořilo cyklus.

Řešení problému paralelizace spočívá v porovnání ID vrcholů, které chceme spojit, a spojení pouze pokud ID[i]<ID[j].

Z důvodu rozumné analýzy se na začátku provede:

pro každý vrchol i a prvního souseda j
    pokud i>j, tak union(i,j)
    pokud nebyl vrchol i unifikovaný, proveď union(i,j)

Oba kroky jsou jednosměrné a nevytvoří cykly. První krok je jednosměrný díky srovnání a nedělá cykly, protože nemůže i<j,j<k a k<i. Druhý krok je také v pořádku, protože nelze aby j byl taky neunifikovaný, jinak by se spojil v prvním kroku.

Důkaz rychlosti se udělá přes sumu hloubky všech stromů. Díky inicializaci je hloubka maximálně n-1 (cesta). Nyní provedeme následující:

cyklus
    identifikuj hvězdy: if P[P[i]]!=P[i] pak P[P[i]] není hvězda
    pro všechny hrany ij pokud je i kořen
        pokud P[i]>P[j] union(i,j)
        pokud P[i]!=P[j] union(i,j)
    pro všechny vrcholy provedeme pointer jumping
opakuj cyklus, dokud pointer jumping něco změnil

Důkaz správnosti: po inicializaci máme les; cyklus spojí dvě hvězdy pod sebe a potom může připojit hvězdu pod nehvězdu (ne naopak!), což nevytvoří cyklus; pointer jumping netvoří cykly.

Důkaz rychlosti: po inicializaci je hloubka součtu stromů nejvýše n-1-(počet isolovaných vrcholů), tato hodnota se žádnou operací nemůže zvýšit; pointer jumping sníží hloubku (lichých) stromů na (h+1)/2 < 2h/3; součet hloubek stromů je v i-té iteraci (2h/3)^i

Paralelní kontrakce stromu

Na strom můžeme použít operace Rake (odebrání listů) a Komprese (zkrácení cest pomocí pointer jumping).

dokud je počet neoznačených synů roota nenulový
    pro všechny nekořenové vrcholy v z V(T)
        pokud je počet neoznačených synů v roven
            0: rake v
            1: komprimuj v
rake root

Potíž je, že tohle není pracovně optimální W(n,p)=n log(n) (počítají se zbytečné části stromu).

Shunt operace je Rake + Komprese sourozence. Tuto operaci není možné použít na oba sourozence zároveň, nebo na vrchol a jeho strýce. Pokud listy očíslujeme, tak zpracováním pouze těch lichých levých listů nemůže dojít k nevalidnímu zpracování. Proto provedeme Shunt nejdříve na všech lichých listech vlevo, potom vpravo, ostatní čísla vydělíme 2mi a opakujeme.

Očíslování listů provedeme přes eulerovský tah (lze ryhle přes LL dle pravidla pravé ruky) kde označíme hranu do listu váhou 1 a zbytek 0, tak bude mít po suffixové sumě hrana z vrcholu do rodiče váhu počtu listů v podstromě.

Shunt(v):
    Rake(v); active[v]=0; active[P[v]]=0;
    Compress(sibling[v]); P[sibling[v]]=P[P[v]];

CompressTree(T):
    spočti počet listů podstromu každého vrcholu T
    pro všechny vrcholy v z V(T)
        aktivní[v]=je v list?
    opakuj log n krát
        pro všechny aktivní nekořenové vrcholy v z V(T)
            pokud je v lichý v očíslování a P[v] není root
                Shunt(v)
            jinak
                očíslování[v]/=2
    Rake(root)

Mějme p=n/log n, přidělíme každému jádru log n/2 listů. Shunt zničí alespoň polovinu listů, takže provedeme nejvýše log n/2+log n/4+…+log n/(2^log log n) + 1 + … + 1 <= 2 log n = O(log n) kroků.

PPA - Pokročilé Paralelní Algoritmy