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

Prvi kolokvijum 2019. godine održan je 29. oktobra i trajao je 105 minuta. Postavka roka dostupna je sa stranice predmeta.

1. zadatak

Postavka

Objasniti kako je nastao power wall i kako to utiče na projektovanje procesora.

Rešenje

Povećanjem takta procesora se povećava količina snage koja se disipira na površini procesora i zato je potrebno bolje hlađenje i više strujne energije kako bi procesor radio. Power wall na taj način ograničava takt procesora, jer vazdušno hlađenje kao i količina struje koje jedan procesor sme da povuče ima svoje granice.

2. zadatak

Postavka

Koje dve klase paralelizma preovladjuju^[sic] u aplikacijama? Koje vrste paralelizma se prepoznaju pri izvršavanju nu^[sic] računarima?

Rešenje

Dve klase paralelizma u aplikacijama su paralelizam na nivou podataka kao i zadataka, dok se pri izvršavanju na računarima prepoznaju kao paralelizam na nivou instrukcije, niti, zahteva, kao i vektorske arhitekture.

3. zadatak

Postavka

Objasniti šta je paralelni programski modeli.^[sic] Objasniti šta su implicitni, a šta eksplicitni modeli, šta su njihove prednosti i nedostaci.

Rešenje

Programski model je skup apstrakcija koje omogućavaju programeru da na uprošćen i transparentan način vidi softver i hardver. Paralelan programski model je programski model koji programeru specifično pomaže sa apstrahovanjem paralelizma u programima. Implicitni programski modeli su oni koji omogućavaju paralelizam u programu bez intervencije programera, automatskom detekcijom delova za paralelizaciju i njihovim paralelizovanjem. Nažalost, teško je napraviti da ovakvi modeli dostignu zadovoljavajući nivo ubrzanja. Eksplicitni programski modeli zahtevaju od programera da definiše delove i načine za paralelizaciju, što je sa jedne strane mnogo više posla za programera ali sa druge dostiže mnogo veće nivoe paralelizma.

4. zadatak

Postavka

Objasniti šta je programski model paralelnih programa i tipičnu arhitekturu sistema koju podrazumeva.

Rešenje

Videti ovde.

5. zadatak

Postavka

Korišćenjem OpenMP tehnologije, paralelizovati kod u prilogu koji vrši određenu vrstu Laplasove transformacije nad zadatom matricom. Obratiti pažnju na efikasnost i korektnost paralelizacije. Smatrati da su sve promenljive ispravno deklarisane.

int iter = 0;
while (error > tol && iter < iter_max) {
    error = 0.0;
    for (int j = 1; j < n-1; j++) {
        for (int i = 1; i < m-1; i++) {
            Anew[j][i] = 0.25 * (A[j][i+1] + A[j][i-1] + A[j-1][i] + A[j+1][i]);
            double diff;
            if ((Anew[j][i] - A[j][i]) > 0.0) {
                diff = Anew[j][i] - A[j][i];
            } else {
                diff = A[j][i] - Anew[j][i];
            }
            if (diff > error) error = diff;
        }
    }
    for (int j = 1; j < n-1; j++) {
        for (int i = 1; i < m-1; i++) {
            A[j][i] = Anew[j][i];
        }
    }
    iter++;
}

Rešenje

int iter = 0;
while (error > tol && iter < iter_max) {
    error = 0.0;
    #pragma omp parallel default(none) shared(A, Anew, n, m) reduction(min:error)
    {
    #pragma omp for collapse(2)
    for (int j = 1; j < n-1; j++) {
        for (int i = 1; i < m-1; i++) {
            Anew[j][i] = 0.25 * (A[j][i+1] + A[j][i-1] + A[j-1][i] + A[j+1][i]);
            double diff;
            if ((Anew[j][i] - A[j][i]) > 0.0) {
                diff = Anew[j][i] - A[j][i];
            } else {
                diff = A[j][i] - Anew[j][i];
            }
            if (diff > error) error = diff;
        }
    }
    #pragma omp for collapse(2)
    for (int j = 1; j < n-1; j++) {
        for (int i = 1; i < m-1; i++) {
            A[j][i] = Anew[j][i];
        }
    }
    }
    iter++;
}

6. zadatak

Postavka

Na koji način nowait odredba može uticati na direktive na koje se odnosi? Navesti kada je ova odredba upotrebljiva i obrazložiti odgovor.

Rešenje

nowait direktiva diktira da na kraju određenog regiona OpenMP koda ne treba da se vrši implicitna sinhronizacija kao što se inače vrši na kraju for, sections i single regiona. Ova direktiva je upotrebljiva kada nam ovakva implicitna sinhronizacija nije potrebna i možemo pustiti više niti da prođe taj region kako bismo ih onda kasnije negde eksplicitno sinhronizovali. Na primer, možemo pustiti niti da prođu kroz više blokova asociranih sa for direktivama ako te petlje ne zavise jedna od druge, a zatim ih sinhronizovati na nekoj barijeri ispod.

7. zadatak

Postavka

Neka se posmatra jedna aplikacija koja vrši obradu velikih matrica koje predstavljaju određenu 2D medicinsku sliku. Nakon merenja performansi sekvencijalne implementacije posmatrane aplikacije pri uobičajenoj upotrebi, dobijeni su sledeći rezultati: aplikacija 15% vremena provodi obavljajući ulazno-izlazne operacije, 85% vremena provodi u obradi podataka. Tipično vreme obrade jednog čvora korišćenjem jednog jezgra je 1s.

1. Ukoliko se aplikacija paralelizuje za izvršavanje na SMP sistemu sa 64 jezgara na 3GHz sa 32GB memorije, navesti formulu za Amdalov zakon i odrediti maksimalno moguće ubrzanje koje se može postići za zadatu aplikaciju.
2. Objasniti različite načine za dekompoziciju domena u kontekstu obrade 2D slike i objasniti kako to može imati uticaja na performanse izvršavanja aplikacije. Kako različiti načini dekompozicije mogu da utiču na performanse keširanja podataka?

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.15$ i $p = 64$ maksimalno ubrzanje koje možemo da postignemo je $S_p = \frac{64}{0.15 \cdot 64 + 1 - 0.15} \approx 6.12$.

Dvodimenzionalne matrice mogu da se podele na različite načine: po redovima, po kolonama, po blokovima, ciklično... na performanse aplikacije, doduše može da utiče način keširanja podataka tokom njihovog dohvatanja. Elementi matrice su generalno podaci koji se nalaze blizu jedan do drugog ukoliko im se pristupa na određen način (u C je to po redovima) i zato je za performanse keširanja podataka najbolje deliti tim redom. Ukoliko elementi matrice imaju malu neujednačenost u potrebnom vremenu obrade, ciklična podela može da pomogne tako da svaka nit ima mogućnost da zahvati i delove koji zahtevaju manje i delove koji zahtevaju više obrade.