Algoritmy a jejich implementace

V letním semestru 2011/2012 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 středy od 15:40 v S3.

Cvičení vede Petr Pasky Baudiš. Cvičení existují dvě, vyberte si prosím jedno v SISu a zapište se na něj.

Co se přednášelo

datum téma
22. 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). Výrazy, literály a operátory. Viz Medvědův průvodce po Céčku.
27. 2. Na prvním cvičení jsme pokračovali v přednášce o Céčku: 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.
29. 2. Přednáška se nekoná – rektorský protestní den.
7. 3. Ještě jednou Céčko: Preprocesor a pravidla nahrazování maker. Standardní knihovna. Některá rozšíření GCC.
14. 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.
21. 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.
28. 3. Honza Hubička: Jak procesor zpracovává instrukce. Různé implementace architektury x86. Pipelines, scheduling instrukcí a predikce skoků.
4. 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.
11. 4. Přednáška pro nemoc odpadla.
18. 4. Vícejádrové procesory a HyperThreading. Různé topologie víceprocesorových strojů, FSB, HyperTransport, QuickPath a NumaConnect. Spusťte si na svém počítači machinfo, co asi vypíše?
25. 4. Jak programovat na SMP a NUMA. Procesy a vlákna a jejich synchronizace (zámky, semafory a futexy). Bezzámkové techniky: atomické instrukce, RCU, transakční paměť softwarová i hardwarová. Relativita pořadí zápisů.
2. 5. Petr Baudiš: 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. [loňské slidy]
9. 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.
16. 5. Rektorský den – přednáška se nekoná.
23. 5. Cache-oblivious algoritmy: násobení matic, van Emde-Boasovo uspořádání vyhledávacích stromů. Model kontra realita (odhad na kompetitivnost LRU).

Odkazy

Stránku spravuje Martin Mareš