Cviceni z implementace algoritmu

Ve skolnim roce 2009/2010 vedu cviceni z predmetu Algoritmy a jejich implementace (NDMI074). Tady najdete podminky pro zapocet, seznam domacich ukolu, i vice ci mene detailni zpravodajstvi ze cviceni a odkazy souvisejici s tim, o cem budeme zrovna mluvit. Budete-li mit jakekoliv dotazy ci pripominky, nevahejte nam poslat mail nebo s nami promluvit osobne.

Kdy cviceni bude? Probiha ve dvou paralelkach, kazdy druhy ctvrtek v SU1. V sude tydny (4.3.) zacina v 9:00, v liche tydny (11.3.) je od 11:00 (sic). Na cviceni se zapisujte v SISu, podivnych atributu a virtualnich cviceni si prosim nevsimejte. Idealni bude, kdyz se nam obe paralelky podari drzet synchronizovane a web cviceni bude pouze jeden, uvidime v praxi.

Co od Vas ocekavame? Predpokladame, ze mate ucet v u-labu, umite alespon zaklady C, jiz jste nekdy videli UNIXovou prikazovou radku a snad si i nejaky Cckogram v UNIXu prelozili a spustili.

O cem cviceni bude? Podivejte se na plan nize. Budeme se soustredit na prakticke vyzkouseni si a zvladnuti zakladnich technik souvisejicich s implementaci vypocetne narocnych programu - bezne neefektivni a efektivni programatorske obraty ve vnitrnich smyckach, zkoumani moznosti optimalizace prekladacem, zpusoby a moznosti profilovani, ruzne moznosti paralelizace a zaklady programovani na (skutecnem) GPU. Cviceni probiha prvnim rokem, ocenime tedy Vasi trpelivost v pripade moznych mensich zadrhelu. :)

Za co nedostanete zapocet? Nebudeme sledovat ucast na cvicenich, ta Vam vsak snad ziskani zapoctu vyznamne usnadni. Budeme se sice snazit zadavat domaci ukoly, ty by Vam sice mely pomoci si latku osvojit, ale na zapocet take vliv nemaji.

Za co tedy dostanete zapocet? Za zapoctovy program. Ten by mel spocivat v ukazce efektivni zoptimalizovane implementace nejakeho konkretniho algoritmu; inspiraci muzete hledat napriklad na strance lonske prednasky. Nestaci jen ukazat zdrojak, budeme chtit i komentar o tom, na kterych mistech program travi nejvice casu (a proc), jak jste se pokusili uzka hrdla odstranit a proc si myslite, ze rychleji to jiz nepujde; dalsi mensi diskuse nad zapoctakem bude (krome dotazu na probranou latku) i soucasti zkousky.

Dokdy mate cas? Tema zapoctoveho programu byste si meli vybrat do pulky semestru, ocekavam, ze postupne zacnete jeste behem semestru pracovat i na implementaci. Tvrda deadline na odevzdani prvni verze zapoctaku bude zacatek zari, odevzdat finalni verzi zapoctaku byste meli nejpozdeji tyden pred zkouskou, abychom meli dostatecne casove buffery. Pocitejte s tim, ze v prubehu srpna budu pravdepodobne na mailu velmi zridka nebo mozna vubec.

Domaci ukoly

Ukoly si rozmyslete do dalsiho cviceni; budete-li mit nejasnosti nebo si nebudete jisti resenim, napiste nam! Nebude-li receno jinak, mela by byt vsechna reseni nejefektivnejsi dosazitelna.

Soutez

Vyhlasujeme soutez nejrychlejsich reseni ruznych domacich ukolu! Jak soutezit? Stahnete si AIM kit, rozbalte prikazem tar xvvfj aim-kit.tar.bz2 a nasledujte pokyny v README. Jako reseni posilejte pouze soubor exercise.c. Muzete reseni vylepsovat a posilat vicekrat.

Posledni termin na doruceni reseni bude pravdepodobne dva tydny pred koncem semestru. Posilejte reseni ulozek hmir, rt90 a scl8; dalsi budou pribyvat.

hmir

rt90

Novinky ze cviceni

Plan predbezny, asi neco pretece, mozna neco pribude, neco mozna zase zmizi, prehodime poradi, ...

1. Uvod do cviceni. Rozjimani nad binarni reprezentaci cisel, hledani bitu, ruzne bitove vlastnosti a zakladni manipulace. Uvod do template pro bitmapove obrazky, premysleni nad reprezentaci a nedostatky, benchmarkovaci minimum. Prvni ulozky: mrizovani a inverze.
2. Opakovani template apod. Mrizovani, inverze, vodorovne prevraceni. Ladeni implementace, mereni rychlosti (...vs cpufreq - je treba procesor "predehrat"), zakladni optimalizace (zvetsovani "vypocetni jednotky" z bitu az na slovo (ctyrbyte), problem s pocitanim meze cyklu podle pointeru), exkurze vygenerovanym assemblerem - co to je a jak se v tom vyznat, jemne zkoumani efektu switchiku a zvolene architektury.
3. [9:00] Vodorovne prevraceni - pokracovani v implementaci, soutez o nejrychlejsi program, mereni ruznych optimalizaci (velikost kroku, predpocitani mezi, tabulka), finalni analyza disassemblatu.
   [11:00] Kratky navrat k vodorovnemu prevraceni. Rotace bitmapoveho obrazku o 90 stupnu. Optimalizace zpusobu iterovani, velikosti bloku. (Priklad reseni.) Uvod do profilovani, principy + prace s gprof.
4. Rotace bitmapoveho obrazku o 90 stupnu, testy a optimalizace ruznych nastaveni, hypotezy o chovani cachi. Uvod do profilovani, principy + prace s gprof. Pattern-matching (patm), hrani si s podminkami, vyhybani se podminkam, profile-driven optimization (-fprofile-generate, -fprofile-use).
5. Pocitani hammingovy vzdalenosti mezi obrazky - vektorizace, SIMD intrinsics a vektorove rozsireni gcc, jak primet prekladac k autovektorizaci. Na zaver navrat k oprofile, ukazka pouziti, mereni chovani cachi pri rotaci obrazku.
6. Pocitani na GPU. Principy CUDA (alokace threadu, oblasti pameti), uvod do syntaxe a prace s SDK (v labu najdete dokumentaci v /opt/cuda/doc, zdrojaky spousty prikladu v /opt/cuda/sdk; informace o zarizeni viz /opt/cuda/sdk/bin/linux/release/deviceQuery). Inverze bitmapy, klasicky mrizovaci efekt. Nacali jsme: Scalovani bitmapy 8:1 resp. mosaic efekt (ctverecky 8x8), kresleni Mandelbrotovy/Juliovy mnoziny. Skupina od 9:00 se sejde mimoradne jeste jednou pristi tyden od 9:00 a budeme si dale hrat s CUDA, tentokrat snad bez sw emulace.