Algoritmy a jejich implementace

V letním semestru 2016/2017 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. Viz též letáček.

Přednáška se koná v pondělí od 14:00 v S9, cvičení v úterý od 9:00 v SU1 vede Ondra Hlavatý.

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 prvním cvičení: Výrazy, literály a operátory. Vedlejší efekty a synchronizační body. Jak číst deklarace, kvalifikátory (const, volatile, restrict) a třídy uložení (static a spol.).
6. 3. Pokračování Céčka: Funkce, jejich deklarace. Příkazy. Funkce s variabilním počtem parametrů. Fáze překladu, úvod k preprocesoru.
7. 3. Pokračování na druhém cvičení: Preprocesor a pravidla nahrazování maker. Standardní knihovna, GCCčková rozšíření jazyka.
13. 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.
20. 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.
27. 3. Plán: Jak procesor zpracovává instrukce. Pipelining, superskalární a out-of-order vykonávání, spekulativní vyhodnocování a predikce skoků. Různé implementace architektury x86.

Odkazy

Stránku spravuje Martin Mareš