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

Ad blocker interference detected!


Wikia is a free-to-use site that makes money from advertising. We have a modified experience for viewers using ad blockers

Wikia is not accessible if you’ve made further modifications. Remove the custom ad blocker rule(s) and the page will load as expected.

V síti Wikia

Náhodná Wiki