Studoši

zara cijena za 5 dana = broj procesora * ona zadana cijena * 5 dana(120h) = 28 * 2 * 120=6720kn
broj procesora se dobije kad za zadanu ucinkovitost (3/2+P) izjednacis s formulom T1/(P*Tp) gdje je Tp tih 5 dana (120h) i dobijes da je broj procesora 28

1. Ukupan broj poruka koje se razmijene (pošalju) u provedbi komunikacijske strukture binarnog stabla za 2^D procesora iznosi _______________.
2. Kompozicija modula u paralelnim programima može biti ______________________________________________________.
3. Ako je učinkovitost 25%, a ubrzanje je 4, koliki je broj procesora? _______________.
4. Izoučinkovitost opisuje kako se mora promijeniti _______________ u ovisnosti o količini posla (računanja) kako bi _______________ ostala nepromijenjena.
5. Pridruživanje se provodi ukoliko je broj _______________ veći od broja _______________.
6. Na APRAM računalu, unutar istog asinkronog odsječka, samo _______________ procesor smije pristupiti _______________ memorijskoj lokaciji.
7. Koje dodatne parametre uvodi model APRAM u odnosu na model PRAM? ______________________.
8. Ukupan broj poruka koji se razmjene(pošalju) u provedbi komunikacijske strukture hiperkocke za 2^d procesa iznosi______.
9. Povecanje zrnatosti može se postici tehnikama____________.
10. Ako je ubrzanje linearno, ucinkovitost je(kakvog iznosa?)___________.
11. Uz superlinearno ubrzanje, učinkovitost je (kakvog iznosa?)_________________.
12. Navedite sve četiri vrste aPRAM instrukcija: ________________, ________________, ________________, ________________.
13. Funkcija izoučinkovitnosti opisuje kako se mora promjeniti ______________________ u ovisnosti o promjeni broja procesora kako bi _______________________ ostala nepromijenjena.
14. Faza pridruživanja se provodi ukoliko je broj ____________________ veći od broja ______________________.
15. Uvišestručavanje računanja je tehnika kojom se ________________________ ukupna količina računanja kako bi se _________________ količina komunikacije.
16. Pojava zagušenja voditelja u modelu voditelj-radnik moguća je uz ___________________________ broj radnika.
17. Ukoliko se ubrzanje paralelnog programa mjeri u odnosu na najbolji slijedni program, radi se o________ ubrzanju.
18. Ukoliko se ubrzanje paralelnog programa mjeri u odnosu na isti program pokrenut na jednom procesoru, radi se o _______________________ ubrzanju.
19. MPI mehanizam dijeljenja komunikatora omogućava izvedbu ______________________________ kompozicije modula u paralelnom programu.
20. MPI mehanizam modula u paralelnim programima omogućava izvedbu _________________________________________.
21. Ubrzanje veće od linearnog naziva se ____________________________.
22. Povećanje zrnatosti možemo ostvariti tehnikama: ___________________ i __________________.
23. Prilikom istodobnog čitanja iste memorijske lokacije u CRCW PRAM računalu, svaki procesor će pročitati ________________ vrijednost.
24. Izraz koji opisuje trajanje slanja jedne poruke duljine L riječi u jednostavnom modelu komunikacije je: ___________________________.
25. Zrnatost zadataka se može definirati kao ___.
26. U modelu raspodijeljene memorije, procesori mogu komunicirati jedino ___.
27. Složenost provedbe postupka scan niza duljine n elemenata na PRAM računalu uz p procesora gdje je p<(n/2) iznosi ___.
28. Prilikom izvođenja optimalno postupka +_reduciranja niza duljine n na PRAM računalu, ukupan broj operacija zbrajanja na svim procesorima iznosi ___.
29. Na APRAM računalu, uz trajanje globalnog pristupa 4 vremenske jedinice, 2 uzastopna globalna pristupa trajat će ___.
30. Prilikom prilagodbe PRAM algoritma za APRAM računalo uz (p/B) procesora, gdje jedan APRAM procesor izvodi instrukcije za B PRAM procesora, jedna EREW PRAM instrukcija izvodi se u ___ koraka.
31. Optimalna složenost algoritma reduciranja niza duljine n na APRAM računalu uz n procesora iznosi ___.
32. Algoritam scan se odnosi na bilo koju ___ operaciju.
33. Poželjna svojstva paralelnih programa su ___.
34. Povratak iz neblokirajuće MPI funkcije znači: ______________________________.
35. Vrste instrukcija na APRAM računalu su: _______________________________.
36. Na APRAM računalu, uz trajanje globalnog pristupa 3 vremenske jedinice, 4 uzastopna globalna pristupa trajat će ___.
37. Amdahlov zakon definira iznos najvećeg mogućeg ______________ u ovisnosti o ________________________.
38. Vremenska složenost provedbe postupka scan niza duljine n elemenata na PRAM računalu uz p procesora gdje je 𝑝 < 𝑛/2, iznosi ________________________.
39. Povratak iz blokirajuće MPI funkcije znači: _______________________________.

@anon00 round2.
Ovo su sva teorijska koja sam iskopao.

Bisolvon

Challenge accepted, nek netko nađe odgovor na 8. ja nemam pojma

1. Ukupan broj poruka koje se razmijene (pošalju) u provedbi komunikacijske strukture binarnog stabla za 2D procesora iznosi 2^d - 1_.

2. Kompozicija modula u paralelnim programima može biti ___ Serijska, paralelna i zajednička kompozicija ___.

3. Ako je učinkovitost 25%, a ubrzanje je 4, koliki je broj procesora? 16? (S=P*E – S=ubrzanje, E=učinkovitost pa onda P=S/E tj 4/0.25 = 16)_________.

4. Izoučinkovitost opisuje kako se mora promijeniti br procesora u ovisnosti o količini posla (računanja) kako bi _učinkovitost ostala nepromijenjena.

5. Pridruživanje se provodi ukoliko je broj zadataka veći od broja procesora.

6. Na APRAM računalu, unutar istog asinkronog odsječka, samo _jedan procesor smije pristupiti istoj globalnoj memorijskoj lokaciji.

7. Koje dodatne parametre uvodi model APRAM u odnosu na model PRAM? __ B (vrijeme potrebno za sinkronizaciju p procesora) i d – vrijeme za globalno čitanje/pisanje __.

8. Ukupan broj poruka koji se razmjene(pošalju) u provedbi komunikacijske strukture hiperkocke za 2d procesa iznosi______??.

9. Povecanje zrnatosti može se postici tehnikama __Povećanje zadataka, uvišestručavanje računanja __.

10. Ako je ubrzanje linearno, ucinkovitost je(kakvog iznosa?) jednaka 1_.

11. Ako je superlinearno učinkovitost je veća od 1

12. Ako je sublinearno učinkovitost je manja od 1

13. Uz superlinearno ubrzanje, učinkovitost je (kakvog iznosa?) >1.

14. Navedite sve četiri vrste aPRAM instrukcija: Globalno čitanje, Globalno pisanje, Lokalna operacija, __Sinkronizacija / ograda.

15. Funkcija izoučinkovitnosti opisuje kako se mora promjeniti količina posla_ u ovisnosti o promjeni broja procesora kako bi ___učinkovitost___ ostala nepromijenjena.

16. Faza pridruživanja se provodi ukoliko je broj Zadataka veći od broja _procesora___.

17. Uvišestručavanje računanja je tehnika kojom se povećava ukupna količina računanja kako bi se smanjila količina komunikacije.

18. Pojava zagušenja voditelja u modelu voditelj-radnik moguća je uz prevelik broj radnika.

19. Ukoliko se ubrzanje paralelnog programa mjeri u odnosu na najbolji slijedni program, radi se o apsolutnom ubrzanju.

20. Ukoliko se ubrzanje paralelnog programa mjeri u odnosu na isti program pokrenut na jednom procesoru, radi se o relativnom ubrzanju.

21. MPI mehanizam dijeljenja komunikatora omogućava izvedbu paralelne kompozicije modula u paralelnom programu.

22. MPI mehanizam modula u paralelnim programima omogućava izvedbu slijedne i paralelne kompozicije modula_.

23. Ubrzanje veće od linearnog naziva se superlinearno.

24. Povećanje zrnatosti možemo ostvariti tehnikama: _Povećanja zadataka i uvišestručavanja računanja_.

25. Prilikom istodobnog čitanja iste memorijske lokacije u CRCW PRAM računalu, svaki procesor će pročitati istu/jednaku vrijednost.

26. Izraz koji opisuje trajanje slanja jedne poruke duljine L riječi u jednostavnom modelu komunikacije je: _Tmsg = ts + twL (ts - postavljanje poruke, tw - prijenos jedne riječi).

27. Zrnatost zadataka se može definirati kao količine računanja (lokalnog rada) i količine komunikacije (nelokalnog rada)_.

28. U modelu raspodijeljene memorije, procesori mogu komunicirati jedino razmjenom poruka.

29. Složenost provedbe postupka scan niza duljine n elemenata na PRAM računalu uz p procesora gdje je p<(n/2) iznosi O(n/p + log p).

30. Prilikom izvođenja optimalno postupka +_reduciranja niza duljine n na PRAM računalu, ukupan broj operacija zbrajanja na svim procesorima iznosi n-­1.

31. Na APRAM računalu, uz trajanje globalnog pristupa 4 vremenske jedinice, 2 uzastopna globalna pristupa trajat će 5 (4+2­1 tj (d+k ­1)).

32. Prilikom prilagodbe PRAM algoritma za APRAM računalo uz (p/B) procesora, gdje jedan APRAM procesor izvodi instrukcije za B PRAM procesora, jedna EREW PRAM instrukcija izvodi se u 5B+2d­2 koraka.

33. Optimalna složenost algoritma reduciranja niza duljine n na APRAM računalu uz n procesora iznosi O(B log n) ili O(logBn) (pomoću B­arnog umjesto binarnog stabla)_.

34. Algoritam scan se odnosi na bilo koju binarnu asocijativnu operaciju.

35. Poželjna svojstva paralelnih programa su istodobnost, skalabilnost, lokalnost i modularnost.

36. Vrste instrukcija na APRAM računalu su: globalno čitanje, globalno pisanje, lokalna operacija i sinkronizacija____.

37. Na APRAM računalu, uz trajanje globalnog pristupa 3 vremenske jedinice, 4 uzastopna globalna pristupa trajat će 6 (3+4­1 tj (d+k ­1)).

38. Amdahlov zakon definira iznos najvećeg mogućeg ubrzanja u ovisnosti o dijelu programa koji se može paralelizirati_.

39. Vremenska složenost provedbe postupka scan niza duljine n elemenata na PRAM računalu uz p procesora gdje je 𝑝 < 𝑛/2, iznosi ______ O(n/p + log p) _____.

40. Povratak iz blokirajuće MPI funkcije znači: da je funkcija završila i može se pristupati memorijskoj lokaciji.

41. Povratak iz neblokirajuće MPI funkcije znači: _da se može ponovno pristupiti toj memorijskoj lokaciji, ali ne i da je funkcija uspješno izvršena – to se mora naknadno provjeriti_____.

42. Navedite moguce uzroke neslaganja (nepotpunosti) jednostavnog modela trajanja paralelnog programa u usporedbi sa stvarnom izvedbom programa: Nejednako opterećenje, uvišestručeno računanje, nesklad algoritma i programskog alata, ograničen kapacitet komnunikacije

43. Navedite i moguce uzroke “anomalije ubrzanja” _Upotreba priručne memorije (cache-a) i anomalija pretraživanja

44. Navedite sve podjele komunikacije u paralelnim algoritmima Lokalna i globalna komunkacija

45. Navedite moguće nedostatke jednostavnog modela ocjene perfomansi u opisu stvarnog ponašanja paralelnog programa? Jednostavni model ne uzima u obzir ograničenja bandwidth-a komunkacijskog kanala, nejednako opterećene, uvišestručeno računanje, nesklad algoritma i programskog alata

46. Ako su ostali parametri isti i povećavamo br procesora učinkovitost monotono pada, a ubrzanje raste do neke točka pa nakon tog pada

Bisolvon

1. Ukupan broj poruka koje se razmijene (pošalju) u provedbi komunikacijske strukture binarnog stabla za 2D procesora iznosi 2^D-1 (nisam siguran, proveo ručno za mala stabla).
2. Kompozicija modula u paralelnim programima može biti slijedna, paralelna ili zajednička.
3. Ako je učinkovitost 25%, a ubrzanje je 4, koliki je broj procesora? 16 (uvrstite u formule).
4. Izoučinkovitost opisuje kako se mora promijeniti broj procesora u ovisnosti o količini posla (računanja) kako bi učinkovitost ostala nepromijenjena.
5. Pridruživanje se provodi ukoliko je broj zadataka veći od broja procesora.
6. Na APRAM računalu, unutar istog asinkronog odsječka, samo jedan procesor smije pristupiti (istoj) globalnoj memorijskoj lokaciji.
7. Koje dodatne parametre uvodi model APRAM u odnosu na model PRAM? trajanje globalne operacije (d) i trajanje sinkronizacije (B)
8. Ukupan broj poruka koji se razmjene(pošalju) u provedbi komunikacijske strukture hiperkocke za 2^d procesa iznosi log(2^d) (isto nisam siguran?).
9. Povecanje zrnatosti može se postici tehnikama aglomeracije.
10. Ako je ubrzanje linearno, ucinkovitost je(kakvog iznosa?) 1.
11. Uz superlinearno ubrzanje, učinkovitost je (kakvog iznosa?) >1.
12. Navedite sve četiri vrste aPRAM instrukcija: globalno čitanje, globalno pisanje, lokalna operacija, sinkronizacija.
13. Funkcija izoučinkovitnosti opisuje kako se mora promjeniti količina posla (veličina problema) u ovisnosti o promjeni broja procesora kako bi učinkovitost ostala nepromijenjena.
14. Faza pridruživanja se provodi ukoliko je broj zadataka veći od broja procesora.
15. Uvišestručavanje računanja je tehnika kojom se povećava ukupna količina računanja kako bi se smanjila količina komunikacije.
16. Pojava zagušenja voditelja u modelu voditelj-radnik moguća je uz prevelik? broj radnika. (nisam siguran)
17. Ukoliko se ubrzanje paralelnog programa mjeri u odnosu na najbolji slijedni program, radi se o apsolutnom ubrzanju.
18. Ukoliko se ubrzanje paralelnog programa mjeri u odnosu na isti program pokrenut na jednom procesoru, radi se o relativnom ubrzanju.
19. MPI mehanizam dijeljenja komunikatora omogućava izvedbu paralelne kompozicije modula u paralelnom programu.
20. MPI mehanizam modula u paralelnim programima omogućava izvedbu _________________________________________.
21. Ubrzanje veće od linearnog naziva se superlinearno.
22. Povećanje zrnatosti možemo ostvariti tehnikama: ___________________ i __________________. (help)
23. Prilikom istodobnog čitanja iste memorijske lokacije u CRCW PRAM računalu, svaki procesor će pročitati istu vrijednost.
24. Izraz koji opisuje trajanje slanja jedne poruke duljine L riječi u jednostavnom modelu komunikacije je: t_s + t_w*L.
25. Zrnatost zadataka se može definirati kao omjer količine računanja i komunikacije.
26. U modelu raspodijeljene memorije, procesori mogu komunicirati jedino porukama.
27. Složenost provedbe postupka scan niza duljine n elemenata na PRAM računalu uz p procesora gdje je p<(n/2) iznosi n/p + logp. (nisam siguran)
28. Prilikom izvođenja optimalno postupka +_reduciranja niza duljine n na PRAM računalu, ukupan broj operacija zbrajanja na svim procesorima iznosi n-1. (nisam siguran)
29. Na APRAM računalu, uz trajanje globalnog pristupa 4 vremenske jedinice, 2 uzastopna globalna pristupa trajat će 5.
30. Prilikom prilagodbe PRAM algoritma za APRAM računalo uz (p/B) procesora, gdje jedan APRAM procesor izvodi instrukcije za B PRAM procesora, jedna EREW PRAM instrukcija izvodi se u 5B + 5 d - 2 koraka. (nisam siguran)
31. Optimalna složenost algoritma reduciranja niza duljine n na APRAM računalu uz n procesora iznosi logn.
32. Algoritam scan se odnosi na bilo koju asocijativnu binarnu operaciju.
33. Poželjna svojstva paralelnih programa su modularnost, skalabilnost, lokalnost, istodobnost.
34. Povratak iz neblokirajuće MPI funkcije znači: (čudno formulirano, ne znači ništa: povratak je trenutan).
35. Vrste instrukcija na APRAM računalu su: globalno čitanje/pisanje, lokalna operacija, sinkronizacija.
36. Na APRAM računalu, uz trajanje globalnog pristupa 3 vremenske jedinice, 4 uzastopna globalna pristupa trajat će 6.
37. Amdahlov zakon definira iznos najvećeg mogućeg ubrzanja u ovisnosti o udjelu programa koji se može paralelizirati.
38. Vremenska složenost provedbe postupka scan niza duljine n elemenata na PRAM računalu uz p procesora gdje je 𝑝 < 𝑛/2, iznosi n/p + logp.
39. Povratak iz blokirajuće MPI funkcije znači: kraj operacije.

Neka neko provjeri, nisam 100% na dosta toga

ZI - 16./17. zadaci 2., 3., 6.
Ima netko postupak za ove zadatke ?

anon00 8. d*log2(d) po onome u skripti, valjda je

anon00 44. Zar ne postoje 4 podjele komunikacije : globalna/lokalna, sinkrona/asinkrona, strukturirana/nestrukturirana, statička/dinamička

Rene Hah! Sucker!
Salu na stranu, super da smo potvrdili odgovore (zanemari sto ja imam par više pitanja, dodao sam par stvari koje sam nasao)

Jedino je ovaj 9 razlicit
“Povecanje zrnatosti može se postici tehnikama aglomeracije.”
To sam i ja prvobitno stavio za odgovor, a onda sam skuzio da je zapravo obrnuta korelacija
Dakle aglomeracija se postiže povećanjem zrnatosti, a povećanje zrnatosti postižemo tehnikama povećanja zadataka i uvišestručavanje računanja

Nisam 100% siguran, ali mi se cini vjerojatnije da je ovo točno

Još tražimo nekog tko zna 100% točan odgovor za 8. (br poruka hiperkocke)

anon00 mislim da sam skuzio hiperkocku, svaki procesor izvršava petlju koja ima logn koraka i šalje jednu poruku u svakom koraku, dakle pošalje se n\cdot logn poruka. Provjerio sam na 3d kocki i dobije se 24 što je točno, pa valjda vrijedi i inače.

teshna Izgleda da si u pravu, tnx na ispravku

Zna netko ova dva riješiti?

Artemis

2. Zadatak

funkcija plaćanja f(p) = 1 kn/h/proc * P proc * (10 + 500/P) h + 12*Tp

Ovo deriviraš i izjednačiš s 0. Zatim pronađeš P koji može biti dvije vrijednosti (obje platiš jednako: ljadu i 110kn): 24 i 25 procesora.

Artemis

1. Zadatak
   a) T = n * (t_c + t_s + t_w)
   b) T = log n * (t_c + t_s + t_w)

Olive Oil Za sigurnu točnost treba provjeriti cijenu za broj procesora ispod i iznad minimuma. Funkcija nije linearna tako nije sigurno da je ona vrijednost koja je bliža uistinu manja, može rasti brže u jednom smjeru. Za primjer u slici, minimum je u P=10.25 pa treba provjeriti i P=10 i P=11. U ovom slučaju ispadne da je P=10 bolje, ali ako dobiješ x.49, tko zna.

Napravio sam neku skriptu teorije iz genetskih algoritama pa evo linka ak kome pomogne :
https://we.tl/t-p5Fl71ItkK
(vjerojatno ćete trebati “I accept” -> “I agree” -> “Download”)

Jel netko ima mozda skupljena rjesenja zadataka iz zavrsnih ispita? 😀 🥰

gladiator ovo je konveksna funkcija s plusevima kak to moze bit nula a da rjesenje nije negativan broj procesora?

Zna li netko ovaj?

5. Neki tekst je zapisan u obliku niza znakova T[] duljine n.
   Napšite algoritam za EREW PRAM racunalo uz najviše n procesora koji ce ispitati duljinu najdulje recenice u tekstu.
   (po ukupnom broju znakova, ukljucujuci i razmake).
   Svaka recenica na kraju ima tocku.

BillIK

int pomocno[];
paralelno (j = 0; j < n; j++) {
___pomocno[j] = 0;
___for(i = 0; i + j < n; i++) {
______if (polje[j + i] != ".") {
__________polje[j + i]++;
______} else 
          break;
___}
}

return max_reduce(pomocno)

BillIK gladiator može se i u O(\log N):

• u pomoćno polje postaviš 1 ako je točka i 0 ako nije
• provedeš +_prescan
• vrijednost prescana je redni broj rečenice za svaki znak
• pomoću toga izgradiš novi niz koji sadrži početne ili završne pozicije svake rečenice
• u opet novi niz izračunati razlike uzastopnih pozicija rečenica, pazeći na EREW
• max_reduce

Zna li netko zasto u onom file-u di rjesavaju zadatke, zadatak 3.3:

Paralelni algoritam iterativno računa elemente matrice. Nova vrijednost elementa
računa se pomoću vrijednosti 2 neposredna susjedna elementa u svakom od 4 smjera, s tim
da matrica ima ‘spojene’ sve bridove (npr. vrijednost elementa A[1,1] računa se pomoću
A[1,2], A[1,3], A[1,N-1], A[1,N], A[N-1,1], A[N,1], A[2,1] i A[3,1]). Trošak računanja jednog
elementa iznosi tc

. Izrazite trajanje izvođenja jedne iteracije na P procesora te učinkovitost i

izoučinkovitost algoritma ako je matrica na procesore podijeljena:
a) po retcima (svaki procesor ima jednak broj redaka),
b) po podmatricama jednake veličine.

Kako je ovdje da u a) slučaju šalje prema 2 procesa, a u b) slučaju prema 4 procesa?
Meni u mojoj glavi ispada da kod a) šalje prema 4 procesa, a u b) prema 8 procesa..

Di sam u krivu?

huhu Ja sam isto kao i ti shvatio, vidim da na ovoj slici u pdfu imaju ove dvojke uz tw koje kasnije nestanu. Mislim da je neka greska u toj slici.

huhu Care to elaborate? U a) se šalju podaci dvama procesima - lijevi i desni. U b) se šalju lijevom, desnom, gornjem i donjem

Bisolvon Al cak je logicno da salje 2N, odnosno u b) 2N/korijen(P), kaj ne?