Algoritmy a jejich implementace

V letním semestru 2015/2016 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á ve čtvrtek od 9:00 v S9, cvičení ve středu od 9:00 v SU2.

Cvičení vede Jan Moskyto Matějka.

Co se přednášelo

datum téma
26. 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.
2. 3. 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.).
3. 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.
9. 3. Pokračování na druhém cvičení: Preprocesor a pravidla nahrazování maker.
10. 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.
17. 3. Ještě krátce o Céčku: standardní knihovna, GCCčková rozšíření jazyka. Úvod do cacheování.
24. 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.
31. 3. 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.
7. 4. Přednáška se nekoná.
14. 4. Techniky predikce skoků (podmíněných i nepřímých). Počítače s více procesory: SMP, protokoly MESI a MOESI pro koherenci cache. Vícejádrové procesory a HyperThreading.
21. 4. Jak programovat na SMP a NUMA. Procesy a vlákna a jejich synchronizace (atomické instrukce, thread-local storage, sdílení paměti, zámky, semafory). Příklad s frontou. Mnoho způsobů, jak si pořídit race condition, deadlock nebo livelock.
28. 4. Implementace zámků. Transakční paměť softwarová i hardwarová. Paměťový model C11. Skutečný SMP hardware: Vícejádrové procesory, HyperThreading a Bulldozer. Různé topologie víceprocesorových strojů, FSB, HyperTransport, QuickPath. Spusťte si na svém počítači machinfo (viz repozitář), co asi vypíše?
5. 5. Pokračování o víceprocesorových strojích. Zvyšujeme počet procesorů: NumaConnect, AMD Magny-Cours a triky v jeho implementaci L3 cache. Directory-based koherence a HT-Assist. Vektorové instrukce – nahlédnutí do zvěřince (MMX, SSE, AVX).
12. 5. Ještě k SSE: Netemporální přístup k paměti a prefetche. Vektorové programování v Céčku. Zmínka o AVX-512. 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.
19. 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.
26. 5. Cache-oblivious algoritmy: třídění v I/O modelu, odpovídající dolní odhad, náčrt funnelsortu.

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 složit až po zkoušce.

Odkazy

Stránku spravuje Martin Mareš