Paralelné a distribuované systémy - ÚINF/PDS

Záverečný prezenčný písomný test v utorok 26. 5. 2020 od 9:00 ~~v P11~~ v P08.
Na dištančnú skúšku sa zatiaľ nikto neprihlásil.
Ďalší termín prezenčnej skúšky určujem predbežne na 9. 6. 2020 9:00 (ale po dohode je možné ho zmeniť)
Termín dištančnej skúšky bude potom 10. 6. (na technických detailoch sa dohodnem s prihlásenými)
Ďalší termín prezenčného testu a ústnej skúšky určujem na 18. 6. 2020 o 10:00 v P17 .

Odporúčaná literatúra a ďalšie zdroje informácií
Pravidlá hodnotenia
Projekty

Zadania domácich úloh - séria A (doc, pdf), séria B (doc, pdf), séria C (doc, pdf), séria D (doc, pdf),
séria E (doc, pdf), séria F (doc, pdf), séria G (doc, pdf), séria H (doc, pdf), séria I (doc, pdf), séria J (doc, pdf)

	Prebraté a plánované témy
10.2.2020	Základné problémy konkurentného, paralelného a distribuovaného výpočtového modelu. Problémy konkurencie procesov vo viacúlohových systémoch. Problém vzájomného vylúčenia (mutual exclusion). Riešenie s aktívnym a pasívnym čakaním. Kritická sekcia a jej ošetrenie mutexami. Synchronizácia procesov, bariéry, monitor. Problémy uviaznutia a vyhladovania a ich riešenie. Slajdy z prednášky. Pre osvieženie poznatkov z OS a z konkuretného programovania - prejdite kapitoly 6, 7 a 8 (str. 257 - 347) z Operating System Concepts (v intranete) Úlohy na precvičenie séria A (doc, pdf) - odovzdať do 17. 2. 2020, 14:25
17.2.2020	Paralelný výpočtový model PRAM. Alternatívy prístupu do spoločnej pamäte (EREW, CREW, CRCW). Časová zložitosť paralelného výpočtu v modeli PRAM. Charakteristiky paralelného algoritmu - zrýchlenie (speedup), efektivita, cena. Výpočet charakteristík pre problém sčítania n prvkov, škálovanie. Paralelný algoritmus na vyhľadávanie, nájdenie maximálneho prvku. Paralelný algoritmus na výpočet prefixových súčtov. Amdahlov zákon. Gustafsonov zákon. Slajdy z prednášky. Joseph Jájá: An Introduction to Parallel Algorithms (1. kapitola v Intranete) Preštudovať kapitoly: 1.1, 1.2, 1.3., 1.4. Úlohy na precvičenie séria B (doc, pdf) - odovzdať do 24. 2. 2020, 14:25
24.2.2020 HVRL	Tutoriál - Programovanie GPU - CUDA (OpenCL). Materiály k tutoriálu + Prezentácia .
2.3.2020 HVRL	Tutoriál - Programovanie GPU - CUDA - 2.časť Bude opäť v Laboratóriu haptiky a virtuálnej reality (pri sekretariáte ÚINF) Dvojlogaritmické stromy. Slajdy z prednášky - aktualizované. Úlohy na precvičenie séria C (doc, pdf) - odovzdať do 9. 3. 2020, 14:25
9.3.2020	Work-time zápis paralelných algoritmov. optimalita. Optimálny paralelný algoritmus na výpočet prefixových súčtov. Paralelný ranking a súvisiace postupy. Paralelné vyhľadávanie, rank, paralelné zlučovanie. Paralelné usporiadanie pomocou paralelného zlučovania (MergeSort), optimalizácia. ( Optimálny rank s paralelným vyhľadávaním s p procesormi v konštantnom čase. loglog(n) optimálne zlučovanie ) - nebude na skúške Slajdy z prednášky. Joseph Jájá: IPA (kapitoly 1.5, 1.6, 2.1 a 2.4 (kap. 4 - MergeSort) v Intranete) Úlohy na precvičenie séria D (doc, pdf) - odovzdať do 16. 3. 2020, 14:25
16.3.2020	Dištančné vzdelávanie bude prebiehať v prostredí MS Teams v triede PDS2020. Svoje otázky môžte zadávať do kanála Chat, materiály k prednáškam budú v kanáli Všeobecné v záložke Súbory/Učebné materiály. Budem aktualizovať aj túto stranku, ak by ste mali s MS Teams problémy ... Úlohy na precvičenie séria E (doc, pdf) - odovzdať do 23. 3. 2020, 14:25 do systému MS Teams
23.3.2020 14:25-17:00 PDS2020	Bitonické postupnosti, bitonické zlučovanie, MergeSort s bitonickým zlučovaním. Even-odd zlučovanie, 0-1 princíp. Sortovacie siete. Pointer jumping a paralelný prefix v lese. Slajdy z prednášky. Joseph Jájá: IPA (kapitola 2.2, kapitola 4. Searching, merging, and sorting) Úlohy na precvičenie séria F (doc, pdf) - odovzdať do 30. 3. 2020, 14:25 do systému MS Teams V úlohe 1 môžte predpokladať, že všetky prvky poľa M sú navzájom rôzne.
30.3.2020 14:25-17:00 PDS2020	Model distribuovaného výpočtu, komunikačné kanály. Synchrónne a asynchrónne odovzdávanie správ, časová a komunikačná zložitosť. Komunikácia v kruhovej sieti, voľba koordinátora. Slajdy z prednášky M. Raynal: Distributed Algorithms for Message-Passing Systems (v intranete) kapitola 4. Leader Election Algorithms Úlohy na precvičenie séria G (doc, pdf) - odovzdať do 6. 4. 2020, 14:25 do systému MS Teams
6.4.2020 14:25-17:00 PDS2020	Tutoriál MPI. Úlohy k tutoriálu sú na konci materiálov. Riešenia posielajte do PDS2020 do 16. 4. 2020 23:59. Za úplné riešenie môžete od RKB dostať max 5 bodov. Na konci materiálov je tiež ponuka projektov z MPI aj s obsadenosťou.
20.4.2020 14:25-17:00 PDS2020	Šírenie správy v stromovej sieti záplavou (flood). Komunikácia vlnou (wave), výzva (join) a odpoveď (echo) spätnou vlnou. Problémy komunikácie v neacyklickej sieti. Zisťovanie topológie distribuovaným algoritmom v acyklickej a v neacyklickej sieti. Hľadanie najkratších ciest a vzdialeností medzi uzlami. Slajdy z prednášky M. Raynal: Distributed Algorithms for Message-Passing Systems (v intranete) kapitola 1. Network Traversal a 2. Distributed Graph Algorithms (2.1 Distributed Shortest Path) Úlohy na precvičenie séria H (doc, pdf) - odovzdať do 27. 4. 2020, 14:25 do systému MS Teams
27.4.2020 14:25-17:00 PDS2020	Intervalové a prefixové smerovanie. Slajdy z prednášky Synchronizácia času v distribuovaných systémoch. Riešenie logickými a fyzickými hodinami, koordinácia, intervalový čas. Aktuálny obraz systému (snapshot). Slajdy z prednášky Z knihy M. Raynal: DA 7.1 Logical Time in Asynchronous Distributed Systems, 6. Concept of Global State, Úlohy na precvičenie séria I (doc, pdf) - odovzdať do 4. 5. 2020, 14:25 do systému MS Teams
4.5.2020 14:25-17:00 PDS2020	Ošetrenie vzájomného vylúčenia v distribuovanom systéme. Možnosti detekcie a prevencie uviaznutia (wound-wait, wait-die) v distribuovanom systéme. Detekcia ukončenia výpočtu. Slajdy z prednášky Z knihy M. Raynal: DA 10. Permission-Based Mutual Exclusion Algorithms 14 Distributed termination detection, 15 Distributed deadlock detection Úlohy na precvičenie séria J (doc, pdf) - odovzdať do 11. 5. 2020, 14:25 do systému MS Teams
11.5.2020 14:25-17:00 PDS2020	Tolerancia chýb v distribuovanom systéme. Spoľahlivé výpočty v prostredí s chybami. Možnosti dohody (konsenzu) v nespoľahlivom prostredí. Byzantínske chyby Distribuovaný konsenzus - systém Paxos, Raft. Navigácia objektov, PageRank, hashing. Sociálne a P2P siete, Chord, Pastry, Kademlia, BitTorent. Slajdy z prednášky Lamport, Shostak, Pease: The Byzantine Generals Problem Video Practical Byzantine Fault Tolerance Lamport - Paxos, Paxos Made Simple Ongaro, Ousterhout - Raft Pastry

Odporúčaná literatúra :

M. Raynal: Concurrent Programming: Algorithms, Principles, and Foundations (prístupná v intranete)
M. Raynal: Distributed Algorithms for Message-Passing Systems (prístupná v intranete)

Joseph Jájá: An Introduction to Parallel Algorithms, Addison-Wesley Prof. Pub., 1992

A.S. Tanenbaum, M. van Steen: Distributed Systems, CreateSpace, 2017
Gerard Tel: Introduction to Distributed Algorithms, CUP 2001 (Google-books)
Sukumar Ghosh: Distributed Systems and Algorithms (Second Edition), CRC Press 2014
P. Sanders, K. Mehlhorn, M. Dietzfelbinger, R. Dementiev: Sequential and Parallel Algorithms and Data Structures (prístupná v intranete)

Ďalšie zdroje na Sieti :

V. K. Garg: Elements of Distributed Computing (distrib. algoritmy v Jave)

Projekty
Vyberte si jednu z tém tutoriálov a vyžiadajte e-mailom zadanie od príslušného prednášateľa.
CUDA - ladislav.mikes at gmail.com

paralelné preskúšanie všetkých možostí (reverzia hash funkcií, faktorizácia ...)
využitie knižničných funkcií (cublas - riešenie sústav rovníc, cufft - spracovanie signálu) na riešenie problémov v matematike, fyzike .. diplomovej práci
vlastná implementácia FFT, neurónovej siete, genetického/pravdepodobnostného algoritmu, algoritmov počítačového videnia - raytracing, z-buffer
detailná implementácia jednoduchšieho problému s analýzou výkonu, testami, použitím profileru (2D DCT kosínusová transformácia použitím cufft, nájdenie k-teho najväčšieho prvku ...)

Riešenia odovzdávajte vo forme, dohodnutej so zadávateľom. Pokiaľ odovzdáte riešenie pred termínom, je možné ho po konzultácii so zadávateľom vylepšiť a získať tak väčší počet bodov.
Termín odvzdania riešenia je 15. 5. 2020, 23:59.
Obhajobu je potrebné dohodnúť najlepšie v zápočtovom týždni, aby ste mali zapísané body v prípade skúšky v predtermíne.
Pokiaľ potrebujete uzavrieť štúdium v skoršom termíne, je potrebné odovzdať projekt pred konaním záverečnej skúšky.

Kritériá hodnotenia - bodované aktivity:

(25 bodov) úspešné riešenie projektu
Projekty budú zadávané individuálne a budú orientované na praktické zručnosti.
(cca 40 bodov) úspešné riešenie domácich zadaní
Opisované riešenia bez udania zdroja nebudú hodnotené a môžu byť posudzované ako porušenie pravidiel čestného správania.
(20 bodov) polsemestrálny test
(30 bodov) záverečný test
(25 bodov) záverečné ústne preskúšanie
Za záverečné preskúšanie je potrebné získať aspoň 15 bodov.

Celkove je možné získať spolu aspoň 140 bodov. Na absolvovanie so ziskom kreditov je potrebných aspoň 70 bodov (z čoho aspoň 15 za záverečné preskúšanie). Stupňom D budeme hodnotiť zisk aspoň 80 bodov, C aspoň 90 bodov, B aspoň 100 bodov a A aspoň 110 bodov.

Otázky na ústne preskúšanie (z každej časti jedna) :

*Problém uviaznutia a jeho riešenie v sekvenčnom, paralelnom a distribuovanom prostredí.
*Modely paralelných výpočtových prostredí, varianty PRAM modelu vzhľadom k prístupu k zdieľanej pamäti. Časová zložitosť, zrýchlenie, cena výpočtu, efektívnosť, škálovateľnosť (príklad - paralelné sčítanie).
*Work-time zápis paralelných algoritmov, čas výpočtu, práca, optimalita (príklad - hľadanie maxima).
*Paralelný algoritmus pre výpočet prefixových súčtov - odhad zložitosti, zrýchlenia, optimálnosť, nerekurzívny prístup, možnosti použitia.
*Amdahlov a Gustafsonov zákon pre odhad reálnej časovej zložitosti výsledku paralelizácie.
*Paralelné výpočty v konštantnom čase (jedinečný/prvý výskyt v postupnosti, monotónnosť)
*Paralelný ranking, zlučovanie usporiadaných postupností v logaritmickom čase.
*Bitonické postupnosti, bitonické triedenie a použitie pre usporiadanie ľubovoľnej postupnosti.
*Even-odd triedenie, 0-1 princíp a jeho využitie pre dôkaz správnosti algoritmu.
*Paralelné hľadanie koreňov v lese v logaritmickom čase.

*Model distribuovaného výpočtu, synchrónne a asynchrónne odovzdávanie správ, časová a komunikačná zložitosť. Šírenie správ v sieti algoritmom záplavy (príkad - hľadanie koordinátora).
*Hľadanie koordinátora v kruhovej (jednosmernej a obojsmernej) sieti. Časová a komunikačná zložitosť.
*Algoritmy vlny, prehľadávanie do šírky v acyklickej a v neacyklickej sieti (príklad).
*Zisťovanie najkratšej cesty ku koordinátorovi pre vážené prepojenia v synchrónnej sieti.
*Intervalové a prefixové smerovanie - základné algoritmické princípy.
*Synchronizácia času v distribuovaných systémoch, riešenie logickými a fyzickými hodinami.
*Riešenie problému vzájomného vylúčenia v distribuovanom prostredí (Ricart-Agrawala, Maekawa).
*Vytvorenie konzistentnej snímky systému v silne súvislej synchrónnej distribuovanej sieti (Chandy-Lamport).
*Detekcia ukončenia (Dijkstra-Scholten).
*Problém dosiahnutia zhody (konsenzu) v synchrónnych systémoch s fatálnymi a byzantínskymi chybami.