SI Wiki - Кориснички доприноси [sr]

Мултипроцесорски системи/К1 2018

2024-10-23T21:20:07Z

Kosta01856: /* Rešenje */

{{tocright}}
'''Prvi kolokvijum 2018. godine''' održan je 30. oktobra i trajao je 105 minuta. Postavka roka je dostupna sa [http://mups.etf.rs/ispiti/2018-2019/si4mps_k1_20182019.pdf stranice predmeta.]

== 1. zadatak ==
: Veoma slično pitanje našlo se na [[Мултипроцесорски системи/К1 2021#1. zadatak|prvom kolokvijumu 2021. godine]]
=== Postavka ===
Opisati pet klasa savremenih računara sa naglaskom na projektne prioritete u svakoj klasi.
=== Rešenje ===
Videti [[Мултипроцесорски системи/К1 2021#1. zadatak|ovde]].

== 2. zadatak ==
=== Postavka ===
Objasniti šta je ILP i navesti tipične primere. Objasniti i obrazložiti trendove iskorišćenja ILP za povećanje performansi nekada i sada.
=== Rešenje ===
ILP (''Instruction-level parallelism'') je paralelizam u obliku istovremenog izvršavanja više instrukcija. Drugim rečima, cilj ILP je povećanje broja izvršenih instrukcija po taktu. Primeri tehnika ILP-a su: protočna obrada, izvršavanje instrukcija van poretka, spekulativno izvršavanje, predikcija skoka i optimizacije prevodioca radi boljeg iskorišćavanja prethodnih tehnika.

ILP je imao najveći značaj u periodu od kraja 80-ih do ranih 2000-ih. Tehnološki trendovi dozvoljavali su veliko usložnjenje organizacije procesora, sa ciljem da povećaju ILP i broj instrukcija po taktu. Danas, poboljšanja performansi od ILP je sve manje i manje, jer se povećanjem broja instrukcija po taktu ne dobija znatno ubrzanje.
== 3. zadatak ==
=== Postavka ===
Objasniti prednosti i nedostatke programskog modela zajedničke memorije.
=== Rešenje ===
Prednosti:
* Globalni adresni prostor olakšava programiranje
* Uniforman pristup podacima, bez potrebe da se kopiraju i maršaluju kao na modelu prenosa poruka.
* Manji komunikacioni ''overhead'' (bez OS, bibliotečkih rutina)
* Prirodna nadogradnja na sekvencijalno programiranje (lakše se paralelizuje postojeći kod)
* Omogućava keširanje
* Može da emulira ostale programske modele
Mane:
* Složeniji hardver
* Teže skalira povećanjem broja procesora
* Zahteva posebne atomske operacije za sinhronizaciju
* Programer odgovoran za pravilan pristup deljenim podacima
* Teže optimizovati implicitnu komunikaciju

== 4. zadatak ==
=== Postavka ===
Nacrtati i objasniti tipičnu strukturu sistema koji podržava model prenosa poruka. Po čemu se ona razlikuje od NUMA arhitekture?
=== Rešenje ===
(''Slika: [http://mups.etf.rs/predavanja/SI4MPS%20-%20P02%20-%20PPM.pdf P02 - PPM, slajd 42]'')

Gradivni element u modelu prenosa poruka je kompletan računar. Računarima su odvojeni adresni prostori i komuniciraju eksplicitnim I/O operacijama preko mreže.

Organizacija je slična NUMA arhitekturama, ali postoje razlike:
* Komunikacija u NUMA sistemima se odnosi na pristup memoriji, ne na razmenu poruka.
* Jača je sprega između procesora i mreže kod prenosa poruka.

== 5. zadatak ==
=== Postavka ===
Korišćenjem OpenMP tehnologije, paralelizovati kod u prilogu koji vrši obilazak i obradu čvorova grafa BFS metodom. Obratiti pažnju na efikasnost i korektnost paralelizacije. Smatrati da su sve promenljive ispravno deklarisane.
<syntaxhighlight lang="c">
queue<node*> q;
q.push(head);
while (!q.empty()) {
qSize = q.size();
for (int i = 0; i < qSize; i++) {
node* currNode = q.front();
q.pop();
doStuff(currNode);
q.push(currNode);
}
}
</syntaxhighlight>

=== Rešenje ===
Ovaj kod za obradu čvorova BFS metodom nije ispravan, jer sve vreme cirkuliše isti čvor u redu, a i nema nikakvog smisla vraćati čvor koji je već bio u redu nazad u taj red. Ukoliko zanemarimo te probleme, i pretpostavimo da se u <code>doStuff</code> radi samo obrada a ne i neko guranje čvorova u red, ovaj zadatak se može paralelizovati OpenMP poslovima, slično kodu za obilaženje ulančane liste:
<syntaxhighlight lang="c" highlight="3,4,5,6,12,17,18">
queue<node*> q;
q.push(head);
#pragma omp parallel
{
#pragma omp single
{
while (!q.empty()) {
qSize = q.size();
for (int i = 0; i < qSize; i++) {
node* currNode = q.front();
q.pop();
#pragma omp task
doStuff(currNode);
q.push(currNode);
}
}
}
}
</syntaxhighlight>

== 6. zadatak ==
=== Postavka ===
Koji model memorijske konzistencije podržava OpenMP i kakav to uticaj može imati na izvršavanje koda niti? Da li postoje direktive kojima se može uticati na izvršavanje niti u smislu održavanja konzistentnog pogleda na memoriju? Obrazložiti odgovor.

=== Rešenje ===
OpenMP podržava model relaksirane konzistencije, tako da ne moraju sve niti da vide isti sadržaj memorije. Ukoliko je nitima neophodno, mogu da koriste <code>flush</code> direktivu koja sinhronizuje pogled niti na memoriju. Ova direktiva je implicitna prilikom nailaska na razne sinhronizacione direktive i pri ulasku i izlasku iz paralelnog regiona. Nije dobro koristiti <code>flush</code> direktivu kad nije apsolutno neophodno.

== 7. zadatak ==
{{delimično rešeno}}
=== Postavka ===
Neka se posmatra jedna aplikacija koja vrši obradu čvorova grafa. Grafovi koji se obrađuju su veoma neujednačenog stepena čvorova, a vreme obrade je proporcionalno
stepenu čvora. Nakon merenja performansi sekvencijalne implementacije posmatrane aplikacije pri uobičajenoj upotrebi, dobijeni su sledeći rezultati: aplikacija 5% vremena provodi obavljajući ulazno-izlazne operacije, 95% vremena provodi u obradi podataka. Tipično vreme obrade jednog čvora korišćenjem jednog jezgra je 1s.
<div class="abc-list">
# Ukoliko se aplikacija paralelizuje za izvršavanje na SMP sistemu sa 16 jezgara na 2GHz sa 32GB memorije, navesti formulu za Amdalov zakon i odrediti maksimalno moguće ubrzanje koje se može postići za zadatu aplikaciju.
# Diskutovati uticaj balansa opterećenja na performanse aplikacije, ukoliko je raspodela čvorova po stepenu kao na grafiku sa slike. Predložiti i obrazložiti šemu paralelizacije kojom bi se poboljšale performanse.
</div>
=== Rešenje ===

[[Категорија:Рокови]]
[[Категорија:Мултипроцесорски системи]]
Sp = T1/T16
<br>
T1 = 1s
<br>
T16 = alfa*T1 + (1-alfa)/N
<br>
N=16
<br>
alfa = 0.05
<br>
T16 = 0.05*T1 + (0.95)*T1/16
<br>
S = T1/T16 = 9.14
<br>
drugi nacin:
Sp = 1/ ((1 - P) + P/N)
<br>
N = 16
<br>
P = 0.95
<br>
Sp = 1 / (0.05 + 0.95/16)
<br>
Sp = 9.14
<br>

Posto je graf neujednacen, neki core-ovi mogu biti vise optereceni, dok su drugi idle.
Zato ovde treba koristiti dinamicku raspodelu zadataka, tako da kada jedna nit(core), zavrsi, odmah
trazi sledeci cvor koji treba da obradi. Na ovaj nacin, ni jedan core nikad nece biti idle.

Мултипроцесорски системи/К1 2018

2024-10-23T21:18:25Z

Kosta01856: /* Rešenje */

{{tocright}}
'''Prvi kolokvijum 2018. godine''' održan je 30. oktobra i trajao je 105 minuta. Postavka roka je dostupna sa [http://mups.etf.rs/ispiti/2018-2019/si4mps_k1_20182019.pdf stranice predmeta.]

== 1. zadatak ==
: Veoma slično pitanje našlo se na [[Мултипроцесорски системи/К1 2021#1. zadatak|prvom kolokvijumu 2021. godine]]
=== Postavka ===
Opisati pet klasa savremenih računara sa naglaskom na projektne prioritete u svakoj klasi.
=== Rešenje ===
Videti [[Мултипроцесорски системи/К1 2021#1. zadatak|ovde]].

== 2. zadatak ==
=== Postavka ===
Objasniti šta je ILP i navesti tipične primere. Objasniti i obrazložiti trendove iskorišćenja ILP za povećanje performansi nekada i sada.
=== Rešenje ===
ILP (''Instruction-level parallelism'') je paralelizam u obliku istovremenog izvršavanja više instrukcija. Drugim rečima, cilj ILP je povećanje broja izvršenih instrukcija po taktu. Primeri tehnika ILP-a su: protočna obrada, izvršavanje instrukcija van poretka, spekulativno izvršavanje, predikcija skoka i optimizacije prevodioca radi boljeg iskorišćavanja prethodnih tehnika.

ILP je imao najveći značaj u periodu od kraja 80-ih do ranih 2000-ih. Tehnološki trendovi dozvoljavali su veliko usložnjenje organizacije procesora, sa ciljem da povećaju ILP i broj instrukcija po taktu. Danas, poboljšanja performansi od ILP je sve manje i manje, jer se povećanjem broja instrukcija po taktu ne dobija znatno ubrzanje.
== 3. zadatak ==
=== Postavka ===
Objasniti prednosti i nedostatke programskog modela zajedničke memorije.
=== Rešenje ===
Prednosti:
* Globalni adresni prostor olakšava programiranje
* Uniforman pristup podacima, bez potrebe da se kopiraju i maršaluju kao na modelu prenosa poruka.
* Manji komunikacioni ''overhead'' (bez OS, bibliotečkih rutina)
* Prirodna nadogradnja na sekvencijalno programiranje (lakše se paralelizuje postojeći kod)
* Omogućava keširanje
* Može da emulira ostale programske modele
Mane:
* Složeniji hardver
* Teže skalira povećanjem broja procesora
* Zahteva posebne atomske operacije za sinhronizaciju
* Programer odgovoran za pravilan pristup deljenim podacima
* Teže optimizovati implicitnu komunikaciju

== 4. zadatak ==
=== Postavka ===
Nacrtati i objasniti tipičnu strukturu sistema koji podržava model prenosa poruka. Po čemu se ona razlikuje od NUMA arhitekture?
=== Rešenje ===
(''Slika: [http://mups.etf.rs/predavanja/SI4MPS%20-%20P02%20-%20PPM.pdf P02 - PPM, slajd 42]'')

Gradivni element u modelu prenosa poruka je kompletan računar. Računarima su odvojeni adresni prostori i komuniciraju eksplicitnim I/O operacijama preko mreže.

Organizacija je slična NUMA arhitekturama, ali postoje razlike:
* Komunikacija u NUMA sistemima se odnosi na pristup memoriji, ne na razmenu poruka.
* Jača je sprega između procesora i mreže kod prenosa poruka.

== 5. zadatak ==
=== Postavka ===
Korišćenjem OpenMP tehnologije, paralelizovati kod u prilogu koji vrši obilazak i obradu čvorova grafa BFS metodom. Obratiti pažnju na efikasnost i korektnost paralelizacije. Smatrati da su sve promenljive ispravno deklarisane.
<syntaxhighlight lang="c">
queue<node*> q;
q.push(head);
while (!q.empty()) {
qSize = q.size();
for (int i = 0; i < qSize; i++) {
node* currNode = q.front();
q.pop();
doStuff(currNode);
q.push(currNode);
}
}
</syntaxhighlight>

=== Rešenje ===
Ovaj kod za obradu čvorova BFS metodom nije ispravan, jer sve vreme cirkuliše isti čvor u redu, a i nema nikakvog smisla vraćati čvor koji je već bio u redu nazad u taj red. Ukoliko zanemarimo te probleme, i pretpostavimo da se u <code>doStuff</code> radi samo obrada a ne i neko guranje čvorova u red, ovaj zadatak se može paralelizovati OpenMP poslovima, slično kodu za obilaženje ulančane liste:
<syntaxhighlight lang="c" highlight="3,4,5,6,12,17,18">
queue<node*> q;
q.push(head);
#pragma omp parallel
{
#pragma omp single
{
while (!q.empty()) {
qSize = q.size();
for (int i = 0; i < qSize; i++) {
node* currNode = q.front();
q.pop();
#pragma omp task
doStuff(currNode);
q.push(currNode);
}
}
}
}
</syntaxhighlight>

== 6. zadatak ==
=== Postavka ===
Koji model memorijske konzistencije podržava OpenMP i kakav to uticaj može imati na izvršavanje koda niti? Da li postoje direktive kojima se može uticati na izvršavanje niti u smislu održavanja konzistentnog pogleda na memoriju? Obrazložiti odgovor.

=== Rešenje ===
OpenMP podržava model relaksirane konzistencije, tako da ne moraju sve niti da vide isti sadržaj memorije. Ukoliko je nitima neophodno, mogu da koriste <code>flush</code> direktivu koja sinhronizuje pogled niti na memoriju. Ova direktiva je implicitna prilikom nailaska na razne sinhronizacione direktive i pri ulasku i izlasku iz paralelnog regiona. Nije dobro koristiti <code>flush</code> direktivu kad nije apsolutno neophodno.

== 7. zadatak ==
{{delimično rešeno}}
=== Postavka ===
Neka se posmatra jedna aplikacija koja vrši obradu čvorova grafa. Grafovi koji se obrađuju su veoma neujednačenog stepena čvorova, a vreme obrade je proporcionalno
stepenu čvora. Nakon merenja performansi sekvencijalne implementacije posmatrane aplikacije pri uobičajenoj upotrebi, dobijeni su sledeći rezultati: aplikacija 5% vremena provodi obavljajući ulazno-izlazne operacije, 95% vremena provodi u obradi podataka. Tipično vreme obrade jednog čvora korišćenjem jednog jezgra je 1s.
<div class="abc-list">
# Ukoliko se aplikacija paralelizuje za izvršavanje na SMP sistemu sa 16 jezgara na 2GHz sa 32GB memorije, navesti formulu za Amdalov zakon i odrediti maksimalno moguće ubrzanje koje se može postići za zadatu aplikaciju.
# Diskutovati uticaj balansa opterećenja na performanse aplikacije, ukoliko je raspodela čvorova po stepenu kao na grafiku sa slike. Predložiti i obrazložiti šemu paralelizacije kojom bi se poboljšale performanse.
</div>
=== Rešenje ===

[[Категорија:Рокови]]
[[Категорија:Мултипроцесорски системи]]
Sp = T1/T16
T1 = 1s
T16 = alfa*T1 + (1-alfa)/N
N=16
alfa = 0.05
T16 = 0.05*T1 + (0.95)*T1/16
S = T1/T16 = 9.14
drugi nacin:
Sp = 1/ ((1 - P) + P/N)
N = 16
P = 0.95
Sp = 1 / (0.05 + 0.95/16)
Sp = 9.14

Posto je graf neujednacen, neki core-ovi mogu biti vise optereceni, dok su drugi idle.
Zato ovde treba koristiti dinamicku raspodelu zadataka, tako da kada jedna nit(core), zavrsi, odmah
trazi sledeci cvor koji treba da obradi. Na ovaj nacin, ni jedan core nikad nece biti idle.