PRL Final Exam

2025-2026-radny-predikce-a

3 min čtení

2025/2026 - řádný termín - cvičná predikce A

Metadata

PoleHodnota
Typcvičné zadání
Cílpredikce pro řádný termín 2025/2026
Doporučený limit120-150 minut
Body70
Jistotavysoká strukturou, střední konkrétními variantami

Témata

Proč tahle varianta

Tohle je nejpravděpodobnější řádný-termínový tvar: PRAM první, MPI poslední, uprostřed architektura, synchronizace, Euler, distribuovaný algoritmus, řazení a formální jazyk. Je blízká řádným termínům term-1-radny-b a term-1-radny-c, ale bere v úvahu i témata z term-0-pretermin-a.

Zadání

  1. PRAM tipovačka, 6 b. Pro modely EREW PRAM, CREW PRAM a common CRCW PRAM určete časovou složitost t(n) a cenu c(n) optimálního algoritmu pro:

    • zjištění, zda posloupnost n bitů obsahuje alespoň jednu jedničku;
    • zjištění, zda jsou všechny prvky posloupnosti stejné;
    • výpočet XOR všech prvků posloupnosti.

  2. VLIW, 9 b. Popište architekturu VLIW procesoru. Vysvětlete, jak se plánuje paralelismus instrukcí, jaké vznikají konflikty a jak se jim předchází. Připojte jednoduchý nákres dlouhého instrukčního slova a funkčních jednotek.

  3. Čtenáři/písaři, 9 b. Navrhněte řešení problému čtenářů a písařů pomocí obecných semaforů tak, aby čtenáři měli přednost. Uveďte inicializaci semaforů, sdílené proměnné a pseudokód pro čtenáře i písaře. Neřešte hladovění písařů.

  4. Euler tour + suffix sums, 9 b. Máte výsledek Eulerova průchodu stromem Etour a pro každou orientovanou hranu umíte zjistit, zda je dopředná. Popište algoritmus pro výpočet preorder čísla preorder(v) pro každý vrchol. Uveďte ohodnocení hran, použití prefix/suffix sum a časovou složitost.

  5. Ricart-Agrawala, 10 b. Čtyři procesy P1..P4 žádají o vstup do kritické sekce. Proces P4 žádá v čase 6, proces P2 v čase 7. Zpráva má latenci 3 takty, kritická sekce trvá 1 takt. Priority při shodném Lamportově čase jsou P1 > P2 > P3 > P4. Nakreslete komunikaci request/reply, doplňte Lamportovy časy událostí a určete pořadí vstupu do kritické sekce.

  6. Enumeration Sort, 9 b. Uvažujte zapojení čtyř procesorů P1..P4 s registry X, Y, C, Z. Vstupní posloupnost 7, 2, 7, 5, 1, 4 je zpracovávaná zprava. Procesory řadí vzestupně a duplicity řeší stabilně podle pořadí vstupu. Zapište obsah registrů po 6. kroku a stručně popište význam registru C.

  7. Pi-kalkul, 9 b. Pro zadaný proces najděte alespoň 4 různé možné redukce do stavu, kde už nelze dále redukovat. U každé redukce uveďte komunikační pár, provedenou substituci a výsledný výraz. Pokud v některém stavu platí pozorování, zapište jej.

(a(x).x<d>.0 + b(y).c<y>.0)
|
(a<c>.0 + c(z).z<e>.0)
|
(new k)(c(k).k<f>.0 | k(u).0)
  1. MPI, 10 b. Každý proces má hodnotu value, svůj rank a počet procesů numprocs. K dispozici jsou zjednodušené funkce MPI_Reduce(send, recv, operace, root) a MPI_Bcast(adresa, root). Napište algoritmus v C++/MPI s logaritmickou komunikační složitostí, který na procesu 0 vypíše součet všech prvků větších než průměr všech hodnot.

Kontrola po dopsání

Graf

Příchozí odkazy