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

Drugi kolokvijum 2019. godine održan je 3. decembra. Trajao je 105 minuta i postavka je dostupna sa 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 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: $\sum_{n = 0}^{\infty} \frac{(-1)^n}{2n + 1} = \frac{\pi}{4}$

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^[sic] podatke, raspodeljuje ih ostalim procesima, a svi procesi trebaju da dobiju finalni rezultat rada.

Rešenje

#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;
}

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.

#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);
    }
    // ...
}

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

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	S	0	A0	S	0

Sadržaj memorije

A0	0
A1	0
A2	0
A3	0

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

Trenutak 3

Sadržaj keševa

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

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

Sadržaj keševa

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

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

Sadržaj keševa

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

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

Sadržaj keševa

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

Sadržaj memorije

A0	1
A1	0
A2	1
A3	0

P0 čita podatak A0 iz memorije (RM).

Trenutak 7

Sadržaj keševa

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

Sadržaj memorije

A0	1
A1	0
A2	1
A3	0

P0 čita podatak A1 iz memorije (RM).

Trenutak 8

Sadržaj keševa

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

Sadržaj memorije

A0	1
A1	0
A2	1
A3	0

P0 čita podatak A0 iz svog keša (RH).