Algoritmy a jejich implementace

V zimním semestru 2008/2009 budeme s Petrem Baudišem přednášet o tom, jak se algoritmy implementují na reálných počítačích. Tedy přednáška napůl teoretická, napůl praktická. 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.

Čas a místo: každou středu od 17:20 v S4.

Co jsme přednášeli

datum co se přednášelo
8. 10. Motivační příklad (sčítání prvků matice). Úvod do hlubin jazyka C99: typový systém a reprezentace objektů (na co se lze spolehnout a na co už ne).
Cvičeni: Jak zjistit, je-li číslo mocnina dvojky? Jak spočítat dvojkový logaritmus.
15. 10. Opakování Céčka: kvalifikátory, deklarace a inicializace, platnost a viditelnost objektů, aliasing ukazatelů.
Cvičeni: Jak změřit délku řetězce?
22. 10. Opakování Céčka: literály, operátory, typové konverze, funkce, va_list, preprocesor a pravidla nahrazování maker. Standardní knihovna.
29. 10. Paměťový subsystém: cache a jejich hierarchie, správa paměti a TLB. Grafy rychlosti přístupu: SR, SW, RR, RW.
Cvičeni: Spusťte si kreslítko grafů na svém stroji a vyvěštěte z jeho výstupu, jak velké máte cache. Pak to zkuste porovnat s tím, co se píše v /proc/cpuinfo a /sys/devices/system/cpu/.
5. 11. GCC a jeho rozšíření. Jak fungují paměti (příklad konfigurace DIMMu).
Cvičení: Jak generovat všechna čísla obsahující zadaný počet jedniček v binárním zápisu? Co udělá kreslítko z minulé přednášky při přístupech pomocí pole místo seznamu?
12. 11. Velmi stručně o assembleru. Zamyšlení nad výstupem z překladače. Ladící a profilovací prostředky: MALLOC_CHECK, Electric Fence, valgrind.
Přepínače GCC:
  • Optimalizace: -O2, -O3, -Os, -march, -mtune, -fomit-frame-pointer, -frename-registers, -DNODEBUG.
  • Dynamické optimalizace: -fprofile-generate, -fprofile-use.
  • Výstup v assembleru: -S, -fverbose-asm.
  • Testování pokrytí: --coverage, gcov,
  • Profilování: -pg, gprof.
Cvičení: Pohrajte si s reprezentací grafů.
19. 11. Ještě o profilování: OProfile. Opět o hardwaru: symetrické multiprocesorové počítače (SMP), koherence cachí a protokol M(O)ESI.
26. 11. Víceprocesorové a vícejádrové počítače a programování na nich: procesy, vlákna, základní synchronizační primitiva, atomické operace, proměnné lokální pro vlákno, OpenMP. Vektorové instrukce (MMX, SSE).
Úkol: Vyberte si příklad ke zkoušce a napište o tom na adresu aim@ucw.cz.
3. 12. 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.
10. 12. Jak procesor vykonává instrukce (Honza Hubička).
17. 12. Počítání na grafických kartách.
7. 1. Cache-oblivious algoritmy: definice modelu, násobení matic, Van Emde-Boasovo uspořádání vyhledávacích stromů, model kontra realita.
14. 1. Cache-oblivious algoritmy: odhad na efektivitu LRU, trychtýřové třídění neboli funnelsort, nástin konstrukce dynamických vyhledávacích stromů pomocí udržování posloupnosti (Ordered File Maintenance).

Zkoušky

Požadavky: Ke zkoušce byste měli zejména mít přehled o přednášených tématech (technické detaily netřeba znát). Mimo to byste si měli naprogramovat optimalizovanou implementaci nějakého (třeba i poměrně triviálního) algoritmu. Rozmyslete si, jak se na váš algoritmus dají použít optimalizační techniky zmíněné na přednášce, a alespoň některé z nich použijte. Také si rozmyslete, nebo ještě lépe změřte, kde váš program tráví většinu času, a navrhněte jak by se toto místo dalo vylepšit. Nezapomeňte na:

Termíny: standardně každou středu ve zkouškovém (vypsány v SISu, přihlašte se, prosím, tam); pokud se vám to nehodí, lze se domluvit individuálně.

Problém pro inspiraci

Odkazy

Stránku spravuje Martin Mareš