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



Záverečný prezenčný písomný test v utorok 26. 5. 2020 od 9:00 v P11 v P08.
Na dištančnú skúšku sa zatiaľ nikto neprihlásil.
Ďalší termín prezenčnej skúšky určujem predbežne na 9. 6. 2020 9:00 (ale po dohode je možné ho zmeniť)
Termín dištančnej skúšky bude potom 10. 6. (na technických detailoch sa dohodnem s prihlásenými)
Ďalší termín prezenčného testu a ústnej skúšky určujem na 18. 6. 2020 o 10:00 v P17 .


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

Zadania domácich úloh - séria A (doc, pdf), séria B (doc, pdf), séria C (doc, pdf), séria D (doc, pdf),
séria E (doc, pdf), séria F (doc, pdf), séria G (doc, pdf), séria H (doc, pdf), séria I (doc, pdf), séria J (doc, pdf)

  Prebraté a plánované témy
10.2.2020 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šenie s aktívnym a pasívnym čakaním.
Kritická sekcia a jej ošetrenie mutexami.
Synchronizácia procesov, bariéry, monitor.
Problémy uviaznutia a vyhladovania a ich riešenie.
Slajdy z prednášky.
Pre osvieženie poznatkov z OS a z konkuretného programovania -
prejdite kapitoly 6, 7 a 8 (str. 257 - 347) z Operating System Concepts (v intranete)
Úlohy na precvičenie séria A (doc, pdf) - odovzdať do 17. 2. 2020, 14:25
17.2.2020 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.
Výpočet charakteristík pre problém sčítania n prvkov, škálovanie.
Paralelný algoritmus na vyhľadávanie, nájdenie maximálneho prvku.
Paralelný algoritmus na výpočet prefixových súčtov.
Amdahlov zákon. Gustafsonov zákon.
Slajdy z prednášky.
Joseph Jájá: An Introduction to Parallel Algorithms (1. kapitola v Intranete)
Preštudovať kapitoly: 1.1, 1.2, 1.3., 1.4.
Úlohy na precvičenie séria B (doc, pdf) - odovzdať do 24. 2. 2020, 14:25
24.2.2020
HVRL
Tutoriál - Programovanie GPU - CUDA (OpenCL).
Materiály k tutoriálu + Prezentácia .
2.3.2020
HVRL
Tutoriál - Programovanie GPU - CUDA - 2.časť
Bude opäť v Laboratóriu haptiky a virtuálnej reality (pri sekretariáte ÚINF)

Dvojlogaritmické stromy.
Slajdy z prednášky - aktualizované.
Úlohy na precvičenie séria C (doc, pdf) - odovzdať do 9. 3. 2020, 14:25
9.3.2020 Work-time zápis paralelných algoritmov. optimalita.
Optimálny paralelný algoritmus na výpočet prefixových súčtov.
Paralelný ranking a súvisiace postupy.
Paralelné vyhľadávanie, rank, paralelné zlučovanie.
Paralelné usporiadanie pomocou paralelného zlučovania (MergeSort), optimalizácia.
( Optimálny rank s paralelným vyhľadávaním s p procesormi v konštantnom čase.
loglog(n) optimálne zlučovanie ) - nebude na skúške
Slajdy z prednášky.
Joseph Jájá: IPA (kapitoly 1.5, 1.6, 2.1 a 2.4 (kap. 4 - MergeSort) v Intranete)
Úlohy na precvičenie séria D (doc, pdf) - odovzdať do 16. 3. 2020, 14:25
16.3.2020 Dištančné vzdelávanie bude prebiehať v prostredí MS Teams v triede PDS2020.
Svoje otázky môžte zadávať do kanála Chat, materiály k prednáškam budú
v kanáli Všeobecné v záložke Súbory/Učebné materiály.
Budem aktualizovať aj túto stranku, ak by ste mali s MS Teams problémy ...
Úlohy na precvičenie séria E (doc, pdf) - odovzdať do 23. 3. 2020, 14:25 do systému MS Teams
23.3.2020
14:25-17:00
PDS2020
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.
Joseph Jájá: IPA (kapitola 2.2, kapitola 4. Searching, merging, and sorting)
Úlohy na precvičenie séria F (doc, pdf) - odovzdať do 30. 3. 2020, 14:25 do systému MS Teams
V úlohe 1 môžte predpokladať, že všetky prvky poľa M sú navzájom rôzne.
30.3.2020
14:25-17:00
PDS2020
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.
Slajdy z prednášky
M. Raynal: Distributed Algorithms for Message-Passing Systems (v intranete)
kapitola 4. Leader Election Algorithms
Úlohy na precvičenie séria G (doc, pdf) - odovzdať do 6. 4. 2020, 14:25 do systému MS Teams
6.4.2020
14:25-17:00
PDS2020
Tutoriál MPI.
Úlohy k tutoriálu sú na konci materiálov. Riešenia posielajte do PDS2020 do 16. 4. 2020 23:59.
Za úplné riešenie môžete od RKB dostať max 5 bodov.
Na konci materiálov je tiež ponuka projektov z MPI aj s obsadenosťou.
20.4.2020
14:25-17:00
PDS2020
Šírenie správy v stromovej sieti záplavou (flood).
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.
Hľadanie najkratších ciest a vzdialeností medzi uzlami.
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 H (doc, pdf) - odovzdať do 27. 4. 2020, 14:25 do systému MS Teams
27.4.2020
14:25-17:00
PDS2020
Intervalové a prefixové smerovanie.
Slajdy z prednášky
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
Z knihy M. Raynal: DA 7.1 Logical Time in Asynchronous Distributed Systems,
6. Concept of Global State,
Úlohy na precvičenie séria I (doc, pdf) - odovzdať do 4. 5. 2020, 14:25 do systému MS Teams
4.5.2020
14:25-17:00
PDS2020
Ošetrenie vzájomného vylúčenia 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
Z knihy M. Raynal: DA 10. Permission-Based Mutual Exclusion Algorithms
14 Distributed termination detection, 15 Distributed deadlock detection
Úlohy na precvičenie séria J (doc, pdf) - odovzdať do 11. 5. 2020, 14:25 do systému MS Teams
11.5.2020
14:25-17:00
PDS2020
Tolerancia chýb v distribuovanom systéme.
Spoľahlivé výpočty v prostredí s chybami.
Možnosti dohody (konsenzu) v nespoľahlivom prostredí.
Byzantínske chyby
Distribuovaný konsenzus - systém Paxos, Raft.
Navigácia objektov, PageRank, hashing.
Sociálne a P2P siete, Chord, Pastry, Kademlia, BitTorent.
Slajdy z prednášky
Lamport, Shostak, Pease: The Byzantine Generals Problem Video
Practical Byzantine Fault Tolerance
Lamport - Paxos, Paxos Made Simple
Ongaro, Ousterhout - Raft
Pastry

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)

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 :

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


Projekty
Vyberte si jednu z tém tutoriálov a vyžiadajte e-mailom zadanie od príslušného prednášateľa.
CUDA - ladislav.mikes at gmail.com
Riešenia odovzdávajte vo forme, dohodnutej so zadávateľom. Pokiaľ odovzdáte riešenie pred termínom, je možné ho po konzultácii so zadávateľom vylepšiť a získať tak väčší počet bodov.
Termín odvzdania riešenia je 15. 5. 2020, 23:59.
Obhajobu je potrebné dohodnúť najlepšie v zápočtovom týždni, aby ste mali zapísané body v prípade skúšky v predtermíne.
Pokiaľ potrebujete uzavrieť štúdium v skoršom termíne, je potrebné odovzdať projekt pred konaním záverečnej skúšky.


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ň 15 za záverečné preskúšanie). Stupňom D budeme hodnotiť zisk aspoň 80 bodov, C aspoň 90 bodov, B aspoň 100 bodov a A aspoň 110 bodov.


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

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