Tato stránka je rozšířenou osnovou kurzu, který je určen pro mírně pokročilé programátorky a programátory, kteří zvládají základy programování v programovacím jazyce C a chtěli by své schopnosti rozšířit směrem k tvorbě paralelních aplikací, a to jak pro architektury se sdílenou pamětí (vícevláknové aplikace), tak i pro architektury s distribuovanou pamětí (clusterové aplikace, aplikace s posíláním zpráv).
Kurz je zaměřen spíše do šířky, a jeho cílem je upozornit na různorodé problémy, na které programátor paralelních aplikací může narazit. Kurz provází studenty od nejnižších úrovní paralelizace až po principy návrhu paralelních aplikací a rozsáhlých distribuovaných systémů.
Kurz se skládá z deseti teoretických přednášek, několika málo praktických ukázek a dvou malých samostatně realizovaných programovacích miniprojektů.
Přednáška 01 - Úvod
Slajdy: IB109_01_uvod.pdf
- Organizace kurzu, cíle kurzu, podmínky pro ukončení kurzu, kontext v rámci FI
IB109_video_01.mp4 (19:49)
-- Pozor, video je neaktuální! Pro úspěšné ukončení je požadováno odevzdání obou miniprojektů.
- Motivace pro paralelní výpočty, abstraktní model výpočetní platformy
IB109_video_02.mp4 (47:38)
- Paralelní výpočty
IB109_video_03.mp4 (43:38)
Přednáška 02 - Programování v prostředí se sdílenou pamětí
Slajdy: IB109_02_shared-memory.pdf
- Výpočetní jádra, vlákna, procesy
IB109_video_04.mp4 (44:55)
- Efektivní využití cache, falešné sdílení
IB109_video_05.mp4 (28:46)
- Mentální vs. reálný model výpočtu, nestálé proměnné, paměťová bariéra
IB109_video_06.mp4 (33:47)
- Demonstrace programů s paralelním přičítání jedničky
IB109_video_07.mp4 (10:44)
Přednáška 03 - Programování v prostředí se sdílenou pamětí, POSIX Threads
Slajdy: IB109_03_pthreads.pdf
- Rizika spojená se sdílenou pamětí
IB109_video_08.mp4 (85:20)
- Posixové rozhraní pro vlákna - správa vláken
IB109_video_09.mp4 (34:21)
- Posixové rozhraní pro vlákna - vzájemné vyloučení
IB109_video_10.mp4 (12:15)
Přednáška 04 - POSIX Threads (pokračování), Win32 Threads
Slajdy: IB109_04_pthreads.pdf
- Posixové rozhraní pro vlákna - podmínkové proměnné a ostatní
IB109_video_11.mp4 (28:05)
- Read-write lock, bariéra pomocí PThread API
IB109_video_12.mp4 (31:15)
- Semafory, Monitory
IB109_video_13.mp4 (07:33)
- POSIX Thread vs. vlákna v MS Windows
IB109_video_14.mp4 (10:47)
Přednáška 05 - Implementace Lock-Free datových struktur
Slajdy: IB109_05_lock_free.pdf
- Lock-Free programování s CAS
IB109_video_15.mp4 (18:24)
- Lock-Free WRRM Mapa
IB109_video_16.mp4 (35:41)
- Hazardní ukazatele (Lock-Free Garbage Collector)
IB109_video_17.mp4 (15:38)
- Lock-Free s transakční pamětí a instrukcemi LL/SC
IB109_video_18.mp4 (05:52)
Přednáška 06 - Pokročilá rozhraní pro implementaci paralelních aplikací
Slajdy: IB109_06_openmp_tbb.pdf
- OpenMP
IB109_video_19.mp4 (46:47)
- Demo použití OpenMP
[ vyučující odmítl poskytnout toto video s odvoláním na svou totální neschopnost,
silnou prokrastinaci a absenci termínu uvolnění Diabla IV ]
- Threading Building Blocks
IB109_video_21.mp4 (34:35)
- C++11
IB109_video_22.mp4 (19:03)
- Paralelní for cyklus @ Sourceforge
IB109_video_23.mp4 (00:33)
Přednáška 07 - Principy návrhu paralelních algoritmů
Slajdy: IB109_07_principy.pdf
- Návrh paralelních algoritmů - Úvod
IB109_video_24.mp4 (29:27)
- Dekompozice
IB109_video_25.mp4 (21:44)
- Mapování a vyrovnávání zátěže
IB109_video_26.mp4 (34:01)
- Redukce režie komunikace
IB109_video_27.mp4 (19:49)
Přednáška 08 - Kolektivní komunikační primitiva
Slajdy: IB109_08_komunikace.pdf
- Kolektivní komunikační primitiva a topologie
IB109_video_28.mp4 (19:39)
- One-to-All, All-to-One
IB109_video_29.mp4 (14:43)
- All-to-All
IB109_video_30.mp4 (07:45)
- Individualizované zprávy v All-to-All
IB109_video_31.mp4 (13:22)
- Méně běžná kolektivní komunikační primitiva
IB109_video_32.mp4 (11:28)
Přednáška 09 - Programování aplikací pro prostředí s distribuovanou pamětí
Slajdy: IB109_09_openmpi.pdf
- Principy programování s předáváním zpráv
IB109_video_33.mp4 (36:47)
- Message Passing Interface - Send, Receive
IB109_video_34.mp4 (29:16)
- Message Passing Interface - Kolektivní komunikace
IB109_video_35.mp4 (29:37)
- Zkušenosti s vývojem MPI aplikace
IB109_video_36.mp4 (15:37)
Přednáška 10 - Analytický model paralelních programů
Slajdy: IB109_10_analyza.pdf
- Analýza a metriky paralelních systémů
IB109_video_38.mp4 (53:37)
- Škálovatelnost
IB109_video_39.mp4 (22:45)
Mini-projekt 01
Vaším cílem v rámci tohoto projektu je naimplementovat s využitím metod Lock-Free programování thread-safe datovou strukturu fronty (požadované metody jsou enqueue -- zařaď prvek do fronty, dequeue -- vyber prvek z fronty a isEmpty --- otestuj, zda je fronta prázdná) a vystavit ji zátěži několika souběžně běžících vláken, které vkládají a vybírají z fronty. Jednotlivé metody pracující nad stejným koncem fronty jsou z podstaty věci vzájemně výlučné, nicméně nad různými konci fronty, by Vaše implementace měla umožnit souběžnou práci (tj. je-li fronta dost dlouhá, enque a deque mohou běžet souběžně). Následně upravte svoji implementaci tak, aby místo lock-free přístupu používala pouze POSIXové rozhraní a test opakujte. Porovnejte výsledky vašeho měření.
Aby vaše řešení bylo uznáno, musí splnit všechny následující podmínky.
- umístěno v jednom adresáři, odevzdaný jako tar.gz soubor
- provedením příkazu make v daném adresáři na stroji aisa se přeloží a spustí Váš kód
- Váš kód nesmí běžet déle jak 3 vteřiny
- aplikace vypíše na konzolu právě 2 řádky
- na 1. prvním řádku Vaše učo
- na 2. druhém řádku jedno celé číslo, které vyjadřuje kolik procent času POSIXového řešení zabralo Lock-Free řešení (tj. bude-li Lock-Free přístup o pětinu rychlejší, vypíše se 80, pokud o pětinu pomalejší, vypíše se 120)
- buďte opatrní a při ladění raději používejte jiný HW než server aisa
Mini-projekt 02
Vaším cílem v tomto mini-projektu je naimplementovat MPI aplikaci, která po spuštění na n-procesech pomocí metod házení mince určí mezi participujícími procesy jednoho vládce. Informaci, kdo je zvoleným vládcem, musí po jeho zvolení znát všichni účastníci výpočtu, což doloží tím, že vypíší na konzolu text "Sloužím ti, můj vládče, slunce naše jasné." a doplní tento text identifikátorem procesu vládce v komunikátoru MPI_COMM_WORLD.
Protokol házení mincí je vícekolový protokol, přičemž princip volby je následující. V každém kole každý, kdo je ještě ve hře o pozici vládce, hodí mincí. Pokud padla alespoň jednou v celém distribuovaném výpočtu v tomto kole panna (řekněmě hodnota 1) tak všichni, kteří jsou ještě ve hře a padl jim v tomto kole orel (hodnota 0), vypadávají ze hry. Kola se opakují, dokud není ve hře právě jeden poslední proces.
Aby vaše řešení bylo uznáno, musí splnit všechny následující podmínky.
- umístěno v jednom adresáři, odevzdaný jako tar.gz soubor
-
provedením příkazu make v daném adresáři na stroji nymfe50 se přeloží a spustí Váš kód na
(8 procesech)6 processech
(můžete předpokládat, že mpirun a mpicc jsou dostupné) - aplikace jako první vypíše Vaše učo (právě jednou) a pak budou následovat výpisy požadované výše
Doporučuji pro účely ladění nastavit si přihlašování mezi stroji nymfe přes ssh bez hesla.