1 Flashcards
(14 cards)
Šta je sekvencijalno , a šta paralelno izvršavanje ?
Sekvencijalno izvršavanje podrazumeva da se sledeća računarska operacija ili programska
naredba izvršava tek nakon što je prethodna završena. Sekvencijalni program ima samo jedan
sekvencijalni tok izvršavanja u vremenu . Paralelno izvršavanje je „istovremeno“ izvršavanje više
računarskih operacija, sekvenci operacija, programa ili delova jednog programa .
Koja tri elementa ima svaki koordinacioni model u distribuiranom programiranju?
Svaki koordinacioni model ima tri elementa:
Entitete čiji se rad koordinira (procesi, niti, agenti, itd.) .
Koodrinacione medijume (kanali, deljene promenljive, prostori podataka, itd.) .
Pravila koordinacije (skup primitiva za upis i čitanje u prostor podataka, itd.) .
Šta je virtuelna deljena memorija?
Virtuelna deljena memorija je prostor rezervisan samo za podatke . Osim pasivnih objekata, može
da sadrži i aktivne delove programa .
Zašto ubrzanje višenitnog programa na multiprocesorskom sistemu
sa n procesora nikada nije n puta u odnosu na izvršavanje na jednoprocesorskom sistemu?
U višenitnom programu uvek dolazi do konflikta usled pristupa deljenim hardverskim ili
sofverskim resursima . Da bi se takvi konflikti razrešili, niti koje su u konfliktu se moraju
serijalizovati , što po Amdahlovom zakonu smanjuje stepen multiparalelizma .
Koja je svrha raspodele opterećenja kod paralelnog nalaženja prostih brojeva?
Cilj je postići ubrzanje izračunavanja od oko 10 puta na multiprocesoru od 10 procesora.
To se radi ravnomernim raspoređivanjem opterećenja, gde svaka nit testira opseg od 10^9 .
Objasnite koncept “krađe poslova” (work stealing) kao rešenje za raspodelu poslova.
Umesto da preopterećena nit deli posao, besposlena nit ga krade . Svaka nit ima svoj rezervoar
spremnih poslova iz kojeg uzima posao bez sinhronizacije. Ako joj nestane poslova, ukrade od
nekoga drugoga, po slučajnom izboru.
Šta je ABA problem i kako se rešava?
ABA problem nastaje kada više niti konkurentno pristupa deljenoj memoriji.
Nit T1 pročita vrednost A iz deljene memorije, zatim T2 promeni vrednost iz A u B, pa ponovo u A. Kada T1 nastavi izvršavanje, ne vidi da je vrednost deljene promenljive u međuvremenu bila menjana, što
može da dovede do nekorektnog izvršavanja.
Rešava se dodavanjem polja sa žigom (stamp). Kada
se polje promeni, vrednost žiga se uveća za jedan, čime se obezbeđuje da se ista referenca na vrh
reda nikada ne ponavlja .
Dat je pseudokod za Test-and-Set spin lock algoritam: Objasniti
anomaliju sa slike gde vreme dohvatanja ključa u multiprocesorskom/ višenitnom sistemu nije
konstantno, već progresivno raste sa porastom broja niti.
Anomalija nastaje zato što se ključ čuva u operativnoj memoriji. Multiprocesori pristupaju
operativnoj memoriji preko zajedničke magistrale , koja postaje usko grlo sistema.
Iako multiprocesori imaju lokalni keš, kada se izmeni vrednost ključa, sve lokalne kopije postaju
nevažeće (invalidirane). Zbog toga svi procesori moraju da dohvate novu vrednost ključa, što
izaziva zagušenje magistrale i dovodi do anomalije.
Pritom, magistrali ne pristupaju samo niti koje čekaju u spin lock-u, već i druge niti koje imaju potrebu za pristupanjem memoriji .
Koja je svrha Cache Coherence protokola kod multiprocesora sa keširanom memorijom?
Cache Coherence protokol služi za održavanje konzistentnosti keširanih podataka. Kada neki
procesor menja svoju kopiju podataka, protokol invalidira ostale keširane kopije tog podatka,
sprečavajući konfuziju. Na taj način, procesor može dalje da menja svoju keširanu vrednost bez
upotrebe magistrale.
Zašto je Test-and-Test-and-Set (TTAS) ključ bolji od jednostavnog TAS ključa po pitanju
performansi?
Iako su logički ekvivalentni po pitanju korektnosti , TTAS ima mnogo bolje performanse . TTAS ključ
omogućava nitima da spinuju nad svojim lokalnim keševima dok je ključ zauzet, čime se izbegava
izlazak na magistralu i smanjuje saobraćaj na njoj. Tek kada ključ postane slobodan, nit pokušava
da ga preuzme putem magistrale, ali bez neprestanog opterećenja magistrale tokom čekanja.
Objasnite koncept “lažnog deljenja” (false sharing) i kako se izbegava.
Lažno deljenje nastaje kada se različiti podaci, koje koriste različite niti, nalaze u istoj keš liniji .
Zbog koherentnosti keša, svaka izmena jednog podatka u toj liniji dovodi do invalidacije cele keš
linije u drugim procesorima, što izaziva pojačan saobraćaj na magistrali i keš promašaje .
Izbegava se dopunjavanjem (padding) elemenata niza tako da se različite elemente mapiraju u različite linije
keša, sprečavajući da lokacije pripadnu istoj liniji keša .
Pitanje: Koje su dobre, a koje loše osobine ALock-a ?
Dobre osobine: J ednostavan je, lak za implementaciju, smanjuje broj nepotrebnih invalidacija
na minimum, čime minimizuje interval između oslobađanja ključa i njegovog preuzimanja .
Garantuje da nema izgladnjivanja i omogućuje fer pristup upotrebom FCFS (First-Come-FirstServed) .
Loše osobine: Nije prostorno efikasan . Zahteva poznatu granicu maksimalnog broja
konkurentnih niE ( n ), pri čemu svakom ključu dodeljuje niz te veličine .
Sinhronizacija L različiEh objekata zahteva O( L n) prostor, čak i kada nit u jednom trenutku
pristupa samo jednom ključu .
Koja je glavna razlika između CLHLock i MCSLock u načinu predstavljanja reda čekanja?
Kod CLHLock-a , status svake niE se snima u objekat QNode sa Bool ean poljem l oc ked , a red
čekanja je apstraktan. Svaka nit spinuje čekajući na lokaciji svog prethodnika . Kod MCSLock-a ,
ključ je **ulančana lista objekata ** QNode , gde svaki QNode predstavlja nit koja drži ključ
ili čeka na preuzimanje ključa. Za razliku od CLHLock-a, ovde lista nije virtuelna, već je
predstavljena pomoću globalnih QNode objekata, tj. preko njihovih nex t polja . MCSLock je
pogodniji za NUMA arhitekture bez keša jer svaka nit kontroliše lokaciju nad kojom će da spinuje.
Koje su prednosti Pekarskog algoritma i zašto nije praktičan?
Pekarski algoritam je koncizan, elegantan i fer . Obezbeđuje First-Come-FirstServed princip tako
što niti uzimaju broj i čekaju dok oni sa manjim brojem ne budu usluženi . MeđuEm, nije praktičan
jer je potrebno čitati N različitih varijabli.
