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

Kurz PDS bude prebiehať v pondelky od 14:25 v P11 (SJ2P11), cvičenia potom v stredu od 14:25 v P5 (SA1C05).

Cvičenia
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

	Prebraté a plánované témy
9.2.2026 P11 14:25	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 16. 2. 2026, 14:25
16.2.2026 P11 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). Joseph Jájá: An Introduction to Parallel Algorithms - kapitoly 1.1, 1.2, 1.3. Úlohy na precvičenie séria B - odovzdať do 23. 2. 2026, 14:25
23.2.2026 14:25	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 2. 3. 2026, 14:25
2.3.2026 P11 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 9. 3. 2026, 14:25
9.3.2026 P11 14:25	Work-time zápis paralelných algoritmov, WT 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 16. 3. 2026, 14:25
16.3.2026 14:25 P11	Paralelné prehľadávanie, rank, paralelné zlučovanie. Paralelné usporiadanie pomocou paralelného zlučovania (MergeSort), optimalizácia. Akcelerované kaskádovanie. 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 23. 3. 2026, 14:25
23.3.2026 14:25 P11	Bitonické postupnosti, bitonické zlučovanie, MergeSort s bitonickým zlučovaním. Even-odd zlučovanie, 0-1 princíp. Sortovacie siete 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 30. 3. 2026, 14:25
1.4.2026 14:25 P5	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 13. 4. 2026, 14:25
13.4.2026 14:25 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. Minimálna kostra ohodnoteného grafu. Najkratšie cesty. 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 20. 4. 2026, 14:25
20.4.2026 14:25 P11	Smerovacie algoritmy. Intervalové a prefixové smerovanie. 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. Aktuálny obraz systému (snapshot).

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
NVIDIA Rubin architektúra NVIDIA Vera Rubin NVL72
Dátové centrá Google video
Internetové štatistiky

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

Kritériá hodnotenia - bodované aktivity:

(30 bodov) aktívna práca na cvičeniach a úspešné dokončenie praktických úloh
Kritériá udeľovania bodov za cvičenia a termíny na ich získanie určí cvičiaci.
(cca 40 bodov) úspešné riešenie domácich zadaní (z prednášok)
Bodovanie domácich zadaní je uvedené individuálne v každom zadaní.
Riešenia sa odovzdávajú v písomnej forme, obsahujúcej meno riešiteľa a zdroje, ktoré použil pri vypracovaní.
Spolupráca a konzultácie v menších skupinkách sa nevylučujú, písomné spracovanie musí byť samostatné
(často ide o vyjadrenie subjektívneho názoru resp. uvedenie príkladu z mnohých možností).
Opisované riešenia hodnotené nebudú a môžu byť posudzované ako porušenie pravidiel čestného správania.
Riešenia odovzdané po termíne sa tiež nehodnotia.
(20 bodov) polsemestrálny písomný test
(20 bodov) záverečný písomný test
(30 bodov) záverečné ústne preskúšanie (z vopred oznámených otázok)
Za záverečné ústne preskúšanie je potrebné získať aspoň 10 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ň 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.

Problémy a otázky môžete konzultovať s cvičiacim (podľa konzultačných hodín), s prednášajúcim po prednáške
resp. elektronickou poštou na adrese jozef.jirasek at upjs.sk. Konzultácie je možné dohodnúť aj individuálne, no len v priebehu semestra.
V skúškovom období konzultácie nebudú.