Cviceni z implementace algoritmu

Ve skolnim roce 2011/2012 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? Cviceni ma dve paralelky - kazde pondeli od 17:20 v SU1 a kazde utery od 15:40 take v SU1. Na cviceni se zapisujte v SISu.

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 GPU. Snad se dozvite i par programatorskych zajimavosti.

A co zapocet? Dostanete jej za hrstku domacich ukolu a hlavne zapoctovy program. Na zapocet nebude mit vliv dochazka na cviceni (prestoze vrele doporucena).

Za domaci ukoly byste meli nasbirat behem semestru alespon 20 bodu. Ulohy budou spocivat v co nejefektivnejsi implementaci ruznych drobnejsich algoritmu. Presny zpusob bodovani ukolu viz nize. Preteceni ci nedosazeni celkove bodove hranice bude mit vliv na pozadovany rozsah zapoctaku.

Hlavni podminkou zapoctu je zapoctovy program. Ten by mel spocivat v ukazce efektivni zoptimalizovane implementace nejakeho konkretniho algoritmu; inspiraci muzete hledat napriklad na prastrance 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; mala diskuse nad zapoctakem bude (krome dotazu na probranou latku) i soucasti zkousky.

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 (vetsinou se ruzne zvedave vyptavam).

Domaci ukoly

Za ukol mate (zhruba) do 14 dnu od zadani co nejefektivneji naimplementovat v jazyce C reseni daneho problemu. Vase reseni musi jednak spravne odpovedet na nekolik testovacich vstupu, druhak bezet dostatecne rychle. Pro kazdy ukol je v systemu schovana rozumne implementovana (ale neprilis zoptimalizovana) referencni implementace; pobezite-li stejne rychle, dostanete 5b, pobezite-li pomaleji/rychleji, dostanete od 1b do 15b:

score = min(floor(5 * reftime/yourtime), 15)

6. 3. eras5Prvocisla - napiste program, ktery dostane jako parametr prirozene cislo n a na standardni vystup vypise pocet vsech prvocisel ≤ n. Program by mel zvladat hodnoty n v radech kolem 1010. (Muzete predpokladat alespon 64bitove longy, 64bitovy adresni prostor a radove 16GiB pameti.)
19. 3. wave5Vlneni obrazku - napiste pro aim-kit funkci exercise(), ktera vezme vstupni obrazek, vertikalne jej rozvlni a tuto podobu ulozi do vystupniho obrazku. Kazdy radek se posouva doprava, posun konkretniho radku vpravo odpovida funkci (unsigned int) (sin(y * M_PI*2 / 64) * 16 + 16) (minipriklad, vetsi priklad pred, po). Na pravem okraji vyteceny obsah zahazujte; vznikly prostor na levem okraji vyplnte barvou odpovidajici na kazdem radku puvodni leve hrane obrazku. Muzete se spolehnout, ze budete moci rychle pocitat s alespon 32-bitovymi cisly, a delka hrany obrazku bude cely nasobek 64. Mailem posilejte pouze obsah souboru exercise.c. Vas program se bude linkovat s parametrem -lm, muzete tedy pouzivat funkce standardni matematicke knihovny.
2. 4. lone5Odstranovani osamelych, smutnych pixelu - muzete tomu rikat treba redukce kontrastu nebo odstraneni sumu. Pokud pixel urcite barvy nema ani jednoho prilehleho (ne diagonalne) souseda stejne barvy, prebarvete jej na opacnou barvu (priklad). Odstranite tim jednopixelove "zrneni" v nekterych castech obrazku. (Rozmyslete se, jak byste se meli zachovat na okrajich obrazku.) Nase definice osamelych pixelu bude mit zajimave konsekvence u nekterych specialnich trid obrazku (pred, po). Muzete se spolehnout, ze budete moci rychle pocitat s alespon 32-bitovymi cisly, a delka hrany obrazku bude cely nasobek 64. Mailem posilejte pouze obsah souboru exercise.c.
17. 4. pixr5Horizontalni zrcadleni obrazku - obrazek otocte tak, aby prava hrana byla vlevo a naopak. Uloha sama o sobe neni tezka, ovsem vyjimecne mate za ukol se vyrovnat s obrazky zcela libovolnych rozmeru (delka hrany nemusi byt ani nasobek osmi; pred, po). Muzete se alespon spolehnout, ze budete moci rychle pocitat s alespon 32-bitovymi cisly. Mailem posilejte pouze obsah souboru exercise.c.
15. 5. ir905Rotace obrazku o 90 stupnu po smeru hodinovych rucicek (priklad). Muzete vyuzivat funkce knihovny libpthread (program je staven pomoci prikazu make aim-opt MYLDFLAGS=-pthread MYCFLAGS=-fopenmp). Zaroven si poradne rozmyslete, jak se chovat co nejefektivneji ke cachim procesoru. Nezapomente se podivat na vyse uvedene informace o hardware testovaciho stroje (je osmijadrovy!). Konkretni parametry klidne prizpusobte jemu, ale snazte se samozrejme mit implementaci co nejsnadneji upravitelnou na stroj s jinymi vlastnostmi. Muzete se spolehnout, ze budete moci rychle pocitat s alespon 32-bitovymi cisly, mit k dispozici SSE-4.2 a AVX instrukce, delka hrany obrazku bude cely nasobek 256 a obrazek bude ctvercovy. Mailem posilejte pouze obsah souboru exercise.c.

Reseni posilejte na e-mailovou adresu aim@kam.mff.cuni.cz; v subjectu uvedte pouze identifikator ukolu a v tele mailu pouze kod reseni. Napriklad v UNIXu prikazem cat zdrojak.c | mail -s kod aim@kam.mff.cuni.cz (s ruznymi privesky, ktere muze generovat treba Vas webmail, se zatim nevyrovname, klidne to z nej vsak alespon zkuste).

Do nekolika minut byste meli dostat zpet informaci o vysledcich. Zatim je nas vyhodnocovaci robot spise v testovacim provozu, takze kdyz se Vam nebude neco zdat, nevahejte se ozvat na aim@ucw.cz (to ctou skutecni lide).

Vase reseni budeme merit prelozene gcc-4.6.2 -lm -Wall -O3 -march=native -std=gnu99 na 8x AMD FX-8150 Bulldozer.

Reseni uzavrenych ukolu. (Pokud zatim v adresari reseni daneho ukolu zadne neni, muzete stale ziskavat body!)

Aktualni vysledky:

StudentPrikladyBodu
"Adam Juraszek" <juraszea@...> eras(15:6.50) lone(15:0.39975) 30
"Dominik Taborsky" <taborskd@...> eras(9) wave(12) 21
"Jakub Hajic" <j.hajic@...> eras(15:5.53) wave(11) 26
"Jan Benes" <benej5am@...> lone(10) wave(15:0.2295) 25
"Jan Tomasek" <tomasek.jan@...> eras(15:6.31) lone(2) wave(15:0.20075) 32
"Petr Fejfar" <fejfarp@...> eras(11) 11
"Roman Kucera" <kucer6am@...> eras(15:5.45) lone(15:0.362) pixr(14) wave(4) 48
"Stepan Havranek" <havranek.stepan@...> eras(15:6.58) 15
"Vaclav Obrazek" <obrazev@...> eras(14) lone(6) wave(2) 22
=?ISO-8859-1?Q?KarelKr=E1l?= <kralkareliv@...> eras(15:5.13) pixr(3) wave(4) 22
=?UTF-8?Q?Ond=C5=99ejMajerech?= <oxyd.oxyd@...> eras(13) 13
Martin Pelikan <pelikan@...> pixr(12) 12
Ondrej Majerech <oxyd.oxyd@...> pixr(7) 7
Petr Baudis <pasky@...> eras(6) ir90(5) lone(8) pixr(7) wave(8) 34
pasky@... wave(4) 4
tauferp@... eras(15:5.04) lone(15:0.31525) wave(15:0.1945) 45

Novinky ze cviceni

Plan je pouze predbezny! Temata kursivou nemuseji 1:1 odpovidat jednotlivym tydnum.

  1. Propojeni prvnich dvou prednasek - povidani o tajuplnych zakoutich C; viz stranky prednasky a Medveduv pruvodce po Cecku.
  2. Prakticke osvezeni jazyka C - prvocisla (txt). Binarni reprezentace cisel; bitove masky, efektivni zjistovani zajimavych vlastnosti (txt).
  3. Dalsi bitove triky (txt). Hratky s preprocesorem – tvorba praktickych maker (txt).
  4. [Utery: Linusovo hashovani.] Bitmapove obrazky, predstaveni AIM kitu (tarball, test16384.pbm) (txt). Uvod do zkoumani assembleru (txt). Review ukolu eras.
  5. Jak umi optimalizovat gcc? Druhy optimalizaci, prepinace a urovne optimalizace. (txt) Zkoumani assemblerove podoby programu (hello, eras). (txt)
  6. Zkoumani assemblerove podoby optimalizovanych programu (eras) - efekty ruznych optimalizaci.
  7. Profilovani a profile-driven optimalizace. (txt)
  8. Cache hierarchie a strategie pristupu do pameti. (txt)
  9. Vektorizace (vektorove typy, intrinsics, autovektorizace). Hammingova vzdalenost: hamming.c (noise noise1024, noise16384. Instruction reference od Intelu, Intrinsics reference od Intelu (od Ch. 35 - str. 1485). (txt)
  10. Nepovinna mezihra - fraktaly, stripky DSP (PCM a dithering), numericke metody. (SDL kit) Pouze v pondeli 7.5.
  11. Paralelizace (jemny uvod do pthreads, OpenMP). (txt)
  12. Pocitani na grafickych kartach (OpenCL). (OpenCL kit) (txt)

Edituje Petr Baudis. No counters, no frames, no syntax errors. Design borrowed from MJ.