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

Prednášky budú prebiehať v P/03 utorok od 13:30 v P4, cvičenia v stredu od 11:00 v P3.
Prosím, vyplňte aj dotazník s hodnotením vyučovania.
Záverečný písomný test bude prezenčne v utorok 31. 5. 2022 o 10:00 v P12 . (prihláste sa v AIS)
Ústne preskúšanie bude potom popoludní.
Ak máte záujem o ďalšie termíny, ozvite sa, prosím, e-mailom týždeň vopred.
Otázky na ústne preskúšanie.
Odporúčaná literatúra a ďalšie zdroje informácií
Pravidlá hodnotenia
Zadania domácich úloh - séria A, séria B, séria C, séria D, séria E, séria F, séria G,
séria H, séria I, séria J, séria K, séria L, séria M
  Prebraté a plánované témy
15.2.2022 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šenia s aktívnym a pasívnym čakaním.
Kritická sekcia a jej ošetrenie mutexami. Lamportov algoritmus.
Semafory a ich využitie pri riešení synchronizačných úloh.
Úlohy typu producer-consumer, readers-writers.
Synchronizácia procesov, bariéry, monitor.
Slajdy z prednášky.
Úlohy na precvičenie séria A - odovzdať do 22. 2. 2022, 15:20 v systéme MS Teams PDS2022
22.2.2022 Problémy uviaznutia a vyhladovania a ich riešenie.
Modely paralelných výpočtov. Booleovské obvody, systolické polia.
Paralelný výpočtový model PRAM.
Alternatívy prístupu do spoločnej pamäte (EREW, CREW, CRCW).
Slajdy z prednášky.
Kapitola 8 z Operating System Concepts (v intranete)
Joseph Jájá: An Introduction to Parallel Algorithms - kapitoly 1.1, 1.2, 1.3.
Úlohy na precvičenie séria B - odovzdať do 1. 3. 2022, 15:20 v systéme MS Teams PDS2022
1.3.2022 Časová zložitosť paralelného výpočtu v modeli PRAM.
Charakteristiky paralelného algoritmu - zrýchlenie (speedup), efektivita, cena.
Problém sčítania n prvkov, binárna redukcia.
Výpočet charakteristík pre problém sčítania n prvkov, škálovanie.
Paralelný algoritmus na výpočet prefixových súčtov.
Slajdy z prednášky.
Úlohy na precvičenie séria C - odovzdať do 8. 3. 2022, 13:30 v systéme MS Teams PDS2022
8.3.2022
13:30 P4 		Paralelný algoritmus na vyhľadávanie maximálneho prvku.
Odmocninová redukcia, dvojlogaritmický strom.
Zovšeobecnenie a zefektívnenie.
Amdahlov zákon. Gustafsonov zákon.
Slajdy z prednášky.
Joseph Jájá: An Introduction to Parallel Algorithms - kapitoly 1.1, 1.2, 1.3., 1.4
Úlohy na precvičenie séria D - odovzdať do 15. 3. 2022, 13:30 v systéme MS Teams PDS2022
15.3.2022 Work-time zápis paralelných algoritmov. optimalita.
Optimálny paralelný algoritmus na výpočet prefixových súčtov.
Joseph Jájá: An Introduction to Parallel Algorithms - kapitoly 1.5, 1.6, 2.1
Cormen, Leiserson, Rivest : Algorithms for Parallel Computers
Slajdy z prednášky.
Úlohy na precvičenie séria E - odovzdať do 22. 3. 2022, 13:30 v systéme MS Teams PDS2022
22.3.2022
13:30
P04		 Paralelné vyhľadávanie, rank, paralelné zlučovanie.
Paralelné usporiadanie pomocou paralelného zlučovania (MergeSort), optimalizácia.
Slajdy z prednášky.
Joseph Jájá: An Introduction to Parallel Algorithms - kapitola 2.4 (resp. kap. 4 - MergeSort)
Úlohy na precvičenie séria F - odovzdať do 29. 3. 2022, 13:30 v systéme MS Teams PDS2022
29.3.2022
13:30
P04		 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.
Úlohy na precvičenie séria G - odovzdať do 5. 4. 2022, 13:30 v systéme MS Teams PDS2022
30.3.2022
11:00 P03		 Polsemestrálny písomný test v P03 (60 min).
5.4.2022
13:30
P04		 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.
M. Raynal: Distributed Algorithms for Message-Passing Systems (v intranete)
Slajdy z prednášky
Úlohy na precvičenie séria H - odovzdať do 12. 4. 2022, 13:30 v systéme MS Teams PDS2022
12.4.2022 Voľba koordinátora.
Šírenie správy v sieti záplavou (flood).
M. Raynal: Distributed Algorithms ... (v intranete) kapitola 4. Leader Election Algorithms
Slajdy z prednášky
Úlohy na precvičenie séria I - odovzdať do 26. 4. 2022, 13:30 v systéme MS Teams PDS2022
26.4.2022
13:30
P04		 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.
Minimálna kostra ohodnoteného grafu. Najkratšie cesty.
Smerovacie algoritmy. Intervalové a prefixové smerovanie.
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 J - odovzdať do 3. 5. 2022, 13:30 v Teams PDS2022
3.5.2022 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
M. Raynal: Distributed Algorithms for Message-Passing Systems (v intranete)
7.1 Logical Time in Asynchronous Distributed Systems
A. D. Kshemkalyani, M. Singhal: Distributed Computing ( v intranete )
Chapters 3. Logical time 4. Global state and snapshot recording algorithms
Úlohy na precvičenie séria K - odovzdať do 10. 5. 2022, 13:30 v Teams PDS2022
10.5.2022 Ošetrenie vzájomného vylúčenia v distribuovanom systéme.
Problém uviaznutia 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
M. Raynal: Distributed Algorithms for Message-Passing Systems (v intranete)
14 Distributed termination detection, 15 Distributed deadlock detection
A. D. Kshemkalyani, M. Singhal: Distributed Computing ( v intranete )
Chapters 7. Termination detection 10. Deadlock detection
Úlohy na precvičenie séria L - odovzdať do 17. 5. 2022, 13:30 v Teams PDS2022
17.5.2022 Tolerancia chýb v distribuovanom systéme.
Spoľahlivé výpočty v prostredí s chybami.
Možnosti dosiahnutia dohody a zhody (konsenzu) v nespoľahlivom prostredí.
Byzantínske chyby
Distribuovaný konsenzus - systém Paxos, Raft.
Slajdy z prednášky
Lamport, Shostak, Pease: The Byzantine Generals Problem Practical Byzantine Fault Tolerance
Lamport - Paxos, Paxos Made Simple
Ongaro, Ousterhout - Raft

Úlohy na opakovanie séria M - odovzdať do 30. 5. 2022, 23:59 v Teams PDS2022

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)
A. D. Kshemkalyani, M. Singhal: Distributed Computing ( slajdy, v intranete )

R. Trobec et al.: Introduction to Parallel Computing (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 : Architektúra akcelerátora NVIDIA Tesla A100
Dátové centrá Google

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


Kritériá hodnotenia - bodované aktivity:

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

V písomnom teste sa predpokladá orientácia, znalosti a schopnosti riešiť úlohy z druhej časti semestra (distribuované algoritmy a systémy).

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

*Vzájomné vylúčenie s pasívnym a aktívnym čakaním - príklady riešenia v konkurentnom prostredí.
*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.

*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 dohody a zhody (konsenzu) v synchrónnych systémoch s fatálnymi a byzantínskymi chybami.