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

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

1. zadatak

Postavka

Objasniti princip paralelizacije kod dataflow programskog modela. Nacrtati strukturu ovakvog sistema i objasniti princip funkcionisanja.

Rešenje

Dataflow programski model postiže paralelizaciju predstavljanjem programa kao grafa sa blokovima instrukcija kao čvorovima koji mogu da se izvrše čim su im podaci spremni. Grane ovakvog grafa predstavljaju zavisnosti po podacima. Između čvorova se prosleđuje token izvršavanja, i svi čvorovi koji imaju token se izvršavaju u paraleli.

2. zadatak

Postavka

Objasniti prednosti i nedostatke primene zajedničke keš memorije u multiprocesorskim sistemima.

Rešenje

Prednosti:

• Pozitivna interferencija: podatak koji je dovukao jedan procesor može služiti i drugom.
• Nema potrebe voditi računa o koherenciji keša.
• Izbegava se lažna deljivost.

Mane:

• Negativna interferencija: podatak koji je dovukao jedan procesor može biti izbačen od strane drugog.
• Što je keš memorija veća to je i sporija.
• Svi procesori pristupaju istoj keš memoriji, pa im je propusni opseg zajedno ograničen

3. zadatak

Postavka

Kakva je motivacija za unapređenje u protokolu MESIF? Objasniti semantiku dodatnog stanja. Precizno objasniti sve akcije koje su vezane za ove stanje i nacrtati samo deo dijagrama stanja vezan za ovo stanje.

Rešenje

U MESI protokolu se u S stanju nije znalo ko će prilikom operacije Transfer, odnosno prenošenja podatka iz jedne u drugu keš memoriju, biti taj koji prenosi podatak. Novouvedeno stanje F (forward) je isto kao S osim što služi da označi procesor koji će raditi to prosleđivanje podatka preko magistrale. Dodeljuje se procesoru koji je poslednji pročitao podatak, tako da se u ovo stanje ulazi čim se pročita podatak sa magistrale, a iz njega izlazi čim se detektuje čitanje ili upis.

4. zadatak

Postavka

Diskutovati kako se reorganizacijom deljenih struktura podataka sa mogućnostima upisa u multiprocesorskom sistemu mogu poboljšati performanse u sledećim slučajevima: a) niz stuktura^[sic] sa dva polja kojima pristupaju dva različita procesa i b) niz čiji elementi su manji od veličine bloka kojima pristupaju različiti procesi.

Rešenje

Niz struktura sa po dva polja se može pretvoriti u dva niza, tako da svaki procesor pristupa drugačijem delu memorije i neće izbacivati jedan drugog iz respektivnih keš memorija (izazivati lažnu deljivost). Niz sa elementima manjim od veličine bloka se može izmeniti tako da svaki element sadrži dovoljno praznog prostora (padding) unutar sebe da procesori ne dohvate elemente ostalih procesora prilikom dohvatanja svojih.

5. zadatak

Postavka

Korišćenjem MPI tehnologije paralelizovati funkciju u prilogu koja vrši pronalaženje svih indeksa u string str na kojima se nalazi znak c. 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. Pronađeni indeksi u rezultujućem nizu treba da odgovaraju ulaznom nizu. Smatrati da alokacije memorije uvek uspevaju.

int* find_all_occurences(char* str, char c) {
    int* loc = malloc(sizeof(int) * strlen(str)), j = 0;
    for (int i = 0; i < strlen(str); i++) {
        if (str[i] == c) {
            loc[j++] = i;
        }
    }
    loc = realloc(loc, (j + 1) * sizeof(int));
    loc[j] = -1;
    return loc;
}

Rešenje

#define MASTER 0

int* find_all_occurences(char* str, char c, int length, int* locSize) {
    int rank;
    MPI_Comm_rank(MPI_COMM_WORLD, &rank);
    int* loc = malloc(sizeof(int) * length);
    *locSize = 0;
    for (int i = 0; i < length; i++) {
        if (str[i] == c) {
            loc[(*locSize)++] = i + rank * length;
        }
    }
    return loc;
}

int main(void) {
    // ...
    MPI_Status status;
    int size;
    int rank;
    MPI_Comm_size(MPI_COMM_WORLD, &size);
    MPI_Comm_rank(MPI_COMM_WORLD, &rank);
    char *str, c;
    if (rank == MASTER) {
        // Input str, c
    }
    int length = strlen(str);
    int chunk = length / size;
    MPI_Bcast(&chunk, 1, MPI_INT, MASTER, MPI_COMM_WORLD);
    MPI_Bcast(&c, 1, MPI_CHAR, MASTER, MPI_COMM_WORLD);
    char* myStr;
    if (rank == MASTER) {
        myStr = str;
        for (int i = 1; i < size; ++i) {
            MPI_Send(str + i * chunk, chunk, MPI_CHAR, i, 0, MPI_COMM_WORLD);
        }
    } else {
        myStr = malloc(chunk * sizeof(char));
        MPI_Recv(myStr, chunk, MPI_CHAR, MASTER, 0, MPI_COMM_WORLD, &status);
    }
    int locSize = 0;
    int* loc = find_all_occurences(myStr, c, chunk, &locSize);
    if (rank == MASTER) {
        int totalLocSize = locSize;
        loc = realloc(loc, length * sizeof(int));
        for (int i = 1; i < size; ++i) {
            int otherLocSize;
            MPI_Recv(&otherLocSize, 1, MPI_INT, i, 1, MPI_COMM_WORLD, &status);
            MPI_Recv(loc + totalLocSize, otherLocSize, MPI_INT, i, 2, MPI_COMM_WORLD, &status);
            totalLocSize += otherLocSize;
        }
        loc = realloc(loc, (totalLocSize + 1) * sizeof(char));
        loc[totalLocSize] = -1;
    } else {
        MPI_Send(&locSize, 1, MPI_INT, MASTER, 1, MPI_COMM_WORLD);
        MPI_Send(loc, locSize, MPI_INT, MASTER, 2, MPI_COMM_WORLD);
        free(loc);
    }
    free(str);
    // ...
}

6. zadatak

Postavka

Kakva je uloga bafera prilikom MPI komunikacije između tačno dva procesa (point-to-point komunikacije)? Kakvu vrstu komunikacije baferi omogućavaju? Da li programer svestan postojanja bafera? Odgovor ilustrovati slikom.

Rešenje

Sistemski bafer u MPI služi za asinhrono primanje i slanje podataka, ali takođe služe i za rukovanje situacijom kada procesu stignu poruke koje ne može odmah da obradi. Sistemski bafer je transparentan za programera.

7. zadatak

Postavka

Dat je multiprocesorski sistem sa 4 identična procesora, koji koristi MOESI 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. P0,R,A0
2. P2,R,A0
3. P0,W,A0
4. P1,R,A0
5. P0,W,A0
6. P0,W,A2
7. P0,R,A1
8. P2,W,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	2	6	33%	RM, WH, WH, flush, WM, RM
P1	0	1	0%	Transfer
P2	0	2	0%	Transfer, WM
P3	0	0	0%

Trenutak 1

Sadržaj keševa

P0			P1			P2			P3
A0	E	0

Sadržaj memorije

A0	0
A1	0
A2	0
A3	0

P0 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 pokušao da pristupi memoriji kako bi dohvatio podatak sa A0, ali ga je P0 keš opslužio umesto memorije (Transfer).

Trenutak 3

Sadržaj keševa

P0			P1			P2			P3
A0	M	1				A0	I	0

Sadržaj memorije

A0	0
A1	0
A2	0
A3	0

P0 je u svoj keš upisao vrednost A0 i nije pristupao memoriji (WH), već samo poništio ostale kopije na magistrali (BusUpgr).

Trenutak 4

Sadržaj keševa

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

Sadržaj memorije

A0	0
A1	0
A2	0
A3	0

P1 je pokušao da pristupi memoriji kako bi dohvatio podatak sa A0, ali ga je P0 keš opslužio umesto memorije (Transfer).

Trenutak 5

Sadržaj keševa

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

Sadržaj memorije

A0	0
A1	0
A2	0
A3	0

P0 je u svoj keš upisao vrednost A0 i nije pristupao memoriji (WH), već samo poništio ostale kopije na magistrali (BusUpgr).

Trenutak 6

Sadržaj keševa

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

Sadržaj memorije

A0	2
A1	0
A2	0
A3	0

P0 je prvo odradio upis svog lokalnog podatka u memoriju (flush), a zatim dohvatio podatak A2 iz memorije radi upisa (WM).

Trenutak 7

Sadržaj keševa

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

Sadržaj memorije

A0	2
A1	0
A2	0
A3	0

P0 čita podatak A1 iz memorije (RM).

Trenutak 8

Sadržaj keševa

P0			P1			P2			P3
A2	M	1	A0	I	1	A0	M	3
A1	E	0

Sadržaj memorije

A0	2
A1	0
A2	0
A3	0

P2 čita podatak A0 iz memorije radi upisa (WM).