Algoritmy a jejich implementace

V letním semestru 2022/2023 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 čtvrtek od 15:40 v S7.

Cvičení ve čtvrtek od 17:20 v SW2 vede Filip Štědronský.

Co se přednášelo

datum téma
16. 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.
16. 2. Pokračování na cvičení: Výrazy a operátory. Typové konverze. Vedlejší efekty a synchronizační body. Jak číst deklarace: typy, kvalifikátory, incializátory.
23. 2. Pokračování Céčka: Třídy uložení (static a spol.). Funkce a jejich deklarace. Příkazy. Preprocesor a pravidla nahrazování maker. Standardní knihovna. GCCčková rozšíření jazyka.
2. 3. 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.
9. 3. Ještě trocha assembleru. Cache a jejich hierarchie. Paměti SDRAM a jejich rozhraní (aproximace). Správa paměti (MMU).
16. 3. Paměť: TLB a jejich interakce s cachemi, sdílení TLB mezi procesy pomocí PCID. Graf rychlosti přístupů k paměti a věštění z něj.
23. 3. Přednáška odpadá, cvičení bude.
30. 3. 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.
6. 4. 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. Úvod do SMP a NUMA.
13. 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.
20. 4. Thread-local storage. 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.
27. 4. Atomické operace a různé sémantiky konsistence atomických proměnných. Paměťový model C11. Implementace zámků a futexy. Transakční paměť softwarová i hardwarová. Restartable sequences. Skutečný SMP hardware: Vícejádrové procesory, HyperThreading a Bulldozer.
4. 5. Různé topologie víceprocesorových strojů, FSB, HyperTransport, QuickPath. Zvyšujeme počet procesorů: NumaConnect, AMD Magny-Cours a triky v jeho implementaci L3 cache. Directory-based koherence a HT-Assist. Co přinesl projekt Larrabee: Xeon Phi a AVX-512, 2D sběrnice ve Skylake.
11. 5. Další implementace x86: AMD Zen. Bezpečnostní problémy spekulativního vyhodnocování: různé druhy postranních kanálů, Meltdown, různé varianty Spectre, L1TF.
18. 5. Pokačování bezpečnostních problémů: SSB, MDS (a.k.a. Fallout, RIDL a ZombieLoad). Příklad ze života: Jak jsme programovali sorter pro LibUCW. Interní třídící algoritmy a jejich chování. Externí třídění aneb proč disk není páska.

Zkoušky

Ke zkoušce je potřeba znalost odpřednesené látky (bez technických detailů hardwaru). Na zkouškové termíny se prosím hlaste v SISu; po domluvě vás rád vyzkouším i jindy. Zápočet můžete získat nezávisle na složení zkoušky.

Odkazy

Stránku spravuje Martin Mareš