Algoritmy a jejich implementace

V letním semestru 2024/2025 přednáším o tom, jak se algoritmy implementují na reálných počítačích [NDMI074]. Bude to přednáška na pomezí teorie a praxe. Očekávat můžete rychlokurs pokročilých partií jazyka C, stručný přehled charakteristik hardwaru důležitých pro optimalizaci algoritmů, základy paralelního programování na SMP/NUMA, vektorové výpočty, pokročilé techniky profilování a metody návrhu algoritmů přátelských ke keším. Také zabrousíme do témat týkajících se bezpečnosti procesorů.

Přednáška se koná ve středu od 15:40 v S6.

Cvičení ve středu od 14:00 v SW1 vede David Čepelík.

Co se přednášelo

datum téma
19. 2. Úvod do hlubin jazyka C11 (viz Medvědův průvodce po Céčku). Typový systém a reprezentace objektů (na co se lze spolehnout a na co už ne). Literály. Výrazy a operátory. Typové konverze. Vedlejší efekty a synchronizační body. Jak číst deklarace: typy, kvalifikátory, incializátory. Třídy uložení (static a spol.). Funkce a jejich deklarace. Příkazy.
26. 2. Pokračování Céčka: Preprocesor a pravidla nahrazování maker. Standardní knihovna. GCCčková rozšíření jazyka. Jak číst přeložené programy. Základy assembleru na IA32/AMD64: datové typy, registry, adresní módy, volací konvence. Různé překlady téhož programu.
5. 3. Místo přednášky se koná další cvičení v SW1. Ještě trocha GCCčkových rozšíření jazyka.
12. 3. Místo cvičení je další přednáška v S10. Cache a jejich hierarchie. Správa paměti (MMU). Paměť: TLB a jejich interakce s cachemi, sdílení TLB mezi procesy pomocí PCID. Paměti SDRAM a jejich rozhraní (aproximace). Graf rychlosti přístupů k paměti a věštění z něj.
19. 3. Přednáška i cvičení odpadají.
26. 3. Místo přednášky se koná další cvičení v SW1.
2. 4. Jak procesor zpracovává instrukce. Pipelining, superskalární a out-of-order vykonávání, spekulativní vyhodnocování a predikce skoků. Konkrétní implementace: Intel Core2 a jeho následníci.
9. 4. μ-op cache v Sandy Bridge. Vektorové programování: MMX, SSEn, AVXn, AVX-512. Další rozšíření instrukční sady: CRC32, AES, RDRAND, BMI, … Netemporální přístup k paměti a prefetche. Jak se vektorové jednotky používají z Céčka.
16. 4. Počítače s více procesory: SMP, protokoly MESI a MOESI pro koherenci cache. Jak programovat na SMP: Procesy a vlákna, různá systémová rozhraní. Všelijaká úskalí sdílení dat. Thread-safety a signal-safety. Thread-local storage.
23. 4. Synchronizace: zámky, semafory, condition variables. Příklad s frontou. Mnoho způsobů, jak si pořídit race condition, deadlock nebo livelock. Granularita zámků. Sdílená paměť mezi procesy a její synchronizace, úskalí NUMA. Implementace zámků a futexy. Transakční paměť softwarová i hardwarová.
30. 4. Plán: Atomické operace a různé sémantiky konsistence atomických proměnných. Paměťový model C11. Restartable sequences. Skutečný SMP hardware: Vícejádrové procesory, HyperThreading a Bulldozer.

Odkazy

Stránku spravuje Martin Mareš