Semestrálna skúška 2021/2022 - riadny termín - skupina A

Př. 1

Pram tipovačka, nepamätám sa presne na zadanie,
proste sa nauč toto

Řešení:

[obrazek: image14]

Př. 2

Test and set

Ř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

procesy zdieľajú hodnotu lock, ktorá je na začiatku 0 (odomknuté)
ak na testandset narazil prvý proces:

test vráti z lock 0 (je odomknutý)
set nastaví lock = 1
vstúpi do kritickej sekcie

lock je potom atomicky zamknutý a proces je v kritickej sekcii
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

ak prvý proces opustí kritickú sekciu, nastaví lock = 0 (odomkne zámok)
druhý proces môže vstúpiť do kritickej sekcie

Př. 3

etour a suffixsum - určení úrovně uzlu ve stromu

Řešení:

[obrazek: image15]

Př. 4 а

Pipeline merge sort (neviem ci priklad ci teoria tak tu hodim teoriu + nejaky priklad

Řešení:

linearne pole procesorov p(n) = log n + 1
cisla nie su ulozene v procesoroch ale postupne do nich vstupuju
kazdy procesor spaja 2 zoradene postupnosti dlzky 2^(i-2)
[obrazek: image16]

Analyza:

procesor Pi zacne ked ma na jednom vstupe postupnost dlzky 2^(i-2) a na druhom 1, teda zacne 2^(i-2)+1 cyklov po procesore Pi-1
n + 2^r + r -1 = 2n + log n -1 cyklov = t(n) = O(n)
c(n) = O(n)*O(log n +1) = O(n*log n) → je optimalny

Priklad:
[obrazek: image17]

Př. 5

Zretazene processory MISD

Řešení:

lineárne prepojené procesory
riešenie úloh s prúdovým charakterom
data prechádzajú postupne jednotlivými procesormi
[obrazek: image18]

Př. 6

Asynchronna komunikacia na synchronnu ci je mozne

Řešení:

Skupina C pr. 5

Př. 7

OCCAM priklad ale netusim aky, bol som C - Neco s polem jako “buffer” (jak se v OCCAM kurva delaji pole?) kam ti chodi prvky z jednoho channelu a v ten moment co ti ten buffer zacina pretykat nebo kdyz ti prijde 0 tak mas vzit prvek ktery je v tom poli nejdyl a ten poslat na “high” output channel pokud je to cislo vetsi nez nejaky threshhold nebo na “low” output channel kdyz mensi nebo rovno (takze jsi dostal 3 channely a jedno cislo - ten threshhold - na vstup te procedury ci jak se to vola)

Řešení:x

Př. 8

MPI priklad ale netusim aky, bol som C - Neco EZ kde stacilo jen zavolat 2x reduce - tusim ze kazdy procesor u z mel nejakou svoji hodnotu (stejne tak rank i size jsi mel v nejakych promennych uz predem) a mel jsi vypsat jestli je suma tech hodnot delitelna maximem (nebo minimem?) tech hodnot? (reduce i broadcast meli zjednodusene argumenty v zadani jeste k tomu)

Řešení:

int max,sum;
MPI_REDUCE(val,max,MPI_INT,MPI_MAX,0); //root proces dostane max pres reduce
MPI_REDUCE(val,sum,MPI_INT,MPI_SUM,0); //root proces dostane sum pres reduce

if (rank == 0) {
if (sum % max == 0) std::cout << “Je delitelno bez zbytku” << std::endl;
else std::cout << “Neni lol” << std::endl;
}

Semestrálna skúška 2021/2022 - riadny termín - skupina B

Př. 1

PRAM tipsport

Řešení:

pozri skupinu A Pr.1

Př. 2

Vektorové procesory SIMD + obrázek

Řešení:

jediný program counter (PC)
dokážu zrýchliť niektoré výpočty za cenu pomerne málo procesorov
Výhody:
- jednoduchší než MIMD
- menšie nároky na pamäť
- jeden inšt. tok a synchronizácia zjednodušuje programy
- odpadá réžia so zložitou synchron. medzi procesmi, ktorá je u MIMD
- rýchlejšia komunikácia medzi procesormi než u MIMD
Nevýhody:
- Nie všetky problémy sú dátovo paralelizovateľné
- pokles výkonnosti u programov s veľa podmienenými skokmi
- nie sú vhodné pri malom počte procesorov
- vyžadujú nie úplne bežné procesory

[obrazek: image19][obrazek: image20]
UMA (uniform memory access) NUMA (non uniform mem. acc.)

Př. 3

Paralelní select K-teho prvku z posloupnosti S. Princip + demonstrace (neviem kde najst demo)

Řešení:

hlada k-ty najmensi prvok v postupnosti S
EREW PRAM s N procesormi
pouziva zdielane pole M o N prvkoch
časová zložitosť je optimálna, teda koľkokrát zvýšime počet procesorov, toľkokrát sa algoritmus zrýchli
t(n) = O(n/N) pre n>4, N < n / log n
p(n) = N
c(n) = O(n) → je optimalnyS

Př. 4

Peterson algoritmus + pseudokód

Řešení:

rieši mutual exclusion
každý proces sa dostane na rad do kritickej sekcie
ak proces chce vstupiť do krit. sekcie, nastaví svoj flag a musí počkať kým príde na rad
P1 navštívi kritickú sekciu aspoň po jednej návšteve P0 (už keď je P0 chytený vo while cykle), nemôže sa teda stať že P1 bude stále predbiehať P0 alebo naopak, zabráni sa tým hladoveniu

Pseudokód:

zapichne svoju vlajočku a dá prednosť druhému
pokiaľ má oponent zapichnutú vlajku a turn je jeho, tak sa čaká
ak bojojú o kritickú sekciu:
1. obaja majú zapichnutú vlajku
2. obaja si dajú navzájom prednosť
3. ale turn má len jeden z nich (buď i alebo j)
ten, ktorý má turn vstúpi do krit. sekcie
po skončení si vezme vlajku
ten čo čakal už nepozerá na turn, do krit. sekcie sa dostane pretože oponent si zobral vlajku

shared var flag: array [0..1] of boolean; //flagy žádosti o vstup do kritické sekce
turn: 0..1; // označení aktuálního kola

repeat
flag[i] := true; // Proces žádá o krit. sekci
turn := j; // Proces nastaví kolo na druhý proces
while (flag[j] and turn=j) do skip; // Čeká kym je kolo druhého procesu a žádá o krit. sekci
<critical section>
flag[i] := false; // Po dokončení krit. sekce proces stáhne žádost o krit sekci
<remainder section>
until false;

Př. 5

Synchronizácia (novinka tento rok)

Řešení:

Př. 6

Enumeration sort napísať X,Y,C,Z po skončení algo aka bol priklad aky neviem ale tu je nejaký na ukážku

Řešení:

lineárne pole n procesorov
majú spoločnú zbernicu, ktorá je schopná preniesť v každom kroku 1 hodnotu
cena nie je optimálna O(n) = n
Priklad:

[obrazek: image21][obrazek: image22]

Př. 7

OCCAM shit
Jestli si matně vybavuju tak na OCCAM tam bylo něco ve smyslu, že mám proceduru co má na vstupu array 10 channelů a vstupy adr a in, všechno BYTE. Když na vstup adr příjde něco, tak inkrementuju channel modulo 10. Když přijde na in něco tak to pošlu na aktuálně nastavený channel.

z toho co je napisane a kodu by som povedal ze je to to iste co 2021/22 1. opravny skup B pr 7

Řešení:

PROC name([10] CHAN OF BYTE channels, CHAN OF BYTE adr,in)
outAdr := 0
WHILE TRUE
ALT
adr ? x
outAdr := outAdr + 1
IF
outAdr > 9
outAdr := 0
TRUE
SKIP
in ? y
channels[outAdr] ! y

Př. 8

MPI: Pokud max % min == 0, pak vypiš “Ano”, jinak vypiš “Ne”.

Řešení:

Volani Reduce je mozna spatne, v te otazce byla hlavicka definovana, tak se to akorat trochu upravi
int rank,val; //bylo zadano, ze kazdy procesor ma svuj rank a hodnotu
⁹
int max,min;
MPI_REDUCE(val,max,MPI_INT,MPI_MAX,0); //root proces dostane max pres reduce
MPI_REDUCE(val,min,MPI_INT,MPI_MIN,0); //root proces dosatne min pres reduce

if (rank == 0) {
if (max % min == 0) std::cout << “Min a max jsou delitelne bezezbytku” << std::endl;
else std::cout << “Min a max nejsou delitelne bezezbytku” << std::endl;
}

Semestrálna skúška 2021/2022 - riadny termín - skupina C

Př. 1

PRAM tipsport extraliga

Řešení:

skupina A Pr. 1

Př. 2

XEON popisat + obrazok (nie, nerobim si srandu, vazne to tam dal -_-) WTF +54

Řešení:

kombinácia SIMD + MIMD

[obrazek: image23]

Př. 3

Mám etour a suffixsum, zistiť koľko je nasledujúcich vrcholov v strome + popísať princíp + určiť časovú náročnosť

Řešení:[obrazek: image24]

analýza

spočítanie Etour O(c)
inicializácia wieght O(c)
výpočet suffixSums O(log n)
korekcia výsledku O(c)li

t(n)=O(log n)
c(n)=závisi od implementácie suffixSums

Př. 4

Monitor popísať (aj wait a signal) + 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 variablesm
- 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ř. 5

asynchronní signály a určit zda jdou předkládat tak aby šly volat synchrone
vypadlo to nějak takto cca
[obrazek: image27]

Řešení:

Musíme zjistit, zda v asynchronním systému existuje koruna. Pokud koruna neexistuje, je systém proveditelný synchronně. Pro každý proces si vypíšeme všechny události, které jsou v relaci kauzality: -e>. A pak se v nich snažíme najít cyklus aka korunu.

1. Proces = (1,4)

2. Proces = (2,3)

3. Proces = (3,5)

[obrazek: image28]4. Proces = (4,1)

5. Proces = (5,6)

6. Proces = (2,6)

Koruna v tam je velikosti 2: (1,4) → (4,1) ⇒ systém nelze provést synchronně.

Př. 6

Príklad na prescan, zoradiť 16 čísel (ukážkový príklad z minulého roku na pochopenie princípu)

Řešení:

prvky : 5, 1, 6, 10, 3, 8, 2, 4
[obrazek: image29]
pozn.: bylo to potřeba zapsat jako pole tj vědět které číslo v tom poli se má přepsat

Př. 7

OCCAM mám ebo in, keď mi do adr príde 1-10 tak nastavím aktívny index na to číslo ináč 0, keď do in niečo príde tak to vložím na aktívny channel

Řešení:

Př. 8

MPI počet prvkov rovnakých ako max a rovnakých ako min v log čase

Řešení:

[obrazek: image30]

Semestrálna skúška 2021/2022 - 1. opravný - skupina A

Př. 1

popísať Algo na CRCW pre AND a uviesť príklad

Řešení:

Tým, že každý z procesorov má pridelenú hodnotu a jedná sa o operáciu AND, stačí aby každý procesor skontroloval, či je jeho hodnota 0 a ak áno, poslal správu hlavnému procesoru (resp. zapísal hodnotu 0 do jeho pamäte). Výsledkom je potom hodnota hlavného procesoru.
[obrazek: image31]
niečo také asi, všetky procesory sa naraz pozrú na svoju hodnotu, proc P3 má hodnotu 0 teda pošle správu hlavnému procesoru P1 a teda celý AND je FALSE

Př. 2

kde by sme využili MIMD, popísať + obrázok

Řešení:

Xeon phi I guess ako kombinácia SIMD a MIMD
[obrazek: image23]

MIMD: Multiple Instruction Multiple Data

zreťazené MIMD
ostatné MIMD - so spoločnou zbernicou, s prepojovacou sieťou, so pevnou sieťou
multiprocesory - tesné viazanie typicky cez zdieľanú pamäť
multicomputery - voľnejšie viazanie typicky cez predávanie správ

Př. 3

suffixsum pre euler path výpočet úrovne vrcholu

Řešení:

úroveň vrcholu je najkratšia vzdialenosť medzi koreňom a vrcholom
daná rozdielom počtu spätných a dopredných hrán na zvyšku Eulerovej cesty od vrcholu
algo:

inicializácia poľa váh: dopredná = -1, spätná = +1
suffix sum na poľom váh
korekcia: cez všetky dopredné hrany sa spočíta úroveň vrcholu v
```
 váha hrany \+1   
```

level(v) = weight(e) + 1, e = (u,v)
[obrazek: image32]

Př. 4

ako budú vyzerať procesory v 12. Kroku pri pipeline sort

Řešení:

nepamätám si zadanie ale bolo tam tuším, že 8 čísel a 4 procesory
pozri si nejaký príklad nech vieš ako sa to robí napr. riadny termín 2021/22, skupina A pr. 4

Př. 5

async → sync či sa dá, ak ano tak ako, kde to vidime atď. ak nie preco a popisat relaciu kauzality
[obrazek: image33]

Řešení:

nie je to možné, vzniká tam koruna o veľkosti 4 medzi prvými 4. procesmi
proces 1 : (S1, R4)
proces 2: (S2, R3)
proces 3: (S3, R1)
proces 4: (S4, R2)
koruna: (S1, R4) → (S4, R2) → (S2, R3) → (S3, R1)

relácia kauzality →

hovoríme, že a kauzálne predchádza b keď jeden proces vykonal tieto udalosti v tomto poradí a → b
broadcast vysielanie a doručenie je v relácii kauzality: send(msg) → deliver(msg)
relácia je tranzitívna

Př. 6

FIFO algoritmy

Řešení:

niesom si úplne istý ale asi chcel tieto dva ?

Lampartov alg.
- procesy se snaží shodnout na tom, ktorý z nich získa kritickú sekciu
- založené na FIFO doručovaní správ
- udržuje lokálnu prioritnú frontu správ, v ktorej priority sú úplne usporiadané podľa predávaných časových razítok
Ricart - Agrawala alg.
- vylepšenie Lampartova alg., vyžaduje len 2(n-1) správ (Lampart 3(n-1) )
- zlučuje správy, odpovede a uvoľnenia dohromady
- synchronizačné oneskorenie je opäť len 1 zaslaná správa

Př. 7

OCCAM chanelly ls,gt,in potom BYTE th ako vstup, vytvorit pole o veľkosti SIZE malo byť že [0..SIZE-1] po in prijať x ak má buffer (pole) miesto a x != 0 tak to uloží do poľa ak miesto nieje alebo x == 0 AND x ⇐ th potom ls ! x a ak x == 0 AND x > th potom gt ! x

Řešení:

Př. 8

MPI nájsť či suma prvkov v 1. Polovici je Broadcastmenšia ako suma prvkov v 2. Vypísať áno alebo nie

Řešení:

[obrazek: image34]
Alebo
[obrazek: image35]

Semestrálna skúška 2021/2022 - 1. opravný - skupina B

Př. 1

Udělat AND pro common CRCW. Popsat princip + příklad

Řešení:

2021/22 1.opr skupina A pr. 1

Př. 2

Xeon Phi Popsat + obrázek (dostal jsem 8b za ten architekturní se skalar, vect jednotkou, cache,… takže chtěl asi ten)

Řešení:

kombinácia SIMD a MIMD
32 512-bitových vektorových registrov
[obrazek: image23]

Př. 3

Odd Even merge sort + ještě nakreslit tu síť 4x4 s použitím CE porovnávaček

Řešení:

princíp je spájanie dvoch zoradených postupností
špeciálna sieť procesorov, základný stavebný kameň je procesorový element CE = sieť 1x1
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: image37]

Př. 4

Marzullův alg

Řešení:

NTP (Network Time Protocol) používa Marzullov alg. na stanovenie času líšiacich sa odpovedí časových serverov
pre množinu intervalov, hľadáme najmenší interval s najväčším počtom prienikov
Alg:

zoraď intervaly podľa offsetov začiatkov a koncov intervalov. Počiatočné okamžiky označ ci =1 a koncové ci = -1
best = 0, count = 0
urob sumu prefixov, teda postupne pre každý offset i od najnižšej hodnoty po najväčšiu urob count += ci

if count > best then best = count

[obrazek: image38]

Př. 5

async → sync či sa dá, ak ano tak ako, kde to vidime atď. ak nie preco a popisat relaciu kauzality. Dá se synchronizovat? Pokud ano uvést jak. Pokud ne, uvést jak se to dá detekovat, co se tam nachází a které konkrétní zprávy tomu zabraňují
[obrazek: image39]

Řešení:

2021/22 1.opr skupina A, pr. 5

Př. 6

Enumeration Sort (predpokladam ze pole a chcel priklad nie algo)

Řešení:

lineárne pole n procesorov so spoločnou zbernicou, v jednom kroku prenesie max 1 hodnotu
procesory majú 4 registre:
- Xi - prvok xi, dostane sa do procesoru cez zbernicu
- Yi - postupne prvky x1..xn, presuvaju sa lineárnym prepojením procesorov
- Zi - zoradený prvok xi (finálna utriedená postupnosť)
- Ci - počet prvkov menších ako xi

neviem ake boli hodnoty, pre ukážku si pozri 2021/22 riadny skupina B pr 6 alebo som nasiel toto
[obrazek: image40]

Př. 7

V tom OCCAM bylo něco jako máte proceduru něco, která má jako parametry [0..9] kanálů CHN, a vstupy IN, ALT typu INT. Na IN přichází hodnoty a jsou posílány na právě aktivní kanál (začíná se 0). Pokud na ALT přijde 1, zapne se alterace a po každém odeslání IN se posuň na další kanál, tj. (active +1) % 10. Pokud přijde na ALT 0, tak vypni alteraci a vše se odesílá na aktuální kanál.

Procedúra s tromi parametrami - pole kanálov OUT[10] a kanály IN a ALT. Na IN a ALT sú prijímané hodnoty 0/1. Hodnota prijatá na ALT zapína/vypína alternovanie medzi OUT kanálmi. Hodnota na IN je poslaná na aktuálny kanál OUT a podľa toho či je zapnutá alternacia je inkrementovany index kanálu OUT (modulo počet kanálov).

Řešení:

[obrazek: image41]

Př. 8

MPI, každej procesor měl prvek a zjistit jestli sudý procesory mají sudy prvky a lichý mají lichý prvky

Řešení:

Dá sa aj s MPI_AND namiesto MPI_SUM
[obrazek: image42]

Semestrálna skúška 2021/2022 - 2. opravný

Př. 1

PRAM tipovačka

Řešení:

Př. 2

Popísať Dataflow architektúru + obrázok

Řešení:

Př. 3

Semafor - popísať P a V operácie

Řešení:

Př. 4

FIFO broadcast - ako prebieha prijímanie a odosielanie a algoritmy

Řešení:

[obrazek: image43]

Př. 5

Príklad na async → sync

Řešení:

Př. 6

Príklad na random mating, skončiť prvú fázu do 4 krokov

Řešení:

Př. 7

LINDA - vyhľadávanie v lineárnom zozname

Řešení:

ze slajdu: (Name, Unique_identifier, Next, Val)

TID id, next;
int to_find;

rd(“list”, “head”, ?id)
while(id != NULL){
rd(“list”, id, ?next, ?val);
if to_find == val
return True
id = next
}

Př. 8

MPI nájsť druhé maximum (pozor, hodnoty môžu byť aj záporné)

PRL Final Exam

Procházet

2021-2022-extract

Semestrálna skúška 2021/2022 - riadny termín - skupina A

Př. 1

Řešení:

Př. 2

Řešení:

Př. 3

Řešení:

Př. 4 а

Řešení:

Př. 5

Řešení:

Př. 6

Řešení:

Př. 7

Řešení:x

Př. 8

Řešení:

Semestrálna skúška 2021/2022 - riadny termín - skupina B

Př. 1

Řešení:

Př. 2

Řešení:

Př. 3

Řešení:

Př. 4

Řešení:

Př. 5

Řešení:

Př. 6

Řešení:

Př. 7

Řešení:

Př. 8

Řešení:

Semestrálna skúška 2021/2022 - riadny termín - skupina C

Př. 1

Řešení:

Př. 2

Řešení:

Př. 3

Řešení:[obrazek: image24]

Př. 4

Řešení:

Př. 5

Řešení:

Př. 6

Řešení:

Př. 7

Řešení:

Př. 8

Řešení:

Semestrálna skúška 2021/2022 - 1. opravný - skupina A

Př. 1

Řešení:

Př. 2

Řešení:

Př. 3

Řešení:

Př. 4

Řešení:

Př. 5

Řešení:

Př. 6

Řešení:

Př. 7

Řešení:

Př. 8

Řešení:

Semestrálna skúška 2021/2022 - 1. opravný - skupina B

Př. 1

Řešení:

Př. 2

Řešení:

Př. 3

Řešení:

Př. 4

Řešení: