FANDOM


Body: 1Editovat

Common CRCW a Arbitrary CRCW. Ktery je silnejsi a proc?Editovat

ŘešeníEditovat

Lemma 2. PRIORITY (prioritní) > ARBITRARY (náhodný) > COMMON (shodný) > CREW > EREW. Arbitrary je silnější než Common, protože algoritmy, které předpokládají, že počítač dovolí zapsat jen pokud jsou všechny hodnoty stejné (jinak končí v nedefinovaném stavu -> programátor nesmí dovolit aby došlo k zápisu do jedné buňky sdílené paměti pokud různé hodnoty) tak ve stejném čase a bez jakékoli změny budou tyto algoritmy fungovat na systému který zapíše náhodně vybranou hodnotu. Opačně to fungovat nebude a kdybychom chtěli spustit algoritmus napsaný pro Arbitrary na Common, museli bychom již provádět simulaci silnějšího na slabším.

Bodů: 2Editovat

Výpočet pořadí od konce v zřetězeném seznamu na CREWEditovat

ZadáníEditovat

Popište časově optimální paralelní algoritmus pro výpočet pořadí od konce (rank) prvků ve zřetězeném seznamu o velikosti n na počítači CREW PRAM s n procesory. Vstupem algoritmu je zřetězený seznam ve sdílené paměti PRAM reprezentován pomocí pole následníků $ S[1, \dots ,n] $.

ŘešeníEditovat

Přeskok ukazatelů, viz. slajd

Bodů: 3Editovat

PRAM post order cislovani stromuEditovat

Zadání:Editovat

  • napsat (optimální?) algoritmus
  • $ p < n, T(n,p) $

ŘešeníEditovat

1) Mám seznam uzlů a seznam hran.
Převedu na oboustranně orientovaný graf, označím si dopředné a zpětné hrany O(n/p), přidám hodnocení hran.
2) Vytvořím Eulerovu kružnici (skripta 108), O(n/p)
3) Vytvořím Eulerovu cestu - rozpojím kružnici v počátku O(1)
4) Zpětné hrany ohodnotím 1, dopředné 0.
5) Aplikuji PPS na vytvořené pole.
6) Ohodnocení uzlu=ohodnocení hrany z něj vedoucí

PRAM, procesory s nezavislou pam a arit. jednotkouEditovat

ZadáníEditovat

Popsat APRAM NC alg. pro paralel. prefix. soucet n cisel pomoci binarni asociativni operace *, T, C a psicka?

ŘešeníEditovat

pokud ho máš, tak sem s ním!

Simulace Prioritni-CRCW na EREWEditovat

ZadáníEditovat

Popiste a vysvetlete polylogaritmicky slozitou simulaci jednoho kroku Prioritni-CRCW-PRAM(n,p) algoritmu S na EREW-PRAM(n+O(p),) pocitaci. Predpokladejte jednotkovy casovy model, kdy R, W a L trvaji cas 1.

ŘešeníEditovat

viz slajdy 20-26.

Algoritmus vypoctu hloubky uzlu na EREW PRAMEditovat

ZadáníEditovat

Popiste EREW PRAM alg. pro vypocet hloubky uzlu eulerovskeho stromu T o n uzlech, kdy koren ma hloubku 0. Vysledkem bude pole Level[1,...,n]. Eulerovsky strom T ma m = 2n-2 hran a je reprezentovan polem uzlu, ktere maji odkazy na cyklicke seznamy svych hran. Predpokladejte, ze jiz je zkonstruovana eulerovska cesta vznikla pri pruchodu T do hloubky a je ulozena v poli EA[1,...,m], kde EA[i] je i-ta hrana teto cesty.

Odvodte paralelni cas T(n,p), jestlize lokalni operace L i globalni R/W trvaji cas 1.

ŘešeníEditovat

Ze zadani vyplyva, ze mame jiz vytvorene pole nasledniku a z nich ziskane informace o rank (poradi) jednotlivych hran. Tato informace (rank) je ulozena pro kazdou hranu v Eulerovske ceste vznikle rozseknutim Eulerovske kruznice.

1) Zjisteni orientace hran (Kazdy CPU nad kazdou hranou se podiva na antiparalelni dvojce a podle hodnoty rank se urci smer hrany)
2) Kazde dopredne hrane se nastavi priznak na 1, zpetne hrane na -1
3) Pomoci PPS se provede soucet a kazdy bude mit nastavenou hodnotu urovne ve stromu


Bodů: 4Editovat

urcete p' a t' u PRAMu (m,p')Editovat

ZadáníEditovat

Odvodte pocet procesoru p‘ a casovou slozitost t‘ simulace PRAM(n,p) algoritmu s casem t = T(n,p) na PRAM (m,p‘) pocitaci tehoz typu, je-li m < n. Tuto simulaci popiste. Jake dalsi predpoklady jsou treba? Uvazujte jednotkovy casovy model, kdy operace R,W a L trvaji cas 1.

ŘešeníEditovat

viz predmaska 3/slajd 19

Určení pořadí v řetězeném seznamu pro PRAMEditovat

ZadáníEditovat

alg. pro urceni poradi v zretezenem seznamu pro EREW-PRAM s p=n, jakou ma skalovatelnost? napiste alg. pro p<n

ŘešeníEditovat

pokud ho máš, tak sem s ním!

Bodů: 5Editovat

Kolektivní komunikační operaceEditovat

Společné zadáni: Odvoďte spodní meze počtu kroků $ \rho _{XXX} $ a a komunikační zpoždění $ \tau _{XXX} $ pro danou operaci XXX na síti s červím přepínáním (WH). Zdrojový uzel vysílá packet o velikosti m. Přenos packetu o velikosti μ na vzdálenost d trvá čas $ t(d,\mu) = t_s + d t_d + \mu t_m $

Popište co nejefektivnější algoritmus. Odvodte co nejpresneji pocet kroku $ r_ {XXX} $ a komunikacni zpozdeni $ t_{XXX} $ a porovnanim se spodnimi mezemi XXX urcete optimalni algoritmus.

OASEditovat

  • T(Z,Z), vseportovy, WH
  • Kombinujici 2-portovy 2D toroid K(z1,z2) s WH prepinanim. Zdroj uzel [a1,a2], 0<= a1 < z1 a pro kazdy uzel ma pripraveny paket o velikosti m. (zde je ještě potřeba spočítat paralelní součet délek použitých cest $ g_{OAS} $ a jeho spodní mez $ \gamma_{OAS} $)
  • 1-port WH 2D mrizka M(z1, z2), zdroj vysilani na [a1, a2] ma pro kazdy uzel pripravenu zpravu o velikosti M.

AASEditovat

  • Qn
    • Nekombinující, nebo v případě že $ t_s \ll /mu t_m $ použít nekombinující algoritmus (skripta 190)
    • Pro případ že $ t_s \ge /mu t_m $ v kombinující síti použít standartní výměnu (SV) ze str. 187
  • 1-portová mřížka $ M(\sqrt{p},\sqrt{p}) $
    • Slidy 11/26
    • kvadrantová výměna (skripta 189)
    • binární výměna (skripta 189)

OABEditovat

  • 2 portová 2D mřížka M(z1,z2)
  • 2 portová 1D mřížka
  • všeportový 2D toroid
    • zde je ještě potřeba spočítat paralelní součet délek použitých cest $ g_{OAS} $ a jeho spodní mez $ \gamma_{OAS} $
    • zobecněná diagonála, viz skripta str. 177

cenove optimalni APRAM alg. pro paralelni redukciEditovat

ZadáníEditovat

Standartni model APRAM (lokalni operace trvaji cas 1, k>=1 krat za sebou jdouci R/W trva k+d-1; a barierova synchronizace $ B(p)=\alpha d \log{p} $, kde $ \alpha $ a d > 1) ma nezavislou pametovou a vypocetni jednotku. Popiste cenove optimalni APRAM alg. pro paralelni redukci n cisel pomoci binarni asociativni operace @ (puntik ;-).

Odvodte T(n,p), C(n,p), $ \psi _1(p) $, $ \psi _2(n) $. Analyzu casove slozitosti provedte pro model dynamicke barierove synchronizace.

ŘešeníEditovat

Řešení je popsané podrobně na stránkách předmětu, zde je výtah:

Postup AEditovat

Pro efektivní simulaci PRAM algoritmu s $ p_p $ procesory na APRAM počítači je potřeba řádově snížit počet procesorů z $ p_a $ na $ p'_a = \tfrac{p_p}{B(p_p)} $. Víme, že p-procesorový PRAM algoritmus pro paralelní redukci nad polem n hodnotje časově i cenově optimální, pokud $ p = \Theta (\tfrac{n}{\log{n}}) $. Položme pro jednoduchost $ p_p = \tfrac{n}{\log{n}} $.

Pro optimální počet procesorů $ p'_a $ pro APRAM redukci platí:

$ p'_a = \dfrac{p_p}{B(p_p)} = \cfrac{\tfrac{n}{\log{n}}}{\alpha d \log{(\tfrac{n}{\log{n}})}} = \dfrac{n}{\alpha d \log{n} (\log{n} - \log{\log{n}})} \dot= \dfrac{n}{\alpha d \log^2{n}} $

V první fázi výpočtu každý APRAM procesor zredkuje sekvence $ n/p'_a = \alpha d \log^2{n} = \beta $ čísel. Z předpokladu pro nezávislou pamětovou a aritmetickou jednotku plyne, že zatímco se z paměti pomocí R načítají hodnoty, aritmetická jednotka je okamžitě redukuje na mezivýsledky. Pak je složitost první fáze rovna $ T_a^I(n,p'_a ) = d+ \beta - 1 + 1 \dot= \beta $.

Druhá fáze začíná bariérou, pak se zapíšou lokální výsledky první fáze, znovu bariéra a pak se provede APRAM redukce $ p'_a $ čísel na $ p'_a $ procesorech:

$ T_a^{II}(n,p'_a ) \dot= B(p'_a) + d + B(p'_a) + 2B(p'_a)\log{p'_a} \dot= 2B(p'_a)\log{p'_a} \le 2 \beta $
.

pozn. - podle mého by tam mělo ještě někde být d...

Výraz $ 2B(p'_a)\log{p'_a} $ předpokládá, že se v každém kroku účastní všech $ p'_a $ procesorů. Při dynamické bariérové synchronizaci ale počet procesorů exponenciálne klesá, takže čas spotřenovaný na dynamickou bariérovou synchronizaci je

$ t_{BS} = 2( B(p'_a) + B(\dfrac{p'_a}{2}) + B(\dfrac{p'_a}{2^2}) + \cdots + B(2)) $
$ t_{BS} = \alpha d \log{p'_a}(log{p'_a}+1) \dot= \alpha d \log^2{p'_a} \le \beta $

Celkový čas je $ T_a(n, p'_a) = T_a^{I}(n,p'_a ) + T_a^{II}(n,p'_a ) \le 2 \beta $.

Celková cena je $ C_a(n, p'_a) = p'_a T_a(n, p'_a) = \dfrac{n}{\beta} \times 2\beta = 2n $

Postup BEditovat

Sekvence APRAM redukce n čísel na $ p_a $ procesorech je

$ \left \langle R \left \langle RL \right \rangle ^{\tfrac{n}{p_a}-1} B W B \left \langle R R L B W B \right \rangle ^{\log{p_a}} \right \rangle $
$ T_a(n,p_a) = d + \left ( \frac{n}{p_a} - 1 \right ) + 1 + B(p_a) + \log{p_a}(d + 1 + 1 + B(p_a) + d + B(p_a)) $

Po sečtení, zaokrouhlení a započtení dynamické bariérové synchronizace (viz předchozí)dostáváme

$ T_a(n,p_a) = \frac{n}{p_a} + 2 d \log{p_a} + 2B(p_a)\log{p_a} \dot= \frac{n}{p_a} + \alpha d \log^2{p_a} $
$ C_a(n,p_a) = n + \alpha d p_a \log^2{p_a} $

Protože $ SU(n) \dot= n $ má rovnice $ E(n,p_a) = \tfrac{n}{n + \alpha d p_a \log^2{p_a}} = E_0 $ řešení:

$ n = \frac{E_0 \alpha d}{1 - E_0} p_a \log^2{p_a} $ a $ p_a \dot= \frac{\gamma n}{\log^2{\gamma n}} $, kde $ \gamma = \frac{1 - E_0}{E_0 \alpha d} $

Paralelní prefixový součet (PPS)Editovat

APRAMEditovat

Melo to byt pro p < n procesoru, takze vlastni vypocet slozitosti mel sekvencni a paralelni cast. Ta paralelni pak vypadala $ \langle RRLBWB\rangle ^{\log{p}} $. Z toho zjistit T(n,p) dosazenim za R,L,W,B, vypocitat C(n,p), Psi1, Psi2.

PoznámkaEditovat

APRAM pocitac postupuje stejne jako PRAM pocitac, akorat se musi prokladat barierama

Ostatní modelyEditovat

T, E , ψ1, ψ2, ψ3, Tmin

  • 2D toroid
  • Qn ($ n = \log{p} $), WH přepínání.
    • algoritmus se zelenými a žlutými registry
  • škálovatelnost v (hyperkub.?) síti v případě že každý procesor má n/p hodnot (možná je to dohromady s předchozím zadáním)

Lineární algebraEditovat

LU dekompoziceEditovat

JakobiEditovat

Sudo lichá redukceEditovat

Třídění / řazeníEditovat

3D sortEditovat

QuicksortEditovat

Bitonic mergesort (BMS)Editovat

Snakelike řazeníEditovat

Odvoďte výraz pro netriviální spodní mez na počet kroků hadovitého (snake-like) paralelního řazení $ n^2 $ čísel pomocí operace Porovnej&Vyměn (CE) na 2-D mřížce $ M(n,n) $.

ShearsortEditovat

MaticeEditovat

Cannonův algoritmus násobení maticEditovat

Foxův algoritmus násobení matic (BMR)Editovat

Popište a vysvětlete Foxův algoritmus paralelního násobení čtvercových $ \sqrt{N} \times \sqrt{N} $ matic $ C = AB $ na vše-portové hyperkrychli $ Q_{\log{p}} $ procesorů, kde $ p < N $.

Odvoďte co nejpřesnější výraz pro paralelní čas $ T(N,p) $, jestliže

  1. směrovače provádění červí (WH) prepínání packetů, kde přenos packetu o velikosti μ mezi 2 uzly ve vzdálenosti d trvá $ t(d,\mu) = t_s + d t_d + \mu t_m $
  2. prvky matic mají velikost m a
  3. sekvenční lokální nasobení dvou matic o velikosti $ r \times r $ trvá čas $ \alpha r^3 $, kde m a α jsou konstanty.

Pro zadanou efektivnost E0 odvoďte izoefektivní funkce $ \psi_1(p) $ a $ \psi_2(N) $. Odvoďte minimální čas a spodní mez počtu procesorů $ \psi_3(N) $ pro dosažení asymptoticky minimálního času.

Násobení matice x vektorEditovat

OstatníEditovat

  • na oBFn dokazte, ze pro dane vstupy a1..an kde a1<a2<..<an a vystupy b1..bn kde b1<..<bn a zobrazeni PI(ai)=bi, ktere je monotonni je bezkolizni. Shit