Algoritmy a jejich implementace

V letním semestru 2009/2010 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á každé úterý od 12:20 v S9.

Cvičení vede Petr Pasky Baudiš, můžete si vybrat buď sudé týdny od 9:00 nebo v liché od 11:00, obojí 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).
9. 3. Opět Céčko: Jak číst deklarace. Kvalifikátory (const, volatile, restrict). Operátory a typové konverze. Funkce, jejich deklarace a práce s va_listy. Pár slov o preprocesoru. Viz Medvědův průvodce po Céčku.
16. 3. Naposledy Céčko: Preprocesor a pravidla nahrazování maker. Standardní knihovna. Některá rozšíření GCC. Stručně o cachích.
23. 3. Honza Hubička: Jak procesor zpracovává instrukce.
30. 3. Jak číst přeložené programy. Základy assembleru na IA32/AMD64: registry, adresní módy, volací konvence. Různé překlady téhož programu.
6. 4. 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.
13. 4. Počítače s více procesory: SMP, protokoly MESI a MOESI pro koherenci cache, NUMA. Vícejádrové procesory a HyperThreading. Propojení procesorů: FSB, HyperTransport, QuickPath.
20. 4. Programování na více procesorech: procesy a vlákna, sdílení paměti, synchronizace procesů, atomické operace, proměnné lokální pro vlákno, jak se vyrovnat s NUMA. Zmínka o OpenMP a TBB.
27. 4. Vektorové instrukce: MMX a SSE. Příklad ze života: Třídění dat v paměti i na disku (jak jsme psali sorter pro LibUCW) aneb proč disk není páska.
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: definice modelu, násobení matic a jiné rozdělování a panování, vyhledávání v setříděných datech.
18. 5. Cache-oblivious algoritmy: model kontra realita (odhad na kompetitivnost LRU), van Emde-Boasovo uspořádání vyhledávacích stromů, trychtýřové třídění neboli funnelsort. [Detailní rozbor trychtýřů a důkaz věty o LRU jsem nestihl, takže je nebudu zkoušet. Vše najdete v textu od Erika Demaine zmíněném níže.]

Zkoušky

Na zkoušky se, prosím, přihlašujte v SISu; kdyby vám žádný termín nevyhovoval, dejte mi, prosím, vědět a domluvíme se. Ke zkoušce je potřeba zápočet.

Zkoušet budu základní přehled o probraných tématech (důležité je chápat principy, ne pamatovat si telefonní seznam) a teorii okolo cache-oblivious algoritmů. Také společně probereme zápočtový program – měli byste mít rozmyšleno, jak by se na váš problém daly aplikovat jednotlivé optimalizační techniky z přednášky. Nezapomeňte na:

Problémy pro inspiraci

Odkazy

Stránku spravuje Martin Mareš