PRL Final Exam

2019-2020-extract

4 min čtení

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

Př. 1

PRAM tipovačka, měla tři části:

urči asymptotickou časovou složitost EREW nějakého algoritmu
urči cenu CREW nějakého (jiného) algoritmu
učit asymptotickou časovou složitost common CRCW nějakého (jiného) algoritmu

Řešení:

Casova zlozitost sucinu prvkov postupnosti

  • EREW PRAM log n

Cena OR postupnosti

  • CREW PRAM n*log n

Casova zlozitost unsorted
ch

  • CRCW PRAM n/N

Př. 2

VLIW - popsat, obrázek

Řešení:

[obrazek: image46]

[obrazek: image47]

Př. 3

Monitor - popsat, hlavně signal a wait, obrázek

Řešení:

[obrazek: image48]
[obrazek: image49]
[obrazek: image26]

Př. 4

Broadcasty - dva obrázky jako ze slajdů, měli jsme určit jestli splňují FIFO, kauzalitu, atomičnost a jednu vlastnost si vybrat, opravit a nakreslit vedle znovu

Řešení:

PS co je kauzalita
[obrazek: image50]

Př. 5

OCCAM - popsat, primitiva, obrázek

Řešení:

[obrazek: image51]
Primitiva
[obrazek: image52]

Př. 6

Stromy - to jsem úplně nepochopil co přesně mám dělat, ale asi napsat algoritmus pro preorder, když máme funkci suffix a cesty uloženy ve struktuře Etour + popsat a složitost

Řešení:

[obrazek: image53]

Př. 7

Random mating - použít na příkladu, aby skončil ve 4 krocích

Řešení:

[obrazek: image54]Richa
kdyztak me opravte, ale pohlavi F a M volim nahodne (spici procesor uz nemeni pohlavi). Jakmile narazim na sekvenci F→M, tak F procesor zmeni svou hodnotu na val[i] + val[succ[i]] a naslednika uspim, poznacim si poradi, ve kterem jsem ho uspal.
Pokracuju, dokud prvni prvek neukazuje na posledni a potom prichazi na radu rekonstrukci faze, kdy probouzim procesory v opacnem poradi a jestli neukazuji na konec listu, tak provedu korekci val[i] = val[i] + val[succ[i]]. Abychom splnili pozadovany pocet kroku, musime zvolit F a M spravne xD

Př. 8

MPI - počet prvků, jejichž hodnota byla větší než průměrná

Ř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);

bool largerThanAvg = buf > avg;
buf = largerThanAvg ? 1 : 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();

ANO: 0x
NE: 0x

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

Př. 1

I cena alg ktory zoradi,
II cena ktory zisti ci je nejaky zhodny,
III casova zlozitost algoritmu ktory spocita AND?

Řešení:

Př. 2

Zretazene procesory

Řešení:

Př. 3

Kod producent konzument

Řešení:

Př. 4

euler suffix sum

Řešení:

Př. 5

Broadcast

Řešení:

Př. 6

Prescan (upsweep, downsweep)

Řešení:

Př. 7

Linda - zadefinovat synchronizaciu alebo vylucenie

Řešení:

Př. 8

MPI (reduce, broadcast) c++ - 16 prvkov zistit ci su aspon 2 rozne - logaritmicka casova zložitosť

Řešení:

MPI_Init(&argc, &argv);

int rank,size,max,min;
bool hasTwoDiffValues;

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

MPI_Reduce(&buf,&max,1,MPI_INT,MPI_MAX,0,MPI_COMM_WORLD);
MPI_Reduce(&buf,&min,1,MPI_INT,MPI_MIN,0,MPI_COMM_WORLD);

if (rank == 0) {
hasTwoDiffValues = max != min;
std::cout << hasTwoDiffValues << std::endl;s
}

MPI_Finalize();

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

Př. 1

PRAM ako na každom termíne

Řešení:

Př. 2

Xeon Phi - architektúra

Řešení:

Kombinace SIMD a MIMD
[obrazek: image23]

Př. 3

Odd-even merge sort - popis algoritmu, sieť 4x4

Řešení:

Př. 4

Marzullo algoritmus - popis algoritmu, ukázať na príklade

Řešení:

[obrazek: image55]

Př. 5

CLA - podrobný postup ako sa sčítajú 2 čísla

Řešení:

Př. 6

Obyčajný semafór - príkazy, princíp

Řešení:

[obrazek: image56]
[obrazek: image57]

  • Synchronizačný nástroj poskytovaný OS, ktorý nevyžaduje aktívne čakanie (busy waiting)
  • semafor S je premenná typu Int ku ktorej (okrem inicializácie) sa môže pristupovať len cez 2 atomické a vzájomne exkluzívne operácie P(S) a V(S)
  • aby sa predišlo aktívnemu čakaniu - ak musí proces čakať, je uložený do fronty blokovaných procesov čakajúcich na rovnakú akciu
  • v skutočnosti je teda semafor štruktúra, obsahujúca celočíselnú premennú a FIFO frontu blokovaných procesov
    [obrazek: image58]
    [obrazek: image59]
  • S.count musí byť inicializované na nezápornú hodnotu
  • Ked je S.count >= 0 tak udáva počet procesov, ktoré môžu použiť P(S) bez toho aby boli zablokované
  • Ked je S.count < 0 tak udáva počet procesov ktoré čakajú na semafor
  • telá funkcií P(S) a V(S) sú kritické sekcie - 2 procesy nemôžu byť súčasne v oboch

Př. 7

LINDA

Řešení:

[obrazek: image60]
[obrazek: image61]

Př. 8

MPI - priemer čísel väčších ako priemer všetkých

Ř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);

bool largerThanAvg = buf > avg;
int cntBuf;
buf = largerThanAvg ? buf : 0;
cntBuf = largerThanAvg ? 1 : 0;

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

if (rank == 0) {
avg = double(sum) / double(cntSum);
std::cout << avg << std::endl;
}
MPI_Finalize();

Pre 2018/19 a staršie pozri druhý doc, link na 1. strane v materiáloch

Graf

Příchozí odkazy