41 - 70

Question 1

41.Ukratko objasnite i po potrebi skicirajte Bullyjev algoritam nadglasavanja,
prstenasti algoritam glasovanja, te algoritam izbora u bežičnim mrežama.

Answer 1

Bully algoritam nakon detekcije ispada trenutnog koordinatora inicira izbore. Svim cvorovima s
vecim ID-evima salje election poruku. Ako ni jedan ne odgovori, taj proces postaje koordinator.
U suprotnom, ovaj proces koji odgovori je novi koordinator.
Prstenasti algoritam glasovanja nakon detekcije ispada salje sljedecem procesu election poruku
(ili onom nakon njega ako je taj u ispadu). Ako ju proces primi, biljezi svoj broj u listu. Nakon
obilaska prstena, proces koji je poslao poruku opet prstenasto salje ID novog koordinatora
(najveci ID u prstenu) svim procesima.
Kod izbora u bezicnim mrezama, svaki cvor moze inicirati izbore slanjem election poruke
cvorovima u dometu.
● Kad cvor primi poruku, biljezi posiljatelja kao svog roditelja i salje election poruku svojim
cvorovima u dometu (osim roditelju).
● Kad cvor primi poruku, potvrdi primitak roditelju
● Kad roditelj primi poruku od svih susjeda, vrati poruku svom roditelju s najboljim
kandidatom za koordinatora
● Na kraju, inicijalni cvor dobije konacnu odluku koordinatora u ovisnosti o dostupnim
resursima. Ta informacija se prosljeduje svim dostupnim cvorovima

Question 2

Ukratko objasnite način rada GPS-a i WiFi lokacijskih usluga

Answer 2

Specijalizirani GPS sateliti konstantno šalju svoju poziciju i vrijeme. GPS receiveri pomoću minimalno 4 satelita koji daju informacije o poziciji i vremenu pomoću jednadžbe računaju položaj tog receivera.
WiFi lokacijskih usluga:
Geolokacijski sistem koji pomoću obližnjih WiFi hotspotova ili poznatih WiFi access pointa određuje lokaciju uređaja. Koristi se tamo di GPS nije adekvatan.

Question 3

Navedite i ukratko objasnite barem 3 mehanizma koji podržavaju paradigmu
raspodijeljenih objekata.

Answer 3

● Java RMI (Remote Method Invocation), objasnjeno kasnije
● Common Object Request Broker Architecture (CORBA), objasnjeno kasnije
● Simple Object Access Procotol (SOAP): komunikacijski protokol baziran na XML koji
omogucuje otvoren, prosiriv nacin za komunikaciju aplikacija preko interneta, neovisno o
jeziku ili platformi pojedinih aplikacija.

Question 4

Ukratko objasnite osnove rada Java RMI arhitekture.

Answer 4

Object-oriented implementacija RPC modela za Java programe. Object server isporucuje
remote object i registrira ih s directory uslugom. Objekt omogucuje udaljene metode koje se
mogu pozivati u klijentskim programima.
Udaljeni objekt je deklariran Java interfaceom. Taj interface implementira konkretni object
server. Object client pristupa objektu pozivajuci udaljene metode pridruzene objektu sintaksom
za RMI.

Question 5

Ukratko objasnite osnove rada CORBA sustava raspodijeljenih objekata.

Answer 5

Standardna arhitektura sustava raspodijeljenih objekata. Omogucuje suradnju raspodijeljenih
objekata u raznorodnim okruzenjima. Razlikuje se od Java RMI jer podrzava i ostale
programske jezike jer sama po sebi nema mogucnost rada s raspodijeljenim objektima, vec je
skup protokola.
Raspodijeljeni objekt se definira pomocu programske datoteke, slicno kao Java RMI, ali se
umjesto Jave koristi CORBA Interface Definition Language (zbog portabilnosti). Time se moze
implementirati u raznim konkretnim programskim jezicima.

Question 6

Objasnite osnovnu razliku između paralelne i raspodijeljene obradbe.

Answer 6

Paralelno znaci da se podaci obraduju visestrukim CPU na jednom racunalu, dok je
raspodijeljeno visestruki CPU na vise raspodijeljenih racunala (mrezom, npr). Paralelna obradba
ima vise procesora koji dijele memoriju, a raspodijeljeni imaju vise procesora od kojih svaki ima
svoju memoriju i spojeni su mrezom.

Question 7

Skicirajte načine obradbe master/worker, producer/consumer i shared queue.

Answer 7

3 SLIKE

Question 8

Skicirajte model raspodijeljenog računala, te objasnite osnovnu razliku između grozda
i spleta računala.

Answer 8

IMA SLIKA.
Zapravo dost jednostavna skica, vise fizickih racunala je spojeno nekakvom vezom izmedu
sebe kako bi mogli komunicirat i djelit podatke (mreza).
Grozd (cluster) je skup racunala povezanih lokalnom mrezom, dok je splet (grid) infrastruktura
koja omogucuje pristup racunalnim resursima na svakom mjestu (WAN).

Question 9

Ukratko objasnite osnovne modele (paradigme) paralelnih programa.

Answer 9

● Komunikacijama porukama (message passing) je vjerojatno najkoristeniji model
paralelnog programiranja. Vise zadataka se izvrsava istovremeno, a podaci se
razmjenjuju porukama. SPMD (Single Program Multiple Data)
● Podatkovni paralelizam (data parallelism) - primjena iste operacije na vise elemenata
podatkovne strukture (npr. pomnozi sve elemente polja s 2).
● Zajednicka memorija - svi procesori/zadaci dijele isti memorijski spremnik. Potrebna
zastita memorije (npr. semafori).
● Sustav zadataka i kanala (tasks and channels) - usmjereni graf gdje su cvorovi zadaci, a
veze kanali kojima oni komuniciraju.

Question 10

Napišite i ukratko objasnite izraze za ubrzanje prema Amdahlovom zakonu.

Answer 10

● ubrzanje = 1/(1-P) gdje je P paralelni udio programa
● ubrzanje = 1/(S + P/N) gdje je:
○ S slijedni udio programa
○ P paralelni udio programa
○ N broj procesora

Question 11

Navedite osnovne korake pretvorbe slijednog algoritma u paralelni, te ih
prodiskutirajte kroz primjer.

Answer 11

1. Pronaci dijelove programa koji se mogu izvoditi istodobno
2. Rastaviti algoritam (funkcionalna i podatkovna dekompozicija)
3. Ostvarenje programa
4. Ispravljanje gresaka, optimizacija izvodenja

Question 12

Navedite i ukratko objasnite barem 2 tipa dekompozicije problema za rad na
paralelnoj platformi.

Answer 12

Funkcionalna dekompozicija - podjela problema na manje dijelove koji se mogu rjesavati
istodobno
● Podatkovna dekompozicija - podjela podataka s kojima algoritam radi na manje dijelove

Question 13

Objasnite pojam funkcionalne dekompozicije problema prilikom prilagodbe
serijskog programa paralelnom izvođenju.

Answer 13

Funckionalna dekompozicija se odnosi na podjelu programske logike na manje dijelove koji se
mogu rjesavati istodobno. Zatim se, ako je to potrebno, vrsi raspodjela podataka.

Question 14

Objasnite pojam raščlanjivanja domene problema prilikom prilagodbe serijskog
programa paralelnom izvođenju.

Answer 14

-Rasclanjivanje domene problema se odnosi na podjelu podataka koji se trebaju paralelno
obradivati izmedu dostupnih procesora.
-Ovdje definiramo zadatke koji su zaduzeni za odgovarajuci dio podataka.
-Potrebno definirati oblik komunikacije

Question 15

Navedite osnovne značajke nakupina računala (engl. cluster), te ukratko opišite barem
3 vrste od njih.

Answer 15

skup računala povezan lokalnom mrežom
manji broj računala koja su identična ili vrlo slična
veća brzina komunikacije
npr. Google search engine, Cray XK7, BlueGene/Q

● Nakupine visokih performansi (HPC cluster) - za rudarenje nad podacima, paralelnu
obradbu, modeliranje klimatskih promjena
● S raspodjelom opterecenja (load balancing) - performanse u obliku raspodjele
opterecenja, FTP i Web posluzitelji
● Visokoraspolozive nakupine (high availability) - sprjecavaju ispade usluga, imaju zalihost

Question 16

Što je OpenMP i koje su njegove 3 glavne komponente?

Answer 16

API za paralelno programiranje viseprocesorskih sustava s dijeljenom memorijom.
Komponente:
● prevoditeljske smjernice (direktive) #pragma
● biblioteka podrzanih funkcija
● varijable okoline (run-time)

Question 17

Navedite osnovne elemente programske okoline OpenMP-ja

Answer 17

● model izvodenja (paralelne regije, sintaksa, varijable okoline)
● smjernice za podjelu poslova (pragme, koja petlja izvodi koji izraz?)
● podatkovna okolina i kombinirani konstrukcijski elementi (privatne i dijeljene varijable,
kombinirane paralelne smjernice dijeljenja poslova)

Question 18

Objasnite i pokažite primjer korištenja smjernice (pragma) za paraleliziranje for petlje.

Answer 18

pragma omp parallel for

for (int i = 0; i < n; i++) {
a[i] = 2;
}

Question 19

Napišite i objasnite ulogu funkcija omp_get_num_procs() i omp_set_num_threads().

Answer 19

● omp_get_num_procs() -> dohvati broj fizicki dostupnih procesora
● omp_set_num_threads() -> postavi broj niti izvodenja za sljedecu paralelnu regiju

Question 20

Navedite opcije (klauzule) smjernice definiranja vidljivosti varijabli i pokažite
primjer uporabe private.

Answer 20

shared i private.
int j = 0;
#pragma omp parallel for private(j)
for (int i = 0; i < n; i++) {
j++;
}

Question 21

Objasnite mogućnosti redukcije (reduce) u OpenMP-ju i pokažite primjer
korištenja iste.

Answer 21

reduce direktiva na kraju paralelne regije “skupi” vrijednosti navedene varijable iz svih niti i nad
njima primjeni neku operaciju, koju zatim sprema u varijablu izvan paralelne regije.
int j = 0;
#pragma omp parallel for private(j) reduce(+;j)
for (int i = 0; i < n; i++) {
j++;
}
// j == n_threads * (n - 1)

Question 22

Objasnite mogućnosti i opcije raspoređivanja u OpenMP-ju.

Answer 22

• Sintaksa: schedule (<type>[,<chunk> ])</chunk></type>
• Chunk(komadić) - je neprekidan raspon ponavljanja, broj uzastopnih iteracija na niti

OPCIJE: schedule(static) sve niti imaju dodjeljene iteracije prije izvođenja
svakoj nit je dobijeljen jednak (sve isto) broj iteracija
blokira alociranje neprekidnih iteracija za svaku petlju
schedule(dynamic) neke iteracije dodijeljene su manjem broju niti (različit broj iteracija na niti)
kad nit završi dohvaća preostale iteracije
schedule(guided) vođeno samoraspoređivanje s minimalnom veličinom komadića 1
schedule(runtime) raspored niti izabran je tijekom izvođenja na temelju vrijednosti OMP_SCHEDULE;

Question 23

Objasnite i na primjeru pokažite uporabu smjernica parallel, for, single, nowait i
sections.

Answer 23

● parallel - definira dio koda koji se izvodi u paralelnoj regiji
● for - paralelizira for petlju dijeljenjem njenih indeksa prema dostupnim procesorima
● single - direktiva kad samo jedna nit treba izvrsiti dio koda (npr ispis)
#pragma omp single
na pocetku koda
● nowait - iskljucuje sinkronizaciju nakon paralelne regije
#pragma omp for nowait
● sections - paralelno izvodenje bilo koje od definiranih sekcija
#pragma omp parallel sections
#pragma omp parallel sections
{
#pragma omp section /* Optional */
v = alpha();
}

Question 24

Koja su dva glavna pristupa paralelizmu pomoću OpenMP-ja?

Answer 24

Paralelne regije i petlje

Question 25

Koja je razlika između zajedničkih i privatnih varijabli OpenMP smjernica?

Answer 25

Zajednicke varijable se dijele izmedu niti, sto znaci svaka nit cita i pise u istu memorijsku
lokaciju. Privatne varijable dupliciraju varijablu, stave ju u svoj memorijski prostor i onda u nju
citaju i pisu, dakle nema dijeljenja. Moguce kombinacije s firstprivate i lastprivate.

Question 26

Navedite i ukratko objasnite tri temeljne funkcije OpenMP okruženja.

Answer 26

● omogucavanje podjele programa u slijedne i paralelne dijelove
● skrivanje slozenosti rukovanja
● sinkronizacijski mehanizmi

Question 27

Objasnite pojam spleta računala (engl. grid) kroz postojeće definicije.

Answer 27

Vrsta paralelnog i raspodijeljenog sustava koji omogucuje dijeljenje, izmjenu, izbor i nakupljanje
zemljopisno raspodijeljenih autonomnih sredstava. Takva sredstva su racunala, programi,
podaci i baze, posebni uredaji i instrumenti

Question 28

Skicirajte slojeve građe spleta računala i njegovih međuslojeva.

Answer 28

IMA SLIKA.

Question 29

Navedite primjere spleta računala u primjeni i ukratko ih opišite (moguć osvrt na CRO
NGI i HR-ZOO).

Answer 29

● Online instrumentacija
● Distributed supercomuputing
● Collaborative engineering
● High-throughput computing
● Problem solving environment
CRO NGI (nacionalna grid infrastruktura) je zajednički resurs znanstvene i akademske
zajednice i predstavlja temeljnu infrastrukturu za znanstvena istraživanja, primjenu novih
tehnologija i povezivanje Hrvatske i hrvatskih znanstvenika u europski istraživački (ERA) i
visokoobrazovni (EHEA) prostor.
Projekt HR-ZOO (znanstveni obrazovni oblak) ima za cilj izgradnju računalnog i podatkovnog
oblaka koji će biti temeljna sastavnica nacionalne istraživačke i inovacijske e-infrastrukture s
namjerom da se znanstvenoj i akademskoj zajednici dugoročno osiguraju napredni računalni i
spremišni resursi te mrežna povezanost nužni za modernu i multidisciplinarnu znanost,
vrhunska istraživanja i obrazovni sustav Republike Hrvatske.

Question 30

Opišite osnovna načela oblaka računala (engl. cloud computing).

Answer 30

Prosirenje SOA (Service Oriented Architecture) na resurse isporucive u oblaku racunala, kao
SaaS, DaaS, PaaS, IaaS itd. Oslanja se na skalabilnost interneta i spajanje na niz razlicitih
uredaja i krajnjih pristupnih tocaka.