Algoritmy a jejich implementace

V letním semestru 2018/2019 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 a zajímavou teorii s překvapivými výsledky v praxi – například cache-oblivious algoritmy.

Přednáška se koná v úterý od 10:40 v pracovně S322. Cvičení ve středu od 17:20 v SU1 vede Filip Štědronský.

Co se přednášelo

datum téma
27. 2. 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). Viz Medvědův průvodce po Céčku.
28. 2. Pokračování na cvičení: Výrazy, literály a operátory. Vedlejší efekty a synchronizační body.
5. 3. Pokračování Céčka: Aritmetika s ukazateli. Jak číst deklarace, kvalifikátory (const, volatile, restrict) a třídy uložení (static a spol.). Funkce, jejich deklarace. Příkazy.
6. 3. Pokračování na cvičení: Funkce s variabilním počtem parametrů. Fáze překladu. Preprocesor a pravidla nahrazování maker.
12. 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.
13. 3. Pokračování na cvičení: Standardní knihovna, GCCčková rozšíření jazyka.
19. 3. Cache a jejich hierarchie. Správa paměti, TLB a jejich interakce s cachemi. Paměti SDRAM a jejich rozhraní (aproximace). Co z toho plyne pro programátory? Graf rychlosti přístupů k paměti a věštění z něj. Spusťte si kreslítko grafů (viz repozitář) na svém stroji a zamyslete se nad jeho výstupem.
26. 3. Drobnosti: va_arg na AMD64, sdílení TLB mezi procesy pomocí PCID. Jak procesor zpracovává instrukce. Pipelining, superskalární a out-of-order vykonávání, spekulativní vyhodnocování a predikce skoků. Techniky predikce skoků (podmíněných i nepřímých). Různé implementace architektury x86.
2. 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é druhy atomických operací, bariéry, thread-local storage.
9. 4. Programování na SMP: sdílení paměti, zámky, semafory, condition variables. Příklad s frontou. Mnoho způsobů, jak si pořídit race condition, deadlock nebo livelock. Granularita zámků. Implementace zámků a futexy. Transakční paměť softwarová i hardwarová.
16. 4. Plán: Paměťový model C11. Zámky ve sdílené paměti mezi procesy. NUMA. 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?

Odkazy

Stránku spravuje Martin Mareš