Algoritmy a jejich implementace

V letním semestru 2012/2013 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 pátek od 10:40 v S5.

Cvičení vedou Petr Pasky Baudiš a Láďa Láska. Obě cvičení jsou ekvivalentní, 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).
Pokračování na prvním cvičení: Výrazy, literály a operátory. Vedlejší efekty a synchronizační body. Viz Medvědův průvodce po Céčku.
1. 3. Céčko podruhé: Jak číst deklarace, kvalifikátory (const, volatile, restrict) a třídy uložení (static a spol.) Funkce, jejich deklarace (práce s va_listy viz cvičení). Příkazy. Preprocesor a pravidla nahrazování maker.
8. 3. Céčko potřetí: Standardní knihovna. Některá rozšíření GCC.
15. 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.
22. 3. Honza Hubička: Jak procesor zpracovává instrukce. Různé implementace architektury x86. Pipelines, scheduling instrukcí a predikce skoků.
29. 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ů (viz repozitář) na svém stroji a zamyslete se nad jeho výstupem.
5. 4. Vektorové instrukce – nahlédnutí do zvěřince (MMX, SSE, AVX). Netemporální přístup k paměti a prefetche.
12. 4. Počítače s více procesory: SMP, protokoly MESI a MOESI pro koherenci cache. Vícejádrové procesory, HyperThreading a Bulldozer. Stručně o sběrnicích. Spusťte si na svém počítači machinfo viz repozitář), co asi vypíše?
19. 4. Různé topologie víceprocesorových strojů, FSB, HyperTransport, QuickPath a NumaConnect. Directory-based koherence a HT-Assist.
26. 4. Jak programovat na SMP a NUMA. Procesy a vlákna a jejich synchronizace (thread-local storage, zámky, semafory a jejich implementace). Bezzámkové techniky: atomické instrukce, transakční paměť softwarová i hardwarová. Relativita pořadí zápisů. Paměťový model C11.
3. 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.
10. 5. Cache-oblivious algoritmy: definice I/O modelu, cache-oblivious a cache-aware modelů. Metoda Rozděl a panuj – třidění a násobení matic.
17. 5. Martin Kruliš: 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]
24. 5. Cache-oblivious algoritmy: van Emde-Boasovo uspořádání vyhledávacích stromů. Model kontra realita (odhad na kompetitivnost LRU). Třídění v I/O modelu a odpovídající dolní odhad.

Zkoušky

Ke zkoušce je potřeba zápočet a znalost odpřednesené látky (bez technických detailů). Na zkouškové termíny se prosím hlaste v SISu; po domluvě vás rád vyzkouším i jindy.

Odkazy

Stránku spravuje Martin Mareš