Multiprocesorski sistemi/K2 2021

Izvor: SI Wiki
Pređi na navigaciju Pređi na pretragu

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 P1 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 i 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.

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

Kada bi se pojavio novi procesor koji želi da čita neki podatak, koji je drugi procesor već izmenio u svom kešu, MESI protokol bi morao da uradi upis tog podatka u memoriju pre nego što pređe u S stanje. Dodavanje novog stanja koje označava samo vlasništvo a ne i eksluzivnost nad tim podatkom bi odložilo ovaj upis. Tako je nastalo stanje O:

  • U ovo stanje se prelazi kada se u stanju M detektuje čitanje podatka na magistrali. Time procesor zadržava vlasništvo nad podatkom ali, logično, gubi eksluzivnost.
  • Prilikom čitanja podatka u ovom stanju, procesor ne mora da menja stanje ili izlazi na magistralu, jer već ima ažuran podatak.
  • Prilikom pisanja podatka u ovom stanju se prelazi nazad u stanje M i poništavaju sve ostale kopije preko magistrale.
  • Prilikom detekcije čitanja u ovom stanju, opslužuje se zahtev za podatkom na magistrali iz svog keša i ostaje se u istom stanju.
  • Prilikom detekcije pisanja u ovom stanju, podatak se upisuje u memoriju (flush) i prelazi se u I stanje. Ovo se takođe radi ukoliko neki drugi procesor zahteva poništavanje tog podatka preko magistrale.

3. zadatak

Postavka

Objasniti 4C model promašaja u keš memorijama. Objasniti svaku vrstu promašaja kao i načn 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.

Rešenje

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 W0, W1 i W2, kao i privatnim prostorima koji sadrže podatke A, W2 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).

Preuzeto iz „https://siwiki.rs/w/index.php?title=Мултипроцесорски_системи/К2_2021&oldid=6949”