PRL Final Exam

2020-2021-extract

9 min čtení

Semestrálna skúška 2020/2021 - riadny termín

Př. 1

cena XOR

  • casova zlozitost OR
  • cena suctu? maxima a minima

Řešení:

[podle toho jak to bylo v minulych letech, overte mi prosim]

  • cas XOR
    • EREW log n
    • CREW log n
    • Common CRCW log n
  • cena sum
    • EREW n*log n
    • CREW n*log n
    • Common CRCW n*log n
  • cena max/min
    • EREW n*log n
    • CREW n*log n
    • Common CRCW n*log n

+2

Př. 2

Operace testAndSet
[asi jde o semafor?]
[Nope. Semafory jsou uz reseni vzajemneho vylouceni bez aktivniho cekani. Tady jde o zpusob, kdy ve while proces, ktery ceka na kritickou sekci, testuje testAndSet(&lock) porad dokola, viz prezentace Vzajemne vylouceni]

Řešení:

  • inštrukcia, ktorá niečo otestuje a výsledkom je hodnota 0/1 na nejakej adrese v pamäti
  • je to atomická inštrukcia, teda otestuje a rovno nastaví hodnotu na 1
  • riešenie pre dva procesy:
  • proces chce vstúpiť do kritickej sekcie
  1. procesy zdieľajú hodnotu lock, ktorá je na začiatku 0 (odomknuté)
  2. ak na testandset narazil prvý proces:
  • test vráti z lock 0 (je odomknutý)
  • set nastaví lock = 1
  • vstúpi do kritickej sekcie
  1. lock je potom atomicky zamknutý a proces je v kritickej sekcii
  2. ak chce pristúpiť do kritickej sekcie ďalší proces:
  • test vráti z lock 1 (je zamknutý)
  • set nastaví lock = 1
  • čaká v smyčke while na uvolnenie zámku
  1. ak prvý proces opustí kritickú sekciu, nastaví lock = 0 (odomkne zámok)
  2. druhý proces môže vstúpiť do kritickej sekcie

Př. 3

kauzalita

Řešení:

[obrazek: image44]

Př. 4

Euler tah -suffix?

Řešení:

Př. 5

R-A

Řešení:

Algoritmus Ricart-Agrawala
– Jedná se o optimalizaci Lamportova algoritmu

Př. 6

Euler strom/graf?

Řešení:

Př. 7

Carry look ahead add - spocitat 39 a 110
r

Řešení:

  1. Prevest do bin

    1. 39: 00100111
    2. 110: 01101110

  2. Spočítať pole di pomoci a. b. kde di \in {propagate, generate, stop}

    1. if xi 1 and yi 1 → di = g // nevadi co prislo zhora, vzdu bude carry
    2. if xi 0 and yi 0 → di = s // nevadi co prislo zhora, nikdy nebude carry
    3. else di = p // carry zavisi na tom, co prijde zhora

    Pro nas priklad

x : 0 0 1 0 0 1 1 1 y : 0 1 1 0 1 1 1 0
d : s p g s p g g p // initialni vector

  1. Pocitam co bude v dalsim kroku, aktulani di <tecka v kolecku> di-1 (pro prvni hodntu di-1 = s - neutralni prvek)
    osa X: to bylo pred tim (di-1)
    osa Y: co je v init vectoru (di)
    [obrazek: image45]

x : 0 0 1 0 0 1 1 1 y : 0 1 1 0 1 1 1 0
d : s p g s p g g p
d’: s g g s g g g s s

  1. Pocitame carry bit - pokud je s/p → nasledujici carry bit ja 0, jinak 1

x : 0 0 1 0 0 1 1 1 y : 0 1 1 0 1 1 1 0
d : s p g s p g g p
d’: s g g s g g g s s
c : 1 1 0 1 1 1 0 0

  1. Delam summu xi + yi + ci

x : 0 0 1 0 0 1 1 1 y : 0 1 1 0 1 1 1 0
d : s p g s p g g p
d’: s g g s g g g s s
c : 1 1 0 1 1 1 0 0
z : 1 0 0 1 0 1 0 1 == 149

Overte me prosim vas
+2

Př. 8

naprogramovat s log zlozitostou sucet hodnot vacsich nez priemer

Ř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 sum;//jiz definovany vyse
MPI_Reduce(&buf,&sum,1,MPI_INT,MPI_SUM,0,MPI_COMM_WORLD);
if (rank == 0) std::cout << sum << std::endl;

MPI_Finalize();

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

Př. 1

PRAM složitosti,

Řešení:

Př. 2

PRAM architektura (popis+obrazek) ,

Řešení:

Př. 3

Pi kalkul (redukce+pozorování),

Řešení:

Př. 4

Random mating(příklad),

Řešení:

Př. 5

Suzuki (princip+obrazek 4 uzly),

Řešení:

Př. 6

Monitor(popsat wait/signal, obrázek),

Řešení:

  • je to high-level jazyková konštrukcia, ktorá poskytuje rovnakú funkcionalitu ako semafory, ale je jednoduchší na použitie
  • môže byť implementovaný pomocou semaforov
  • je to softvérový modul ktorý obsahuje:
    • jednu alebo viac procedúr
    • inicializačnú sekvenciu
    • lokálne premenné
  • charakteristiky:
    • lokálne premenné sú prístupné len procedúram monitoru
    • proces vstúpi do monitoru tým že zavolá jednu z jeho procedúr
    • len 1 proces môže byť v monitore v jednom čase
    • pre každú podmienkovú premennú obsahuje vnútornú frontu
    • naviac má jednu urgentnú frontu
  • monitor nám zaručuje vzájomné vylúčenie (mutual exclusion) a nepotrebujeme ho pritom naprogramovať ručne, čiže naše zdieľané dáta sú chránené ak ich umiestnime do monitoru
  • Condition variables
    • sú prístupné len z monitoru
    • môže sa k ním pristúpiť len z týchto 2 funkcí:
      • wait(a) - blokuje vykonanie volajúceho procesu na podmienke a
        - proces môže pokračovať len ak iný proces zavolá signal(a)
      • signal(a) - vzbudí pokračovanie vykonávania nejakého procesu, ktorý čaká na podmienku a

[obrazek: image25]
[obrazek: image26]

Př. 7

Linda ( reverz seznamu)

Řešení:

TID id, prev, next;
int val;

rd(“list”, “head”, ?id);
in(“list”, id, ?next, ?val);
out(“list”, id, NULL, val);
prev = id;
id = next;

while(id != NULL) {
 in(“list”, id, ?next, ?val);
 out(“list”, id, prev, val);

 prev = id;
 id = next;
}
out(“list”, “head”, prev);

— netreba sa este zbavit original headu?
— cize pred poslednym riadkom:
— in(“list”, “head”, ?id);

Př. 8

MPI ( součet čísel větších jak průměr)

Řešení:

Semestrálna skúška 2020/2021 - 2. opravný termín

Př. 1

PRAM tipovačka

Řešení:

Př. 2

VLIW + ako sa riešia konflikty

Řešení:

Př. 3

Monitor - popis + obrázok

Řešení:

  • je to high-level jazyková konštrukcia, ktorá poskytuje rovnakú funkcionalitu ako semafory, ale je jednoduchší na použitie
  • môže byť implementovaný pomocou semaforov
  • je to softvérový modul ktorý obsahuje:
    • jednu alebo viac procedúr
    • inicializačnú sekvenciu
    • lokálne premenné
  • charakteristiky:
    • lokálne premenné sú prístupné len procedúram monitoru
    • proces vstúpi do monitoru tým že zavolá jednu z jeho procedúr
    • len 1 proces môže byť v monitore v jednom čase
    • pre každú podmienkovú premennú obsahuje vnútornú frontu
    • naviac má jednu urgentnú frontu
  • monitor nám zaručuje vzájomné vylúčenie (mutual exclusion) a nepotrebujeme ho pritom naprogramovať ručne, čiže naše zdieľané dáta sú chránené ak ich umiestnime do monitoru
  • Condition variables
    • sú prístupné len z monitoru
    • môže sa k ním pristúpiť len z týchto 2 funkcí:
      • wait(a) - blokuje vykonanie volajúceho procesu na podmienke a
        - proces môže pokračovať len ak iný proces zavolá signal(a)
      • signal(a) - vzbudí pokračovanie vykonávania nejakého procesu, ktorý čaká na podmienku a

[obrazek: image25]
[obrazek: image26]

Př. 4

Problém 5 filozofov - kód so semaformi + popis ako to funguje (plus musel byt deadlock proof ten kód)

Řešení:

Jde o úlohu, kde 5 filosofů/procesů v náhodných chvílích buď přemýšlí, žádají o vidličku nebo jedí. Pokud chce filosof jíst, musí získat 2 sdílené zdroje/vidličky, kdy jedna je od něj vlevo a druhá vpravo. Zároveň jsou vidličky ale sdílené se sousedními filosofy. Řešení, kde je ošetřena možnost uváznutí:

semaphore E;
fork = array[0..4] of semaphore;

initialize:
E.count = 4; //porusime cyklickou ozavislost (viz Coffmanovy podminky), nechame jist pouze 4 z 5 filosofu
for i=0..4 {fork[i] = 1;} //jen jeden proces muze danou vidlicku v jednu chvili vlastnit
filosof:
repeat
think;
P(E);
P(fork[i]); //leva vidlicka - kdo to v tom nevidi, necht si nakresli stul s 5 procesy okolo a 5 vidlicek
//nutne si indexy nakreslit proti smeru hodinovych rucicek a kazda leva vidlicka bude mit
//dany index procesu
P(fork[i+1 mod 5]); //prava vidlicka
eat;
V(fork[i+1 mod 5]);
V(fork[i]);
V(E);
forever

Př. 5

Nieco s FIFO a broadcastom, nejaká random tabuľka, v živote som to nevidel

Řešení:

Př. 6

Random mating (pravdepodobne 1:1 recycle z 1. opravného)

Řešení:

Př. 7

OCCAM - naprogramovanie procedúry AVG, ktorá má tri kanály typu BYTE a to DATA, CHNH, CHNL. Procedúra berie čísla z kanálu DATA, počíta z nich dlhodobý priemer, a podľa toho či číslo, ktoré prišlo je väčšie alebo menšie ako priemer tak ho pošle príslušnému kanálu. (nepísal však ktorému tak som predpokladal, že CHNH je pre väčšie čísla a ten druhý je pre menšie alebo rovné (ale tá rovnosť nebola explicitne zmienená)).

Řešení:

Pomocí různých jiných řešení jsem se to pokusil splácat, ale netuším jestli to je dobře, tak je na vás jestli tomu chcete věřit, možná by nad SEQ mělo být WHILE TRUE, idk:

PROC avg(CHAN OF BYTE DATA, CHNH, CHNL)
INT counter := 0
INT sum := 0
INT value :
INT avg :
SEQ
counter := counter + 1
DATA ? value

    sum := sum \+ value  
    avg := sum/counter  
    IF  
        value \<= avg  
            CHNL \! value  
        value \> avg  
            CHNH \! value

Já bych udělal paralelní sekci pro výpočet meanu a pro výstup, což by taky znamenalo, že aktuální hodnota by se nepočítala do dlouhodobého průměru při rozhodování, na který výstup se hodnota pošle. Možná to i dává větší smysl, říct, zda je hodnota větší nebo menší než dosavadní průměr a až potom upravit ten průměr.z

Př. 8

MPI - “spočítať sumu menších čísiel v postupnosti ako je jej minimum” ⇐ potom sa na upozornenie opravil a povedal, že si máme zvoliť menších ako maximum alebo väčších ako minimum

Ř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
int max;

MPI_Reduce(&buf,&max,1,MPI_INT,MPI_MAX,0,MPI_COMM_WORLD); // root process receives max → this value need to be sent to all other processes

MPI_Bcast(&max, 1, MPI_INT, 0, MPI_COMM_WORLD);

int val = buf < max ? buf : 0 ;
int sum;
MPI_Reduce(&val,&sum,1,MPI_INT,MPI_SUM,0,MPI_COMM_WORLD);
if (rank == 0) std::cout << sum << std::endl;

MPI_Finalize();

Myslím, že MPI_Reduce a MPI_Bcast mohou být nahrazeny MPI_Allreduce.
Ale v zadani je uvedeno (ne tady, ale v originalnim) ze muzeme pouzit jenom cMPI_Reduce a MPI_Bcast

Graf

Příchozí odkazy