PRL Final Exam

2018-2019-extract

10 min čtení

Semestrálna skúška 2018/2019 - riadny termín - skupina A

Zadanie je prepísané doslovne 1:1

Př. 1 (6b)

Odpověď na příklady 1-3 musí být provedena zakroužkováním správné volby v tomto zadání (odpovědi na přiloženém papíře nebudou hodnoceny). Možnosti odpovědí pro příklady 1 až 3 jsou následující:
a) konstantní
b) logaritmická
c) n.log n
d) lineární
e) kvadratická
f) polynomiální

  1. mějme výpočetní model PRAM s N procesory. Jaká bude cena optimálního algoritmu, který spočte AND prvků 1/0 v posloupnosti n prvků (pro n=N) v případě:
    1. EREW PRAM
    2. CREW PRAM
    3. common CRCW PRAM
  2. mějme výpočetní model PRAM s N procesory. Jaká bude cena optimálního algoritmu, který zjistí, zdali se v posloupnosti n prvků (pro n=N) nachází alespoň dva rozdílné (tedy že není posloupností stejných prvků) v případě:
    1. EREW PRAM
    2. CREW PRAM
    3. common CRCW PRAM
  3. mějme výpočetní model PRAM s N procesory. Jaká bude časová složitost optimálního algoritmu, který spočte průměrnou hodnotu posloupnosti n prvků (pro n=N) v případě:
    1. EREW PRAM
    2. CREW PRAM
    3. common CRCW PRAM

Řešení:

  1. AND
    1. c) n log n
    2. c) n log n
    3. d) linearni
  2. nachází alespoň dva rozdílné
    1. c) n log n
    2. c) n log n
    3. d) linearni
  3. Prumer
    1. b) logaritmická
    2. b) logaritmická
    3. b) logaritmická

ANO: 1x
NE: 0x (V 2. nemalo by to byť hľadanie maxima a minima a potom porovnanie? Čiže v odpovedi common CRCW PRAM by malo byť 2 * (n * log(n)) = n log n
–tady není nutné hledat max/min, stačí když:

  1. každý procesor si vezme jednu hodnotu O(1)
  2. např. procesor s rank == 0 umístí svoji hodnotu do sdílené paměti O(1)
  3. každý procesor si tu hodnotu natáhne a porovná se svojí O(1)
  4. pokud nějaký procesor má různé hodnoty, tak tu informaci někam zapíše a jelikož těchto procesorů může být víc tak u CREW by to byl problém, ale tady to bude v O(1)

–takže cena = n)

Př. 2 (9b)

Uveďte, na jakých úrovních lze spatřovat granularity paralelismu. jednotlivé úrovně stručně popište z hlediska paralelizace.

Řešení:

[prednaska PDA0102_Arch_MNG stranka 21 slajd 40]

  • Uvnitr instrukci
    • Nejjemnejsi paralelismus
    • Programator nema nad tim kontrolu a nejsou viditelne pro programatora
    • Pri vykonaní inst-ci nektere akce se provadeji paralelne
  • Mezi instrukci
    • Nektere inst-ci se provadeji paralelne, ale neni to videt na urovni prog jazyka
    • Typicke zretezeni u RISC
  • Mezi prikazy
    • Vektorove pocitace
    • Specializovane koprocesory (FPU)
    • Programátor ma nad tim urcitou kontrolu
  • Mezi bloky procesu (vlakna, thready)
    • predpoklada se ze mame sdileny adresovy prostor a vytvoreni noveho vlaklna skoro zadarmo
    • Programator muze to ovlivnovat
  • Mezi procesy
    • zpravidla nemaji sdilenou pamet
    • Muzou byt kompilovane oddelene

Př. 3 (9b)

Uveďte algoritmicky Odd-Even transposition sort a odvoďte jeho cenu.

Řešení:

[obrazek: image62]
[obrazek: image63]

Př. 4 (9b)

Uveďte, k čemu u Meakawova algoritmu slouží kvóra, co musí splňovat a jak se určují pro nějakou množinu procesů. Názorně ilustrujte obrázkem

<i v prednaskach algos je uplne na picu vysvetlen, takze nvm>

Řešení:

Kvórum, definice, účel: podmnožina procesů o velikosti alespoň odmocniny celkového počtu procesů. Každé 2 kvóra musí mít alespoń jeden společný proces

Kvórum, alg. nalezení: pro n procesorů, kde n = a^2 | a ∈ ℕ, jinak nějaké matematické metody.. ale asi by se pro menší počet procesorů dalo určit nějak iterativně na zkoušce
[obrazek: image64]
Obr:

Př. 5 (9b)

Paralelní procesy zapsané níže v jazyce Π kalkulu redukujte všemi možnými způsoby. V každé fázi redukce včetně původního zápisu uveďte, pokud existují, jaká pozorování platí (např. ↓x, ↓neg(z) atd.)[obrazek: image65]

Řešení:

[obrazek: image66]

src: https://discord.com/channels/461541385204400138/621775635722928128/840993532240068608
pár drobností - ak je samotná 0 v procese, nepíše sa
na konci v zadaní je P’ (P s čiarkou), pričom tá čiarka sa od oranžového riadku stratila, pozor na to
nestratili sa tam niekde < a >? viem, že sme neprišli na to, ako sa s nimi pracuje, ale minimálne zapísané by byť mali, nie?
v zelenom výsledku je neg(a) (c), pričom c by nemalo byť v zátvorke

Př. 6 (9b)

Pro graf G=(V, E), V = {v1, v2, v3, v4, v5, v6} a E = {e1, …, e14},
e1 = (v3, v6), e2 = (v6, v3),
e3 = (v5, v3), e4 = (v3, v5),
e5 = (v1, v2), e6 = (v2, v1),
e7 = (v3, v4), e8 = (v4, v3),
e9 = (v1, v3), e10 = (v3, v1),
e11 = (v4, v5), e12 = (v5, v4),
e13 = (v4, v6), e14 = (v6, v4),
demonstrujte názorně paralelní výpočet Eulerova tahu.

Řešení:

[obrazek: image67]

[obrazek: image68]

Př. 7 (9b)

Algoritmem Carry Look Ahead Parallel Binary Adder proveďte součet čísel 90 a 139. Názorně demonstrujte jednotlivé kroky. Musí být jasné, jak celý proces sčítání probíhá.

Řešení:

[obrazek: image69]

Př. 8 (10b)

Naprogramujte paralelní algoritmus v jazyce C++ s pomocí knihovni MPI, který bude mít logaritmickou časovou složitost a který provede součet čísel posloupnosti, která jsou větší než její průměr. K dispozici máte knihovní funkcie v podobě:
MPI_Bcast (adresa_hodnoty, root)
MPI_Reduce (adresa_send, adresa_recv, operace, root).
Každý proces má hodnotu prvku posloupnosti na pozici svého ranku uloženou v proměnné value. Také má uložen celkový počet procesorů v proměnné numprocs a svůj rank v proměnné rank. Výsledek je vypsán na obrazovku.

Řešení:

MPI_Init(&argc, &argv);

int rank,size,sum;
MPI_Comm_rank(MPI_COMM_WORLD, &rank);
MPI_Comm_size(MPI_COMM_WORLD, &size);
int buf=(rank*1234)%33; //“random” data

MPI_Reduce(&buf,&sum,1,MPI_INT,MPI_SUM,0,MPI_COMM_WORLD);

double avg;
if (rank == 0) avg = (double)sum / (double)size;
MPI_Bcast(&avg,1,MPI_DOUBLE,0,MPI_COMM_WORLD);

buf = buf > avg ? buf : 0;

int cnt;
MPI_Reduce(&buf,&cnt,1,MPI_INT,MPI_SUM,0,MPI_COMM_WORLD);
if (rank == 0) std::cout << cnt << std::endl;
MPI_Finalize();

Semestrálna skúška 2018/2019 - riadny termín - skupina B

Př. 1

PRAM otazky

Cena OR postupnosti
Cena reverzacie postupnosti
Casova zlozitost sucinu prvkov postupnosti

Řešení:

Cena OR postupnosti

  • EREW PRAM n*log n
  • CREW PRAM n*log n
  • common CRCW PRAM n

Cena reverzacie postupnosti

  • EREW PRAM ???
  • CREW PRAM ???
  • common CRCW PRAM ???

Casova zlozitost sucinu prvkov postupnosti

  • EREW PRAM log n (cena n log n, pozor, na co se ptají)
  • CREW PRAM log n
  • common CRCW PRAM log n

Reverse neni to stajne co serazeni? → stejna cena jako u serazeni by bylo

Řešení:

PRAM - Parallel Random Access Machine

Př. 2

Popisat architekturu PRAM + obrazok

  • synchrónny model paralelneho vypoctu, procesory komunikujú zdielanou pamatou

  • skladá sa z p procesorov RAM

  • Pamäť (sada registrov):

    • neobmedzený počet

  • Je to alternetívny model k paralelnému Turingovmu stroju

  • Všetky RAMy sú riadené jedným spoločným programom
    [obrazek: image70]

  • Definicia :

    • PRAM je synchrónny model paralelného výpočtu, v ktorom procesory komunikujú zdieľanou pamäťou. Skladá sa z p procesorov P1…Pn, ktoré sú typu RAM.

    • Výpočet prebieha po krokoch synchrónne: 1. čítanie zdieľanej pamäte

      2. lokálny zápis

      3. zápis do zdieľanej pamäte

Obmedzenie prístupu k zdieľanej pameti

  • 4 rôzne architektúry prístupu pamäti:
    • EREW - exclusive read, exclusive write
    • ERCW - exclusive read, concurrent write - nepoužíva sa
    • CREW - concurrent read, exclusive write
    • CRCW - concurrent read, concurrent write - spĺňajú len niektoré architektury

Př. 3

Popisat Paralell splitting + uviest mensi priklad

Řešení:

-mam trosku problem pochopit o co tu ide, z prednasky mi to nie je jasne, ma sa rozdelit nezoradena postupnost a skoncit rozdelena nezoradeno? napr. 3,5,1,9,2,10
rozdelime podla m=5 na L = 3,1,2; E = 5 a G = 9,10? akeby sme mali 3 procesory tak kazdy si vezme 2 cisla, urobi si LEG a potom ich spoji do kopy hej?

  • jeho ulohou je rozdelit postupnost S podla cisla m na 3 casti:
    • L = {si € S: si < m}
    • E = {si € S: si = m}
    • G = {si € S: si > m}
  • Po tom co se vytvoří se vypočítá, kam mají procesory ukládat své výsledné posloupnosti (suma prefixů), aby mohly ukládat současně a nemusely čekat, než budou uloženy všechny předchozí hodnoty.
  • u sekvencneho algoritmu mame zlozitost O(n)

[obrazek: image71][obrazek: image72]

Př. 4

Popisat princip Suzuki algoritmus. Nakreslit obrazok na priklad: Mame styri procesory (uzly), jeden, ktory nema token, ziada o KS. (Tri mensie obrazky)

Řešení:

-token aj procesy obsahuju vektor, pri tokene to označuje kolkokrát bol token ktorému procesu prideleny, pri procese to označuje koľkokrát zažiadal o token
-ak chce proces vstúpiť do KS, odošle ostatńym procesom správu s číslom, ktoré udáva koľkikrát o KS žiada. Procesy si hodnotu upravia ak je nižšia než ta čo prišla, následne proces ktorý ma token odošle danému procesu token, daný proces ak obdrží token zvýši hodnotu v jeho čítači
- ak žiadaju o token viaceré procesy, tak je odoslaný tomu ktorý je prvý vo fronte, podľa nejakého kritéria
[obrazek: image73][obrazek: image74]

Př. 5

Pi kalkul - redukovat vyraz a napisat pozorovania

Řešení:

Př. 6

Random mating demonstrovat na 8 prvkoch, tak aby algo skoncil v 4 krokoch. Obe faze.

Řešení:

Př. 7

CLA scitacka. 77 + 125. Popisat vsetko potrebne.

Řešení:

[obrazek: image75][obrazek: image76]
ako sa ziska ten posledny riadok Z??? xi + yi + ci (mod 2) je to *binarni* scitani, tim padem zadny (mod 2) ⇐ lol, student MITu
Ako sa prosim vypočítal ten riadok C a ten riadok s kruzkom nad nim?
To je suma prefixů daného operátoru ˚ pro CLA, nosič {p, g, s}, p neutrální prvek, s a g levě agresivní. Symbol g generuje 1 ve vyšším bitu, s generuje 0 ve vyšším bitu, p propaguje současný bit výše.

Př. 8

MPI - Zistit pocet prvkov, ktore su maximami alebo minimami.

Řešení:

[obrazek: image77]

Semestrálna skúška 2018/2019 - riadny termín - skupina C

Př. 1

PRAM otazky
pro kazdou otazku byly 3 podotazky jak je to u EREW, CREW a common CRCW
1a) časová zložitosť operácie XOR
1b) cena kontroly či daná postupnosť je monotónna
1c) časová zložitosť súčtu absolútnych hodnôt prvkov postupnosti

Řešení:

1a) časová zložitosť operácie XOR

  • EREW PRAM log n
  • CREW PRAM log n
  • common CRCW PRAM log n

1b) cena neceho
1c)časová zložitosť súčtu absolútnych hodnôt prvkov postupnosti

  • EREW PRAM log n
  • CREW PRAM log n
  • common CRCW PRAM log n

tymto si niesom ista, je to len z mojej hlavy, riesime len sucet hodnot, lebo absolutnu hodnotu si urobi kazdy procesor sam za konstantny cas

Př. 2

Popsat architekturu zretezenych procesoru + nakres

Řešení:

  • lineárne prepojené procesory
  • riešenie úloh s prúdovým charakterom
  • data prechádzajú postupne jednotlivými procesormi
    [obrazek: image78]
  • v prednaskach je aj tento obrazok, nejde vsak o zretazenie instrukcii a nie procesorov? ved zretazene instrukcie sa daju vykonavat na 1 procesore nie?
    [obrazek: image79]

Př. 3

Popsat odd-even merge + nakresliť chceli všeobecnú schému a sieť 4x4 pomocou CE blokov

Řešení:

  • každý procesor má 2 výstupné a 2 vstupné kanály
  • každý procesor porovná hodnoty na svojich vstupoch a menší dá na výstup L(Low) a väčší na výstup H (High)

[obrazek: image36]
[obrazek: image80]

Př. 4

Popsat Marzullo algoritmus, okrem popísania bol aj príklad podobný prednáškam

Řešení:

- NTP používa marzullov alg. na stanovenie času z líšiacich sa odpovedí časových serverov

[obrazek: image81][obrazek: image82]

Př. 5

Pi kalkul - redukovat vyraz a napisat pozorovania

Řešení:

Př. 6

zadané nejaké prvky, spraviť prescan - napísať výsledok po prvom kroku a po skončení upsweep, potom výsledok po prvom kroku a po skončení downsweep (za predpokladu že na začiatku downsweepu bol vložený už neutrálny prvok na poslednú pozíciu)

Řešení:

  1. UpSweep - každému uzlu sa priradí súčet jeho synov

  2. DownSweep : a) koreňu sa priradí neutrálny prvok

    b) ďalej dá každý uzol:

    — svoju pravému synovi: svoju hodnotu ⊕ hodnotu Laveho syna

    — svojmu lavemu synovi: svoju hodnotu

    - krok b) sa prevedie postupne pre každú úroveň (teda log n krat) a robí sa paralelne v každej úrovni

[obrazek: image83]
[obrazek: image84]
Príklad na preskúšanie:
prvky : 5, 1, 6, 10, 3, 8, 2, 4
Riesenie:d
[obrazek: image85]
Imo je v UpSweep chyba a měl by končit číslem 39 (Reduce všech čísel s operací plus→ 22+17) +1 DownSweep mi vyšel stejně +1

Př. 7

CLA scitacka. 77 + 125. Popisat vsetko potrebne.

Řešení:

SPř. 8

MPI - pocet prvku, ktere jsou bezezbytku delitelne prvnim prvkem, k dispozici pouze mpi_bcast a mpi_reduce, požadovali logaritmickú časovú zložitosť

Řešení:

odstrihol si ze:
int prvok0 = value; //inak to spadne,lebo budeme porovnavat nedef.
[obrazek: image86]

Semestrálna skúška 2018/2019 - 1. opravný termín

pre 1. op a starsie roky check druhy doc:
https://docs.google.com/document/d/18PI10fxMBaaUFgexU52Kk_WHQrSrq5VgpGcA9IKfcvY/edit#heading=h.swp6u0hxje7b

Graf

Příchozí odkazy