Algoritmy a jejich implementace

V letním semestru 2010/2011 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 párovací haldy a cache-oblivious algoritmy.

Přednáška se koná ve středy od 9:00 v S4.

Cvičení vede Petr Pasky Baudiš, koná se hned po přednášce v SU1, alternativní cvičení v pondělky od 17:20 taktéž v SU1.

Co se přednášelo

datum téma
2. 3. Motivace. Úvod do hlubin jazyka C99: Typový systém a reprezentace objektů (na co se lze spolehnout a na co už ne). Výrazy a příkazy. Synchronizační body. Jak číst deklarace, kvalifikátory (const, volatile, restrict) a třídy uložení (static a spol.) Funkce, jejich deklarace a práce s va_listy. Pár slov o preprocesoru. Viz Medvědův průvodce po Céčku.
9. 3. Ještě jednou Céčko: Preprocesor a pravidla nahrazování maker. Standardní knihovna. Některá rozšíření GCC.
16. 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.
23. 3. Cache a jejich hierarchie. Správa paměti, TLB a jejich interakce s cachemi. Graf rychlosti přístupů k paměti a věštění z něj. Spusťte si kreslítko grafů na svém stroji a zamyslete se nad jeho výstupem.
30. 3. Honza Hubička: Jak procesor zpracovává instrukce.
6. 4. Vektorové instrukce – nahlédnutí do zvěřince (MMX, SSE, AVX). Počítače s více procesory: SMP, protokoly MESI a MOESI pro koherenci cache.
13. 4. Vícejádrové procesory a HyperThreading. Různé topologie víceprocesorových strojů, FSB, HyperTransport, QuickPath a NumaConnect. Jak programovat na SMP a NUMA.
20. 4. Jestě trocha SMP: zámky a semafory, lockless techniky – atomické instrukce, RCU, transakční paměť (STM). Příklad ze života: Jak jsme programovali sorter pro LibUCW).
27. 4. Pokračování o sorteru: externí třídění aneb proč disk není páska. Úvod do cache-oblivious algoritmů.
4. 5. Martin Krulíš: Počítání na grafických kartách. Srovnání CPU vs. GPU. Framework OpenCL. Příklad s násobením matic a jeho optimalizace. [slidy]
11. 5. Cache-oblivious algoritmy: násobení matic, van Emde-Boasovo uspořádání vyhledávacích stromů.
18. 5. Rektorský den – přednáška se nekoná.
25. 5. Cache-oblivious algoritmy: model kontra realita (odhad na kompetitivnost LRU), trychtýřové třídění neboli funnelsort.
Zmínka o LibUCW (slidy).

Odkazy

Stránku spravuje Martin Mareš