Fandom

Education

Příklady paralelním architekturám a modelům

429pages on
this wiki
Add New Page
Talk0 Share

Body: 1Edit

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

ŘešeníEdit

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ů: 2Edit

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

ZadáníEdit

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íEdit

Přeskok ukazatelů, viz. slajd

Bodů: 3Edit

PRAM post order cislovani stromuEdit

Zadání:Edit

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

ŘešeníEdit

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

PRAM, procesory s nezavislou pam a arit. jednotkouEdit

ZadáníEdit

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

ŘešeníEdit

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

Simulace Prioritni-CRCW na EREWEdit

ZadáníEdit

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íEdit

viz slajdy 20-26.

Algoritmus vypoctu hloubky uzlu na EREW PRAMEdit

ZadáníEdit

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íEdit

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

Bodů: 4Edit

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

ZadáníEdit

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íEdit

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

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

ZadáníEdit

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

ŘešeníEdit

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

Bodů: 5Edit

cenove optimalni APRAM alg. pro paralelni redukciEdit

ZadáníEdit

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íEdit

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

Provest PPS na APRAMEdit

ZadáníEdit

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ámkaEdit

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

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.