Мултипроцесорски системи/К2 2018

Drugi kolokvijum 2018. godine održan je 4. decembra. Trajao je 105 minuta i postavka je dostupna sa stranice predmeta.

1. zadatak

Postavka

Opisati i objasniti dataflow paralelni programski model. Koji su nedostaci primene ovog modela.

Rešenje

Dataflow programski model predstavlja program kao graf blokova instrukcija koje se mogu izvršavati čim su njihovi podaci dostupni. Nažalost, ovaj programski model nije zaživeo u današnje vreme zbog nekoliko nedostataka:

• Ne vodi se računa o lokalnosti podataka, i time mnogo umanjuje efekat keš memorije.
• Radi se mnogo nepotrebnih izračunavanja dok se čeka na podatke koji npr. određuju da li će se izvršiti jedan ili drugi blok.
• Pošto ne postoji programski brojač, dohvatanje instrukcija iz ove memorije je mnogo složenije.

2. zadatak

Postavka

Objasniti i nacrtati kako izgleda paralelni sistem sa zajedničkom keš memorijom. Koje su prednosti ovog sistema?

Rešenje

Paralelni sistem sa zajedničkom keš memorijom ima keš memoriju kao sloj ispred obične memorije, tako da procesori kada pristupaju nekom podatku iz memorije prvo dođu do keša a zatim se pristupa memoriji ukoliko podatak nije u kešu. Prednosti ovakvog pristupa su što izbegavamo problem koherencije keša, uvodimo pozitivnu interferenciju i izbegavamo lažnu deljivost.

3. zadatak

Postavka

Objasniti pojmove validnost, vlasništvo i ekskluzivnost u protokolima za koherenciju. U donjim tabelama napisati stanja za protokole MESI i Dragon i deklarisati ih u pogledu ove tri osobine (staviti + ili – u odgovarajuće polje).

Rešenje

• Vlasništvo: jedan procesor kod sebe čuva ažurnu kopiju podatka, može da je menja kako hoće ali je njegova odgovornost da tu kopiju na kraju upiše u memoriju (write-back).
• Ekskluzivnost: samo jedan procesor kod sebe čuva jedan podatak, pa zna da ne mora da izlazi na magistralu da javlja ostalima svoje operacije nad njim.
• Validnost: procesor ima ažurnu verziju podatka kod sebe u kešu.

MESI

Stanje	validno	vlasnik	eksluzivno
M	+	+	+
E	+	-	+
S	+	-	-
I	-	-	-

Dragon

Stanje	validno	vlasnik	eksluzivno
M	+	+	+
E	+	-	+
Sc	+	-	-
Sm	+	+	-

4. zadatak

Postavka

Objasniti pojave pravog deljenja (true sharing) i lažnog deljenja (false sharing). Kako povećanje veličine bloka utiče na ove pojave.

Rešenje

Pravo deljenje je kada dva procesora rade nad istim podatkom, i zato izbacuju jedan drugom taj podatak iz keš memorije tokom održavanje koherencije. Lažno deljenje je kada dva procesora rade nad podacima koji se nalaze u istom bloku keša, i efekat je isti, ali daleko manje koristan od prave deljivosti. Povećanje veličine bloka ne utiče na pravu deljivost^[?] ali može da poveća lažnu deljivost, jer sa više podataka u jednom bloku može da dođe do češćih konflikata nad tim podacima nego kad je podataka manje.

5. zadatak

Postavka

Korišćenjem MPI tehnologije paralelizovati kod u prilogu koji vrši normalizaciju slike. Obratiti pažnju na efikasnost i korektnost 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 i sakuplja rezultat rada.

int index, n = width * height;
float mean = 0.0, var = 0.0, svar, std;
for (index = 0; index < n; index++) mean += (float)(inputImage[index]);
mean /= (float)n;
for (index = 0; index < n; index++) {
    svar = (float)(inputImage[index]) - mean;
    var += svar * svar;
}
var /= (float)n;
std = sqrtf(var);
for (index = 0; index < n; index++)
    outputImage[index] = (inputImage[index] - mean)/std;

Rešenje

int rank;
int size;
MPI_Comm_rank(MPI_COMM_WORLD, &rank);
MPI_Comm_size(MPI_COMM_WORLD, &size);
if (rank == MASTER) {
    // Input width, height, inputImage.
}
int index, n = width * height / size;
MPI_Bcast(&n, 1, MPI_INT, MASTER, MPI_COMM_WORLD);
MPI_Scatter(inputImage, n, MPI_INT, inputImageRecv, n, MPI_INT, MASTER, MPI_COMM_WORLD);
float sum = 0.0, varSum = 0.0, var, svar, std, mean;
for (index = 0; index < n; index++) sum += (float)(inputImageRecv[index]);
MPI_Allreduce(&sum, &mean, 1, MPI_FLOAT, MPI_SUM, MPI_COMM_WORLD);
mean /= (float)(n * size);
for (index = 0; index < n; index++) {
    svar = (float)(inputImageRecv[index]) - mean;
    varSum += svar * svar;
}
MPI_Allreduce(&varSum, &var, 1, MPI_FLOAT, MPI_SUM, MPI_COMM_WORLD);
var /= (float)(n * size);
std = sqrtf(var);
for (index = 0; index < n; index++)
    outputImage[index] = (inputImage[index] - mean)/std;

MPI_Gather(outputImage, n, MPI_INT, outputImageRecv, n, MPI_INT, MASTER, MPI_COMM_WORLD);

6. zadatak

Postavka

Koja je prednost korišćenja i kakve su karakteristike kolektivne komunikacije kod MPI tehnologije? Na primeru koda u prilogu kojim se svakom procesu šalje jedinstveni deo niza na obradu, komentarisati performanse i napisati alternativu koja koristi rutine za kolektivnu komunikaciju.

...
if (rank == MASTER) {
    for (i = 1; i < size; i++)
        MPI_Send(arr + i * chunk, chunk, MPI_INT, i, 1000, MPI_COMM_WORLD);
} else {
    MPI_Status status;
    MPI_Recv(buff, chunk, MPI_INT, MASTER, 1000, MPI_COMM_WORLD, &status);
}

Rešenje

Prednosti kolektivne komunikacije su što može da značajno olakša posao programeru, koji umesto da ručno piše send/receive komande može da to ostavi MPI da odradi, i korišćenjem metoda kolektivne komunikacije takođe jasnije MPI dajemo do znanja šta želimo da uradimo, pa on može da optimizuje komunikaciju na način koji je specifičan za naš problem. Gornji blok koda može se zameniti MPI_Scatter pozivom:

MPI_Scatter(arr, chunk, MPI_INT, buff, chunk, MPI_INT, MASTER, MPI_COMM_WORLD);

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:

1. P1,R,A0
2. P0,W,A0
3. P2,R,A0
4. P0,W,A2
5. P1,W,A2
6. P2,W,A1
7. P0,R,A1
8. 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

CPU	Broj pogodaka	Ukupan broj pristupa	Hit rate	Pristupi memoriji
P0	0	6	0%	WM, flush, WM, flush, RM, RM
P1	0	2	0%	RM, WM
P2	0	2	0%	RM, WM
P3	0	0	0%

Trenutak 1

Sadržaj keševa

P0			P1			P2			P3
			A0	S	0

Sadržaj memorije

A0	0
A1	0
A2	0
A3	0

P1 je pristupao memoriji kako bi dohvatio podatak sa A0 (RM).

Trenutak 2

Sadržaj keševa

P0			P1			P2			P3
A0	M	1	A0	I	0

Sadržaj memorije

A0	0
A1	0
A2	0
A3	0

P0 je pristupao memoriji kako bi dohvatio podatak sa A0 za pisanje (WM).

Trenutak 3

Sadržaj keševa

P0			P1			P2			P3
A0	S	1	A0	I	0	A0	S	1

Sadržaj memorije

A0	1
A1	0
A2	0
A3	0

P0 je pristupao memoriji kako bi upisao svoj podatak (flush) a zatim je P2 pristupio kako bi taj podatak pročitao (RM).

Trenutak 4

Sadržaj keševa

P0			P1			P2			P3
A2	M	1	A0	I	0	A0	S	1

Sadržaj memorije

A0	1
A1	0
A2	0
A3	0

P0 je pristupao memoriji kako bi pročitao podatak A2 radi upisa (WM).

Trenutak 5

Sadržaj keševa

P0			P1			P2			P3
A2	I	1	A2	M	2	A0	S	1

Sadržaj memorije

A0	1
A1	0
A2	1
A3	0

P0 je pristupao memoriji kako bi upisao svoj podatak (flush), a zatim je P1 pristupao memoriji kako bi pročitao podatak A2 radi upisa (WM).

Trenutak 6

Sadržaj keševa

P0			P1			P2			P3
A2	I	1	A2	M	2	A0	S	1
						A1	M	1

Sadržaj memorije

A0	1
A1	0
A2	1
A3	0

P2 je pristupao memoriji kako bi pročitao podatak A1 radi upisa (WM).

Trenutak 7

Sadržaj keševa

P0			P1			P2			P3
A2	I	1	A2	M	2	A0	S	1
A1	S	1				A1	S	1

Sadržaj memorije

A0	1
A1	1
A2	1
A3	0

P0 je pristupao memoriji kako bi pročitao podatak A1 (RM).

Trenutak 8

Sadržaj keševa

P0			P1			P2			P3
A0	S	1	A2	M	2	A0	S	1
A1	S	1				A1	S	1

Sadržaj memorije

A0	1
A1	1
A2	1
A3	0

P0 je pristupao memoriji kako bi pročitao podatak A0 (RM).