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).
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. | eras | 5 | Prvocisla - 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. | wave | 5 | Vlneni 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. | lone | 5 | Odstranovani 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. | pixr | 5 | Horizontalni 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. | ir90 | 5 | Rotace 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:
| Student | Priklady | Bodu |
|---|---|---|
| "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 |
Plan je pouze predbezny! Temata kursivou nemuseji 1:1 odpovidat jednotlivym tydnum.