Efektivní implementace algoritmů

Přihlášení do KOSu pro zápis předmětu Zobrazit rozvrh

Kód	Zakončení	Kredity	Rozsah	Jazyk výuky
BI-EIA	Z,ZK	5	2+1	č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

Rozvrh na zimní semestr 2011/2012:

	06:00–08:0008:00–10:0010:00–12:0012:00–14:0014:00–16:0016:00–18:0018:00–20:0020:00–22:0022:00–24:00
Po	místnost T9:301 Šimeček I. 11:00–12:30 (přednášková par. 1) Dejvice NBFIT učebnamístnost T9:350 Šimeček I. 12:45–14:15 LICHÝ TÝDEN (přednášková par. 1 paralelka 101) Dejvice NBFIT PC ucebna
Út
St
Čt
Pá

Rozvrh na letní semestr 2011/2012:

Rozvrh není připraven

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