Efektivní implementace algoritmů

Předmět není vypsán Nerozvrhuje se

Kód	Zakončení	Kredity	Rozsah	Jazyk výuky
BI-EIA	Z,ZK	5	2P+1C	česky

Garant předmětu:

Přednášející:

Cvičící:

Předmět zajišťuje:

katedra teoretické informatiky

Anotace:

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ů.

Požadavky:

Předmět BI-EFA. Znalost programování v jazyce C nebo C++, pasivní znalost assembleru. Mít osvojené pojmy z oblasti architektury procesorů a pamětí.

Osnova 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 efektivních 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í

Osnova 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

Cíle studia:

Cílem předmětu je umět vytvořit efektivní, v praxi použitelné programy díky propojení znalostí ze SW a HW, které se často studují odděleně. Tento předmět se snaží spojit myšlenky obou v efektivní program na daném počítači (např. u asymptotické složitosti se multiplikativní konstanty „škrtají“, protože nejsou matematicky zajímavé, v praxi zajímavé jsou). Cílem je naučit studenty vytěžit z počítače maximum výkonu a naučit je poznat, že maxima dosáhli.

Studijní materiály:

Wolfe, M. ''High-Performance Compilers for Parallel Computing''. Addison Wesley, 1995. ISBN 0805327304.

Wadleigh, K. R., Crawford, I. L. ''Software Optimization for High Performance Computing: Creating Faster Applications''. Prentice Hall PTR, 2000. ISBN 0130170089.

Poznámka:

Informace o předmětu a výukové materiály naleznete na https://courses.fit.cvut.cz/BI-EIA/

Další informace:

https://courses.fit.cvut.cz/BI-EIA/

Pro tento předmět se rozvrh nepřipravuje

Předmět je součástí následujících studijních plánů: