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. 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.
3. 4. Počítače s více procesory: SMP, protokoly MESI a MOESI pro koherenci cache. Jak programovat na SMP. Procesy a vlákna a jejich synchronizace (atomické instrukce, thread-local storage, sdílení paměti, zámky, semafory). Příklad s frontou.
10. 4. Mnoho způsobů, jak si pořídit race condition, deadlock nebo livelock. Granularita zámků. Implementace zámků. Transakční paměť softwarová i hardwarová. Paměťový model C11. NUMA. Spusťte si na svém počítači machinfo (viz repozitář), co asi vypíše?
17. 4. Ēostre, Paasfees, Великден, Ülestõusmispühad, Πάσχα, Páskar, 復活祭, Pace.
24. 4. 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.
25. 4. Náhradní přednáška od 10:40 v S221 (chodba 2. patro východ). Vektorové instrukce – nahlédnutí do zvěřince (MMX, SSE, AVX). Netemporální přístup k paměti a prefetche. Vektorové programování v Céčku. Zmínka o AVX-512.
9. 5. Náhradní přednáška od 10:40 v S221 (chodba 2. patro východ). 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.
15. 5. Cache-oblivious algoritmy: definice I/O modelu, cache-oblivious a cache-aware modelů. Násobení matic metodou Rozděl a panuj, "fraktální" reprezentace matic. Model kontra realita, odhad na kompetitivnost LRU.
22. 5. Cache-oblivious algoritmy: vyhledávání, van Emde-Boasova reprezentace binárních stromů, třídění v I/O modelu, odpovídající dolní odhad.

Odkazy

Stránku spravuje Martin Mareš