| Prebraté a plánované témy |
12.2.2025 P3 15:20 |
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. Slajdy z prednášky. kapitoly 6 a 7 (str. 257 - 316) z Operating System Concepts (v intranete) Úlohy na precvičenie séria A - odovzdať do 17. 2. 2025, 14:25 |
17.2.2025 P3 14:25 |
Synchronizácia procesov, bariéry, monitor. Úlohy typu producer-consumer, readers-writers. Problémy uviaznutia a vyhladovania a ich riešenie. Kapitola 8 z Operating System Concepts (v intranete) Slajdy z prednášky (konkurentné programovanie). Modely paralelných výpočtov. Booleovské obvody, systolické polia. Slajdy z prednášky (paralelné modely na hw úrovni). Úlohy na precvičenie séria B - odovzdať do 26. 2. 2025, 15:20 |
26.2.2025 15:20 |
Paralelný výpočtový model PRAM. Alternatívy prístupu do spoločnej pamäte (EREW, CREW, CRCW). 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. Joseph Jájá: An Introduction to Parallel Algorithms - kapitoly 1.3., 1.4., 2.1. Slajdy z prednášky. Úlohy na precvičenie séria C - odovzdať do 3. 3. 2025, 14:25 |
3.3.2025 P3 14:25 |
Paralelný algoritmus na vyhľadávanie maximálneho prvku. Odmocninová redukcia, dvojlogaritmický strom. Amdahlov zákon. Gustafsonov zákon. Joseph Jájá: An Introduction to Parallel Algorithms - kapitola 2.6. Slajdy z prednášky. Úlohy na precvičenie séria D - odovzdať do 10. 3. 2025, 14:25 |
10.3.2025 P3 14:25 |
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. Slajdy z prednášky. Úlohy na precvičenie séria E - odovzdať do 19. 3. 2025, 15:20 |
19.3.2025 15:20 P11 |
Paralelné prehľadávanie, rank, paralelné zlučovanie. Paralelné usporiadanie pomocou paralelného zlučovania (MergeSort), optimalizácia. Joseph Jájá: An Introduction to Parallel Algorithms - kap. 2.4 a kap. 4 - MergeSort Slajdy z prednášky. Úlohy na precvičenie séria F - odovzdať do 26. 3. 2025, 15:20 |
26.3.2025 15:20 P11 |
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. Joseph Jájá: An Introduction to Parallel Algorithms - kapitola 2.2, kapitola 4.4 Slajdy z prednášky. Úlohy na precvičenie séria G - odovzdať do 2. 4. 2025, 15:20 |
31.3.2025 14:25 P3 |
Polsemestrálny písomný test. |
2.4.2025 15:20 P11 |
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ť. Slajdy z prednášky Úlohy na precvičenie séria G+ - odovzdať do 9. 4. 2025, 15:20 |
9.4.2025 15:20 P11 |
Komunikácia v kruhovej sieti, voľba koordinátora. Šírenie správ v sieti záplavou (flood). M. Raynal: Distributed Algorithms for Message-Passing Systems (v intranete) kapitola 4. Leader Election Algorithms Slajdy z prednášky Úlohy na precvičenie séria H - odovzdať do 16. 4. 2025, 15:20 |
16.4.2025 15:20 P11 |
Komunikácia vlnou (wave), výzva (join) a odpoveď (echo) spätnou vlnou. Distribuované prehľadávanie acyklickej siete do šírky. Problémy komunikácie v neacyklickej sieti. Minimálna kostra ohodnoteného grafu. Najkratšie cesty. Intervalové a prefixové smerovanie. M. Raynal: Distributed Algorithms for Message-Passing Systems (v intranete) kapitola 1. Network Traversal a 2. Distributed Graph Algorithms (2.1 Distributed Shortest Path) Slajdy z prednášky Úlohy na precvičenie séria I - odovzdať do 23. 4. 2025, 15:20 |
23.4.2025 15:20 P11 |
J. van Leeuwen, R. B. Tan: Intervalové smerovanie E. M. Bakker, J. van Leeuwen, R. B. Tan: Prefixové smerovanie Synchronizácia času v distribuovaných systémoch. Riešenie logickými a fyzickými hodinami, koordinácia, intervalový a vektorový čas. M. Raynal: 7.1 Logical Time in Asynchronous Distributed Systems Slajdy z prednášky Úlohy na precvičenie séria J - odovzdať do 7. 5. 2025, 15:20 |
7.5.2025 15:20 P11 |
Aktuálny obraz systému (snapshot). 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). M. Raynal: 11. Distributed Resource Allocation, 15. Distributed deadlock detection A. D. Kshemkalyani, M. Singhal: Distributed Computing ( v intranete ) 4. Global state and snapshot recording algorithms, 9. Distributed mutual exclusion algorithms 10. Deadlock detection Slajdy z prednášky Úlohy na precvičenie séria K - odovzdať do 12. 5. 2025, 14:25 |
12.5.2025 14:25 P03 |
Detekcia ukončenia výpočtu. 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, problém dohody byzantínskych generálov Distribuovaný konsenzus - systém Paxos, Raft. A. D. Kshemkalyani, M. Singhal: Distributed Computing ( v intranete ) Chapters 7. Termination detection 14. Consensus and agreement algorithms Slajdy z prednášky Lamport, Shostak, Pease: The Byzantine Generals Problem Video Practical Byzantine Fault Tolerance Video Úlohy na opakovanie séria L - odovzdať do 21. 5. 2025, 10:00 |
:
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)
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
zo všetkých prebratých tém
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.
*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ť.
*Hľadanie koordinátora v kruhovej (jednosmernej a obojsmernej) sieti. Časová a komunikačná zložitosť.
*Šírenie správ v sieti algoritmom záplavy (príkad - hľadanie koordinátora).
*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).
*Typy chýb distribuovaného prostredia a možnosti ich odstránenia. Riešenie problému zhody s najviac k fatálnymi chybami.
*Problém dosiahnutia dohody a zhody (konsenzu) v synchrónnych systémoch s fatálnymi a byzantínskymi chybami.