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

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

1. zadatak

Postavka

Objasniti kako može doći do problema keš koherencije čak i kada se radi o privatnim podacima.

Rešenje

Dva moguća načina:

• Migracija procesa: Do problema keš koherencije može doći čak i kada je reč o privatnim podacima zbog migracije procesa sa jednog procesora na drugi - to se može dogoditi npr. kada raspoređivač procesa pokuša da poboljša balans opterećenja u sistemu. Neka postoji podatak na adresi A0 u operativnoj memoriji sa vrednošću 0 i neka ga trenutno nijedan procesor nema u svom kešu. Neka se proces P0 nalazi na procesoru Proc1 sa keš memorijom C0. On može da dovuče podatak u keš i izmeni mu vrednost na 1 samo u svom kešu tako da podatak u memoriji sada nije ažuran. Neka se sada dogodi migracija procesa P0 sa procesora Proc0 na procesor Proc1 sa keš memorijom C1. Ako proces P1 sada pokuša da pročita podatak, prvo će ga potražiti u kešu C1, pa pošto ga tu neće pronaći pročitaće ga iz memorije, a pošto podatak u memoriji nije ažuran, sistem će ući u nekonzistentno stanje i time upravo nastaje problem keš koherencije.
• Lažno deljenje: Do problema keš koherencije može doći čak i kada je reč o privatnim podacima zbog pojave "lažne deljivosti". Neka proces na procesoru Proc0 upisuje u podatak koji je u memoriji na adresi A0 i neka ga ima u svom kešu. Neka proces na procesoru Proc1 upisuje u podatak koji je u memoriji na adresi A1 i neka ga ima u svom kešu. Neka je veličina jednog bloka koji keševi dohvataju i smeštaju u jednu keš liniju veličine dve susedne memorijske lokacije. To bi značilo da, iako procesor Proc0 menja samo podatak sa adrese A0, a procesor Proc1 samo podatak sa adrese A1 (dakle, različite podatke) svaka takva modifikacija biće detektovana kao problem keš koherencije koji treba razrešiti iako tog problema uopšte nema, pa onda dolazi do bespotrebnog poništavanja ili ažuriranja podataka u zavisnosti od protokola koji se koristi za obezbeđivanje keš koherencije. Ovog problema ne bi bilo kada bi veličina bloka koji dohvataju keševi bila veličine jedne memorijske reči, ali je onda pitanje koliko bi bilo korisno takvo keširanje - zato je potrebno dobro razmisliti pri projektovanju keš memorije kolika bi trebalo da bude veličina jedne keš linije kako bi se istovremeno što bolje iskoristilo keširanje, ali isto tako i smanjila pojava "lažnog deljenja".

2. zadatak

Postavka

Objasniti motivaciju za stanje O u protokolu MOESI. Kakva je semantika ovog stanja? Precizno opisati sve prelaze iz ovog stanja i prelaze u ovo stanje.

Rešenje

Kod MESI protokola imamo sledeću situaciju: ukoliko je neka keš linija na nekom procesoru u stanju M i neki drugi procesor zatraži podatak koji se nalazi u toj keš liniji za čitanje, prvi procesor bi (pre prelaska u stanje S) uradio operaciju flush kojom bi istovremeno ažurirao memoriju i dostavio podatak procesoru koji ga je tražio za čitanje. Memorija mora da se ažurira kod MESI protokola u ovoj situaciji, jer ako se to ne bi uradilo bilo bi moguće da sistem uđe u nekonzistentno stanje u slučaju kada su sve keš linije sa tim podatkom u stanju S jer tada nijedna keš linija nema vlasništvo nad podatkom, tj. nije odgovorna za taj podatak. Ako je to slučaj, i dodatno podatak se ne nalazi u memoriji, može da se dogodi zamena blokova u ovim keš linijama koje su u stanju S i onda bismo trajno izgubili ažurnu vrednost podatka.

Zato se kod MOESI protokola uvodi stanje O koje ima semantiku vlasništva, tj. odgovornosti nad podatkom, ali ne i ekskluzivnosti. Zbog ovog stanja u opisanoj situaciji nije potreban upis u memoriju jer se odgovornost nad podatkom dodeljuje procesoru kod koga je keš linija bila u stanju M i zato će taj procesor tek kad zaista bude bio neophodan upis u memoriju to i uraditi (dakle, odloženo u odnosu na MESI protokol) i zato garantovano neće nikad doći do trajnog gubitka ažurnog podatka.

Prelazi vezani za stanje O:

• U stanje O se prelazi iz stanja M kada neki drugi procesor zatraži podatak za čitanje - tada procesor kod koga je keš linija bila u stanju M šalje podatak procesoru koji ga je tražio za čitanje (BusRd/Transfer). Prelaskom keš linije iz stanja M u stanje O procesor zadržava vlasništvo nad podatkom ali, logično, gubi ekskluzivnost.
• Prilikom čitanja u stanju O, keš linija ostaje u istom stanju i nema nikakvih bočnih efekata (PrRd/--) jer keš ima ažuran podatak.
• Prilikom upisa u stanju O, prelazi se u stanje M i šalje se signal BusUpgr na magistralu da bi ostali procesori invalidirali svoje kopije podatka (PrWr/BusUpgr).
• Prilikom detekcije čitanja u stanju O, ostaje se u istom stanju i prosleđuje se podatak iz keša direktno u keš procesora koji je zatražio podatak za čitanje (BusRd/Transfer).
• Prilikom detekcije pisanja u stanju O, prelazi se u stanje I i radi se operacija flush (BusRdX/Flush) - ovo je situacija kada neki procesor kod koga je keš linija sa ovim podatkom bila u stanju I zatraži upis u dati podatak (tada je potreban flush jer keš tog procesora nema ažuran podatak). Prilikom detekcije signala BusUpgr se samo prelazi u stanje I bez ikakvih bočnih efekata (BusUpgr/--) - ovo je situacija kada neki procesor kod koga je keš linija sa ovim podatkom bila u stanju S zatraži upis u dati podatak (tada nije potreban flush jer keš tog procesora već ima ažuran podatak).

3. zadatak

Postavka

Objasniti 4C model promašaja u keš memorijama. Objasniti svaku vrstu promašaja kao i način da se broj promašaja pojedine vrste smanji.

Rešenje

4C model označava četiri uzorka promašaja u kešu:

1. Compulsory: Ukoliko se podatak po prvi put dovlači u keš memoriju. Ova vrsta promašaja je neophodna i ne može se smanjiti.
2. Capacity: Ukoliko je u keš memoriji ponestalo kapaciteta. Može se smanjiti povećanjem kapaciteta keš memorije.
3. Conflict: Ukoliko je došlo do konflikta prilikom set-asocijativnosti. Može se smanjiti smanjiti povećanjem set-asocijativnosti keš memorije.
4. Coherence: Ukoliko je podatak izbačen usled prave ili lažne deljivosti. Prava deljivost se može smanjiti promenom softvera tako da manje deli podatke, a lažna deljivost se može smanjiti promenom veličine bloka keša.

4. zadatak

Овај задатак није решен. Помозите SI Wiki тако што ћете га решити.

Postavka

Objasniti motivaciju za adaptivne protokole keš koherencije. Kakav je njihov uobičajeni način rada? Objasniti kako dolazi do invalidacije u protokolu EDWP.

5. zadatak

Postavka

Korišćenjem MPI tehnologije paralelizovati funkciju u prilogu koja vrši određenu vrstu interpolacije korišćenjem sinusne transformacije. 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. Smatrati da alokacije memorije uvek uspevaju.

double* sin_trans_interpolation(int n, double a, double b, double fa, double fb, double s[], int nx, double x[]) {
    double angle, f1, f2, pi = 3.141592653589793, *value;
    int i, j;
    value = new double[nx];
    for (i = 0; i < nx; i++) {
        f1 = f1_calc(a, b, fa, fb, x[i]); f2 = 0.0;
        for (j = 0; j < n; j++) {
            angle = angle_calc(a, b, j, x[i], pi);
            f2 = f2 + s[j] * sin (angle);
        }
        value[i] = f1 + f2;
    }
    return value;
}

Rešenje

int main(void) {
    // ...
    int size;
    int rank;
    MPI_Comm_size(MPI_COMM_WORLD, &size);
    MPI_Comm_rank(MPI_COMM_WORLD, &rank);
    int n, nx = 1;
    double a, b, fa, fb, s[...], x[...];
    if (rank == MASTER) {
        // Input n, a, b, fa, fb, n, nx, s, x
    }
    int ints[] = {n, nx};
    double doubles[] = {a, b, fa, fb};
    MPI_Bcast(ints, 2, MPI_INT, MASTER, MPI_COMM_WORLD);
    MPI_Bcast(doubles, 4, MPI_DOUBLE, MASTER, MPI_COMM_WORLD);
    MPI_Bcast(s, n, MPI_DOUBLE, MASTER, MPI_COMM_WORLD);
    int count = ints[1] / size;
    double* recvX = new double[count];
    MPI_Scatter(x, count, MPI_DOUBLE, recvX, count, MPI_DOUBLE, MASTER, MPI_COMM_WORLD);
    double* value = sin_trans_interpolation(ints[0], doubles[0], doubles[1], doubles[2], doubles[3], s, count, recvX);
    double* recvVal = new double[nx];
    MPI_Gather(value, count, MPI_DOUBLE, recvVal, nx, MPI_DOUBLE, MASTER, MPI_COMM_WORLD);
    delete[] value;
    delete[] recvX;
    // ...
}

6. zadatak

Postavka

Jednostrana komunikacija

1. Na slici su prikazana tri procesa sa odgovarajućim alociranim prozorima W₀, W₁ i W₂, kao i privatnim prostorima koji sadrže podatke A, W₂ i C. Objasniti koja akcija zasnovana na PUT ili GET operaciji i od strane kog procesa je sprovedena da bi se dobilo stanje opisano slikom.
2. Da li se pristup prozoru jednog procesa mora štiti sinhronizacionim rutinama? Na koji način bi se mogao zaštiti pristup prozoru u slučaju prikazanom pod a)?

Rešenje

1. Izvršena je GET operacija od strane procesa 1.
2. Operacije pristupa ne garatuju sekvencijalan pristup od strane više procesa, pa je u tom slučaju potrebno sinhronizovati ih. Za sinhronizaciju je moguće koristiti LOCK/UNLOCK operacije ili fence.

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

• 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

Napomena: Uzeli smo pretpostavku da operacija flush samo upiše ažuran podatak u memoriju i uopšte ga ne prosledi drugom kešu koji ga je tražio, već će on morati da pristupi memoriji da bi pročitao tu vrednost. Moguća je i drugačija implementacija kod koje bi procesor koji uradi flush takođe i prosledio odmah procesoru koji je tražio podatak tu vrednost i onda taj drugi procesor uopšte ne bi pristupao memoriji jer bi imao taj podatak u svom kešu - tada bismo kod njega imali RH umesto RM pri pristupu tom podatku. Ako isprobate sekvence pristupa iz zadatka u Vivio simulatoru 5.1 videćete da flush funkcioniše ovako.

CPU	Broj pogodaka	Ukupan broj pristupa	Hit rate	Pristupi memoriji
P0	1	5	20%	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
			A1	S	0

Sadržaj memorije

A0	0
A1	0
A2	0
A3	0

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

Trenutak 2

Sadržaj keševa

P0			P1			P2			P3
A1	M	1	A1	I	0

Sadržaj memorije

A0	0
A1	0
A2	0
A3	0

P0 je pristupio memoriji kako bi dohvatio podatak u koji je hteo da upiše (WM).

Trenutak 3

Sadržaj keševa

P0			P1			P2			P3
A1	M	2	A1	I	0

Sadržaj memorije

A0	0
A1	0
A2	0
A3	0

P0 je pokušao da pristupi memoriji radi upisa u A1, ali je taj podatak već bio u njegovom kešu (WH).

Trenutak 4

Sadržaj keševa

P0			P1			P2			P3
			A0	S	0
A1			A1	I	0

Sadržaj memorije

A0	0
A1	0
A2	0
A3	0

P1 je pristupio memoriji radi čitanja A0 (RM).

Trenutak 5

Sadržaj keševa

P0			P1			P2			P3
A0	S	0	A0	S	0
A1	M	2	A1	I	0

Sadržaj memorije

A0	0
A1	0
A2	0
A3	0

P0 je pristupio memoriji radi čitanja A0 (RM).

Trenutak 6

Sadržaj keševa

P0			P1			P2			P3
A0	S	0	A0	S	0
A1	S	2	A1	S	2

Sadržaj memorije

A0	0
A1	2
A2	0
A3	0

P0 je pristupio memoriji kako bi upisao izmenjenu vrednost A1 (flush), nakon čega je P1 pristupio kako bi tu vrednost pročitao (RM).

Trenutak 7

Sadržaj keševa

P0			P1			P2			P3
A0	S	0	A0	S	0
A1	I	2	A1	M	3

Sadržaj memorije

A0	0
A1	2
A2	0
A3	0

P1 je izmenio A1 koji je bio u njegovoj keš memoriji (WH) a onda invalidirao ostale kopije.

Trenutak 8

Sadržaj keševa

P0			P1			P2			P3
A0	S	0	A0	S	0
A1	S	3	A1	S	3

Sadržaj memorije

A0	0
A1	3
A2	0
A3	0

P1 je pristupio memoriji kako bi upisao izmenjenu vrednost A1 (flush), nakon čega je P0 pristupio kako bi tu vrednost pročitao (RM).