| Prebraté a plánované témy |
12.2.2024 P11 12:35 |
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. Úlohy na precvičenie séria A - odovzdať do 19. 2. 2024, 12:35 |
19.2.2024 P11 12:35 |
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. Úlohy na precvičenie séria B - odovzdať do 26. 2. 2024, 12:35 |
26.2.2024 mimoriadne P03 12:35 |
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. 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 4. 3. 2024, 12:35 |
26.2.2024 P03 14:25 |
Tutoriál - programovanie GPU. Materiály k tutoriálu + Prezentácia |
4.3.2024 P03 12:35 |
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 - kapitoly 2.2., 2.6. Slajdy z prednášky. Úlohy na precvičenie séria D - odovzdať do 11. 3. 2024, 12:35 |
11.3.2024 P11 12:35 |
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 18. 3. 2024, 12:35 |
18.3.2024 12:35 P11 |
Paralelné preľadávanie, rank, paralelné zlučovanie. Paralelné usporiadanie pomocou paralelného zlučovania (MergeSort), optimalizácia. Joseph Jájá: An Introduction to Parallel Algorithms - kapitola 2.4 Slajdy z prednášky. Úlohy na precvičenie séria F - odovzdať do 25. 3. 2024, 12:35 |
25.3.2024 12:35 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. Opakovanie s riešením úloh. Joseph Jájá: An Introduction to Parallel Algorithms - kapitola 2.2, kapitola 4 Slajdy z prednášky. Úlohy na precvičenie séria G - odovzdať do začiatku testu 8. 4. 2024, 12:35 |
8.4.2024 12:35 P11 |
Polsemestrálny písomný test (60 min). |
8.4.2024 14:25 P03 |
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) kapitola 4. Leader Election Algorithms Slajdy z prednášky Úlohy na precvičenie séria H - odovzdať do 15. 4. 2024, 12:35 |
15.4.2024 12:35 P11 |
Šírenie správ v sieti záplavou (flood). 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. M. Raynal: Distributed Algorithms for Message-Passing Systems (v intranete) kapitola 1. Network Traversal Algorithms Slajdy z prednášky Úlohy na precvičenie séria I - odovzdať do 22. 4. 2024, 12:35 |
22.4.2024 12:35 P11 |
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. M. Raynal: Distributed Algorithms for Message-Passing Systems (v intranete) kapitola 2. Distributed Graph Algorithms (2.1 Distributed Shortest Path) a 3. Global Functions on a Process Graph J. van Leeuwen, R. B. Tan: Intervalové smerovanie E. M. Bakker, J. van Leeuwen, R. B. Tan: Prefixové smerovanie Slajdy z prednášky Úlohy na precvičenie séria J - odovzdať do 29. 4. 2024, 12:35 |
29.4.2024 12:35 P11 |
Synchronizácia času v distribuovaných systémoch. Riešenie logickými a fyzickými hodinami, koordinácia, intervalový a vektorový čas. Aktuálny obraz systému (snapshot). Ošetrenie vzájomného vylúčenia v distribuovanom systéme. |
29.4.2024 14:25 P03 |
Tutoriál Apache Spark - distribuované spracovanie veľkých dát. |
:
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)
Sú súčasťou celkového hodnotenia (možno získať až 20 bodov).
Vyberte si jednu z tém tutoriálov a vyžiadajte e-mailom zadanie od príslušného prednášateľa.
Z každého tutoriálu je možné vyberať len z obmedzeného počtu tém.
Termín vyhodnotenia riešení projektov je 17. 5. 2024, 23:59. Termín nebude predlžovaný!.
Čím skôr si vyberiete tému, tým viac času budete mať na jej riešenie.
Odovzdávajte riešenia dostatočne dlho pred termínom, aby ich bolo možné vyhodnotiť.
Po konzultácii so zadávateľom je možné riešenie vylepšiť a získať tak väčší počet bodov.
Riešenia odovzdávajte vo forme, dohodnutej so zadávateľom.
Témy projektov z tutoriálu CUDA - ladislav.mikes at gmail.com
Tutoriál MPI - rastislav.krivos-bellus at upjs.sk
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.