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

Kurz PDS bude prebiehať v pondelky od 12:35 v P11 (resp. P3), cvičenia potom od 14:25 v P3.

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

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
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.
22.4.2024 14:25 P03	Tutoriál MPI - 2. časť

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 H100
NVIDIA B100 Blackwell architektúra
Dátové centrá Google
Internetové štatistiky

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

Projekty
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

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

Tutoriál MPI - rastislav.krivos-bellus at upjs.sk

Kritériá hodnotenia - bodované aktivity:

(35 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.
(25 bodov) praktické zadania z cvičení a tutoriálov
(20 bodov) úspešné riešenie projektu
Projekty budú zadávané individuálne a budú orientované na praktické zručnosti.
(20 bodov) polsemestrálny test
(20 bodov) záverečný písomný test
(20 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.