Мултипроцесорски системи/К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

Do problema keš koherencije čak i kada se radi o privatnim podacima može doći na sledeća dva 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 promašaja u keš memorijama se odnosi na 4 uzroka promašaja u keš memorijama:

1. Compulsory: Ovo je promašaj koji se događa kada se podatak prvi put dovlači u keš memoriju - ovakav promašaj je neizbežan. Ovi promašaji se mogu smanjiti povećanjem veličine bloka koji može da stane u jednu keš liniju - logično, tako bi se više podataka odjednom dovuklo u keš i to onda potencijalno može pretvoriti višestruke Compulsory promašaje u jedan.
2. Capacity: Ovo je promašaj koji se događa zbog ograničene veličine keš memorije - ukoliko je radni skup našeg programa (veličina memorije koju on koristi) veći od veličine cele keš memorije, moguće je da se dogodi da se neki blok u kešu zameni nekim drugim čak i kada bi keš memorija bila potpuno asocijativna (što bi značilo da bilo koji blok sme da se smesti u bilo koju keš liniju) jer prosto nema dovoljno mesta u kešu da se u njemu u jednom trenutku nađe naš čitav radni skup. Ovi promašaji se mogu smanjiti povećanjem veličine keš memorije.
3. Conflict: Ovo je promašaj koji se događa zbog ograničene set-asocijativnosti keš memorije. Mapiranje blokova u keš linije može biti direktno, set-asocijativno ili potpuno asocijativno. Kod direktnog mapiranja, svaki blok sme da se smesti u tačno jednu keš liniju i jasno je da tada imamo najviše promašaja zbog konflikta jer će tada maksimalan broj blokova biti mapiran na jednu keš liniju i oni će se svi međusobno izbacivati iz keša (ovde je veličina seta 1). Kod set-asocijativnog mapiranja jedan blok može da se smesti na bilo koju od keš linija koje pripadaju istom setu (set predstavlja ništa drugo nego skup keš linija), pa je jasno da će tada za veće setove biti sve manje promašaja usled konflikta jer svaki blok ima sve više opcija gde može da se smesti u kešu. Kod potpuno asocijativnog mapiranja svaki blok može da se smesti u bilo koju keš liniju u okviru keša jer je tu veličina seta maksimalna - jednaka je veličini cele keš memorije. Kod ovakvog mapiranja promašaji usled konflikta ne mogu uopšte da se dogode, logično, jer nijedan blok nije mapiran ni u jednu konkretnu keš liniju, već svaki može da se smesti u bilo koju slobodnu keš liniju. Međutim, zbog velike hardverske složenosti potrebne za implementaciju potpuno asocijativnog mapiranja, uglavnom se koristi set-asocijativno mapiranje. Ovi promašaji se očigledno smanjuju povećanjem veličine seta.
4. Coherence: Ovo je promašaj koji se događa zbog deljenja podatka između više procesora. Ovo deljenje može biti pravo ili lažno. Kod pravog deljenja zaista jedan isti podatak aktivno menja više procesora. Promašaji nastali usled pravog deljenja mogu da se smanje povećanjem veličine bloka jer tako ako je npr. deljen niz dužine 8 memorijskih reči i jedan procesor izmeni svaku reč u nizu, drugi procesor mora da dohvati čitav niz, pa će to uraditi sa dva promašaja ukoliko je veličina bloka 4 memorijske reči, a sa jednim promašajem ako je veličina bloka 8 memorijskih reči. Promašaji usled pravog deljenja se mogu smanjiti i softverski tako što programer smanji količinu deljenih podataka između procesora. Kod lažnog deljenja procesori koriste različite podatke koji pripadaju istom bloku, pa se onda događaju invalidacije ili ažuriranja (u zavisnosti od tipa korišćenog protokola za održavanje keš koherencije) čitavog bloka uvek iako procesori modifikuju različite podatke. Promašaji usled lažnog deljenja se mogu smanjiti smanjenjem veličine bloka. Lažno deljenje bi bilo u potpunosti otklonjeno ako bi veličina bloka bila jednaka veličini jedne memorijske reči, ali takvo keširanje ne bi bilo isplativo, pa se to ne radi.

Compulsory, Capacity i Conflict promašaji postoje i kod jednoprocesorskih i kod multiprocesorskih sistema, dok Coherence promašaji postoje samo kod multiprocesorskih sistema.

4. zadatak

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

• Motivacija: Ne može se reći da su generalno poništavajući protokoli za održavanje keš koherencije bolji od ažurirajućih ili obratno, zato što direktno zavisi od karakteristika same aplikacije koji tip protokola je bolje primeniti. Osnovni kriterijum koji se razmatra pri odabiru tipa protokola jeste procesorska lokalnost, tj. koliko se podaci koriste od strane samo jednog procesora. Indikator procesorske lokalnosti je dužina upisnog niza (write run), tj. koliko puta neki procesor uspe da upiše u dati podatak pre nego što ga neki drugi procesor zatraži za čitanje ili upis. Poništavajući protokoli su efikasniji za duže upisne nizove (npr. ako je dužina upisnog niza 20, jednom bismo javili ostalim procesorima na početku da invalidiraju svoje kopije, pa bismo onda lokalnim, jeftinim upisima u našu keš memoriju menjali podatak i onda bismo ga dostavili procesoru koji ga zatraži nakon naših 20 upisa; ovo je dosta efikasnije nego kada bismo koristili ažurirajući protokol jer bi se tada bespotrebno na svaki naš upis slala vrednost podatka svim procesorima iako nijednom ne treba ništa drugo osim vrednosti podatka nakon našeg poslednjeg, tj. 20. upisa). Ažurirajući protokoli su efikasniji za kraće upisne nizove (npr. ako je dužina upisnog niza 1, nakon svake izmene podatka u našem kešu slali bismo novu vrednost svim procesorima koji imaju kopiju tog podatka i u ovom slučaju je to odlično jer će svakako uvek neki drugi procesor zatražiti taj podatak nakon samo jednog našeg upisa, a ovako će ga tada uvek pronaći u svom kešu; ovo je dosta efikasnije nego kada bismo koristili poništavajući protokol jer bi onda vrednost podatka u ostalim procesorima nakon svakog upisa našeg procesora bila invalidirana, što znači da bi svi ostali procesori naredni put kada im zatreba taj podatak uvek promašili u svojim keševima). Sada kada znamo šta tačno znači procesorska lokalnost, jasno je da ona može biti promenljiva i u okviru jedne aplikacije, što znači da je moguće da nekim delovima aplikacije više odgovaraju poništavajući protokoli, a drugim ažurirajući, pa se tako došlo do ideje o adaptivnim protokolima koji bi trebalo da kombinuju oba tipa protokola kako bi potencijalno bile ostvarene bolje performanse.
• Uobičajeni način rada: Adaptivni protokoli keš koherencije obično prvo pretpostave da je dužina upisnog niza (write run) mala i zato prvo počnu sa primenom ažurirajućeg protokola. Ukoliko dužina upisnog niza poraste preko nekog unapred definisanog praga, onda se smatra da se tada više isplati poništavajući protokol i zato se onda prelazi na njegovo korišćenje. Pošto je ovo obično realizovano hardverski, transparentno je za programera, ali takođe povećava hardversku složenost sistema.
• Invalidacija u protokolu EDWP: Kao preteča EDWP (Efficient Distributed Writing Protocol) protokolu prvo se pojavio RWB (Read and Write Broadcast) protokol kod kog se već za dužinu upisnog niza od dva upisa prelazi sa ažuriranja na invalidaciju (ta promena se dogodi već pri drugom upisu). Zaključeno je da je to prerano (npr. kod sinhronizacije procesa prvo se dogodi upis vrednosti 0 u deljenu promenljivu mutex, pa onda upis vrednosti 1 od strane istog procesa na istom procesoru - tada npr. treba neki drugi proces na drugom procesoru da pročita tu vrednost mutex-a kako bi nastavio svoj rad, međutim ona je invalidirana jer je u nju pisano dva puta, pa će on promašiti u svom kešu; kada bi se tek pri trećem upisu prešlo sa ažuriranja na invalidaciju, drugi proces na drugom procesoru bi pronašao podatak u svom kešu). Kao što je bilo i očekivano, na osnovu rezultata simulacija zaključeno je da je bolje da se prelazi sa ažuriranja na invalidaciju tek pri trećem upisu i to samo kada svi procesori koji imaju kopiju tog podatka detektuju upisni niz dužine tri upisa (može se desiti da su neki procesori detektovali upisni niz dužine tri upisa, a da npr. jedan procesor prekine taj upisni niz tako što će da pročita taj podatak, pa je onda za njega upisni niz dužine nula upisa - u tom slučaju će se nastaviti sa primenom ažurirajućeg protokola sve dok nisu svi procesori (osim, naravno, onog koji upisuje u podatak) detektovali upisni niz dužine tri upisa, i tada će se preći na poništavajući protokol zbog čega će se onda invalidovati kopije u njihovim keševima).

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

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