Návrh a implementace paralelních systémů
prof. RNDr. Jiří Barnat, Ph.D.
Návrh a implementace paralelních systémů


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:  

  • Organizace kurzu, cíle kurzu, podmínky pro ukončení kurzu, kontext v rámci FI
    IB109_video_01.mp4
    (19:49)
  • Motivace pro paralelní výpočty, abstraktní model výpočetní platformy
    (47:38)


Přednáška 02 - Programování v prostředí se sdílenou pamětí

Slajdy: IB109_02_shared-memory.pdf

  • Mentální vs. reálný model výpočtu, nestálé proměnné, paměťová bariéra
    IB109_video_06.mp4 (33:47)


Přednáška 03 - Programování v prostředí se sdílenou pamětí, POSIX Threads

Slajdy: IB109_03_pthreads.pdf



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)



Přednáška 05 - Implementace Lock-Free datových struktur

Slajdy: IB109_05_lock_free.pdf


Přednáška 06 - Pokročilá rozhraní pro implementaci paralelních aplikací

Slajdy: IB109_06_openmp_tbb.pdf

  • 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 ]




Přednáška 07 - Principy návrhu paralelních algoritmů

Slajdy: IB109_07_principy.pdf



Přednáška 08 - Kolektivní komunikační primitiva

Slajdy: IB109_08_komunikace.pdf




Přednáška 09 - Programování aplikací pro prostředí s distribuovanou pamětí

Slajdy: IB109_09_openmpi.pdf



Přednáška 10 - Analytický model paralelních programů



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 desítek 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í.


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.

Předchozí
Následující