Semestrálna skúška 2023/2024 - Predtermin
Př. 1
Tipsport crcw - XOR, NAND, AND
Př. 2
PRAM model - opisat ho, nakreslit obrazok
Př. 3
Kauzalni broadcast + relace kauzality
Př. 4
Euler pro počet následovníků + popis
Př. 5
CLA
Př. 6
Meakawův algoritmus - opisat kvorum a na obrazku znazornit zalomenu verziu kvor pre 12 procesov. takto ukazte zistenie kvor pre 2 procesy
Př. 7
OCCAM - implementujte proceduru IDK, ktora na vstupe dostava channely pre input, clk, a outputy OUT_LEFT a OUT_RIGHT. Ked dostane na inpute cislo, da ho do vnutornej nekonecnej queue. Ked dostane na clk lubovolnu vec, tak outputne na OUTL alebo OUTR prvy prvok queue. ukazatel na prvy prvok sa potom posunie, treba to robit rucne. tento clk vzdy outputuje striedavo (ako v PMS uplne prvy proces)
Př. 8
MPI - mate k dispozicii reduce, broadcast, rank procesu, a pocet vsetkych prvkov. kazdy proces ma premennu value, v ktorej ma nejaku hodnotu. napiste kod, v ktorom si kazdy proces vypocita value - (priemer vsetkych hodnot), a vysledok da na output vo formate rank: vysledok
Semestrálna skúška 2023/2024 - RADNY skupina B
Př. 1
PRAM “tipovacka” (6b)
a) časova složitost: XOR pro EREW, CREW, common CRCW
b) časova složitost: počet sudych čísel pro EREW, CREW, common CRCW
c) cena: NAND pro EREW, CREW, common CRCW
Př. 2
Popište architekturu procesů s velkým kódovým slovem (VLIW). Popište možné konflikty a způsob jejich předcházení, resp. řeešní. Ilustrujte patřičnými obárázky. (Vlevo okynko nadepsane “princip, konflikty”, vpravo nadepsane “obrazky”) (9b)
Př. 3
Pro problém čtenáři písaři uveďte kódy, kterými lze řešit pomocí obecného semaforu tak, aby nedocházelo ke konfliktům ani úváznutí. Řešením má být varianta, kdy čtenáři mají přednost. Neřešte případné hladovění písařů. Z algoritmu by měl být zřejmý princip vzájemného vyloučení při vstupu do kritické sekce. (9b)
Př. 4
Demonstrujte operace nad stromem s použitím funkce sumy sufixů SuffixsS(hrany, ohodnocení). Pokud máte výsledek Eulerova průchodu stromem ve struktuře Etour, pokud jste schopni provést podmíněný příkaz “if e je dopredna then” podle toho, zdali je hrana je či není dopředná, jak lze spočíst pořadí vrcholů (pro zobrazení preor(v)→N) při průchodu pre-order? Uveďte algoritmus, krátký slovní popis pincipu a časovou složitost celého výpočtu. (Zvlast misto na alg, zvlast misto na popis, zvlast mistecko pro casovou slozitost. (9b)
Př. 5
Randezvouz smth smth novy priklad - viz obrazek. (10b)
[obrazek: image1]
[obrazek: image2]
-1
[obrazek: image3]
+1
Př. 6
Vyplnit vysledek po 6 krocich enumeration sortu zapojeny v řadě (viz dalsi obrazek). (9b)
Př. 7
PI kalkul cca: (new v) (a(v).a(v).0 | b’z. … .0 + b(x). … .0 )| b(x). … .0 | b’f.c’a.0) Najit alespon 4 ruzne redukce aby uz neslo dale redukovat. (9b)
Př. 8
MPI: vypsat soucet prvku vetsich nez prumer, dispozici broadcast a reduce. (9b)
Semestrálna skúška 2023/2024 - RADNY skupina A
Př. 1
PRAM Tipsport (OR, je posloupnost monotonni?, je v poli cisel nula?)
Př. 2
Popsat princip zřetězených procesorů
Př. 3
Popsat monitor (včetně signal a wait) + nákres
Př. 4
K dispozici funkce na výpočet sumy sufixu a příkaz “if e je dopredna then do…” - popsat algoritmus pro výpočet úrovně vrcholu (pseudokód + slovní popis + časová složitost)
Př. 5
Rendezvous kktina, nový příklad
Př. 6
Pipeline Merge Sort - stav po 10 krocích
Př. 7
Pi kalkul
Př. 8
MPI - proces má v proměnné value svoji hodnotu, pomocí Reduce a Bcast (definice funkcí byly v zadání) implementovat následující: chceme vytisknout součet lichých hodnot * součet sudých hodnot
Semestrálna skúška 2023/2024 - RADNY skupina B
Př. 1
PRAM “tipovacka” (6b)
a) časova složitost: XOR pro EREW, CREW, common CRCW
b) časova složitost: počet sudych čísel pro EREW, CREW, common CRCW
c) cena: NAND pro EREW, CREW, common CRCW
Př. 2
Popiště architekturu procesů s velkým kódovým slovem (VLIW). Popiště možné konflikty a způsob jejich předcházení, resp. řeešní. Ilustrujte patřičnými obárázky. (Vlevo okynko nadepsane “princip, konflikty”, vpravo nadepsane “obrazky”) (9b)
Př. 3
Pro problém čtenáři písaři uvěďtě kódy, kterými lze řešit pomocí obecného semaforu tak, aby nedocházelo ke konfliktům ani úváznutí. Řešením má být varianta, kdy čtenáři mají přednost. Neřešte případné hladovění písařů. Z algoritmu by měl být zřejmý princip vzájemného vyloučení při vstupu do kritické sekce. (9b)
Př. 4
Demonstrujte operace nad stromem s použitím funkce sumy sufixů SuffixsS(hrany, ohodnocení). Pokud máte výsledek Eulerova průchodu stromem ve struktuře Etour, pokud jste schopni provést podmíněný příkaz “if e je dopredna then” podle toho, zdali je hrana je či není dopředná, jak lze spočíst pořadí vrcholů (pro zobrazení preor(v)→N) při průchodu pre-order? Uveďte algoritmus, krátký slovní popis pincipu a časovou složitost celého výpočtu. (Zvlast misto na alg, zvlast misto na popis, zvlast mistecko pro casovou slozitost. (9b)
Př. 5
Randezvouz smth smth novy priklad - viz obrazek. (10b)
[obrazek: image1]
[obrazek: image2]
Př. 6
Vyplnit vysledek po 6 krocich enumeration sortu zapojeny v řadě (viz dalsi obrazek). (9b)
[obrazek: image4]
Př. 7
PI kalkul cca: (new v) (a(v).a(v).0 | b’z. … .0 + b(x). … .0 )| b(x). … .0 | b’f.c’a.0) Najit alespon 4 ruzne redukce aby uz neslo dale redukovat. (9b)
Př. 8
MPI: vypsat soucet prvku vetsich nez prumer, dispozici broadcast a reduce. (9b)
Semestrálna skúška 2023/2024 - 1. opravny
Př. 1
6b: PRAM (EREW, CREW, COMMON CRCW): cena zoradit sekvenciu, cena XOR, casova zlozitost AND
Př. 2
9b: a) FIFO broadcast send, recv algoritmus, b) definovat relaciu kauzality
Př. 3
9b: testandset riesenie kritickej sekcie - kod plus popis
Př. 4
9b: algoritmus 4 citacov princip fungovania plus nakreslit 2 obrazky, v jednom sa detekovalo ukoncenie a v druhom nie
Př. 5
10b: RA synchronizácia vstupov do CS, 4 procesy, synchronny cas, plus pocitanie logickeho casu jednotlivych udalosti, sprava ma latency 3 takty, kriticka sekcia trva 1 takt, na vstupe a vystupe nastanu 2 abstraktne udalosti, priority procesov: 1 ma najvacsiu prioritu, v case 6 taktov zaziada proces 4, v case 7 taktov zaziada o CS proces 3, naznacit komunikaciu sipkami, napisat ku kazdej udalosti logicky cas (podla Lamporta), vypisat aj logicky cas kazdeho procesu po poslednej vykonanej udalosti
Př. 6
9b: random mating (8 uzlov, vyberat F/M pseudonahodne tak, aby sa jumping phase skoncil do 4 iteracii, nezabudnut aj reconstruction phase)
Př. 7
9b: pi kalkul (vypisat tie 3 vyrazy, na ktore to mozno redukovat)
Př. 8
9b: MPI najst druhy najmensi prvok v log. case, mozno pouzit len MPI_Bcast, MPI_Reduce