Multiprocesorski sistemi/K1 2021

Prvi kolokvijum 2021. godine održan je 2. novembra i trajao je 105 minuta. Postavka roka je dostupna sa stranice predmeta.

1. zadatak

Postavka

Opisati pet tipičnih klasa računara. Navesti za koje aplikacije se obično koriste, kao i najbitnije projektne ciljeve.

Rešenje

• Lični mobilni uređaji (PMD - Personal mobile devices) su prenosivi računari namenjeni za ličnu upotrebu. Najbitniji projektni ciljevi su niska cena, niska potrošnja energije i performanse u reprodukciji medija.
• Desktop računari su računari opšte upotrebe sa širokim opsegom aplikacija. Najbitniji ciljevi su odnos cene i performansi, potrošnja energije i performanse za grafiku.
• Server računari su računari za servise koji imaju velik broj korisnika i zahtevaju visok nivo pouzdanosti. Najbitniji ciljevi su propusni opseg, dostupnost/izdržljivost, potrošnja energije.
• Klasteri ili WSC (Warehouse Scale Computing) su skupovi više hiljada računara povezanih na LAN. Koriste se za SaaS (Software as a Service). Najbitniji ciljevi su dostupnost, odnos cena i performansi, potrošnja energije.
• IoT/ugrađeni računari se koriste u uređajima široke upotrebe, najčešće dizajnirani za specifične svrhe. Najbitniji ciljevi su niska cena, niska potrošnja energije i performanse specifične za njihovu primenu.

2. zadatak

Postavka

Opisati istorijske trendove u arhitekturi računara u pogledu ostvarivanja paralelizma obrade.

Rešenje

U VLSI računarskim sistemima prisutan je trend povećavanja paralelizma.

Najpre se pojavilo povećavanje bit paralelizma. Proširivanjem staze podataka i širine registara smanjen je broj instrukcija, a samim tim i taktova neophodnim za izvršenje poslova. Ovaj trend je trajao do poznih 1980ih, sa ključnim trenutkom kada ceo mikroprocesor i keš memorija staju na jedan čip.

Nakon toga je nastupio trend paralelizma na nivou instrukcije (ILP). Cilj je bio povećati broj instrukcija po taktu, što je postignuto protočnom obradom, izvršavanjem van poretka itd. Procesori bivaju znatno složeniji i potrošnja resursa je povećana.

Ranih 2000ih dostignut je vrhunac poboljšanja performansi sa ILP i prelazi se na paralelizam na nivou niti (TLP).

3. zadatak

Postavka

Nacrtati UMA i NUMA arhitekture. Objasniti sličnosti i razlike između njih.

Rešenje

Pregled karakteristika

Karakteristika	UMA	NUMA
Način pristupa memoriji	Direktan pristup svakoj memorijskoj lokaciji.	Memorija je distribuirana, lokalni i udaljeni pristup.
Brzina pristupa	Nekeširan pristup ima istu cenu za svaku lokaciju.	Lokalni pristup je brži (direktan pristup), udaljeni sporiji (preko poruka na ICN).
Propusni opseg	Zahteva veći jer svi pristupi idu kroz ICN/magistralu.	Manja potreba za brzim ICN.
Skalabilnost	Teže se skalira, usko grlo je obično magistrala/interconnect mreža.	Mnogo bolje skalira.

4. zadatak

Postavka

Objasniti programski model Data parallel. Nacrtati i objasniti tipičnu arhitekturu koja podržava ovaj model.

Rešenje

Data Parallel programski model se odnosi na izvršavanje iste operacije nad različitim podacima u paraleli kako bi se brže obradila cela struktura podataka.

Postoje specijalni procesori (array processors) koji su, za razliku od klasičnih opštenamenskih procesora, optimizovani upravo za programski model Data Parallel u kojem je neophodna brza obrada velike količine podataka.

Data Parallel programski model je naročito primenjiv za razna naučna istraživanja u kojima se masovno radi nad nizovima i matricama.

Arhitektura ovakvih array processor-a je SIMD (Single Instruction Multiple Data) jer niti izvršavaju iste instrukcije nad različitim podacima. Postoji jedan kontrolni procesor koji je zadužen za upravljanje i raspoređivanje podataka na ostale procesore čija je jedina uloga izračunavanje na osnovu podataka koji su im dodeljeni i smešteni u njihovim lokalnim memorijama.

5. zadatak

Postavka

Korišćenjem OpenMP tehnologije, paralelizovati deo koda u prilogu koji pronalazi parametar alfa sa zadovoljavajućom tačnošću u metodu konjugovanih gradijenata. Obratiti pažnju na efikasnost i korektnost paralelizacije. Paralelizaciju obaviti ručnim raspoređivanjem posla nitima. Smatrati da su sve promenljive ispravno deklarisane.

bool alfaSet = false;
int alfaIter = 0;
int step = 1;
double localAlfa = alfa;
double *testX = (double *) malloc(dim * sizeof(double));

while (!alfaSet) {
    alfaIter += step;
    localAlfa = pow(gamma, alfaIter - 1);

    for (i = 0; i < dim; i++) {
        testX[i] = x[i] + localAlfa * d[i];
    }
    
    if (func(testX, dim) - delta * localAlfa * b <= oldFunc) {
        if (!alfaSet) {
            alfaSet = true;
            alfaIter = 0;
            alfa = localAlfa;
        }
    }
}
free(testX);

Rešenje

Ukoliko pretpostavimo da se pod ručnim raspoređivanjem poslova misli na nekorišćenje worksharing direktiva i OpenMP poslova, i takođe da je potrebno da nađemo jedno alfa umesto prvog alfa koje zadovoljava uslove, jedna mogućnost je:

#include <omp.h>
bool alfaSet = false;
#pragma omp parallel
{
int alfaIter = 0;
int step = 1;
double localAlfa = alfa;
double *testX = (double *) malloc(dim * sizeof(double));
alfaIter = omp_get_thread_num();
step = omp_get_num_threads();

while (!alfaSet) {
    alfaIter += step;
    localAlfa = pow(gamma, alfaIter - 1);

    for (i = 0; i < dim; i++) {
        testX[i] = x[i] + localAlfa * d[i];
    }
    
    if (func(testX, dim) - delta * localAlfa * b <= oldFunc) {
        #pragma omp critical (alfa_set_sync)
        if (!alfaSet) {
            alfaSet = true;
            alfaIter = 0;
            alfa = localAlfa;
        }
    }
}
free(testX);
}

6. zadatak

Postavka

Na koji način se promenljive podrazumevano prosleđuju u okviru OpenMP task direktive? Zbog čega je to neophodno i da li je uvek neophodno? Obrazložiti odgovor.

Rešenje

Promenljive se podrazumevano prosleđuju kao firstprivate, odnosno privatne kopije promenljivih dobijaju početnu vrednost. Ovo ima smisla jer se poslovi mogu izvršavati u neodređenom, kasnijem trenutku kada prosleđena promenljiva može biti van dosega. Ovakve deljenje nije uvek neophodno jer kao i u ostalim direktivama za podelu posla, ponegde su neophodni deljeni podaci.

7. zadatak

Postavka

Neka se posmatra jedna numerička simulacija. Aplikacija najpre učitava parametre simulacije, zatim rešava složene sisteme linearnih diferencijalnih jednačina i na kraju upisuje rezultate svoga rada. Nakon merenja performansi sekvencijalne implementacije posmatrane aplikacije pri uobičajenoj upotrebi, dobijeni su sledeći rezultati: aplikacija 5% vremena provodi obavljajući ulazno-izlazne operacije, a 95% vremena provodi u obradi podataka. Tipično vreme obrade u okviru simulacije korišćenjem jednog jezgra je 1000s.

1. Ukoliko se aplikacija paralelizuje za izvršavanje na SMP sistemu sa 4 jezgara na 2GHz sa 32GB memorije, navesti formulu za Amdalov zakon i odrediti maksimalno moguće ubrzanje koje se može postići za zadatu aplikaciju sa datom konfiguracijom.
2. Šta predstavlja osobina skalabilnosti u kontekstu paralelnog računarstva i specifično paralelnog hardvera? Da li bi dodavanje novih procesorskih jezgara u slučaju pod a) doprinelo ubrzavanju opisane paralelne aplikacije i u kojim slučajevima?

Rešenje

Formula za Amdalov zakon glasi:

• $T_p = \alpha T_1 + (1 - \alpha) \frac{T_1}{p}$
• $S_p = \frac{T_1}{T_P} = \frac{1}{\alpha + \frac{1 - \alpha}{p}} = \frac{p}{\alpha p + 1 - \alpha}$

Kako je nama ovde $\alpha = 0.05$ i $p = 4$ maksimalno ubrzanje koje možemo da postignemo je $S_p = \frac{4}{0.05 \cdot 4 + 1 - 0.05} \approx 3.47$.

Skalabilnost u paralelnom računarstvu se odnosi na mogućnost paralelnog sistema da proporcionalno ubrza svoj rad sa dodavanjem novih procesora (resursa) u sistem. Specifično, za paralelni hardver misli se na povećanje broja jezgara, povećanje propusnog opsega i slično. U ovom slučaju, dodavanje novih procesorskih jezgara bi značajno doprinelo ubrzanju ove aplikacije, jer se u najvećem delu može paralelizovati njen kod. Uslov da se aplikacija zaista i ubrza je, naravno, da se taj kod koji može da se paralelizuje zaista i paralelizuje.