Logo ČVUT
ČESKÉ VYSOKÉ UČENÍ TECHNICKÉ V PRAZE
STUDIJNÍ PLÁNY
2018/2019

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
Přednášející:
Ivan Šimeček (gar.)
Cvičící:
Ivan Šimeček (gar.)
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:

Rozsah=prednasky+proseminare+cviceni:2p+1c

Další informace:
Pro tento předmět se rozvrh nepřipravuje
Předmět je součástí následujících studijních plánů:
Platnost dat k 23. 5. 2019
Aktualizace výše uvedených informací naleznete na adrese http://bilakniha.cvut.cz/cs/predmet1124806.html