BI-EIA – Efektivní implementace algoritmů

Cíl předmětu

Studenti se naučí kombinovat svě programátorské dovednosti (schopnost tvořit efektivní algoritmy) a znalost HW (využití všech dostupných rysů architektur procesorů a paměťové hierarchie). Studenti se naučí i ladit a optimalizovat výkonnost a efektivnost algoritmů.

Program přednášek

  1. Opakování základních pojmů z architektur (pipeline, cache paměti, TLB).
  2. Nové architekturní rysy moderních procesorů.
  3. Paralelní (vícejádrové) architektury.
  4. Popis rozhraní OpenMP.
  5. Efektivní algoritmy, asymptotická složitost a její nevýhody v inženýrské praxi.
  6. Volba optimální datových struktur a jejich kombinací.
  7. Základní rutiny pro numerické lineární algebry (husté matice).
  8. Základní rutiny pro numerické lineární algebry (řídké matice).
  9. Metody transformací zdrojových kódů I.
  10. Metody transformací zdrojových kódů II.
  11. Kompilátory a optimalizace.
  12. Modely chování skryté (cache) paměti.
  13. Modely chování sdílených skrytých (cache) pamětí.

Program cvičení

  1. Seznámení s vybavením učebny.
  2. Výkonnostní ukazatele.
  3. Algoritmy pro vyhledávání prvku.
  4. Algoritmy pro vyhledávání v textu, vyhodnocení logických výrazů.
  5. Profilování kódu pomocí čítačů událostí, zadání úlohy č. 1
  6. Experimenty s nastavením kompilátoru.
  7. Řazení ve vnitřní paměti.
  8. Řazení ve vnější paměti, odevzdání úlohy č. 1
  9. Algoritmus FFT a modelování interakce více částic, zadání úlohy č. 2
  10. Grafové algoritmy, zadání úlohy č. 3
  11. Šifrování, komprese dat, odevzdání úlohy č. 2
  12. Dostupné matematické knihovny
  13. Odevzdání úlohy č.3, zápočet



Poslední změna: 10.7.2010, 23:15