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

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

1. zadatak

Veoma slično pitanje našlo se na prvom kolokvijumu 2021. godine

Postavka

Opisati pet klasa savremenih računara sa naglaskom na projektne prioritete u svakoj klasi.

Rešenje

Videti ovde.

2. zadatak

Postavka

Objasniti šta je ILP i navesti tipične primere. Objasniti i obrazložiti trendove iskorišćenja ILP za povećanje performansi nekada i sada.

Rešenje

ILP (Instruction-level parallelism) je paralelizam u obliku istovremenog izvršavanja više instrukcija. Drugim rečima, cilj ILP je povećanje broja izvršenih instrukcija po taktu. Primeri tehnika ILP-a su: protočna obrada, izvršavanje instrukcija van poretka, spekulativno izvršavanje, predikcija skoka i optimizacije prevodioca radi boljeg iskorišćavanja prethodnih tehnika.

ILP je imao najveći značaj u periodu od kraja 80-ih do ranih 2000-ih. Tehnološki trendovi dozvoljavali su veliko usložnjenje organizacije procesora, sa ciljem da povećaju ILP i broj instrukcija po taktu. Danas, poboljšanja performansi od ILP je sve manje i manje, jer se povećanjem broja instrukcija po taktu ne dobija znatno ubrzanje.

3. zadatak

Postavka

Objasniti prednosti i nedostatke programskog modela zajedničke memorije.

Rešenje

Prednosti:

• Globalni adresni prostor olakšava programiranje
• Uniforman pristup podacima, bez potrebe da se kopiraju i maršaluju kao na modelu prenosa poruka.
• Manji komunikacioni overhead (bez OS, bibliotečkih rutina)
• Prirodna nadogradnja na sekvencijalno programiranje (lakše se paralelizuje postojeći kod)
• Omogućava keširanje
• Može da emulira ostale programske modele

Mane:

• Složeniji hardver
• Teže skalira povećanjem broja procesora
• Zahteva posebne atomske operacije za sinhronizaciju
• Programer odgovoran za pravilan pristup deljenim podacima
• Teže optimizovati implicitnu komunikaciju

4. zadatak

Postavka

Nacrtati i objasniti tipičnu strukturu sistema koji podržava model prenosa poruka. Po čemu se ona razlikuje od NUMA arhitekture?

Rešenje

(Slika: P02 - PPM, slajd 42)

Gradivni element u modelu prenosa poruka je kompletan računar. Računarima su odvojeni adresni prostori i komuniciraju eksplicitnim I/O operacijama preko mreže.

Organizacija je slična NUMA arhitekturama, ali postoje razlike:

• Komunikacija u NUMA sistemima se odnosi na pristup memoriji, ne na razmenu poruka.
• Jača je sprega između procesora i mreže kod prenosa poruka.

5. zadatak

Postavka

Korišćenjem OpenMP tehnologije, paralelizovati kod u prilogu koji vrši obilazak i obradu čvorova grafa BFS metodom. Obratiti pažnju na efikasnost i korektnost paralelizacije. Smatrati da su sve promenljive ispravno deklarisane.

queue<node*> q;
q.push(head);
while (!q.empty()) {
    qSize = q.size();
    for (int i = 0; i < qSize; i++) {
        node* currNode = q.front();
        q.pop();
        doStuff(currNode);
        q.push(currNode);
    }
}

Rešenje

Ovaj kod za obradu čvorova BFS metodom nije ispravan, jer sve vreme cirkuliše isti čvor u redu, a i nema nikakvog smisla vraćati čvor koji je već bio u redu nazad u taj red. Ukoliko zanemarimo te probleme, i pretpostavimo da se u doStuff radi samo obrada a ne i neko guranje čvorova u red, ovaj zadatak se može paralelizovati OpenMP poslovima, slično kodu za obilaženje ulančane liste:

queue<node*> q;
q.push(head);
#pragma omp parallel
{
#pragma omp single
{
while (!q.empty()) {
    qSize = q.size();
    for (int i = 0; i < qSize; i++) {
        node* currNode = q.front();
        q.pop();
        #pragma omp task
        doStuff(currNode);
        q.push(currNode);
    }
}
}
}

6. zadatak

Postavka

Koji model memorijske konzistencije podržava OpenMP i kakav to uticaj može imati na izvršavanje koda niti? Da li postoje direktive kojima se može uticati na izvršavanje niti u smislu održavanja konzistentnog pogleda na memoriju? Obrazložiti odgovor.

Rešenje

OpenMP podržava model relaksirane konzistencije, tako da ne moraju sve niti da vide isti sadržaj memorije. Ukoliko je nitima neophodno, mogu da koriste flush direktivu koja sinhronizuje pogled niti na memoriju. Ova direktiva je implicitna prilikom nailaska na razne sinhronizacione direktive i pri ulasku i izlasku iz paralelnog regiona. Nije dobro koristiti flush direktivu kad nije apsolutno neophodno.

7. zadatak

Овај задатак није решен. Помозите SI Wiki тако што ћете га решити.

Postavka

Neka se posmatra jedna aplikacija koja vrši obradu čvorova grafa. Grafovi koji se obrađuju su veoma neujednačenog stepena čvorova, a vreme obrade je proporcionalno stepenu čvora. 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, 95% 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 16 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. Diskutovati uticaj balansa opterećenja na performanse aplikacije, ukoliko je raspodela čvorova po stepenu kao na grafiku sa slike. Predložiti i obrazložiti šemu paralelizacije kojom bi se poboljšale performanse.

Rešenje

Sp = T1/T16
T1 = 1s
T16 = alfa*T1 + (1-alfa)/N
N=16
alfa = 0.05
T16 = 0.05*T1 + (0.95)*T1/16
S = T1/T16 = 9.14
drugi nacin: Sp = 1/ ((1 - P) + P/N)
N = 16
P = 0.95
Sp = 1 / (0.05 + 0.95/16)
Sp = 9.14

Posto je graf neujednacen, neki core-ovi mogu biti vise optereceni, dok su drugi idle. Zato ovde treba koristiti dinamicku raspodelu zadataka, tako da kada jedna nit(core), zavrsi, odmah trazi sledeci cvor koji treba da obradi. Na ovaj nacin, ni jedan core nikad nece biti idle.