Algoritmy a jejich implementace
V letním semestru 2024/2025 přednáším o tom, jak se algoritmy implementují na reálných počítačích [NDMI074]. 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ů.
Čas konání se bude umlouvat.
Odkazy
- Repozitář s materiály k přednášce:
- Videozáznamy z přednášek z roku 2021
- 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
- Popis paměťového modelu C11 v CPP Reference
- 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)
- Zábava: