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


Záverečný písomný test bude v utorok 30. 5. 2017 o 10:00 v P12.
Ďalší termín písomného testu je piatok 9. 6. 2017 o 10:00 v P12.
Posledný test a skúška bude v utorok 27. 6. 2017 o 10:00 v P10.
Ak absolvujete viac testov, započíta sa najlepší. Ústna skúška sa počíta vždy len posledná.

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

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
16.2.2017 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.
Úlohy na precvičenie séria A (doc, pdf) - odovzdať do 23. 2. 2017, 13:30 - zdrojové súbory k úlohe 5
23.2.2017 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.
Work-time zápis paralelných algoritmov. optimalita.
Paralelný algoritmus pre vyhľadávanie, nájdenie maximálneho prvku.
Zrýchlenie, efektivita a cena.
Paralelný algoritmus na výpočet prefixových súčtov.
Akcelerované kaskádovanie.
Slajdy z prednášky
Joseph Jájá: An Introduction to Parallel Algorithms - fotokópia, čiast. preklad (MFF BA)
Preštudovať kapitoly: 1.1, 1.2, 1.3.2, 1.3.4, 1.4, 1.5, 1.6, 1.8, 2.1 (2.1.3 len informačne), 2.6
Úlohy na precvičenie séria B (doc, pdf) - odovzdať do 2. 3. 2017, 13:30
2.3.2017 Amdahlov zákon. Gustafsonov zákon.
Paralelné vyhľadávanie, rank, paralelné zlučovanie.
Paralelné usporiadanie pomocou paralelného zlučovania (MergeSort), optimalizácia.
Bitonické postupnosti, bitonické zlučovanie, MergeSort s bitonickým zlučovaním.
Even-odd zlučovanie, 0-1 princíp.
Slajdy z prednášky
Preštudovať Jájá: Kapitola 4 (Searching, merging, and sorting)
Úlohy na precvičenie séria C (doc, pdf) - odovzdať do 9. 3. 2017, 13:30
9.3.2017
13:30
Tutoriál - Programovanie GPU - CUDA, OpenCL.
Bude v Laboratóriu zobrazovacích metód - v suteréne za posluchárňou P15
Materiály k tutoriálu.
Riešenia pošlite najneskôr do 16. 3. 2017, 23:59
16.3.2017 Rank s paralelným vyhľadávaním s p procesormi.
loglog(n) optimálne zlučovanie.
Pointer jumping a paralelný prefix v lese.
Lámanie symetrie v cykle.
Preštudovať Jájá: 2.2 (Pointer jumping), 2.4 (Partitioning), 2.7 (Symetry Breaking), 4.2 (Merging)
Slajdy z prednášky
Úlohy na precvičenie séria D (doc, pdf) - odovzdať do 23. 3. 2017, 13:30
23.3.2017 Polsemestrálny písomný test v P03 (60 min).
Tutoriál - Programovanie GPU - dokončenie (v Laboratóriu zobrazovacích metód).
Ponúkam bonusové body k testu - úlohy série E (doc, pdf) - odovzdať do 30. 3. 2017, 13:30
30.3.2017 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.
Ší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.
Materiály k štúdiu - M. Raynal: Distributed Algorithms for Message-Passing Systems (v intranete)
kapitoly 4. Leader Election Algorithms a 1. Network Traversal Algorithms
Slajdy z prednášky
Úlohy na precvičenie séria F (doc, pdf) - odovzdať do začiatku prednášky 10. 4. 2017, 13:30
6.4.2017
P03
Tutoriál MPI.
Slajdy z tutoriálu.
Virtuálny stroj (3.6 GB) k tutoriálu o MPI (na jeho spustenie potrebujete VirtualBox)
Demonštračný projekt.
MPI Tutorál , MPI Tutoriál LLNL
Projekt MPJ Express - Java implementácia MPI, návod
MPJ Plugin do Eclipse (rozzipovať a jarko skopírovať do /home/pds/eclipse/plugins)
10.4.2017
P11 13:30
po SDI
Zisťovanie topológie distribuovaným algoritmom v acyklickej a v neacyklickej sieti.
Minimálna kostra ohodnoteného grafu. Smerovacie algoritmy.
Intervalové a prefixové smerovanie.
Hľadanie najkratších ciest a vzdialeností medzi vrcholmi.
Materiály k štúdiu - M. Raynal: Distributed Algorithms for Message-Passing Systems (v intranete)
kapitoly 2. Distributed Graph Algorithms a 3. Global Functions on a Process Graph
Slajdy z prednášky
J. van Leeuwen, R. B. Tan: Intervalové smerovanie, E. M. Bakker, J. van Leeuwen, R. B. Tan: Prefixové smerovanie
Úlohy na precvičenie séria G (doc, pdf) - odovzdať do 4. 5. 2017, 13:30
20.4.2017
P03
Tutoriál Hadoop.
Slajdy z tutoriálu.
Virtuálny stroj k tutoriálu.
Hadoop web, Hadoop tutoriál
4.5.2017 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 a problém uviaznutia v distribuovanom systéme.
Možnosti detekcie a prevencie uviaznutia (wound-wait, wait-die).
Slajdy z prednášky
Kapitoly z knihy M. Raynal: 7. Logical Time in Asynchronous Distributed Systems,
9. Simulating Synchrony on Top of Asynchronous Systems,
10. Permission-Based Mutual Exclusion Algorithms a 11. Distributed Resource Allocation
Úlohy na precvičenie séria H (doc, pdf) - odovzdať do 11. 5. 2017, 13:30
10.5.2017 O 13:30 v P11 nezabudnite na prezentácie diplomových prác
O 15:30 vo VKM odporúčame prednášku Mariána Dvorského
Evolúcia Big Data systémov
11.5.2017 Aktuálny obraz systému (snapshot), detekcia ukončenia.
Algoritmus Dijkstra-Scholten (celý článok v intranete)
Tolerancia chýb v distribuovanom systéme.
Úlohy na precvičenie séria I (doc, pdf) - odovzdať do 18. 5. 2017, 13:30
18.5.2017 Spoľahlivé výpočty v prostredí s chybami.
Možnosti dohody (konsenzu) v nespoľahlivom prostredí.

Trochu som doplnil slajdy z prednášky.
Skúste ešte posledné dve Úlohy na precvičenie séria J (doc, pdf) - odovzdať do 30. 5. 2017, 10:00


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: 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


Ďalšie zdroje na Sieti :

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



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é 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:

*Vzájomné vylúčenie s pasívnym a aktívnym čakaním - príklady riešenia v paralelnom a distribuovanom prostredí.
*Problém uviaznutia a jeho riešenie v 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 minima).
*Paralelný algoritmus pre výpočet prefixových súčtov - odhad zložitosti, zrýchlenia, optimálnosť, nerekurzívny prístup.
*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) 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.
*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.
*Vytvorenie konzistentnej snímky systému (Chandy-Lamport).
*Detekcia ukončenia (Dijkstra-Scholten).
*Problém dosiahnutia zhody v synchrónnych systémoch s fatálnymi a byzantínskymi chybami.
(riešenie problému vzájomného vylúčenia a uviaznutia v distribuovanom systéme je už zahrnutá v iných otázkach).