Záverečný písomný test bude vo štvrtok 6. 6. 2019 o 9:00 v P9.
Ďalší termín písomného testu je štvrtok 13. 6. 2019 o 9:00 v P9.
Posledný test a skúška bude v piatok 21. 6. 2019 o 10:30 v P10.
Ak absolvujete viac testov, započíta sa najlepší. Ústna skúška sa počíta vždy len posledná.
| Prebraté a plánované témy | |
| 14.2.2019 |
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. Lamportov algoritmus. Semafory a ich využitie pri riešení synchronizačných úloh. Úlohy typu producer-consumer, readers-writers. Synchronizácia procesov, bariéry, monitor. Problémy uviaznutia a vyhladovania a ich riešenie. Slajdy z prednášky. M. Raynal: Concurrent Programming: Algorithms, Principles, and Foundations (v Intranete) Úlohy na precvičenie séria A (doc, pdf) - odovzdať do 21. 2. 2019, 14:25 |
| 21.2.2019 |
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) Úlohy na precvičenie séria B (doc, pdf) - odovzdať do 28. 2. 2019, 14:25 |
| 28.2.2019 |
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. Slajdy z prednášky. Joseph Jájá: An Introduction to Parallel Algorithms (1.a 2. kapitola v Intranete) Úlohy na precvičenie séria C (doc, pdf) - odovzdať do 7. 3. 2019, 14:25 |
| 7.3.2019 HVRL |
Tutoriál - Programovanie GPU - CUDA (OpenCL). Materiály k tutoriálu + Prezentácia . Texty programov na redukované súčty poľa. Úlohy na precvičenie sú na konci materiálov. |
| 14.3.2019 |
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). 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á: An Introduction to Parallel Algorithms: 4. kapitola: Searching, merging, and sorting (v Intranete): Úlohy na precvičenie séria D (doc, pdf) - odovzdať do 21. 3. 2019, 14:25 Písomné riešenie úlohy 2 a úlohy 5* stačí odovzdať do 28.3. |
| 21.3.2019 | Polsemestrálny písomný test v P03 (60 min). 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 Materiály k štúdiu - M. Raynal: Distributed Algorithms for Message-Passing Systems (v intranete) kapitola 4. Leader Election Algorithms Úlohy na precvičenie séria E (doc, pdf) - odovzdať do 28. 3. 2019, 14:25 |
| 28.3.2019 |
Ší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. Minimálna kostra ohodnoteného grafu. Smerovacie algoritmy. Hľadanie najkratších ciest a vzdialeností medzi vrcholmi. 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 F (doc, pdf) - odovzdať do začiatku tutoriálu 4. 4. 2019, 14:25 |
| 4.4.2019 P03 |
Tutoriál MPI. Nezabudnite odoslať riešenie úlohy na konci materiálov k tutoriálu priamo na adresu RKB Za úplné riešenie môžete od RKB dostať max 5 bodov. |
| 11.4.2019 P03 |
Tutoriál Apache Spark - spracovanie veľkých dát. Slajdy z tutoriálu (VM pre VirtualBox). Zadanie úlohy (za max 5 bodov): Napíšte Spark program v Scale, ktorý nájde vo Wikipedia Pageviews datasete stránky na Slovenskej wikipédii (všetky projekty začínajúce na "sk"), ktoré majú najväčší počet slov v nadpise. Riešenia a prípadné otázky smerujte na marian.dvorsky at gmail.com so subjektom Spark tutorial najneskôr do 18. 4. 2019, 14:25 |
| 18.4.2019 P03 |
Tutoriál Apache Spark - dokončenie. Úlohy na precvičenie séria G (doc, pdf) - odovzdať do 2. 5. 2019, 14:25 |
| 2.5.2019 |
Synchronizácia času v distribuovaných systémoch. Riešenie logickými a fyzickými hodinami, koordinácia, intervalový čas. 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. Aktuálny obraz systému (snapshot), detekcia ukončenia. Slajdy z prednášky Kapitoly z knihy M. Raynal: 7.1 Logical Time in Asynchronous Distributed Systems, 10. Permission-Based Mutual Exclusion Algorithms 14 Distributed termination detection, Úlohy na precvičenie séria H (doc, pdf) - odovzdať do 16. 5. 2019, 14:25 |
| 16.5.2019 |
Možnosti dohody (konsenzu) v nespoľahlivom prostredí. Distribuovaný konsenzus - systém Paxos, Raft. Navigácia objektov, PageRank, hashing. Slajdy z prednášky |
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:
Principles and Paradigms, Prentice Hall, 2002
Gerard Tel:
Introduction to Distributed Algorithms, CUP 2001
(Google-books)
Sukumar Ghosh: Distributed Systems and Algorithms (Second Edition), CRC Press 2014
V. K. Garg: Elements of Distributed Computing (distrib. algoritmy v Jave)
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.
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 (prednášky 5, 6, 7, 8).
Otázky na ústne preskúšanie (z každej časti jedna) :
*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 minima).
*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ý 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).
*Problém dosiahnutia zhody (konsenzu) v synchrónnych systémoch s fatálnymi a byzantínskymi chybami.
