KockaAdmiralac: rank -> size

2022-12-07T13:44:33Z

rank -> size

← Старија измена		Верзија на датум 7. децембар 2022. у 15:44
Ред 56:		Ред 56:
	MPI_Bcast(&maxIter, 1, MPI_INT, MASTER, MPI_COMM_WORLD);		MPI_Bcast(&maxIter, 1, MPI_INT, MASTER, MPI_COMM_WORLD);
	double pi;		double pi;
	for (int i = rank; i < maxIter; i += ~~rank~~) {		for (int i = rank; i < maxIter; i += size) {
	pi += ((i & 1) ? -1. : 1.)/(2. * i + 1.);		pi += ((i & 1) ? -1. : 1.)/(2. * i + 1.);
	}		}

KockaAdmiralac: Ova tabela je bila prekopirana sa prethodnog K2

2022-12-07T13:14:03Z

Ova tabela je bila prekopirana sa prethodnog K2

← Старија измена		Верзија на датум 7. децембар 2022. у 15:14
Ред 122:		Ред 122:
	\|-		\|-
	! P0		! P0
	\| 1 \|\| 6 \|\| 16.6% \|\| RM, WM, WH, RM, ~~flush~~, RM		\| 1 \|\| 7 \|\| 14.3% \|\| WM, flush, WM, flush, RM, RM, RH
	\|-		\|-
	! P1		! P1
	\| 1 \|\| 5 \|\| 20% \|\| RM, RM~~, RM, WH, flush~~		\| 0 \|\| 2 \|\| 0% \|\| RM, RM
	\|-		\|-
	! P2		! P2
	\| 0 \|\| 0 \|\| 0% \|\|		\| 0 \|\| 1 \|\| 0% \|\| RM
	\|-		\|-
	! P3		! P3

KockaAdmiralac: Moja rešenja K2 2019 (Allreduce u šestom pozajmljen od Alekse)

2022-12-07T11:24:26Z

Moja rešenja K2 2019 (Allreduce u šestom pozajmljen od Alekse)

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

{{tocright}}
'''Drugi kolokvijum 2019. godine''' održan je 3. decembra. Trajao je 105 minuta i postavka je dostupna sa [http://mups.etf.bg.ac.rs/ispiti/2019-2020/si4mps_k2_20192020.pdf stranice predmeta.]

== 1. zadatak ==
=== Postavka ===
Skicirati i objasniti generičku paralelnu arhitekturu i njene delove. Kako se ova opšta arhitektura može prilagoditi da efikasno podržava pojedine programske modele?

=== Rešenje ===
Generička paralelna arhitektura se sastoji od više procesora, svaki sa svojim kešom, zajedničke memorije i komunikacionog asistenta, gde svi komuniciraju preko magistrale. Komunikacioni asistent je komponenta za komunikaciju preko mreže, koja može biti adaptirana u zavisnosti od potreba konkretnih programskih modela:
* ''Deljena memorija:'' asistent treba biti uvezan sa memorijom za jednostavan pristup preko mreže
* ''Prosleđivanje poruka:'' asistent treba imati podršku za eksplicitno slanje poruka
* ''Data Parallel:'' asistent treba imati brzu globalnu sinhronizaciju
* ''Dataflow:'' asistent treba imati podršku za dinamičko raspoređivanje izračunavanja

== 2. zadatak ==
=== Postavka ===
Objasniti dva slučaja kada procesi imaju samo logički privatne podatke, a izazivaju se akcije protokola za koherenciju.

=== Rešenje ===
Isto kao [[Мултипроцесорски системи/К2 2021#1. zadatak|prvi zadatak sa drugog kolokvijuma 2021. godine]].

== 3. zadatak ==
=== Postavka ===
Precizno objasniti akcije i promene stanja koje se odvijaju pri upisu u protokolu MESI. Nacrtati ovaj deo dijagrama stanja.

=== Rešenje ===
Pri upisu u podatak, procesor koji je upisao prelazi u stanje M a svi ostali procesori kada to detektuju prelaze u stanje I. Ukoliko je procesor bio u stanju M pre detekcije upisa, on radi operaciju ''flush'', a u suprotnom prenosi vrednost podatka/bloka procesoru koji upisuje (ako nije u stanju I). Ukoliko više procesora u stanju S želi da prenese procesoru koji upisuje vrednost podatka/bloka, MESI ne definiše način na koji se to radi. Ovaj problem je rešen kasnijim protokolima (MESIF, MOESI).

== 4. zadatak ==
=== Postavka ===
Šta je procesorska lokalnost? Definisati parametar koji je indikator procesorske lokalnosti. U odnosu na vrednost ovog parametra komentarisati kada bolje performanse ima strategija invalidacije, a kada strategija ažuriranja.

=== Rešenje ===
Procesorska lokalnost je osobina podatka da se koristi na samo jednom procesoru. Indikator procesorske lokalnosti podatka jeste dužina ''write run'', odnosno koliko puta je procesor uspeo da upiše u podatak u svom kešu pre nego što mu je neki drugi procesor preoteo taj podatak. Duži upisni niz pokazuje da je taj podatak više lokalan za određen procesor, dok kraći upisni niz pokazuje da je više deljen a manje lokalan. U odnosu na ovo, strategija invalidacije je korisnija kod dužih upisnih nizova, jer poništava zastarele kopije, dok kod kraćih upisnih nizova izaziva mnogo ponovnih pristupa memoriji nakon invalidacije, gde je strategija ažuriranja korisnija.

== 5. zadatak ==
=== Postavka ===
Korišćenjem MPI tehnologije napisati deo koda koji računa broj PI korišćenjem Lajbnicove formule: <math>\sum_{n = 0}^{\infty} \frac{(-1)^n}{2n + 1} = \frac{\pi}{4}</math>

Obratiti pažnju na efikasnost paralelizacije. Smatrati da je MPI okruženje već inicijalizovano i da svi procesi treba da učestvuju u obradi. Proces sa rangom 0 dobija ulazni<sup>[sic]</sup> podatke, raspodeljuje ih ostalim procesima, a svi procesi trebaju da dobiju finalni rezultat rada.

=== Rešenje ===
<syntaxhighlight lang="c">
#define MASTER 0

int main(void) {
// ...
int rank;
int size;
MPI_Comm_rank(MPI_COMM_WORLD, &rank);
MPI_Comm_size(MPI_COMM_WORLD, &size);
int maxIter;
if (rank == MASTER) {
scanf("%d", &maxIter);
}
MPI_Bcast(&maxIter, 1, MPI_INT, MASTER, MPI_COMM_WORLD);
double pi;
for (int i = rank; i < maxIter; i += rank) {
pi += ((i & 1) ? -1. : 1.)/(2. * i + 1.);
}
double totalPi;
MPI_Allreduce(&pi, &totalPi, 1, MPI_DOUBLE, MPI_SUM, MPI_COMM_WORLD);
printf("%lf\n", totalPi);
// ...
return 0;
}
</syntaxhighlight>

== 6. zadatak ==
=== Postavka ===
Koja je prednost korišćenja grupa i komunikatora prilikom kolektivne MPI komunikacije. Pod pretpostavkom da je pokrenuto ''n'' MPI procesa, a da samo prvih ''n''/2 procesa treba da dobije celobrojnu vrednost ''x'' od master procesa, napisati deo koda za formiranje nove grupe i komunikatora i prosleđivanje podatka odgovarajućom rutinom za kolektivnu komunikaciju.

=== Rešenje ===
Prednost korišćenja grupa i komunikatora je u tome što možemo da ograničimo na koji način mogu procesi da komuniciraju, i da komunikaciju vršimo u manjim grupama.
<syntaxhighlight lang="c">
#define MASTER 0

int main(void) {
// ...
int n;
int rank;
MPI_Comm_size(MPI_COMM_WORLD, &n);
MPI_Comm_rank(MPI_COMM_WORLD, &rank);
int x;
if (rank == MASTER) {
// Input x
}
MPI_Group globalGroup;
MPI_Comm_group(MPI_COMM_WORLD, &globalGroup);
MPI_Comm newComm;
MPI_Group newGroup;
int ranges[][3] = {{0, n/2, 1}};
MPI_Group_range_incl(globalGroup, 1, ranges, &newGroup);
MPI_Comm_create(MPI_COMM_WORLD, newGroup, &newComm);
if (rank < n/2) {
MPI_Bcast(&x, 1, MPI_INT, MASTER, newComm);
}
// ...
}
</syntaxhighlight>

== 7. zadatak ==
=== Postavka ===
Dat je multiprocesorski sistem sa 4 identična procesora, koji koristi MSI protokol za održavanje koherencije keš memorije. Svaka keš memorija ima po 2 ulaza, koji su veličine jedne reči. Preslikavanje je direktno. Početne vrednosti podataka su 0. Svaki upis uvećava vrednost izmenjenog podatka za 1. Na početku su sve keš memorije prazne. Data je sledeća sekvenca pristupa memoriji:
# P1,R,A0
# P2,R,A0
# P0,W,A0
# P0,W,A2
# P1,R,A2
# P0,R,A0
# P0,R,A1
# P0,R,A0

* Napisati stanja koherencije u svim procesorima i stanje memorije posle svake promene i skicirati opisani sistem u trenutku 8.
* Koliko puta koji od procesora pristupa memoriji? Za svaki pristup navesti razlog.
* Koliki je Hit Rate za svaki od procesora (brojati i čitanje i upis, prikazati zbirno)?

=== Rešenje ===
{| class="wikitable"
! CPU
! Broj pogodaka !! Ukupan broj pristupa !! Hit rate !! Pristupi memoriji
|-
! P0
| 1 || 6 || 16.6% || RM, WM, WH, RM, flush, RM
|-
! P1
| 1 || 5 || 20% || RM, RM, RM, WH, flush
|-
! P2
| 0 || 0 || 0% ||
|-
! P3
| 0 || 0 || 0% ||
|}

==== Trenutak 1 ====
{| class="wikitable"
|+ Sadržaj keševa
! colspan="3" | P0
! colspan="3" | P1
! colspan="3" | P2
! colspan="3" | P3
|-
| || ||
| A0 || S || 0
| || ||
| || ||
|-
| || ||
| || ||
| || ||
| || ||
|}
{| class="wikitable"
|+ Sadržaj memorije
! A0
| 0
|-
! A1
| 0
|-
! A2
| 0
|-
! A3
| 0
|}
P1 je pristupao memoriji kako bi dohvatio podatak sa A0 (RM).

==== Trenutak 2 ====
{| class="wikitable"
|+ Sadržaj keševa
! colspan="3" | P0
! colspan="3" | P1
! colspan="3" | P2
! colspan="3" | P3
|-
| || ||
| A0 || S || 0
| A0 || S || 0
| || ||
|-
| || ||
| || ||
| || ||
| || ||
|}
{| class="wikitable"
|+ Sadržaj memorije
! A0
| 0
|-
! A1
| 0
|-
! A2
| 0
|-
! A3
| 0
|}
P2 je pristupao memoriji kako bi dohvatio podatak sa A0 (RM).

==== Trenutak 3 ====
{| class="wikitable"
|+ Sadržaj keševa
! colspan="3" | P0
! colspan="3" | P1
! colspan="3" | P2
! colspan="3" | P3
|-
| A0 || M || 1
| A0 || I || 0
| A0 || I || 0
| || ||
|-
| || ||
| || ||
| || ||
| || ||
|}
{| class="wikitable"
|+ Sadržaj memorije
! A0
| 0
|-
! A1
| 0
|-
! A2
| 0
|-
! A3
| 0
|}
P0 čita podatak A0 sa namerom upisa (WM), takođe invalidirajući ostale podatke tom prilikom.

==== Trenutak 4 ====
{| class="wikitable"
|+ Sadržaj keševa
! colspan="3" | P0
! colspan="3" | P1
! colspan="3" | P2
! colspan="3" | P3
|-
| A2 || M || 1
| A0 || I || 0
| A0 || I || 0
| || ||
|-
| || ||
| || ||
| || ||
| || ||
|}
{| class="wikitable"
|+ Sadržaj memorije
! A0
| 1
|-
! A1
| 0
|-
! A2
| 0
|-
! A3
| 0
|}
P0 upisuje podatak A0 u memoriju (flush), a zatim čita podatak A2 iz memorije radi upisa (WM).

==== Trenutak 5 ====
{| class="wikitable"
|+ Sadržaj keševa
! colspan="3" | P0
! colspan="3" | P1
! colspan="3" | P2
! colspan="3" | P3
|-
| A2 || S || 1
| A2 || S || 1
| A0 || I || 0
| || ||
|-
| || ||
| || ||
| || ||
| || ||
|}
{| class="wikitable"
|+ Sadržaj memorije
! A0
| 1
|-
! A1
| 0
|-
! A2
| 1
|-
! A3
| 0
|}
P0 upisuje podatak A2 u memoriju (flush), kako bi P1 taj podatak zatim pročitao (RM).

==== Trenutak 6 ====
{| class="wikitable"
|+ Sadržaj keševa
! colspan="3" | P0
! colspan="3" | P1
! colspan="3" | P2
! colspan="3" | P3
|-
| A0 || S || 1
| A2 || S || 1
| A0 || I || 0
| || ||
|-
| || ||
| || ||
| || ||
| || ||
|}
{| class="wikitable"
|+ Sadržaj memorije
! A0
| 1
|-
! A1
| 0
|-
! A2
| 1
|-
! A3
| 0
|}
P0 čita podatak A0 iz memorije (RM).

==== Trenutak 7 ====
{| class="wikitable"
|+ Sadržaj keševa
! colspan="3" | P0
! colspan="3" | P1
! colspan="3" | P2
! colspan="3" | P3
|-
| A0 || S || 1
| A2 || S || 1
| A0 || I || 0
| || ||
|-
| A1 || S || 0
| || ||
| || ||
| || ||
|}
{| class="wikitable"
|+ Sadržaj memorije
! A0
| 1
|-
! A1
| 0
|-
! A2
| 1
|-
! A3
| 0
|}
P0 čita podatak A1 iz memorije (RM).

==== Trenutak 8 ====
{| class="wikitable"
|+ Sadržaj keševa
! colspan="3" | P0
! colspan="3" | P1
! colspan="3" | P2
! colspan="3" | P3
|-
| A0 || S || 1
| A2 || S || 1
| A0 || I || 0
| || ||
|-
| A1 || S || 0
| || ||
| || ||
| || ||
|}
{| class="wikitable"
|+ Sadržaj memorije
! A0
| 1
|-
! A1
| 0
|-
! A2
| 1
|-
! A3
| 0
|}
P0 čita podatak A0 iz svog keša (RH).

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

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

KockaAdmiralac: rank -> size

KockaAdmiralac: Ova tabela je bila prekopirana sa prethodnog K2

KockaAdmiralac: Moja rešenja K2 2019 (Allreduce u šestom pozajmljen od Alekse)