KockaAdmiralac: Sedmi zadatak

2022-12-07T08:55:15Z

Sedmi zadatak

KockaAdmiralac: Naziv predmeta

2022-12-07T00:29:50Z

Naziv predmeta

← Старија измена		Верзија на датум 7. децембар 2022. у 02:29
Ред 145:		Ред 145:

	[[Категорија:Рокови]]		[[Категорија:Рокови]]
	[[Категорија:~~Назив предмета~~]]~~<!-- Zameniti sa nazivom predmeta -->~~		[[Категорија:Мултипроцесорски системи]]

KockaAdmiralac: WIP, bez sedmog zadatka

2022-12-07T00:29:25Z

WIP, bez sedmog zadatka

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

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

== 1. zadatak ==
=== Postavka ===
Objasniti princip paralelizacije kod ''dataflow'' programskog modela. Nacrtati strukturu ovakvog sistema i objasniti princip funkcionisanja.

=== Rešenje ===
''Dataflow'' programski model postiže paralelizaciju predstavljanjem programa kao grafa sa blokovima instrukcija kao čvorovima koji mogu da se izvrše čim su im podaci spremni. Grane ovakvog grafa predstavljaju zavisnosti po podacima. Između čvorova se prosleđuje token izvršavanja, i svi čvorovi koji imaju token se izvršavaju u paraleli.

== 2. zadatak ==
=== Postavka ===
Objasniti prednosti i nedostatke primene zajedničke keš memorije u multiprocesorskim sistemima.

=== Rešenje ===
Prednosti:
* Pozitivna interferencija: podatak koji je dovukao jedan procesor može služiti i drugom.
* Nema potrebe voditi računa o koherenciji keša.
* Izbegava se lažna deljivost.
Mane:
* Negativna interferencija: podatak koji je dovukao jedan procesor može biti izbačen od strane drugog.
* Što je keš memorija veća to je i sporija.
* Svi procesori pristupaju istoj keš memoriji, pa im je propusni opseg zajedno ograničen

== 3. zadatak ==
=== Postavka ===
Kakva je motivacija za unapređenje u protokolu MESIF? Objasniti semantiku dodatnog stanja. Precizno objasniti sve akcije koje su vezane za ove stanje i nacrtati samo deo dijagrama stanja vezan za ovo stanje.

=== Rešenje ===
U MESI protokolu se u <code>S</code> stanju nije znalo ko će prilikom operacije <code>Transfer</code>, odnosno prenošenja podatka iz jedne u drugu keš memoriju, biti taj koji prenosi podatak. Novouvedeno stanje <code>F</code> (''forward'') je isto kao <code>S</code> osim što služi da označi procesor koji će raditi to prosleđivanje podatka preko magistrale. Dodeljuje se procesoru koji je poslednji pročitao podatak, tako da se u ovo stanje ulazi čim se pročita podatak sa magistrale, a iz njega izlazi čim se detektuje čitanje ili upis.

== 4. zadatak ==
=== Postavka ===
Diskutovati kako se reorganizacijom deljenih struktura podataka sa mogućnostima upisa u multiprocesorskom sistemu mogu poboljšati performanse u sledećim slučajevima: a) niz stuktura<sup>[sic]</sup> sa dva polja kojima pristupaju dva različita procesa i b) niz čiji elementi su manji od veličine bloka kojima pristupaju različiti procesi.

=== Rešenje ===
Niz struktura sa po dva polja se može pretvoriti u dva niza, tako da svaki procesor pristupa drugačijem delu memorije i neće izbacivati jedan drugog iz respektivnih keš memorija (izazivati lažnu deljivost). Niz sa elementima manjim od veličine bloka se može izmeniti tako da svaki element sadrži dovoljno praznog prostora (''padding'') unutar sebe da procesori ne dohvate elemente ostalih procesora prilikom dohvatanja svojih.

== 5. zadatak ==
=== Postavka ===
Korišćenjem MPI tehnologije paralelizovati funkciju u prilogu koja vrši pronalaženje svih indeksa u string str na kojima se nalazi znak c. 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 ulazne podatke, raspodeljuje ih ostalim procesima, učestvuje u obradi i sakuplja rezultate. Pronađeni indeksi u rezultujućem nizu treba da odgovaraju ulaznom nizu. Smatrati da alokacije memorije uvek uspevaju.
<syntaxhighlight lang="c">
int* find_all_occurences(char* str, char c) {
int* loc = malloc(sizeof(int) * strlen(str)), j = 0;
for (int i = 0; i < strlen(str); i++) {
if (str[i] == c) {
loc[j++] = i;
}
}
loc = realloc(loc, (j + 1) * sizeof(int));
loc[j] = -1;
return loc;
}
</syntaxhighlight>

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

int* find_all_occurences(char* str, char c, int length, int* locSize) {
int rank;
MPI_Comm_rank(MPI_COMM_WORLD, &rank);
int* loc = malloc(sizeof(int) * length);
*locSize = 0;
for (int i = 0; i < length; i++) {
if (str[i] == c) {
loc[(*locSize)++] = i + rank * length;
}
}
return loc;
}

int main(void) {
// ...
MPI_Status status;
int size;
int rank;
MPI_Comm_size(MPI_COMM_WORLD, &size);
MPI_Comm_rank(MPI_COMM_WORLD, &rank);
char *str, c;
if (rank == MASTER) {
// Input str, c
}
int length = strlen(str);
int chunk = length / size;
MPI_Bcast(&chunk, 1, MPI_INT, MASTER, MPI_COMM_WORLD);
MPI_Bcast(&c, 1, MPI_CHAR, MASTER, MPI_COMM_WORLD);
char* myStr;
if (rank == MASTER) {
myStr = str;
for (int i = 1; i < size; ++i) {
MPI_Send(str + i * chunk, chunk, MPI_CHAR, i, 0, MPI_COMM_WORLD);
}
} else {
myStr = malloc(chunk * sizeof(char));
MPI_Recv(myStr, chunk, MPI_CHAR, MASTER, 0, MPI_COMM_WORLD, &status);
}
int locSize = 0;
int* loc = find_all_occurences(myStr, c, chunk, &locSize);
if (rank == MASTER) {
int totalLocSize = locSize;
loc = realloc(loc, length * sizeof(int));
for (int i = 1; i < size; ++i) {
int otherLocSize;
MPI_Recv(&otherLocSize, 1, MPI_INT, i, 1, MPI_COMM_WORLD, &status);
MPI_Recv(loc + totalLocSize, otherLocSize, MPI_INT, i, 2, MPI_COMM_WORLD, &status);
totalLocSize += otherLocSize;
}
loc = realloc(loc, (totalLocSize + 1) * sizeof(char));
loc[totalLocSize] = -1;
} else {
MPI_Send(&locSize, 1, MPI_INT, MASTER, 1, MPI_COMM_WORLD);
MPI_Send(loc, locSize, MPI_INT, MASTER, 2, MPI_COMM_WORLD);
free(loc);
}
free(str);
// ...
}
</syntaxhighlight>

== 6. zadatak ==
=== Postavka ===
Kakva je uloga bafera prilikom MPI komunikacije između tačno dva procesa (''point-to-point'' komunikacije)? Kakvu vrstu komunikacije baferi omogućavaju? Da li programer svestan postojanja bafera? Odgovor ilustrovati slikom.

=== Rešenje ===
Sistemski bafer u MPI služi za asinhrono primanje i slanje podataka, ali takođe služe i za rukovanje situacijom kada procesu stignu poruke koje ne može odmah da obradi. Sistemski bafer je transparentan za programera.

== 7. zadatak ==
=== Postavka ===
Dat je multiprocesorski sistem sa 4 identična procesora, koji koristi ''MOESI'' 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:
# P0,R,A0
# P2,R,A0
# P0,W,A0
# P1,R,A0
# P0,W,A0
# P0,W,A2
# P0,R,A1
# P2,W,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 ===

[[Категорија:Рокови]]
[[Категорија:Назив предмета]]

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

KockaAdmiralac: Sedmi zadatak

KockaAdmiralac: Naziv predmeta

KockaAdmiralac: WIP, bez sedmog zadatka