Algoritmy a jejich implementace

V letním semestru 2020/2021 přednáším o tom, jak se algoritmy implementují na reálných počítačích. 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á v úterý od 14:00 na Zoomu. Odkaz vám měl přijít e-mailem.

Cvičení v úterý od 15:40 na Zoomu vede Filip Štědronský.

Co se přednášelo

datum téma záznam
9. 3. Motivace: záhada transponování matice. Úvod do hlubin jazyka C11: Typový systém a reprezentace objektů (na co se lze spolehnout a na co už ne). Výrazy, literály a operátory. Viz Medvědův průvodce po Céčku. video tabule
9. 3. Pokračování na cvičení: Vedlejší efekty a synchronizační body. Aritmetika s ukazateli. Jak číst deklarace, kvalifikátory (const, volatile, restrict) a třídy uložení (static a spol.). Funkce a jejich deklarace. video tabule
16. 3. Pokračování Céčka: Příkazy. Preprocesor a pravidla nahrazování maker. Standardní knihovna. GCCčková rozšíření jazyka. video tabule
23. 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. video tabule
30. 3. Cache a jejich hierarchie. Správa paměti (MMU), TLB a jejich interakce s cachemi. Graf rychlosti přístupů k paměti a věštění z něj. video tabule
6. 4. Na okraj: Novinky v GCC. Ještě k paměti: sdílení TLB mezi procesy pomocí PCID; paměti SDRAM a jejich rozhraní (aproximace); co z toho plyne pro programátory? Jak procesor zpracovává instrukce. Pipelining, superskalární a out-of-order vykonávání, spekulativní vyhodnocování a predikce skoků. video tabule
13. 4. Techniky predikce skoků (podmíněných i nepřímých). Různé implementace architektury x86. Počítače s více procesory: SMP, protokoly MESI a MOESI pro koherenci cache, NUMA. video tabule
20. 4. Jak programovat na SMP: Procesy a vlákna, různá systémová rozhraní. Různá úskalí sdílení dat. 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ů. video tabule
27. 4. Sdílená paměť mezi procesy a její synchronizace, úskalí NUMA. 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á. video tabule
4. 5. Skutečný SMP hardware: Vícejádrové procesory, HyperThreading a Bulldozer. 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. Spusťte si na svém počítači machinfo (viz repozitář), co asi vypíše? video tabule
11. 5. Vektorové programování: MMX, SSEn, AVX, AVX-512. Další rozšíření instrukční sady: CRC32, AES, PEXT, … Netemporální přístup k paměti a prefetche. Jak se vektorové jednotky používají z Céčka. video tabule
18. 5. Odbočka: zoo znakových typů v Céčku. Co přinesl projekt Larrabee: Xeon Phi a AVX-512, 2D sběrnice ve Skylake. Další implementace x86: AMD Zen. Bezpečnostní problémy spekulativního vyhodnocování: různé druhy postranních kanálů, Meltdown. video tabule
25. 5. Bezpečnostní problémy: různé varianty Spectre, SSB, L1TF, MDS (a.k.a. Fallout, RIDL a ZombieLoad). Třídění: úvodní příklady. video tabule
1. 6. 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. Třídění s keší/diskem: více-cestný Mergesort a odpovídající dolní odhad. video tabule

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š