Paradigmata programování 4 (Paralelní programování) - Seznam přednášek (sylabus)

1. Paralelní program
   Paralelní programování, stav a historie paralelního programu, atomické akce, atomičnost složených akcí, synchronizace, charakteristiky paralelního programu.


2. Základy programové logiky
   Dokazování v sekvenčním a paralelním programu, atomicita a charakteristiky stroje, synchronizace, techniky vyloučení interference (invarianty, pomocné proměnné), problém producenta a konzumenta, bankovní systém, vlastnosti bezpečnosti a živosti (férovosti plánování).


3. Kritické sekce
   Hrubá a jemná synchronizace, implementace kritických sekcí: zámek (spin lock), prolomení remízy (Petersonův algoritmus Tie-Breaker), tahání lístků (Ticket), pekařský algoritmus (Bakery). Dokazování kritických sekcí: vzájemné vyloučení, vyloučení uváznutí, vyloučení zbytečného čekání a záruka vstupu. Aktivní a pasivní čekání.


4. Bariéry a datově paralelní algoritmy
   Bariéry a jejich implementace: sdílený čítač, vlajky a koordinátor, stromově kombinované a symetrické bariéry. Použití bariér. Problémy řešitelné datově paralelními algoritmy: prefixy pole, konec seznamu.


5. Semafory
   Semafory, operace nad nimi a jejich použití. Typické úlohy paralelního programování řešené semafory: kritická sekce, bariéra, producent a konzument, omezený buffer, večeřící filozofové, čtenáři a písaři. Technika předávání peška (bassing the baton). Implementace semaforů.


6. Synchronizace v operačních systémech
   Paralelizace a synchronizace v OS: kritické sekce, synchronizační primitiva (spin lock, read-write zámek, semafor). Synchronizace jader M$ Windows XP a Linux. API pro synchronizaci procesů a vláken v OS M$ Windows a GNU/Linux (UNIX).