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

Извор: SI Wiki
Пређи на навигацију Пређи на претрагу

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: ukoliko su ažurni podaci nekog procesa upisani u keš nekog drugog procesora, a proces se preuzme od strane nekog drugog procesora, migrirani proces pokušavaće da pristupi podacima koji ne samo da nisu u kešu, već njihove kopije u memoriji nisu ažurne. Ovaj problem može da se desi ako
  • Lažno deljenje: iako su podaci privatni za svaki procesor, mogu se naći u istom bloku keša.

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).

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