NEW
Font size
WorksheetsPOATE TRECEM SI NOI
Total questions: 51
Worksheet time: 26mins
Care este numarul necesar de bariere pentru calculul sumelor prefix in paralel, pe o arhitectura MIMD?
3
1
0
2
In cazul cautarii binare paralele folosind P thread-uri, complexitatea pentru citirea valorii de cautat x intr-un sistem SIMD - CREW este
O(P)
O(logP)
O(1)
O(PlogP)
MPI_Recv este un apel blocant / MPI_Send NU este un apel blocant in conditii normale
A/A
A/F
F/F
F/A
Ce complexitate are Odd Even Transposition Sort pentru n=p (unde n este numarul de elemente de sortat si p este numarul de thread-uri)?
O(N)
O(N^2/P)
O(NlogN)
O(logN)
In Java, pentru a astepta terminarea unui thread t creat in thread-ul principal, folosim
t.run()
t.modify()
t.join()
t.plm()
Ce face o bariera?
Forteaza re-activarea unui thread blocat pe o resursa
Blocheaza thread-urile o perioada scurta de timp
Blocheaza thread-ul curent pana ce un numar dat de thread-uri ajunge la un apel al acesteia
Separa codul in bucati
In standardul MPI, MPI_COMM_WORLD este:
functie
comunicator
biblioteca
proces
Problema comis voiajorului foloseste codificarea:
permutare
cu numere reale
binara
cu lista de reguli
Care este complexitatea Parallel Merge Sort, pentru P=N ?
O(N^2)
O(NlogN)
O(logN)
O(N)
Algoritmul cu mesaje de sondaj cu ecou:
nu conteaza topologia
poate fi folosit doar pe topologii arbore si nu poate fi generalizat
poate fi folosit doar pe topologii inel
poate fi folosit pe topologii arbore, dar si generalizat pe topologii cu grafuri
Intr-un ExecutorService, shutdown() permite task-urilor active sa-si termine executia / shutdownNow() opreste imediat executia task-urilor active
A/A
A/F
F/A
F/F
Care din variantele specificate nu este un tip predefinit de date in MPI?
MP_LM
MPI_FLOAT
MPI_VECTOR
MPI_LONG_DOUBLE
Problema de sincronizare East-West Bridge poate fi rezolvata folosind idea de rezolvare de la:
Problema Barbierului
Problema Filozofilor
Producer-Consumer
Problema Cititori-Scriitori
În detecția terminării folosind tehnica jetoanelor, cazul general, este necesară găsirea apriori a unui:
ciclu Hamiltonian pe graf
ciclu care include toate arcele grafului
ciclu care include toate nodurile grafului
diametrul grafului
Cum se poate delimita o zona critica?
Folosind Lock/Unlock asupra unui mutex
Cu bagheta lui Gandalf
Folosind apelul functiei sleep
Folosind bariera
Consideram un sistem cu n procesoare pe care dorim sa realizam in paralel suma elementelor unui vector ce contine n elemente. Suma
elementelor va fi la sfarsit la nivelul ultimului proces. Care este regula ca la un anumit pas (j) un proces sa lucreze? (j porneste cu valoarea 1)
rank_proces - pow(2,j) < 1
rank_proces mod pow(2,j) == 0
rank_proces - pow(2,j) >= 1
rank_proces - pow(2,j-1) >= 1
Care este eficienta pentru sortarea OETS in cazul rularii pe P procesoare? Se considera N dimensiunea vectorului de sortat
log(N)
log(P)
logN/N
log(N)/P
In distributie, conform cu modelul Foster, timpul total se calculeaza ca:
suma timpului de comunicare intra-procesor, de calcul si idle pe fiecare proces
suma timpului de comunicare inter-procesor, de calcul si idle pe fiecare proces
suma timpului de calcul si de comunicare inter-procesor pe fiecare proces
suma timpului de comunicare, de calcul si idle pe fiecare proces
În implementarea unui semafor distribuit, de ce aveți nevoie să folosiți operații de broadcast?
Pentru că avem nevoie să descoperim prin relația de cauzalitate valorile de ceas logic curente pentru a ordona folosind aceleași momente operațiile asupra semaforului
Pentru că unele mesaje pot fi distorsionate de atacatori malițioși
Pentru că avem nevoie să asigurăm participarea tuturor proceselor distribuite
Pentru că unele mesaje se pot pierde în tranzit și avem nevoie de siguranța în comunicație
Care dintre următoarele NU este un interactive consistency conditions pentru problema generarilor bizantini
Dacă Generalul comandant este loial, atunci toți Locotenenții loiali se supun aceluiași ordin
Toți Locotenenții loiali se supun aceluiași ordin
Toți Locotenenții se supun aceluiași ordin
Dacă Generalul comandant este loial, atunci fiecare Locotenent loial se supune ordinului Generalului comandant
La initierea unei bariere in pthread este obligatoriu sa se specifice:
Numarul de thread-uri ce vor astepta la bariera
ID-ul unui thread master ce va fi primul deblocat din apelul pthread_barrier_wait()
Cate procesoare exista pe masina locala
Specificul organizației care dezvoltă soluția tehnologicăTimpul minim pentru care orice thread va fi blocat la apelul pthread_barrier_wait()
Intr-un sistem e-commerce (e.g., Amazon, e-Bay, etc), care sunt opțiunile pe care NU e nevoie să le considerăm când alegem între consistență
și disponibilitate?
Tipuri de date diferite (e.g., shopping cart, billing, product, etc.)
Specificul organizației care dezvoltă soluția tehnologică
Tipuri diferite de operații (e.g., query, purchase, etc.)
Tipuri diferite de servicii (e.g., distributed lock, DNS, etc.)
In cazul Blockchain, consistența și implicit corectitudinea tranzacțiilor sunt asigurate de:
strong consistency - vânzătorul trebuie să fie sigur că întreaga rețea confirmă o tranzacție
operația de creare de blocuri este costisitoare și nodurile sunt obligate să comute pe blockchainul cel mai lung (blockchain fork) anulând astfel eventuale tranzacții false
eventual consistency - după un timp nodurile vor actualiza oricum informația
Vanzatorul trebuie sa fie sigur ca intreaga retea o confirma
strong consistency - cine înregistrează o tranzacție trebuie să ateste că cel puțin 51% dintre noduri au confirmat adăugarea acesteia
Ce face functia pthread_join()?
Blocheaza thread-ul curent in asteprarea thread-ului dat ca argument
Opreste thread-ul dat ca argument
Opreste toate thread-urile
Intrerupe thread-ul dat ca argument
Care din urmatoarele este un efect al unei bariere?
Un thread care ajunge la o bariera trece intotdeauna imediat mai departe
Mai multe thread-uri nu pot rula simultan o bucata de cod delimitata de doua bariere
Operatiile de dupa bariera devin atomice
Tot codul de dinainte de bariera se executa de catre toate thread-urile inainte de tot codul de dupa bariera
Care este timpul de executie in cazul descopunerii distribuite uni-dimensionale pe
randuri a problemeii lui Floyd de aflare a drumui minim? Se considera o matrice NxN si P
procese.
t_msg - este timpul de transmitere a unui mesaj (o linie din matrice) catre urmatorul
proces destinatie
for [k = 0 to N-1]
for [i = local_i_start to local_i_end]
for [j = 0 to N-1]
I[i,j]k+1 = min(I[i,j]k, I[i,k]k + I[k,j]k)
t_iteratieN^3/P + NlogP*t_msg
t_iteratieN^3/P + NlogP
t_iteratieN^3/P + Nt_msg
t_iteratieN^3/P + logPt_msg
Care este complexitatea de difuzare a unei valori intr-un sistem SIMD - EREW cu P procesoare?
O(P)
O(logP)
1
O(PlogP)
Care este complexitatea pentru a calcula(efficient) in paralel distanta din fiecare punct al unei lise pana la sfarsitul acesteia? Lista are N elemente
O(logN)
O(logP)
O(N^2)
O(NlogN)
Care este complexitatea pentru algoritmul OETS in cazul rularii pe P thread-uri.
O(N^2/P)
O(N^2)
O(N)
O(NlogN)
Care este complexitatea multiplicarii de matrice folosind P thread-uri
O(N^3/P)
O(N^3)
O(P/N^3)
O(P)
Complexitatea algoritmului Parallel Merge Sort in cazul rularii pe P thread-uri este:
O(P)
O(P^2)
O(log(N^2))
O(logN)
Complexitatea algoritmului Parallel Binary Search in cazul rularii pe P thread-uri este:
O(P)
O(logP N)
O(log(N^2))
O(logN)
Complexitatea de timp a algoritmului inel este:
O(N)
O(D)
O(P)
O(K)
Complexitatea de timp algoritmului arbore este:
O(N)
O(D)
O(N^2)
O(P)
Complexitatea de timp a algoritmului ecou este:
O(N)
O(D)
O(N^2)
O(NlogN)
Complexitatea de timp a algoritmului fazelor este:
O(2D)
O(D)
O(N^2)
O(N * D^2)
Complexitatea de timp a algoritmului de alegere a liderului Tree este:
O(D)
O(N^2)
O(NlogN)
O(K)
Complexitatea de timp a algoritmului de alegere a liderului LeLann este:
O(N^2)
O(N)
O(D)
O(PLM)
Complexitatea de timp a algoritmului de alegere a liderului LeLann-Chang-Robert este:
O(N)
O(D)
O(N^2)
O(N^3/3)
Complexitatea de timp a algoritmului de alegere a liderului Sinclair este:
O(N)
O(D)
O(N^2)
O(NlogN)
Complexitatea de timp a algoritmului pulsatiilor este:
O(D)
O(N)
O(P)
O(K)
Complexitatea de timp a algoritmului de sondaje cu mesaje este:
= NR mesaje
= NR mesaje + 1
O(N)
pic apd-ul
Care este numarul de mesaje pentru algoritmul INEL:
N
N^2
2N
2N-3
In cazul algoritmului ARBORE, numarul de mesaje transmise:
N
3N
4N
N^3
Pentru algoritmul Lider-TREE numarul de mesaje:
4N-4
4N
N-1
N
In cazul algoritmului de alegere LIDER-LELANN, numarul de mesaje:
N^2
2N
3N
2N-1
Numarul de mesaje in cazul algoritmului LIDER-SINCLAIR:
N
N^5
N*logN
logN
SPEEDUP ul in cazul algoritmului OETS este:
PlogN/N
PlogN
logN
logN^2
SPEEDUP ul in cazul algoritmului SHEAR SORT:
P/log(sqrt(N))
log(sqrt(N))
N
-1
Pentru MATRIX MULTIPLY, speedup ul este:
P
1
D
PlogN
Complexitatea temporala a difuzarii paralele a unei valori, pentru P=N/2 ?
O(log2N)
O(N^2)
O(N)
O(N*log2N)
