Algoritmy a jejich implementace
V letním semestru 2020/2021 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, vektorové výpočty, pokročilé techniky profilování a metody návrhu algoritmů přátelských ke keším. Také zabrousíme do témat týkajících se bezpečnosti procesorů.
Přednáška se koná v úterý od 14:00 na Zoomu. Odkaz vám přijde e-mailem.
Cvičení v úterý od 15:40 na Zoomu vede Filip Štědronský.
Začínáme 9. 3.
Odkazy
- Repozitář s materiály k přednášce:
- Videozáznamy z přednášek z roku 2015
- Různé texty k přednášce:
- Céčko a Unix:
- Norma jazyka C11
- Single Unix Specification v4 (nástupce POSIXu)
- System V ABI (pro 32-bitový mód; na Linuxu berte s rezervou)
- AMD64 ABI (64-bitový mód)
- Dokumentace ke GCC
- comp.lang.c FAQ (pozor, mírně zastaralé)
- přednáška Jonase Skeppstedta o paralelním programování, v níž je mimo jiné pěkně převyprávěn paralelní paměťový model C11
- Hardware:
- What Every Programmer Should Know About Memory od Ulricha Dreppera
- Sandpile – prakticky vše o procesorech x86/amd64
- Dokumentace od procesorů AMD a GPU ATI (za přečtení stojí zejména AMD64 Architecture Programmer's Manual a Software Optimization Guide)
- Totéž od Intelu
- Optimalizační triky:
- Bit Hacks – různé triky s čísly a bitovými operacemi
- Software optimization resources Agnera Foga
- Teorie:
- Practical Data Structures – bakalářská práce Michala Pokorného, mimo jiné o cache-oblivious datových strukturách
- Cache-Oblivious Algorithms and Data Structures – úvodní text od Erika Demaine
- The I/O Complexity of Sorting and Related Problems (A. Aggarwal, J. S. Vitter)
- Cache-Oblivious B-Trees (M. A. Bender, E. D. Demaine, M. Farach-Colton)