36PAR Paralelní systémy a algoritmy

36PAR, přednáší Prof.Ing. Pavel Tvrdík, CSc.

Proč tahle stránka vznikla?

Citelně při přípravě na zkoušku chybí nějaká skripta cvičení. Bylo by fajn, kdyby se tu časem vytvořil soubor řešených příkladů. Pokud si nebudete s něčím vědět rady, prosím napište kde si nejse jistí a třeba na to nějaký kolega přijde a tím pomůže on Vám a vy zase jemu, že se bude cítit o něco jistější před psaním písemky.

Rozhodně by to tu nemělo suplovat slides nebo skripta. Maximálně to tu používejte jako poznámky k dovysvětlení látky nebo k zpřehlednění nějaké pasáže. Pak ale důsledně prosím používejte odkaz na literaturu (včetně data vydání skript! číslování v dalším vydání může být jiné!).

Pro dotazy typu jak mám s tímhle příkladem začít a podobně, prosím, používejte diskusi.

Jak udělat zkoušku?

Jak už říkal Lenin: Učit se, učit se, učit se. Ale jak? Pár tipů:

• Opatřete si příklady z minulých 2-3 let a vyškrtejte z nich ty, které už tento rok byly (vyškrtání občas neplatí u letních termínů), ale při tom dávejte velký pozor, protože na některá témata se vyskytují třeba 2 nebo 3 variace (bitonic postavený na shearsortu, bitonic na hyperkrychli...). Platí pravidlo: nejsem-li si jistý, jestli příklad už byl, radši si ho spočítám.
• Před každou kapitolou si označte příklady, které se k téhle kapitole vztahují. Pomůže vám to v orientaci, co má pro příklady zásadní význam a co jen okrajový.
• Při pročítání kapitoly se už rovnou učte algoritmy, protože bez perfektní znalosti a pochopení algoritmů se tahle zkouška udělat nedá (je to podmínka nutná, nikoli postačující - když máte v 5ti bodovém příkladu dobře algoritmus a nic jiného je to stejně jen za 1 bod).
• Když něčemu nerozumím, pustím si příslušnou pasáž na náznamu z přednášek, třeba to z toho pochopím. Tohle je ale docela časově náročné.
• Je potřeba všechny příklady, které nejsou vyškrtnuté, spočítat a hlavně vědět, proč to tak zrovna je. Pokud u zkoušky máte blbě odvození počátečního výrazu, můžete mít 1000x dobře výsledek, ale body za to nedostanete. Naopak ale když máte odvození dobře jen se přepíšete v průběhu výpočtu ve znaménku nebo špatně sečtete 2 čísla, tak vám za to ani možná nic nesrazí.
• Pozor taky na zanedbávání. Když něco zanedbávám, vždy musím vědět vůči čemu je to menší a případně za jakých podmínek (předpokladů).
• Opakování matka moudrosti. Další den začínám opakováním včerejších algoritmů (podívám se na něj až když už jsem si jistý, že ho z hlavy nevypotím) a opakováním algoritmů probraných před 3mi dny.
• Nepočítejte s tím, že se to naučíte za 2 dny - cca týden je minimum, na jedničku při plném počtu bodů ze semestru aspoň tak 2 týdny.

Tipy jak psát na wiki (cvakni na edit napravo a uvidíš zdroják)

mikromentr: μm, horni index: inch², odkaz: heslo wikipedie: Jak editovat stranku. (newline:)
Obrazek se nejdriv musi nahrat na speciální stránce Special:Upload a pak teprve vlozit obrazek

tabulky	se dělají
jako	v html

matika: Sází se jako v TeXu, tedy v podstatě vzorec píšete jako kdybyste ho někomu diktovali (fakt to nění věda). Podrobnosti: Jak psát matematiku,

$T(n^2,p)=t_s+2\frac{n^2}{p}t_m(\sqrt{p} - 1)+O\left(\frac{n^2}{p}\right)$

Zkouškové příklady

Zkouškové příklady 36PAR

Poznámky a rozšiřující materiály k jednotlivým kapitolám

Analýza složitosti paralelních algoritmů

Asymptotika

základní funkce

odvozené

Mně pomohlo zopakovat si jak vypadají jednotlivé funkce v grafu a z nich je hned vidět, že od nějakého bodu se ty funkce rozbíhají a že už jedna nepřeleze tu druhou. Další možnost je zapsat si to do něčeho takového:

$1 c\cdot \log n < c\cdot \sqrt{n} < c\cdot n$

nebo jste-li Lispu milovnými:

$1 = o(\log n = o( \sqrt{n} = o (n)))$

Odvozené vztahy:

$c \cdot \sqrt{n} < \frac{n}{\log n}$ a dále pak $n < c \cdot n \cdot \log n < c \cdot n^2$

Vzorce k zapamatování:

• $\log(n!) = \Theta (n\cdot \log n)$ (Stirlingova f.)
• $\sum \limits _{k=1}^n \frac{1}{k} = \Theta (\log n)$
• $\sum \limits _{k=1}^n k^p = \Theta (n^{p+1})$ kde p = konst.

Výkonnost paralelních algoritmů

Vzorce k zapamatování:

• $S(n,p)= \frac{SU(n)}{T(n,p)} \le p$ (Zrychlení - optimální lineární zrychlení $S(n,p)= \Theta (p)$)
• $C(n,p)= p \times T(n,p)$ (Cena - optimální $C(n,p)=O(SU(n))$)
• $W(n,p)= T_1 + T_2 + \dots +T_p$ (Práce - optimální $W(n,p)= O(SU(n))$)
• $E(n,p)= \frac{SU(n)}{C(n,p)}= \frac{S(n,p)}{p}$ (Efektivnost)

Isoefektivnost

• $\forall n_p = \Omega (\psi_1(p)): E(n_p,p)\ge E_0$
• $\forall p_n = O(\psi_2(n)): E(n,p_n)\ge E_0$
• $\forall p = \Omega(\psi_3(n))$ a $p = O(p_{mt}): T(m,p)=O(T_{\text{min}})$

Amdahlův zákon

Pro dané $n$ má smysl zvyšovat $p$ pouze do $\psi_2(n)$.

• $SU(n) = f_s + f_p = 1$
• $T(n,p)= f_s + \frac{f_p}{p}$
• $S(n,p) \le \frac{1}{f_s+\frac{1-f_s}{p}}$

Gustafsonův zákon

• $SU(n) = T(n,1) = f_s + pf_p$
• Pozor! $f_{p}$ je tu trochu něco jiného než u Amdahlova zákona: $T(n,p)= f_s + f_p = 1$
• $S(n,p) = \frac{f_s +pf_p}{1}=f_s+p(1-f_s)=p(\frac{f_s}{p}+(1-f_s))$

Paralelní prohledávání stavového prostoru

• půlení zásobníku:
  • u dna
  • u řezné výšky
  • podél celého zásobníku
• hledání dárce:
  • asynchronní cyklické žádosti
    • každý p lokální čítač podle kterého žádá o práci
  • globální cyklické žádosti
    • jeden procesor si vede evidenci čítačem a po každé žádosti inkrementuje
  • náhodné výzvy
    • prostě funkce random()
  • topologičtí sousedé
    • vhodné pro topologie, kde se zvyšuje komunikační režie vzhledem k tomu s kým komunikuju
  • nevyvážené páry
    • kružnice na které je vždy schod, který určuje kdo odpoví na žádost
    • distribuovaná varianta globální cyklické žádosti
• ukončení:
  • Dijskrův peškový
    • pouze pokud nedochází k dynamickému vyvažování
  • modifikovaný Dijskrův peškový
    • obarvování peška podle toho jestli jsem posláním dozadu algoritmus nezkazil
  • stromový
    • vystaví se strom rozdělování (nějaké procesory v něm mohou být ve více uzlech) a nesmí chybět zpětné oznámení dárci po ukončení výpočtu

Paralelní architektury a modely

Taxonomie paralelních architektur

• SIMD
  • různá data
  • instrukce rozesílány centrálně všem najednou
  • implicitně synchronní
• MIMD
  • lokální paměť dat i instrukcí
  • komunikace přes sdílenou paměť nebo propojovací síť
  • asynchronní -> synchronizace explicitně pomocí SW/sítě

PRAM

• $PRIORITY \ge ARBITRARY \ge COMMON \ge CREW \ge EREW$
  • Prioritní CRCW procesory mají pevně přiřazenou prioritu,zápis může provést pouze žadatel s nejvyšší. Simulace 1 kroku na EREW trvá $O(log (p))$, vyhodnocení priorit průchodem stromu, viz. slajd
  • Náhodný CRCW (arbitrary) Zápis provede náhodně vybraný z žadatelů.
  • Shodný CRCW (common) Hodnota, kterou chtějí žadatelé najednou zapsat, musí být stejná - zaručit to musí algoritmus - jinak nastane nedefinovaný stav.

• Časově optimální
  • $T(n,p)=O(\log ^{O(1)}n)$
  • $C(n,p)=O(SU(n)\log ^{O(1)}n)$
• Cenově optimální
  • $T(n,p)=O(\log ^{O(1)}n)$
  • $C(n,p)=O(SU(n))$
• Plně paralelní
  • $T(n,n)=O(1)$
  • $C(n,p)=O(SU(n))$

Propojovací sítě

Teorie grafů

• bisekční šířka .. nejmenší počet hran, které musíme odebrat,aby se graf rozpadl na dvě části o velikosti nejvýše $|V|/2$

• souvislost .. minimální počet uzlů, jejichž odebrání způsobí rozpojení grafu

• Lema: Bipartitní graf může mít hamiltonovskou kružnici pouze pokud je vyvážený.
  • bipartitní .. existuje-li 2-barvení (lze obarvit uzly 2 barvami,aby sousedi nebyli stejně barevní
  • vyvážený .. pokud $|V1|=|V2|$(rozklad V na V1 a V2 vzniklý 2-barvením)

Striktně ortogonální

• Hyperkrychle $Q_n$
  • uzlů $|V(Q_n)|=2^n$
  • hran $|E(Q_n)|=n2^{n-1}$
  • stupeň deg$(Q_n) = \{n\}$
  • průměr diam$(Q_n) = n$
  • bisekční šířka bw$_e(Q_n)=2^{n-1}$
  • hammiltonovská kružnice = grayův kód
  • regulární
• n-rozměrná mřížka $M(z_1,\dots ,z_n)$
  • uzlů
    • množina všech řetězců délky n jejíž jednotlivá písmena z abecedy, která charakterizuje velikosti stran
    • = kartézskému součinu těch množin znaků jednotlivých stran
  • hran
    • v 1 směru kolik jich je v podmnožině
    • součet přes všechny dimenze
  • není regulární
  • bisekční šířka - rozpůlíme po nejkratší straně
  • částečně neefektivně škálovatelná
• toroid $K(z_1,\dots ,z_n)$
  • z kartézského součinu lineárních polí (mřížka) -> kartézský součin kružnice
  • průměr - klesne na polovinu
  • bisekční šířka a stupeň 2x větší
  • uzlově symetrický, regulární
  • k-ární n-toroid je i hranově symetrický
  • přeložení (definováno přes MOD x u hyperkrychle XOR)

Hyperkubické

Graf $wBF_3$ (černě) a $CCC_3$ (červeně)

• kružnice propojené krychlí $CCC_n$
  • uzlů $|V(CCC_n)|=n2^n$
  • hran $|E(CCC_n)|=n2^{n-1}+n2^n$
  • stupeň deg$(CCC_n) = \{3\}$
  • průměr diam$(CCC_3) = 6$, diam$(CCC_n) = 2n - 2 + \lfloor n/2 \rfloor$
  • bw$_e(CCC_n)=2^{n-1}$
• zabalený motýlek $wBF_n$
  • jinak propojené kružnice - vložím hranu tak, že spojuje uzel odpovídající bitu a na druhé kružnici bit následující
  • vlastnosti hodně podobné $CCC_n$

• obyčejný motýlek $oBF_n$
  • udělám z kružnic lineární pole -> není už uzlově symetrické (neregulární)
  • získám hierarchickou rekurzivnost
  • zmizela možnost kružnice liché délky -> dvojbarvení triviální

Nepřímé sítě

Vícestupňové nepřímé sítě (MIN)

• Banyan NxN MIN
  • k-ární delta MIN jako levná náhražka křížových přepínačů ($K=O(\log{N})$)
• blokující MIN $K=\log{N}$
  • dokonalé promíchání $\sigma$ - rotace o 1b
  • motýlek $\beta_i$ - prohození i-tého a nejlevějšího
  • základní $\delta_i$ - rotace postfixu o délce i
• představitelné MIN $K=2\log{N}-1$
  • benešova síť
    • protože $\left(2^{\frac{N}{2}}\right)^{2\log{N}-1} > N!$ tak přestavitelná (lze předpočítat libovolnou permutaci)
    • 2 zrcadlově symetričtí motýlci slepení k sobě
    • dědí vlastnosti po motýlkovi např. rekurzivita (Beneš je složený z malých Benešátek)
• obousměrné MIN
  • chození po stromu (v nějakém přepínači udělám čelem vzad)
  • adaptivní směrování

Stromové sítě

• hyperstrom $HT(m,k,h)$

Vnořovaní a simulace

• statické
• dynamické
  • vyvažování zátěže
  • migrace procesů
  • vnořování

Definice pro statické vnořování

• vnoření = dvojice zobrazení
  • $\varphi:$ zobrazení uzlů
  • $\xi:$ zobrazení hran do cest v cílovém grafu
• zatížení (load)
  • kolik procesů na uzlu běží (kolik uzlů ze zdrojového grafu namapuji na konkrétní uzel v cílovém grafu)
  • optimální stejnoměrné zatížení
• expanze (vexp)
  • vexp$(\varphi,\xi)=\frac{|V(H)|}{|V(G)|}=\frac{\text{cilovy}}{\text{zdrojovy}}$
  • čím větší, tím větší plýtvání
• dilatace (dil)
  • délka cesty na kterou se protáhne jedna hrana
  • optimální stejnosměrná dilatace
• linkové a uzlové zahlcení (ecng, ncng)
  • linkové: počet zdrojových cest procházející přes cílovou hranu
  • uzlové: počet cest začínajících, končících nebo procházejících daným uzlem z cílového grafu
• Qasiisometrické vnoření
  • jestliže měřítka vnoření jsou konstatní

Do Hyperkrychle

• simuluje optimálně téměř jakoukoli topologii
• optimální $Q_n$ pro load=1: $n = \lceil\log{|\text{uzlu zdrojoveho}|}\rceil$
• vnoření cest a klužnic
  • $\bar{\bar{x}} = x \to$ když se adresa zdroje a cílového uzlu cesty liší v konkrétním bitu, tak počet rovnoběžných hran tomu odpovídající v cestě bude lichý
• vnoření stromů
  • $CBT_n \stackrel{emb}{\rightarrow} Q_{n+1}$ dil = 2 a load = ecng = 1
  • inorder číslování
  • když udělám ze stromu vyvážený (2 kořeny) a graficky (pozor, algebraicky to není jen translace, nýbrž posun kombinovaný s permutací současně) ty 2 stromy vedle sebe poposunu
  • dynamické (pravděpodobnostní)
  • D & C
    • jednovlnový
      • n-úrovňový - load=1 ale plýtvá 50% uzlů (které se použijou na ten sestup ve stromu)
    • vícevlnový
      • jakoby v pajplajnu několik vln zasebou
      • load=1 a dil=2 je optimální
• vnoření mřížek a toroidů
  • mřížka a toroid s všemi kružnicemi sudé délky je podgraf $Q_{\lceil\log{n}\rceil}$
  • když některé liché, tak dil=2
• vnoření hyperkubických sítí
  • jsou to podgrafy, takže s $CCC_n, wBF_n, oBF_n$ není žádný problém

Do toroidů a mřížek

• hyperkrychlí
  • takový ten cik-cak (lexikograficky po řádcích) tzv. Peanova křivka
• toroidů do toroidů
  • po řádcích jestliže je víc sloupců
• mřížky
  • čtvercových do obdélníkových
    • rozsekat na sloupce a jednotlivé sloupce zanořit (vznikne hodně malých hadů)
    • aby ale byla lepší vodorovná komunikace, tak začíná vždy odzhora
  • obdélníky do čtverců
    • klempíř bez nůžek a kusem plechu - buďto had, nebo šnek, někdy je lepši to, jindy ono

Směrování, techniky přepínání a zablokování

• jednotky komunikace
  • zpráva - z hlediska programu
  • packet - se směrovací informací (hlavičkový flit + datový flit)
  • flit (flow digit)
    • jednotka toku na linkové vrstvě
    • několik slov, několik cyklů
  • fit (fyzical digit)
    • co se dá přenést mezi přepínači za jeden cykl

Klasifikace

1. Rozhodování o smerování
   • distribuované (inkrementální)
   • zdrojové (all-at-once)
     • dlouhá hlavička, pokud dlouhá česta
       • křižovatkové (u ortogonálních = pravoúhých) - předpočítám jen směry (jak na dálnicích ukazatele na jednotlivá města)
   • hybridní
     • jen některé uzly jsou předpočítané a ostatní cesty se počítají za běhu
   • centralizované - dnes už muzeální (SIMD)
2. Adaptivita
   • Deterministické
   • Datově necitlivé
     • Deterministické její podmnožinou
     • nejsou adaptivní (např round-robin nebo random)
   • Adaptivní
     • sbírají informace o kolí -> roste ale komplexnost algoritmu
     • distribuované adaptivní
3. Minimálnost
   • • minimální (lačné, přímé, po nejkratší trase nebo přírustkové)
       • neuhne a ne a ne a ne! ;) může se zablokovat
     • neminimální
       • dynamické blokování (livelock) - některé jsou odmítnuty a jak tam krouží tak to okolí zahlcují
4. Progresivnost
   • Progresivní
     • nikdy necouvne
   • Neprogresivní
     • když ucpané, tak se o několik stáhnu a tím uvolňuji prostředky
     • vždy adaptivní
5. Implementace smerovacích algoritmu
   • Konecný automat - počítám to
   • směrovací tabulky - mám předpočítáno

Základní modely přepínání

• Bisekční propustnost - z jedné poloviny do druhé
• Sítová propustnost - když použiju všechny kanály najednou
• $t_s$ startovni zpozdeni (doba pro vytvoreni paketu) [s]
• $t_r$ čas pro vytvoreni směrovacího rozhodnutí [s]
• $t_w$ cas prenosu pres prepinac z vstupu na vystup [s/B]
• $t_m$ zpozdeni kanalu, cas na prenos jednoho fitu [s/B]

• Přepínání kanálů (Circuit Switching, CS)
  • vybuduje se nejdřív kanál (směrovací sonda vyvrtá ďouru tím že nastavuje směrovače) -> potvrzení -> data tečou po vytvořené cestě jako po jednom vodiči (data se neukládají v uzlech po cestě) -> není závislé na velikosti posílaných dat
  • Prenos zprávy délky $\mu$ na vzdálenost $\delta$ trvá cas
  • $t_{CS}(\mu, \delta) = t_s + \delta(t_r + p(t_w + t_m)) + \delta(t_w + t_m) + \mu t_m =$ nastartovat + čas sondy aby se dostala k cíli + potvrzení sondy + vlastní přenos dat
• Ulož-pošli-dál (Store-and-Forward, SF)
  • prakticky IP směrování (nebo ethernet přepínání)
  • $t_{SF}(\mu, \delta) = t_s + \delta(t_r + (t_w + t_m)\mu)$ = nastartování + v každém přepínači (rozhodni kam s ním dál + (překopíruj ho přes směrovač + pošli na další směrovač)) $\doteq t_s + \delta\mu t_m$
  • čím delší zpráva, tím delší zpoždění (lineárně) -> datově citlivé přepínání
  • větší paměť -> dražší směrovače
  • výhoda: jeden packet zabírá z celé trasy jen jednu část
• Průřezové přepínání (Virtual Cut-Through, VCT)
  • hlavičkový flit se prodírá sítí stejně jako u SF a zbytek dorazí až potom, ale to už přepínač počítá kam s ním dál a než dorazí konec, hlavička už může být na jiném přepínači (packet = vláček datových flitů)
  • přepínače opět paměť na celý packet, ale když nebudou kolize, tak se nevyužijí
  • $t_{VCT}(\mu, \delta) = t_s + \delta (t_r + t_w + t_m) + \mu max(t_w, t_m)$ = nastartujeme + hlavička způsobuje na každém switchi (routování + projdutí přes switch + cesta na další switch) + dojezd zbytku packetu po příjezdu hlavičky do cíle (pokud výstupní i vstupní fronty, jinak $t_w + t_m$
• Červí přepínání (Wormhole, WH)
  • odstraňuje nevýhodu VCT - nepotřebuje paměti na celý packet -> když už se to posílá po flitech, tak tam bude paměť jen na flit (nebo pár flitů)
  • když ale dojde ke kolizi, tak vláček zamrzne jak vlak na transibiřské magistrále (a vláčky co jedou za ním (kolize) jsou vlastně pak třeba taky jakoby rozbité)
  • WH 2-D toroid muže výkonově překonat WH hyperkrychli zhruba téže ceny.
  • $t_{WH}(\mu, \delta) = t_s + \delta(t_r + t_w + t_m) + \mu max(t_w, t_m) =$

stejné jako u VCT až na to zamrzání a cenu

• CS, VCT a WH jsou necitlivé na vzdálenost
  • $t_{CS}(\mu, \delta) \doteq t_{VCT}(\mu, \delta) = t_{WH}(\mu,\delta) \doteq t_s + \delta t_d + \mu t_m$, kde $t_d = t_r + t_w + t_m$

Zablokování (deadlock)

Když (orientovaný) graf kanálových zívislostí (Z) je acyklický, tak nemůže dojít k zablokování naopak.

1. Detekce a zotavení: nejméne opatrné, možný velký zisk, ale i ztráty.
2. Prevence: konzervativní pridelování všech prostredku najednou => jejich malé využití – použito v technice prepínání kanálu (CS).
3. Vyhnutí se zablokování: postupné pridelování prostredku tak, aby globálne nemohlo k zablokování dojít
   • usporádání (serazení) dimenzí (smeru)
     • např. XY pro 2D -> tím se Z stane acyklycký a přitom stále graf zůstává souvislým
     • nefunguje v kružnicích
   • Algoritmy typu Nahoru*/Dolu*
     • libovolná topologie
     • korektní orientace když:
       1. existuje kořen z nějž žádná orientovaná nevychází (všechny jen vcházejí)
       2. neexistují orientované kružnice
     • konstrukce pomocí kostry do šířky a zorientuje se směrem ke kořenu (pokud hloubka různá) nebo směrem k uzlu s menším ID
     • algoritmus směrování pak funguje tak, že nejdřív směrem po smětu šipe grafu (Nahoru*) a potom směrem proti šipkám (Dolu*)
     • Obě skupiny mohou být prázdné, takže mohu jít i třeba jen nahoru nebo jen dolu. Název je vlastně regulární výraz
     • Důkaz: všechny uzly dosažitelné přes kořen a cyklus tam nejde udělat, protože bych po dolu musel použít nahoru.
   • Zablokování v toroidech
     • řešení pouze pomocí virtuálních kanálů (každý má své řízení)
     • multiplexery a demultiplexery ktere slévají na jednu kolej 2 vláčky a až je pořeba tak je zase rozděluje
     • stačí 2 - horní a dolní -> použijeme podobný mechanismus jako u nahoru*/dolu* a řekneme že nejprve smí přes horní a pak už jen dolní (tím vznikne virtuální spirála a ta není cyklická ale má konec a začátek)

Paralelní prefixový součet a technika eulerových cest

• Redukce je krásne paralelizovatelná $\iff \oplus$ = asociativní.
• normální hyperkubický algoritmus = v jednom paralelním kroku používá pouze hrany jedné dimenze a v následujícím jen hrany dimenze o 1 se lišící

Paralelní prefixový součet PPS

• Výstupem pole stejné délky jako vstupní a součty jsou od začátku
• Sekvenční alg. stejný jako u redukce, jen zapisuji i mezivýsledky (stejná složitost)
• Paralelní na EREW: vždy se sčítají hodnoty ve vzdálenosti 2x větší než v minulém kroku
  • Táž časová složitost jako EREW PRAM paralelní redukce!
• Na nepřímém stromu
  • rodič kromě poslání nahoru (vzestupná vlna) se posílá od levého dítěte k pravému dítěti (sestupná vlna) a co případně přijde zezhora tak je rozkopírováno všem dětem
  • ideální je,když lineární pole není jen v listech,ale namapujeme ho na něj POSTORDER -> pak výpočet v $2h(T)$ krocích
  • na libovolné síti: konstrukce kostry do šířky a pak předchozí algoritmus
  • to mapování pole se dělá jen jednou
• Na hyperkrychli
  • PPS = normální hyperkubický algoritmus
  • počet kroků log
  • zelené registry se posílají sousedovi v dané dimenzi
  • do žlutého to co přišlo přičtu jen když adresa od koho to přišlo < než moje
  • na konci v zeleném globální sumu a ve žlutém prefixový součet
• Na SF mřížce
  • namapuju lexikograficky
  • pomalé přepínání - ve třech fázích na 2D mřížce: vodorovná fáze, svislá fáze, zpětná vodorovná
  • rychlé přepínání - namapujeme na tu mřížku strom a simulujeme jednotlivá patra -> dosáhneme (2x) log složitost

Škálovatelnost PPS

• To samé jako u redukce akorát ještě sekvenční část na konci.
• algoritmus:
  • Procesory si provedou nad svým kouskem sekvenčně PS a nad posledními prvky se provede PPS.
  • Dopočítání lokálních součtů (tím se to liší od redukce).
• Táž časová složitost jako paralelní redukce! ($T(n, p) = O(n/p + \log{p})$ kroku na PRAMech, hyperkrychli, WH mrížkách a sítích s $O(\log{p})$ průměrem.

Aplikace PPS

• Zhušťovací problém
  • Na začátku namapované pole nějak na procesory, ale žádný neví v jakých dalších procesorech jsou ostatní prvky pole. Cílem to pole (velikosti k) dostat na prvních k procesorů aby se ale nepřehodilo pořadí.
  • provede se PPS nad příznaky.
• RadixShort
  • v každém kroku sesuneme (zhustíme) ale nepřeházíme podle bitu stejném jako číslo kroku
• Paralelní binární sčítačka s predikcí prenosu
  • Definuje se operace $\odot$ pomocí které se vyruší neznámé z pole přenosů.
  • Operace je asociativní a tedy použiju PPS na výpočet pole přenosů bez neznámých (p).
• Tridiagonální systém rovnic
  • speciálně řídká: nenulové koeficienty jen na diagonále a nad a pod.
  • každou jednotlivou rovnici si vyjádříme pomocí maticových operací do tří vektorů po dvojicích a přidáme jedničku:
    • i-tá položka pole vektorů = konstantní matice $G_i$ * (i-1)-tá položka pole vektorů
    • nakonec to vede na maticové rovnice, kde místo $G_i$ je matice $H_i$, která vznikne jako prefixový součin matic $G_i..G_1$ a napravo matice $\begin{bmatrix} x_1\\ 0\\ 1\\ \end{bmatrix}$
    • jakmile máme pomocí PPS spočítané pole matic $H_i$ tak jeden procesor spočítá soustavu 3 rovnic pro neznámou $x_1$ a pak už je to trivka ;)

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

• Cílem je vypočítat všechny prefixové součty uvnitř segmentů izolovane.
• 1 globální PPS aplikovaný na celé pole s modifikovanou bin. operací $\overline{\oplus}$, která navíc obsahuje informaci o hranicích segmentů
  • když levý operand prvním ze segmentu, tak výsledek ocejchován jako výsledek na levém okraji
    • Tím říkám, že s tímhle výsledkem jsem už zkončil,už je to nedotknutelné.
  • když pravý operand první v segmentu, tak výsledkem zase jen ten levý operand (tam už z tohohle segmentu zasahovat nesmím)
• EREW PRAM paralelní QuickSort
  • kontrolujeme při každém kroku jestli už to není setříděno: paralelně porovnáním všech sousedních dvojic jestli to neporušuje (paralelní redukce s AND)
  • v každém segmentu pivota (první prvek)
  • procesor musí oznámit hodnotu pivota všem procesorům (nevím kolik, nevím jak je dlouhý segment) se kterým sdílím segment -> dá se to rychle realizovat pomocí SPPS (operace $a \oplus b = a$ - tedy rozkopíruju všechny hodnoty, ale jen k první zarážce)
  • rozdělíme na části:
    1. prvky < pivot pomocí PPS (zhuštění)
    2. prvky = pivot pomocí PPS (zhuštění)
    3. prvky > pivot pomocí PPS (zhuštění)
  • provedeme permutace (proházení čísel a tím vytvoříme 3 podsegmenty <,=,>)

Prefixový součet nad zřetězené seznamy

• každý prvek zná pouze svého následníka (na vstupu jen lokální informace)
• Převod z pole následníků na pole předchůzců (plně paralelní algoritmus):
  • paralelně udělej
    • každý zapíše sebe jako svého předchůdce
    • pokud nejsem poslední,tak zapiš jako předchůdce mého následníka sebe
• Přeskakování ukazatelů (výpočet pořadí prvků)
  • alg:
    • paralelně udělej
      • nastavení: všechny hodnoty 1 kromě posledního kde bude 0
      • log n násobné opakování operace:
        • do pole pořadí zapiš = přičti pořadí mé a mého následníka a přeskoč mého následníka (můj následník je od ted následník bývalého následníka)
  • každému pointeru přiřadím na začátku 1 a pak ty jedničky sčítám
  • vyžaduje paralelní čtení tedy CREW (hodnotu posledního následníka pořád chce víc a víc procesorů)
  • když místo 1 dáme nějaké hodnoty, tak se vlastně provádí PPS (respektive sufixový=příponový součet)
  • škálovatelnost
    • nefunguje škálovatelnost že snížím počet procesorů, protože tam není žádná lokalita dat
    • řešení: počítám s $p = \Theta(n/\log{n})$ a zmenším počet prvků na $n' = n/\log{n}$ (ta transformace se dá udělat v $\log{n}$ čase), protože pak $T(n',p) = O(\log{n})$ a $C(n',p) = O(n)$

Eulerovské cesty a Eulerovské grafy

• Eulerovský graf = každý uzel musí mít sudý stupeň
• Eulerovský cyklus = kružnice, procházející každou hranou G právě jednou
• jak paralelně postavit eulerovskou cestu (plně paralelní algoritmus)
  • když graf je strom, tak projdu celý graf tak, že vždy na křižovatce zahnu vpravo
  • alg. procházení stromu do hloubky
  • každé hraně určím následníka tak, že ho nastavím na následníka jejího siblinga ET[e] := (AA[e].Sib).Next
• nalezení všech rodičů stromu
  • ke každé hraně známe pořadí a ke každé její dvojče
  • když je to ta která jde nahoru (ke kořeni) tak má vyšší pořadí než její dvojče, nastavím jí Direction na up a první uzel nastavím jako rodiče druhého uzlu
• Výpočet velikostí všech podstromu paralelně
  • I
    • ke každému uzlu podstromu vedou 2 hrany
    • odečtu pořadí, přičtu jedničku a vydělím dvěma (platí, pokud je druhý uzel rodič prvního)
  • II
    • velikost podstromu = počet jeho Down hran.
• Výpočet úrovní všech uzlů paralelne
  • PPS pro weight, které určím jako 1 nebo -1 podle příznaku Direction.
• Číslování Preorder
  • PPS pro počet hran směřujících dolů, když procházím strom do hloubky

Paralelní třídicí algoritmy

• třídění pomocí operace porovnej-a-vyměň (C&E)
• Nepřímé sítě
  • třídící síť = sloupce komparátorů = HW implementace C&E
  • Počet C&E kroků = hloubka třídící sítě = délka nejdelší cesty ze vstupu na výstup.
• Přímé sítě
  • procesory oindexujeme a pak si povídají a vyměňují čísla až je nakonec pole setříděno podle indexů procesorů
  • indexace hamiltonovskou cestou (hadovitě) nebo nehamiltonovsky (lexikograficky)
  • třídění pomocí dokonalého párování (v každém kroku všechny postavíme do dvojic jako ve školce a oni si navzájem vymění podle indexů čísla) -> datově necitlivé
  • Škálovatelnost (p<N): každý si srovná svojí posloupnost a po párování sloučíme (sloučená srovnaná) a rozpůlíme uprostřed Sluč-a-Rozděl (M&S)
  • odvození časové složitosti při p<N, když známe jen pro generický případ p = N (procesorů jako čísel - časová složitost toho je to $\tau (p)$): $T(N, p) = O \left(\frac{N}{p}\log{\frac{N}{p}}\right)+O \left(\tau(p)\frac{N}{p}\right)$ = každý si setřídí svoje + paralelně si porovnávají svoje posloupnosti
• Datově necitlivé 0-1 třídění
  • monotonně rostoucí (když $x \le y$ pak i $f(x) \le (y)$) funkce, tak je jedno jestli nejdřív aplikuju funkci a pak setřídím nebo setřídím a pak aplikuji funkci na výstupní hodnotách
  • z toho plyne že když algoritmus (síť) umí setřídit binární posloupnost tak umí setřídit libovolnou posloupnost
  • Důkaz (sporem): síť setřídí správně binární posloupnosti, nesetřídí správně nebinární posloupnosti, definujeme monotonně rostoucí fci (nebinární -> do binární), nemůže nastat situace, že by na výstupu byly přehozené 0 a 1 a tady ani obrazy nemůžou být přehozené.

Třídění na mřížkách

• Sudo lichá transpozice (EOTSort, paralelní bubble-sort) na 1-D
  • párování licho-sudé nebo sudo-liché (jiné párování neexustuje), takže je budeme střídat
  • v každém kroku se jednička posuno o jednu (v nejhorším tedy N kroků - jediná 1 úplně vlevo)
  • škálovatelnost stejná jako pro naivní MergeSort ($T(N, p) = O \left(\frac{N}{p}\log{\frac{N}{p}}\right)+O \left( N \right)$) ale tady je nejlepší možný (topologicky optimální)
  • $T_{generic}(N,P) = O(N)$
• ShearSort na 2-D
  • seřadíme do hada
  • střídá se:
    • setřiďování řádků (liché rostou doprava a sudé doleva - aby z toho pak byl ten had)
    • setřiďování sloupců (všechny rostou směrem dolů)
  • kolikrát: dostatečný počet krát ($2\log{n}+1$), protože 1 řádková a 1 sloupcová fáze zmenší počet nečistých řádek nejméně na polovinu
  • Složitost: $T_{generic}(N,P) = O(\sqrt{N}.log(N))$
  • Modifikovaný algoritmus s tříděním řádku stejným směrem nefunguje.
• Spodní mez složitosti hadovitého třídění na 2-D mřížce
  • $M(n,n)$: minimálně $max(2n-2,3n-2\sqrt{n}-4)$ kroků tzn. někdy nejde dosáhnout ani triviální meze (průměru)
  • Důkaz (metoda odpůrce)
    • rozdělíme na trojůhelník (v něm budou jen 0 nebo N) a zbytek. Necháme nejdokonalejší algoritmus pracovat $2n-2\sqrt{n}-3$ počet kroků (nezbytné abych se pomocí přeskoku dostal z trojuhelníkové oblasti až do tesné blízkosti pravého spodního rohu) -> tedy trojůhelník dosud nemohl zatím ovlivnit ten pravý dolní roh
    • protivník teď zvolí tolik N aby vyplňily řádek (a pokud sudý had, tak i předposlední řádek) takže ještě n-1 kroků
    • $(2n-2\sqrt{n}-3) + (n-1) = 3n-2\sqrt{n}-4$ a tedy nemůže jich být trivijální spodní mez ale tohle
• 3DSort: Lexikografické třídění
  • skládá se z rovinných fázích (konstantní počet - tím se liší od ShearSortu, který těch 1D třídění potřeboval log)
    • setřídění v průmětu zx (1. rozměr - nuly se sesypou dolů, ale každá rovina z tomografu vypadá jinak)
    • kolmo (2.rozměr - zase se sesypou nuly dolů), v každé rovině může být max 1 schod
    • 3x vodorovně: hady (střídají se) a jednou vodorovně a teď už může být max 1 špinavá vodorovná rovina a tak ještě naposled setřídím vodorovně (3.rozměr).
    • Složitost: $T_{generic}(N,P) = O(N^{1/3}.log(N))$

Třídění na hyperkubických sítích

• Sudo-Lichý MergeSort (EOMS)
  • rekurzivní - 2 malé EOMS jejichž výsledky se sloučí
  • slučování také rekurzivně
    • lichá a sudá podposloupnost (podle indexů) a každá na jeden podblok EOMerge(N/2,N/2)
    • na výstupu se zase rozhodí do dvojic a sloupec komparátorů (už to bude špatně jen v jednom případě a to některým komparátorem zachytím)
  • Časová složitost = hloubka EOMerge(N,N) $d_s(N)=O(\log^2{N})$
  • Cenová složitost = počet komparátorů $c_s(N)=O(N\log^2{N})$ -> není asymptoticky optimální
• Sudo-Sudý MergeSort (EEMS)
  • liší se pouze v tom jak rozdělí ty posloupnosti (sudé z a a sudé z b jdou do jednoho podbloku EEMerg)
  • výhoda: ve výstupním sloupci se ušetří 1 komparátor, protože první a poslední číslo jsou už jednoznačně dobře
• Bitonické posloupnosti
  • skládá se ze 2 posloupností, z níž jedna roste a jedna klesá (a nezáleží na rotaci) = existuje tam právě jeden vrchol a jedno údolí
  • bitonické rozdělení - rozseknu na 2 stejně dlouhé poloviny a položím je na sebe (někde se protnou - musejí) a v místě protnutí rozseknu vodorovně a to co je pod dám doleva a nad doprava
    • vlastnosti:
      1. obě vzniklé posloupnosti jsou zase bitonické
      2. každý prvek z levé je menší než z pravá
  • můžeme to dělat rekurzivně až z toho bude monotonní posloupnost
• Implementace
  • EOMS na $oBF_n$
    • funguje jako nárazník - výstupy se po čase objeví na vstupech
    • v prvním stupni se nahoře nechávají rovně, v druhé polovině se prohazují
    • čím jdu do větší hloubky do motýlka, tak tím slučuji větší n-tice
  • EOMS na $Q_4$
    • sloučení do dvojic - pouze vodorovně v jednom směru
    • sloučení do čtveřic - musím otočit modré vůči červeným, pak provedu 2x komparaci a mám čtveřice
    • podobně do osmic
    • výsledkem je lexikografické uspočádání jen jsme každou druhou posloupnost museli ještě otočit
    • -> ještě zmodifikujeme aby se to otáčelo rovnou v těch podkrychlích (prostě jen jinak interpretuji ty komparace) -> přímočará implementace MergeSortu (CubeBMS) $T(N,N) = O(\log^2{N})$
    • simulace na PRAM - procesor jen šáhne do sdílené paměti a prohodí
    • simulace na mřížkách (MeshBMS)
      • mapování krychle na mřížku pomocí peanovy křivky

Permutační směrování

• o tom jak si procesory vyměňují data
• třídění je speciální případ permutace
• pomocné fronty pro $\beta$ packetů
• paměťově optimální permutace: $\beta = O(1)$

V mřížkách

• 1-mnoha v 1D mřížce
  • uzel cílem nejvýše 1 packetu, takže packetů je stejně jako procesorů (ale některý procesor může generovat víc packetů a některý žádný)
  • protokol nejvzdálenější první (FF) v nejvýše n-1 krocích (optimální)
  • Důkaz: velmi podobný jako 1D EOTShort
• Permutace 1-1 na 1-D mrížkách
  • speciální případ EOTSortu na 1D mřížce
  • odlišné jen v tom, že tady se v prvním kroku vždy něco do pohybu dá
• XY permutacní smerování v 2-D mrížkách
  • zvládnout se to dá v $2n-2$ což je optimální, ale platíme za to větší paměťovou náročností (pro velká n cca 2/3 packetů)
  • packety nejdříve do správného sloupce a pak v tom výtahu jede nahoru nebo dolů
  • Důkaz
    • nejhorší případ když v jednom uzlu 3 dostanu (zleva, zprava, zespodu) a jeden pošlu nahoru, kam chtějí ale všichni (takže musím pro 2/3 mít místo v paměti)
    • časová složitost: do správného sloupce + do správného patra $= (n-1) + (n-1) = 2n-2$
  • na vícerozměrné (k-D) mřížky se to dá zobecnit ($k(n-1)$ kroků, paměťová bude $\approx \sqrt[k]{n}$)

Metody minimalizace paměťových požadavků pro permutační směrování

• nejen pro mřížky
• randomizace
  • při náhodné permutaci se stane nejhorší případ jen s malou pravděpodobností
  • převod zlobivé permunace na náhodnou permutaci
    • převede se na 2 náhodné permutace
    • náhodný generátor vygeneruje adresu mezilehlého uzlu (a tím tam už pravděpodobná ta situace)
    • více uzlů může vygenerovat stejnou adresu (ale málo pravděpodobné)
  • Když paměti $\beta = O(\log{n})$ tak s pravděpodobností $1-O(1/n^2)$ dosáhneme času $2n+o(n)$.
• založené na seřazení
  • alg:
    • procesory k paketům přistupují jako k položkám seznamu (klíčem adresa) a tohle pole setřídí do hada lexikograficky ($T_{sort}(M(n, n))$)
    • každý druhý sloupec otočím ($n-1$)
    • nejsou tam pak v jednom řádku 2 stejné čísla sloupců (délka může být max n a když předtím bylo v hadovi, tak nemůžou být)
    • rozmístí se do správných sloupců ($n-1$)
    • permutace v rámci sloupců ($n-1$)
  • $O(T_{sort}(M(n, n)) + 3n)$
• s předvýpočtem
  • každý procesor nevěděl o jiných procesorech (proto kolize, protože nulová koordinace)
  • předem si vypočítáme bezkolizní permutaci a pak už jí jen on-line používáme opakovaně
  • algoritmus pro předvýpočet ($3n-3$ kroků):
    • pro všechny sloupce předpočítáme permutace aby neexistovaly řádkové kolize
    • pak už postupuju stejně jako minule (místo sortu je tam ten předvýpočet)
  • Hallova věta o párování:
    • bipartitní (existuje dvojbarvení), každá barva stejně uzlů a k-regulární (každý uzel k hran) může být obarven tak, aby každý uzel měl od každé barvy hran jednu.
    • permutační problém -> graf:
      • packet ->hrana
      • zdrojové sloupce -> uzly vlevo (S)
      • cílové sloupce -> uzly vpravo (d)
      • když permutace úplná tak budou nějaké hrany chybět
      • číslo řádku -> barva
      • proházeli jsme packety ve sloupcích aby každý paket byl ve sloupci který náleží jeho barvě (a tím nemůže být už v řádku stejný index sloupce, protože máme jednoznačné párování)
    • alg. nalezení takového barvení (deterministický a polynomiální):
      • zkoušej přidělit chlapcům děvčata (tedy n krát opakuj)
      • pokud jsou všechny děvčata pro daného chlapce už rozebraná, tak se vrať dokuď se nějaká neuvolní (v nejhorším případě n)

V hyperkubických MIN

• On-line permutační směrování na síti motýlek
  • permutace = bitová operace
    • otočení = přepíšu od konce k začátku
    • prohození = rozpůlím na 2 poloviny a ty prohodím
    • přeložení (parametr w) = xor s tím w
    • doplněk = inverze
  • Otočení a prohození
    • přetížení hran uprostřed (nutná serializace -> zpoždění)
    • $\Theta(\sqrt{N})$ kroků, kde $N=2^n$ (všeportový, SF ale je to jedno, $indBF_n$)
    • tedy to zpoždění nepříjemně veliké
    • Důkaz: počet uzlů který je výstupní do střední sekce jsou jen ty, které mají adresu v levo nuly a jen těch k bitů který už se udělali jsou různé -> časová složitost $\approx \sqrt{N}$
    • paměťové požadavky
      1. záplavový alg. $\beta = \sqrt{N/8}$
      2. priorita zleva $\beta=0$ (aneb se slušností nejdál dojdeš)
    • nejhorší případy pro minimální směrování na hyperkubických sítích
  • Zhušťovací permutace (viz látka o PPS)
    • relativní pořadí se nezmění
    • pomocí PPS si spočítá pořadí a tím určím kam to mám poslat
    • Důkaz že je to bezkolizní (uděláno na $oBF$): infuktivní, založený na tom, že rekurzivní topologie
      1. nemůže nastat na 1. sloupci: nepřehazují se, jen se ztratí mezery (na konci musí jít těsně zasebou, pokud vcházeli na stejném mikromtýlku)
         • buď oba půjdou rovně (neinvertují bit)-> vyhnou se)
         • nebo oba půjdou šikmp (oba invertují) -> vyhnou se
      2. indukční krok: dalším sloupci to platí také
  • Roztažná permutace a redukce permutačního směrování na řazení
    • roztahovací = otočení zhušťování
    • setřídění paketů podle adres + roztažení
  • Monotóní permutace
    • • složení zhušťovací a roztahovací
  • Permutace přeložení a doplněk
    • XOR znamená že v každém sloupci se buď kříží nebo ne
• Off-line permutační směrování na Benešově síti
  • složená z motýlků
  • pro libovolné permutace jdou předpočítat cesty (proto je to představitelná)
    • jakmile udělám 1b volbu, ostatní už jsou dány (když první paket chce rovně, tak druhý už musí jít přes spodní půlku) -> musím ošetřit všechny přepínače na nejvyšší úrovni
    • rekurzivně aplikuji dál
• Off-line optimální směrování pro libovolnou permutaci na $oBF_n$
  • obdélníková mřížková topologie na které ale neexistují sloupce (jsou jen vyrtuální) -> musíme dělat jinak než u standardních mřížek
  • použijeme Hallovu větu a spočítáme si aby na každé kružnici byla permutace mezi úrovněmi (každá je adresátem právě jednou)
  • každý sloupec bude jedna permutace benešovy sítě
  • 1 předvýpočet pro halovu větu a pak pro každou halovu větu zvlášť
  • všechny ty permutace můžeme udělat najednou (v pajplajnu)
  • dopředné vlny, zpětné vlny a pak už každý packet ve správné úrovni (kružnici)
  • Přímá síť $wBF_n$ (nebo jiná hyperkubická síť) může simulovat libovolnou N-uzlovou síť se zpomalením $O(d\log{N})$, kde d je max stupeň uzlu (obě sítě všeport, fullduplex a SF).
  • Důsledek: Je-li povolen předvýpočet, pak libovolnou $(N \log{N})$-uzlovou síť G s omezeným stupněm uzlu lze simulovat na N-uzlové hyperkrychli se zpomalením $O(d logN)$, kde d je maximální stupeň uzlu G.

Kolektivní komunikační operace

• časová složitost
  • konstatní čas - počet kroků
    • spodní mez $\rho_{xxx}(G)$
    • horní mez $r_{xxx}(G)$
  • lineární čas - počet sekund (ms atd.)
    • spodní mez $\tau_{xxx}(G)$
    • horní mez $t_{xxx}(G)$
• komunikační práce: počet hopů, paketo-hran
  • spodní mez: $\eta_{xxx}(G)$
  • horní mez: $h_{xxx}(G)$
• komunikační efektivnost
  • plně využívá propustnost
  • eliminovat redundantní komunikaci - dělat jen to co skutačně musí
    • NODUP = žádný packet na stejný uzel nepříjde více jak jednou
    • NOHO = aby se packet který pošlu já nevrátila zase mě

OAB

• OAB v SF sítích
  • Dolní meze
    • $\eta_{OAB}(G,s)=$ počet uzlů - 1 = počet cílových uzlů (sobě to posílat nemusím)
    • při větších excentricitách:
      • $\rho_{OAB}(G,s)=\text{diam}(G)$ je uzlově symetrická (nezáleží na tom, kde vysílač je)
      • $\rho_{OAB}(G,s)=\text{excentricita}_G(s)$ je uzlově nesymetrická
    • při větších hodně malé excentricitě:
      • $\rho_{OAB}(G,s)=log_{d+1}(|V(G)|)$
      • v jednom taktu můžu vyslat k směry zprávu, proto logaritmus o tomto základu, protože počet informovaných uzlů se v jednom kole bude zvětšovat o (d+1)-krát (d je kolik výstupních portů má každý uzel)
      • počet informovaných v každém kole bude řada: $(1)+(1+d)+(1+d+d(d+1))+\dots = \sum \limits _{i=1}^x (d+1)^i$
  • Optimální OAB ve výstupně-všeportových SF sítích
    • záplavovým algoritmem
  • SF OAB: 1-portové a d-portové sítě (kde d < všeportový)
    • binární logaritmus v dolní mezi u 1-portového (respektive u neúplného - u úplného grafu je to průměr grafu)
    • u stromu to nejde
    • obecně NP-úplný problém zjistit zda to jde
    • alg. rekurzivní zdvojování (RD):
      • rozdělí se graf na 2 poloviny, já jsem v jedné půlce a můj soused je ve druhé polovině.
      • pošle se to sousedovi a každý zvlášť ve své polovině to zopajeme
    • RD na EREW PRAM je vlastně jen otočené šipky jinak redukce: $\rho_{OAB}(EREW)=\lceil \log{p}\rceil$ - optimální
    • RD v hyperkrychli
      • 1-portový i všeportový jsou optimální (i pracovně)
  • Mřížky
    • Dimenzionálne usporádané kostry
    • dynamické usporádání smeru = FF - vybírám pořadí směrů na 1portu podle zbývajících velikostí v dané dimenzi
  • Toroidy
    • uzlově symetrické -> mřížkový algoritmus se zdrojem umísteným uprostřed mřížky.
• OAB v WH sítích
  • Ve spodních mezích odpadají ty excentricity (průměr) - redukuje se to jen na ty log
  • simulací hyperkubického RD OAB a tím dosáhneme spodní mez
  • ve všeportových sítích je to ale velmi složité dosáhnout (protože ten log je menší)
  • RD v 1-portových toroidech a mrížkách
    • rozdělí se to na 2 půlky (půlkružnice)
    • pošle se větší polovina (to je ale blbost - tím myslím pokud liché ;) tomu párovému
    • rekurzivně se to opakuje
    • dvě vlny (jedna jedním směrem, druhá druhým) - optimální
    • více dimenzí: nejdřív jednu dimenzi, pak druhou atd. (akorát pro hodně liché nebudu vždy splňovat že se to bude půlit v každém kroku)
  • Algoritmus dvojitého stromu ve všeportové hyperkrychli (DoubleTreeOAB)
    • rozešle do n směrů, přičemž v druhé polovině to skončí v doplňku současného uzlu
    • oba s v polovičkách udělají neúpný SBT
  • HoKaoOAB
    • v každém kroku vezmu každý informovaný uzel a k němu najdu n neinformovaných zbuduju k těm neinformovaným WH cestu a všichni najednou komunikaci provedou
    • potřebuju ale, aby cesty (kterých bude s mocninou přibývat) byly bezkonfliktní
    • Jednoduchá dimenzionálně rosoucí cesta: když vezmu cílovou a zdrojovou adresu, zXORuju je tak pozice té jedničky (může být jen jedna mezi dvěma) musí být stále rostoucí oproti předcházejícím XORům
    • pomocí e-cube směrování s porovnáváním bitu zleva doprava (tedy opačně než ta rostoucí cesta) pošlu právě do těch uzlů které byly spočítány pomocí jednoduché dimenzionálně rostoucí a pak ty cesty vytvořené e-cube směrováním jsou uzlově disjunktní
    • budu to dělat rekurzivně až do dimenze 6, tam začíná fungovat ten DoubleTreeOAB který na to také aplikuju
  • Všeportové mrížky a toroidy
    • velmi těžké se přiblížit spodní mezi: musí nalézt 2n neinformovaných a doručit jim packety po disjunktnich cestach v každém kroku
    • přístupy:
      • rekurzivní dělení
      • dominující množiny
      • zobecněná diagonála
        • rozdělím mřížku na 5 pásů a 4em pošlu informaci, rekurzivně opakuji (funguje to pro toroid - pro mřížky se to musí trochu ohnout) - ($\lceil \log_5{n} \rceil$ kol):
        • pošlu na diagonálu (tady ale posílám jen jedním portem (nevyužívám plně možností všeportovosti) (1 kolo)
        • teď dělím na diagonální pásy (na 5) a pošlu vždy do čtyř v jiném diagonálním pásu, rekurzivně opakuji ($\lceil \log_5{n} \rceil$)

MC

• řádově obtížnejší než OAB
• u SF se dají použít modifikace OAB, u WH ne
• 1-portové, fullduplexní, se standardním nejkratším směrováním tak následující úpravy RD pro MC fungují
• Hyperkrychle
  • podobné HoKaoOAB
  • dimenzionálně uspořádaný řetězec v hyperkrychli = lexikograficky seřazené podle uzlů kdy pořadí indukování e-cube směrováním
  • RD akorát že to lineární pole je natažené na té krychli (hranově disjunktní, ale nemusí být uzlově disjunktní)
• Mřížky
  • platí to velmi podobně jako u té hyperkrychle
  • dimenzinálně uspořádaný řetězec uzlu a ten rozpůlíme v 2D a v těch půlkách zase půlím atd.

OAS

• podobná složitost jako AAB
• Nekombinující
  • není tam shoda s broadcastem
  • každý packet právě jednoho adresáta
  • 1-portový = pošlu po kružnici (u SF nuté FF u WH není potřeba)
  • všeportový = stejně veliké podgrafy (a v nich to bude postupovat v nějakém stromu) a do každého budeme ládovat jeden packet v jednom kroku
  • konstrukce těch stromů (z kořene jdou vždy nejkratší cesty - dané hammingovou vzdáleností - vždy unitř toho podstromu)
    • vytvářím tabulku po řádcích - zasebe dávám řetězce podle počtu jedniček
    • některé řetězce budou asymetrické (mají jen některé rotace - vykrejou jen část řádku) a jiné symetrické (vykrejou celý řádek) a rozdělím to do prstenců (skupinky uzavřené vůči rotaci)
    • musím to dělat tak, aby všechny řetězce ve sloupci i měli v i-tém bitu 1 a zároveň aby měl řetězec vždy svého souseda někde nadsebou (liší se o 1 bit)
    • stromy budou sloupce
• Kombinující
  • podporují speciální službu pošty, že do obálky dám několik dopisů, pošlu to na nějakou vzdálenou poštu a tam to rozlepí a těch pět teprve odtamtud rozdistribuují lokálně
  • tohle se může dít na několika úrovních (z velkých dopisů se budou stávat menší dopisy)
  • v 1D mřížce je kombinující kontraproduktivní
  • rekurzivní zdvojování ci znásobování, podobne jako u OAB, jen si nechám tu větší půlku, protože jinak bych mu posílal 5 různých zpráv
  • na krychli: rekurzivní zdvojování s optimálním počtem kroků a časovou složitostí

AAB kombinující

• gossip = celková výmena (doslova: tlachy,drby)
• SF všeportový
  • fullduplex
    • spodní mez: $\rho_{AAB}(G) = \text{diam}(G)$
    • záplavový (lačný) -> potřeba větších pamětí
  • halfduplex
    1. simuluji fullduplex se zpožděním max 2 (rozložím v čase a posílám jednou toho a jednou toho)
       • spodní mez: $\text{diam}(G) \le \rho_{AAB}(G) \le \text{diam}(G)$
    2. Soustřeď-Rozešli
       • zvolen akumulátor, kterým se pomocí AOG (redukce) nashromáždí od všech ty zprávy
       • akumulátor rozešle nashromážděnou zprávu všem
       • velké množství redundance (ani NOHO, ani NODUP)
       • zpětné rozesílání i když běží po stejném stromu je delší, protože už posílám obrovskou úplnou zprávu
       • lze ale použít úplně kdykoli
    3. v bipartitních sítích
       • záplavový kde se ale střídají směry mezi 2ma stejnými skupinami (navzájem si posílají agregáty který už nashromáždily)
    4. silně zorientovaný graf
       • aby byl silně orientovaný = orientované hrany a aby vše bylo odkudkoli dostupné
       • zorientovat NP-úplný problém -> pro některé topologie vyřešeno:
         • pro 2-D mrížky a toroidy (tzv. Manhattanský problém) ale jen pro velké instance
         • hyperkrychle dimenze > 3
• SF 1-portový
  • 1D mřížky
    • jsem omezen zespoda spodní mezí Soustřeď-Rozešli pro OAB a zvrchu 2x horní mezí OAB
    • záplavový algoritmus: výměni mezi licho-sudými a sudo-lichými páry
  • 1D toroidy
    • když se sudou délkou tak to samé jako 1d mřížka
    • když s lichou délkou, tak jeden se zapojí až v druhém kroku, ale jen jedním směrem (zase je tam jeden který nekomunikuje)
    • informace původně nekomunikujícího se šíří se zpožděním dvou kroků
  • vícerozměrné mřížky
    • rozklad po dimenzích (horizontální a vertikální fáze)
    • akorát pořád boptná zpráva
  • hypekrychle
    • žádná neoptimalita, přesně se zdvojnásobují (AAB je to samé co all-to-all redukce)
    • vlastně velmi podobně jako u PPS na hyperkrychli (zelené registry jsou vlastně akumulovaná zpráva z AAB)

AAB nekombinující

• SF všeportový
  • z každého OAB stromu bude aktivní vždy jen jedna vrstva
  • časově-hranově-disjunktní stomy (TADT) když 2 uzly v daném kroku na dané úrovni nechtějí použít stejnou hranu.
  • kdyz jsou 2 OAB stromy TADT, tak bezkolizní přenos
  • uděláme hamiltonovskou kružnici a pošleme podel ní ty zprávy
  • 2-D a 3-D toroidy
    • 4 různé směry
    • aby se rotace nepřekrývaly
    • ParallelHamilCycleAAB
      • zkonstruují se 2 hranově disjunktní hammiltonovské kružnice
      • tím z toho uděláme vlastně toroid, každý uzel má i modrou i červenou
      • svojí zprávu rozpůlí a půlku pošle do červené a druhou půlku do modré
      • časová složitost je OK, ale počet stratupů je 2x než potřebujeme (kdyby zpráva byla malá, tak startup nepříjemně velký)
  • hyperkrychle
    • stejně jako u toroidů - musí být každá úroveň služená z n hran n směrů
    • inverzí i-té jedničky (i je sloupec) dostanu řetězec, který musí být v nějakém předchozím řádku (a který je předchůdce v tom stromě - musí být výše aby byl už informován)
• WH
  • na delší vzdálenosti
  • záleží na podmínkách (velikost zpráv, topologie atd.) jestli se to vyplatí nebo ne (někdy i na WH se používají předchozí alg.)
  • akumulace-broadcast
    • rozdělím na regiony (shluky, clustery) a vrámci nich si zvolíme reprezentanta, kterému pošleme všechno z daného regionu
    • jednotlivé regiony si prostřednictvím zástupců provedou úpnou výměnu mezi sebou (když si zvolím mocinu dvou počet regionů -> mohu použít simulaci na hyperkrychli v log čase)
    • reprezentanti to zase rozdistribuují v rámci regionu

AAS

• co se dá ovlivnit: počet startupů
• Spodní mez daná bisekční propustností
  • rozdělím na poloviny a spodní časová mez je daná těmi dvěma polovinami * délka a tm dělená bisekční šířkou
  • $\tau_{AAS}(G,\mu) = \rho_{AAS}(G)t_{s}+\frac{\lceil N/2\rceil \lfloor N/2\rfloor \mu t_m}{bw_e(G)}$
• hyperkrychle
  • standardní výměna (není obecně optimální)
• mřížky a toroidy
  • 1D poloduplexní
    • běhám kolem dokola, triviální cyklický pipeline je asymptoticky optimální (v každém kroku všechny hrany jsou využity)
    • 50% efektivnost protože běhám jen jedním směrem a někdy běžím delší cestou
    • WH nedává lepší řešení protože je potřeba časově multiplexovat ty cesty
    • horní mez: lineárně klesá velikost zprávy (každý si z ní odebere to co je pro něj)
  • 1D fullduplex
    • posílám oběma směry najednou
    • optimální, protože tady už jdou nejkratší cestou (půlkou průměru), a mají poloviční velikost
  • vícerozměrné
    • kombinování z různých dimenzí
• WH AAS s kombinováním paketů
  • hyperkrychle
    • když to $t_s$ bude dominovat,tak ten algoritmus je použitelný (je optimální)
  • 1-portové mřížky/toroidy
    • simulace binární výměny na krychli
    • využíváme kapacitu na 25% (proto ta 1/4 v horní mezi)
  • výměna mezi kvadranty
    • rozdělím na kvadranty a mezi kvadranty probíhá výměna takovým tím všediagonálním způsobem
    • to se dělá rekurzivně až na úroveň (2x2 - mikro AAS)
    • a tam si to pomocí třech operací přepošlu
• WH AAS bez kombinování paketů
  • AAS = sjednocení permutací (nebo posloupnost permutací tak že nedochází k duplikacím)
  • Přímá výměna (na hyperkrychly
    • permutace přeložení (XOR)
    • 50% efektivnosti
  • simulace předchozího algoritmu na mřížkách

Paralelní algoritmy pro lineární algebru

Maticové operace

• Proužkové mapování
  • blokově - řádky se rozdělí na souvislé p-tice
  • cyklicky - přidělování modulo
  • blokove-cyklicky - dostávají menší skupinky než při blokovém
  • převod blokově na cyklicky a opačně pomocí AAS, protože každý procesor musí všem ostatním předat nejméně jeden řádek
  • šachovnicové mapování - matice je rozdělena na submatice
• Transpozice
  • proužkové mapování - každý prvek bude potom patřit jinému procesoru (AAS)
  • šachovnicově mapovaná (mřížky)
    • SF -> permutace (vůbec žádné kolize - všichni postupují ve frontách k diagonále, tam se otočí o 90° a pokračují na své místo)
      • není škálovatelný (má komunikační režii > vlastní výpočet)
    • WH -> vybudování přímých cest najednou (XY smerování) -> kolize (když 2 procesory v jednom řádku na stejné straně diagonáli pošlou najednou) -> serializace
      • vždy můžeme najednou obsloužit 2 sloupce proti sobě
  • na hyperkrychli
    • nebudou tam kolize, pač máme řádově víc kanálů
    • rekurzivní algoritmus (máme dráty abychom ho dostali do správné čtvrtiny)
    • komunikační složitost je pořád složitější (i když řádově měnší než u mřížek) a teda pořád neškálovatelné
• Násobení matice vektorem
  • mapování po řádcích (na mřížce)
    • AAB pro poslání své části vektoru (složitost $T(N,p) =\Theta(\sqrt{N})$ závislá na topologii)
    • každý procesor vynásobí sekvenčně ti co má (složitost $T(N,p) = \Theta\left(\frac{N}{p}\right)$ nezávislá na topologii)
    • isoefektivni funkce: až do velikosti počtu řádků bude počet procesorů efektivní (víc nemá smysl, když mám mapování po řádcích)
  • mapování po sloupcích
    • každý procesor má zrovna ten sloupec, který je třeba vynásobit s tím svým kouskem vektoru (sekvenčně vynásobí svůj kousek se sloupcem)
    • redukce všichni se všemi (každý procesor má zodpovědnost za jeden redukční strom a zároveň krmí všechny ostatní stromy) = skoro úplně to samé jako AAB (akorát se tu musí ještě sčítat ty kousky)
    • řádově úplně to samé jako po řádcích
  • šachovnicové mapování
    • chceme aby byl výsledek byl uložen stejně jako velktor původní (v pravém sloupci)
    1. musíme rozdistribuovat tam kde ho bude potřebovat: první kus pošleme na diagonálu (i-tý bude potřeba v i-tém sloupci)
    2. v diagonále se rozhodí po celém sloupci (AAB v 1D mřížkách = sloupcích - tím se liší od té operace u mapování po řádcích - tady jsou to oddělené nezávislé sloupce)
    3. lokálně vynásobí submatici a subvektor
    4. redukce izolovaně v jednotlivých řádcích
• Násobení matice maticí
  • $p=mln$ (každý tedy udělá jedno násobení a pak udělají redukci) - naivní algoritmus
  • blokově šachovnicové mapování - není paměťově škálovatelný (časově je výborně)
  • Cannonův algoritmus
    • paměťově nenáročný (po celou dobu si vystačí s konstantní pamětí)
    • procesory fungují synchronně, data se přemisťují ve vlnách aby vždy ve správný okamžik dorazila na správný procesor (systolický algoritmus
      1. nejdřív si matice přehrabe
         • u A zpermutuje řádky - i-tý řádek se orotuje o i pozic doleva
         • u B zpermutuje sloupce - i-tý sloupec se orotuje o i pozic nahoru
      2. rozdělí teď na procesory submatice a díky přehrabání druhý index A souhlasí s prvním indexem B -> může lokálně násobit (výsledek uchovám v akumulátoru)
      3. orotuji - matici A doleva, B nahoru -> zase sedí ty indexy -> takže můžu zase násobit
      4. opakuje se to $\sqrt{p}$krát a pak už je to vše na správném místě vypočítané
    • isoefektivně jsem na tom stejně, ale paměťově na tom sakra lépe
  • Foxův algoritmus = Broadcast-Multiply-Roll (BMR)
    • necháme matici B tak jak je, ale nahrajeme jim takové kousky A aby mohli násobit (procesory v prvním řádku touží všechny po takovém kousku, který má první index nulový) - posílají se matice z hlavní diagonály všem na řádku
    • matice B posuneme nahoru a tedy posílím z druhé diagonály
    • má o nějakou konstantu větší paměťovou složitost (kromě své matice si musím pamatovat i to co mi příjde broadcastem)
    • časová složitost závisí na broadcastu, ale příliš se to nemění

Rešení soustavy lineárních rovnic (SLR)

• metody
  • přímé
    • gausovo eliminační schéma
  • nepřímé (iterativní)
    • pro řídké matice
  • gradientní
  • speciální
• Tridiagonální SLR a sudo-lichá redukce
  • viz také 36PAR_Paralelní_systémy_a_algoritmy#Aplikace_PPS
  • každou rovnici s proměnou liché proměnné vyjádřím
  • dosadím do rovnic se sudými indexy proměných dostanu výraz
  • tím zmenším počet rovnic na polovinu (paralelní redukce)
• Trojúhelníkové matice a zpetná substituce
  • matice (která má na diagonále nenulové prvky) * vektor neznámých = vektor konstant
  • namapované např po řádcích -> první procesor vypočítá neznámou a pošle jí OAB -> dalšímu výjde jedna neznámá atd.
  • $SU(n)=T(n,n)=O(n^2)$ protože to serializujeme
  • pokud bude broadcast rychlejší (WH, hyperkrychle) tak o maličko lepší $O(n\log{n})$ pořád ale nepoužitelné
  • $p \ll n$ (matice strašně obrovská a procesorů hodně malá)
    • cyklické mapování po řádcích (modulo mapování)
      • co rovnice, to jedno předání ostatním procesorům
      • $T(n,p) = nO(\log{p})+nO(\frac{n}{p})=$ n*broadcasty + n*výpočet jedné proměnné (což už je skoro lineární zrychlení protože $SU(n)=O(n^2)$
    • blokové mapování po řádcích
      • v rámci jednoho procesoru mohu vyřešit všech n/p rovnic a těch n/p pošlu všem ostatním a jeden se stane zase tím aktivním, který může už vyřešit
      • $T(n,p) = pO(\frac{n}{p}\log{p})+pO(\frac{n^2}{p^2})=$komunikace + výpočty = při mapování cyklicky
• Přímá metoda pro rešení SLR s více pravými stranami
  • LU dekompozice
    • rozložím matici na 2 trojúhelníkové
    • dopředná redukce - vypočítám vektor y
    • zpětná substituce - zpětně spočítám standardními maticovými operacemi
    • idea paralelní LU dekompozice
      • přirozená datová závislost kterou musím respektovat
      1. první rádek U totožný s prvním rádkem A
      2. první sloupec jsou součiny $u_{11}$ s jednotlivými l -> mohu spočítat první rádek matice L
      3. teď mohu dopočítat u koeficienty v druhém řádku (všechno k tomu už znám)
      4. mohu spočítat druhý sloupec
      • takto postupuju řádek modré, sloupec červené atd.
      • optimální mapování: Blokově-cyklicky šachovnicové mapování
• Nepřímé (iterační) metody
  • nejsou vždy stabilní (ne vždycky to vyjde)
  • dosadím vždy nějaké řešení a zjistím jestli jsem už spokojen (mám nějakou normu)
  • pokud ještě nejsem spokojen, tak dosadím poupravené řešení (opravil jsem ho nějak v návaznosti na tom jak to předtím nevyšlo)
    • Jakobi
      • novou generaci hodnot počítám tak, že dosadím do i-té rovnice všechny hodnoty z předchozí generace za všechny proměnné (kromě té i-té samozřejmě, aby mi tam zbyla jedna proměnná)
      • ideální pro paralelizaci
      • redukce
      • boadcast (toho zbytkového vektoru = residuální)
    • Gaus-Seidel
      • vezmu staré hodnoty za i-tou proměnnou, ale nové hodnoty před i-tou proměnnou (před diagonálou)
      • tohle numericky konverguje rychleji
      • není to moc dobře paralelizovatelné, protože je tam datová závislost
      • Diskretizace
        • metoda konecných diferencí
        • metoda konecných prvku (FEM)
      • vysoce paralelní alg
      • očíslujeme jinak - potřebuje jen bezprostřední sousedy, tak to uděláme tak, aby byli v jiné generaci -> parita indexů
    • superrelaxace
      • bere to ještě nejaký průměr předchozích hodnot
      • z hlediska parallelizace to není tak moc důležité