Algoritmy a jejich implementace

V letním semestru 2013/2014 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ředu od 15:40 v S4, cvičení ve čtvrtek od 15:40 v SU2.

Cvičení vede Láďa Láska.

Co se přednášelo

datum téma
26. 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).
27. 3. Pokračování na prvním cvičení: Výrazy, literály a operátory. Vedlejší efekty a synchronizační body. Jak číst deklarace, kvalifikátory (const, volatile, restrict) a třídy uložení (static a spol.) Viz Medvědův průvodce po Céčku.
5. 3. Céčko podruhé: Funkce, jejich deklarace, práce s va_listy. Příkazy. Preprocesor a pravidla nahrazování maker.
6. 3. Pokračování na druhém cvičení: Standardní knihovna. Některá rozšíření GCC.
12. 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.
19. 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.
26. 3. Jak procesor zpracovává instrukce. Různé implementace architektury x86. Pipelines, scheduling instrukcí a predikce skoků. (Přednášel Láďa Láska.)
2. 4. Ještě k přístupům k paměti. Vektorové instrukce – nahlédnutí do zvěřince (MMX, SSE, AVX). Netemporální přístup k paměti a prefetche.
9. 4. Vektorové programování v Céčku. Zmínka o AVX-512. Počítače s více procesory: SMP, protokoly MESI a MOESI pro koherenci cache. Vícejádrové procesory, HyperThreading a Bulldozer. Spusťte si na svém počítači machinfo (viz repozitář), co asi vypíše?
16. 4. Různé topologie víceprocesorových strojů, FSB, HyperTransport, QuickPath a NumaConnect. Příklad ze života: AMD Magny-Cours a triky v jeho implementaci L3 cache. Directory-based koherence a HT-Assist.
23. 4. Jak programovat na SMP a NUMA. Procesy a vlákna a jejich synchronizace (thread-local storage, sdílení paměti, zámky, semafory a jejich implementace). Bezzámkové techniky: atomické instrukce, transakční paměť softwarová i hardwarová. Mnoho způsobů, jak si pořídit race condition nebo deadlock.
30. 4. Programování na NUMA. Relativita pořadí zápisů. Paměťový model C11. 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.
7. 5. Cache-oblivious algoritmy: definice I/O modelu, cache-oblivious a cache-aware modelů. Násobení matic metodou Rozděl a panuj, "fraktální" reprezentace matic. Model kontra realita.
14. 5. Místo přednášky se koná rektorský sportovní den.
21. 5. Cache-oblivious algoritmy: odhad na kompetitivnost LRU, B-stromy a van Emde-Boasovo uspořádání vyhledávacích stromů. Třídění v I/O modelu a odpovídající dolní odhad (důkaz jsme nestihli, najdete ho v článku od Aggarwala a Vittera).

Zkoušky

Ke zkoušce je potřeba zápočet a znalost odpřednesené látky (bez technických detailů hardwaru). 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š