Arhitecturi Paralele - Note de curs

Podcast

Play an AI-generated podcast conversation about this lesson

Questions and Answers

Conform metodei 3 descrise în secțiunea de sortare, când începe un procesor să transmită spre stânga?

Imediat ce primește o valoare din dreapta. (correct)
Imediat ce primește o valoare din stânga.
Imediat după ce numerele sunt sortate.
Imediat ce toate valorile sunt transmise la stânga

Ce complexitate temporală are metoda de sortare descrisă ca `Metoda 4` în text?

3N-3 pași
4N-3 pași
3N-2 pași (correct)
4N-2 pași

În contextul algoritmilor de sortare discutați, ce acțiune inițiază un procesor din `Metoda 4`, după finalizarea primei faze?

Așteaptă până când toate procesele sunt finalizate
Începe să primească date din dreapta
Începe să transmită date în dreapta
Începe să transmită date în stânga, după ce nu mai primește valori din stânga (correct)

Care dintre următoarele este o cerință specifică impusă de implementarea metodelor de sortare 1 si 2, spre deosebire de metodele 3 si 4?

Cunoașterea poziției procesoarelor în vector și contorizarea valorilor inspectate. (C) Signup and view all the answers

În exemplul fazei a doua a Metodei 4, ce indică o tranziție de la un rând la următorul?

Trecerea valorii din dreapta la ieșirea din stânga. (B) Signup and view all the answers

În algoritmul de sortare prezentat, ce se întâmplă cu valorile după ce au fost procesate prin toate cele 8 etape (S1-S8) ale pipeline-ului?

Valorile sunt stocate în ordine crescătoare și sunt scoase prin celula din stânga. (C) Signup and view all the answers

Câte etape individuale (S1, S2, S3, etc.) sunt utilizate în pipeline-ul de sortare prezentat în exemplu, pentru a sorta o listă de 8 numere?

8 (A) Signup and view all the answers

Conform textului, cât durează prima fază a algoritmului de sortare, pentru N valori?

$2N - 1$ pași (B) Signup and view all the answers

În contextul algoritmului de sortare prin pipeline, care este rolul fiecărei etape (S1, S2, etc.)?

Fiecare etapă compară și ordonează două valori. (A) Signup and view all the answers

În algoritmul de sortare prezentat, care este scopul fazei a doua?

Extragerea valorilor sortate prin celula din stânga. (C) Signup and view all the answers

Cum este modificată poziția unei valori în timpul procesului de sortare cu pipeline?

Valorile sunt comparate și, dacă este necesar, mutate la stânga, proces continuând în etapele următoare. (C) Signup and view all the answers

Care dintre următoarele afirmații descrie cel mai bine procesul de sortare prezentat?

Un tip de sortare în rețea unde valorile trec printr-o serie de etape de comparații și permutări simultane. (B) Signup and view all the answers

În contextul algoritmului de sortare prin pipeline, ce se întâmplă dacă există valori duplicate în lista inițială?

Valorile duplicate sunt sortate corect, menținându-se toate ocurențele lor. (D) Signup and view all the answers

Ce model de paralelism este descris n contextul 'CPU Instruction pipeline'?

Paralelism pipeline (A) Signup and view all the answers

Ntr-un pipeline, un pas specific poate fi executat de:

Un thread, un proces sau un element hardware. (C) Signup and view all the answers

N contextul execuiei sarcinilor fr pipeline, cum se calculeaz timpul total de execuie?

$total_execution_time = task_execution_time * number_of_tasks$ (B) Signup and view all the answers

Ce reprezint 'step_execution_time' n contextul unui pipeline ideal?

Timpul necesar executrii unei singure etape din pipeline. (C) Signup and view all the answers

Care este avantajul principal al utilizrii unui pipeline n procesarea sarcinilor multiple?

Permite executarea simultan a diferitelor etape pentru diferite sarcini. (C) Signup and view all the answers

Cum se modific timpul total de execuie ideal ntr-un pipeline dup ce se finalizeaz un numr de sarcini egal cu numrul de etape?

$total_execution_time = number_of_tasks * step_execution_time$ (B) Signup and view all the answers

Ce se ntmpl cu execuia unei sarcini ntr-un pipeline ideal, odat ce acesta este complet ocupat?

O sarcin se termina la intervalul unei singure etape, dup nceperea pipeline-ului. (D) Signup and view all the answers

Ce tip de paralelism este cel mai potrivit pentru a prelucra instruciunile unui procesor?

Paralelism pipeline (D) Signup and view all the answers

Care dintre urmtoarele nu este un exemplu de aplicaie n care se poate utiliza paralelism pipeline?

Tranzacii bancare izolate (B) Signup and view all the answers

N comparaie cu execuia secvenial, cum afecteaz un pipeline timpul total de execuie al mai multor sarcini?

l reduce semnificativ. (A) Signup and view all the answers

Care este gradul maxim al unui polinom dat de formula generală $P(x) = \sum_{i=0}^{n} a_i x^i$ ?

Este egal cu n. (B) Signup and view all the answers

În procesul de calcul al unui polinom folosind pipeline, ce reprezintă `S1`, `S2`, `S3` etc.?

Etapele de calcul în pipeline. (C) Signup and view all the answers

Dat polinomul $P(x) = 1 + 8x - 4x^3 + x^4$, care este coeficientul termenului $x^2$?

0 (C) Signup and view all the answers

În contextul problemei damelor, ce restricție impune regula 'Nu mai mult de o damă pe linie'?

Dama nu poate ocupa aceeași linie cu o altă damă. (A) Signup and view all the answers

În problema damelor, ce conflict apare dacă două dame se află pe aceeași diagonală?

Conflict diagonal. (C) Signup and view all the answers

Care dintre următoarele nu este o regulă de bază în problema damelor?

Pot fi oricâte dame pe tablă. (B) Signup and view all the answers

Ce reprezintă numerele 1, 3, 0, 2 în contextul soluției problemei damelor prezentată sub forma `1 3 0 2`?

Indicii coloanelor, ordonate în funcție de linii. (B) Signup and view all the answers

Cum se evaluează un polinom $P(x)$ folosind metoda pipeline, în comparație cu metoda tradițională?

Metoda pipeline efectuează operațiile secvențial într-un mod mai eficient. (B) Signup and view all the answers

Ce semnificație are notația $x_{ij}$ in contextul evaluarii unui polinom prin algoritmul pipeline?

Reprezintă termenul $x$ ridicat la puterea $j$ în etapa $i$. (A) Signup and view all the answers

În problema damelor, dacă avem o soluție marcată `0 0`, ce tip de conflict semnalează această configurație?

Conflict pe linie. (B) Signup and view all the answers

Care este scopul principal al algoritmului pipeline în calculul polinomului?

Să îmbunătățească viteza de calcul prin execuție secvențială. (D) Signup and view all the answers

De ce este relevantă aplicația problemei damelor în contextul informaticii?

Reprezintă o problemă clasică de backtracking și explorare a spațiului stărilor. (B) Signup and view all the answers

Cum este utilizată noțiunea $n$ în definiția generală $P(x) = \sum_{i=0}^{n} a_i x^i$ a unui polinom?

Ca numărul de termeni din sumă (B) Signup and view all the answers

În algoritmul pipeline pentru evaluarea unui polinom, ce rol au etapele $S1$, $S2$, $S3$, etc. în procesul de calcul?

Procesează iterativ calculele, progresiv. (D) Signup and view all the answers

Ce reprezintă o soluție `1 3 0 2` în problema damelor?

O succesiune a coloanelor unde sunt așezate damele, pe linii, de la linia 0 la linia 3. (B) Signup and view all the answers

Flashcards

Sortare

Un proces care ordonează elementele dintr-o listă într-o anumită ordine, crescătoare sau descrescătoare.

Sortare cu pipeline

Metoda de sortare care folosește pipeline-ul pentru a muta valorile ordonate în fața listei.

Faza 1

Primul pas în sortarea cu pipeline, unde cele mai mici valori sunt mutate în fața listei un element la un moment dat.

Sortarea cu pipeline: faza a doua

Un proces care ordonează elementele dintr-o listă de la stânga la dreapta, un element la un moment dat.