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

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

1. zadatak

Postavka

Objasniti promenu principa projektovanja procesora koji favorizuju paralelno procesiranje.

Rešenje

Industrija je naišla na tri glavne prepreke pri povećanju kapaciteta procesora, power wall (struja je skupa, tranzistori su jeftini), memory wall (operacije sa memorijom su mnogo skuplje od operacija procesora) i ILP wall (dobici od paralelizma na nivou instrukcija su sve manji). Tu je uočena potreba da se ide ka slabijim višejezgarnim procesorima umesto jačim jednojezgarnim, pošto performanse procesora napreduju mnogo sporije nego ranije i takt više ne može da raste toliko brzo kao ranije, dok se na paralelizaciji programa mogu dobiti mnogo veći dobici u performansama.

2. zadatak

Postavka

Šta je pretpostavka Gustafson-ovog zakona? Izvesti i precizno objasniti ovaj zakon.

Rešenje

Gustafson-ov zakon pretpostavlja da paralelni deo programa raste sa brojem procesora. To znači da ako za procesor sa $p$ jezgara uzmemo da se program izvršava $T_p = \alpha T + \left(1 - \alpha\right) T$ gde je $\alpha$ procenat sekvencijalnog koda u aplikaciji, onda se za procesor sa jednim jezgrom taj isti program izvršava $T_1 = \alpha T + \left(1 - \alpha\right) pT$. Ubrzanje je onda $S_p = \frac{T_1}{T_p} = \frac{\alpha T + \left(1 - \alpha\right) pT}{\alpha T + \left(1 - \alpha\right) T} = \frac{\alpha T + \left(1 - \alpha\right) pT}{T} = \alpha + \left(1 - \alpha\right) p$. Ovo znači da $\lim_{p \to +\infty} S_p = +\infty$, ali ova pretpostavka važi samo za skalabilne aplikacije.

3. zadatak

Postavka

Opisati tehnološke trendove u procesorskoj tehnologiji i njihove posledice.

Rešenje

• Trend u procesorskoj tehnologiji je bio smanjenje veličine tranzistora. Smanjenjem veličine tranzistora možemo da spakujemo više tranzistora na istu količinu mesta i na taj način pravimo jače procesore. Nažalost, smanjenjem tranzistora oni menjaju svoje elektronske karakteristike, kola u kojima se oni koriste postaju nestabilnija i postoji ograničenje do kojeg se veličina tranzistora može smanjivati.
• Trend je takođe bio povećanje takta procesora, povećavajući broj izvršenih instrukcija po sekundi. Nažalost, kako su procesori rasli tako je raslo i kašnjenje između logičkih kola, i to predstavlja problem za povećanje takta procesora, koje je poslednje decenije usporilo. Takođe se dešava sa povećavanjem takta da se veća energija disipira na tako maloj površini, pa je procesoru potrebno mnogo bolje hlađenje, i tu takođe nailazimo na power wall.

4. zadatak

Postavka

Dati uporedni pregled karakteristika programskih modela zajedničke memorije i prenosa poruka. U čemu se razlikuju arhitekture i organizacije sistema koji direktno podržavau^[sic] ove modele.

Rešenje

Pregled karakteristika

Karakteristika	Zajednička memorija	Prenos poruka
Pristup memoriji	Direktan pristup istoj memoriji	Direktan pristup svojoj memoriji, posredstvom poruka pristup tuđim memorijama
Sinhronizacija	Moraju se koristiti odvojene strukture (kapaciteti operativnog sistema i hardvera) kako bi se pristup memoriji sinhronizovao	Implicitna, jer razmenjuju poruke
Kopiranje podataka	Nije potrebno, drugi imaju pristup istoj memoriji kao mi	Potrebno, jer jedino tako drugi mogu da dobiju sadržaj naše privatne memorije
Identitet	Procesi ne (moraju da) znaju jedan za drugog	Procesi znaju jedan za drugog
Arhitektura i organizacija	Složenija, postoje UMA i NUMA varijante kako bi procesori delili memoriju između sebe i potrebno je održavati koherenciju keš memorija	Manje složena, pošto procesori eksplicitno zahtevaju jedni od drugih memoriju koja im je potrebna, ali je zato softver koji to radi složeniji

5. zadatak

Postavka

Korišćenjem OpenMP tehnologije, paralelizovati funkciju u prilogu koji računa vrednost određenog integrala korišćenjem Simpsonovog 1/3 pravila. Obratiti pažnju na efikasnost i korektnost paralelizacije. Smatrati da su sve promenljive ispravno deklarisane.

float simpsons(float ll, float ul, int n) {
    float h = (ul - ll) / n, x[10], fx[10];
    for (int i = 0; i <= n; i++) {
        x[i] = ll + i * h; fx[i] = func(x[i]);
    }
    float res = 0;
    for (int i = 0; i <= n; i++) {
        if (i == 0 || i == n) res += fx[i];
        else if (i % 2 != 0) res += 4 * fx[i];
        else res += 2 * fx[i];
    }
    res = res * (h / 3);
    return res;
}

Rešenje

Sledeće rešenje je pisano pod uslovom da su deklaracije x i fx kao nizove od 10 brojeva simbolične i da n zapravo sme da bude veće 10, jer inače paralelizacija ovog programa ne bi imala nikakvog smisla.

float simpsons(float ll, float ul, int n) {
    float h = (ul - ll) / n, x[10], fx[10];
    #pragma omp parallel for default(none) shared(x, fx, ll, ul, n, h)
    for (int i = 0; i <= n; i++) {
        x[i] = ll + i * h; fx[i] = func(x[i]);
    }
    float res = 0;
    #pragma omp parallel for default(none) shared(fx) reduction(+:res)
    for (int i = 0; i <= n; i++) {
        if (i == 0 || i == n) res += fx[i];
        else if (i % 2 != 0) res += 4 * fx[i];
        else res += 2 * fx[i];
    }
    res = res * (h / 3);
    return res;
}

6. zadatak

Postavka

Da li i na koji način OpenMP podržava ugneždeni paralelizam? Da li je moguće u okviru paralelnog regiona pokrenuti novi paralelni region i pod kojim uslovima?

Rešenje

OpenMP podržava ugneždeni paralelizam, u smislu da je moguće ugnezditi paralelni region unutar drugog paralelnog regiona. Pri ugneždavanju će se stvoriti tim niti sa jednom niti u njemu, osim ukoliko ugneždavanje nije omogućeno korišćenjem omp_set_nested(true) funkcije, ili OMP_NESTED promenljive okruženja. Neke implementacije ne podržavaju ove metode ugneždavanja, i u njima će ugneždeni tim niti uvek imati jednu nit.

7. zadatak

Postavka

Neka se posmatra jedna aplikacija za prikupljanje i agregaciju podataka sa interneta. Aplikacija se sastoji od veb tragača (web crawler) koji prikuplja određene informacije na internetu, a zatim se radi obrada. Nakon merenja performansi sekvencijalne implementacije posmatrane aplikacije pri uobičajenoj upotrebi, dobijeni su sledeći rezultati: aplikacija 45% vremena provodi obavljajući ulazno-izlazne operacije (sekvencijalno prikupljanje podataka iz jednog izvora), a 55% vremena provodi u obradi podataka. Tipično vreme obrade jednog paketa podataka korišćenjem jednog jezgra je 1s.

1. Ukoliko se aplikacija paralelizuje za izvršavanje na SMP sistemu sa 8 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.
2. Da li i na koji način može organizovati paralelno izvršavanje sekvencijalnog dela aplikacije, ukoliko paketi sa interneta mogu nezavisno da se obrađuju? Smatrati da paketi imaju neujednačeno vreme obrade i diskutovati moguće načine paralelne obrade.

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.45$ i $p = 8$ maksimalno ubrzanje koje možemo da postignemo je $S_p = \frac{8}{0.45 \cdot 8 + 1 - 0.45} \approx 1.93$.

Aplikacija može da održava osam niti, od kojih jedna nit radi primanje podataka preko interneta i kako pristižu paketi ubacuje ih u neku deljenu strukturu i nekom sinhronizacionom primitivom signalizira da ima paketa za obradu (slično bag of tasks pristupu korišćenjem programskog modela deljene memorije). Ostalih sedam niti mogu da iz ove vreće zadataka preuzimaju pakete za obradu i obrađuju ih paralelno. Bez obzira na to što paketi imaju neujednačeno vreme obrade, niti ne moraju da čekaju jedna na drugu tako da dok jedna nit obrađuje zahtevniji paket ostale niti ne zavise od nje (ne postoji bottleneck). Više od osam niti verovatno neće ubrzati aplikaciju jer će svesti na klasičan time-sharing umesto paralelne obrade.