Дејан Ковачевић: broj -> veličina

2022-11-01T19:05:35Z

broj -> veličina

← Старија измена		Верзија на датум 1. новембар 2022. у 21:05
Ред 21:		Ред 21:

	=== Rešenje ===		=== Rešenje ===
	* Trend u procesorskoj tehnologiji je bio smanjenje veličine tranzistora. Smanjenjem veličine tranzistora možemo da spakujemo više tranzistora na istu količinu mesta i na taj način pravimo jače procesore. Nažalost, smanjenjem tranzistora oni menjaju svoje elektronske karakteristike, kola u kojima se oni koriste postaju nestabilnija i postoji ograničenje do kojeg se ~~taj broj~~ tranzistora može smanjivati.		* Trend u procesorskoj tehnologiji je bio smanjenje veličine tranzistora. Smanjenjem veličine tranzistora možemo da spakujemo više tranzistora na istu količinu mesta i na taj način pravimo jače procesore. Nažalost, smanjenjem tranzistora oni menjaju svoje elektronske karakteristike, kola u kojima se oni koriste postaju nestabilnija i postoji ograničenje do kojeg se veličina tranzistora može smanjivati.
	* Trend je takođe bio povećanje takta procesora, povećavajući broj izvršenih instrukcija po sekundi. Nažalost, kako su procesori rasli tako je raslo i kašnjenje između logičkih kola, i to predstavlja problem za povećanje takta procesora, koje je poslednje decenije usporilo. Takođe se dešava sa povećavanjem takta da se veća energija disipira na tako maloj površini, pa je procesoru potrebno mnogo bolje hlađenje, i tu takođe nailazimo na ''power wall''.		* Trend je takođe bio povećanje takta procesora, povećavajući broj izvršenih instrukcija po sekundi. Nažalost, kako su procesori rasli tako je raslo i kašnjenje između logičkih kola, i to predstavlja problem za povećanje takta procesora, koje je poslednje decenije usporilo. Takođe se dešava sa povećavanjem takta da se veća energija disipira na tako maloj površini, pa je procesoru potrebno mnogo bolje hlađenje, i tu takođe nailazimo na ''power wall''.

KockaAdmiralac: Moja rešenja K1 2020

2022-11-01T17:06:45Z

Moja rešenja K1 2020

Нова страница

{{tocright}}
'''Prvi kolokvijum 2020. godine''' održan je 3. novembra i trajao je 105 minuta. Postavka roka je dostupna sa [http://mups.etf.bg.ac.rs/ispiti/2020-2021/si4mps_k1_20202021.pdf stranice predmeta.]

== 1. zadatak ==
=== Postavka ===
Objasniti promenu principa projektovanja procesora koji favorizuju paralelno procesiranje.

=== Rešenje ===
Industrija je naišla na tri glavne prepreke pri povećanju kapaciteta procesora, ''power wall'' (struja je skupa, tranzistori su jeftini), ''memory wall'' (operacije sa memorijom su mnogo skuplje od operacija procesora) i ''ILP wall'' (dobici od paralelizma na nivou instrukcija su sve manji). Tu je uočena potreba da se ide ka slabijim višejezgarnim procesorima umesto jačim jednojezgarnim, pošto performanse procesora napreduju mnogo sporije nego ranije i takt više ne može da raste toliko brzo kao ranije, dok se na paralelizaciji programa mogu dobiti mnogo veći dobici u performansama.

== 2. zadatak ==
=== Postavka ===
Šta je pretpostavka ''Gustafson''-ovog zakona? Izvesti i precizno objasniti ovaj zakon.

=== Rešenje ===
''Gustafson''-ov zakon pretpostavlja da paralelni deo programa raste sa brojem procesora. To znači da ako za procesor sa <math>p</math> jezgara uzmemo da se program izvršava <math>T_p = \alpha T + \left(1 - \alpha\right) T</math> gde je <math>\alpha</math> procenat sekvencijalnog koda u aplikaciji, onda se za procesor sa jednim jezgrom taj isti program izvršava <math>T_1 = \alpha T + \left(1 - \alpha\right) pT</math>. Ubrzanje je onda <math>S_p = \frac{T_1}{T_p} = \frac{\alpha T + \left(1 - \alpha\right) pT}{\alpha T + \left(1 - \alpha\right) T} = \frac{\alpha T + \left(1 - \alpha\right) pT}{T} = \alpha + \left(1 - \alpha\right) p</math>. Ovo znači da <math>\lim_{p \to +\infty} S_p = +\infty</math>, ali ova pretpostavka važi samo za skalabilne aplikacije.

== 3. zadatak ==
=== Postavka ===
Opisati tehnološke trendove u procesorskoj tehnologiji i njihove posledice.

=== Rešenje ===
* Trend u procesorskoj tehnologiji je bio smanjenje veličine tranzistora. Smanjenjem veličine tranzistora možemo da spakujemo više tranzistora na istu količinu mesta i na taj način pravimo jače procesore. Nažalost, smanjenjem tranzistora oni menjaju svoje elektronske karakteristike, kola u kojima se oni koriste postaju nestabilnija i postoji ograničenje do kojeg se taj broj tranzistora može smanjivati.
* Trend je takođe bio povećanje takta procesora, povećavajući broj izvršenih instrukcija po sekundi. Nažalost, kako su procesori rasli tako je raslo i kašnjenje između logičkih kola, i to predstavlja problem za povećanje takta procesora, koje je poslednje decenije usporilo. Takođe se dešava sa povećavanjem takta da se veća energija disipira na tako maloj površini, pa je procesoru potrebno mnogo bolje hlađenje, i tu takođe nailazimo na ''power wall''.

== 4. zadatak ==
=== Postavka ===
Dati uporedni pregled karakteristika programskih modela zajedničke memorije i prenosa poruka. U čemu se razlikuju arhitekture i organizacije sistema koji direktno podržavau<sup>[sic]</sup> ove modele.

=== Rešenje ===
{| class="wikitable"
|+ Pregled karakteristika
! Karakteristika
! Zajednička memorija
! Prenos poruka
|-
! Pristup memoriji
| Direktan pristup istoj memoriji
| Direktan pristup svojoj memoriji, posredstvom poruka pristup tuđim memorijama
|-
! Sinhronizacija
| Moraju se koristiti odvojene strukture (kapaciteti operativnog sistema i hardvera) kako bi se pristup memoriji sinhronizovao
| Implicitna, jer razmenjuju poruke
|-
! Kopiranje podataka
| Nije potrebno, drugi imaju pristup istoj memoriji kao mi
| Potrebno, jer jedino tako drugi mogu da dobiju sadržaj naše privatne memorije
|-
! Identitet
| Procesi ne (moraju da) znaju jedan za drugog
| Procesi znaju jedan za drugog
|-
! Arhitektura i organizacija
| Složenija, postoje UMA i NUMA varijante kako bi procesori delili memoriju između sebe i potrebno je održavati koherenciju keš memorija
| Manje složena, pošto procesori eksplicitno zahtevaju jedni od drugih memoriju koja im je potrebna, ali je zato softver koji to radi složeniji
|}

== 5. zadatak ==
=== Postavka ===
Korišćenjem OpenMP tehnologije, paralelizovati funkciju u prilogu koji računa vrednost određenog integrala korišćenjem Simpsonovog 1/3 pravila. Obratiti pažnju na efikasnost i korektnost paralelizacije. Smatrati da su sve promenljive ispravno deklarisane.
<syntaxhighlight lang="c">
float simpsons(float ll, float ul, int n) {
float h = (ul - ll) / n, x[10], fx[10];
for (int i = 0; i <= n; i++) {
x[i] = ll + i * h; fx[i] = func(x[i]);
}
float res = 0;
for (int i = 0; i <= n; i++) {
if (i == 0 || i == n) res += fx[i];
else if (i % 2 != 0) res += 4 * fx[i];
else res += 2 * fx[i];
}
res = res * (h / 3);
return res;
}
</syntaxhighlight>

=== Rešenje ===
Sledeće rešenje je pisano pod uslovom da su deklaracije <code>x</code> i <code>fx</code> kao nizove od 10 brojeva simbolične i da <code>n</code> zapravo sme da bude veće 10, jer inače paralelizacija ovog programa ne bi imala nikakvog smisla.
<syntaxhighlight lang="c" highlight="3,8">
float simpsons(float ll, float ul, int n) {
float h = (ul - ll) / n, x[10], fx[10];
#pragma omp parallel for default(none) shared(x, fx, ll, ul, n, h)
for (int i = 0; i <= n; i++) {
x[i] = ll + i * h; fx[i] = func(x[i]);
}
float res = 0;
#pragma omp parallel for default(none) shared(fx) reduction(+:res)
for (int i = 0; i <= n; i++) {
if (i == 0 || i == n) res += fx[i];
else if (i % 2 != 0) res += 4 * fx[i];
else res += 2 * fx[i];
}
res = res * (h / 3);
return res;
}
</syntaxhighlight>

== 6. zadatak ==
=== Postavka ===
Da li i na koji način OpenMP podržava ugneždeni paralelizam? Da li je moguće u okviru paralelnog regiona pokrenuti novi paralelni region i pod kojim uslovima?

=== Rešenje ===
OpenMP podržava ugneždeni paralelizam, u smislu da je moguće ugnezditi paralelni region unutar drugog paralelnog regiona. Pri ugneždavanju će se stvoriti tim niti sa jednom niti u njemu, osim ukoliko ugneždavanje nije omogućeno korišćenjem <code>omp_set_nested(true)</code> funkcije, ili <code>OMP_NESTED</code> promenljive okruženja. Neke implementacije ne podržavaju ove metode ugneždavanja, i u njima će ugneždeni tim niti uvek imati jednu nit.

== 7. zadatak ==
=== Postavka ===
Neka se posmatra jedna aplikacija za prikupljanje i agregaciju podataka sa interneta. Aplikacija se sastoji od veb tragača (''web crawler'') koji prikuplja određene informacije na internetu, a zatim se radi obrada. Nakon merenja performansi sekvencijalne implementacije posmatrane aplikacije pri uobičajenoj upotrebi, dobijeni su sledeći rezultati: aplikacija 45% vremena provodi obavljajući ulazno-izlazne operacije (sekvencijalno prikupljanje podataka iz jednog izvora), a 55% vremena provodi u obradi podataka. Tipično vreme obrade jednog paketa podataka korišćenjem jednog jezgra je 1s.
<div class="abc-list">
# Ukoliko se aplikacija paralelizuje za izvršavanje na SMP sistemu sa 8 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.
# Da li i na koji način može organizovati paralelno izvršavanje sekvencijalnog dela aplikacije, ukoliko paketi sa interneta mogu nezavisno da se obrađuju? Smatrati da paketi imaju neujednačeno vreme obrade i diskutovati moguće načine paralelne obrade.
</div>

=== Rešenje ===
Formula za Amdalov zakon glasi:
* <math>T_p = \alpha T_1 + (1 - \alpha) \frac{T_1}{p}</math>
* <math>S_p = \frac{T_1}{T_P} = \frac{1}{\alpha + \frac{1 - \alpha}{p}} = \frac{p}{\alpha p + 1 - \alpha}</math>
Kako je nama ovde <math>\alpha = 0.45</math> i <math>p = 8</math> maksimalno ubrzanje koje možemo da postignemo je <math>S_p = \frac{8}{0.45 \cdot 8 + 1 - 0.45} \approx 1.93</math>.

Aplikacija može da održava osam niti, od kojih jedna nit radi primanje podataka preko interneta i kako pristižu paketi ubacuje ih u neku deljenu strukturu i nekom sinhronizacionom primitivom signalizira da ima paketa za obradu (slično ''bag of tasks'' pristupu korišćenjem programskog modela deljene memorije). Ostalih sedam niti mogu da iz ove vreće zadataka preuzimaju pakete za obradu i obrađuju ih paralelno. Bez obzira na to što paketi imaju neujednačeno vreme obrade, niti ne moraju da čekaju jedna na drugu tako da dok jedna nit obrađuje zahtevniji paket ostale niti ne zavise od nje (ne postoji ''bottleneck''). Više od osam niti verovatno neće ubrzati aplikaciju jer će svesti na klasičan ''time-sharing'' umesto paralelne obrade.

[[Категорија:Рокови]]
[[Категорија:Мултипроцесорски системи]]

Мултипроцесорски системи/К1 2020 - Историја измена

Дејан Ковачевић: broj -> veličina

KockaAdmiralac: Moja rešenja K1 2020