| A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z | |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
1 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | ||||||||||||||||
2 | K3 2023 | ❌✅Objasniti strukturu kataloga i objasniti kako se postiže ušteda prostora u 'cache based' tehnikama. Opisati operaciju upisa u deljeni blok. Koje su prednosti, a koji nedostaci kod ove operacije u odnosu na full-map tehniku? Koje su prednosti i nedostaci? Objasniti organizaciju kataloga i izračunati njegovu veličinu ako je m – veličina memorije, c – veličina keš memorije, b – veličina bloka i n – broj procesora. Koje su prednosti i nedostaci ovakve organizacije? Šta se postiže primenom “cache-based” protokola? Koje su prednosti i nedostaci ovakve organizacijeKoje su prednosti i nedostaci ovakve organizacije? Šta se postiže primenom cache-based protokola? Objasniti organizaciju kataloga i izračunati njegovu veličinu. Koje su prednosti i nedostaci? Opisati šta se dešava pri izbacivanju nekog bloka iz keš memorije kod directory protokola. Posebno diskutovati alternative pri izbacivanju bloka čiji je sadržaj isti kao u memoriji. Identifikovati situacije i protokole za koje su pojedine alternative pogodne. Objasniti organizaciju informacije o koherenciji i akcije tipičnog directory protokola. Ilustrovati slikom. Koji su osnovni problemi vezani za ovakav protokol? Objasniti organizaciju informacije o koherenciji i akcije directory protokola sa dinamičkom alokacijom pointera. Objasniti organizaciju informacije i akcije u cache-based directory protokolima. Objasniti motivaciju za 'cache-based' šeme i objasniti i nacrtati strukturu kataloga. Koja je osnovna motivacija ’cache-based’ kataloga? Precizno objasniti i nacrtati strukturu kataloga. Izvesti izraz za veličinu kataloga i objasniti oznake u izrazu. Šta se postiže primenom cache-based protokola? Objasniti osnovne akcije protokola. Šta se postiže primenom “cache-based” protokola?Precizno opisati šta se dešava kod read miss-a i write hit-a. | ❌✅ Šta je motivacija za tehniku smanjivanja “visine” kataloga? Ukratko objasniti implementaciju. Objasniti šta je osnovna prednost, a šta nedostatak? Objasniti organizaciju kataloga i opisati akcije protokola koji kombinuje tehnike za smanjenje visine i širine kataloga. Na kojem zapažanju su zasnovane tehnike smanjivanja “visine” kataloga. Načelno opisati organizaciju kataloga kod tih tehnika. Objasniti strukuru kombinovanog kataloga gde se kombinuju tehnike smanjenja visine i širine kataloga. Objasniti osnovne operacije. Na kojoj činjenici su zasnovane metode za smanjivanje visine kataloga u directory protokolima? Objasniti kako izgleda struktura koja se koristi za katalog i opisati operacije za alokaciju i dealokaciju ulaza. Kakve su specifičnosti ove strukture u odnosu na uobičajeno korišćenje u procesoru? Na kojem zapažanju su zasnovane tehnike za smanjivanje “visine” kataloga u directory protokolima. Objasniti organizaciju kataloga i osnovne akcije protokola. Objasniti ideju za smanjenje visine kataloga u directory protokolima. Kakve su specifičnosti realizacije? Objasniti kako se može smanjiti “visina” kataloga kod directory protokola, kao i osnovne operacije u takvom rešenju. Objasniti tipične načine deljenja u aplikacijama. Komentarisati implikacije ove analize na organizaciju kataloga u directory protokola Analizirati skaliranje directory protokola sa aspekta načina deljenja u aplikacijama i kako to utiče na strukturu kataloga. Koji su karakteristični načini deljenja u odnosu na broj invalidacija? Objasniti kako studija o načinima deljenja podataka u aplikacijama utiče na strukturu kataloga u directory protokolima? U sklasu sa tim, kakva je skalabilnost ovih protokola? Objasniti i nacrtati strukturu kataloga u cache-based directory protokolu. Objasniti i operacije koje se izvršavaju pri čitanju ili upisu od nekog procesora. Objasniti motivaciju za tehniku smanjivanja visine u directory protokolima. Ukratko objasniti funcionisanje ove tehnike, prednosti i nedostatke. Objasniti motivaciju za osnovnu tehniku smanjivanja širine u directory protokolima. Ukratko objasniti funcionisanje ove tehnike, kao i njenu prostornu složenost. | ✅ Nacrtati opštu strukturnu šemu višestepene sprežne mreže (MIN). Objasniti strukturu i princip rada. Kolika je hardverska složenost, a kolika latencija? Objasniti princip organizacije višestepene sprežne mreže tipa Omega, kao i način rutiranja poruka. Objasniti da li je mreža blokirajuća. Ako jeste, nacrtati u mreži 8x8 primer rutiranja dve poruke koje izazivaju blokiranje i označiti mesto gde dolazi do blokiranja. Objasniti kako se dolazi do reda funkcije hardverske složenosti i funkcije latencije u višestepenoj interkonekcionoj mreži (MIN) dimenzije n. Kojoj grupi interkonekcione mreža pripada mreža tipa Omega. Nacrtati i objasniti strukturu ove mreže za 8 čvorova. Objasniti motivaciju i princip organizacije višestepenih interkonekcionih mreža (MIN). Objasniti motivaciju i princip organizacije višestepenih interkoncekcionih mreža (MIN). Objasniti način povezivanja Butterfly mreže i nacrtati je za slučaj 8x8. Objasniti kako se dolazi do reda funcije hardverske složenosti i funkcije latencije u višestepenoj interkonekcionoj mreži (MIN) dimenzije n. Nacrtati mrežu tipa Butterfly, prikazati put između čvorova 2 i 6 i objasniti kako se vrši rutiranje. Nacrtati interkonekcionu mrežu Butterfly 8x8. Objasniti način povezivanja mreže i rutiranja poruka. Da li je mreže blokirajuća? Ako jeste, na slici ilustrovati dva prenosa koji bi izazvali blokiranje. Kojoj grupi interkonekcionih mreža pripada Butterfly? Objasniti način povezivanja i nacrtati ovu mrežu za 8 ulaza i 8 izlaza. Nacrtati put poruke između ulaza 7 i izlaza 3. Objasniti da li je mreža blokirajuća. | ❌ Kojoj grupi interkonekcionih mreža pripada mreža tipa stabla? Objasniti strukturu ove mreže i nacrtati je za n = 8. Napisati izraze za vrednosti parametara mreže u opštem slučaju. Koji je njen glavni problem i kako se prevazilazi? Preko broja čvorova n izraziti stepen čvora, prečnik i propusni opseg bisekcije. | Šta je to burst sekcija i kako ona utiče na pristup memorji kod grafičkih procesora? Na primeru dela koda u prilogu koji vrši množenje matrice, navesti i objasniti kod kojih pristupa se koriste prednosti pristupa u transakciji, a kod kojih ne. Odgovor ilustrovati slikom __global__ void MatrixMulKernel (float* Md, float* Nd, float* Pd, int Width) { int Row = blockIdx.y * blockDim.y + threadIdx.y; int Col = blockIdx.x * blockDim.x + threadIdx.x; float Pvalue = 0; for (int k = 0; k < Width; ++k) Pvalue += Md[Row * Width + k] * Nd[k * Width + Col]; Pd[Row * Width + Col] = Pvalue; } | ✅ Nacrtati i objasniti tipičnu redukcionu šemu na grafičkom procesoru. Navesti broj koraka i operacija koji se pritom izvršava i uporediti sa klasičnom sekvencijalnom redukcijom. Zašto sekvencijalna redukcija nije pogodna na grafičkom procesoru? Objasniti način kako se može efikasno sproversti operacija redukcije na grafičkom procesoru i nacrtati odgovarajuću redukcionu šemu. Koje uslove mora da zadovolji redukcioni operator da bi operacija mogla da se sprovede? Koje alternative mogu da se koriste? | Koristeći CUDA tehnologiju paralelizovati funkciju koja računa vrednosti gradijenta zadate slike. Koristiti 2D organizaciju jezgra. Obratiti pažnju na efikasnost paralelizacije i koristiti deljenu memoriju. Smatrati da su sve promenljive inicijalizovane enum orientation : unsigned char { None, Vertical, Horizontal } double *grad ( size_t rows, size_t cols, int img[], short gradImg[], char dirImg[] ) { for (size_t i = 1; I < rows - 1; i++) { for (size_t j = 1; j < cols - 1; j++) { size_t index = i * cols + j; int com1 = img[index + cols + 1] - img[index - cols - 1]; int com2 = img[index - cols + 1] - img[index + cols - 1]; int gx = com1 + com2 + img[index + 1] - img[index - 1]; int gy = com1 - com2 + img[index + cols] - img[index - cols]; int sum = hypot(gx, gy); gradImg[index] = sum; if (sum >= THRESHOLD) { dirImg[index] = abs(gx) >= abs(gy) ? Vertical : Horizontal; } } } } | ||||||||||||||||||
3 | K2 2023 | ❌ Navesti prednosti i nedostatke programskog modela zajedničke memorije. Nacrtati i objasniti osnovne arhitekture sistema koji podržavaju model zajedničke memorije. Diskutovati njihovu skalabilnost. Nacrtati i objasniti tipove arhitektura sistema sa zajedničkom memorijom i objasniti ih. Objasniti prednosti i nedostatke zajedničke keš memorije. Gde se u procesoru ona najčešće koristi? Koji nivoi u keš memoriji su obično deljeni? Objasniti prednosti i nedostatke zajedničke keš memorije u odnosu na privatne. Objasniti karakteristike i prednosti korišćenja zajedničke keš memorije u multiprocesorskim sistemima. Objasniti prednosti i nedostatke programskog modela zajedničke memorije. Nacrtati i objasniti tipove arhitektura sistema sa zajedničkom memorijom i objasniti ih. Diskutovati prednosti i nedostatke zajedničke (deljene) keš memorije. Gde se ona obično primenjuje? Nacrtati i objasniti osnovne tipove skalabilnih i neskalabilbnih arhitektura sistema sa zajedničkom memorijom. Nacrtati i objasniti osobine nekih tipičnih arhitektura sistema sa zajedničkom memorijom. Objasniti programski model zajedničke memorije i njegove prednosti. Nacrtati i objasniti arhitekturu sistema koja najbolje podržava ovaj model. | ❌ Objasniti na koje vrste promašaja u keš memoriji utiče povećanje veličine bloka i na koji način. Diskutovati prednosti i mane povećanja veličine bloka keš memorije u multiprocesorskim sistemima. Objasniti negativne efekte povećanja veličine bloka keš memorije. Objasniti načine da se ovi negativni efekti ublaže. Šta je osnovni cilj povećanje veličine bloka keš memorije? Detaljno diskutovati pozitivne i negativne efekte povećanja veličine bloka u keš memoriji. Kako se negativni efekti mogu ublažiti? Koji su negativni efekti povećanja veličine bloka keš memorije? Objasniti neke načine za ublažavanje ovih efekata. Diskutovati pozitivne i negativne efekte povećanja veličine bloka u multiprocesorskim sistemima. | Objasniti kao bi se MSI protokol nadgradio ReadBroadcast funkcionalnošću. Nacrtati digaram prelaza i objasniti rad tako nadgrađenog protokola ako se pri upisu u validan blok koristi posebna transakcija BusUpgr. Nacrtati digaram prelaza i objasniti rad MSI protokola ako se pri upisu u validan blok koristi posebna transakcija BusUpgr. Protokol nadgraditi i ReadBroadcast funkcionalnošću. Nacrtati dijagam prelaza stanja za MSI protokol i detaljno objasniti akcije i transakcije. Koji su glavni nedostaci ovog protokola? Koji problemi se sagledavaju kod MSI protokola? Kako bi se oni mogli rešiti? Dati dokaz koherencije MSI protokola. Kod protokola MSI precizno objasniti: a) stanja, b) transakcije na magistrali i c) akcije protokola. Za protokol MSI: a) precizno objasniti akcije pri RH, RM, WH, WM i zameni, b) nacrtati dijagram prelaza i označiti koje prelaze izazivaju akcije procesora, a koje transakcije na magistrali, c) navesti osnovne probleme ovog protokola i načelno objasniti kako se rešavaju. | Neka su u multiprocesorskom sistemu sa n procesora sa zajedničkom magistralom data dva načina deljenja: SP1: {P1: Write V, P2..p: Read V} x q SP2: {(P1: Write V) x p; (P2: Read V, Write V)} x q U početku blok V nije keširan ni u jednoj privatnoj keš memoriji. Izračunati koliko se transakcija (i kojih) na magistrali izvrši kod SP1 i SP2 ako se koristi invalidujući protokol, a koliko ako se koristi ažurirajući protocol. Diskutovati komparativno performanse protokola kod oba slučaja u zavisnosti od vrednosti parametra p. 2) Neka se dva procesa sinhronizuju preko zajedničkog flega x. Proces A čeka da x bude 0, a onda radi i zatim postavi x na 1. Proces B čeka da x bude 1, a onda radi i zatim postavi x na 0. Opisati neophodne transakcije u slucaju invalidacionog i ažurirajućeg protokola i izvesti zaključak. | ✅ Neka je dat niz realnih brojeva. Potrebno je formirati novi niz od ulaznog niza tako da bude zadovoljen uslov b[i] = f(a[i]). Ulazni niz je alociran u procesu sa rangom 0 (master). Smatrati da je broj elemenata niza deljiv brojem procesa u MPI svetu. Koristeći MPI biblioteku i navedene definicije: #define K 32 #define N 1024 double f(double x); a) [5] Napisati deo koda master procesa koji ravnomerno raspoređuje ulazni niz svim procesima i prihvata rezultat rada nakon formiranja novog niza. b) [10] Ukoliko se koristi manager - worker model, napisati deo koda za master procesa kojim se po K elemenata niza šalje na obradu svakom workeru i prihvata i smešta rezultat celokupne obrade. Proces se odvija beskonačno. | ❗Šta predstavlja jednostrana komunikacija i koje su prednosti njenog korišćenja prilikom komunikacije između MPI procesa? Napisati skelet koda za dva procesa koji razmenjuju niz od 64 karaktera putem jednostrane komunikacije. Definisati pojam stalne komunikacije kod MPI biblioteke. Kada ima smisla koristiti ovaj vid komunikacije i koje alternative postoje? Napisati skelet odgovarajućih kodova za inicijalizaciju, slanje i prijem putem stalne komunikacije poruka iz zadatog bafera msg dužine 64 32-bitna cela broja između dva procesa sa rangovima definisanim konstantama MASTER i SLAVE. Šta predstavlja stalna komunikacija i koje su prednosti njenog korišćenja prilikom komunikacije između MPI procesa? Napisati skelet koda za dva procesa koji razmenjuju niz od 64 karaktera putem stalnog komunikacionog kanala. | ✅ MOESI VIDETI ROK: chrome-extension://efaidnbmnnnibpcajpcglclefindmkaj/http://mups.etf .rs/ispiti/2022-2023/si4mps_k2_20222023.pdf | ||||||||||||||||||
4 | K1 2023 | ❌ Objasniti suštinu fenomena power wall. Navesti neke tehnike za smanjivanje snage. kako se prevazilazi. posledice. kako utice na projektovanje procesora? Sta su memory wall i ILP wall i njegove konsekvense? | ❌ Objasniti šta je ILP i navesti primere. Diskutovati trendove u iskorišćenju ILP i potkrepiti činjenicama. Ukratko objasniti načine, trendove i potencijale iskorišćenja paralelizma na nivou instrukcije (ILP). Objasniti šta je ILP i navesti neki primer. Objasniti i obrazložiti potencijale i ograničenja u iskorišćenju ILP-a. Objasniti šta je ILP i navesti tipične primere. Objasniti neke načine iskorišćenja paralelizma na nivou instrukcije (ILP). Objasniti i obrazložiti trendove iskorišćenja ILP za povećanje performansi nekada i sada. Sa po 2-3 rečenice definisati i objasniti sledeće skraćenice: ILP, MISD i MIN. Navesti i obrazložiti zaključak o daljim potencijalima u iskorišćenju ILP. | K1 2017 3) | ❌ Objasniti karakteristike programskog modela prenosa poruka. Nacrtati i objasniti tipičnu arhitekturu sistema koja podržava ovaj model. Uporediti programske modele zajedničke memorije i prenosa poruka. Dati uporedni pregled karakteristika programskih modela zajedničke memorije i prenosa poruka. U čemu se razlikuju arhitekture i organizacije sistema koji direktno podržavau ove modele. Objasniti karateristike paralelnog programskog modela prenosa poruka, kao i karakteristike sistema koji ga podržavaju. Objasniti paralelni programski model prenosa poruka. Diskutovati njegove prednosti i nedostatke. Objasniti detaljno kako se ostvaruje komunikacija između dva procesa. Uporediti prednosti i nedostatke programskih modela zajedničke memorije i prenosa poruka. Ukratko definisati pojam DSM (distributed shared memory). | 💻Korišćenjem OpenMP tehnologije, paralelizovati deo koda u prilogu koji sortira niz korišćenjem quicksort algoritma za sortiranje. Obratiti pažnju na efikasnost i korektnost paralelizacije. Smatrati da su sve promenljive ispravno deklarisane. #include <stdio.h> void quicksort(int *A, int len) { if (len < 2) return; int pivot = A[len / 2]; int i, j; for (i = 0, j = len - 1; ; i++, j--) { while (A[i] < pivot) i++; while (A[j] > pivot) j--; if (i >= j) break; int temp = A[i]; A[i] = A[j]; A[j] = temp; } quicksort(A, i); quicksort(A + i, len - i); } int main (void) { // int a[] = ...; // int n = ...; quicksort(a, n); return 0; } | ✅ Kod u prilogu je paralelizovan korišćenjem OpenMP tehnologije, ali sadrži određene nedostatke. Diskutovati nedostatke, načine njihovog rešavanja i navesti alternativu. #pragma omp parallel shared(sum) { double factor; for (long long i = n * omp_get_thread_num() / N; i < n *(omp_get_thread_num() + 1) / N; i++) { factor = (i % 2 == 0) ? 1.0 : -1.0; #pragma omp critical { sum += factor /(2*i+1); } } } | ✅ 14) Nakon merenja performansi jednog programa za obradu slika pri uobičajenoj upotrebi, dobijeni su sledeći rezultati: program 50% vremena provodi čekajući da korisnik konfiguriše obradu, 30% vremena provodi učitavajući ulazne podatke i 20% vremena provodi u obradi podataka. Podaci koje program obrađuje su fotografije maksimalne veličine 3648x2736, a za obradu se koriste različiti konvolucioni filteri. Obrađuje se jedna fotografija u jednom trenutku. Vreme potrebno da bude učitana i obrađena jedna fotografija na sistemu sa jednim jednojezgarnim procesorom, koji radi na 2 GHz, je u proseku 10 sekundi. Predložiti vrstu hardverske i softverske platforme za paralelnu verziju ovog programa. Obrazložiti svaku projektnu odluku (arhitektura, programski model, broj procesora itd.). Prilikom određivanja maksimalnog smislenog broja procesora, pretpostaviti da dodatno vreme uvedeno paralelizacijom ne postoji i navesti formulu za Amdalov zakon koja odgovara toj pretpostavci.13) Posmatra se jedna naučna aplikacija koja vrši određenu obradu nad 2D matricama veoma velikih dimenzija. Tipično, matrice su reda veličine od par stotina MB do nekoliko desetina GB. Prilikom obrade matrice, nova vrednost odgovarajućeg elementa se dobija množenjem vrednosti elementa i elemenata u bližem susedstvu sa matricom odgovarajućih dimenzija (3x3, 5x5 ili 9x9) i sabiranjem dobijenih proizvoda. Nakon merenja performansi sekvencijalne implementacije posmatrane aplikacije pri uobičajenoj upotrebi, dobijeni su sledeći rezultati: aplikacija 30% vremena provodi obavljajući ulazno-izlazne operacije, a 70% vremena provodi u obradi podataka. Vreme potrebno da bude obrađen jedan paket podataka na uobičajenom jednoprocesorskom sistemu, čiji procesor radi na 2GHz, je u proseku 1s. Predložiti vrstu hardverske i softverske platforme za paralelnu verziju ovog programa. Obrazložiti svaku projektnu odluku (arhitektura, programski model, broj procesora itd.). Prilikom određivanja maksimalnog smislenog broja procesora, pretpostaviti da dodatno vreme uvedeno paralelizacijom ne postoji i navesti formulu za Amdalov zakon koja odgovara toj pretpostavci. 12) Posmatra se jedna naučna aplikacija koja vrši određenu fizičku simulaciju. Sama simulacija se može podeliti u pet faza, od kojih su prva i treća pogodne za paralelizaciju, a ostale nisu. Treća faza aplikacije intenzivno radi sa operativnom memorijom. Aplikacija radi nad podacima relatvino male veličine, reda veličine 1GB, a izlazni podaci su reda veličine par desetina MB. Nakon merenja performansi sekvencijalne implementacije posmatrane aplikacije pri uobičajenoj upotrebi, dobijeni su sledeći rezultati: aplikacija 10% vremena provodi obavljajući ulazno-izlazne operacije, u prvoj fazi provodi 40% vremena, u drugoj 25%, u trećoj 5% i u preostalim fazama po 10% vremena. Vreme potrebno da bude obrađen jedan paket podataka na uobičajenom jednoprocesorskom sistemu, čiji procesor radi na 2GHz, je u proseku 1000s. Predložiti vrstu hardverske i softverske platforme za paralelnu verziju ovog programa. Obrazložiti svaku projektnu odluku (arhitektura, programski model, broj procesora itd.). Prilikom određivanja maksimalnog smislenog broja procesora, pretpostaviti da dodatno vreme uvedeno paralelizacijom ne postoji i navesti formulu za Amdalov zakon koja odgovara toj pretpostavci. 11) Posmatra se jedna naučna aplikacija koja obradu nad 2D matricama velikih dimenzija, tipično oko 64GB. Glavni deo obrade se vrši unutar tri ugneždene for petlje, trougaonog tipa. Za izvršavanje ovog programa je paralelizaciju ovog programa je dostupan ccNUMA multiprocesorski sistem koji sadrži 64 jezgara, organizovanih u 8 čvorova (procesora) od 8 jezgara koja rade na 2GHz. Svaki čvor unutar sistema poseduje 16GB RAM. Nakon merenja performansi sekvencijalne implementacije posmatrane aplikacije pri uobičajenoj upotrebi, dobijeni su sledeći rezultati: aplikacija 20% vremena provodi obavljajući ulazno-izlazne operacije, a 80% vremena provodi u obradi podataka. Vreme potrebno da bude obrađen jedan paket podataka korišćenjem jednog jezgra je 1000s. Objasniti najpogodniju strategiju paralelizacije navedene aplikacije korišćenjem OpenMP tehnologije i šta je neophodno uraditi da bi se dobile nabolje performanse. Koliko je maksimalno ubrzanje moguće ostvariti na zadatom multiprocesorskom sistemu? Prilikom određivanja maksimalnog ubrzanja, pretpostaviti da dodatno vreme uvedeno paralelizacijom ne postoji i navesti formulu za Amdalov zakon koja odgovara toj pretpostavci. 10) Posmatra se jedna naučna aplikacija koja vrši obradu nad 2D matricama reda veličine nekoliko stotina MB. Nakon merenja performansi sekvencijalne implementacije posmatrane aplikacije pri uobičajenoj upotrebi, dobijeni su sledeći rezultati: aplikacija 20% vremena provodi obavljajući ulazno-izlazne operacije i memorijske transfere, a 80% vremena provodi u obradi podataka. Vreme potrebno da bude obrađen jedan skup matrica korišćenjem jednog jezgra je 1000s. Ukoliko se pokuša paralelizacija date aplikacije na grafičkom procesoru sa 30 streaming multiprocessor-a sa po 16 skalarnih procesora i 3GB RAM, koliko je maksimalno ubrzanje moguće ostvariti na zadatom multiprocesorskom sistemu? Prilikom određivanja maksimalnog ubrzanja, pretpostaviti da dodatno vreme uvedeno paralelizacijom ne postoji i navesti formulu za Amdalov zakon koja odgovara toj pretpostavci. Da li bi povećanje veličine ulaznih podataka uticalo na mogućnost primene zadatog multiprocesorskog sistema i kako? 9) Neka se posmatra jedna naučna aplikacija koja se bavi izračunavanjem elektrostatičkih potencijala indukovanih tačkastim naelektrisanjem u 3D prostoru. Prostor se predstavlja u vidu 3D matrice reda veličine 16GB. Metoda je lokalnog karaktera, odnosno sve interakcije između tačaka koje su na nekoj određenoj udaljenosti većoj od zadate se ne obrađuju. Stoga se 3D matrica može podeliti na blokove koji se uglavnom mogu nezavisno obrađivati, osim ivičnih elemenata do određene dubine. Nakon merenja performansi sekvencijalne implementacije posmatrane aplikacije pri uobičajenoj upotrebi, dobijeni su sledeći rezultati: aplikacija 10% vremena provodi obavljajući ulazno-izlazne operacije, a 90% vremena provodi u obradi podataka. Vreme potrebno da bude obrađen jedan paket podataka korišćenjem jednog jezgra je 1000s. a) [8] Ukoliko se aplikacija paralelizuje za izvršavanje na distribuiranom računarskom sistemu sa 32 čvora, od kojih se svaki sastoji od procesora na 2GHz sa 4GB memorije, navesti formulu za Amdalov zakon i odrediti maksimalno moguće ubrzanje koje se može postići. b) [7] Prilikom paralelizacije ove aplikacije na distribuiranom računarskom sistemu, kako podesiti granularnost komunikacije? Koju veličinu paketa je pogodono izabrati? Obrazložiti odgovor. 8) Neka se posmatra jedna aplikacija za obradu slike. Slike se predstavljaju pomoću 2D matrica u maksimalnoj, UHD rezoluciji 3840×2160 tačaka. Korisnik zadaje ili pojedinačne slike na obradu ili ih može zadati u tzv. batch režimu kada zadaje jednu istu operaciju koja se izvršava nad većim brojem slika istih dimenzija. Nakon merenja performansi sekvencijalne implementacije posmatrane aplikacije pri uobičajenoj upotrebi, dobijeni su sledeći rezultati: aplikacija 30% vremena provodi obavljajući ulazno-izlazne operacije, a 70% vremena provodi u obradi podataka. Vreme potrebno da bude obrađen jedna slika korišćenjem jednog jezgra je 1s. a) [8] Ukoliko se aplikacija paralelizuje za izvršavanje na SMP računaru sa deljenom memorijom i 32 procesora sa 4 jezgra na 2GHz sa 4GB memorije, navesti formulu za Amdalov zakon i odrediti maksimalno moguće ubrzanje koje se može postići za zadatu aplikaciju. b) [7] Predložiti način paralelizacije ukoliko se obrađuje pojedinačna slika i ukoliko se obrađuje više slika u batch režimu. Obrazložiti odgovor. 7) Neka se posmatra jedna aplikacija za pretraživanje i istraživanje podataka (data mining) u bazi podataka neke kompanije. Baza podataka je reda veličine nekoliko desetina GB. Korisnik zadaje složene upite nad ovakvom bazom, Nakon merenja performansi sekvencijalne implementacije posmatrane aplikacije pri uobičajenoj upotrebi, dobijeni su sledeći rezultati: aplikacija 10% vremena provodi obavljajući ulazno-izlazne operacije, a 90% vremena provodi u obradi podataka. Tipično vreme obrade jednog upita korišćenjem jednog jezgra je 100s. a) [8] Ukoliko se aplikacija paralelizuje za izvršavanje na računarskom klasteru koji se sastoji od 16 SMP čvorova sa 4 jezgra na 3GHz sa 16GB memorije, navesti formulu za Amdalov zakon i odrediti maksimalno moguće ubrzanje koje se može postići za zadatu aplikaciju. b) [7] Pretpostaviti da se upiti u aplikaciji mogu izvršavati nezavisno jedni od drugih i da se svaki može izvršavati na jednom čvoru klastera. Ukoliko vreme izvršavanja pojedinačnih upita značajno varira, predložiti način paralelizacije koji bi obezbedio što je moguće bolje balansiranje opterećenja pod ovakvim uslovima. Obrazložiti odgovor. 6) Neka se posmatra jedna aplikacija koja vrši obradu slike. Obrada jednog piksela slike zavisi od 8 suseda. 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, a 85% vremena provodi u obradi podataka. Tipično vreme obrade jednog upita korišćenjem jednog jezgra je 10s. a) [8] Ukoliko se aplikacija paralelizuje za izvršavanje na SMP sistemu sa 8 jezgara na 3GHz sa 16GB memorije, navesti formulu za Amdalov zakon i odrediti maksimalno moguće ubrzanje koje se može postići za zadatu aplikaciju. b) [7] Diskutovati uticaj dekompozicije domena problema na performanse aplikacije na sistemu opisano pod a). Da li je bolja blokovska ili ciklična dekompozicija i po kojim dimenzijama? Obrazložiti odgovor. 5) 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. a) [7] 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. 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. ROK: chrome-extension://efaidnbmnnnibpcajpcglclefindmkaj/http://mups.etf.rs/ispiti/2018-2019/si4mps_k1_20182019.pdf 4) 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. a) [7] 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. b) [8] 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? 3) Neka se posmatra jedna aplikacija za prikupljanje i agregaciju podataka sa interneta. Aplikacija se sastoji od veb tragača (web crawler) koji prikuplja određene informacije na internetu, a zatim se radi obrada. Nakon merenja performansi sekvencijalne implementacije posmatrane aplikacije pri uobičajenoj upotrebi, dobijeni su sledeći rezultati: aplikacija 45% vremena provodi obavljajući ulazno-izlazne operacije (sekvencijalno prikupljanje podataka iz jednog izvora), a 55% vremena provodi u obradi podataka. Tipično vreme obrade jednog paketa podataka korišćenjem jednog jezgra je 1s. a) [7] Ukoliko se aplikacija paralelizuje za izvršavanje na SMP sistemu sa 8 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. b) [8] Da li i na koji način može organizovati paralelno izvršavanje sekvencijalnog dela aplikacije, ukoliko paketi sa interneta mogu nezavisno da se obrađuju? Smatrati da paketi imaju neujednačeno vreme obrade i diskutovati moguće načine paralelne obrade. 1) Neka se posmatra jedna numerička simulacija. Aplikacija najpre učitava parametre simulacije, zatim rešava složene sisteme linearnih diferencijalnih jednačina i na kraju upisuje rezultate svoga rada. 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, a 95% vremena provodi u obradi podataka. Tipično vreme obrade u okviru simulacije korišćenjem jednog jezgra je 1000s. a) [7] Ukoliko se aplikacija paralelizuje za izvršavanje na SMP sistemu sa 4 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 sa datom konfiguracijom. b) [8] Šta predstavlja osobina skalabilnosti u kontekstu paralelnog računarstva i specifično paralelnog hardvera? Da li bi dodavanje novih procesorskih jezgara u slučaju pod a) doprinelo ubrzavanju opisane paralelne aplikacije i u kojim slučajevima? 2) Neka se posmatra jedna aplikacija koja vrši obradu video snimka. Aplikacija najpre učitava video snimak visoke rezolucije, tipično 3840 x 2160 sa 60 slika u sekundi (frames per second – FPS), zatim primenjuje zadate filtere i na kraju upisuje rezultate svoga rada. 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, a 95% vremena provodi u obradi podataka. Tipično vreme obrade pojedinačne slike (frame-a) korišćenjem jednog jezgra je 50ms. a) [7] Ukoliko se aplikacija paralelizuje za izvršavanje na SMP sistemu sa 4 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 sa datom konfiguracijom. Da li je postignuto ubrzanje u slučaju pod a) dovoljno da se postigne prikazivanje obrađenog snimka u realnom vremenu, odnosno da se zadrži FPS od 60 slika po sekundi? Diskutovati moguće načine za paralelizaciju obrade, kao i hardverske alternative koje bi omogućile postizanje odgovarajućeg FPS. Smatrati da se pojedinačne slike u okviru snimka mogu nezavisno obrađivati. | ✅ 7) Nakon merenja performansi nekog sekvencijalnog programa pri uobičajenoj upotrebi,, dobijeni su sledeći rezultati: program 15% vremena provodi čekajući na korisnika, 85% vremena provodi računajući. Podaci koje program obrađuje su takvi da među njima postoje zavisnosti unutar jednog paketa podataka i da nema zavisnosti između paketa, ali su svi paketi takvi da zavise od poslednje aktivnosti korisnika. Veličina paketa je u proseku 10kB. Vreme potrebno da bude obrađen jedan paket na uobičajenom jednoprocesorskom sistemu, čiji procesor radi na 2GHz, je u proseku 1s. Predložiti vrstu hardverske i softverske platforme za paralelnu verziju ovog programa. Obrazložiti svaku projektnu odluku (arhitektura, programski model, broj procesora itd.). Prilikom određivanja maksimalnog smislenog broja procesora, pretpostaviti da dodatno vreme uvedeno paralelizacijom ne postoji i navesti formulu za Amdalov zakon koja odgovara toj pretpostavci. 6) Nakon merenja performansi nekog sekvencijalnog programa pri uobičajenoj upotrebi, dobijeni su sledeći rezultati: program 90% vremena provodi čekajući na korisnika, 10% vremena provodi računajući, pri čemu skoro sve ovo vreme odlazi na sortiranje celog paketa ulaznih podataka. Podaci koje program obrađuje su takvi da nema zavisnosti između paketa, ali su svi paketi takvi da zavise od poslednje aktivnosti korisnika koja uvek rezultira jednim paketom. Veličina paketa je u proseku 100kB. Vreme potrebno da bude obrađen jedan paket na uobičajenom jednoprocesorskom sistemu je u proseku 500ms. Predložiti vrstu hardverske i softverske platforme za paralelnu verziju ovog programa. Obrazložiti svaku projektnu odluku (eventualne promene programskog koda radi postizanja ubrzanja, arhitektura, programski model, broj procesora itd.). Prilikom određivanja maksimalnog smislenog broja procesora, pretpostaviti da dodatno vreme uvedeno paralelizacijom ne postoji i navesti formulu za Amdalov zakon koja odgovara toj pretpostavci. 5) .Nakon merenja performansi nekog sekvencijalnog programa pri uobičajenoj upotrebi, dobijeni su sledeći rezultati: program 55% vremena provodi čekajući da korisnik izabere fajl sa ulaznim podacima, 30% vremena provodi učitavajući ulazne podatke i 15% vremena provodi u obradi podataka. Drugi, znatno češći, scenario upotrebe programa je paketna obrada, kada korisnik zadaje spisak fajlova koje program treba da obradi. Podaci koje program obrađuje su unutar fajla organizovani u vidu stabla u kome postoje zavisnosti između čvorova. Po učitavanju, podaci su u memoriji organizovani u vidu dvodimenzionalnog niza. Obrada podataka je takva da unutar jednog niza nema zavisnosti između elemenata. Veličina jednog fajla je u proseku 10 MiB. Veličina učitanih podataka je u proseku 80MiB. Vreme potrebno da bude učitan i obrađen jedan fajl na sistemu sa jednim jednojezgarnim procesorom, koji radi na 2 GHz, je u proseku 6 sekundi. Predložiti vrstu hardverske i softverske platforme za paralelnu verziju ovog programa. Obrazložiti svaku projektnu odluku (arhitektura, programski model, broj procesora itd.). Prilikom određivanja maksimalnog smislenog broja procesora, pretpostaviti da dodatno vreme uvedeno paralelizacijom ne postoji i navesti formulu za Amdalov zakon koja odgovara toj pretpostavci. 4) Nakon merenja performansi nekog sekvencijalnog programa pri uobičajenoj upotrebi, dobijeni su sledeći rezultati: program 10% vremena provodi čekajući da korisnik izabere fajl sa ulaznim podacima, 20% vremena provodi učitavajući ulazne podatke i 70% vremena provodi u obradi podataka. Podaci koje program obrađuje su unutar fajla organizovani po međusobno nezavisnim paketima. Obrada jednog paketa ne može početi pre nego ceo paket bude učitan. Obrada podataka je takva da unutar jednog paketa postoje manje zavisnosti između elemenata. Po učitavanju paketa, podaci su u memoriji organizovani u vidu dvodimenzionalnog niza. Veličina jednog paketa unutar fajla je u proseku 30 KiB. Fajlovi sa paketima su nezavisni od aktivnosti korisnika i imaju visoko regularne nazive. Veličina učitanih podataka jednog paketa je u proseku 1 MiB. Rezultat obrade je veličine do 100 B. Vreme potrebno da bude učitan i obrađen jedan paket na sistemu sa jednim jednojezgarnim procesorom, koji radi na 2 GHz, je u proseku 0.9 sekundi. Predložiti vrstu hardverske i softverske platforme za paralelnu verziju ovog programa. Obrazložiti svaku projektnu odluku (arhitektura, programski model, broj procesora itd.). Prilikom određivanja maksimalnog smislenog broja procesora, uzeti u obzir dodatno vreme uvedeno paralelizacijom i navesti izmenjenu formulu za Amdalov zakon koja odgovara toj pretpostavci. 3) Nakon merenja performansi nekog sekvencijalnog programa pri uobičajenoj upotrebi, dobijeni su sledeći rezultati: program 90% vremena provodi čekajući da korisnik izabere fajlove sa ulaznim podacima, 1% vremena provodi učitavajući ulazne podatke i 9% vremena provodi u obradi podataka. Program obrađuje grupu fotografija istih dimenzija i na osnovu određenog algoritma dolazi do nove fotografije. Algoritam uzima piksele na istom mestu u ulaznim fotografijama i izračunava vrednosti za novi piksel na datom mestu. Deo programa koji učitava pojedinačnu fotografiju sliku iz fajla je relativno složen i težak za razumevanje. Po učitavanju, pikseli fotografije su u memoriji organizovani u vidu dvodimenzionalnog niza. Fotografije su u rezoluciji 2816×2112, snimljene sa stepenom kompresije od prosečno 50%. Vreme potrebno da bude učitana i obrađena grupa slika na sistemu sa jednim jednojezgarnim procesorom, koji radi na 2 GHz, je u proseku 10 sekundi. Predložiti vrstu hardverske i softverske platforme za paralelnu verziju ovog programa. Obrazložiti svaku projektnu odluku (arhitektura, programski model, broj procesora itd.). Prilikom određivanja maksimalnog smislenog broja procesora, pretpostaviti da dodatno vreme uvedeno paralelizacijom ne postoji i navesti formulu za Amdalov zakon koja odgovara toj pretpostavci. 2) Nakon merenja performansi nekog sekvencijalnog programa pri uobičajenoj upotrebi, dobijeni su sledeći rezultati: program 1% vremena provodi čekajući da korisnik kofiguriše obradu, 17% vremena provodi učitavajući ulazne podatke i 82% vremena provodi u obradi podataka. Podaci koje program obrađuje su unutar fajla organizovani po međusobno nezavisnim paketima čija veličina ne prelazi 10KiB. Obrada jednog paketa traje dosta dugo i prilično je komplikovana. Rezultat obrade je veličine do 100KiB. Vreme potrebno da bude učitan i obrađen jedan paket na sistemu sa jednim jednojezgarnim procesorom, koji radi na 2 GHz, je u proseku 1 sekunda. Predložiti vrstu hardverske i softverske platforme za paralelnu verziju ovog programa. Obrazložiti svaku projektnu odluku (arhitektura, programski model, broj procesora itd.). Prilikom određivanja maksimalnog smislenog broja procesora, pretpostaviti da dodatno vreme uvedeno paralelizacijom ne postoji i navesti formulu za Amdalov zakon koja odgovara toj pretpostavci. 1) Posmatra se jedna naučna aplikacija koja vrši simulaciju određenog fizičkog procesa. Nakon merenja performansi sekvencijalne implementacije posmatrane aplikacije pri uobičajenoj upotrebi, dobijeni su sledeći rezultati: aplikacija 20% vremena provodi obavljajući ulaznoizlazne operacije, a 80% vremena provodi u obradi podataka. Podaci koje program obrađuje su organizovani u vidu paketa, takvih da postoje zavisnosti unutar jednog paketa podataka i da nema zavisnosti između paketa, osim eventualno na početku i na kraju obrade. Obrada jednog paketa podataka zahteva veliku količinu operativne memorije za privremene podatke, tipično više od 2GB. Vreme potrebno da bude obrađen jedan paket podataka na uobičajenom jednoprocesorskom sistemu, čiji procesor radi na 2GHz, je u proseku 1s. Predložiti vrstu hardverske i softverske platforme za paralelnu verziju ovog programa. Obrazložiti svaku projektnu odluku (arhitektura, programski model, broj procesora itd.). Prilikom određivanja maksimalnog smislenog broja procesora, pretpostaviti da dodatno vreme uvedeno paralelizacijom ne postoji i navesti formulu za Amdalov zakon koja odgovara toj pretpostavci. | |||||||||||||||||
5 | Jun 2023 | K1 2020 2) | Jun 2020 1) | K2 2023 1) | K2 2023 3) | K3 2023 2) | K3 2023 4) | ✅ Neka se posmatra kod u prilogu koji određuje ukupan broj prostih brojeva od 2 do N. Ukoliko je potrebno navedeni kod paralelizovati korišćenjem OpenMP biblioteke, navesti odgovarajuću direktivu i posebno diskustovati potrebu za korišćenjem odredbi koje definišu deljene i privatne promenljive. Objasniti kada je njihovo navođenje potrebno i zašto. for ( i = 2; i <= n; i++ ) { prime = 1; for ( j = 2; j < i; j++ ) if ( i % j == 0 ) { prime = 0; break; } total = total + prime; } | K2 2023 6) | Koristeći CUDA tehnologiju, paralelizovati kod u prilogu koji vrši izračunavanje srednje brzine niza čestica prilikom rešavanja nekog problema molekularne dinamike u 3D prostoru. Podaci brzini jedne čestice su dati u korespodentnim lokacijama nizova vh_x, vh_y i vh_z. Obratiti pažnju na efikasnost i korektnost paralelizacije. double velavg(int npart, double vh_x[], double vh_y[], double vh_z[], double h){ double vel = 0.0, sq; for (int i = 0; i < npart; i++){ sq = sqrt(vh_x[i] * vh_x[i] + vh_y[i] * vh_y[i] + vh_z[i] * vh_z[i]); vel += sq; } vel /= h; return vel; } | Dat je multiprocesorski sistem sa 4 identična procesora, koji koristi MOESI protokol za održavanje koherencije keš memorije. Svaka keš memorija ima po 2 ulaza, koji su veličine jedne reči. Preslikavanje je direktno. Početne vrednosti podataka su 0. Svaki upis uvećava vrednost izmenjenog podatka za 1. Na početku su sve keš memorije prazne. Data je sledeća sekvenca pristupa memoriji: Napisati stanja koherencije u svim procesorima i stanje memorije posle svake promene i skicirati opisani sistem u trenutku 8. [8 poena] Da li procesori pristupaju memoriji i kada? Za svaki pristup navesti razlog. VIDETI ROK: chrome-extension://efaidnbmnnnibpcajpcglclefindmkaj/http://mups.etf.rs/ispiti/2022-2023/mps _jun_20222023.pdf ❌✅ | |||||||||||||||
6 | Jul 2023 | K1 2023 1) | ❌ Opisati karakteristike sistolnih arhitektura. Diskutovati prednosti i nedostatke. Objasniti prinsip rada sistolnih arhitektura kao i njihove karakteristike. Šta su wavefront procesori? Koje su njihove prednosti i koje aplikacije efikasno podržavaju. | K2 2023 3) | K2 2023 2) | ❌✅ Komparativno objasniti strukuru kataloga i operacije kod protokola DiriNB i DiriB. Objasniti i uporediti Diri B i Diri NB protokole. Objasniti sličnosti i razlike Diri B i Diri NB protokola. Diskutovati performanse. | K3 2023 3) | ✅ Šta su to virtuelne topologije kod MPI biblioteke? Navesti vrste ovih topologija, kao i prednosti i mane njihovog korišćenja. Šta su to virtuelne topologije i koje su prednosti njihovog korišćenja kod paralelizacije koda MPI bibliotekom? Napisati deo koda koji od postojećeg MPI sveta kreira Dekartovu topologiju dimenzija 4x4, periodičnu po x osi. Smatrati da MPI svet sadrži više od 16 procesa. Čemu služe virtuelne topologije u MPI standardu? Kakva je to Dekartova virtuelna topologija i šta njome omogućava? | Funkcija u prilogu može prouzrokovati određene probleme sa performansama prilikom izvršavanja na GPU kada se istovremeno pozove iz jezgra od strane više niti. Navesti i objasniti koji su to problemi i napisati alternativnu verziju funkcije koja te probleme rešava ili umanjuje. __device__ int calc (int arg) { int result; if (threadIdx.x % 2) result = foo(arg); else result = bar(arg); return result; } | ✅ Koristeći OpenMP tehnologiju paralelizovati funkciju koja računa histogram osvetljenja (alpha) date slike na vidljivim pixelima. Smatrati da osvetljenje može uizmati najviše 255 različitih vrednosti. Obratiti pažnju na efikasnost paralelizacije i sinhronizacije i obrazložiti upotrebljeni konstrukt. struct Pixel{ unsigned char r, g, b, alpha; }; void histogram(Pixel** image, int* histo, int h, int w) { for (int i=0; i<255; i++) { histo[i] = 0; } for (int i=0; i<w; i++) { for (int j=0; i<h; j++) { if (image[j][i].alpha != 0) histo[image[j][i].alpha]++; } | Dat je multiprocesorski sistem sa 4 identična procesora, koji koristi Firefly protokol za održavanje koherencije keš memorije. Svaka keš memorija ima po 2 ulaza, koji su veličine jedne reči. Preslikavanje je direktno. Početne vrednosti podataka su 0. Svaki upis uvećava vrednost izmenjenog podatka za 1. Na početku su sve keš memorije prazne. Data je sledeća sekvenca pristupa memoriji: Napisati stanja koherencije u svim procesorima i stanje memorije posle svake promene i skicirati opisani sistem u trenutku 8. [8 poena] Da li procesori pristupaju memoriji i kada? Za svaki pristup navesti razlog. VIDETI ROK: chrome-extension://efaidnbmnnnibpcajpcglclefindmkaj/http://mups.etf.rs/ispiti/2022-2023/mps_jul_20222023.pdf ❌✅ | |||||||||||||||
7 | Feb 2023 | K1 2023 1) | ❌ Objasniti karakteristike programskog modela Data parallel kao i aplikcaije koje odgovaraju ovakvom modelu. Nacrtati i objasniti arhitekturu koja podržava ovaj model. Objasniti karakteristike programskog modela Data parallel, kao i karakteristike arhitektura u kojima se koristi. | K2 2023 3) | ❌✅ Objasniti motivaciju za adaptivne protokole. Ukratko opisati njihovu strategiju i način rada. Zašto su potrebni adaptivni protokoli i kakva je njihova logika? Načelno opisati hardversku realizaciju takvog protokola. Objasniti logiku i strategiju adaptivnih protokola. Ukratko opisati stanja i akcije RWB protokola? Diskutovati postavljeni invalidacioni prag. Objasniti logiku i strategiju adaptivnih protokola. Ukratko opisati stanja i akcije RWB protokola. Diskutovati njegov invalidacioni prag. Objasniti logiku i strategiju adaptivnih protokola za koherenciju. Objasniti motivaciju za adaptivne protokole keš koherencije. Kakav je njihov uobičajeni način rada? Objasniti kako dolazi do invalidacije u protokolu EDWP. Objasniti motivaciju za adaptivne protokole. Objasniti način rada adaptivnog protokola sa hardverskom podrškom. Objasniti motivaciju i logiku adaptivnih protokola. Koja su dodatna stanja u protokolu EDWP i koja je njihova semantika? Objasniti kako se vrši invalidacija u ovom protoklu. Objasniti motivaciju za adaptivne protokole. Koji je osnovni princip ovih protokola? Objasniti kako se u njima vrši invalidacija. Ukratko opisati logiku i realizaciju adaptivnog RWB protoka. Koji je njegov nedostatak? | ❌✅ Nacrtati i objasniti strukturu jednog ulaza kataloga Dir3 B protokola. Objasniti onovne operacije. Koji su nedostaci protokola? Objasniti strukturu kataloga u Dir4 SW protokolu. Opisati precizno operacije promašaja pri čitanju i promašaja pri upisu. Objasniti i nacrtati strukturu kataloga kod Dir3 SW protokola. Ukratko objasniti akcije protokola. Precizno objasniti funkcionisanje ovog protokola. Objasniti organizaciju kataloga i akcije protokola sa ograničenim brojem pointera koji softverski rešava problem prekoračenja (Diri SW). Diskutovati performanse. Kojoj grupi protokola priprada Diri NB? Objasniti osnovne akcije i nedostatke. Detaljno objasniti i nacrtati strukturu kataloga u protokolu Diri DP. Precizno objasniti funkcionisanje ovog protokola. Objasniti strukturu (kataloga) i način održavanja kataloga kod Diri SW protokola. Objasniti strukturu kataloga i funkcionisanje Diri DP protokola sa dinamičkim pointerima. Objasniti organizaciju katalog i način rada protokola DiriSW. Kometarisati performanse. Objasniti strukturu kataloga, funkcionisanje, prednosti i nedostatke Diri B protokola. Objasniti kako izgleda katalog kod Diri B protokola. Precizno objasniti odvijanje promašaja pri čitanju i pogotka pri upisu. Diskutovati performanse. Objasniti organizaciju kataloga kod Diri SW protokola i opisati njegove akcije. Od čega zavise njegove performanse? Objasniti organizaciju informacija o koherenciji i akcije Diri SW protokola | Objasniti organizaciju, akcije i transakcije u hijerarhijskom sistemu sa distribuiranom memorijom. | Navesti i objasniti na koji način se vrši i od čega zavisi raspodela blokova po multiprocesorskim jedinicama prilikom izvršavanja niti na grafičkom procesoru. U kojim situacijama može doći do redukcije paralelizma i od čega to zavisi? Navesti i objasniti na koji način se vrši i od čega zavisi raspodela registara prilikom izvršavanja niti na grafičkom procesoru. Kako potrebe za registrima mogu uticati na performanse izvršavanja programskog koda? Zbog čega je bitan pristup memoriji u transakcijama na grafičkom procesoru i kako on utiče na performanse? Kada se dešava pristup u više transakcija? Odgovor ilustrovati slikom. Na koji način se vrši alokacija registara prilikom izvršavanja koda na grafičkom procesoru i kako to utiče na performanse izvršavanja koda? Kako se vrši alokacija registara na grafičkom procesoru i da li to može da utiče na performanse izvršavanog jezgra? Nacrtati i objasniti tipičnu arhitekturu jedne multiprocesorske jedinice u okviru grafičkog procesora (streaming multiprocessor). Na koji način se blokovi niti izvršavaju na jednoj multiprocesorskoj jedinici i kako se čuvaju i nformacije o nitima? Gde se i kako izvršavaju blokovi niti na grafičkom procesoru? Na koji način je postignuta skalabilnost izvršavanja jezgra? Kako se izvršavaju blokovi niti na jednom streaming multiprocesoru grafičkog procesora? Da li se sve niti izvršavaju u isto vreme ili ne? | Jun 2023 8) | ✅ Korišćenjem OpenMP biblioteke, paralelizovati kod u prilogu koji vrši numeričku integraciju korišćenjem kvadraturnog pravila nad prstenom. Obratiti pažnju na efikasnost i korektnost paralelizacije. void annulus_rule_compute ( double center[2], double r1, double r2, int nr, int nt, double w[], double x[], double y[] ) { double a, area, b, c, d, *ra, *rw, t, tw; int i, j, k; const double r8_pi = 3.141592653589793; ra = ( double * ) malloc ( nr * sizeof ( double ) ); rw = ( double * ) malloc ( nr * sizeof ( double ) ); legendre_ek_compute ( nr, ra, rw ); a = -1.0; b = +1.0; c = r1 * r1; d = r2 * r2; for ( i = 0; i < nr; i++ ) ra[i] = sqrt ( ra[i] ); for ( i = 0; i < nr; i++ ) rw[i] = rw[i] / ( r2 + r1 ) / ( r2 - r1 ); tw = 1.0 / ( double ) ( nt ); area = annulus_area ( center, r1, r2 ); k = 0; for ( i = 0; i < nt; i++ ) { t = 2.0 * r8_pi * ( double ) ( i ) / ( double ) ( nt ); for ( j = 0; j < nr; j++ ) { x[k] = center[0] + ra[j] * cos ( t ); y[k] = center[1] + ra[j] * sin ( t ); w[k] = area * tw * rw[j]; k = k + 1; } } free ( ra ); free ( rw ); return; } | Dat je multiprocesorski sistem sa 4 identična procesora, koji koristi MOESI protokol za održavanje koherencije keš memorije. Svaka keš memorija ima po 2 ulaza, koji su veličine jedne reči. Preslikavanje je direktno. Početne vrednosti podataka su 0. Svaki upis uvećava vrednost izmenjenog podatka za 1. Na početku su sve keš memorije prazne. Data je sledeća sekvenca pristupa memoriji: Napisati stanja koherencije u svim procesorima i stanje memorije posle svake promene i skicirati opisani sistem u trenutku 8. [8 poena] Da li procesori pristupaju memoriji i kada? Za svaki pristup navesti razlog. [2 poena] VIDETI LINK: chrome-extension://efaidnbmnnnibpcajpcglclefindmkaj/http://mups.etf.rs/ispiti/2022-2023/mps_februar_ 20222023.pdf ✅ | |||||||||||||||
8 | Avg 2023 | ❌ Ukratko objasniti na kojim nivoima paralelizma se istorijski zasnivalo poboljšanje performansi računara. Opisati istorijske trendove u arhitekturi računara u pogledu ostvarivanja paralelizma obrade. | ❌ Objasniti strukturu i osnovne karakteristike NUMA arhitektura. Diskutovati prednosti i nedostatke u odnosu na UMA arhitekturu. "Nacrtati UMA i NUMA arhitekture. Objasniti sličnosti i razlike između njih. " Po čemu se NUMA razlikuje od arhitekture sistema koji podržava model slanja poruka? Nacrtati i objasniti tipičnu strukturu sistema koji podržava model prenosa poruka. Po čemu se ona razlikuje od NUMA arhitekture? Koji programski model NUMA podržava? Kako NUMA može da se prilagođava različitim programskim modelima? Kakve su hardverske karakteristike NUMAe i šta je bitno za dobre performanse? | ❌ Detaljno objasniti samo operacije upisa u protokolu MESI i nacrtati samo deo dijagrama stanja koji se na njih odnosi. Nacrtati i precizno objasniti dijagram stanja i prelaze u protokolu MESI. objasniti prelaze vezane za operacije upisa. Opisati i objasniti dva poboljšanja protokola MESI. Kod protokola MESI objasniti: a) kako neki blok može da se nađe u stanju Shared u nekom kešu, a da nema drugih kopija istog bloka u drugim keš memorijama b) precizno opisati šta se dešava prilikom pogotka pri upisu (write hit)Kod protokola MESI precizno objasniti: a) stanja, b) transakcije na magistrali i c) akcije protokola i na strani procesora i na strani magistrale. Kod protokola MESI objasniti: a) kako neki blok može da se nađe u stanju Shared u nekom kešu, a da nema drugih kopija istog bloka u drugim keš memorijama b) precizno opisati šta se dešava prilikom pogotka pri upisu (write hit). Kod protokola MESI precizno objasniti: a) stanja, b) transakcije na magistrali i c) akcije protokola. Nacrtati dijagram stanja i prelaza. Navesti osnovne neefikasnosti ovog protokola. | ❌ Definisati svojstvo inkluzije kod keš memorija. Koji su problemi kod održavanja inkluzije, a koji su potrebni uslovni za njeno održavanje? Objasniti kako se inkluzija odražava na održavanje koherencije. Definisati svojstvo inkluzije kod keš memorija. Objasniti koje prednosti donosi inkluzija kada se radi o protokolima za koherenciju. Objasniti šta je inkluzija u keš hijerarhiji i koji su potrebni uslovi za njeno održavanje. Objasniti koje prednosti donosi inkluzija kada se radi o protokolima za koherenciju. Objasniti koje transakcije se odvijaju između dva nivoa keš memorija L1 i L2 u oba smera ako se održava inkluzija. Definisati svojstvo inkluzije kod keš memorija i objasniti zašto je poželjna. Koji se problemi javljaju kod održavanja inkuzije i koji su potrebni uslovi za njeno održavanje? ] Nacrtati sliku hijerarhijskog sistema sa distribuiranom memorijom organizovanog oko dva nivoa magistrala B1 i B2. Ako se u sistemu održava inkluzija u keš hijerarhiji opisati kako se odvijaju operacije čitanja i upisa od nekog procesora. a) Definisati pojam inkluzije u keš hijerarhiji. Objasniti šta se dobija primenom inkluzije. b) U slučaju da se održava inkluzija, objasniti koje sve se transakcije i kako obavljaju između dva nivoa keš memorije. Objasniti transakcije koje se odvijaju između dva nivoa keš memorije u hijerarhiji u kojoj se održava inkluzija. Definisati pojam inkluzije u keš hijerarhiji. Objasniti osnovnu prednost koju primena inkluzije obezbeđuje a) Definisati pojam inkluzije u keš hijerarhiji. Objasniti šta se dobija primenom inkluzije. b) U slučaju da se održava inkluzija, objasniti koje sve se transakcije i kako obavljaju između dva nivoa keš memorije. Dati primer koji ilustruje narušavanje svojstva inkluzije u dvonivoskoj hijerarhiji keš memorija. Nacrtati organizaciju hijerarhijskog sistema sa dva nivoa zasnovanog na magistralama i sa globalnom memorijom. Ako se održava inkluzija, opisati akcije koje se odvijaju između dva nivoa u oba smera. Opisati transakcije koje se u oba smera obavljaju između dva nivoa keš memorije u protokolu koji koristi inkluziju. Koje su prednosti i koji su problemi u održavanju inkluzije u hijerarhijama keš memorija? Ilustrovati jedan takav problem u dvonivoskoj hijerarhiji set-asocijativnih keš memorija sa LRU strategijom zameneDetaljno objasniti transakcije koje se odvijaju između dva nivoa hijerarhije keš memorija kada se primenjuje princip inkluzije. Definisati osobinu inkluzije. Detaljno opisati transakcije između dva nivoa hijerarhije keš memorija kada se primenjuje inkluzija. Precizno objasniti akcije koje izazivaju komunikaciju između dva nivoa u hijerarhiji keš memorija kada se koristi prinsip inkluzije. Objasniti transakcije koje se odvijaju između dva nivoa keš memorije u dvonivoskoj hijerarhiji koja poštuje princip inkluzije. Precizno objasniti transakcije između nivoa u dvonivoskoj keš hijerarhiji kada se primenjuje princip inkluzije. Objasniti šta podrazumeva održavanje inkluzije u višenivoskim keš hijerarhijama. Diskutovati probleme i prednosti. Objasniti šta podrazumeva princip inkluzije u keš hijerarhiji. Objasniti šta je neophodno na implementacionom nivou da bi se održala inkluzija? Koje su prednosti, a koji overhead-i pri održavanju inluzije? U kojim slučajevima nastaju problemi sa održavanjem inkluzije? Nacrtati i objasniti jedan primer narušavanja inkluzije u dvonivoskoj keš hijerarhiji. Detaljno objasniti transakcije koje se odvijaju između dva nivoa hijerarhije keš memorija kada se primenjuje princip inkluzije. | ❌✅ Objasniti strukturu kataloga kao i funkcionisanje full-map directory protokola. Šta je njegova osnovna prednost, a šta nedostatak? Uporediti njegove performanse sa performansama ostalih directory protokola. Objasniti organizaciju kataloga kod full-map protokola i protokola sa ograničenim brojem pointera. Uporediti ih po memorijskoj skalabilnosti i po performansi. Za full-map directory protokol objasniti organizaciju informacije o koherenciji, transakcije u mreži i akcije protokola. Nacrtati i objasniti dijagram stanja i prelaza. Objasniti i nacrtati strukturu kataloga kod full-map protokola. Detaljno objasniti akcije prilikom promašaja pri čitanju u lokalnoj keš memoriji. Kako se može optimizovati ovaj slučaj? Za full-map directory protokol objasniti organizaciju informacije o koherenciji, transakcije u mreži i akcije protokola. Nacrtati i objasniti dijagram stanja i prelaza. | ❌ Objasniti topologiju interkonekcione mreže tipa hiperkocke i njene osnovne osobine. Kolike su vrednosti karakterisičnih parametara? Nacrtati topologiju za n=4. Objasniti način povezivanja mreže i rutiranja poruka. Kolike su vrednosti karakterističnih parametara? Diskutovati prednosti i mane. Kojoj grupi interkonekcionih mreža pripada mreža tipa k-arna d-kocka. Objasniti strukturu ove mreže i nacrtati je za k = 3 i n = 81? Napisati izraze za vrednosti uobičajenih parametara u opštem slučaju? | ✅ (2-1:24:00;2:33:00) Neka se posmatra isečak koda u prilogu. Navesti gde u kodu postoje sinhronizacione tačke i objasniti da li se i na koji način može izvršiti optimizacija koda dostupnim odredbama OpenMP direktiva. #pragma omp parallel { #pragma omp for for (int i = 0; i < 10; ++i) c(i); #pragma omp single { d(); } #pragma omp for for (int i = 0; i < 10; ++i) g(i); } | Priloženi kod predstavlja jednu naivnu implementaciju broadcast operacije korišćenjem MPI tehnologije. Na koji način se nedostaci implementacije mogu ispraviti korišćenjem rutina za asinhronu komunikaciju i zašto? Napisati odgovarajući deo koda koristeći rutine za asinhronu komunikaciju. void my_bcast(void* data, int count, MPI_Datatype datatype, int root, MPI_Comm comm) { int world_rank, world_size; MPI_Comm_rank(comm, &world_rank); MPI_Comm_size(comm, &world_size); if (world_rank == root) for (int i = 0; i < world_size; i++) if (i != world_rank) MPI_Send(data, count, datatype, i, 0, comm); else MPI_Recv(data, count, datatype, root, 0, comm, MPI_STATUS_IGNORE); } 💻 | Korišćenjem CUDA tehnologije, paralelizovati kod u prilogu. Obratiti pažnju na efikasnost i korektnost paralelizacije. void calc(float *x, float *y, float *work1, float *work2, int *ind,int n) { int i; for( i=0;i < n;i++) { x[i]= randPoint(); y[i]= randPoint(); ind[i]= calcIndex(x[i], y[i]); work1[i]=i; work2[i]=i*i; } for( i=0;i< n;i++) { x[ind[i]] += work1[i]; y[i] += work2[i]; } } | Dat je multiprocesorski sistem sa 4 identična procesora, koji koristi WTI protokol za održavanje koherencije keš memorije. Svaka keš memorija ima po 2 ulaza, koji su veličine jedne reči. Preslikavanje je direktno. Početne vrednosti podataka su 0. Svaki upis uvećava vrednost izmenjenog podatka za 1. Na početku su sve keš memorije prazne. Data je sledeća sekvenca pristupa memoriji: Napisati stanja koherencije u svim procesorima i stanje memorije posle svake promene i skicirati opisani sistem u trenutku 8. [8 poena] Da li procesori pristupaju memoriji i kada? Za svaki pristup navesti razlog. [2 poena] VIDETI ROK: chrome-extension://efaidnbmnnnibpcajpcglclefindmkaj/http://mups.etf.rs/ispiti/2022-2023/mps_avg_20222023.pdf ❌✅ | |||||||||||||||
9 | K3 2022 | K3 2023 2) | K3 2023 1) | Avg 2023 4) | Avg 2023 6) | U prilogu je dati CUDA jezgro za određivanje statistike pojavljivanja (histograma) mali slova engleskog alfabeza po podskupovima a-d, e-h, i-l, m-p, q-t, u-x, y-z. Kakve su performanse zadatog jezgra u smislu broja operacija u odnosu na broj pristupa globalnoj memoriji i šta predstavlja najveće usko grlo u tom smislu? Kojom tehnikom se ovo rešenje može poboljšati? Skicirati i diskutovati. __global__ void histo_kernel(unsigned char *buffer, long size, unsigned int *histo) { int i = threadIdx.x + blockIdx.x * blockDim.x; int stride = blockDim.x * gridDim.x; while (i < size) { int alphabet_position = buffer[i] – “a”; if (alphabet_position >= 0 && alpha_position < 26) atomicAdd(&(histo[alphabet_position/4]), 1); i += stride; } } | Definisati izvršni model CUDA arhitekture. Na koji način se elementi programskog modela preslikavaju na hardverske elemente grafičkog procesora? Nacrtati odgovarajuću sliku i objasniti. Nacrtati i objasniti memorijsku hijerarhiju grafičkog procesora koji podržava CUDA arhitekturu. Posebno naglasiti vremena pristupa pojedinim delovima hijerarhije i ko može da pristupa i na koji način delovima hijerarhije. Objasniti razliku između korišćenja registara i lokalne memorije prilikom alokacije promenljivih koje koristi jedna nit prilikom izvršavanja jezgra na grafičkom procesoru koji podržava CUDA tehnologiju. Koji način alokacije je bolji i da li postoje ograničenja? Šta označva pojam branch divergence i kako on utiče na izvršavanje koda na SIMD procesorima? Objasniti kada i kako se ovaj efekat javlja kod CUDA grafičkih procesora. | Koristeći CUDA tehnologiju paralelizovati deo koda koji rešava 2D Laplasovu jednačinu. Koristiti 2D organizaciju jezgra. Obratiti pažnju na efikasnost paralelizacije i koristiti deljenu memoriju, ukoliko je moguće. Smatrati da su podaci već inicijalizovani, a memorijski transferi izvršeni. Napisati poziv jezgra. 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++; } | ||||||||||||||||||
10 | K2 2022 | ❌ Objasniti dva slučaja kada procesi imaju samo logički privatne podatke, a izazivaju se akcije protokola za koherenciju lObjasniti kako i kada se javlja problem koherencije keš memorija. Da li se i kada može javiti i kod logički privatnih podataka? Nabrojati prednosti korišćenja privatnih keš memorija u multiprocesorskim sistemima, kao i eventualne probleme. Objasniti kao može doći do problema keš koherencije čak i kada se radi o privatnim podacima. Kako se problem koherencije keš memorija može javiti čak i kada su podaci logički privatni za neki proces. Opisati scenario. Objasniti dve situacije kada se javlja problem koherencije čak i kada procesi imaju samo logički privatne podatke. Ilustrovati na primeru. | ❌ Objasniti motivaciju za stanje O u protokolu MOESI. Kakva je semantika ovog stanja? Precizno opisati sve prelaze iz ovog stanja i prelaze u ovo stanje. Koja operacija se optimizuje u MOESI protokolu? Objasniti stanja i karakterisati ih u pogledu validnosti, ekskluzivnosti i vlasništva ? | ❌ Objasniti 4C model promašaja u keš memorijama. Objasniti svaku vrstu promašaja kao i načn da se broj promašaja pojedine vrste smanji. Objasniti uticaj povećanja veličine keš memorije na različite vrste promašaja u keš memoriji. Objasniti vrste promašaja koji nastaju zbog održavanja koherencije. Kako se broj promašaja može smanjiti? Objasniti kako povećanje veličine keš memorije utiče na razne vrste promašaja iz 4C modela. Objasniti kako se mogu klasifikovati vrste promašaja u keš memorijama multiprocesorskih sistema. Kako se broj promašaja po pojedinim klasama može smanjiti? Objasniti na koje vrste promašaja u keš memoriji utiče povećanje veličine bloka i na koji način. Objasniti tipove promašaja koji se javljaju u multiprocesorskim sistemima (4C model) i njihove uzroke. Objasniti tehnike za njihovo smanjivanje ili izbegavanje. | Feb 2023 4) | Korišćenjem MPI tehnologije paralelizovati funkciju u prilogu koja vrši određenu vrstu interpolacije korišćenjem sinusne transformacije. Obratiti pažnju na efikasnost paralelizacije. Smatrati da je MPI okruženje već inicijalizovano i da svi procesi treba da učestvuju u obradi. Proces sa rangom 0 dobija ulazne podatke, raspodeljuje ih ostalim procesima, učestvuje u obradi i sakuplja rezultate. Smatrati da alokacije memorije uvek uspevaju. double *sin_trans_interpolation ( int n, double a, double b, double fa, double fb, double s[], int nx, double x[] ) { double angle, f1, f2, pi = 3.141592653589793, *value; int i, j; value = new double[nx]; for (i = 0; i < nx; i++) { f1 = f1_calc(a, b, fa, gb, x[i]); f2 = 0.0; for (j = 0; j < n; j++) { angle = angle_calc(a, b, j, x[i], pi); f2 = f2 + s[j] * sin (angle); } value[i] = f1 + f2; } return value; } 💻 | ✅ VIDETI ROK: chrome-extension://efaidnbmnnnibpcajpcglclefindmkaj /http://mups.etf.rs/ispiti/2021-2022/si4mps_k2_20212022.pdf | ✅ Dat je multiprocesorski sistem sa 4 identična procesora, koji koristi MSI protokol za održavanje koherencije keš memorije. Svaka keš memorija ima po 2 ulaza, koji su veličine jedne reči. Preslikavanje je direktno. Početne vrednosti podataka su 0. Svaki upis uvećava vrednost izmenjenog podatka za 1. Na početku su sve keš memorije prazne. Data je sledeća sekvenca pristupa memoriji: Napisati stanja koherencije u svim procesorima i stanje memorije posle svake promene i skicirati opisani sistem u trenutku 8. [10 poena] Koliko puta koji od procesora pristupa memoriji? Za svaki pristup navesti razlog. [3 poena] Koliki je Hit Rate za svaki od procesora (brojati i čitanje i upis, prikazati zbirno)? [2 poena] VIDETI ROK: chrome-extension://efaidnbmnnnibpcajpcglclefindmkaj/http: //mups.etf.rs/ispiti/2021-2022/si4mps_k2_20212022.pdf | ||||||||||||||||||
11 | K1 2022 | ✅ Opisati pet tipičnih klasa računara. Navesti za koje aplikacije se obično koriste, kao i najbitnije projektne ciljeve. Opisati pet klasa savremenih računara sa naglaskom na projektne prioritete u svakoj klasi. | Avg 2023 1) | Avg 2023 2) | Feb 2023 2) | ❗ Korišćenjem OpenMP tehnologije, paralelizovati deo koda u prilogu koji pronalazi parametar alfa sa zadovoljavajućom tačnošću u metodu konjugovanih gradijenata. Obratiti pažnju na efikasnost i korektnost paralelizacije. Paralelizaciju obaviti ručnim raspoređivanjem posla nitima. Smatrati da su sve promenljive ispravno deklarisane. bool alfaSet = false; int alfaIter = 0; int step = 1; double localAlfa = alfa; double *testX = (double *) malloc(dim * sizeof(double)); while (!alfaSet) { alfaIter += step; localAlfa = pow(gamma, alfaIter - 1); for (i = 0; i < dim; i++) { testX[i] = x[i] + localAlfa * d[i]; } if (func(testX, dim) - delta * localAlfa * b <= oldFunc) { if (!alfaSet) { alfaSet = true; alfaIter = 0; alfa = localAlfa; } } } free(testX); | ❗Objasniti u kojim situacijama je pogodno koristiti koncept task-ova prilikom paralelizacije korišćenjem OpenMP tehnologije? Navesti primer. Na koji način se promenljive podrazumevano prosleđuju u okviru OpenMP task direktive? Zbog čega je to neophodno i da li je uvek neophodno? Obrazložiti odgovor. Objasniti gde i kada se završavaju poslovi generisani task direktivom kod OpenMP tehnologije. Da li programer može imati uticaja na to? Šta predstavlja koncept task switching-a kod OpenMP-a i zbog čega se on koristi? Na primeru sa slike, obeležiti tačke kod kojih može doći do task switching-a i navesti razlog. #pragma omp single { for (i=0; i < ONEZILLION; i++) #pragma omp task process(item[i]); } - resenje: za nestandardne konstrukte; tamo gde broj iteracija nije unapred poznat | K1 2023 7) | ||||||||||||||||||
12 | Sep 2022 | Jun 2020 1) | Avg 2023 2) | Avg 2023 3) | K2 2022 3) | ❌✅ Objasniti i uporediti dve varijante directory protokola sa ograničenim brojem pokazivača, sa broadcast-om i bez njega. | Avg 2023 4) | ✅ Kod u prilogu koji određuje ukupan broj prostih brojeva od 2 do N delimično je paralelizovan korišćenjem OpenMP biblioteke. Diskutovati načine za sinhronizaciju nad promenljivom total, kao i uticaj tih načina na performanse izvršavanja ovog koda. #pragma omp parallel for shared(n) private(i,j,prime) for ( i = 2; i <= n; i++ ) { prime = 1; for ( j = 2; j < i; j++ ) { if ( i % j == 0 ) { prime = 0; break; } } total = total + prime; } | Grafički procesori specifičnu organizaciju globalne i deljene memorije koja omogućava povećanje propusnog opsega memorije prilikom pristupa podacima. Objasniti način organizacije ovih memorija, kao i uslove koje niti treba da zadovolje da bi se uspešno realizovao pristup sa povećanim propusnim opsegom. Odgovor ilustrovati slikom. Na koji način se na grafičkom procesoru sakrivaju kašnjenja koja nastaju prilikom pristupa sporoj, globalnoj memoriji uređaja? Koja razlika tu postoji u odnosu na centralni procesor? Na koji način se na grafičkom procesoru sakrivaju kašnjenja koja nastaju prilikom pristupa sporoj, globalnoj memoriji uređaja? Koja razlika tu postoji u odnosu na centralni procesor? Na koji način je organizovana globalna (operativna) memorija grafičkog procesora da bi se podržao paralelizam velikog broja niti? Navesti primer jednog poželjnog obrasca pristupa memoriji. | Korišćenjem rutina iz MPI biblioteke, napisati deo koda koji vrši razmenu graničnih elemenata matrice unew. Smatrati da je matrica već ravnomerno raspodeljena procesima blokovski po kolonama i da je MPI svet već inicijalizovan. Obratiti pažnju na efikasnost komunikacije kroz korišćenje rutina za neblokirajuću komunikaciju. int nx, ny, iterations; double dx, dy, f[NX][NY], u[NX][NY], unew[NX][NY]; ... int i, it, j; for ( it = 0; it < iterations; it++ ) { for ( j = 1; j < ny - 1; j++ ) { for ( i = 0; i < nx; i++ ) { unew[i][j] = 0.25 * (u[i-1][j] + u[i][j+1] + u[i][j-1] + u[i+1][j] + f[i][j] * dx * dy ); } } /* exchange border elements */ memcpy(u, unew, ny * nx * sizeof(double)); } 💻 | Dat je multiprocesorski sistem sa 4 identična procesora, koji koristi Firefly protokol za održavanje koherencije keš memorije. Svaka keš memorija ima po 2 ulaza, koji su veličine jedne reči. Preslikavanje je direktno. Početne vrednosti podataka su 0. Svaki upis uvećava vrednost izmenjenog podatka za 1. Na početku su sve keš memorije prazne. Data je sledeća sekvenca pristupa memoriji: Napisati stanja koherencije u svim procesorima i stanje memorije posle svake promene i skicirati opisani sistem u trenutku 8. [8 poena] Da li procesori pristupaju memoriji i kada? Za svaki pristup navesti razlog. [2 poena] VIDETI ROK: chrome-extension://efaidnbmnnnibpcajpcglclefindmkaj/http://mups.etf.rs/ispiti/2021-2022/mps_sep_20212022.pdf ❌✅ | |||||||||||||||
13 | Jun 2022 | ✅ Navesti i objasniti trendove tehnologije u pogledu frekvencije takta procesora u ranijem i današnjem periodu. Objasniti i obrazložiti trendove u pogledu povećanja radne frekvencije u savremenim procesorima. Objasniti i obrazložiti trendove u pogledu povećanja radne frekvencije u savremenim procesorima. Objasniti trendove tehnologije u pogledu povećanja broja tranzistora na čipu i radne frekvencije, kao i konsekvence na rast performansi. | Jul 2018 1) | ❗ Kakvo poboljšanje donosi MOESI protokol u odnosu na MESI? Karakterisati stanja protokola u pogledu vlasništva, validnosti i eksluzivnosti. Kakva je semantika novouvedenog stanja O? Objasniti aktivnosti protokola koje se odnose na ovo stanje. | ✅ Objasniti preporuke koje treba slediti pri razvoju softvera da bi se se smanjio overhead održavanja koherencije. Objasniti o čemu mora da se vodi računa pri razvoju paralelnog softvera da bi se smanjio overhead pri održanju koherencije i poboljšale performanse. | K3 2023 1) | Avg 2023 6) | Neka se posmatra isečak koda u prilogu napisan putem CUDA tehnologije za izvršavanje na grafičkom procesoru. Objasniti koji problem postoji u kodu i navesti način kako on može da se reši. Da li se rešenjem umanjuju performanse koda? __shared__ float partialSum[SIZE]; partialSum[threadIdx.x] = X[blockIdx.x * blockDim.x + threadIdx.x]; unsigned int t = threadIdx.x; for(unsigned int stride = 1; stride < blockDim.x; stride *= 2){ if(t % (2*stride) == 0) partialSum[t] += partialSum[t+stride]; } | Neka u okviru jednog MPI programa procesi obrađuju dve velike dvodimenzionalne matrice celih brojeva. Svaki proces dobija k vrsta jedne i k kolona druge matrice na osnovu kojih radi dalju obradu i formira niz od k rezultujućih elemenata koji vraća pošiljaocu. Vrste i kolone su jednake dužine. Koji mehanizmi (komunikacione rutine) na nivou MPI biblioteke su dostupni za ovakav scenario obrade? Na koji način izvedeni tipovi mogu da se iskoriste u ovom slučaju? Navesti pozive rutina za opis tih tipova. | ✅ Korišćenjem OpenMP biblioteke, paralelizovati kod u prilogu koji vrši izračunavanje srednje brzine niza čestica prilikom rešavanja nekog problema molekularne dinamike u 3D prostoru. Podaci brzini jedne čestice su dati u tri uzastopne lokacije nizu vh. Obratiti pažnju na efikasnost i korektnost paralelizacije. double velavg(int npart, double vh[], double vaver, double h){ int i; double vaverh = vaver * h, vel = 0.0, sq; extern double count; count = 0.0; for (i = 0; i < npart * 3; i += 3){ sq = sqrt(vh[i] * vh[i] + vh[i+1] * vh[i+1] + vh[i+2] *vh[i+2]); if (sq > vaverh) count++; vel += sq; } vel /= h; return(vel); } | Dat je multiprocesorski sistem sa 4 identična procesora, koji koristi WTI-allocate protokol za održavanje koherencije keš memorije. Svaka keš memorija ima po 2 ulaza, koji su veličine jedne reči. Preslikavanje je direktno. Početne vrednosti podataka su0. Svaki upis uvećava vrednost izmenjenog podatka za 1. Na početku su sve keš memorije prazne. Data je sledeća sekvenca pristupa memoriji: Napisati stanja koherencije u svim procesorima i stanje memorije posle svake promene i skicirati opisani sistem u trenutku 8. [8 poena] Da li procesori pristupaju memoriji i kada? Za svaki pristup navesti razlog. [2 poena] VIDETI ROK: chrome-extension://efaidnbmnnnibpcajpcglclefindmkaj/http://mups.etf.rs/ispiti/2021-2022/mps_jun_20212022.pdf ❌✅ | |||||||||||||||
14 | Jul 2022 | K1 2023 2) | ✅ Opisati osnovne karakteristike programskog modela paralelnih podataka. Nacrtati i opisati tipičnu arhitekturu. Nacrtati arhitekturu koja podržava programski model paralelnih podataka i objasniti njene osnovne karakteristike. Šta su vektorski računari? | Avg 2023 3) | K2 2023 2) | K3 2023 2) | K3 2023 3) | ✅ (2-1:25:40) Koja je razlika između critical i atomic direktiva kod OpenMP-a? U čemu je prednost korišćenja atomic u odnosu na critical direktivu ili obratno? Navesti primer. | Koja je prednost korišćenja jednostrane komunikacije između više procesa u MPI? Na primeru koda u prilogu, komentarisati korektnost i performanse i napisati alternativu koja koristi rutine za jednostranu komunikaciju uz alokaciju potrebnih resursa. for (int i=0; i<num_proc; i++) { if(rank!=i && x%4==i%4){ MPI_Send((&y, 1, MPI_INT, 0, 100, MPI_COMM_WORLD); MPI_Recv((&x, 1, MPI_INT, 0, 100, MPI_COMM_WORLD, MPI_STATUS_IGNORE); x = f(x); MPI_Send((&x, 1, MPI_INT, 0, 100, MPI_COMM_WORLD); MPI_Recv((&y, 1, MPI_INT, 0, 100, MPI_COMM_WORLD, MPI_STATUS_IGNORE); } } | Koristeći CUDA tehnologiju paralelizovati funkciju koja računa histogram osvetljenja(alpha) date slike na vidljivim pixelima. Koristiti 2D organizaciju jezgra. Obratiti pažnju na efikasnost paralelizacije i koristiti deljenu memoriju. struct Pixel{ unsigned char r, g, b, alpha; }; void histogramCPU(Pixel** image, int* histo, int h, int w) { for (int i=0; i<w; i++) { for (int j=0; i<h; j++) { if (image[j][i].alpha != 0) histo[image[j][i].alpha]++; } __global__ void histogramGPU(Pixel** image, int* histo, int h, int w) | Dat je multiprocesorski sistem sa 4 identična procesora, koji koristi Dragon protokol za održavanje koherencije keš memorije. Svaka keš memorija ima po 2 ulaza, koji su veličine jedne reči. Preslikavanje je direktno. Početne vrednosti podataka su 0. Svaki upis uvećava vrednost izmenjenog podatka za 1. Na početku su sve keš memorije prazne. Data je sledeća sekvenca pristupa memoriji: Napisati stanja koherencije u svim procesorima i stanje memorije posle svake promene i skicirati opisani sistem u trenutku 8. [8 poena] Da li procesori pristupaju memoriji i kada? Za svaki pristup navesti razlog. [2 poena] VIDETI ROK: chrome-extension://efaidnbmnnnibpcajpcglclefindmkaj/http://mups.etf.rs/ispiti/2021-2022/mps_jul_20212022.pdf ❌✅ | |||||||||||||||
15 | Feb 2022 | Feb 2023 1) | K2 2023 1) | Objasniti kako se može smanjiti broj invalidacionih promašaja u invalidacionim protokolima. Diskutovati da li ova tehnika ima i neke nedostatke. | ❌ Definisati procesorsku lokalnost. Uporedno diskutovati prednosti i nedostatke strategija invalidacije i ažuriranja u keš protokolima. Uporediti strategije invalidacije i ažuriranja, njihove prednosti i mane. Definisati osnovni kriterijum koji utiče na njihove performanse. Šta je procesorska lokalnost? Definisati parametar koji je i ndikator procesorske lokalnosti. U odnosu na vrednost ovog parametra komentarisati kada bolje performanse ima strategija invalidacije, a kada strategija ažuriranja. Komparativno objasniti strategije invalidacije i ažuriranja kod snoopy protokola. Od čega zavise njihove performanse? Objasniti šta je upisni niz i kako se meri njegova dužina. U odnosu na to uporediti kada i zašto je bolja strategija invalidacije, a kada ažuriranje Definisati procesorsku lokalnost. Uporedno diskutovati prednosti i nedostatke strategija ažuriranja i invalidacije. 2)Šta odlučujuće utiče na izbor strategije koherencije kod snoopy protokola? U tom smislu diskutovati performanse ažurirajućih i invalidacionih protokola. 3) Objasniti logiku i motivaciju adaptivnih snoopy protokola. Objasniti njihovo adaptivno ponašanje. Šta je to invalidacioni prag i kako se on obično implementira? | Feb 2023 5) | K3 2023 4) | Feb 2023 7) | ✅ Neka se posmatra deo koda u prilogu. Izvršiti paralelizaciju koda korišćenjem OpenMP tehnologije, ukoliko je poznato da je M za red ili više veličina manje od N, a zatim objasniti da li se i na koji način može izvršiti optimizacija koda dostupnim odredbama. for (i=0; i<M; i++) { for ( j=0; j<N; j++ ) A[i][j] = 0; for ( k=0; k<N; j++ ) A[i][j] += B[i] * C[j][k] | Korišćenjem MPI biblioteke, paralelizovati kod u prilogu koji vrši detekciju ivica korišćenjem Sobel filtera. Obratiti pažnju na efikasnost i korektnost paralelizacije. Procesgospodar treba da raspodeli posao, učesvuje u obradi i prikupi rezultate. Smatrati da je MPI okruženje već inicijalizovano. void sobelFiltering(unsigned char **image1, unsigned char **image2, int weight[3][3], int x_size, int y_size, double min, max) { int x, y, i, j; double pixel_value; for (y = 1; y < y_size - 1; y++) { for (x = 1; x < x_size - 1; x++) { pixel_value = 0.0; for (j = -1; j <= 1; j++) { for (i = -1; i <= 1; i++) { pixel_value += weight[j + 1][i + 1] * image1[y + j][x + i]; } } pixel_value = MAX_BRIGHTNESS * (pixel_value - min) / (max - min); image2[y][x] = (unsigned char)pixel_value; } } } | Dat je multiprocesorski sistem sa 4 identična procesora, koji koristi Firefly protokol za održavanje koherencije keš memorije. Svaka keš memorija ima po 2 ulaza, koji su veličine jedne reči. Preslikavanje je direktno. Početne vrednosti podataka su 0. Svaki upis uvećava vrednost izmenjenog podatka za 1. Na početku su sve keš memorije prazne. Data je sledeća sekvenca pristupa memoriji: Napisati stanja koherencije u svim procesorima i stanje memorije posle svake promene i skicirati opisani sistem u trenutku 8. [8 poena] Da li procesori pristupaju memoriji i kada? Za svaki pristup navesti razlog. [2 poena] VIDETI ROK: chrome-extension://efaidnbmnnnibpcajpcglclefindmkaj/http://mups.etf.rs/ispiti/2021-2022/mps_febru ar_20212022.pdf ❌✅ | |||||||||||||||
16 | Avg 2022 | K1 2020 3) | ✅ Formalno definisati koherentan memorijski sistem. Koja je osnovna implikacija? Precizno navesti uslove da memorijski sistem bude koherentan kao i osobine koje to implicira. Navesti tri uslova koja treba da zadovolji memorijski sistem da bi bio koherentan. Koje tri osobine su ovim uslovima implicirane? | K2 2023 4) | ✅ Objasniti pojam lažnog deljenja (false sharing). Opisati dva primera kada se ono javlja. Kakve su posledice ove pojave kod invalidacionih, a kakve kod ažurirajućih protokola? Kako bi se ova pojava mogla izbeći? Objasniti šta je pravo deljenje, a šta lažno deljenje. Objasniti kako se lažno deljenje može smanjiti. Objasniti fenomen lažnog deljenja i načine njegovog ublažavanja. Šta je pravo deljenje, a šta lažno deljenje? Kako se lažno deljenje može smanjiti? Opisati fenomene pravog i lažnog deljenja. Objasniti tehnike za smanjivanje ili eliminaciju lažnog deljenja. Objasniti efekat lažnog deljenja (false sharing) kod upotrebe keš memorija. Kojim tehnikama se može umanjiti njegov uticaj? Objasniti pojave pravog deljenja (true sharing) i lažnog deljenja (false sharing). Kako povećanje veličine bloka utiče na ove pojave. Šta je lažno deljenje? Objasniti kako se ono pri pisanju paralelnih programa može smanjiti. Objasniti softverske tehnike za smanjivanje lažnog deljenja. Objasniti šta je pravo deljenje, a šta lažno deljenje. Objasniti i diskutovati tehnike za smanjenje lažnog deljenja. | K3 2023 2) | Avg 2023 4) | K1 2022 6) | Neka se posmatra isečak koda u prilogu napisan putem CUDA tehnologije za izvršavanje na grafičkom procesoru. Objasniti koji problem postoji u kodu i navesti zašto je on rešen korišćenjem atomskih operacija. Da li se rešenjem umanjuju performanse koda? Da li je alternativa korišćenje redukcije na nivou bloka? __global__ void find_matches_kernel ( int* d_a, int d_an, int* d_b, int d_bn, int min_len, int* d_matches, int* d_matches_ind) { int idx = blockIdx.x * blockDim.x + threadIdx.x; int idy = blockIdx.y * blockDim.y + threadIdx.y; int sub_len = 0; if (d_a[idx] == d_b[idy]) { while ((idx + sub_len < d_an) && (idy + sub_len < d_bn) && (d_a[idx + sub_len] == d_b[idy + sub_len])) sub_len ++; if (sub_len >= min_len) { d_matches [atomicAdd(d_matches_ind, 1)] = store_res(idx, idy, sub_len); } } return; } | Korišćenjem MPI tehnologije, paralelizovati kod u prilogu koji vrši izračunavanje srednje brzine niza čestica prilikom rešavanja nekog problema molekularne dinamike u 3D prostoru. Podaci brzini jedne čestice su dati u tri uzastopne lokacije nizu vh. Obratiti pažnju na efikasnost i korektnost paralelizacije. double velavg(int npart, double vh[], double vaver, double h){ i nt i; double vaverh = vaver * h, vel = 0.0, sq, count; count = 0.0; for (i = 0; i < npart * 3; i += 3){ sq = sqrt(vh[i] * vh[i] + vh[i+1] * vh[i+1] + vh[i+2] *vh[i+2]); if (sq > vaverh) count++; vel += sq; } vel /= h; return(vel); } | Dat je multiprocesorski sistem sa 4 identična procesora, koji koristi MESI protokol za održavanje koherencije keš memorije. Svaka keš memorija ima po 2 ulaza, koji su veličine jedne reči. Preslikavanje je direktno. Početne vrednosti podataka su 0. Svaki upis uvećava vrednost izmenjenog podatka za 1. Na početku su sve keš memorije prazne. Data je sledeća sekvenca pristupa memoriji: Napisati stanja koherencije u svim procesorima i stanje memorije posle svake promene i skicirati opisani sistem u trenutku 8. [8 poena] Da li procesori pristupaju memoriji i kada? Za svaki pristup navesti razlog. [2 poena] VIDETI ROK: chrome-extension://efaidnbmnnnibpcajpcglclefindmkaj/http://mups.etf.rs/ispiti/2021-2022/mps_avg_20212022.pdf ❌✅ | |||||||||||||||
17 | K3 2021 | ❌✅ Precizno objasniti proces zamene bloka u keš memoriji kada se primenjuju directory protokoli. Posebno diskutovati dve varijante pri zameni ažurne kopije i komparativno razmotriti konsekvence kod a) protokola sa nizom bita prisutnosti i protokola sa ograničenim brojem pokazivača i b) deljenja sa preovlađujućim upisom i deljenja sa preovlađujućim upisom. | ❌✅ Objasniti strukturu kataloga i funcionisanje DiriCVr protokola sa grubim vektorom. Ako je broj procesora p=256, koliko ja maksimalna vrednost parametra i da bi veličina kataloga bila manja nego kod full-map protokola? Ako je i=4, koliko najviše nepotrebnih invalidacija u grupi može biti poslato pri jednom upisu? Komparativno objasniti strukturu i način održavanja kataloga kod Diri B i Diri NB protokola sa grubim vektorom. Koji od njih je pogodniji za ’read-only’ i ’ read-mostly’ podatake i zašto? Kojem od njih odgovara objavljivanje zamene ažurne kopije u keš memoriji? Objasniti strukturu i način održavanja kataloga kod directory protokola sa grubim vektorom. Ukratko objasniti prednosti i nedostatke ovog protokola. Objasniti organizaciju i funkcionisanje kataloga kod directory šeme sa grubim vektorom. Ukoliko u sistemu postoji 256 procesora, a raspoloživa su četiri hardverska pokazivača po ulazu, koliko bitova ima svaki ulaz i kolika je veličina grupe? Objasniti kako izgleda katalog i kako radi directory protokol sa „grubim“ vektorom (Diri CVr). Odrediti r ako je broj procesora u sistemu 256, a i = 4. Objasniti organizaciju kataloga kod Diri CVr tehnike sa “grubim” (coarse) vektorom. Objasniti značenje parametara i i r, kao i njihovu vezu sa brojem procesora n. Opisati karakteristične osnovne akcije protokola. Objasniti strukturu kataloga i opisati osnovne akcije u protokolu koji koristi katalog sa grubim vektorom (Diri CV). | Avg 2023 4) | K3 2023 3) | ✅ Zadato CUDA jezgro dodaje vrednost elementa M[0] na svaki element niza M. Kakve su performanse zadatog jezgra u smislu broja operacija u odnosu na broj pristupa globalnoj memoriji? Da li i na koji način se ovo može poboljšati od strane programera ili izvršnog okruženja? Kako ovaj odnos generalno utiče na performanse jednog CUDA jezgra? Diskutovati. __global__ void addNumToEachElement(float* M) { i nt index = blockIdx.x * blockDim.x + threadIdx.x; M[index] = M[index] + M[0]; } | Feb 2023 7) | Koristeći CUDA tehnologiju paralelizovati funkciju koja računa vrednosti korelacije u okviru zadatog uzorka signala. Koristiti 1D organizaciju jezgra. Obratiti pažnju na efikasnost paralelizacije i koristiti deljenu memoriju. double *corr ( int n, double x[], int m ){ int i, j; double *r, xbar; r = ( double * ) malloc ( ( m + 1 ) * sizeof ( double ) ); for ( i = 0; i <= m; i++ ) r[i] = 0.0; xbar = 0.0; for ( j = 0; j < n; j++ ) xbar = xbar + x[j]; xbar = xbar / ( double ) ( n ); for ( i = 0; i <= m; i++ ) { for ( j = 0; j < n - i; j++ ) r[i] = r[i] + ( x[i+j] - xbar ) * ( x[j] - xbar ); } for ( i = 0; i <= m; i++ ) r[i] = r[i] / ( double ) ( n ); return r; } | ||||||||||||||||||
18 | K2 2021 | Okt 2009 2) | K2 2023 1) | ❌ Kakva je motivacija za unapređenje u protokolu MESIF? Objasniti semantiku dodatnog stanja. Precizno objasniti sve akcije koje su vezane za ove stanje i nacrtati samo deo dijagrama stanja vezan za ovo stanje. Kakvo poboljšanje donosi MESIF protokol u odnosu na MESI? Kakva je semantika nnovouvedenog stanja F? Objasniti aktivnosti protokola koje se odnose na ovo stanje i skicirati samo taj deo dijagrama stanja. | ✅ Diskutovati kako se reorganizacijom deljenih struktura podataka sa mogućnostima upisa u multiprocesorskom sistemu mogu poboljšati performanse u sledećim slučajevima: a) niz stuktura sa dva polja kojima pristupaju dva različita procesa i b) niz čiji elementi su manji od veličine bloka kojima pristupaju različiti procesi. | ✅ Korišćenjem MPI tehnologije paralelizovati funkciju u prilogu koja vrši pronalaženje svih indeksa u string str na kojima se nalazi znak c. Obratiti pažnju na efikasnost paralelizacije. Smatrati da je MPI okruženje već inicijalizovano i da svi procesi treba da učestvuju u obradi. Proces sa rangom 0 dobija ulazne podatke, raspodeljuje ih ostalim procesima, učestvuje u obradi i sakuplja rezultate. Pronađeni indeksi u rezultujućem nizu treba da odgovaraju ulaznom nizu. Smatrati da alokacije memorije uvek uspevaju. int* find_all_occurences(char *str, char c) { int *loc = malloc(sizeof(int) * strlen(str)), j = 0; for (int i = 0; i < strlen(str); i++) { if (str[i] == c) { loc[j++] = i; } } loc = realloc(loc, (j + 1)* sizeof(int)); loc[j] = -1; return loc; } | ❌ Kakva je uloga bafera prilikom MPI komunikacije između tačno dva procesa (pointto-point komunikacije)? Kakvu vrstu komunikacije baferi omogućavaju? Da li programer svestan postojanja bafera? Odgovor ilustrovati slikom. Kakva je uloga baferisanja u MPI komunikaciji i u kojim situacijama ono može da pomogne? Na koji način programer može da utiče na baferisanje? | ❌ Dat je multiprocesorski sistem sa 4 identična procesora, koji koristi MOESI protokol za održavanje koherencije keš memorije. Svaka keš memorija ima po 2 ulaza, koji su veličine jedne reči. Preslikavanje je direktno. Početne vrednosti podataka su 0. Svaki upis uvećava vrednost izmenjenog podatka za 1. Na početku su sve keš memorije prazne. Data je sledeća sekvenca pristupa memoriji: Napisati stanja koherencije u svim procesorima i stanje memorije posle svake promene i skicirati opisani sistem u trenutku 8. [10 poena] Koliko puta koji od procesora pristupa memoriji? Za svaki pristup navesti razlog. [3 poena] Koliki je Hit Rate za svaki od procesora (brojati i čitanje i upis, prikazati zbirno)? [2 poena] VIDETI ROK: chrome-extension://efaidnbmnnnibpcajpcglclefindmkaj/http://mups.etf.rs/is piti/2020-2021/si4mps_k2_20202021.pdf ✅ | ||||||||||||||||||
19 | K1 2021 | ❌ Objasniti promenu principa projektovanja procesora koji favorizuju paralelno procesiranje. Uporedno navesti i diskutovati starije i novije principe razvojne filozofije projektovanja procesora. Komparativno objasniti kako su se promenili principi projektovanja procesora. | ❌ Šta je pretpostavka Gustafson-ovog zakona? Izvesti i precizno objasniti ovaj zakon.Objasniti na kojim pretpostavkama se zasniva Gustafson-ov zakon i izvesti ga. Diskutovati konačan izraz i njegove konsekvence. Objasniti na kojim se pretpostavkama zasniva Gustafson-ov zakon i izvesti ga. Objasniti konačni izraz i njegove konsekvence. | ❌ Objasniti tehnološke trendove u pogledu broja tranzistora na čipu i kako se oni koriste. Kakve to ima implikacije na paralelno procesiranje? Opisati tehnološke trendove u procesorskoj tehnologiji i njihove posledice. Ukratko objasniti osnovne tehnološke trendove i njihov uticaj na performanse procesora. Objasniti trendove tehnologije po pitanju broja tranzistora na čipu i brzine takta. Objasniti uticaj trendova tehnologije na razvoj paralelnog procesiranja. Diskutovati trendove arhitekture u razvoju paralelnog procesiranja. Objasniti kako trendovi tehnologije utiču na razvoj paralelnih sistema. Objasniti uticaj trendova tehnologije na paralelno procesiranje. | K1 2023 4) | ✅ Korišćenjem OpenMP tehnologije, paralelizovati funkciju u prilogu koji računa vrednost određenog integrala korišćenjem Simpsonovog 1/3 pravila. Obratiti pažnju na efikasnost i korektnost paralelizacije. Smatrati da su sve promenljive ispravno deklarisane. float simpsons(float ll, float ul, int n) { float h = (ul - ll) / n, x[10], fx[10]; for (int i = 0; i <= n; i++) { x[i] = ll + i * h; fx[i] = func(x[i]); } float res = 0; for (int i = 0; i <= n; i++) { if (i == 0 || i == n) res += fx[i]; else if (i % 2 != 0) res += 4 * fx[i]; else res += 2 * fx[i]; } res = res * (h / 3); return res; } | ❗Da li i na koji način OpenMP podržava ugneždeni paralelizam? Da li je moguće u okviru paralelnog regiona pokrenuti novi paralelni region i pod kojim uslovima? | K1 2023 7) | ||||||||||||||||||
20 | Sep 2021 | Jun 2022 1) | ✅ Objasniti na kojem nivou (procesor, memorija, U/I) se ostvaruje komunikacija i sinhronizacija u paralelnim programskim modelima zajedničke memorije, prenosa poruka i paralenih podataka. | Avg 2021 3) | Avg 2022 4) | Jul 2021 5) | ❌ Šta su direktne interkonekcione mreže? Objasniti najvažnije parametre kojima se karakterišu, kao i njihove poželjne vrednosti? | Objasniti gde se i kako koriste eager i rendezvous tehnike prilikom komunikacije u okviru MPI biblioteke. Koje su prednosti i mane jedne i druge tehnike i da li se mogu koristiti u kombinaciji? Kakvu ulogu u implementaciji MPI biblioteke imaju message passing protokoli? Objasniti kako funkcioniše eager, a kako rendezvous message passing protokol i navesti njihove prednosti i mane. | Priloženi kod predstavlja CUDA jezgro koje vrši množenje dve matrice M i N. Kod je napisan sa određenim ograničenjima u smislu korektnosti i performansi. Objasniti koja su to ograničenja i kako ih je moguće ispraviti. __global__ void simpleMatMul(float* d_M, float* d_N, float* d_P, int width) { int row = blockIdx.y*width+threadIdx.y; int col = blockIdx.x*width+threadIdx.x; float product_val = 0 for(int k=0;k<width;k++) { product_val += d_M[row*width+k]*d_N[k*width+col]; } d_p[row*width+col] = product_val; } | ✅ Korišćenjem OpenMP tehnologije paralelizovati deo koda u prilogu koji pronalazi broj kombinacija u kojima neki broj d zadovoljava uslove Pitagorine četvorke (a2 + b2 + c2 = d2). Obratiti pažnju na efikasnost paralelizacije. Paralelizaciju sprovesti korišćenjem task-ova. int a,b,c,d, s = 0; int r[N+1]; memset(r,0,sizeof(r)); for(a=1; a<=N; a++){ for(b=a; b<=N; b++){ int aabb; if(a&1 && b&1) continue; aabb=a*a + b*b; for(c=b; c<=N; c++){ int aabbcc=aabb + c*c; d=(int)sqrt((float)aabbcc); if(aabbcc == d*d && d<=N) { r[d]+=1; s++; } } } } | Dat je multiprocesorski sistem sa 4 identična procesora, koji koristi MSI protokol za održavanje koherencije keš memorije. Svaka keš memorija ima po 2 ulaza, koji su veličine jedne reči. Preslikavanje je direktno. Početne vrednosti podataka su 0. Svaki upis uvećava vrednost izmenjenog podatka za 1. Na početku su sve keš memorije prazne. Data je sledeća sekvenca pristupa memoriji: Napisati stanja koherencije u svim procesorima i stanje memorije posle svake promene i skicirati opisani sistem u trenutku 8. [8 poena] Da li procesori pristupaju memoriji i kada? Za svaki pristup navesti razlog. [2 poena] ROK: chrome-extension://efaidnbmnnnibpcajpcglclefindmkaj/http://mups.etf.rs/ispiti/2020-2021/mps_sep_20202021.pdf ❌✅ | |||||||||||||||
21 | Jun 2021 | K1 2023 2) | Jul 2018 1) | K2 2021 3) | Feb 2022 4) | K3 2021 2) | Jul 2022 6) | ❗ Neka se posmatra isečak koda u prilogu paralelizovan putem OpenMP. Objasniti kakav problem navedeni kod rešava, kao i ulogu i neophodnost upotrebe flush direktive. #define NUM_THREADS 256 int synch[NUM_THREADS]; float work[NUM_THREADS]; float result[NUM_THREADS]; int main() { int iam, neighbor; #pragma omp parallel private(iam,neighbor) shared(work,synch) { iam = omp_get_thread_num(); synch[iam] = 0; #pragma omp barrier work[iam] = function_1(iam); #pragma omp flush(work,synch) synch[iam] = 1; #pragma omp flush(synch) neighbor = ...; while (synch[neighbor] == 0) { #pragma omp flush(synch) } #pragma omp flush(work,synch) result[iam] = function2(work[neighbor], work[iam]); } } | ✅ Neka se posmatra sledeći scenario u okviru jednog MPI programa. Procesi najpre rade nad nekim nizom n elemenata, svaki nad svojim delom. Svaki lokalno formira rezultujući niz od p << n elemenata koji je potrebno da pošalje svim ostalim procesima, kako bi nastavili obradu. Koji mehanizmi (komunikacione rutine) na nivou MPI biblioteke su dostupne za ovakav scenario obrade? Diskutovati koje alternative mogu da se koriste? | Korišćenjem CUDA tehnologije, paralelizovati kod u prilogu koji vrši detekciju ivica korišćenjem Sobel filtera. Obratiti pažnju na efikasnost i korektnost paralelizacije. Koristiti 2D organizaciju jezgra. Navesti poziv jezgra. void sobelFiltering(unsigned char **image1, unsigned char **image2, int weight[3][3], int x_size, int y_size, double min, max) { int x, y, i, j; double pixel_value; for (y = 1; y < y_size - 1; y++) { for (x = 1; x < x_size - 1; x++) { pixel_value = 0.0; for (j = -1; j <= 1; j++) { for (i = -1; i <= 1; i++) { pixel_value += weight[j + 1][i + 1] * image1[y + j][x + i]; } } pixel_value = MAX_BRIGHTNESS * (pixel_value - min) / (max - min); image2[y][x] = (unsigned char)pixel_value; } } } | Dat je multiprocesorski sistem sa 4 identična procesora, koji koristi MSI protokol za održavanje koherencije keš memorije. Svaka keš memorija ima po 2 ulaza, koji su veličine jedne reči. Preslikavanje je direktno. Početne vrednosti podataka su 0. Svaki upis uvećava vrednost izmenjenog podatka za 1. Na početku su sve keš memorije prazne. Data je sledeća sekvenca pristupa memoriji: Napisati stanja koherencije u svim procesorima i stanje memorije posle svake promene i skicirati opisani sistem u trenutku 8. [8 poena] Da li procesori pristupaju memoriji i kada? Za svaki pristup navesti razlog. [2 poena] ROK: chrome-extension://efaidnbmnnnibpcajpcglclefindmkaj/http://mups.etf.rs/ispiti/2020-2021/mps_jun_20202021.pdf | |||||||||||||||
22 | Jul 2021 | K1 2021 3) | Jul 2022 2) | K2 2023 1) | K2 2023 3) | Feb 2023 5) | Avg 2023 4) | Neka se posmatra kod u prilogu koji vrši određenu obradu nad svakim elementom niza mArr i traži minimum tako obrađenih elemenata u tom nizu. Na koje sve načine se može sprovesti raspoređivanje i obrada podataka tako da se paralelizacija obavi efikasno korišćenjem MPI tehnologija? Skicirati odgovarajući deo koda za master i procese-radnike. mArr[0] = f(mArr[0]); min = mArr[0]; for (j = 0; j < n; j++) { mArr[j] = f(mArr[j]); if (min > mArr[j]) { min = mArr[j]; } } | ✅ Na koji način se može rešiti problem atomičnog inkrementiranja brojača kod određivanja histograma na GPU? Kako takvo rešenje utiče na propusni opseg i na koji način tehnika privatizacije izlaza utiče na povećanje propusnog opsega? | ✅ Korišćenjem OpenMP biblioteke, paralelizovati kod u prilogu koji vrši detekciju ivica korišćenjem Sobel filtera. Obratiti pažnju na efikasnost i korektnost paralelizacije. void sobelFiltering(unsigned char **image1, unsigned char **image2 , int weight[3][3], int x_size, int y_size, double min, max) { int x, y, i, j; double pixel_value; for (y = 1; y < y_size - 1; y++) { for (x = 1; x < x_size - 1; x++) { pixel_value = 0.0; for (j = -1; j <= 1; j++) { for (i = -1; i <= 1; i++) { pixel_value += weight[j + 1][i + 1] * image1[y + j][x + i]; } } pixel_value = MAX_BRIGHTNESS * (pixel_value - min) / (max - min); image2[y][x] = (unsigned char)pixel_value; } } } | Dat je multiprocesorski sistem sa 4 identična procesora, koji koristi Firefly protokol za održavanje koherencije keš memorije. Svaka keš memorija ima po 2 ulaza, koji su veličine jedne reči. Preslikavanje je direktno. Početne vrednosti podataka su 0. Svaki upis uvećava vrednost izmenjenog podatka za 1. Na početku su sve keš memorije prazne. Data je sledeća sekvenca pristupa memoriji: Napisati stanja koherencije u svim procesorima i stanje memorije posle svake promene i skicirati opisani sistem u trenutku 8. [8 poena] Da li procesori pristupaju memoriji i kada? Za svaki pristup navesti razlog. [2 poena] ROK: chrome-extension://efaidnbmnnnibpcajpcglclefindmkaj/http://mups.etf.rs/ispiti/2020-2021/mps_jul_20202021.pdf | |||||||||||||||
23 | Feb 2021 | ✅ Objasniti dva osnovne indikatore performanse i trendove njihovog poboljšanja. Objasniti dva osnovna indikatora performanse računara i njihove trendove. Ukratko diskutovati trendove osnovnih indikatora performanse u računarskim sistemima. | Okt 2009 2) | Avg 2021 3) | K2 2023 2) | K3 2023 2) | ✅ Uporediti tri vrste interkonekcionih mreža: krosbar, višestepene interkonekcione mreže (MIN) i magistralu u pogledu performanse, cene i sklalabilnosti. Precizno definisati parametre direktnih interkonekcionih mreža. Za svaki od njih objasnosti zbog čega je važan i koje su poželjne vrednosti. Objasniti osnovne osobine i strukturu krosbar interkonekcione mreže. Uporediti je po ceni i performasi sa magistralom. Nabrojati glavne parametre interkonekcionih mreža. Objasniti njihov uticaj na performanse kao i poželjne vrednosti. Objasniti strukturu, karakteristike i način funkcionisanja krosbar interkonekcione mreže. Nacrtati i objasniti strukturu interkonekcione mreže tipa mesh? Definisati vrednosti bitnih parametara parametre ovih mreža i njihove poželjne vrednosti i navesti njene prednosti. Objasniti i nacrtati interkonekcionu mrežu sa topologijom krosbar. Analizirati prednosti i nedostatke, posebno u odnosu na magistralu. Nabrojati glavne parametre interkonekcionih mreža. Objasniti njihov uticaj na performanse kao i poželjne vrednosti. Navesti osnovne osobine indirektnih i direktnih interkonekcionih mreža. Nabrojati osnovne tipove u svakoj od grupa. Nacrtati i objasniti višestepenu interkonekcionu mrežu (MIN). Uporediti je po perfomansi i ceni sa crossbar-om i magistralom. 2) Nacrtati i objasniti tri vrste interkonekcionih mreža: crossbar, višestepene interkonekcione mreže (MIN) i magistralu i uporediti ih po performansama i ceni? 3) Nacrtati i objasniti strukture multiprocesorskih sistema sa zajedničkom memorijom zasnovanih na crossbar-u i magistrali. Uporediti prednosti i nedostatke ove dve interkonekcione mreže. | ❗ Navesti način i mogućnosti za korišćenje brava na OpenMP biblioteci. Da li su i kada one korisnije od drugih sinhronizacionih konstrukata? | Kako i na koji način GPU organizuje pristupe memoriji u transakcije? Na primeru strukture podataka u prilogu koja opisuje poziciju, brzinu i masu čestice u 3D prostoru, disktutovati organizaciju podataka, scenarije i broj pristupa pojedinačnim podacima u kontekstu redukcije broja pristupa memoriji. typedef struct particle_s { float px[N], py[N], pz[N]; float vx[N], vy[N], vz[N]; float mass[N]; } Particle_t; Particle_t s; | Korišćenjem MPI biblioteke, napisati deo koda procesa-gospodara za paralelizaciju koda koji je dat u prilogu i vrši normalizaciju slike. Proces-gospodar treba da raspodeli posao, učesvuje u obradi i prikupi rezultate. int index, n = width * height; float mean = 0.0, var = 0.0, svar, std; for (index = 0; index < n; index++) mean += (float)(inputImage[index]); mean /= (float)n; for(index = 0; index < n; index++) { svar = (float)(inputImage[index]) - mean; var += svar * svar; } var /= (float)n; std = sqrtf(var); for (index = 0; index < n; index++) outputImage[index] = (inputImage[index] - mean)/std; | Dat je multiprocesorski sistem sa 4 identična procesora, koji koristi MESI protokol za održavanje koherencije keš memorije. Svaka keš memorija ima po 2 ulaza, koji su veličine jedne reči. Preslikavanje je direktno. Početne vrednosti podataka su 0. Svaki upis uvećava vrednost izmenjenog podatka za 1. Na početku su sve keš memorije prazne. Data je sledeća sekvenca pristupa memoriji: Napisati stanja koherencije u svim procesorima i stanje memorije posle svake promene i skicirati opisani sistem u trenutku 8. [8 poena] Da li procesori pristupaju memoriji i kada? Za svaki pristup navesti razlog. [2 poena] ROK: chrome-extension://efaidnbmnnnibpcajpcglclefindmkaj/http://mups.etf.rs/ispiti/2020-2021/mps_februar_20202021.pdf | |||||||||||||||
24 | Avg 2021 | Jun 2023 1) | Avg 2022 1) | Objasniti sve akcije i promene stanja koje iniciraju upisi od strane procesora u protokolu Dragon. Zašto je neophodno Shared-modified stanje u protokolu Dragon? Da li bi se ono moglo izbeći i kako? Navesti osnovne neefikasnosti ovog protokola. Nacrtati i objasniti odgovorajuće delove dijagama stanja i prelaza. Kod protokola Dragon precizno objasniti: a) kakva je uloga stanja Shared-Modified i kako bi se ono moglo izbeći, b) precizno opisati šta se dešava prilikom pogotka pri upisu (write hit). Opisati situacije u protokolu Dragon kada postoji samo jedna kopija nekog bloka u keš memorijama, a da to protokol ne može da prepozna. Kako do ovih situacija dolazi i kako bi mogle da se izbegnu? Precizno opisati sve akcije i prelaze između stanja u protokolu Dragon u kojima se koristi dinamička detekcija deljivosti. Za protokol Dragon: a) definisati semantiku stanja, b) precizno objasniti akcije koje se dešavaju prilikom upisa ( WH, WM). c) nacrtati dijagram prelaza samo za gornje akcije i označiti koje prelaze izazivaju akcije procesora, a koje transakcije na magistrali. Kod protokola Dragon precizno: a) definisati stanja b) opisati šta se dešava prilikom pogotka pri promašajima kod čitanja i upisa, kao i pri zameni. | Feb 2023 4) | Feb 2023 5) | Feb 2021 6) | ✅ Objasniti da li se može koristiti reduction odredba u okviru task direktive OpenMP biblioteke? Diskutovati alternative. Korigovati kod u prilogu koji vrši određenu vrstu redukcije tako da predstavlja korektno rešenje. int index, n = width * height; float mean = 0.0; #pragma omp parallel { #pragma omp single { #pragma omp task for (index = 0; index < n; index++) mean += process(inputImage[index]); std = sqrtf(var); mean /= (float)n; } #pragma omp for for (index = 0; index < n; index++) outputImage[index] = (inputImage[index] - mean)/std; } | Feb 2023 7) | Korišćenjem MPI biblioteke, napisati deo koda procesa-gospodara za paralelizaciju koda koji je dat u prilogu i vrši sinusnu transformaciju signala. Proces-gospodar treba da raspodeli posao, učesvuje u obradi i prikupi rezultate. double *sine_transform_data (double d[], int n) { double angle, pi = 3.141592653589793, *s; int i, j; s = new double[n]; for (i = 0; i < n; i++) { s[i] = 0.0; for (j = 0; j < n; j++) { angle = pi * (double) ((i + 1) * (j + 1)) / (double) (n + 1); s[i] = s[i] + sin(angle) * d[j]; } s[i] = s[i] * sqrt (2.0 / (double) (n + 1)); } return s; } | Dat je multiprocesorski sistem sa 4 identična procesora, koji koristi MOESI protokol za održavanje koherencije keš memorije. Svaka keš memorija ima po 2 ulaza, koji su veličine jedne reči. Preslikavanje je direktno. Početne vrednosti podataka su 0. Svaki upis uvećava vrednost izmenjenog podatka za 1. Na početku su sve keš memorije prazne. Data je sledeća sekvenca pristupa memoriji: Napisati stanja koherencije u svim procesorima i stanje memorije posle svake promene i skicirati opisani sistem u trenutku 8. [8 poena] Da li procesori pristupaju memoriji i kada? Za svaki pristup navesti razlog. [2 poena] ROK: chrome-extension://efaidnbmnnnibpcajpcglclefindmkaj/http://mups.etf.rs/ispiti/2020-2021/mps_avg_20202021.pdf ❌✅ | |||||||||||||||
25 | K3 2020 | ❌✅ Objasniti karakteristične načine deljenja podataka sa aspekta broja invalidacija pri upisu. Kakav je opšti zaključak sa stanovišta strukture kataloga? 2) Objasniti zaključke analize načina deljenja podataka u tipičnim paralelnim aplikacijama, kao i konsekvence ove analize na strukturu kataloga u directory protokolima. 3)Navesti tipične načine deljenja podataka sa aspekta broja invalidacija. Objasniti kako zaključci analize deljenja utiču na organizaciju i veličinu kataloga. 4) Razmotriti tipične načine deljenja u aplikacijama sa aspekta broja invalidacija. Koje su implikacije u odnosu na organizaciju kataloga? | K3 2023 1) | Avg 2023 4) | Feb 2021 6) | Zadato CUDA jezgro koje vrši obradu slike dimenzija width x height je napisano korišćenjem 1D organizacije. Napisati isto jezgro korišćenjem 2D organizacije i diskutovati prednosti i nedostatke 1D i 2D organizacije jezgra. Napisati pozive za oba načina implementacije jezgra. __global__ void kabs(char *output, char *input1, char *input2, unsigned int width, unsigned int height) { i nt index = blockIdx.x * blockDim.x + threadIdx.x; output[index] = abs(input1[index] -input2[index]) ; } | K3 2022 6) | Koristeći CUDA tehnologiju paralelizovati funkciju koja računa vrednost određenog integrala korišćenjem pravila trapeza. Obratiti pažnju na efikasnost paralelizacije i koristiti deljenu memoriju. Smatrati da je funkcija f(double) već napisana. void trap_rule(double a, double b, int n) { double h, x, result; h = (b-a)/n; result = (f(a) + f(b))/2.0; for (i = 1; i <= n-1; i++) { x = a + i*h; result += f(x); } result = result*h; return result; } | ||||||||||||||||||
26 | K2 2020 | ❌ Skicirati i objasniti generičku paralelnu arhitekturu i njene delove. Kako se ova opšta arhitektura može prilagoditi da efikasno podržava pojedine programske modele? Nacrtati i opisati generičku arhitekturu ka kojoj konvergiraju paralelni sistemi. Nacrtati i objasniti generičku paralelnu arhitekturu. Objasniti kakve specifičnosti ona treba da ima za podršku različitim programskim modelima. | K2 2022 1) | Avg 2023 3) | Feb 2022 4) | ✅ Korišćenjem MPI tehnologije napisati deo koda koji računa broj PI korišćenjem Lajbnicove formule: ( ) 4 1 2 1 0 = + − = n n n Obratiti pažnju na efikasnost paralelizacije. Smatrati da je MPI okruženje već inicijalizovano i da svi procesi treba da učestvuju u obradi. Proces sa rangom 0 dobija ulazni podatke, raspodeljuje ih ostalim procesima, a svi procesi trebaju da dobiju finalni rezultat rada. chrome-extension://efaidnbmnnnibpcajpcglclefindmkaj/http://mu ps.etf.rs/ispiti/2019-2020/si4mps_k2_20192020.pdf | ❌ Koja je prednost korišćenja grupa i komunikatora prilikom kolektivne MPI komunikacije. Pod pretpostavkom da je pokrenuto n MPI procesa, a da samo prvih n/2 procesa treba da dobije celobrojnu vrednost x od master procesa, napisati deo koda za formiranje nove grupe i komunikatora i prosleđivanje podatka odgovarajućom rutinom za kolektivnu komunikaciju. Navesti i objasniti načine za formiranje novih grupa i komunikatora korišćenjem MPI biblioteke. Da li se komunikator može napraviti nezavisno od grupe? Neka je stvoren MPI svet koji se sastoji od 10 procesa. a) [5] Čemu služe grupe, a čemu komunikatori i da li jedan proces može biti član više grupa i komunikatora? Kako se proces identifikuje u okviru grupe i komunikatora? b) [5] Napiseti deo koda koji deli zadate procese u dve grupe i formira dva nova komunikatora. U jednoj grupi treba da se nađu svi procesi sa parnim rangom, a u drugoj svi procesi sa neparnim rangom. Šta radi i na koji način se može iskoristiti split operacija prilikom rada sa MPI procesima? Napisati deo koda koji sve procese iz MPI sveta deli u tri nezavisna komunikatora u zavisnosti od ranga konkretnog procesa. Čemu služe grupe i komunikatori u MPI standardu? Da li jedan proces može biti član više grupa istovremeno? Da li se za jednu grupu može kreirati više komunikatora ili samo jedan? Čemu služi grupe, a čemu komunikatori u MPI svetu? Na primeru MPI sveta kojima ima 7 procesa, prikazati deo koda potreban za kreiranje dva nova komunikatora. Prvi komunikator treba da obuhvati procese sa rangom 0, 1, 5 i 6, a drugi komunikator treba da obuhvati procese sa rangom 0, 2, 3 i 4. | ❌ Dat je multiprocesorski sistem sa 4 identična procesora, koji koristi MSI protokol za održavanje koherencije keš memorije. Svaka keš memorija ima po 2 ulaza, koji su veličine jedne reči. Preslikavanje je direktno. Početne vrednosti podataka su 0. Svaki upis uvećava vrednost izmenjenog podatka za 1. Na početku su sve keš memorije prazne. Data je sledeća sekvenca pristupa memoriji: Napisati stanja koherencije u svim procesorima i stanje memorije posle svake promene i skicirati opisani sistem u trenutku 8. [10 poena] Koliko puta koji od procesora pristupa memoriji? Za svaki pristup navesti razlog. [3 poena] Koliki je Hit Rate za svaki od procesora (brojati i čitanje i upis, prikazati zbirno)? [2 poena] ROK: chrome-extension://efaidnbmnnnibpcajpcglclefindmkaj/http://mups.etf.rs/isp iti/2019-2020/si4mps_k2_20192020.pdf✅ | ||||||||||||||||||
27 | K1 2020 | K1 2023 1) | ❌ Koje dve klase paralelizma preovladjuju u aplikacijama? Nabrojati osnovne klase i nivoe paralelizma. Koje vrste paralelizma se prepoznaju pri izvršavanju nu računarima? Kako se ove vrste paralelizma implementiraju? Navesti glavne klase računarskih sistema i njihove karakteristike. | ❌ Objasniti šta je paralelni programski modeli. Objasniti šta su implicitni, a šta eksplicitni modeli, šta su njihove prednosti i nedostaci. Objasniti pojmove implicitnog i eksplicitnog modela i uporediti ih sa aspekta odgovornosti programera. | Jul 2022 2) | ✅ 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++; } | ✅ 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. Čemu služi i u okviru kojih OpenMP direktiva može da se koristi nowait odredba? Na primeru koda u prilogu navesti da li i gde može da se iskoristi nowait odredba i diskutovati eventualni uticaj na performanse. void func(int n, int m, float *a, float *b, float *y, float *z) { int i; #pragma omp parallel { #pragma omp for for (i=1; i<n; i++) b[i] = (a[i] + a[i-1]) / 2.0; #pragma omp for for (i=0; i<m; i++) y[i] = sqrt(z[i]); } } | K1 2023 7) | ||||||||||||||||||
28 | Jun 2020 | ✅ Izvesti Amdahl-ov zakon i interpretirati ga. Koju vrstu skalabilnosti podrazumeva? Koji faktori dodatno ograničavaju ubrzanje? Koja je njegova osnovna pretpostavka? Koji faktori praktično ograničavaju teoretsku vrednost ubrzanja?. komentarisati njegove konsekvence. Objasniti o čemu govori Amdahl-ov zakon i izvesti ga. Ako se želi postići ubrzanje 60 na sistemu sa 90 procesora, koliki deo aplikacije može biti sekvencijalan? Ako se želi postići ubrzanje 80 na sistemu od 100 procesora koliki deo aplikacije može biti sekvencijalan? | K1 2017 3) | K2 2022 2) | K2 2023 2) | K3 2021 2) | Avg 2023 6) | ✅ Neka se posmatra isečak koda u prilogu. Navesti gde u kodu postoje sinhronizacione tačke i objasniti da li se i na koji način može izvršiti optimizacija koda dostupnim odredbama #pragma omp parallel { b(); #pragma omp for for (int i = 0; i < 10; ++i) { c(i); } #pragma omp critical { d(); } } z(); | K3 2023 6) | Korišćenjem MPI tehnologije, paralelizovati kod u prilogu koji računa vrednost određenog integrala korišćenjem Simpsonovog 1/3 pravila. Obratiti pažnju na efikasnost i korektnost paralelizacije. Smatrati da je MPI okruženje već inicijalizovano, a da proces gospodar ima sve dostupne ulazne podatke i da ravnopravno vrši obradu. float simpsons(float ll, float ul, int n) { float h = (ul - ll) / n, x[10], fx[10]; for (int i = 0; i <= n; i++) { x[i] = ll + i * h; fx[i] = func(x[i]); } float res = 0; for (int i = 0; i <= n; i++) { if (i == 0 || i == n) res += fx[i]; else if (i % 2 != 0) res += 4 * fx[i]; else res += 2 * fx[i]; } res = res * (h / 3); return res; } | Dat je multiprocesorski sistem sa 4 identična procesora, koji koristi Firefly protokol za održavanje koherencije keš memorije. Svaka keš memorija ima po 2 ulaza, koji su veličine jedne reči. Preslikavanje je direktno. Početne vrednosti podataka su 0. Svaki upis uvećava vrednost izmenjenog podatka za 1. Na početku su sve keš memorije prazne. Data je sledeća sekvenca pristupa memoriji: Napisati stanja koherencije u svim procesorima i stanje memorije posle svake promene i skicirati opisani sistem u trenutku 8. [8 poena] Da li procesori pristupaju memoriji i kada? Za svaki pristup navesti razlog. [2 poena] ROK: chrome-extension://efaidnbmnnnibpcajpcglclefindmkaj/http://mups.etf.rs/ispiti/2019-2020/mps_jun_20192020.pdf✅ | |||||||||||||||
29 | Feb 2020 | Jun 2020 1) | ✅ Šta su paralelni programski modeli i kako se obično implementiraju? | K2 2023 1) | Feb 2023 4) | Feb 2023 5) | K3 2023 4) | Na koji način se korišćenjem MPI izvedenih tipova mogu modelovati strukture i šta se time omogućava? Za strukturu u prilogu, napisati deo koda kojim se formira odgovarajući izvedeni tip. typedef struct body { char name[MAX]; double f, d; int type; } Body; | ✅ Čemu služi single direktiva kod OpenMP biblioteke? Da li postoji barijera na kraju single bloka i da li se to ponašanje može promeniti i kako? Koja je razlika između single i master direktiva kod OpenMP-a? Da li se i na koji način korišćenjem single direktive može proizvesti ponašanje master direktive i obratno? Ukoliko je neki od slučajeva moguć, navesti primer. | Korišćenjem CUDA tehnologije jezgro koje paralelizuje deo koda u prilogu koji pronalazi sve brojeve d koji zadovoljavaju uslove Pitagorine četvorke ( a2 + b2 + c2 = d2), gde važi 1 ≤ a, b, c ≤ N. Obratiti pažnju na efikasnost paralelizacije. Koristiti 1D organizaciju jezgra. Napisati poziv jezgra. int a,b,c,d, s = 0, r[N+1 = {0}; for(a=1; a<=N; a++){ for(b=a; b<=N; b++){ int aabb; if(a&1 && b&1) continue; aabb=a*a + b*b; for(c=b; c<=N; c++){ int aabbcc=aabb + c*c; d=(int)sqrt((float)aabbcc); if(aabbcc == d*d && d<=N) { r[d]=1; s++; }}}} | Dat je multiprocesorski sistem sa 4 identična procesora, koji koristi MESI protokol za održavanje koherencije keš memorije. Svaka keš memorija ima po 2 ulaza, koji su veličine jedne reči. Preslikavanje je direktno. Početne vrednosti podataka su 0. Svaki upis uvećava vrednost izmenjenog podatka za 1. Na početku su sve keš memorije prazne. Data je sledeća sekvenca pristupa memoriji: Napisati stanja koherencije u svim procesorima i stanje memorije posle svake promene i skicirati opisani sistem u trenutku 8. [8 poena] Da li procesori pristupaju memoriji i kada? Za svaki pristup navesti razlog. [2 poena] ROK: chrome-extension://efaidnbmnnnibpcajpcglclefindmkaj/http://mups.etf.rs/ispiti/2019-2020/mps_februar_20192020.pdf | |||||||||||||||
30 | Avg 2020 | ❌ Objasniti tehnološke trendove u memorijskoj tehnologiji. | Jul 2023 2) | K2 2023 1) | K2 2022 3) | Avg 2023 5) | Avg 2023 4) | Jul 2022 7) | Priloženi kod predstavlja jednu naivnu implementaciju broadcast operacije korišćenjem MPI tehnologije. Objasniti koji su nedostaci priloženog rešenja i kako ih je moguće ispraviti. Zašto je bolje korišćenje MPI_Bcast operacije? void my_bcast(void* data, int count, MPI_Datatype datatype, int root, MPI_Comm comm) { int world_rank, world_size; MPI_Comm_rank(comm, &world_rank); MPI_Comm_size(comm, &world_size); if (world_rank == root) for (int i = 0; i < world_size; i++) if (i != world_rank) MPI_Send(data, count, datatype, i, 0, comm); else MPI_Recv(data, count, datatype, root, 0, comm, MPI_STATUS_IGNORE); } | Korišćenjem CUDA tehnologije, paralelizovati funkciju u prilogu koji računa broj PI. Obratiti pažnju na efikasnost i korektnost paralelizacije. double compute_pi(long n) { long i; double factor, sum = 0.0; for (i = 0; i < n; i++) { factor = (i % 2 == 0) ? 1.0 : -1.0; sum += factor/(2*i+1); } sum = 4.0*sum; return sum; } | Dat je multiprocesorski sistem sa 4 identična procesora, koji koristi MESI protokol za održavanje koherencije keš memorije. Svaka keš memorija ima po 2 ulaza, koji su veličine jedne reči. Preslikavanje je direktno. Početne vrednosti podataka su 0. Svaki upis uvećava vrednost izmenjenog podatka za 1. Na početku su sve keš memorije prazne. Data je sledeća sekvenca pristupa memoriji: Napisati stanja koherencije u svim procesorima i stanje memorije posle svake promene i skicirati opisani sistem u trenutku 8. [8 poena] Da li procesori pristupaju memoriji i kada? Za svaki pristup navesti razlog. [2 poena] ROK: chrome-extension://efaidnbmnnnibpcajpcglclefindmkaj/http://mups.etf.rs/ispiti/2019-2020/mps_avg_20192020.pdf | |||||||||||||||
31 | K3 2019 | Feb 2023 5) | K3 2023 2) | ❌ Nacrtati i objasniti strukturu dvonivoskog hijerarhijskog sistema sa distribuiranom memorijom. Ukratko objasniti održavanje koherencije. Nacrtati opštu strukturnu šemu dvonivoskog hijerarhijskog sistema sa distribuiranom memorijom zasnovanog na magistralama. Objasniti strukturu i princip rada. Precizno objasniti šta se sve dešava u dvonivoskoj keš hijerarhiji (L1+L2) sa invalidacionom strategijom kada se desi write miss u L1? Nacrtati dvonivoski hijerarhijski sistem sa distribuiranom memorijom zasnovanom na magistralama, a zatim opisati kako se odvijaju čitanja i upisi. | Sep 2021 6) | Zadato CUDA jezgro predstavlja jednu varijantu redukcije na nivou bloka. Detaljno objasniti odsustvo sinhronizacije u poslednjih nekoliko koraka i na koji način se taj mehanizam sprovodi. template <unsigned int blockSize> __global__ void reduce(int *g_idata, int *g_odata, unsigned int n) { extern __shared__ int sdata[]; unsigned int tid = threadIdx.x; unsigned int i = blockIdx.x*(blockSize*2) + tid; unsigned int gridSize = blockSize*2*gridDim.x; sdata[tid] = 0; while (i < n) { sdata[tid] += g_idata[i] + g_idata[i+blockSize]; i += gridSize; } __syncthreads(); if (blockSize >= 512) { if (tid < 256) { sdata[tid] += sdata[tid + 256]; } __syncthreads(); } if (blockSize >= 256) { if (tid < 128) { sdata[tid] += sdata[tid + 128]; } __syncthreads(); } if (blockSize >= 128) { if (tid < 64) { sdata[tid] += sdata[tid + 64]; } __syncthreads(); } if (tid < 32) { if (blockSize >= 64) sdata[tid] += sdata[tid + 32]; if (blockSize >= 32) sdata[tid] += sdata[tid + 16]; if (blockSize >= 16) sdata[tid] += sdata[tid + 8]; if (blockSize >= 8) sdata[tid] += sdata[tid + 4]; if (blockSize >= 4) sdata[tid] += sdata[tid + 2]; if (blockSize >= 2) sdata[tid] += sdata[tid + 1]; } if (tid == 0) g_odata[blockIdx.x] = sdata[0]; } | Feb 2023 7) | Koristeći CUDA tehnologiju paralelizovati funkciju koja računa procentualnu razliku dve slike istih dimenzija. Slika je definisana kao niz čija svaka tri uzastopna elementa predstavljaju RGB komponente slike. Obratiti pažnju na efikasnost paralelizacije i koristiti deljenu memoriju. Napisati deo koda za centralni procesor koji vrši pozivanje implementiranog jezgra. #define RED_C 0 #define GREEN_C 1 #define BLUE_C 2 #define GET_PIXEL(IMG, X, Y) ((IMG)->buf[ (Y) * (IMG)->width + (X) ]) ... image im1, im2, totalDiff = 0.0; unsigned int x, y; ... for(x=0; x < im1->width; x++) { for(y=0; y < im1->width; y++) { totalDiff += fabs(GET_PIXEL(im1, x, y)[RED_C] – GET_PIXEL(im2, x, y)[RED_C] ) / 255.0; totalDiff += fabs(GET_PIXEL(im1, x, y)[GREEN_C] – GET_PIXEL(im2, x, y)[GREEN_C] ) / 255.0; totalDiff += fabs(GET_PIXEL(im1, x, y)[BLUE_C] – GET_PIXEL(im2, x, y)[BLUE_C] ) / 255.0; } } | ||||||||||||||||||
32 | K2 2019 | Okt 2009 2) | K2 2023 1) | ❌ Objasniti pojmove validnost, vlasništvo i ekskluzivnost u protokolima za koherenciju. U donjim tabelama napisati stanja za protokole MESI i Dragon i deklarisati ih u pogledu ove tri osobine (staviti + ili – u odgovarajuće polje). | Avg 2022 4) | ✅ Korišćenjem MPI tehnologije paralelizovati kod u prilogu koji vrši normalizaciju slike. Obratiti pažnju na efikasnost i korektnost paralelizacije.Smatrati da je MPI okruženje već inicijalizovano i da svi procesi treba da učestvuju u obradi. Proces sa rangom 0 dobija ulazne podatke, raspodeljuje ih ostalim procesima i sakuplja rezultat rada. int index, n = width * height; float mean = 0.0, var = 0.0, svar, std; for (index = 0; index < n; index++) mean += (float)(inputImage[index]); mean /= (float)n; for(index = 0; index < n; index++) { svar = (float)(inputImage[index]) - mean; var += svar * svar; } var /= (float)n; std = sqrtf(var); for (index = 0; index < n; index++) outputImage[index] = (inputImage[index] - mean)/std; | ❌ Koja je prednost korišćenja i kakve su karakteristike kolektivne komunikacije kod MPI tehnologije? Na primeru koda u prilogu kojim se svakom procesu šalje jedinstveni deo niza na obradu, komentarisati performanse i napisati alternativu koja koristi rutine za kolektivnu komunikaciju. if (rank == MASTER) { for (i = 1; i < size; i++) MPI_Send(arr + i * chunk, chunk, MPI_INT, i, 1000, MPI_COMM_WORLD); } else { MPI_Status status; MPI_Recv(buff, chunk, MPI_INT, MASTER, 1000, MPI_COMM_WORLD, &status); } | ✅ Dat je multiprocesorski sistem sa 4 identična procesora, koji koristi MSI protokol za održavanje koherencije keš memorije. Svaka keš memorija ima po 2 ulaza, koji su veličine jedne reči. Preslikavanje je direktno. Početne vrednosti podataka su 0. Svaki upis uvećava vrednost izmenjenog podatka za 1. Na početku su sve keš memorije prazne. Data je sledeća sekvenca pristupa memoriji: Napisati stanja koherencije u svim procesorima i stanje memorije posle svake promene i skicirati opisani sistem u trenutku 8. [10 poena] Koliko puta koji od procesora pristupa memoriji? Za svaki pristup navesti razlog. [3 poena] Koliki je Hit Rate za svaki od procesora (brojati i čitanje i upis, prikazati zbirno)? [2 poena] ROK: chrome-extension://efaidnbmnnnibpcajpcglclefindmkaj/http://mups.etf.rs/ispiti/2018-2019/si4mps_k2_20182019.pdf | ||||||||||||||||||
33 | K1 2019 | K1 2022 1) | K1 2023 2) | K2 2023 1) | Avg 2023 2) | ✅ 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); } } | ✅ 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. | K1 2023 7) | ||||||||||||||||||
34 | Jun 2019 | Jul 2015 1) | Feb 2023 2) | Feb 2022 4) | Feb 2022 4) | K3 2023 2) | Feb 2021 6) | ✅ Neka se posmatraju dva isečka koda u prilogu. Izvršiti paralelizaciju koda korišćenjem OpenMP tehnologije, ukoliko je poznato da je M za red ili više veličina manje od N. Objasniti da li se i na koji način može izvršiti optimizacija oba koda dostupnim odredbama. KOD1: for ( i=0; i<M; i++ ) for ( j=0; j<N; j++ ) A[i][j] = B[i][j] + C[i][j] KOD2: for (i=0; i<M; i++) { y[i] = 0.; for (j=0; j<N; j++) y[i] += A[i][j] * x[j] } | K3 2022 6) | Korišćenjem MPI tehnologije, paralelizovati kod u prilogu koji računa broj PI. Proces gospodar treba da vrši komunikaciju sa korisnikom i ispis rezultata. Obratiti pažnju na efikasnost i korektnost paralelizacije. #include <stdio.h> double f( double a ) { return (4.0 / (1.0 + a*a)); } int main( int argc, char *argv[]) { int done = 0, n = 0, i; double mypi, pi, h, sum, x; while (!done) { scanf("%d",&n); if (n != 0) { h = 1.0 / (double) n; sum = 0.0; for (i = 1; i <= n; i += 1) { x = h * ((double)i - 0.5); sum += f(x); } mypi = h * sum; printf("pi: %f\n", mypi); } else return 0; } } | Dat je multiprocesorski sistem sa 4 identična procesora, koji koristi MSI protokol za održavanje koherencije keš memorije. Svaka keš memorija ima po 2 ulaza, koji su veličine jedne reči. Preslikavanje je direktno. Početne vrednosti podataka su 0. Svaki upis uvećava vrednost izmenjenog podatka za 1. Na početku su sve keš memorije prazne. Data je sledeća sekvenca pristupa memoriji: Napisati stanja koherencije u svim procesorima i stanje memorije posle svake promene i skicirati opisani sistem u trenutku 8. [8 poena] Da li procesori pristupaju memoriji i kada? Za svaki pristup navesti razlog. [2 poena] ROK: chrome-extension://efaidnbmnnnibpcajpcglclefindmkaj/http://mups.etf.rs/ispiti/2018-2019/mps_jun_20182019.pdf | |||||||||||||||
35 | Jul 2019 | Objasniti zašto se ne prave sve složeniji superskalarni procesori. | K1 2020 3) | Avg 2023 3) | ✅ Objasniti kako migracija procesa utiče na performanse u sistemu sa održavanjem koherencije. | K3 2023 2) | K3 2023 4) | ❌ Da li postoje razlike u implementaciji rutina za komunikaciju tačno dva procesa i kolektivnih operacija kod MPI biblioteke? Objasniti na primeru slanja jednog podatka korišćenjem MPI_Bcast poziva i slanja tog istog podatka sa nekoliko MPI_Send operacija. | Za priloženi kod koji vrši iteriranje kroz piksele zadate slike, napisati korišćenjem CUDA tehnologije kostur 2D jezgra za izvšravanje na GPU. Navesti poziv takvog jezgra. for (uint16 pixelY = 0; pixelY < rectHeight; pixelY++) { for (uint16 pixelX = 0; pixelX < rectWidth; pixelX++) { pixelOffset = (pixelX * columnBytes + pixelY * rowBytes); doEffect(pixelOffset); } } | ✅ Korišćenjem OpenMP tehnologije, paralelizovati kod u prilogu. Obratiti pažnju na efikasnost i korektnost paralelizacije. Smatrati da su sve promenljive ispravno definisane i inicijalizovana, a memorija alocirana. double epot, vir; void forces(int npart, double x[], double f[], double side, double rcoff){ int i, j; double sideh, rcoffs, xi,yi,zi,fxi,fyi,fzi,xx,yy,zz; double rd, rrd, rrd2, rrd3, rrd4, rrd6, rrd7, r148; double forcex, forcey, forcez; vir = 0.0; epot = 0.0; sideh = 0.5*side; rcoffs = rcoff*rcoff; for (i=0; i<npart*3; i+=3) { xi = x[i]; yi = x[i+1]; zi = x[i+2]; fxi = 0.0; fyi = 0.0; fzi = 0.0; for (j=i+3; j<npart*3; j+=3) { xx = xi-x[j]; yy = yi-x[j+1]; zz = zi-x[j+2]; rd = xx*xx+yy*yy+zz*zz; if (rd<=rcoffs) { rrd = 1.0/rd; rrd2 = rrd*rrd; rrd3 = rrd2*rrd; rrd4 = rrd2*rrd2; rrd6 = rrd2*rrd4; rrd7 = rrd6*rrd; epot += (rrd6-rrd3); r148 = rrd7-0.5*rrd4; vir -= rd*r148; forcex = xx*r148; fxi += forcex; f[j] -= forcex; forcey = yy*r148; fyi += forcey; f[j+1] -= forcey; forcez = zz*r148; fzi += forcez; f[j+2] -= forcez; } } f[i] += fxi; f[i+1] += fyi; f[i+2] += fzi; } } | Dat je multiprocesorski sistem sa 4 identična procesora, koji koristi Firefly protokol za održavanje koherencije keš memorije. Svaka keš memorija ima po 2 ulaza, koji su veličine jedne reči. Preslikavanje je direktno. Početne vrednosti podataka su 0. Svaki upis uvećava vrednost izmenjenog podatka za 1. Na početku su sve keš memorije prazne. Data je sledeća sekvenca pristupa memoriji: Napisati stanja koherencije u svim procesorima i stanje memorije posle svake promene i skicirati opisani sistem u trenutku 8. [8 poena] Da li procesori pristupaju memoriji i kada? Za svaki pristup navesti razlog. [2 poena] ROK: chrome-extension://efaidnbmnnnibpcajpcglclefindmkaj/http://mups.etf.rs/ispiti/2018-2019/mps_jul_20182019.pdf | |||||||||||||||
36 | Avg 2019 | K1 2020 2) | Sep 2021 2) | Avg 2021 3) | K2 2022 3) | Feb 2023 5) | Sep 2021 6) | ❌ Objasniti gde se i kako koriste polling i interrupt tehnike prilikom komunikacije u okviru MPI biblioteke. Koje su prednosti i mane jedne i druge tehnike? | Priloženi kod predstavlja CUDA jezgro koje vrši množenje dve matrice M i N. Kod je napisan sa određenim ograničenjima u smislu korektnosti i performansi. Objasniti koja su to ograničenja i kako ih je moguće ispraviti. __global__ void simpleMatMul(float* d_M, float* d_N, float* d_P, int width) { int row = blockIdx.y*width+threadIdx.y; int col = blockIdx.x*width+threadIdx.x; float product_val = 0 for(int k=0;k<width;k++) { product_val += d_M[row*width+k]*d_N[k*width+col]; } d_p[row*width+col] = product_val; } | ✅ Korišćenjem OpenMP tehnologije, paralelizovati kod u prilogu koji računa broj PI. Obratiti pažnju na efikasnost i korektnost paralelizacije. #include <stdio.h> #include <stdlib.h> #include <math.h> int main(int argc, char* argv[]) { long long n, i; int thread_count; double factor; double sum = 0.0; n = strtoll(argv[1], NULL, 10); for (i = 0; i < n; i++) { factor = (i % 2 == 0) ? 1.0 : -1.0; sum += factor/(2*i+1); } sum = 4.0*sum; printf(" Our estimate of pi = %.14f\n", sum); printf(" pi = %.14f\n", 4.0*atan(1.0)); return 0; } | Dat je multiprocesorski sistem sa 4 identična procesora, koji koristi WTI-allocate protokol za održavanje koherencije keš memorije. Svaka keš memorija ima po 2 ulaza, koji su veličine jedne reči. Preslikavanje je direktno. Početne vrednosti podataka su 0. Svaki upis uvećava vrednost izmenjenog podatka za 1. Na početku su sve keš memorije prazne. Data je sledeća sekvenca pristupa memoriji: Napisati stanja koherencije u svim procesorima i stanje memorije posle svake promene i skicirati opisani sistem u trenutku 8. [8 poena] Da li procesori pristupaju memoriji i kada? Za svaki pristup navesti razlog. [2 poena] ROK: chrome-extension://efaidnbmnnnibpcajpcglclefindmkaj/http://mups.etf.rs/ispiti/2018-2019/mps_avg_20182019.pdf | |||||||||||||||
37 | K3 2018 | Feb 2023 4) | K3 2020 1) | ❌✅ Objasniti kako je organizovan katalog u tehnici kombinovanog kataloga. Opisati osnovne akcije. | Jul 2022 6) | Iz zadatog CUDA jezgra koje određuje histogram zadatog niza su uklonjeni određeni sinhronizacioni konstrukti. Na koji način se sve može postići sinhronizacija u okviru CUDA jezgra? Obrazložiti i dodati na odgovarajuća mesta u kodu sinhronizacione konstrukte, kako bi se kod u prilogu korektno izvršavao. __global__ void histo_kernel(const char *input, int *bins, int num_elements, int num_bins) { int tid = blockIdx.x * blockDim.x + threadIdx.x; extern __shared__ unsigned int bins_s[]; for (int binIdx = threadIdx.x; binIdx < num_bins; binIdx += blockDim.x) bins_s[binIdx] = 0; for (int i = tid; i < num_elements; i += blockDim.x * gridDim.x) atomicAdd(&(bins_s[(unsigned int)input[i]]), 1); for (int binIdx = threadIdx.x; binIdx < num_bins; binIdx += blockDim.x) atomicAdd(&(bins[binIdx]), bins_s[binIdx]); } | Koje su prednosti korišćenja deljene memorije prilikom izvršavanja programa na grafičkom procesoru? Na primeru množenja matrica, navesti tipičnu strategiju rešavanja problema na grafičkom procesoru uz korišćenje deljene memorije. Na koji način je organizovana memorijska hijerarhija grafičkog procesora i kako to utiče na performanse izvršavanja koda? Kako je organizovana operativna memorija na strani grafičkog procesora i kada je omogućeno povećanje propusnog opsega prilikom pristupa memoriji? Navesti primer za jedan poželjan i jedan nepoželjan obrazac pristupa memoriji i objasniti zašto. Šta predstavlja deljena memorija i gde se ona nalazi u memorijskoj hijerarhiji grafičkog procesora? Ko njoj sme da pristupa? Napisati deklaraciju celobrojnog niza od 1024 elementa koji treba da bude smešten u deljenoj memoriji. Objasniti kako je organizovano izvršavanje funkcija jezgara na grafičkom procesoru. Kako to utiče na njihovu skalabilnost u zavisnosti od broja streaming multiprocesora unutar grafičkog procesora? | Koristeći CUDA tehnologiju paralelizovati funkciju koja je data u prilogu. Funkcija vrši konvoluciju dva zadata signala. Prilikom paralelizacije koristiti deljenu memoriju. Obratiti pažnju na efikasnost paralelizacije. Napisati deo koda za centralni procesor koji vrši pozivanje implementiranog jezgra. void convolve(double *Signal, size_t SignalLen, double *Kernel, size_t KernelLen, double *Result) { size_t i, kmin, kmax, k; for (i = 0; i < SignalLen + KernelLen - 1; i++) { Result[i] = 0; kmin = (i >= KernelLen - 1) ? i - (KernelLen - 1) : 0; kmax = (i < SignalLen - 1) ? i : SignalLen - 1; for (k = kmin; k <= kmax; k++) Result[i] += Signal[k] * Kernel[i - k]; } } | ||||||||||||||||||
38 | K2 2018 | K2 2022 1) | ✅ Procesi A i B se izvršavaju na dva procesora sa privatnim keš memorijama i sinhronizuju se preko deljene promenljive S čija je početna vrednost 0 na sledeći način: - A čeka da S bude 0, onda nešto radi i postavi ga na 1 - B čeka da S bude 1, onda nešto radi i postavi ga na 0. Ispisati niz transakcija na magistrali koje se javljaju ukoliko se koristi strategija a) invalidacije i b) ažuriranja. Na osnovu toga, komentarisati koja strategija je pogodnija u ovakvim slučajevima. | Avg 2023 3) | K2 2022 3) | Korišćenjem MPI tehnologije paralelizovati funkciju u prilogu za računanje vrednosti određenog integrala korišćenjem kvadratnog pravila. Obratiti pažnju na efikasnost paralelizacije. Smatrati da je MPI okruženje već inicijalizovano i da svi procesi treba da učestvuju u obradi. Proces sa rangom 0 dobija ulazne podatke, raspodeljuje ih ostalim procesima, a svi procesi trebaju da dobiju finalni rezultat rada. double quadraticRule(double a, double b, int n, int i; double total = 0.0, x, pi = 3.141592653589793; for ( i = 0; i < n; i++ ) { x = ((double)(n – i - 1) * a + (double)(i) * b) / (double)(n - 1); total = total + 50.0 / (pi * ( 2500.0 * x * x + 1.0)); } total = (b - a) * total / (double) n; return total; } | Koja je prednost korišćenja asinhronih, neblokirajućih rutina prilikom MPI komunikacije između tačno dva procesa (point-to-point komunikacije)? Na primeru koda u prilogu, komentarisati korektnost i performanse i napisati alternativu koja koristi asinhrone, neblokirajuće rutine. if(rank==0) { MPI_Send(&x, 1, MPI_INT, 1, 100, MPI_COMM_WORLD); MPI_Recv(&y, 1, MPI_INT, 1, 100, MPI_COMM_WORLD, MPI_STATUS_IGNORE); } if(rank==1) { MPI_Send((&y, 1, MPI_INT, 0, 100, MPI_COMM_WORLD); MPI_Recv((&x, 1, MPI_INT, 0, 100, MPI_COMM_WORLD, MPI_STATUS_IGNORE); } | Dat je multiprocesorski sistem sa 4 identična procesora, koji koristi Dragon protokol za održavanje koherencije keš memorije. Svaka keš memorija ima po 2 ulaza, koji su veličine jedne reči. Preslikavanje je direktno. Početne vrednosti podataka su 0. Svaki upis uvećava vrednost izmenjenog podatka za 1. Na početku su sve keš memorije prazne. Data je sledeća sekvenca pristupa memoriji: Napisati stanja koherencije u svim procesorima i stanje memorije posle svake promene i skicirati opisani sistem u trenutku 8. [10 poena] Koliko puta koji od procesora pristupa memoriji? Za svaki pristup navesti razlog. [3 poena] Koliki je Hit Rate za svaki od procesora (brojati i čitanje i upis, prikazati zbirno)? [2 poena] ROK: chrome-extension://efaidnbmnnnibpcajpcglclefindmkaj/http://mups.etf.rs/ispiti/2017-2018/si4mps_k2_20172018.pdf ❗✅ | ||||||||||||||||||
39 | K1 2018 | K1 2021 1) | K1 2021 2) | ✅ Definisati pojam paralelnog programskog modela. Diskutovati kako se on realizuje i podržava. Navesti glavne programske modele i ukratko ih karakterisati. Objasniti šta je paralelni programski model i nabrojati osnovne paralelne programske modele? Na koje projektne odluke i kako utiče izbor paralelnog programskog modela? Definisati pojam paralelnog programaskog modela. Navesti osnovne paralelne programske modele. Definisati paralelni programski model. Objasniti šta uključuje i kako se implementira. Definisati pojam paralelnog programskog modela. Kako se oni po tipu paralelizacije mogu grubo podeliti? | Feb 2023 2) | ✅Korišćenjem OpenMP tehnologije, paralelizovati kod u prilogu koji vrši normalizaciju slike. Obratiti pažnju na efikasnost i korektnost paralelizacije. Smatrati da su sve promenljive ispravno deklarisane. int index, n = width * height; float mean = 0.0, var = 0.0, svar, std; // Calculate the mean of the image intensities for (index = 0; index < n; index++) { mean += (float)(inputImage[index]); } mean /= (float)n; // Calculate the standard deviation of the image intensities for(index = 0; index < n; index++) { svar = (float)(inputImage[index]) - mean; var += svar * svar; } var /= (float)n; std = sqrtf(var); // Rescale using the calculated mean and standard deviation for (index = 0; index < n; index++) { outputImage[index] = (inputImage[index] - mean)/std; } | ❌ (2-1:29:00) Deo koda u prilogu vrši određivanje stepena svakog čvora grafa koji je predstavljen listom grana. Diskutovati uticaj critical OpenMP direktive na performanse priloženog koda i navesti eventualne alternative. #pragma omp parallel for for (j=0; j<nedges; j++){ #pragma omp critical { degree[edge[j].vertex1]++; degree[edge[j].vertex2]++; } } | K1 2023 7) | ||||||||||||||||||
40 | Sept 2018 | Feb 2021 1) | Avg 2023 2) | K2 2023 1) | Avg 2022 4) | Avg 2023 5) | Avg 2023 4) | Jul 2023 7) | Šta predstavlja warp na grafičkim procesorima koji podržavaju CUDA tehnologiju? Na koji način izvršavanje niti u okviru utiče na performanse izvršavanja koda? Šta predstavljaju warp-ovi i kako se i gde oni izvršavaju na grafičkom procesoru? | ✅ Korišćenjem OpenMP biblioteke paralelizovati kod u prilogu koji rešava „Knapsack 0-1“ problem. Obratiti pažnju na efikasnost i korektnost paralelizacije. int knapsack01(int *mArr, int *v, int *w, int n, int W) { int i, j, m; for (j = 0; j <= W; j++) { mArr[j] = 0; } for (i = 0; i < n; i++) { for (j = W; j >= w[i]; j--) { if ((mArr[j - w[i]] + v[i]) > mArr[j]) { mArr[j] = mArr[j - w[i]] + v[i]; } } } m = mArr[0]; for (j = 0; j <= W; j++) { if (m < mArr[j]) { m = mArr[j]; } } return m; } | Dat je multiprocesorski sistem sa 4 identična procesora, koji koristi MESI protokol za održavanje koherencije keš memorije. Svaka keš memorija ima po 2 ulaza, koji su veličine jedne reči. Preslikavanje je direktno. Početne vrednosti podataka su 0. Svaki upis uvećava vrednost izmenjenog podatka za 1. Na početku su sve keš memorije prazne. Data je sledeća sekvenca pristupa memoriji: Napisati stanja koherencije u svim procesorima i stanje memorije posle svake promene i skicirati opisani sistem u trenutku 8. [8 poena] Da li procesori pristupaju memoriji i kada? Za svaki pristup navesti razlog. [2 poena] ROK: chrome-extension://efaidnbmnnnibpcajpcglclefindmkaj/http://mups.etf.rs/ispiti/2017-2018/mps_sept_20172018.pdf | |||||||||||||||
41 | Jun 2018 | Avg 2023 1) | K1 2018 3) | Avg 2021 3) | ❌✅ Objasniti princip organizacije kataloga sa ograničenim brojem pokazivača. Objasniti motivaciju za ovakvu organizaciju. Diskutovati prostorne i vremenske karakteristike. Objasniti organizaciju kataloga sa ograničenim brojem pointera i motivaciju za nju. Diskutovati prednosti i nedostatke. | K2 2022 3) | K3 2023 4) | K2 2020 6) | Jezgro u prilogu se neće korektno izvršavati na GPU. Navesti i objasniti razlog i dopisati deo koda potreban da se jezgro ispravno izvršava. __global__ void kernel(double* d_in) { unsigned int prevIndex = blockIdx.x * blockDim.x + threadIdx.x double *d_prev_ptr, *d_current_ptr, *d_next_ptr; d_prev_ptr = (double*) (d_in + prevIndex); d_current_ptr = (double*) (d_prev_ptr + 1); d_next_ptr = (double*) (d_current_ptr + 1); double prev_val = *d_prev_ptr; double curr_val = *d_current_ptr; double next_val = *d_next_ptr; if(curr_val == 0.0) *d_current_ptr = ( prev_val == 0.0 ) ? next_val : prev_val; } | ✅ Korišćenjem OpenMP tehnologije, paralelizovati kod u prilogu. Obratiti pažnju na efikasnost i korektnost paralelizacije. Smatrati da su sve promenljive ispravno definisane, a memorija alocirana. #include <stdio.h> #include <stdlib.h> #include <omp.h> void calc(float *x, float *y, float *work1, float *work2 int n) { int *index, i; index=(int*)malloc(n*sizeof(float)); for( i=0;i < n;i++) { x[i]= randPoint(); y[i]= randPoint(); index[i]= calcIndex(x[i], y[i]); work1[i]=i; work2[i]=i*i; } for( i=0;i< n;i++) { x[index[i]] += work1[i]; y[i] += work2[i]; } for( i=0;i < n;i++) printf("%d %g %g\n",i,x[i],y[i]); } | Dat je multiprocesorski sistem sa 4 identična procesora, koji koristi MESI protokol za održavanje koherencije keš memorije. Svaka keš memorija ima po 2 ulaza, koji su veličine jedne reči. Preslikavanje je direktno. Početne vrednosti podataka su 0. Svaki upis uvećava vrednost izmenjenog podatka za 1. Na početku su sve keš memorije prazne. Data je sledeća sekvenca pristupa memoriji: Napisati stanja koherencije u svim procesorima i stanje memorije posle svake promene i skicirati opisani sistem u trenutku 8. [8 poena] Da li procesori pristupaju memoriji i kada? Za svaki pristup navesti razlog. [2 poena] ROK: chrome-extension://efaidnbmnnnibpcajpcglclefindmkaj/http://mups.etf.rs/ispiti/2017-2018/mps_jun_20172018.pdf ❗ ✅ | |||||||||||||||
42 | Jul 2018 | ✅ Definisati pojmove slabo (weak) i jako (strong) skaliranje. Koji zakon podrazumeva prvi, a koji drugi tip? Definisati pojam skalabilnosti. Objasniti dva tipična načina skaliranja i uslove kojima odgovaraju. Objasniti šta je labavo skaliranje? Koji zakon pretpostavlja ovakav vid skaliranja? Objasniti i izvesti izraz za ubrzanje po ovom zakonu i komentarisati ga. Objasniti šta je čvrsto skaliranje? Koji zakon pretpostavlja ovakav vid skaliranja? Objasniti i izvesti izraz za ubrzanje po ovom zakonu i komentarisati ga. | K2 2023 1) | Avg 2022 2) | Feb 2022 4) | Feb 2023 5) | K3 2023 3) | ✅ Diskutovati kontekst, prednosti i nedostatke korišćenja critical i atomic direktiva iz OpenMP biblioteke. Na primeru koda u prilogu navesti koje rešenje je bolje koristiti. #pragma omp parallel shared(next_job, n) { int my_job, res; while (1) { my_job = next_job; next_job += incr; res = process(my_job); if (res > n) break; } } | Objasniti na koji način se mogu ukloniti kašnjenja usled korišćenja sinhronih komunikacionih primitiva kod MPI biblioteke? Na koji način se obezbeđuje korektnost programa ukoliko se ove direktive ne koriste? | Korišćenjem CUDA tehnologije napisati jezgro koje vrši uprosečavanje zadate matrice dimenzija mxn kompleksnih brojeva faktorom divisor. Matrica kompleksnih brojeva je linearizovana po vrstama, a za svaki kompleksni broj su redom smeštani realni i imaginarni deo. Obratiti pažnju na efikasnost i korektnost paralelizacije. __global__ void avgMatrixEl(double *a, int m, int n, int divisor); | ] Dat je multiprocesorski sistem sa 4 identična procesora, koji koristi Firefly protokol za održavanje koherencije keš memorije. Svaka keš memorija ima po 2 ulaza, koji su veličine jedne reči. Preslikavanje je direktno. Početne vrednosti podataka su 0. Svaki upis uvećava vrednost izmenjenog podatka za 1. Na početku su sve keš memorije prazne. Data je sledeća sekvenca pristupa memoriji: Napisati stanja koherencije u svim procesorima i stanje memorije posle svake promene i skicirati opisani sistem u trenutku 8. [8 poena] Da li procesori pristupaju memoriji i kada? Za svaki pristup navesti razlog. [2 poena] ROK: chrome-extension://efaidnbmnnnibpcajpcglclefindmkaj/http://mups.etf.rs/ispiti/2017-2018/mps_jul_20172018.pdf | |||||||||||||||
43 | Feb 2018 | Jun 2022 1) | Avg 2023 2) | Avg 2023 3) | K3 2023 2) | Avg 2023 4) | Feb 2021 6) | ❗ Navesti i objasniti načine za postavljanje i promenu broja niti unutar programa napisanog korišćenjem OpenMP biblioteke. | Kod u prilogu može prouzrokovati određene probleme sa performansama prilikom izvršavanja na GPU. Navesti i objasniti koji su to problemi i napisati alternativnu verziju funkcije koja te probleme rešava. __device__ int calc_D (int A, int B, int C) { int D = 0; if (A < 10) D = A*6; else if (A < 17) D = A*6 + B*2; else if (A < 26) D = A*6 + B*2 + C; else D = A*6 + B*2 + C*3; return D; } | Korišćenjem MPI biblioteke, napisati deo koda procesa-gospodara za paralelizaciju koda koji je dat u prilogu. Proces-gospodar treba da raspodeli posao, učesvuje u obradi i prikupi rezultate. Kod određuje minimalnu hash vrednost zadatog stringa koja je formirana od k uzastopnih karaktera. Smatrati da su sve promenljive već definisane i incijalizovane, kao i sam MPI svet. Obratiti pažnju na efikasnost paralelizacije. unsigned minhash(char *str, int n, int k) { ... for (i=0; i < n-k; i++) khashes[i] = khash(str + i, k); minh = khashes[0]; for (i=1; i < n-k; i++) if (khashes[i] < minh) minh = khashes[i]; return minh; } | Dat je multiprocesorski sistem sa 4 identična procesora, koji koristi Firefly protokol za održavanje koherencije keš memorije. Svaka keš memorija ima po 2 ulaza, koji su veličine jedne reči. Preslikavanje je direktno. Početne vrednosti podataka su 0. Svaki upis uvećava vrednost izmenjenog podatka za 1. Na početku su sve keš memorije prazne. Data je sledeća sekvenca pristupa memoriji: Napisati stanja koherencije u svim procesorima i stanje memorije posle svake promene i skicirati opisani sistem u trenutku 8. [8 poena] Da li procesori pristupaju memoriji i kada? Za svaki pristup navesti razlog. [2 poena] ROK: chrome-extension://efaidnbmnnnibpcajpcglclefindmkaj/http://mups.etf.rs/ispiti/2017-2018/mps_februar_20172018.pdf | |||||||||||||||
44 | K3 2017 | ❌✅ Objasniti šta se dešava pri zameni u keš memoriji u sistemu sa directory protokolom. Diskutovati projektne alternative pri zameni kopije u kešu koja je ažurna sa memorijom u zavisnosti od vrste directory protokola (full-map, Diri B, Diri NB) i karakteristika pristupa. | K3 2023 2) | Avg 2023 4) | ❌ Kojoj grupi interkonekcionih mreža pripada 3D torus? Objasniti način povezivanja i nacrtati ovu mrežu. Koje su vrednosti karakterističnih parametara mreže? | U priloženom kodu su prikazana dva načina za predstavljanje slike u RGB formatu. Prvi kod koristi pristup niza struktura (array of structures), dok drugi kod koristi pristup strukture nizova (structure of arrays). Diskutovati prednosti i nedostatke jednog i drugog pristupa i navesti koji pristup daje bolje performanse na CUDA platformi i u kojim slučajevima? struct { uint8_t r, g, b; } AoS[N]; struct { uint8_t r[N]; uint8_t g[N]; uint8_t b[N]; } SoA; | K3 2022 6) | Koristeći CUDA tehnologiju paralelizovati kod koji je dat u prilogu. Kod vrši određene proračune u simulaciji prostiranja talasa na žici. Napisati odgovarajući kod za grafički procesor, kao i deo koda za centralni procesor koji vrši njegovo pozivanje. Smatrati da su svi memorijski transferi već obavljeni. Obratiti pažnju na efikasnost paralelizacije. for (i = 0; i < nsteps; i++) { for (j = 0; j < tpoints; j++) { if ((j == 0) || (j == tpoints-1)) newval[j] = 0.0; else newval[j] = (2.0 * values[j]) - oldval[j] + (sqtau * (values[j-1] - (2.0 * values[j]) + values[j+1])); } for (j = 0; j < tpoints; j++) { oldval[j] = values[j]; values[j] = newval[j]; } } | ||||||||||||||||||
45 | K2 2017 | Avg 2022 2) | K2 2023 1) | Kako granularnost (dimenzija) bloka niti može uticati na performanse izvršavanja programskog koda na grafičkom procesoru? Pretpostaviti da je granularnost objekta koherencije – jedna reč: a) Diskutovati prednosti i nedostatke ove odluke, b) U ovom slučaju diskutivati prednosti i nedostatke primene ažurirajućeg ili invalidacionog protokola. | U jednom paralelnom programu tri procesa pristupaju nizu a definisanim kao struct S {int x; long int y; long double z;}; S a[N]; Proces P1 upisuje samo polje x veličine jedne reči, proces P2 samo polje y veličine dve reči, a proces P3 samo polje z veličine dve reči. Veličina bloka je 4 reči. Predložiti i obrazložiti reorganizaciju ove strukture podataka tako da performanse deljenja ovog niza u paralelnom sistemu koji koristi invalidacioni protokol budu što bolje i ispisati je. | Korišćenjem MPI tehnologije paralelizovati funkciju koja je data u prilogu. Funkcija vrši naivnu pretragu stringa pat u stringu txt. Obratiti pažnju na efikasnost paralelizacije. Smatrati da je MPI okruženje već inicijalizovano i da svi procesi treba da učestvuju u obradi. Proces sa rangom 0 dobija ulazne podatke, raspodeljuje ih ostalim procesima i sakuplja rezultate pretrage. int search(char *pat, char *txt){ int M = strlen(pat); int N = strlen(txt); for (int i = 0; i <= N - M; i++) { int j; for (j = 0; j < M; j++) if (txt[i+j] != pat[j]) break; if (j == M) return i; } } | ✅ Koja dva sinhronizaciona mehanizma se tipično koriste prilikom implementacije komunikacionih rutina MPI biblioteke? Ukratko ih objasniti i navesti osnovne prednosti i nedostatke jednog i drugog pristupa. | Dat je multiprocesorski sistem sa 4 identična procesora, koji koristi MESI protokol za održavanje koherencije keš memorije. Svaka keš memorija ima po 2 ulaza, koji su veličine jedne reči. Preslikavanje je direktno. Početne vrednosti podataka su 0. Svaki upis uvećava vrednost izmenjenog podatka za 1. Na početku su sve keš memorije prazne. Data je sledeća sekvenca pristupa memoriji: Napisati stanja koherencije u svim procesorima i stanje memorije posle svake promene i skicirati opisani sistem u trenutku 8. [10 poena] Koliko puta koji od procesora pristupa memoriji? Za svaki pristup navesti razlog. [3 poena] Koliki je Hit Rate za svaki od procesora (brojati i čitanje i upis, prikazati zbirno)? [2 poena] ROK: chrome-extension://efaidnbmnnnibpcajpcglclefindmkaj/http://mups.etf.rs/ispiti/2016-2017/si4mps_k2_20162017.pdf | ||||||||||||||||||
46 | K1 2017 | Objasniti glavne projektne odluke i bitne karakteristike koje se moraju razmotriti kod primene paralelnog procesiranja. | K1 2023 1) | ✅ Objasniti koji se nivoi paralelizma i elementi Flynn-ove klasifikacije mogu pronaći u savremenim višejezgarnim procesorima. Dati Flynn-ovu klasifikaciju računara i objasniti pojedine klase, objasniti osnovne tipove sistema. Nacrtati opštu strukturu savremenog multicore procesora. Objasniti koji elementi Flynn-ove klasifikacije se u njemu mogu prepoznati? | K1 2023 4) | ✅ Korišćenjem OpenMP tehnologije, paralelizovati funkciju kod u prilogu. Paralelizaciju izvršisti korišćenjem task-ova. Obratiti pažnju na efikasnost i korektnost paralelizacije. Smatrati da su sve promenljive ispravno deklarisane. diff = 0.0; for ( i = 1; i < M - 1; i++ ) { for ( j = 1; j < N - 1; j++ ) { w[i][j] = ( u[i-1][j] + u[i+1][j] + u[i][j-1] + u[i][j+1] ) / 4.0; if ( diff < fabs ( w[i][j] - u[i][j] ) ) { diff = fabs ( w[i][j] - u[i][j] ); } } } | K1 2020 6) | K1 2023 7) | ||||||||||||||||||
47 | Sep 2017 | Feb 2016 1) | Feb 2023 2) | Avg 2021 3) | Feb 2023 4) | K3 2023 2) | Feb 2021 6) | Objasniti kakva je razlika između vektorskog i indeksiranog MPI izvedenog tipa. Na primeru matrice dimenzija 200x50, napisati deo koda za kreiranje a) vektorskog tipa kojim se šalju dva uzastopne kolone ove matrice i b) indeksiranog tipa kojim se šalju svi parni elementi zadate kolone. Da li se slučaj pod b) može implementirati i vektorskim tipom? | Kada i kako se može koristiti sinhronizacija na barijeri kod CUDA programskog modela? Na koji način se može postići globalna sinhronizacija niti? | ❗ Korišćenjem OpenMP tehnologije, paralelizovati funkciju u prilogu koji vrši sortiranje niza celih brojeva quicksort algoritmom. Paralelizaciju izvršiti korišćenjem taskova. Obratiti pažnju na efikasnost i korektnost paralelizacije. Po potrebi napisati i dodatan kod. void quickSort(int* arr, int left, int right) { int i = left, j = right; int tmp; int pivot = arr[(left + right) / 2]; while (i <= j) { while (arr[i] < pivot) i++; while (arr[j] > pivot) j--; if (i <= j) { tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; i++; j--; } } if (left < j){ quickSort(arr, left, j); } if (i< right){ quickSort(arr, i, right); } } | Dat je multiprocesorski sistem sa 4 identična procesora, koji koristi MSI protokol za održavanje koherencije keš memorije. Svaka keš memorija ima po 2 ulaza, koji su veličine jedne reči. Preslikavanje je direktno Početne vrednosti podataka su 0. Svaki upis uvećava vrednost izmenjenog podatka za 1. Na početku su sve keš memorije prazne. Data je sledeća sekvenca pristupa memoriji: Napisati stanja koherencije u svim procesorima i stanje memorije posle svake promene i skicirati opisani sistem u trenutku 8. [8 poena] Da li procesori pristupaju memoriji i kada? Za svaki pristup navesti razlog. [2 poena] ROK: chrome-extension://efaidnbmnnnibpcajpcglclefindmkaj/http://mups.etf.rs/ispiti/2016-2017/mps_sep_20162017.pdf | |||||||||||||||
48 | Okt 2017 | ✅ Objasniti osnovne vrste paralelizma koji se mogu naći u aplikacijama. | K1 2023 4) | K2 2023 1) | ✅ Koji su osnovni ciljevi pri hardverskoj implementaciji protokola za koherenciju? Navesti neke elemente koji usložnjavaju implementaciju. Koje su prednosti hardverskih rešenja za održavanje koherencije keš memorija? Kako se dele? Objasniti kada može da se pojavi problem koherencije keš memorija. Koje su prednosti hardverskog načina rešavanja ovog problema. Koje su prednosti, a koji su nedostaci hardverskih protokola za koherenciju u odnosu na softverske realizacije? Koje su osnovne prednosti hardverske realizacije protokola za koherenciju keš memorija? | Objasniti koji problemi se javljaju u realizaciji hijerarhija keš memorija u multiprocesorskim sistemina i kako se rešavaju. | Feb 2021 6) | Na primeru koda sa slike, označiti deo koda nad kojim je potrebno izvršiti sinhronizaciju, predložiti odgovarajuće direktive i diskutovati razlike u upotrebi critical i atomic direktiva i njihov uticaj na performanse priloženog koda. #pragma omp parallel for private(k, f_part_k, len, len_3, mg, fact) for (k = part+1; k < n; k++) { /* Compute force on part due to k */ len_3 = len*len*len; f_part_k[X] = (curr[part].s[X] - curr[k].s[X]) * mg / len_3 * fact; f_part_k[Y] = (curr[part].s[Y] - curr[k].s[Y]) * mg / len_3 * fact; len = sqrt(f_part_k[X]*f_part_k[X] + f_part_k[Y]*f_part_k[Y]); /* Add force in to total forces */ forces[part][X] += f_part_k[X]; forces[part][Y] += f_part_k[Y]; forces[k][X] -= f_part_k[X]; forces[k][Y] -= f_part_k[Y]; } | Objasniti na koji način je organizovano izvršavanje niti u okviru jezgra kod CUDA programskog modela i kakva fleksibilnost se na taj način postiže. | Korišćenjem MPI tehnologije, napisati program koji vrši obradu nad nizom celih brojeva. Proces-gospodar dobija niz celih brojeva, vrši cikličnu raspodelu elemenata po procesima i učestvuje u obradi. Obrada se sastoji u određivanju maksimuma dobijenih elemenata po procesima. Svaki proces treba da rezultat svoje obrade dostavi procesugospodaru. Smatrati da je broj elemenata niza umnožak broja procesa. Smatrati da je MPI okruženje već inicijalizovano. void processArr (int* arr, int n, int* results); | Dat je multiprocesorski sistem sa 4 identična procesora, koji koristi Dragon protokol za održavanje koherencije keš memorije. Svaka keš memorija ima po 2 ulaza, koji su veličine jedne reči. Preslikavanje je direktno Početne vrednosti podataka su 0. Svaki upis uvećava vrednost izmenjenog podatka za 1. Na početku su sve keš memorije prazne. Data je sledeća sekvenca pristupa memoriji: Napisati stanja koherencije u svim procesorima i stanje memorije posle svake promene i skicirati opisani sistem u trenutku 8. [8 poena] Da li procesori pristupaju memoriji i kada? Za svaki pristup navesti razlog. [2 poena] ROK: chrome-extension://efaidnbmnnnibpcajpcglclefindmkaj/http://mups.etf.rs/ispiti/2016-2017/mps_okt_20162017.pdf ❗ | |||||||||||||||
49 | Jun 2017 | K1 2023 1) | K1 2017 3) | Objasniti kako se i u kojim situacijama vrši dinamička detekcija deljivosti kod MESI protokola. U kojem stanju može biti blok čija se ažurna kopija nalazi u samo jednom kešu? Objasniti. Objasniti kako se i u kojim situacijama vrši dinamička detekcija deljivosti kod MESI protokola. U kojem stanju može biti blok čija se ažurna kopija nalazi u samo jednom kešu? Objasniti. 15] Za protokol MESI: a) Objasniti kako se vrši dinamička detekcija deljivosti i zašto je ona uvedena. b) Da li kopija u stanju S uvek mora da bude deljena? Ako ne mora, objasniti kako dolazi do toga i kako bi se moglo izbeći. c) Ako trenutno u sistemu nema kopija nekog bloka u stanju M, a ima kopija u stanju S, pa se javi zahtev od nekog procesora za tim blokom, objasniti kako bi se mogao efikasno zadovoljiti. | K2 2022 3) | K3 2021 2) | K3 2023 3) | CUDA jezgro u prilogu vrši operaciju redukcije nad elementima zadatog niza. Objasniti na koje se sve načine može izvršiti dodatna optimizacija priloženog koda, tako da se ubrza njegovo izvršavanje. __global__ void reduce(int *g_idata, int *g_odata) { extern __shared__ int sdata[]; unsigned int tid = threadIdx.x; unsigned int i = blockIdx.x * blockDim.x + threadIdx.x; sdata[tid] = g_idata[i]; __syncthreads(); for (unsigned int s = blockDim.x/2; s > 0; s >>= 1) { if (tid < s) sdata[tid] = sdata[tid] + sdata[tid + s]; __syncthreads(); } if (tid == 0) g_odata[blockIdx.x] = sdata[0]; } | K1 2022 6) | Korišćenjem rutina iz MPI biblioteke, napisati deo koda koji vrši razmenu graničnih elemenata matrice unew. Smatrati da je matrica već ravnomerno raspodeljena procesima i da je MPI svet već inicijalizovan. Obratiti pažnju na efikasnost komunikacije int nx, ny, iterations; double dx, dy, f[NX][NY], u[NX][NY], unew[NX][NY]; ... int i, it, j; for ( it = 0; it < iterations; it++ ) { for ( j = 1; j < ny - 1; j++ ) { for ( i = 0; i < nx; i++ ) { unew[i][j] = 0.25 * (u[i-1][j] + u[i][j+1] + u[i][j-1] + u[i+1][j] + f[i][j] * dx * dy ); } } /* exchange border elements */ memcpy(u, unew, ny * nx * sizeof(double)); } | Dat je multiprocesorski sistem sa 4 identična procesora, koji koristi MOESI protokol za održavanje koherencije keš memorije. Svaka keš memorija ima po 2 ulaza, koji su veličine jedne reči. Preslikavanje je direktno. Početne vrednosti podataka su 0. Svaki upis uvećava vrednost izmenjenog podatka za 1. Na početku su sve keš memorije prazne. Data je sledeća sekvenca pristupa memoriji: Napisati stanja koherencije u svim procesorima i stanje memorije posle svake promene i skicirati opisani sistem u trenutku 8. [8 poena] Da li procesori pristupaju memoriji i kada? Za svaki pristup navesti razlog. [2 poena] ROK: chrome-extension://efaidnbmnnnibpcajpcglclefindmkaj/http://mups.etf.rs/ispiti/2016-2017/mps_jun_20162017.pdf | |||||||||||||||
50 | Jul2 2017 | Avg 2020 1) | Okt 2009 2) | K2 2023 3) | ✅ Komparativno diskutovati prednosti strategija poništavanja i ažuriranja. Koji je osnovni kriterijum u izboru odgovarajuće strategije? Uporedno prikazati prednosti i nedostatke strategija poništavanja i ažuriranja u protokolima. Koji je osnovni kriterijum za izbor u pogledu osobina aplikacije? | Feb 2023 5) | Avg 2023 4) | ✅ Objasniti kakve su i šta rade MPI rutine MPI_Reduce and MPI_Allreduce i navesti razliku između njih. Napisati deo koda koji korišćenjem MPI_Reduce i dodatnog koda simulira ponašanje MPI_Allreduce rutine. | ✅ Kada i kako se može koristiti sinhronizacija na barijeri kod OpenMP programskog modela? Na kojim mestima se nalazi implicitna barijera? | Korišćenjem CUDA tehnologije paralelizovati funkciju u prilogu koja predstavlja jedan korak simulacije poznate igre Game of Life. Koristiti 2D organizaciju jezgra. Obratiti pažnju na efikasnost paralelizacije. void evolve(void *u, int w, int h) { unsigned (*univ)[w] = u, new[h][w]; for (int x = 0; x < w; x++) for (int y = 0; y < h; y++) { int n = 0; for (int y1 = y - 1; y1 <= y + 1; y1++) for (int x1 = x - 1; x1 <= x + 1; x1++) if (univ[(y1 + h) % h][(x1 + w) % w]) n++; if (univ[y][x]) n--; new[y][x] = (n == 3 || (n == 2 && univ[y][x])); } for (int x = 0; x < w; x++) for (int y = 0; y < h; y++) univ[y][x] = new[y][x]; } | Dat je multiprocesorski sistem sa 4 identična procesora, koji koristi WTI write-no-allocate protokol za održavanje koherencije keš memorije. Svaka keš memorija ima po 2 ulaza, koji su veličine jedne reči. Preslikavanje je asocijativno Početne vrednosti podataka su 0. Svaki upis uvećava vrednost izmenjenog podatka za 1. Na početku su sve keš memorije prazne. Data je sledeća sekvenca pristupa memoriji: Napisati stanja koherencije u svim procesorima i stanje memorije posle svake promene i skicirati opisani sistem u trenutku 8. [8 poena] Da li procesori pristupaju memoriji i kada? Za svaki pristup navesti razlog. [2 poena] ROK: chrome-extension://efaidnbmnnnibpcajpcglclefindmkaj/http://mups.etf.rs/ispiti/2016-2017/mps_jul2_20162017.pdf | |||||||||||||||
51 | Jul1 2017 | ✅ Navesti četiri razloga za primenu paralelnog procesiranja. | K1 2018 3) | Avg 2023 3) | K2 2022 3) | Jul 2023 5) | Jul 2022 6) | ✅ Kod u prilogu koji određuje ukupan broj prostih brojeva od 2 do N je paralelizovan korišćenjem OpenMP biblioteke. Diskutovati uticaj dodavanja različitih varijanti schedule odredbe na performanse izvršavanja ovog koda. #pragma omp parallel for shared(n) private(i,j,prime) reduction(+:total) for ( i = 2; i <= n; i++ ) { prime = 1; for ( j = 2; j < i; j++ ) { if ( i % j == 0 ) { prime = 0; break; } } total = total + prime; } | Grafički procesori poseduju konstantnu memoriju i memoriju za teksture koje se mogu iskoristiti za poboljšanje performansi CUDA programa. Navesti osnovne osobine ovih memorija (ko, kako i kada može da im pristupa) i objasniti način na koji može doći do poboljšanja performansi. | Korišćenjem MPI biblioteke napisati deo koda procesa-radnika koji simulira poznatu igru Game of Life. Simulacija je modelovana matricom ćelija dimenzija NxN, gde je N deljivo brojem procesa. Ćelije sadrže žive ili mrtve ćelije, a na raspolaganju je funkcija evolve(x, y) koja određuje naredno stanje za svaku ćeliju. Proces master učitava sve neophodne podatke, šalje podatke procesima, signalizira kraj na zahtev korisnika i ne učestvuje u obradi. Smatrati da je MPI svet već inicijalizovan. Za proces-radnika napisati deo koda koji se odnosi na incijalni prijem podataka, simulaciju i slanje konačnog stanja master-procesu. Obratiti pažnju na efikasnost paralelizacije. void game_of_life(int **mat, int n); | Dat je multiprocesorski sistem sa 4 identična procesora, koji koristi Dragon protokol za održavanje koherencije keš memorije. Svaka keš memorija ima po 2 ulaza, koji su veličine jedne reči. Preslikavanje je direktno Početne vrednosti podataka su 0. Svaki upis uvećava vrednost izmenjenog podatka za 1. Na početku su sve keš memorije prazne. Data je sledeća sekvenca pristupa memoriji: Napisati stanja koherencije u svim procesorima i stanje memorije posle svake promene i skicirati opisani sistem u trenutku 8. [8 poena] Da li procesori pristupaju memoriji i kada? Za svaki pristup navesti razlog. [2 poena] ROK: chrome-extension://efaidnbmnnnibpcajpcglclefindmkaj/http://mups.etf.rs/ispiti/2016-2017/mps_jul1_20162017.pdf ❗ | |||||||||||||||
52 | Feb 2017 | K1 2023 2) | K1 2020 3) | Avg 2021 3) | Avg 2022 4) | Feb 2023 5) | K3 2023 4) | ✅ Koje su osnovne osobine rutina za kolektivnu komunikaciju u MPI biblioteci? Da li svi procesi moraju da učestvuju u komunikaciji i na koji način se može smanjiti opseg komunikacije? | Kakav uticaj na performanse ima deljena memorija na GPU i kada se isplati njeno korišćenje? Napisati deo koda u prilogu tako da koristi deljenu memoriju i prokomentarisati moguće dobitke. __global__ kernel (float *devA, float *devB, int n) { int idx = blockDim.x * blockIdx.x + threadIdx.x; int left = idx > 0 ? idx-1 : 0; int right = idx < n – 1 ? idx + 1 : n – 1; devB[idx] = (0.5 * devA[left] + devA[idx] + 0.5 * devA[right])/2 } | ✅ Korišćenjem OpenMP tehnologije, paralelizovati kod koji je dat u prilogu. Kod vrši određene proračune u simulaciji prostiranja talasa na žici. Obratiti pažnju na efikasnost paralelizacije. Smatrati da su sve promenljive već definisane i incijalizovane. for (i = 1; i<= nsteps; i++) { for (j = 1; j <= tpoints; j++) { if ((j == 1) || (j == tpoints)) newval[j] = 0.0; else newval[j] = (2.0 * values[j]) - oldval[j] + (sqtau * (values[j-1] - (2.0 * values[j]) + values[j+1])); } for (j = 1; j <= tpoints; j++) { oldval[j] = values[j]; values[j] = newval[j]; } } resenje: for (i = 1; i<= nsteps; i++) { for (j = 1; j <= tpoints; j++) { if ((j == 1) || (j == tpoints)) newval[j] = 0.0; else newval[j] = (2.0 * values[j]) - oldval[j] + (sqtau * (values[j-1] - (2.0 * values[j]) + values[j+1])); } for (j = 1; j <= tpoints; j++) { oldval[j] = values[j]; values[j] = newval[j]; } } | Dat je multiprocesorski sistem sa 4 identična procesora, koji koristi MESI protokol za održavanje koherencije keš memorije. Svaka keš memorija ima po 2 ulaza, koji su veličine jedne reči. Preslikavanje je asocijativno. Početne vrednosti podataka su 0. Svaki upis uvećava vrednost izmenjenog podatka za 1. Na početku su sve keš memorije prazne. Data je sledeća sekvenca pristupa memoriji: Napisati stanja koherencije u svim procesorima i stanje memorije posle svake promene i skicirati opisani sistem u trenutku 8. [8 poena] Da li procesori pristupaju memoriji i kada? Za svaki pristup navesti razlog. [2 poena] ROK: chrome-extension://efaidnbmnnnibpcajpcglclefindmkaj/http://mups.etf.rs/ispiti/2016-2017/mps_februar_20162017.pdf | |||||||||||||||
53 | K3 2016 | K3 2020 1) | Feb 2023 5) | Avg 2023 4) | Feb 2021 6) | Zadati deo nekog CUDA jezgra poseduje jedan značajan nedostatak. Koji je to nedostatak, kako utiče na izvršavanje koda i kako bi se mogao prevazići? for (int i = 0; i < blockDim.x; i++) { if (threadIdx.x % 2) sdata[threadIdx.x] ^= sdata[i] & MASK1; else sdata[threadIdx.x] ^= sdata[i] & MASK2; } | Feb 2023 7) | Zadato jezgro CUDA vrši kompletnu obradu korišćenjem globalne memorije. Napisati ponovo jezgro, tako da se koristi deljena memorija. Obrazložiti kako korišćenje deljene memorije može da doprinese poboljšanju performansi u ovom konkretnom slučaju. __global__ void averageKernel (int* devA, int* devB, int n){ int idx = blockDim.x * blockIdx.x + threadIdx.x; int left, right; left = idx > 0 ? idx - 1 : 0; right = idx < n - 1 ? idx + 1 : n - 1; if( idx < n ) { devB[idx] = (devA[left] + devA[idx] + devA[right]) / 3; } } | ||||||||||||||||||
54 | K2 2016 | K2 2022 1) | Avg 2021 3) | K2 2023 2) | Feb 2023 4) | Koristeći rutine za neblokirajuću komunikaciju iz MPI biblioteke napisati funkciju ringCalc koja vrši kružnu obradu nad nizom celih brojeva. Proces sa rangom 0 dobija niz odbiraka sa početnim stanjem putem pokazivača A i raspoređuje ga ravnomerno svim procesima. Svaki proces radi određenu obradu nad dobijenim delom niza, zatim ga prosleđuje svom desnom susedu, a prima novi deo niza na obradu od levog suseda. Obrada se vrši dok svaki deo niza ne prođe jednom kroz sve procese. Smatrati da MPI svet nije postojao pre poziva funkcije ringCalc. double ringCalc (int* A, int n); | Sep 2021 7) | Dat je multiprocesorski sistem sa 4 identična procesora, koji koristi MOESI protokol za održavanje koherencije keš memorije. Svaka keš memorija ima po 2 ulaza, koji su veličine jedne reči. Preslikavanje je direktno. Početne vrednosti podataka su 0. Svaki upis uvećava vrednost izmenjenog podatka za 1. Na početku su sve keš memorije prazne. Data je sledeća sekvenca pristupa memoriji: Napisati stanja koherencije u svim procesorima i stanje memorije posle svake promene i skicirati opisani sistem u trenutku 8. [10 poena] Koliko puta koji od procesora pristupa memoriji? Za svaki pristup navesti razlog. [3 poena] Koliki je Hit Rate za svaki od procesora (brojati i čitanje i upis, prikazati zbirno)? [2 poena] ROK: chrome-extension://efaidnbmnnnibpcajpcglclefindmkaj/http://mups.etf.rs/ispiti/2015-2016/si4mps_k2_20152016.pdf ❌❗ | ||||||||||||||||||
55 | K1 2016 | K1 2021 2) | K1 2023 2) | K1 2020 3) | Avg 2023 2) | ✅ Korišćenjem OpenMP tehnologije, paralelizovati funkciju koja je data u prilogu. Funkcija vrši određenu obradu nad slikom predstavljenom zadatom matricom. Obratiti pažnju na efikasnost paralelizacije. void erodeOperation(double *matrix, double *result, int rows, int cols, char * se, int se_rows, int se_cols) { scr = (se_rows - 1) / 2; scc = (se_cols - 1) / 2; for(i = 0; i < rows; i++) for(j = 0; j < cols; j++) { double min_value = matrix[i * cols + j]; for(m = 0; m < se_rows; m++) for(n = 0; n < se_cols; n++) if (se[m * se_cols + n]) if ((i – scr + m) >= 0 && (j – scc + n) >= 0 && (i – scr + m) < rows && (j – scc + n) < cols) if (matrix[(i – scr + m) * cols + j – scc + n] < min_value) min_value = matrix[(i – scr + m) * cols + j – scc + n]; result[i * cols + j] = min_value; } } | Feb 2020 8) | K1 2023 7) | ||||||||||||||||||
56 | Sep 2016 | K1 2020 2) | Avg 2023 2) | Feb 2023 4) | K2 2022 3) | Feb 2023 5) | K3 2019 3) | U prilogu je dat primer jednog CUDA jezgra koje vrši uparivanje stringova. Diskutovati aritmetički intenzitet jezgra i njegovu pogodnost za izvršavanje na grafičkom procesoru i predložiti eventualna poboljšanja. Funkcija atomicAdd je ugrađena CUDA funkcija za atomično dodavanje. __global__ void kernel (int* tokA, int* tokB, int* match, int* matchIndex){ int idx = blockIdx.x * blockDim.x + threadIdx.x; int idy = blockIdx.y * blockDim.y + threadIdx.y; int substrLen = 0; if (tokA.h[idx]) == tokB.h[idy])) { while ((idx + substrLen < tokA.size) && (idy + substrLen < tokB.size) && (tokA.vector[idx + substrLen]) == (tokB.vector[idy + substrLen])) substrLen++; if (substrLen >= MML) match[atomicAdd(matchIndex, 1)] = substrLen; } } | ✅ Šta predstavlja i za šta se može koristiti polje tag u rutinama za point-to-point komunikaciju MPI biblioteke? Da li je polje obavezno? Navesti primer rutine za prijem koja prihvata jedan ceo broj od procesa sa rangom 0 bez obzira na vrednost tag-a poruke. Kakva je uloga tag polja u MPI point-to-point komunikaciji i u kojim situacijama ono može da pomogne? Da li proces može da primi poruku za bilo kojim tag-om i kako? Navesti primer. | ✅ Korišćenjem OpenMP tehnologije, paralelizovati funkciju koja je data u prilogu. Funkcija vrši numeričku integraciju funkcije f(x) na intervalu od a do b u n tačaka. Paralelizaciju izvršiti korišćenjem worksharing direktiva i korišćenjem taskova. Obratiti pažnju na efikasnost paralelizacije. Kratko diskutovati performanse oba rešenja. for ( i = 0; i < n; i++ ) { x = ( ( double ) ( n - i - 1 ) * a + ( double ) ( i ) * b ) / ( double ) ( n - 1 ); total = total + f ( x ); } | Dat je multiprocesorski sistem sa 4 identična procesora, koji koristi Dragon protokol za održavanje koherencije keš memorije. Svaka keš memorija ima po 2 ulaza, koji su veličine jedne reči. Preslikavanje je direktno. Početne vrednosti podataka su 0. Svaki upis uvećava vrednost izmenjenog podatka za 1. Na početku su sve keš memorije prazne. Data je sledeća sekvenca pristupa memoriji: Napisati stanja koherencije u svim procesorima i stanje memorije posle svake promene i skicirati opisani sistem u trenutku 8. [8 poena] Da li procesori pristupaju memoriji i kada? Za svaki pristup navesti razlog. [2 poena] ROK: chrome-extension://efaidnbmnnnibpcajpcglclefindmkaj/http://mups.etf.rs/ispiti/2015-2016/mps_septembar_20152016.pdf | |||||||||||||||
57 | Jun 2016 | K1 2021 3) | K2 2023 1) | Jun 2017 3) | ✅ Koje su vrste promašaja usled deljenja i gde se javljaju? Objasniti ih i diskutovati kako se njihov broj promašaja može smanjiti. | K3 2023 1) | K3 2023 4) | U prilogu je dato CUDA jezgro koje vrši konverziju slike iz RGB kolor modela u nijanse sive. __global__ void rgb2gray(float *grayImage, float *rgbImage, int channels, int width, int height) { int x = threadIdx.x + blockIdx.x * blockDim.x; int y = threadIdx.y + blockIdx.y * blockDim.y; if (x < width && y < height) { int grayOffset = y * width + x; int rgbOffset = grayOffset * channels; float r = rgbImage[rgbOffset]; float g = rgbImage[rgbOffset + 1]; float b = rgbImage[rgbOffset + 2]; grayImage[grayOffset] = 0.21f * r + 0.71f * g + 0.07f * b; } } a) [5] Kakav je aritmetički intenzitet ovog jezgra u odnosu na pristupe memoriji? Komentarisati. b) [5] Da li bi i na koji način korišćenje deljene memorije ubrzalo izvršavanje ovog jezgra? | ✅ Za šta služi struktura Status prilikom prijema poruke korišćenjem MPI_Recv poziva? Na koji način se može iskoristiti ova struktura, ukoliko je poruka primljena korišćenjem džoker simbola MPI_ANY_SOURCE kao izvorišta poruke? Navesti primer. | ✅ Korišćenjem OpenMP tehnologije, paralelizovati funkciju koja je data u prilogu. Funkcija vrši jednu iteraciju rešavača jedne vrste parcijalnih diferencijalnih jednačina. Obratiti pažnju na efikasnost paralelizacije. void iterate ( int nx, int ny, double dx, double dy, double f[NX][NY], int itold, int itnew, double u[NX][NY], double unew[NX][NY]) { int i, it, j; for ( it = itold + 1; it <= itnew; it++ ) { for ( j = 0; j < ny; j++ ) { for ( i = 0; i < nx; i++ ) { u[i][j] = unew[i][j]; } } for ( j = 0; j < ny; j++ ) { for ( i = 0; i < nx; i++ ) { if ( i == 0 || j == 0 || i == nx - 1 || j == ny - 1 ) { unew[i][j] = f[i][j]; } else { unew[i][j] = 0.25 * (u[i-1][j] + u[i][j+1] + u[i][j-1] + u[i+1][j] + f[i][j] * dx * dy ); } } } } return; } | Dat je multiprocesorski sistem sa 4 identična procesora, koji koristi MSI protokol za održavanje koherencije keš memorije. Svaka keš memorija ima po 2 ulaza, koji su veličine jedne reči. Preslikavanje je direktno. Početne vrednosti podataka su 0. Svaki upis uvećava vrednost izmenjenog podatka za 1. Na početku su sve keš memorije prazne. Data je sledeća sekvenca pristupa memoriji: Napisati stanja koherencije u svim procesorima i stanje memorije posle svake promene i skicirati opisani sistem u trenutku 8. [8 poena] Da li procesori pristupaju memoriji i kada? Za svaki pristup navesti razlog. [2 poena] ROK: chrome-extension://efaidnbmnnnibpcajpcglclefindmkaj/http://mups.etf.rs/ispiti/2015-2016/mps_jun_20152016.pdf ❗ | |||||||||||||||
58 | Jul 2016 | Avg 2020 1) | K1 2023 4) | ✅ Po kojim kriterijumima i kako se mogu klasifikovati rešenja za koherenciju keš memorija. | Jul2 2017 3) | K3 2023 2) | K3 2023 3) | ✅ Objasniti na koji način schedule odredba utiče na performanse koda paralelizovanog korišćenjem OpenMP tehnologije. Na primeru funkcije u prilogu predložiti i obrazložiti izbor odgovarajuće odredbe kako bi se dobile što bolje performanse. int prime_number (int n){ int i, j, prime, total = 0; for ( i = 2; i <= n; i++ ) { prime = 1; for ( j = 2; j < i; j++ ) if ( i % j == 0 ) { prime = 0; break; } total = total + prime; } return total; } | K2 2021 6) | Napisati jezgro CUDA programa koje vrši obradu nad dva znakovna niza jednake dužine. Jezgro treba da pronađe pozicije i dužine poklapanja podnizova koji se nalaze na korespodentnim pozicijama u zadatim nizovima. Smatrati da poklapanja nisu duža od 256 znakova. Nizovi su alocirani unapred. Koristiti 1D organizaciju jezgra. Prilikom rešavanja zadatka koristiti deljenu memoriju i voditi računa da se ostvari maksimalan paralelizam. Navesti poziv (izvršnu konfiguraciju) jezgra za nizove dužine 1M elemenata. __global__ void match (char* s1, char* s2, char* out, int n); | Dat je multiprocesorski sistem sa 4 identična procesora, koji koristi Firefly protokol za održavanje koherencije keš memorije. Svaka keš memorija ima po 2 ulaza, koji su veličine jedne reči. Preslikavanje je direktno. Početne vrednosti podataka su 0. Svaki upis uvećava vrednost izmenjenog podatka za 1. Na početku su sve keš memorije prazne. Data je sledeća sekvenca pristupa memoriji: Napisati stanja koherencije u svim procesorima i stanje memorije posle svake promene i skicirati opisani sistem u trenutku 8. [8 poena] Da li procesori pristupaju memoriji i kada? Za svaki pristup navesti razlog. [2 poena] ROK: chrome-extension://efaidnbmnnnibpcajpcglclefindmkaj/http://mups.etf.rs/ispiti/2015-2016/mps_jul_20152016.pdf | |||||||||||||||
59 | Feb 2016 | Jul 2018 1) | Feb 2023 2) | K2 2023 3) | K2 2022 3) | K3 2023 2) | Avg 2023 6) | Šta su to rutine za neblokirajuću komunikaciju u MPI biblioteci? Deo koda sa slike napisati tako da se upotrebljavaju rutine za neblokirajuću komunikaciju. int outmsg, inmsg, rc, tag=1; MPI_Status Stat; ... if (rank == 0) { rc = MPI_Send(&outmsg, 1, MPI_CHAR, 1, tag, MPI_COMM_WORLD); } else if (rank == 1) { rc = MPI_Recv(&inmsg, 1, MPI_CHAR, 0, tag, MPI_COMM_WORLD, &Stat); } | ✅ 1) Šta kontroliše schedule odredba for direktive kod OpenMP tehnologije? Dati primer for petlje kod koje se vrši ravnomerna, ciklična raspodela iteracija petlje nitima u grupama od po četiri iteracije 2) Kakav uticaj na performanse ima schedule odredba prilikom primene OpenMP for direktive? Navesti dva slučaja kada primena ove odredbe može da pomogne poboljšanju performansi. | Po ugledu na priloženi kod, napisati jezgro CUDA programa koje određuje ukupan broj prostih brojeva u prvih n celih brojeva. Prilikom rešavanja zadatka koristiti deljenu memoriju za smeštanje međurezultata i voditi računa da se ostvari maksimalan paralelizam. Navesti poziv (izvršnu konfiguraciju) jezgra za n = 100000. int prime_number (int n){ int i, j, prime, total = 0; for ( i = 2; i <= n; i++ ) { prime = 1; for ( j = 2; j < i; j++ ){ if ( i % j == 0 ) { prime = 0; break; } total = total + prime; } return total; } | Dat je multiprocesorski sistem sa 4 identična procesora, koji koristi Dragon protokol za održavanje koherencije keš memorije. Svaka keš memorija ima po 2 ulaza, koji su veličine jedne reči. Preslikavanje je direktno. Početne vrednosti podataka su 0. Svaki upis uvećava vrednost izmenjenog podatka za 1. Na početku su sve keš memorije prazne. Data je sledeća sekvenca pristupa memoriji: Napisati stanja koherencije u svim procesorima i stanje memorije posle svake promene i skicirati opisani sistem u trenutku 8. [8 poena] Da li procesori pristupaju memoriji i kada? Za svaki pristup navesti razlog. [2 poena] ROK: chrome-extension://efaidnbmnnnibpcajpcglclefindmkaj/http://mups.etf.rs/ispiti/2015-2016/mps_februar_20152016.pdf ❗ | |||||||||||||||
60 | K3 2015 | Feb 2023 4) | Avg 2023 5) | K3 2023 2) | Objasniti kakve su prednosti i nedostaci organizacije čvora kao manjeg multiprocesora u hijerarhijskim multiprocesorskim sistemima. | U datom kodu je prikazana loša paralelna redukcija na grafičkom procesoru. Kratko objasniti do kog problema dolazi kod izvšršavanja zadatog koda i napisati deo koda koji ispravlja izložene nedostatke. __global__ void reduce(int *g_idata, int *g_odata) { extern __shared__ int sdata[]; unsigned int tid = threadIdx.x; unsigned int i = blockIdx.x * blockDim.x + threadIdx.x; sdata[tid] = g_idata[i]; for (unsigned int stride = 1; s < blockDim.x; s *= 2) { __syncthreads(); int index = 2 * stride * tid; if (index < blockDim.x) { sdata[index] += sdata[index + stride]; } } if (tid == 0) g_odata[blockIdx.x] = sdata[0]; } | K2 2017 3) | Napisati jezgro CUDA programa koje vrši obradu nad jednodimenzionalnim nizom celih brojeva. Jezgro treba da formira novi niz čiji su elementi ciklično pomereni za offset mesta ulevo ili udesno, što je definisano argumentom direction. Dužina niza može biti proizvoljna. Voditi računa da se ostvari maksimalan paralelizam. _global__ void func (int* in, int* out, int n, int offset, int direction); | ||||||||||||||||||
61 | K2 2015 | Okt 2017 4) | K2 2023 1) | K2 2023 3) | K2 2023 2) | Neka se posmatra jedan program koji simulira amplitudu talasa duž uniformne, vibrirajuće žice. Talas se predstavlja pomoću niza realnih odbiraka (tačaka) zadate dužine n. Amplituda talasa u nekoj tački zavisi i od susednih tačaka i od amplitude tačke u prethodnim vremenskim trenucima i računa se po sledećoj formuli: A(i,t+1) = (2.0 * A(i,t)) - A(i,t-1)+ (c * (A(i-1,t) - (2.0 * A(i,t)) + A(i+1,t))) gde i predstavlja koordinatu tačke, a t vremenski trenutak (iteraciju) u kojoj se amplituda izračunava. Koristeći rutine iz MPI biblioteke napisati funkciju calcAmplitude koja izračunava stanje zadatog talasa dužine n nakon maxIter iteracija. Proces sa rangom 0 dobija niz odbiraka sa početnim stanjem putem pokazivača A i raspoređuje ga ravnomerno svim procesima, učestvuje u obradi i sakuplja konačan rezultat izvršavanja. Smatrati da MPI svet nije postojao pre poziva funkcije calcAmplitude. double calcAmplitude (int* A, int n, int c, int maxIter); | K2 2020 6) | Dat je multiprocesorski sistem sa 4 identična procesora, koji koristi Firefly protokol za održavanje koherencije keš memorije. Svaka keš memorija ima po 2 ulaza, koji su veličine jedne reči. Preslikavanje je direktno. Početne vrednosti podataka su 0. Svaki upis uvećava vrednost izmenjenog podatka za 1. Na početku su sve keš memorije prazne. Data je sledeća sekvenca pristupa memoriji: Napisati stanja koherencije u svim procesorima i stanje memorije posle svake promene i skicirati opisani sistem u trenutku 8. [10 poena] Koliko puta koji od procesora pristupa memoriji? Za svaki pristup navesti razlog. [3 poena] Koliki je Hit Rate za svaki od procesora (brojati i čitanje i upis, prikazati zbirno)? [2 poena] ROK: chrome-extension://efaidnbmnnnibpcajpcglclefindmkaj/http://mups.etf.rs/ispiti/2014-2015/si4mps_k2_20142015.pdf | ||||||||||||||||||
62 | K1 2015 | K1 2022 1) | K2 2023 1) | Jul 2022 2) | Okt 2009 2) | ✅ Korišćenjem OpenMP tehnologije, paralelizovati funkciju koja je data u prilogu. Funkcija računa histogram zadate slike. Obratiti pažnju na efikasnost paralelizacije. int* histogram (unsigned int* img, unsigned char* histo, unsigned int img_width, unsigned int img_height, unsigned int histo_width, unsigned int histo_height, int numIterations) { unsigned int i, iter; for (iter = 0; iter < numIterations; iter++){ memset(histo,0,histo_height*histo_width*sizeof(unsigned char)); unsigned int i; for (i = 0; i < img_width*img_height; ++i) { const unsigned int value = img[i]; if (histo[value] < 256) ++histo[value]; } } } Rešenje: int* histogram (unsigned int* img, unsigned char* histo, unsigned int img_width, unsigned int img_height, unsigned int histo_width, unsigned int histo_height, int numIterations) { unsigned int i, iter; for (iter = 0; iter < numIterations; iter++){ memset(histo,0,histo_height*histo_width*sizeof(unsigned char)); for (i = 0; i < img_width*img_height; ++i) { const unsigned int value = img[i]; if (histo[value] < 255) ++histo[value]; } } } | K1 2022 6) | K1 2023 7) | ||||||||||||||||||
63 | Sep 2015 | Feb 2021 1) | K1 2023 4) | Avg 2021 3) | ✅ Objasniti implikacije protokola za koherenciju na pisanje paralelnog koda. Diskutovati prednosti implikacije protokola koherencije na pisanje paralelnih programa. Navesti implikacije na pisanje paralelnih programa. | Feb 2023 5) | K3 2019 3) | Korišćenjem rutina iz MPI biblioteke, paralelizovati deo koda u prilogu. Obratiti pažnju na efikasnost paralelizacije. Smatrati da je MPI svet već inicijalizovan, a neophodna memorija već alocirana. Proces sa rangom 0 treba da rasporedi ulazni niz podjednako svim procesima, učestvuje u obradi i sakupi konačan rezultat izvršavanja. Smatrati da je dužina niza deljiva brojem procesa. int *in, int *out, int *t, int n, int iter, int c1, int c2; ... for (int i = 0; i < iter; i++) { for (int j = 0; j < n; j++) { int left = j > 0 ? j – 1 : n – 1; int right = j < n – 1 ? j + 1 : 0; out[j] = c2 * (in[left] + in[right]) + c1 * in[j]; } t = in; in = out; out = t; } | ✅ U čemu je razlika između single i master OpenMP direktiva? Na primeru koda u prilogu, objasniti i naznačiti kako bi se primenila jedna, a kako druga direktiva da bi se funkcija init() izvršila od strane samo jedne niti uz korektno izvršavanje koda Master direktiva: #pragma omp parallel { init(a); #pragma omp for for(i = 0; i < n; i++) { b[i] = c1 * a[i] + c2; } } Slave direktiva: #pragma omp parallel { init(a); #pragma omp for for(i = 0; i < n; i++) { b[i] = c1 * a[i] + c2; } } | Sep 2022 8) | Dat je multiprocesorski sistem sa 4 identična procesora, koji koristi MOESI protokol za održavanje koherencije keš memorije. Svaka keš memorija ima po 2 ulaza, koji su veličine jedne reči. Preslikavanje je direktno. Početne vrednosti podataka su 0. Svaki upis uvećava vrednost izmenjenog podatka za 1. Na početku su sve keš memorije prazne. Data je sledeća sekvenca pristupa memoriji: Napisati stanja koherencije u svim procesorima i stanje memorije posle svake promene i skicirati opisani sistem u trenutku 8. [8 poena] Da li procesori pristupaju memoriji i kada? Za svaki pristup navesti razlog. [2 poena] ROK: chrome-extension://efaidnbmnnnibpcajpcglclefindmkaj/http://mups.etf.rs/ispiti/2014-2015/mps_septembar_20142015.pdf | |||||||||||||||
64 | Jun 2015 | K1 2023 1) | Avg 2023 2) | Jul 2017 3) | ✅ Objasniti prednosti i nedostatke povećanja bloka keš memorije. Navesti načine kako se nedostaci mogu ublažiti. | K3 2021 2) | K3 2019 3) | Napisati jezgro CUDA programa koje vrši obradu nad dvodimenzionalnom matricom celih brojeva. Svaka nit najpre treba da izvrši XOR operaciju nad elementima odgovarajuće kolone, a zatim niti unutar bloka treba da zajednički izvrše XOR operaciju nad dobijenim međurezultatima. Koristiti 1D organizaciju jezgra. Prilikom rešavanja zadatka koristiti deljenu memoriju za smeštanje međurezultata i voditi računa da se ostvari maksimalan paralelizam. Navesti poziv (izvršnu konfiguraciju) jezgra za matricu dimenzija 200x300. __global__ void matxor (int* in, int* out, int m, int n); | ✅ Na koji način se sve može kontrolisati broj pokrenutih niti u paralelnom regionu kod OpenMP tehnologije? Da li se dva paralelna regiona u okviru istog programa mogu pokrenuti sa različitim brojem niti? Navesti primer. | Jun 2023 8) | Dat je multiprocesorski sistem sa 4 identična procesora, koji koristi MESI protokol za održavanje koherencije keš memorije. Svaka keš memorija ima po 2 ulaza, koji su veličine jedne reči. Preslikavanje je asocijativno. Početne vrednosti podataka su 0. Svaki upis uvećava vrednost izmenjenog podatka za 1. Na početku su sve keš memorije prazne. Data je sledeća sekvenca pristupa memoriji: Napisati stanja koherencije u svim procesorima i stanje memorije posle svake promene i skicirati opisani sistem u trenutku 8. [8 poena] Da li procesori pristupaju memoriji i kada? Za svaki pristup navesti razlog. [2 poena] ROK: chrome-extension://efaidnbmnnnibpcajpcglclefindmkaj/http://mups.etf.rs/ispiti/2014-2015/mps_jun_20142015.pdf | |||||||||||||||
65 | Jul 2015 | Navesti i objasniti glavne namene paralelnih računara. Objasniti četiri glavne namene paralelnih računara. Navesti četiri razloga upotrebe paralelnih računara | K1 2018 3) | K2 2023 3) | Feb 2022 4) | Feb 2023 5) | K3 2015 4) | ❗ Korišćenjem OpenMP tehnologije, paralelizovati funkciju koja je data u prilogu. Obratiti pažnju na efikasnost paralelizacije. void process (int cols, int penalty, int *in, int *ref) { int idx, index; for( int i = 0 ; i < cols-2 ; i++){ for( idx = 0 ; idx <= i ; idx++){ index = (idx + 1) * cols + (i + 1 - idx); in[index]= max(in[index-1-cols] + ref[index], in[index-1] - penalty, in[index-cols] - penalty); } } for( int i = cols - 4 ; i >= 0 ; i--){ for( idx = 0 ; idx <= i ; idx++){ index = (cols - idx - 2) * cols + idx + cols - i - 2; in[index]= max(in[index-1-cols]+ ref[index], in[index-1] - penalty, in[index-cols] - penalty); } } } Rešenje: void process (int cols, int penalty, int *in, int *ref) { int idx, index; for( int i = 0 ; i < cols-2 ; i++){ for( idx = 0 ; idx <= i ; idx++){ index = (idx + 1) * cols + (i + 1 - idx); in[index]= max(in[index-1-cols] + ref[index], in[index-1] - penalty, in[index-cols] - penalty); } } for( int i = cols - 4 ; i >= 0 ; i--){ for( idx = 0 ; idx <= i ; idx++){ index = (cols - idx - 2) * cols + idx + cols - i - 2; in[index]= max(in[index-1-cols]+ ref[index], in[index-1] - penalty, in[index-cols] - penalty); } } } | U prilogu je dato jezgro napisano na CUDA tehnologiji koje vrši operaciju redukcije. Da li je priloženo jezgro ispravno? Ukoliko nije, dopisati i objasniti neophodne izmene, tako da jezgro ispravno vrši operaciju redukcije. Smatrati da jedan blok sadrži 256 niti. __global__ void reductionSum (int* devA, int* blockResults, int n) { extern __shared__ int sharedData[]; unsigned int tid = threadIdx.x; unsigned int i = blockIdx.x * blockDim.x + threadIdx.x; if (i < n) sharedData[tid] = devA[i]; else sharedData[tid] = 0; __syncthreads(); if (tid < 128) sharedData[tid] += sharedData[tid + 128]; if (tid < 64) sharedData[tid] += sharedData[tid + 64]; if (tid < 32) sharedData[tid] += sharedData[tid + 32]; if (tid < 16) sharedData[tid] += sharedData[tid + 16]; if (tid < 8) sharedData[tid] += sharedData[tid + 8]; if (tid < 4) sharedData[tid] += sharedData[tid + 4]; if (tid < 2) sharedData[tid] += sharedData[tid + 2]; if (tid < 1) sharedData[tid] += sharedData[tid + 1]; if (tid == 0) blockResults[blockIdx.x] = sharedData[0]; } | Šta rade i čemu služe MPI operacije Scatter i Gather? Da li su ove operacije blokirajuće? Navesti primer korišćenja Scatter operacije u MPI svetu sa 4 procesa kod koga se u procesu sa rangom 0 nalazi niz od 100 elemenata. | Dat je multiprocesorski sistem sa 4 identična procesora, koji koristi Firefly protokol za održavanje koherencije keš memorije. Svaka keš memorija ima po 2 ulaza, koji su veličine jedne reči. Preslikavanje je direktno. Početne vrednosti podataka su 0. Svaki upis uvećava vrednost izmenjenog podatka za 1. Na početku su sve keš memorije prazne. Data je sledeća sekvenca pristupa memoriji: Napisati stanja koherencije u svim procesorima i stanje memorije posle svake promene i skicirati opisani sistem u trenutku 8. [8 poena] Da li procesori pristupaju memoriji i kada? Za svaki pristup navesti razlog. [2 poena] ROK: chrome-extension://efaidnbmnnnibpcajpcglclefindmkaj/http://mups.etf.rs/ispiti/2014-2015/mps_jul_20142015.pdf | |||||||||||||||
66 | Feb 2015 | Objasniti probleme dovođenja energije i odvođenja toplote u savremenim procesorima. | Feb 2023 2) | Avg 2023 3) | Avg 2022 4) | Avg 2023 4) | K3 2023 2) | ✅ Na koji način se može sprovesti operacija redukcije korišćenjem OpenMP tehnologije? Na primeru koda u prilogu, prikazati dva načina na koji se može obaviti ova operacija prlikom paralelizacije koda korišćenjem OpenMP. for (j = 0; j < n; j++) sum += b[j]; | Sep 2016 8) | Napisati jezgro CUDA programa koje vrši obradu nad dvodimenzionalnom matricom celih brojeva. Jezgro treba da formira novu matricu na osnovu postojeće tako da svaki element novoformirane matrice dobija vrednost najvećeg od četiri moguća suseda (gore, dole, levo, desno). Smatrati da su matrice alocirane unapred. Koristiti 2D organizaciju jezgra. Prilikom rešavanja zadatka koristiti deljenu memoriju za smeštanje međurezultata i voditi računa da se ostvari maksimalan paralelizam. Navesti poziv (izvršnu konfiguraciju) jezgra za matricu dimenzija 500x200. __global__ void maxmat (float* in, float* out, int m, int n); | Dat je multiprocesorski sistem sa 4 identična procesora, koji koristi Dragon protokol za održavanje koherencije keš memorije. Svaka keš memorija ima po 2 ulaza, koji su veličine jedne reči. Preslikavanje je direktno. Početne vrednosti podataka su 0. Svaki upis uvećava vrednost izmenjenog podatka za 1. Na početku su sve keš memorije prazne. Data je sledeća sekvenca pristupa memoriji: Napisati stanja koherencije u svim procesorima i stanje memorije posle svake promene i skicirati opisani sistem u trenutku 8. [8 poena] Da li procesori pristupaju memoriji i kada? Za svaki pristup navesti razlog. [2 poena] ROK: chrome-extension://efaidnbmnnnibpcajpcglclefindmkaj/http://mups.etf.rs/ispiti/2014-2015/mps_februar_20142015.pdf | |||||||||||||||
67 | K3 2014 | Jun 2022 4) | ✅ Objasniti zašto primena isključivo invalidacione ili ažurirajuće strategije najčešće nije optimalno rešenje. Objasniti kako se to prevazilazi. | K3 2023 1) | Avg 2023 4) | Šta predstavlja loop unrolling tehnika za optimizaciju petlji? Na primeru reductionSum jezgra pokazati kako ona može da doprinese poboljšanju performansi koda koji se izvršava na grafičkom procesoru __global__ void reductionSum (int* devA, int* blockResults, int n) { extern __shared__ int sharedData[]; unsigned int tid = threadIdx.x; unsigned int i = blockIdx.x * blockDim.x + threadIdx.x; if (i < n) sharedData[tid] = devA[i]; else sharedData[tid] = 0; __syncthreads(); for (unsigned int s = blockDim.x/2; s > 0; s >>= 1) { if (tid < s) { sharedData[tid] += sharedData[tid + s]; } __syncthreads(); } if (tid == 0) blockResults[blockIdx.x] = sharedData[0]; } | Sep 2022 8) | Napisati jezgro CUDA programa koje vrši obradu nad dvodimenzionalnom kvadratnom matricom realnih brojeva. Jezgro treba da formira novu matricu na osnovu postojeće tako da svaki element novoformirane matrice ima vrednost: Outx,y = C1 ∙ Inx,y + C2 ∙ (Inx-1,y + Inx+1,y + Inx,y-1 + Inx,y+1) / 4 Smatrati da svaki element matrice ima najviše četiri suseda. Smatrati da su matrice alocirane unapred. Koristiti 2D organizaciju jezgra. Prilikom rešavanja zadatka koristiti deljenu memoriju za smeštanje međurezultata i voditi računa da se ostvari maksimalan paralelizam. __global__ void filter (float* in, float* out, int n, float C1, float C2); | ||||||||||||||||||
68 | K2p 2014 | Okt 2009 2) | Napisati izraz za vreme prenosa u linearnom modelu. Objasniti značenje pojednih komponenata. | Definisati model sekvencijalne konzsitencije i ograničen ja koja nameće. Šta određuje model memorijske konzistencije? Dali koherencija garantuje konzistenciju. Pokazati na primeru. Definisati pojam sekvencijalne konzistencije i navesti koji su dovoljni uslovi za njuŠta određuje model memorijske konzistencije? Kakve su njegove implikacije? Definisati pojam sekvencijalne konzistencije. Koji su dovoljni uslovi za sekvencijalnu konzistenciju? Objasniti i uporediti pojmove memorijske koherencije i konzistencije. Definisati njihov odnos. Objasniti da li je neophodno da neki sistem bude sekvencijalno konzistentan i kakvo je alternativno rešenje. Definisati pojam sekvencijalne konzistencije. Ako se u jednom sekvencijalno konzistentnom sistemu na dva procesora izvršavaju sledeća dva programska segmenta P1 P2 A = 1 B = 1 Print B Print C C = 1 Print A a početne vrednosti su A=B=C=0, pokazati da li su mogući sledeći ishodi za (A, B) : a) (1, 0, 0) i b) (0, 0, 1). Definisti pojam sekvencijalne konzistencije. Neka se u nekom sekvencijalno konzistentnom sistemu izvršavaju procesi P1 i P2: P1 P2 (1a) A = 1; (2a) print B; (1b) B = 2; (2b) print A; Pokazati da li je poredak izvršavanja 1b->1a->2b->2a ispravan? Kakve su implikacije modela konzistencije | Jan 2014 3) | Jul 2023 7) | Neka su data dva niza celih brojeva. Potrebno je formirati novi niz od ulaznih nizova tako da bude zadovoljen uslov c[i] = max(a[i], b[i]). Nizovi su alocirani u procesu sa rangom 0 (master). Smatrati da je broj elemenata niza deljiv brojem procesa u MPI svetu. Koristeći MPI biblioteku: a) [5] Napisati deo koda master procesa koji ravnomerno raspoređuje ulazne nizove svim procesima i prihvata rezultat rada nakon formiranja trećeg niza. b) [10] Ukoliko ulazne nizove treba raspodeliti ciklički, napisati deo koda master i slave procesa kojim se elementi nizova ravnomerno raspoređuju svim procesima. Dovoljno je napisati kod na primeru jednog ulaznog niza. | Dat je multiprocesorski sistem sa 4 identična procesora, koji koristi MOESI protokol za održavanje koherencije keš memorije. Svaka keš memorija ima po 2 ulaza, koji su veličine jedne reči. Preslikavanje je direktno. Početne vrednosti podataka su 0. Svaki upis uvećava vrednost izmenjenog podatka za 1. Na početku su sve keš memorije prazne. Data je sledeća sekvenca pristupa memoriji: Napisati stanja koherencije u svim procesorima i stanje memorije posle svake promene i skicirati opisani sistem u trenutku 8. [10 poena] Koliko puta koji od procesora pristupa memoriji? Za svaki pristup navesti razlog. [3 poena] Koliki je Hit Rate za svaki od procesora (brojati i čitanje i upis, prikazati zbirno)? [2 poena] ROK: chrome-extension://efaidnbmnnnibpcajpcglclefindmkaj/http://mups.etf.rs/ispiti/2013-2014/si4mps_k2p_20132014.pdf ❌❗❗❗❗ | ||||||||||||||||||
69 | K2 2014 | Feb 2023 2) | K2 2022 1) | K2p 2014 3) | Avg 2023 3) | ROK: chrome-extension://efaidnbmnnnibpcajpcglclefindmkaj/http://mups.etf.rs/ispiti/2013-2014/si4mps_k2_20132014.pdf | Neka je stvoren MPI svet koji se sastoji od 10 procesa. Neka proces sa rangom 0 učita celobrojnu vrednost n sa standardnog ulaza. a) [3] Navesti poziv rutine za kolektivnu komunikaciju koji omogućava prosleđivanje unete vrednosti svim ostalim procesima u MPI svetu. b) [7] Da li se ista rutina za kolektivnu komunikaciju može iskoristiti za slanje istog podatka određenoj grupi procesa u MPI svetu? Ako jeste, napisati deo koda koji omogućava korišćenje iste rutine za kolektivnu komunikaciju za slanje podatka grupi procesa sa rangovima 4, 6, 7 i 9. | Dat je multiprocesorski sistem sa 4 identična procesora, koji koristi Dragon protokol za održavanje koherencije keš memorije. Svaka keš memorija ima po 2 ulaza, koji su veličine jedne reči. Preslikavanje je direktno. Početne vrednosti podataka su 0. Svaki upis uvećava vrednost izmenjenog podatka za 1. Na početku su sve keš memorije prazne. Data je sledeća sekvenca pristupa memoriji: Napisati stanja koherencije u svim procesorima i stanje memorije posle svake promene i skicirati opisani sistem u trenutku 8. [10 poena] Koliko puta koji od procesora pristupa memoriji? Za svaki pristup navesti razlog. [3 poena] Koliki je Hit Rate za svaki od procesora (brojati i čitanje i upis, prikazati zbirno)? [2 poena] ROK:chrome-extension://efaidnbmnnnibpcajpcglclefindmkaj/http://mups.etf.rs/ispiti/2013-2014/si4mps_k2_20132014.pdf | ||||||||||||||||||
70 | K1p 2014 | Avg 2020 1) | ✅ Objasniti kako povećanje broja procesora u sistemu obično utiče na ubrzanje i nacrtati tipičnu krivu. Objasniti razloge koji onemogućavaju da se postigne linearno ubrzanje. | K1 2018 3) | Feb 2021 6) | ❗ Kakva pravila vidljivosti važe za promenljive unutar parallel regiona? Da li private promenljive dobijaju neku inicijalnu vrednost i na koji način se to može postići? - Shared!!! podrazumevano | ✅ Korišćenjem OpenMP tehnologije, paralelizovati funkciju koja je data u prilogu. Funkcija vrši množenje zadate matrice vektorom. Obratiti pažnju na efikasnost paralelizacije pod pretpostavkom da je matrica retka. void matVecMul(long M, long N, double *a, double *b, double *c) { long i, j, k; for(i = 0; i < N; i++) { c[i] = 0.0; } for(i = 0; i < M; i++) for(j = 0; j < N; j++) c[i] += a[i * N + j] * b[j]; } | K1 2023 7) | ||||||||||||||||||
71 | K1 2014 | Jun 2022 1) | K1 2023 2) | K1 2023 4) | Avg 2023 2) | ✅ Korišćenjem OpenMP tehnologije, paralelizovati funkciju koja je data u prilogu. Funkcija vrši sumiranje elemenata po nizovima različite dužine. Obratiti pažnju na efikasnost paralelizacije. int* countTheMoney (int **bags, int* bagsCount, int bagsNum) { int* bagsSum, i, j; bagsSum = (int*) malloc(bagsNum * sizeof(int)); for (i = 0; i < bagsNum; i++) bagsSum[i] = 0; for (i = 0; i < bagsNum; i++) for (j = 0; j < bagsCount[i]; j++) { bagsSum[i] += bags[i][j]; } return bagsSum; } | Jul 2022 7) | K1 2023 7) | ||||||||||||||||||
72 | Okt 2014 | Avg 2020 1) | Feb 2023 2) | Avg 2023 5) | Feb 2023 4) | Feb 2023 6) | ✅ Objasniti kako može doći do problema koherencije čak i kada nema logičkog deljenja podataka između procesa. | Neka su data dva niza celih brojeva. Potrebno je formirati novi niz od ulaznih nizova tako da bude zadovoljen uslov c[i] = min(a[i], b[i]). Nizovi su alocirani u procesu sa rangom 0 (master). Smatrati da je broj elemenata niza deljiv brojem procesa u MPI svetu. Koristeći MPI biblioteku: a) [5] Napisati deo koda master procesa koji ravnomerno raspoređuje ulazne nizove svim procesima i prihvata rezultat rada nakon formiranja trećeg niza. b) [5] Ukoliko rezultat rada treba da se nađe u svim procesima, napisati deo koda koji to omogućava. c) [5] Napisati definiciju izvedenog tipa kojim bi se omogućilo ciklično raspoređivanje elemenata ulaznih nizova na n procesa u blokovima od po 5 elemenatač. | Feb 2023 7) | Feb 2016 8) | Dat je multiprocesorski sistem sa 4 identična procesora, koji koristi Firefly protokol za održavanje koherencije keš memorije. Svaka keš memorija ima po 2 ulaza, koji su veličine jedne reči. Preslikavanje je direktno. Početne vrednosti podataka su 0. Svaki upis uvećava vrednost izmenjenog podatka za 1. Na početku su sve keš memorije prazne. Data je sledeća sekvenca pristupa memoriji: Napisati stanja koherencije u svim procesorima i stanje memorije posle svake promene i skicirati opisani sistem u trenutku 8. [8 poena] Da li procesori pristupaju memoriji i kada? Za svaki pristup navesti razlog. [2 poena] ROK: chrome-extension://efaidnbmnnnibpcajpcglclefindmkaj/http://mups.etf.rs/ispiti/2013-2014/mps_oktobar_20132014.pdf | |||||||||||||||
73 | Jun 2014 | K1p 2014 2) | K2p 2014 3) | Avg 2021 3) | K2 2022 3) | K3 2023 2) | Avg 2023 4) | 💻 Korišćenjem OpenMP tehnologije, paralelizovati funkciju koja je data u prilogu. Funkcija vrši LU dekompoziciju kvadratne matrice koja je u memoriji linearizovana po vrstama. Obratiti pažnju na efikasnost paralelizacije. void luDecomposition(float *a, int size) { int i,j,k; float sum; for (i=0; i<size; i++){ for (j=i; j<size; j++){ sum=a[i*size+j]; for (k=0; k<i; k++) sum -= a[i*size+k]*a[k*size+j]; a[i*size+j]=sum; } for (j=i+1;j<size; j++){ sum=a[j*size+i]; for (k=0; k<i; k++) sum -=a[j*size+k]*a[k*size+i]; a[j*size+i]=sum/a[i*size+i]; } } } Rešenje: void luDecomposition(float *a, int size) { int i,j,k; float sum; for (i=0; i<size; i++){ for (j=i; j<size; j++){ sum=a[i*size+j]; for (k=0; k<i; k++) sum -= a[i*size+k]*a[k*size+j]; a[i*size+j]=sum; } for (j=i+1;j<size; j++){ sum=a[j*size+i]; for (k=0; k<i; k++) sum -=a[j*size+k]*a[k*size+i]; a[j*size+i]=sum/a[i*size+i]; } } } | Šta predstavlja pojam memory coalescing-a i na koji način niti treba da pristupaju podacima u globalnoj memoriji grafičkog procesora da bi se ostvarile maksimalne performanse? | K2 2020 6) | Dat je multiprocesorski sistem sa 4 identična procesora, koji koristi MSI protokol za održavanje koherencije keš memorije. Svaka keš memorija ima po 2 ulaza, koji su veličine jedne reči. Preslikavanje je direktno. Početne vrednosti podataka su 0. Svaki upis uvećava vrednost izmenjenog podatka za 1. Na početku su sve keš memorije prazne. Data je sledeća sekvenca pristupa memoriji: Napisati stanja koherencije u svim procesorima i stanje memorije posle svake promene i skicirati opisani sistem u trenutku 8. [8 poena] Da li procesori pristupaju memoriji i kada? Za svaki pristup navesti razlog. [2 poena] ROK: chrome-extension://efaidnbmnnnibpcajpcglclefindmkaj/http://mups.etf.rs/ispiti/2013-2014/mps_jun_20132014.pdf ❌❗ | |||||||||||||||
74 | Jul 2014 | ✅ Objasniti razloge koji su doveli do multicore procesora. | Okt 2009 2) | Avg 2021 3) | K2 2023 1) | Jul 2023 5) | Avg 2023 4) | Korišćenjem CUDA tehnologije, napisati jezgro (kernel) koje određuje broj pojavljivanja elemenata u zadatom nizu celih brojeva koji su deljivi sa zadatim brojem k. Smatrati da je alokacija memorije obavljena unapred. Obratiti pažnju na efikasnost paralelizacije. __global__ void stat_k (int* array, int n, int k); | ✅ Kakva je prednost korišćenja tzv. orphaned direktiva kod OpenMP i kada se one mogu koristiti? Na primeru sa slike prikazati kako se ove direktive koriste. void main { int a[100], n, iter; ... for(i=0; i < iter; i++) { load_from_file(a, n); dowork(a, n); save_to_file(a, n); } ... } void dowork(int *a, int n) { for(i=0; i < n; i++) { a[i]++; } } | U čemu je glavna razlika između sinhrone i blokirajuće komunikacije kod MPI komunikacije? Da li je sihrona komunikacija istovremeno i blokirajuća? | Dat je multiprocesorski sistem sa 4 identična procesora, koji koristi WTI writeno-allocate protokol za održavanje koherencije keš memorije. Svaka keš memorija ima po 2 ulaza, koji su veličine jedne reči. Preslikavanje je direktno. Početne vrednosti podataka su 0. Svaki upis uvećava vrednost izmenjenog podatka za 1. Na početku su sve keš memorije prazne. Data je sledeća sekvenca pristupa memoriji: Napisati stanja koherencije u svim procesorima i stanje memorije posle svake promene i skicirati opisani sistem u trenutku 8. [8 poena] Da li procesori pristupaju memoriji i kada? Za svaki pristup navesti razlog. [2 poena] ROK: chrome-extension://efaidnbmnnnibpcajpcglclefindmkaj/http://mups.etf.rs/ispiti/2013-2014/mps_jul_20132014.pdf | |||||||||||||||
75 | Jan 2014 | Avg 2020 1) | K1p 2014 2) | Avg 2021 3) | K2p 2014 3) | K3 2014 2) | Avg 2023 4) | / | Sep 2022 8) | Neka su data dva niza celih brojeva. Potrebno je formirati novi niz od ulaznih nizova tako da bude zadovoljen uslov c[i] = max(a[i], b[i]). Nizovi su alocirani u procesu sa rangom 0 (master). Smatrati da je broj elemenata niza deljiv brojem procesa u MPI svetu. Koristeći MPI biblioteku: a) [5] Napisati deo koda master procesa koji ravnomerno raspoređuje ulazne nizove svim procesima i prihvata rezultat rada nakon formiranja trećeg niza. b) [10] Ukoliko ulazne nizove treba raspodeliti ciklički, napisati deo koda master i slave procesa kojim se elementi nizova ravnomerno raspoređuju svim procesima. Dovoljno je napisati kod na primeru jednog ulaznog niza. | Dat je multiprocesorski sistem sa 4 identična procesora, koji koristi MOESI protokol za održavanje koherencije keš memorije. Svaka keš memorija ima po 2 ulaza, koji su veličine jedne reči. Preslikavanje je direktno. Početne vrednosti podataka su 0. Svaki upis uvećava vrednost izmenjenog podatka za 1. Na početku su sve keš memorije prazne. Data je sledeća sekvenca pristupa memoriji: Napisati stanja koherencije u svim procesorima i stanje memorije posle svake promene i skicirati opisani sistem u trenutku 8. [8 poena] Da li procesori pristupaju memoriji i kada? Za svaki pristup navesti razlog. [2 poena] ROK: chrome-extension://efaidnbmnnnibpcajpcglclefindmkaj/http://mups.etf.rs/ispiti/2013-2014/mps_januar_20132014.pdf | |||||||||||||||
76 | Feb 2014 | K1 2023 2) | Avg 2023 2) | K2 2023 3) | K2 2023 2) | Objasniti osnovne principe hijerarhijskih directory protokola. Objasniti princip organizacije hijerarhijskih kataloga. | Feb 2023 5) | ✅ Kod kojih sve konstrukata postoje implicitno definisane barijere kod OpenMP tehnologije? Da li se barijera može ukloniti ukoliko je suvišna? Na primeru koda u prilogu, izvršiti uklanjanje barijere dodavanjem odgovarajućih odredbi. #pragma omp for for (j = 0; j < n; j++) a[j] = b[j] + c[j]; #pragma omp for for (j = 0; j < n; j++) d[j] = e[j] + f[j]; #pragma omp for for (j = 0; j < n; j++) z[j] = a[j] + a[j+1]; | Sep 2018 8) | Neka je dat niz celih brojeva. Potrebno je formirati novi niz od ulaznog niza tako da bude zadovoljen uslov b[i] = a[i] / 2. Ulazni niz je alociran u procesu sa rangom 0 (master). Smatrati da je broj elemenata niza deljiv brojem procesa u MPI svetu. Koristeći MPI biblioteku: a) [5] Napisati deo koda master procesa koji ravnomerno raspoređuje ulazni niz svim procesima i prihvata rezultat rada nakon formiranja novog niza. b) [10] Ukoliko se koristi manager - worker model, napisati deo koda za master procesa kojim se jedan element niza šalje na obradu, prihvata i smešta rezultat obrade, a zatim šalje novi element na obradu, itd. | Dat je multiprocesorski sistem sa 4 identična procesora, koji koristi Firefly protokol za održavanje koherencije keš memorije. Svaka keš memorija ima po 2 ulaza, koji su veličine jedne reči. Preslikavanje je direktno. Početne vrednosti podataka su 0. Svaki upis uvećava vrednost izmenjenog podatka za 1. Na početku su sve keš memorije prazne. Data je sledeća sekvenca pristupa memoriji: Napisati stanja koherencije u svim procesorima i stanje memorije posle svake promene i skicirati opisani sistem u trenutku 8. [8 poena] Da li procesori pristupaju memoriji i kada? Za svaki pristup navesti razlog. [2 poena] ROK: chrome-extension://efaidnbmnnnibpcajpcglclefindmkaj/http://mups.etf.rs/ispiti/2013-2014/mps_februar_20132014.pdf | |||||||||||||||
77 | K3 2013 | Avg 2022 4) | ❌✅ Koliko bitova sadrži jedan ulaz kataloga za Diri NB protokol u sistemu sa n procesora? Opisati precizno akcije ovog protokola za read miss i write hit kod nekog procesora. Koji su nedostaci ovog protokola i kada pokazuje loše performanse? | K3 2023 2) | Avg 2023 4) | Kako se organizuje izvršavanje jezgra na grafičkim procesorima koji podržavaju CUDA tehnologiju? Na primeru VectorAddition jezgra, napisati izvršnu konfiguraciju i poziv jezgra prilikom izvršavanja jezgra za nizove dužine 1M elemenata. Smatrati da su nizovi devA, devB i devC već alocirani. __global__ void VectorAddition (int* devA, int* devB, int* devC, int n){ int idx = threadIdx.x + blockDim.x * blockIdx.x; if(idx < n) devC[idx] = devA[idx] + devB[idx]; } | K3 2018 6) | Napisati jezgro CUDA programa koje vrši prebrojavanje parnih i neparnih brojeva u zadatom nizu celih brojeva. Obradu niza vršiti po blokovima od 1024 elementa. Smatrati da u jednom bloku niti ima 256 niti. Jezgro treba da formira dva niza celih brojeva, od kojih prvi sadrži broj parnih, a drugi sadrži broj neparnih elemenata za svaki obrađeni blok pojedinačno. Smatrati da su svi nizovi alocirani unapred. Prilikom rešavanja zadatka koristiti deljenu memoriju za smeštanje međurezultata i voditi računa da se ostvari maksimalan paralelizam. __global__ void countKernel (int* array, int* evenCnt, int* oddCnt, int n); | ||||||||||||||||||
78 | K2p 2013 | K2 2020 1) | K2p 2014 3) | Avg 2023 3) | Avg 2021 3) | K2 2020 6) | Koristeći MPI biblioteku: a) [5] Napisati deo koda koji kreira i postavlja u MPI svet vektorski izvedeni tip koji omogućava efikasan prenos jedne kolone statičke matrice dimenzija 1024x768. b) [10] Koristeći realizovani izvedeni tip, napisati deo koda koji ravnomerno raspoređuje kolone matrice između svih procesa u MPI svetu. Smatrati da se na početku matrica nalazi u procesu sa rangom 0 i da je broj kolona deljiv ukupnim brojem procesa u MPI svetu. | Dat je multiprocesorski sistem sa 4 identična procesora, koji koristi Dragon protokol za održavanje koherencije keš memorije. Svaka keš memorija ima po 2 ulaza, koji su veličine jedne reči. Preslikavanje je direktno. Početne vrednosti podataka su 0. Svaki upis uvećava vrednost izmenjenog podatka za 1. Na početku su sve keš memorije prazne. Data je sledeća sekvenca pristupa memoriji: Napisati stanja koherencije u svim procesorima i stanje memorije posle svake promene i skicirati opisani sistem u trenutku 8. [10 poena] Koliko puta koji od procesora pristupa memoriji? Za svaki pristup navesti razlog. [3 poena] Koliki je Hit Rate za svaki od procesora (brojati i čitanje i upis, prikazati zbirno)? [2 poena] ROK: chrome-extension://efaidnbmnnnibpcajpcglclefindmkaj/http://mups.etf.rs/ispiti/2012-2013/si4mps_k2_popravni_20122013.pdff | ||||||||||||||||||
79 | K2 2013 | Napisati i objasniti model cene komunikacije. Objasniti model cene komunikacije. Na osnovu njega definisati indikatore performanse bitne sa aspekta procesora. U modelu cene komunikacije identifikovati komponente od kojih se sastoji vreme komunikacije. Koliko je vreme koje se može preklopiti sa drugim operacijama, a kolika je frekvencija izdavanja operacije? | K2 2023 1) | K2 2018 2) | Avg 2021 3) | Neka je data matrica dimenzija MxN koja sadrži podatke tipa int. Program treba da vrši određenu obradu nad kolonama matrice. Nakon obrade kolone, ona ima iste dimenzije, ali izmenjene elemente. Proces upravljač šalje neobrađene kolone matrice slobodnim procesima radnicima i prihvata rezultate od radnika, sve dok ima neobrađenih kolona. Procesi radnici prihvataju po jednu kolonu matrice, obrađuju ih i vraćaju nazad sve dok ih upravljač ne obavesti da više nema posla. Proces upravljač je implementiran funkcijom master() koja je data u prilogu. Koristeći rutine iz MPI biblioteke napisati funkciju slave() koja implementira proces radnika u opisanom manager – worker modelu obrade podataka. enum tags {ROW_INDEX_TAG = 11111, RESULT_TAG, END_TAG}; void readMatrix (int matrix[][N], int row, int col); printMatrix(matrix, rows, cols); void processColumn (int column[], int n); void master (int size) { int matrix[ROW][COL]; int rows, cols, i, colSent = 0, resultReceived = 0 ; MPI_Datatype columnType; MPI_Status status; scanf("%d%d", &rows, &cols); readMatrix(matrix, rows, cols); MPI_Bcast(&rows, 1, MPI_INT, MASTER, MPI_COMM_WORLD); MPI_Type_vector(rows, 1, COL, MPI_INT, &columnType); MPI_Type_commit(&columnType); for (i = 1; i < size; i++) { if (colSent < cols) { MPI_Send(&matrix[0][colSent], 1, columnType, i, colSent++, MPI_COMM_WORLD); } else { MPI_Send(&matrix[0][0], 1, columnType, i, END_TAG, MPI_COMM_WORLD); } } while (resultReceived < cols) { int colRecv; MPI_Recv(&colRecv, 1, MPI_INT, MPI_ANY_SOURCE, ROW_INDEX_TAG, MPI_COMM_WORLD, &status); MPI_Recv(&matrix[0][colRecv], 1, columnType, status.MPI_SOURCE, RESULT_TAG, MPI_COMM_WORLD, &status); resultReceived++; if (colSent < cols) { MPI_Send(&matrix[0][colSent], 1, columnType, status.MPI_SOURCE, colSent++, MPI_COMM_WORLD); } else { MPI_Send(&matrix[0][0], 1, columnType, status.MPI_SOURCE, END_TAG, MPI_COMM_WORLD); } } printMatrix(matrix, rows, cols); MPI_Type_free(&columnType); } | ✅ U čemu je razlika između blokirajućih i neblokirajućih rutina za point-to-point komunikaciju u MPI standardu? Da li rutine za slanje i prijem moraju biti istog tipa ili je moguće njihovo kombinovanje u tom smislu? | Dat je multiprocesorski sistem sa 4 identična procesora, koji koristi MOESI protokol za održavanje koherencije keš memorije. Svaka keš memorija ima po 2 ulaza, koji su veličine jedne reči. Preslikavanje je direktno. Početne vrednosti podataka su 0. Svaki upis uvećava vrednost izmenjenog podatka za 1. Na početku su sve keš memorije prazne. Data je sledeća sekvenca pristupa memoriji: Napisati stanja koherencije u svim procesorima i stanje memorije posle svake promene i skicirati opisani sistem u trenutku 8. [10 poena] Koliko puta koji od procesora pristupa memoriji? Za svaki pristup navesti razlog. [3 poena] Koliki je Hit Rate za svaki od procesora (brojati i čitanje i upis, prikazati zbirno)? [2 poena] ROK: chrome-extension://efaidnbmnnnibpcajpcglclefindmkaj/http://mups.etf.rs/ispiti/2012-2013/si4mps_k2_20122013.pdff | ||||||||||||||||||
80 | K1p 2013 | Jul 2015 1) | K1 2017 3) | Feb 2021 6) | K2 2023 1) | / | / | K1 2023 7) | ||||||||||||||||||
81 | K1 2013 | K1 2021 1) | K1 2023 2) | K1 2018 3) | K1 2023 4) | / | / | k1 2023 7) | ||||||||||||||||||
82 | Sep 2013 | K1 2021 3) | Feb 2023 2) | Avg 2022 4) | K2 2023 3) | Feb 2023 5) | Avg 2023 4) | / | K2 2020 6) | Koristeći CUDA tehnologiju, potrebno je napisati CUDA jezgro koje vrši određenu obradu nad matricom realnih brojeva. Jezgro treba da formira novu matricu, tako što svakom elementu na poziciji (i, j) dodeli vrednost aritmetičke sredine njegovih suseda u polaznoj matrici (maksimalno 8 suseda). Matrice su u memoriji predstavljene kao nizovi linearizovani po vrstama. Smatrati da su matrice već alocirane, a memorijski transferi već obavljeni. Prilikom rešavanja zadatka koristiti deljenu memoriju za smeštanje međurezultata i voditi računa da se ostvari maksimalan paralelizam. int ar_susedi (float *mat_in, float *mat_out, int m, int n); | Dat je multiprocesorski sistem sa 4 identična procesora, koji koristi Firefly protokol za održavanje koherencije keš memorije. Svaka keš memorija ima po 2 ulaza, koji su veličine jedne reči. Preslikavanje je direktno. Početne vrednosti podataka su 0. Svaki upis uvećava vrednost izmenjenog podatka za 1. Na početku su sve keš memorije prazne. Data je sledeća sekvenca pristupa memoriji: Napisati stanja koherencije u svim procesorima i stanje memorije posle svake promene i skicirati opisani sistem u trenutku 8. [8 poena] Da li procesori pristupaju memoriji i kada? Za svaki pristup navesti razlog. [2 poena] ROK: chrome-extension://efaidnbmnnnibpcajpcglclefindmkaj/http://mups.etf.rs/ispiti/2012-2013/mps_septembar_20122013.pdf | |||||||||||||||
83 | Okt 2013 | Jul 2014 1) | K1 2023 4) | Okt 2017 4) | Avg 2023 3) | K3 2023 2) | K3 2015 4) | / | ✅ Objasniti čemu služi i koja su ograničenja ugrađene funkcije __syncthreads() prilikom programiranja grafičkih procesora u CUDA tehnologiji? | Koristeći MPI biblioteku: a) [5] Napisati deo koda koji kreira i postavlja u MPI svet vektorski izvedeni tip koji omogućava efikasan prenos jedne kolone statičke matrice dimenzija 2048x1024. b) [10] Koristeći realizovani izvedeni tip, napisati deo koda master procesa koji ciklično šalje broj kolone i samu kolonu matrice jednom po jednom procesu radniku, dok god se ne pošalju sve kolone matrice. Matrica se na početku nalazi u procesu sa rangom 0. | Dat je multiprocesorski sistem sa 4 identična procesora, koji koristi MESI protokol za održavanje koherencije keš memorije. Svaka keš memorija ima po 2 ulaza, koji su veličine jedne reči. Preslikavanje je direktno. Početne vrednosti podataka su 0. Svaki upis uvećava vrednost izmenjenog podatka za 1. Na početku su sve keš memorije prazne. Data je sledeća sekvenca pristupa memoriji: Napisati stanja koherencije u svim procesorima i stanje memorije posle svake promene i skicirati opisani sistem u trenutku 8. [8 poena] Da li procesori pristupaju memoriji i kada? Za svaki pristup navesti razlog. [2 poena] ROK: chrome-extension://efaidnbmnnnibpcajpcglclefindmkaj/http://mups.etf.rs/ispiti/2012-2013/mps_oktobar_20122013.pdf | |||||||||||||||
84 | Jun 2013 | K1 2023 2) | K2 2023 1) | K2 2023 2) | Avg 2021 3) | K3 2023 1) | Avg 2023 4) | / | Čemu služi vektorski izvedeni tip kod MPI biblioteke? Napisati deo koda koji kreira i postavlja u MPI svet vektorski izvedeni tip koji omogućava efikasan prenos svakog stotog i sto prvog elementa niza celih brojeva veličine 10K elemenata. | Za potrebe jedne banke, potrebno je napisati program koji simulira prebrojavanje novca u vreći korišćenjem grafičkog procesora. Vreća se predstavlja nizom celih brojeva. Pretpostaviti da se u vreći nalaze samo novčanice u apoenima od 10, 50, 100, 500 i 1000 dinara. Program treba da izračuna ukupnu prebrojanu svotu novca, kao i broj novčanica u vreći za svaki pojedinačni apoen. Koristeći CUDA tehnologiju, napisati jezgro koje vrši obradu jednog bloka niza koji predstavlja vreću sa novcem. Smatrati da su svi nizovi već alocirani, a memorijski transferi već obavljeni. Prilikom rešavanja zadatka koristiti deljenu memoriju za smeštanje međurezultata i voditi računa da se ostvari maksimalan paralelizam. Napisati deo koda na centralnom procesoru kojim se napisano jezgro poziva. __global__ void prebroji (int* vreca, int n, int* broj_po_apoenima); | Dat je multiprocesorski sistem sa 4 identična procesora, koji koristi MSI protokol za održavanje koherencije keš memorije. Svaka keš memorija ima po 2 ulaza, koji su veličine jedne reči. Preslikavanje je direktno. Početne vrednosti podataka su 0. Svaki upis uvećava vrednost izmenjenog podatka za 1. Na početku su sve keš memorije prazne. Data je sledeća sekvenca pristupa memoriji: Napisati stanja koherencije u svim procesorima i stanje memorije posle svake promene i skicirati opisani sistem u trenutku 8. [8 poena] Da li procesori pristupaju memoriji i kada? Za svaki pristup navesti razlog. [2 poena] ROK: chrome-extension://efaidnbmnnnibpcajpcglclefindmkaj/http://mups.etf.rs/ispiti/2012-2013/mps_jun_20122013.pdf | |||||||||||||||
85 | Jul 2013 | K2 2013 1) | Avg 2023 2) | K2 2023 1) | Feb 2022 4) | K3 2023 2) | Nacrtati i objasniti arhitekturu hijerarhijskog sistema organizovanog oko dva nivoa magistrala. Objasniti kako se obavljaju upisi i čitanja u ovakvom sistemu. | Da li svi procesi u MPI svetu moraju učestvovati u kolektivnim operacijama? Na primeru celobrojnog niza od 1K elemenata, prikazati deo koda koji vrši ravnomernu podelu elemenata niza svim aktivnim procesima u MPI svetu od ukupno 4 procesa. Svu komunikaciju sprovesti kolektivnim operacijama. | K3 2018 6) | Neka su zadate sledeće definicije na programskom jeziku C: typedef struct { ... } Arguments; void* work (void* arg) { Obj* obj; ... ; pthread_exit(obj); } a) [7] Koristeći POSIX standard za niti, napisati deo koda koji kreira NUM_THREADS niti nad funkcijom work i prosledi im objekat koji sadrži argumente opisane strukturom Arguments b) [8] Ukoliko je objekat obj u funkciji work dinamički alociran, napisati deo koda unutar glavne niti koji čeka na završetak svake pojedinačne niti i prihvata rezultat koji je vraćen iz funkcije work. Rezultat svake pojedinačne niti smestiti na odgovarajuće mesto u niz rezultujućih objekata. | Dat je multiprocesorski sistem sa 4 identična procesora, koji koristi MOESI protokol za održavanje koherencije keš memorije. Svaka keš memorija ima po 2 ulaza, koji su veličine jedne reči. Preslikavanje je direktno. Početne vrednosti podataka su 0. Svaki upis uvećava vrednost izmenjenog podatka za 1. Na početku su sve keš memorije prazne. Data je sledeća sekvenca pristupa memoriji: Napisati stanja koherencije u svim procesorima i stanje memorije posle svake promene i skicirati opisani sistem u trenutku 8. [8 poena] Da li procesori pristupaju memoriji i kada? Za svaki pristup navesti razlog. [2 poena] ROK: chrome-extension://efaidnbmnnnibpcajpcglclefindmkaj/http://mups.etf.rs/ispiti/2012-2013/mps_jul_20122013.pdf ❌✅ | |||||||||||||||
86 | Feb 2013 | K1 2021 3) | Okt 2009 2) | K2 2022 3) | Avg 2023 5) | Feb 2023 4) | K3 2021 2) | / | Feb 2023 7) | Za potrebe jedne banke, potrebno je napisati program koji simulira prebrojavanje novca u vreći korišćenjem MPI biblioteke. Vreća se predstavlja nizom celih brojeva. Pretpostaviti da se u vreći nalaze samo novčanice u apoenima od 10, 50, 100, 500 i 1000 dinara. Program treba da ispiše ukupnu prebrojanu svotu novca, kao i prebrojanu svotu novca i broj novčanica u vreći za svaki pojedinačni apoen. Proces gospodar učitava sve neophodne podatke, nakon čega ravnopravno učestvuje u poslu sa ostalim procesima i ispisuje rezultate prebrojavanja. Procesi radnici prihvataju odgovarajući deo posla i vraćaju rezultat procesu gospodaru. Smatrati da je broj elemenata niza celobrojni umnožak broja procesa. Koristeći rutine iz MPI biblioteke napisati funkciju master() koja implementira proces gospodar sa opisanim funkcionalnostima. Za raspodelu posla i prikupljanje rezultata koristiti kolektivne operacije. Smatrati da funkcija za prebrojavanje novca već postoji. int prebroji_novac (int* vreca, int n, int* broj_po_apoenima); | Dat je multiprocesorski sistem sa 4 identična procesora, koji koristi Firefly protokol za održavanje koherencije keš memorije. Svaka keš memorija ima po 2 ulaza, koji su veličine jedne reči. Preslikavanje je direktno. Početne vrednosti podataka su 0. Svaki upis uvećava vrednost izmenjenog podatka za 1. Na početku su sve keš memorije prazne. Data je sledeća sekvenca pristupa memoriji: Napisati stanja koherencije u svim procesorima i stanje memorije posle svake promene i skicirati opisani sistem u trenutku 8. [8 poena] Da li procesori pristupaju memoriji i kada? Za svaki pristup navesti razlog. [2 poena] ROK: chrome-extension://efaidnbmnnnibpcajpcglclefindmkaj/http://mups.etf.rs/ispiti/2012-2013/mps_februar_20122013.pdf | |||||||||||||||
87 | K3 2012 | K2 2023 2) | Avg 2023 5) | Feb 2023 5) | Okt 2013 6) | Napisati jezgro CUDA programa koje vrši određenu obradu nad nizom tačaka u prostoru. Svaka tačka je opisana strukturom koja sadrži tri realna polja (x, y i z koordinate tačke). Jezgro treba da formira niz realnih brojeva koji sadrži rastojanja između svake tačke u nizu tačaka i zadate referentne tačke. typedef struct {float x, y, z} Point; __global__ void distance (Point *points, float *dist, Point ref); Napisati izvršnu konfiguraciju i poziv jezgra prilikom izvršavanja jezgra za niz dužine 1M elemenata. Da li je navedena organizacija niza tačaka najpovoljnija sa stanovišta efikasnog pristupa memoriji? Kako bi bilo dobro organizovati tu strukturu podataka za efikasniji pristup memoriji? | Napisati program na programskom jeziku C ili C++ koji vrši određenu obradu nad nizom tačaka u prostoru. Svaka tačka je opisana strukturom koja sadrži tri realna polja (x, y i z koordinate tačke). Program treba da formira i ispiše dva niza tačaka, od kojih će prvi niz sadržati one tačke koje se nalaze unutar, a drugi niz sadržati one tačke koje se nalaze izvan zamišljene sfere zadate poluprečnikom sa centrom u koordinatnom početku. Obradu paralelizovati i realizovati korišćenjem MPI, uz podelu procesa po grupama. Proces sa rangom 0 (gospodar) treba da učita podatke i učestvuje u obradi. Procesi sa parnim rangom treba da formiraju niz onih tačaka koje se nalaze unutar zadate sfere, a procesi sa neparnim rangom niz onih tačaka koje se nalaze izvan zadate sfere. Procesi sa rangom 0 unutar svake grupe treba da ispišu rezultujuće nizove i njihovu dužinu. Pretpostaviti da je broj procesa uvek veći od 1. Ako korisnik unese broj elemenata niza koji nije celobrojni umnožak polovine broja procesa, prekinuti program. | |||||||||||||||||||
88 | K2p 2012 | K2 2013 1) | K2 2023 1) | K2p 2014 3) | Avg 2021 3) | Dat je multiprocesorski sistem sa 4 identična procesora, koji koristi MSI protokol za održavanje koherencije keš memorije. Svaka keš memorija ima po 2 ulaza, koji su veličine jedne reči. Preslikavanje je asocijativno. Početne vrednosti podataka su 0. Svaki upis uvećava vrednost izmenjenog podatka za 1. Na početku su sve keš memorije prazne. Data je sledeća sekvenca pristupa memoriji: 5.1. Napisati stanja koherencije u svim procesorima posle svake promene. [8 poena] 5.2. Koliko puta koji od procesora pristupa memoriji? Za svaki pristup navesti razlog. [4 poena] 5.3. Koliki je Hit Rate za svaki od procesora (brojati i čitanje i upis, prikazati zbirno)? [4 poena] 5.4. Skicirati opisani sistem posle trenutka 10. ROK: chrome-extension://efaidnbmnnnibpcajpcglclefindmkaj/http://mups.etf.rs/ispiti/2011-2012/si4mps_k2_popravni_20112012.pdf | Napisati program na programskom jeziku C ili C++ koji vrši određenu obradu nad nizom tačaka u prostoru. Svaka tačka je opisana strukturom koja sadrži tri realna polja (x, y i z koordinate tačke). Program treba da formira i ispiše niz realnih brojeva koji sadrži rastojanja između svake tačke u nizu tačaka i zadate referentne tačke. Obradu paralelizovati i ostvariti korišćenjem MPI. Proces sa rangom 0 (gospodar) obavlja svu komunikaciju sa korisnikom i ravnopravno učestvuje u obradi sa ostalim procesima. Za slanje delova niza tačaka koristiti odgovarajući izvedeni tip podataka. Pretpostaviti da je broj procesa uvek veći od 1. Ako korisnik unese broj elemenata niza koji nije celobrojni umnožak broja procesa, prekinuti program. | |||||||||||||||||||
89 | K2 2012 | Jul 2023 2) | K2 2022 1) | Diskutovati prednosti i nedostatke primene trenutnog (WT) i odloženog upisa (WB). U kojim protokolima se primenjuje prvi, a u kojima drugi način? | Avg 2023 3) | ROK: chrome-extension://efaidnbmnnnibpcajpcglclefindmkaj/http ://mups.etf.rs/ispiti/2011-2012/si4mps_k2_20112012.pdf | Napisati program na programskom jeziku C ili C++ koji vrši određenu obradu nad matricom celih brojeva maksimalnih dimenzija 3648x2736. Program treba da formira i ispiše niz celih brojeva na osnovu elemenata zadate matrice. Jedan element niza se formira primenom XOR operacije nad svim elementima jedne kolone matrice. Obradu paralelizovati i ostvariti korišćenjem MPI. Proces sa rangom 0 (gospodar) obavlja svu komunikaciju sa korisnikom, vrši raspodelu poslova i prihvata rezultate obrade. Ostali procesi primaju po jednu kolonu matrice, vrše zadatu obradu, vraćaju rezultat gospodaru i ponavaljaju opisani postupak sve dok ih gospodar obavesti da više nema posla. Za slanje jedne kolone matrice koristiti odgovarajući izvedeni tip podataka. Pretpostaviti da je broj procesa uvek veći od 1. | |||||||||||||||||||
90 | K1p 2012 | K1 2023 2) | Jul 2015 1) | K1 2023 4) | K2 2023 1) | ROK: chrome-extension://efaidnbmnnnibpcajpcglclefindmkaj/http://mups.etf.rs/ispiti/2011-2012/si4mps_k1_popravni_20112012.pdf | K1 2023 7) | |||||||||||||||||||
91 | K1 2012 | K1 2021 3) | K1p 2014 2) | Feb 2023 2) | Avg 2023 2) | / | K1 2023 7) | |||||||||||||||||||
92 | Jun 2012 | Jul 2015 1) | ✅ Objasniti Data-parallel programski model i karakteristike odgovarajućih arhitektura. | Avg 2022 4) | Avg 2021 3) | Feb 2023 5) | Okt 2013 6) | K3 2018 6) | / | Sastaviti MPI program na jeziku C ili C++ koji pronalazi kolone matrice sa maksimalnom i minimalnom sumom elemenata. Proces sa rangom 0 u MPI svetu treba da obavlja svu komunikaciju sa korisnikom (unos matrice i ispis rezultata) i ne učestvuje u obradi. Procese treba podeliti u dve grupe koje sadrže isti broj procesa. Prva grupa treba da pronađe kolone sa maksimalnom sumom elemenata, a druga grupa kolone sa minimalnom sumom elemenata. Svaki proces treba da obradi jednak broj kolona matrice. Proces sa rangom 0 u svakoj grupi treba da prikupi rezultate za svoju grupu i pošalje ih procesu sa rangom 0 u MPI svetu. Ako broj kolona matrice nije odgovarajući broju procesa u MPI svetu, prekinuti program. Za slanje kolone matrice koristiti izvedene tipove. | ||||||||||||||||
93 | Feb 2012 | Jan 2012 1) | K2 2020 1) | Sep 2015 4) | K2 2023 3) | K3 2023 1) | Avg 2023 4) | K3 2018 6) | / | Sastaviti program na jeziku C ili C++ koji vrši množenje matrice zadatim vektorom. Program najpre treba da pročita dimenzije i elemente matrice realnih brojeva, kao i dužinu i elemente vektora realnih brjeva, a zatim proveri da li se matrica i vektor mogu pomnožiti. Nakon izvršenog množenja, ispisati rezultujući vektor. Obradu paralelizovati i realizovati korišćenjem MPI. Proces sa rangom 0 u MPI svetu treba da obavlja svu komunikaciju sa korisnikom, izvrši raspodelu posla i učestvuje u obradi. Ako broj vrsta matrice nije umnožak broja procesa u MPI svetu, prekinuti program. | ||||||||||||||||
94 | K3 2011 | Feb 2023 4) | Feb 2022 4) | Avg 2022 4) | K3 2021 2) | Objasniti model izvršavanja CUDA programa. Kako se izvršava CUDA jezgro i od čega to zavisi? | Napisati program na programskom jeziku C ili C++ koji pronalazi vrstu i kolonu matrice sa najvećom sumom elemenata. Obradu paralelizovati i realizovati korišćenjem MPI, uz podelu procesa po grupama. Procesi sa parnim rangom treba da obrađuju vrste, a procesi sa neparnim rangom kolone matrice. Svaki proces treba da obradi jednu vrstu ili kolonu matrice. Proces sa rangom 0 (gospodar) treba da učita podatke i ne treba da učestvuje u obradi, već da po završenoj obradi prikupi rezultate obrade od procesa sa rangom 0 u svakoj od namenskih grupa i ispiše rezultate. Ako korisnik zada broj procesa manji od potrebnog, prekinuti program. Ako korisnik zada broj procesa veći od potrebnog, prekobrojne procese rasporediti u posebnu grupu, u kojoj će svaki proces samo ispisati poruku da je bez posla. Prilikom prenosa vrsta i kolona matrice koristiti izvedene tipove. | |||||||||||||||||||
95 | K2p 2011 | K2 2020 1) | Objasniti kako i kada se javlja problem koherencije keš memorija. Koje su osnovne strategije kod protokola za održavanje koherencije? | Avg 2023 3) | K2p 2014 3) | ROK: chrome-extension://efaidnbmnnnibpcajpcglclefindmkaj/http://mups.etf.rs/ispiti/2010-2011/si4mps_k2_popravni_20102011.pdf | ROK: chrome-extension://efaidnbmnnnibpcajpcglclefindmkaj/http://mups.etf.rs/ispiti/2010-2011/si4mps_k2_popravni_20102011.pdf | |||||||||||||||||||
96 | K2 2011 | Jul 2013 1) | Avg 2023 2) | K2p 2014 3) | K2 2023 3) | ROK: chrome-extension://efaidnbmnnnibpcajpcglclefindmkaj/http://mups.etf.rs/ispiti/2010-2011/si4mps_k2_20102011.pdf | Napisati program na programskom jeziku C ili C++ koji simulira prebrojavanje novca u vreći. Vreća se predstavlja nizom celih brojeva. Pretpostaviti da se u vreći nalaze samo novčanice u apoenima od 10, 50, 100, 500 i 1000 dinara. Program treba da ispiše ukupnu prebrojanu svotu novca, kao i prebrojanu svotu novca i broj novčanica u vreći za svaki pojedinačni apoen. Obradu paralelizovati i ostvariti korišćenjem MPI. Proces sa rangom 0 učitava dimenzije, a potom i elemente niza celih brojeva sa standardnog ulaza, nakon čega ravnopravno učestvuje u poslu sa ostalim procesima i ispisuje rezultate prebrojavanja. Pretpostaviti da je broj procesa uvek veći od 1. Ako korisnik unese broj elemenata niza koji nije celobrojni umnožak broja procesa, prekinuti program. | |||||||||||||||||||
97 | K1p 2011 | Jul 2015 1) | K1 2017 3) | K1 2018 3) | K2 2023 1) | / | K1 2023 7) | |||||||||||||||||||
98 | K1 2011 | K1 2023 1) | Jun 2020 1) | K1 2023 4) | K1p 2013 3) | / | K1 2023 7) | |||||||||||||||||||
99 | Jun 2011 | Jun 2020 1) | K2 2023 1) | ✅ Diskutovati prednosti i nedostatke povećanja dužine bloka u multiprocesorskim sistemima. | K2 2023 3) | Jun 2018 4) | Avg 2023 4) | / | ROK: chrome-extension://efaidnbmnnnibpcajpcglclefindmkaj/http://mups.etf.rs/ispiti/2010-2011/mps_jun_20102011.pdf | Sastaviti MPI program na jeziku C ili C++ koji vrši cirkularno pomeranje niza celih brojeva za određeni broj mesta ulevo ili udesno. Proces sa rangom 0 u MPI svetu treba da obavlja svu komunikaciju sa korisnikom (unos podataka i ispis rezultata) i ravnopravno učestvuje u poslu sa ostalim procesima. Ako broj elemenata niza nije odgovarajući broju procesa u MPI svetu, prekinuti program | ||||||||||||||||
100 | Jul 2011 | Jan 2012 1) | ✅ Ukratko opisati programski model slanja poruka. | Sep 2015 4) | Avg 2023 3) | K3 2023 1) | Okt 2013 6) | / | ROK: chrome-extension://efaidnbmnnnibpcajpcglclefindmkaj/http://mups.etf.rs/ispiti/2010-2011/mps_jul_20102011.pdf | Sastaviti MPI program na jeziku C ili C++ koji vrši zamenu kolona matrice, tako da prva postane poslednja, druga pretposlednja i tako redom. Proces sa rangom 0 (gospodar) u MPI svetu treba da obavlja svu komunikaciju sa korisnikom (unos matrice i ispis rezultata) i upravlja drugim procesima. Ostali procesi treba da dobiju po jednu vrstu matrice, izvrše obradu, vrate rezultat gospodaru, a zatim ponavljaju opisani postupak sve dok ih gospodar ne obavesti da nema više posla. Proces koji prvi pošalje rezultat prvi treba da dobije novu vrstu za obradu. Za prenos jedne vrste matrice koristiti izvedene tipove podataka. |