Etfsibg: /* Rešenje */

2023-11-01T13:23:07Z

Rešenje

← Старија измена		Верзија на датум 1. новембар 2023. у 15:23
Ред 63:		Ред 63:
	while (error > tol && iter < iter_max) {		while (error > tol && iter < iter_max) {
	error = 0.0;		error = 0.0;
	#pragma omp parallel default(none) shared(A, Anew, n, m) reduction(~~min~~:error)		#pragma omp parallel default(none) shared(A, Anew, n, m) reduction(max:error)
	{		{
	#pragma omp for collapse(2)		#pragma omp for collapse(2)

Etfsibg: /* 4. zadatak */

2023-10-31T17:32:35Z

4. zadatak

← Старија измена		Верзија на датум 31. октобар 2023. у 19:32
Ред 24:		Ред 24:

	== 4. zadatak ==		== 4. zadatak ==
	~~{{delimično rešeno}}~~
	=== Postavka ===		=== Postavka ===
	Objasniti šta je programski model paralelnih programa i tipičnu arhitekturu sistema koju podrazumeva.		Objasniti šta je programski model paralelnih programa i tipičnu arhitekturu sistema koju podrazumeva.

	=== Rešenje ===		=== Rešenje ===
			Videti [[Мултипроцесорски системи/К1 2021#4. zadatak\|ovde]].

	== 5. zadatak ==		== 5. zadatak ==

KockaAdmiralac: Moja rešenja K1 2019

2022-11-01T19:06:08Z

Moja rešenja K1 2019

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

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

== 1. zadatak ==
=== Postavka ===
Objasniti kako je nastao ''power wall'' i kako to utiče na projektovanje procesora.

=== Rešenje ===
Povećanjem takta procesora se povećava količina snage koja se disipira na površini procesora i zato je potrebno bolje hlađenje i više strujne energije kako bi procesor radio. ''Power wall'' na taj način ograničava takt procesora, jer vazdušno hlađenje kao i količina struje koje jedan procesor sme da povuče ima svoje granice.

== 2. zadatak ==
=== Postavka ===
Koje dve klase paralelizma preovladjuju<sup>[sic]</sup> u aplikacijama? Koje vrste paralelizma se prepoznaju pri izvršavanju nu<sup>[sic]</sup> računarima?

=== Rešenje ===
Dve klase paralelizma u aplikacijama su paralelizam na nivou podataka kao i zadataka, dok se pri izvršavanju na računarima prepoznaju kao paralelizam na nivou instrukcije, niti, zahteva, kao i vektorske arhitekture.

== 3. zadatak ==
=== Postavka ===
Objasniti šta je paralelni programski modeli.<sup>[sic]</sup> Objasniti šta su implicitni, a šta eksplicitni modeli, šta su njihove prednosti i nedostaci.

=== Rešenje ===
Programski model je skup apstrakcija koje omogućavaju programeru da na uprošćen i transparentan način vidi softver i hardver. Paralelan programski model je programski model koji programeru specifično pomaže sa apstrahovanjem paralelizma u programima. Implicitni programski modeli su oni koji omogućavaju paralelizam u programu bez intervencije programera, automatskom detekcijom delova za paralelizaciju i njihovim paralelizovanjem. Nažalost, teško je napraviti da ovakvi modeli dostignu zadovoljavajući nivo ubrzanja. Eksplicitni programski modeli zahtevaju od programera da definiše delove i načine za paralelizaciju, što je sa jedne strane mnogo više posla za programera ali sa druge dostiže mnogo veće nivoe paralelizma.

== 4. zadatak ==
{{delimično rešeno}}
=== Postavka ===
Objasniti šta je programski model paralelnih programa i tipičnu arhitekturu sistema koju podrazumeva.

=== Rešenje ===

== 5. zadatak ==
=== Postavka ===
Korišćenjem OpenMP tehnologije, paralelizovati kod u prilogu koji vrši određenu vrstu Laplasove transformacije nad zadatom matricom. Obratiti pažnju na efikasnost i korektnost paralelizacije. Smatrati da su sve promenljive ispravno deklarisane.
<syntaxhighlight lang="c">
int iter = 0;
while (error > tol && iter < iter_max) {
error = 0.0;
for (int j = 1; j < n-1; j++) {
for (int i = 1; i < m-1; i++) {
Anew[j][i] = 0.25 * (A[j][i+1] + A[j][i-1] + A[j-1][i] + A[j+1][i]);
double diff;
if ((Anew[j][i] - A[j][i]) > 0.0) {
diff = Anew[j][i] - A[j][i];
} else {
diff = A[j][i] - Anew[j][i];
}
if (diff > error) error = diff;
}
}
for (int j = 1; j < n-1; j++) {
for (int i = 1; i < m-1; i++) {
A[j][i] = Anew[j][i];
}
}
iter++;
}
</syntaxhighlight>

=== Rešenje ===
<syntaxhighlight lang="c" highlight="4,5,6,19,25">
int iter = 0;
while (error > tol && iter < iter_max) {
error = 0.0;
#pragma omp parallel default(none) shared(A, Anew, n, m) reduction(min:error)
{
#pragma omp for collapse(2)
for (int j = 1; j < n-1; j++) {
for (int i = 1; i < m-1; i++) {
Anew[j][i] = 0.25 * (A[j][i+1] + A[j][i-1] + A[j-1][i] + A[j+1][i]);
double diff;
if ((Anew[j][i] - A[j][i]) > 0.0) {
diff = Anew[j][i] - A[j][i];
} else {
diff = A[j][i] - Anew[j][i];
}
if (diff > error) error = diff;
}
}
#pragma omp for collapse(2)
for (int j = 1; j < n-1; j++) {
for (int i = 1; i < m-1; i++) {
A[j][i] = Anew[j][i];
}
}
}
iter++;
}
</syntaxhighlight>

== 6. zadatak ==
=== Postavka ===
Na koji način <code>nowait</code> odredba može uticati na direktive na koje se odnosi? Navesti kada je ova odredba upotrebljiva i obrazložiti odgovor.

=== Rešenje ===
<code>nowait</code> direktiva diktira da na kraju određenog regiona OpenMP koda ne treba da se vrši implicitna sinhronizacija kao što se inače vrši na kraju <code>for</code>, <code>sections</code> i <code>single</code> regiona. Ova direktiva je upotrebljiva kada nam ovakva implicitna sinhronizacija nije potrebna i možemo pustiti više niti da prođe taj region kako bismo ih onda kasnije negde eksplicitno sinhronizovali. Na primer, možemo pustiti niti da prođu kroz više blokova asociranih sa <code>for</code> direktivama ako te petlje ne zavise jedna od druge, a zatim ih sinhronizovati na nekoj barijeri ispod.

== 7. zadatak ==
=== Postavka ===
Neka se posmatra jedna aplikacija koja vrši obradu velikih matrica koje predstavljaju određenu 2D medicinsku sliku. Nakon merenja performansi sekvencijalne implementacije posmatrane aplikacije pri uobičajenoj upotrebi, dobijeni su sledeći rezultati: aplikacija 15% vremena provodi obavljajući ulazno-izlazne operacije, 85% 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 64 jezgara na 3GHz sa 32GB memorije, navesti formulu za Amdalov zakon i odrediti maksimalno moguće ubrzanje koje se može postići za zadatu aplikaciju.
# Objasniti različite načine za dekompoziciju domena u kontekstu obrade 2D slike i objasniti kako to može imati uticaja na performanse izvršavanja aplikacije. Kako različiti načini dekompozicije mogu da utiču na performanse keširanja podataka?
</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.15</math> i <math>p = 64</math> maksimalno ubrzanje koje možemo da postignemo je <math>S_p = \frac{64}{0.15 \cdot 64 + 1 - 0.15} \approx 6.12</math>.

Dvodimenzionalne matrice mogu da se podele na različite načine: po redovima, po kolonama, po blokovima, ciklično... na performanse aplikacije, doduše može da utiče način keširanja podataka tokom njihovog dohvatanja. Elementi matrice su generalno podaci koji se nalaze blizu jedan do drugog ukoliko im se pristupa na određen način (u C je to po redovima) i zato je za performanse keširanja podataka najbolje deliti tim redom. Ukoliko elementi matrice imaju malu neujednačenost u potrebnom vremenu obrade, ciklična podela može da pomogne tako da svaka nit ima mogućnost da zahvati i delove koji zahtevaju manje i delove koji zahtevaju više obrade.

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

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

Etfsibg: /* Rešenje */

Etfsibg: /* 4. zadatak */

KockaAdmiralac: Moja rešenja K1 2019