Algoritmy a jejich implementace

V letním semestru 2014/2015 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 12:20 v S9, cvičení v pondělí od 9:00 v SU1.

Cvičení vedou Láďa Láska s Michalem Vanerem.

Co se přednášelo

datum téma záznam
24. 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. video
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.) Funkce, jejich deklarace. Příkazy. video
3. 3. Pokračování Céčka: Funkce s variabilním počtem parametrů. Preprocesor a pravidla nahrazování maker. Standardní knihovna. video
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. video
17. 3. Ještě krátce o Céčku: Některá rozšíření GCC. Cache a jejich hierarchie. video
24. 3. 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. video
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. video
7. 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. video
14. 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. video
21. 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? video
28. 4. 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). Netemporální přístup k paměti a prefetche. Vektorové programování v Céčku. Zmínka o AVX-512. video
5. 5. 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. video
12. 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. B-stromy a van Emde-Boasovo uspořádání vyhledávacích stromů. video
19. 5. Cache-oblivious algoritmy: Model kontra realita, odhad na kompetitivnost LRU. Dynamické cache-oblivious B-stromy (kombinujeme packed memory array, vEB uspořádané binární stromy a indirekci). video

Odkazy

Stránku spravuje Martin Mareš