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

Kosta01856: /* Rešenje */

2024-10-23T21:20:07Z

Rešenje

← Старија измена		Верзија на датум 23. октобар 2024. у 23:20
Ред 107:		Ред 107:
	[[Категорија:Мултипроцесорски системи]]		[[Категорија:Мултипроцесорски системи]]
	Sp = T1/T16		Sp = T1/T16
			<br>
	T1 = 1s		T1 = 1s
			<br>
	T16 = alfa*T1 + (1-alfa)/N		T16 = alfa*T1 + (1-alfa)/N
			<br>
	N=16		N=16
			<br>
	alfa = 0.05		alfa = 0.05
			<br>
	T16 = 0.05T1 + (0.95)T1/16		T16 = 0.05T1 + (0.95)T1/16
			<br>
	S = T1/T16 = 9.14		S = T1/T16 = 9.14
			<br>
	drugi nacin:		drugi nacin:
	Sp = 1/ ((1 - P) + P/N)		Sp = 1/ ((1 - P) + P/N)
			<br>
	N = 16		N = 16
			<br>
	P = 0.95		P = 0.95
			<br>
	Sp = 1 / (0.05 + 0.95/16)		Sp = 1 / (0.05 + 0.95/16)
			<br>
	Sp = 9.14		Sp = 9.14
			<br>

Kosta01856: /* Rešenje */

2024-10-23T21:18:25Z

Rešenje

← Старија измена		Верзија на датум 23. октобар 2024. у 23:18
Ред 106:		Ред 106:
	[[Категорија:Рокови]]		[[Категорија:Рокови]]
	[[Категорија:Мултипроцесорски системи]]		[[Категорија:Мултипроцесорски системи]]
			Sp = T1/T16
			T1 = 1s
			T16 = alfa*T1 + (1-alfa)/N
			N=16
			alfa = 0.05
			T16 = 0.05T1 + (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.

KockaAdmiralac: Odgovor na šesti zadatak

2022-11-02T11:54:12Z

Odgovor na šesti zadatak

← Старија измена		Верзија на датум 2. новембар 2022. у 13:54
Ред 87:		Ред 87:

	== 6. zadatak ==		== 6. zadatak ==
	~~{{delimično rešeno}}~~
	=== Postavka ===		=== 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.		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 ===		=== 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 ==		== 7. zadatak ==

KockaAdmiralac: Potencijalno rešenje petog zadatka

2022-11-02T11:42:16Z

Potencijalno rešenje petog zadatka

@@ Ред 47: / Ред 47: @@
 == 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.
@@ Ред 63: / Ред 62: @@
+}
 </syntaxhighlight>
 === Rešenje ===
 == 6. zadatak ==

TopOfKeks: K1 2018

2022-11-02T09:15:32Z

K1 2018

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

{{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 ==
{{delimično rešeno}}
=== 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 ===

== 6. zadatak ==
{{delimično rešeno}}
=== 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 ===

== 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 ===

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